Daniil Medovich

Building a flat inverted index for high-cardinality workloads

EN RU

TL;DR. A mutable inverted index for high-cardinality data spends much of its memory on representation rather than payload. A flat layout fixes that by putting term bytes in one arena, keeping term metadata in an indexed array, storing the first posting inline, and allocating positions only when they are used. Exact lookup remains hash-based; prefix lookup comes from a small, lazily built lexicographic view.

The workload shapes the index

An inverted index maps a term to the documents that contain it:

"timeout"       -> [{doc: 4, count: 2}, {doc: 19, count: 1}]
"trace.7f31..." -> [{doc: 9, count: 1}]

Natural-language text and observability data produce very different term distributions. Text has a relatively stable vocabulary and long posting lists. Logs and traces contain request IDs, trace IDs, IP addresses, attribute names, generated paths, and error values. A large fraction of those terms occur in exactly one document.

That changes the optimization target. Tree traversal depth still matters, but bytes and allocations per unique term become equally important. An index with fast lookup can still be expensive if a million one-document terms create a million backing arrays and a large graph of heap objects.

The mutable stage also needs more than exact lookup. It must support prefix queries, phrase positions, concurrent reads, snapshots, and export into an immutable segment. The challenge is to add those capabilities without turning the compact exact path back into a general-purpose tree.

Why map[string][]Posting is not actually flat

The obvious Go representation is concise:

type Index struct {
    terms map[string][]Posting
}

Its logical model is correct, but its physical model is costly at high cardinality. The map stores a string header and a slice header for every term. Term bytes live in separate backing storage. Every non-empty posting slice needs another backing array. Growth creates new arrays and copies old data. The garbage collector must scan the resulting object graph.

When most posting lists contain one element, the slice machinery can cost as much as the posting itself. The problem is not asymptotic complexity; it is representation overhead multiplied by term cardinality.

HAMT, radix tree, and flat storage

A hash array mapped trie partitions a hash into small chunks and walks a fixed-depth tree. It offers predictable exact lookup and handles hash distribution well. A sliced radix tree compresses shared prefixes and makes prefix traversal natural. Both are useful layouts, but both maintain structural objects that a high-cardinality exact-heavy workload may rarely benefit from.

The flat index follows a different rule: make the common representation dense, then add secondary views only for operations that need them. It is not a universally better index. It is a layout specialized around a large term set, a high percentage of df=1 terms, and an append-oriented mutable phase.

Memory layout: arena, entries, and collision chains

The index has five storage areas:

                         map[uint64]int32
term bytes -> FNV-1a -> collision-chain head
                              |
                              v
                     entries[] by int32 index
                   +-------------------------+
                   | token offset / length   |
                   | first posting           |
                   | remaining postings      |
                   | next collision          |
                   +-------------------------+
                         |              |
                         v              v
                 shared byte arena   optional positions[entry]

secondary view: termOrder[]int32 (built only when needed)

All term bytes are appended to one []byte arena. An entry refers to a term with a 32-bit offset and length. The exact-search map stores a 64-bit hash and a 32-bit entry index, not a string and not a pointer to a term object.

type entry struct {
    first    Posting
    rest     []Posting
    tokenOff uint32
    tokenLen uint32
    next     int32
}

A hash is only a routing hint. Multiple terms may share it, so each map value points to a collision chain. Every candidate is verified against the original bytes in the arena. The index therefore preserves exact semantics: a hash collision can make lookup slower, but it cannot produce a false match.

Inlining the first posting

The first posting is stored directly in the entry. The rest slice remains nil until the term reaches a second document:

df = 1  -> entry.first
df = 2  -> entry.first + entry.rest[0]
df = N  -> entry.first + entry.rest[0:N-1]

This is a small-object optimization for posting lists. It removes a backing-array allocation from the most common high-cardinality case while keeping ordinary slice behavior for terms that grow. Repeated occurrences in the same document increment Posting.Count instead of adding duplicate document references.

Ordered postings without sorting every search

Document ordinals normally arrive in increasing order. In that path, adding a new document is an O(1) append and adding another occurrence to the current document is an O(1) count update.

A library index cannot assume that all callers preserve this order. When a smaller ordinal arrives, the index uses binary search to find its position. An existing posting is updated in place; a new one is inserted into the sorted slice. This cold path costs O(df) because insertion moves elements, but it pays that cost once. Search, snapshot, and export no longer sort the same posting list repeatedly.

The sequence value is derived from the document ordinal, so keeping postings ordered also preserves stable result order across terms and snapshot round trips.

Positions without enlarging every entry

Phrase search needs token positions per document. Putting a [][]uint32 field into every entry would add a slice header even to an exact-only index. Instead, positions live in a separate parallel table that grows only as far as positional entries require:

entries[42]        -> postings for "timeout"
positions[42][0]  -> positions in the first document
positions[42][1]  -> positions in the second document

Insert never allocates positional metadata. InsertAt grows the table and records a position. If an out-of-order document is inserted, its position list moves together with its posting. Positions inside one document are also kept sorted, which lets the same data be exported directly into a sealed segment.

Positional search allocates result descriptors, but their position slices share read-only backing storage with the index. Copying every position on every phrase query would defeat the purpose of retaining them in memory.

Exact search stays simple

Exact lookup has four steps:

  1. Hash the query term.
  2. Read the collision-chain head from map[uint64]int32.
  3. Compare query bytes with arena bytes for each candidate.
  4. Return a copy of the already ordered postings.

No prefix structure or positional table is touched. Optional capabilities therefore do not add branches or pointer chasing to the main lookup path.

Prefix search without a prefix tree

A flat hash index has no natural prefix traversal. Scanning every term for every prefix query would work, but it would ignore the fact that term bytes can be ordered once and reused.

The secondary termOrder view contains only 32-bit entry indices sorted by their arena bytes. It is built lazily on the first prefix search, serialization, or segment export. Adding a new term invalidates it implicitly because its length no longer matches the entry array.

A prefix query performs a binary lower-bound search, then walks the contiguous matching range:

termOrder: api, apple, apply, trace, tracing
query:     "app"
                 ^ lower bound
matches:  apple, apply
stop:                 trace

Postings from matching terms are merged by document ordinal and their counts are added. The first query after new terms arrive pays for sorting; subsequent prefix queries use the cached view. This does not make a flat index a radix tree. A radix tree still has the stronger traversal structure for prefix-dominant workloads. The secondary view is a compact compromise for mixed workloads.

Concurrency and immutable segments

The mutable index uses an RWMutex. Insertions take the write lock; exact and positional searches take a read lock. Rebuilding termOrder briefly takes the write lock, then prefix search continues under a read lock.

Segment export also runs against the lexicographic view under a read lock. The callback receives term bytes, ordered postings, and cloned position lists from one consistent state. Writers wait until export finishes, so sealing cannot observe half of an insertion.

This creates a useful lifecycle boundary: the flat index is optimized for building and querying the active mutable set; the sealed segment owns the compact read-only representation, checksums, and file-backed access modes.

FLT2: a snapshot that can reject bad input

A mutable snapshot must restore enough information to continue indexing, including positions. The second snapshot version has this logical layout:

magic "FLT2"
term count
repeated terms:
    token length
    token bytes
    posting count
    repeated postings:
        delta-encoded document ordinal
        term frequency
        position count
        positions
CRC32

Terms are written lexicographically and postings by ordinal. Delta encoding keeps common ordinal gaps small. The loader checks the total snapshot size, term count, token length, posting count, integer bounds, strict ordinal order, position order, duplicate terms, trailing bytes, and checksum before publishing an index.

New snapshots use FLT2; the loader still accepts positionless FLT1 snapshots. Versioning the format is preferable to guessing whether bytes after a posting count are positions or the beginning of the next term.

Tests should describe invariants

Feature tests alone are not enough for an index. The important properties are the relationships that must survive every code path:

  • posting ordinals remain strictly ordered after arbitrary insertion order;
  • term frequency changes do not change sequence values;
  • positions stay aligned with postings during insertion and serialization;
  • a rebuilt prefix view includes terms added after the previous query;
  • concurrent prefix searches and inserts expose consistent snapshots;
  • mutable snapshots and sealed segments return the same postings;
  • corrupt checksums and malformed lengths fail instead of returning partial data.

The suite also keeps a 10,000-term high-cardinality case and runs the concurrency paths under Go's race detector. Sequence tests mirror the HAMT and radix implementations so the backends are compared against the same behavioral contract.

Benchmarks, with the usual warning

The three mutable backends use the same synthetic setup: 500 terms, 500 documents, and 20 occurrences per document. Insert benchmarks create a unique term per iteration. The numbers below were measured on an AMD Ryzen 5 2600 with Go 1.26.4:

operation             flat          sliced radix       HAMT
Insert                692-709 ns    949-1068 ns        1161-1359 ns
InsertAt              917-999 ns    1037-1151 ns       1079-1207 ns
Exact Search          165-176 ns    171-191 ns         446-455 ns
Positional Search     399-426 ns    403-448 ns         381-412 ns
Prefix Search         159-171 us    172-187 us         -

For unique-term insertion, the flat index used 419-485 bytes and two allocations per operation. The sliced radix index used 579-638 bytes and three allocations; the HAMT used 589-661 bytes and six allocations.

These are microbenchmarks, not a ranking for every dataset. They mostly demonstrate that adding prefix and positional capabilities did not require giving up the compact exact path. Real selection should use the application's vocabulary distribution, posting-list lengths, prefix-query rate, sealing cadence, and memory profile.

Choosing by workload

The flat layout is a good fit when the active index has many unique terms, exact lookup dominates, documents usually arrive in ordinal order, and the index is periodically sealed. A radix tree remains attractive when prefix traversal is the central operation and shared prefixes are abundant. A HAMT remains useful when hash-partitioned lookup and its fixed traversal shape match the workload.

The larger lesson is that an index is not only its lookup algorithm. The memory layout determines how many objects exist, which bytes share cache lines, what the garbage collector must scan, and how expensive it is to cross from mutable state into an immutable segment. At high cardinality, those properties are part of the algorithm.