Index Compression

Index Compression

MemCP indexes map ordered or matched values to compact record-ID sets and ranges. Main index state is stored with the rebuilt shard; an ordered index-local delta structure covers newer rows. Iteration merges both while respecting deletions, transaction visibility, and requested direction.

Traditional trees store keys, child pointers and node slack. MemCP can exploit an immutable shard generation differently: sort a compact permutation of RecordIDs by the indexed columns, then binary-search column values through that permutation. Inserts do not splice into the immutable main array; the delta index covers them until rebuild. Wide strings therefore need not be copied into every tree entry.

For a shard whose RecordIDs fit in 16 bits, 60,000 permutation entries need roughly 120 kB before surrounding metadata. Actual size varies with representation, shard size and auxiliary boundaries; inspect current statistics instead of treating that illustration as a guarantee.

The essential data structure can be read from this reduced historical sketch. Current code adds transactions, delta ordering, richer boundary types and cost evidence, but the pointer-free permutation remains the central idea:

<syntaxhighlight lang="go">type StorageIndex struct {

   columns     []string
   savings     float64
   sortedItems StorageInt // RecordIDs sorted by column values
   inactive    bool       // collect evidence before building

}</syntaxhighlight>

Rows compare through columns[0], then columns[1], and so on. A lookup binary-searches the compressed RecordID permutation and reads the indexed column values from column storage. The index therefore avoids storing a second copy of wide keys and avoids one heap pointer per entry.

The planner can build adaptive equality, range, prefix, computed-expression, and compact membership structures when observed workload and cost justify them. RecSets may carry exact record sets or safe candidate supersets; candidate sets retain a residual predicate. Index selection is a physical decision after logical decorrelation and join ordering.

Boundary extraction and reuse

Conjunctions can provide equality prefixes followed by at most one useful ordered range, for example a = ? AND b = ? AND c BETWEEN ? AND ?. Canonical column/expression identities allow related queries to share an index. A longer compatible index can serve a shorter prefix, avoiding a second physical structure. LIKE-prefix and other inexact matchers may return candidates and keep the original predicate as proof.

Adaptive build decision

A syntactically possible index starts as an opportunity, not an immediate allocation. The analyzer estimates full-scan cost, build cost, indexed probe cost, shard population and expected reuse. Evidence accumulates until the projected savings amortize construction. Small shards may never build; ORDER/LIMIT benefit is weighted by the number of rows it can actually avoid.

An early postcode experiment recorded an 8.275 ms full scan, an 18.188 ms scan that also built the index, followed by indexed lookups of 43.871, 45.681 and 39.021 µs. That observation motivated the original “build on the second use” heuristic. It lacks a current commit, dataset details, repetitions and result validation, so the figures are retained as design history rather than a current 200× claim. The current cost model is richer: creation should be paid for by observed future work, not triggered by every possible WHERE clause.

Index size and performance depend on cardinality, clustering, fingerprint/range choices, update rate, and query distribution. A B-Heap layout was proposed to improve cache locality while traversing a tree; it remains an interesting future representation, not part of the supported current index. Persisted index formats obey the same permanent magic/version compatibility contract as columns.

See Data Auto Sharding and Auto Indexing, Scan, and Query Planner and Physical Lowering.