We currently use a uint32 for segment.DocID, which limits the maximum number of documents per segment to 4B. The primary motivation for this is lack of support for uint64 in RoaringBitmap. We should revisit this if we ever see this becoming an issue.

Instead of the encode/decoder types we have in index/encoding, would be good to consolidate on a single one.

We should have a high level example of how to use m3ninx. Specifically, it should include:

• how to create an index (segment currently)
• how to insert documents
• how to search for documents

Need a method on Segment which returns an estimate for the number of documents it contains. It can be a rough approximation.

Intent is to use this during a background process in m3db (ticking) to emit metrics ~= cardinality.

We've got a quite a few data points indicating we should re-work our postings list implementation/API, they are:

• Support for postings.ID to be uint64 (#12)
• Benchmark numbers showing upstream Roaring is worse than Pilosa
• We're using Pilosa's serialisation mechanism for the FST segment, as a result are having to double serialise/deserialise when accessing data. i.e. on write it goes from our roaring implementation -> pilosa's -> []byte. And reverse that order for reads. Can avoid an extra hop by just using Pilosa directly.

The points above clearly indicate we should use Pilosa instead of upstream roaring. Further, when re-working the APIs we should consider:

• Our current postings lists implementation currently wraps all access in a RWMutex. This made sense when all we had was a mutable segment. But it's not required when we've got immutable mmap'd data.
• Impact of immutability semantics on the postings list itself: the postings list in mutable segments only need Add() as a mutator.
• Pooling of postings lists: upstream roaring's implementation does not lend itself to pooling. We should revisit this with Pilosa, and immutability (i.e. if we can pool cheaply, an immutable API would be even more tempting).
• Implications of Seek() ahead, which is required for efficient posting list merging at query time.

Currently, mem segments support everything golang/Regexp will compile; fs segments support a subset of that (e.g. Vellum has DFA state limits, no support for zero-width assertions, etc).

We need to make this uniform across the two.

Add the following methods to idx/query.go:

func Marshall(Query) ([]byte, error) { ... }
func Unmarshall([]byte) (Query, error) { ... }

Can eliminate Query.SearchQuery() after that.

String keys require extra allocs that we could avoid if we rolled with our own hashmap implementation. We should evaluate the perf impact of doing so and make the corresponding changes.

Doing so also opens up the possibility of using a map hidden from the GC ("native"/mmap'd), which we should look into too.

There's a bug in the upstream FST library's handling of FSTs with a single empty string. Our fs segment has this bug for now.

Here's the current API spec for two methods on the Segment type:

type Segment interface {
  Fields() ([][]byte, error)
  Terms([]byte) ([][]byte,error)
} 

The return types as [][]byte have a number of detriments:

• Can't pool the underlying []byte (no easy way for user to finalise and return)
• Have to alloc the entire [][]byte upfront
• Can't wrap underlying iterators. e.g. we could wrap vellum's FST iterator if returned an iterator ourselves

Other factors to consider:

• We could enforce lexicographical ordering on the returned iterators, which would be useful when constructing FSTs, and the iterators returned by FST would natively satisfy this.
• Could tie-lifecycle of the iterator being returned to the segment's lifecycle - e.g. FST iterator wrapper would only be valid for as long as the iterator itself.