columnar

README

Columnar Collections & Querying

This package is my experimental attempt in building a fast, in-memory columnar collections in Go. The basic idea is to arrange property bags (i.e. map[string]interface{}) into columns and be able to write queries effiently around them. Under the hood, this uses roaring bitmaps extensively to provide fast comparisons and selection.

Features

• Columnar (Structures of Arrays) data layout for very fast iteration over large sets of data
• Zero heap allocation (or close to it) inside the library (see benchmarks below)
• Querying capability with filtering (aka "where" clause) and projections (aka "select" clause)
• Using dense and fast bitmaps for indexing and free/fill-lists

Example usage

// oldHumanMages returns a query which performs a full scan on 3 different columns and compares
// them given the specified predicates. This is not indexed.
func oldHumanMages(filter columnar.Query) {
	filter.WithString("race", "human").
		WithString("class", "mage").
		WithFilter("age", func(v interface{}) bool {
			return v.(float64) >= 30
		})
}

// oldHumanMagesIndexed returns an indexed query which uses exlusively bitmap indexes, the result
// will be the same as the query above but the performance of the query is 10x-100x faster
// depending on the size of the underlying data.
func oldHumanMagesIndexed(filter columnar.Query) {
	filter.With("human").With("mage").With("old")
}

func main(){

	// Create a new columnar collection
	players := columnar.New()

	// index on humans
	players.Index("human", "race", func(v interface{}) bool {
		return v == "human"
	})

	// index for mages
	players.Index("mage", "class", func(v interface{}) bool {
		return v == "mage"
	})

	// index for old
	players.Index("old", "age", func(v interface{}) bool {
		return v.(float64) >= 30
	})

	// Load the items into the collection
	for _, v := range loadFixture("players.json") {
		players.Add(v)
	}

	// How many human mages over age of 30? First is unindexed (scan) while the
	// second query is indexed based on the predefined indices built above.
	count := players.Count(oldHumanMages)
	count := players.Count(oldHumanMagesIndexed)

	// Same condition as above, but we also select the actual names of those 
	// players and iterate through them
	players.Find(oldHumanMagesIndexed, func(o Object) bool {
		fmt.Println(o["name"]) // outputs the name
		return true
	}, "name")
}

Benchmarks

cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
BenchmarkCollection/add-8              5004789    234.1 ns/op     82 B/op    0 allocs/op
BenchmarkCollection/fetch-to-8        92310531    12.28 ns/op      0 B/op    0 allocs/op
BenchmarkCollection/count-8            1653796    725.2 ns/op      0 B/op    0 allocs/op
BenchmarkCollection/count-indexed-8   23074526    51.51 ns/op      0 B/op    0 allocs/op
BenchmarkCollection/find-8             1207858    996.8 ns/op    336 B/op    2 allocs/op
BenchmarkCollection/find-indexed-8     3986691    303.9 ns/op    336 B/op    2 allocs/op

Documentation

Index

• type Collection
  • func New() *Collection
  • func (c *Collection) Add(obj Object) uint32
  • func (c *Collection) Count(where func(where Query)) int
  • func (c *Collection) Fetch(index uint32) (Object, bool)
  • func (c *Collection) FetchTo(idx uint32, dest *Object) bool
  • func (c *Collection) Find(where func(where Query), fn func(Object) bool, props ...string)
  • func (c *Collection) Index(name, property string, fn IndexFunc)
  • func (c *Collection) Remove(idx uint32)
• type IndexFunc
• type Indexer
• type Mutator
• type Object
• type Query
  • func (q Query) With(index string) Query
  • func (q Query) WithFilter(property string, predicate func(v interface{}) bool) Query
  • func (q Query) WithString(property string, value string) Query
  • func (q Query) Without(index string) Query

Types

type Collection

type Collection struct {
	// contains filtered or unexported fields
}

Collection represents a collection of objects in a columnar format

func New

func New() *Collection

New creates a new columnar collection.

func (*Collection) Add

func (c *Collection) Add(obj Object) uint32

Add adds an object to a collection and returns the allocated index

func (*Collection) Count

func (c *Collection) Count(where func(where Query)) int

Count counts the number of elements which match the specified filter function. If there is no specified filter function, it returns the total count of elements in the collection.

func (*Collection) Fetch

func (c *Collection) Fetch(index uint32) (Object, bool)

Fetch retrieves an object by its handle

func (*Collection) FetchTo

func (c *Collection) FetchTo(idx uint32, dest *Object) bool

FetchTo retrieves an object by its handle into a existing object

func (*Collection) Find

func (c *Collection) Find(where func(where Query), fn func(Object) bool, props ...string)

Find ...

func (*Collection) Index

func (c *Collection) Index(name, property string, fn IndexFunc)

Index creates an index on a specified property

func (*Collection) Remove

func (c *Collection) Remove(idx uint32)

Remove removes the object

type IndexFunc

type IndexFunc = func(v interface{}) bool

IndexFunc represents a function which can be used to build an index

type Indexer

type Indexer interface {
	Index() bitmap.Bitmap
}

Indexer represents an index contract

type Mutator

type Mutator interface {
	Set(idx uint32, value interface{})
	Get(idx uint32) (interface{}, bool)
	Del(idx uint32)
}

type Object

type Object map[string]interface{}

Object represents a single object

type Query

type Query struct {
	// contains filtered or unexported fields
}

Query represents a query for a collection

func (Query) With

func (q Query) With(index string) Query

With applies a logical AND operation to the current query and the specified index.

func (Query) WithFilter

func (q Query) WithFilter(property string, predicate func(v interface{}) bool) Query

WithFilter applies a filter predicate over values for a specific properties. It filters down the items in the query.

func (Query) WithString

func (q Query) WithString(property string, value string) Query

WithString ...

func (Query) Without

func (q Query) Without(index string) Query

Without applies a logical AND NOT operation to the current query and the specified index.