Index Compression: Difference between revisions

From MemCP
Jump to navigation Jump to search
(Created page with "== Memory-Efficient Indices for In-Memory Storages == Most databases implement indices as a kind of tree. I will show you that columnar storages can do even better. The most widely used kind of tree structure in databases is the B-Tree. A B-Tree is a n-ary tree whose nodes fit exactly into one „page“ – may it be a cache line of 64 bytes or a HDD page of 512 bytes or a memory page of 4K. The advantage of btrees is that it balances the memory fetch time with the ti...")
 
(Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference)
Line 1: Line 1:
== Memory-Efficient Indices for In-Memory Storages ==
<!-- Copyright (C) 2026 Carl-Philip Haensch -->
Most databases implement indices as a kind of tree. I will show you that columnar storages can do even better.
<!-- SPDX-License-Identifier: GPL-3.0-or-later -->
= Index Compression =


The most widely used kind of tree structure in databases is the B-Tree. A B-Tree is a n-ary tree whose nodes fit exactly into one „page“ – may it be a cache line of 64 bytes or a HDD page of 512 bytes or a memory page of 4K.
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.


The advantage of btrees is that it balances the memory fetch time with the time spent on computing on a chunk of memory. A btree node is basically layouted like <code>pointer|value|pointer|value|pointer|value|pointer</code>
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.


This means, half of the space of the index is wasted on pointers, the other half is wasted on values. Latter is problematic when values get wide – especially when dealing with strings.
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.


We will provide a different approach for indices that are far more memory efficient and thus faster in in-memory storage engines: '''sorted list indices'''.
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:


== Sorted lists of Record IDs ==
<syntaxhighlight lang="go">type StorageIndex struct {
In contrast to OLTP databases that need fast insert and delete procedures, in a separated main and delta storage, we don’t have to care about insert performance because we never insert into the main storage. When items are inserted, they are inserted into the delta storage and the main storage is rebuilt on demand. Deletions are also easy to handle. When scanning through a table, we can just ignore deleted items.
    columns    []string
    savings    float64
    sortedItems StorageInt // RecordIDs sorted by column values
    inactive    bool      // collect evidence before building
}</syntaxhighlight>


So instead of storing pointers and values (where on multidimensional indices, values can span multiple columns), we can just store the recordId. For a 10k items storage, this would require less then 20KiB of RAM ! The list of recordIds can then be sorted according to our sort criterion and compressed into a bit compressed integer storage.
Rows compare through <code>columns[0]</code>, then <code>columns[1]</code>, 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.


Whenever we want to find a certain item or a range of items, we can now walk through the sorted list of recordIds and perform our binary search algorithms.
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.


This is the data structure I came up with:
== Boundary extraction and reuse ==
type StorageIndex struct {
        cols []string // sort equal-cols alphabetically, so similar conditions are canonical
        savings float64 // store the amount of time savings here -> add selectivity (outputted / size) on each
        sortedItems StorageInt // we can do binary searches here
        t *table
        inactive bool
}
Here some facts:


* <code>cols</code>is the list of columns that are considered in the index
Conjunctions can provide equality prefixes followed by at most one useful ordered range, for example <code>a = ? AND b = ? AND c BETWEEN ? AND ?</code>. 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.
* The list of sorted recordIds is stored in <code>sortedItems</code>
* The items are sorted according to the value of <code>cols[0]</code>; in case of equality, <code>cols[1]</code> is considered and so on
* In the beginning, we set <code>inactive</code> to true, so the index is ''considered'' but not built
* In <code>savings</code>, we accumulate the amount of computation time we could save by having the index
* As soon as <code>savings</code> exceeds a threshold, the index is built. Otherwise, we will do a full table scan.
* The index implements <code>func (s *StorageIndex) iterate(lower []scmer, upperLast scmer) chan uint</code> which will start a index scan beginning at <code>lower</code> and will stop as soon as the last column reaches a value greater than <code>upperLast</code>. When <code>inactive</code> is set, the function will instead increase the <code>savings</code> value and stream all recordIds of the table


== Finding the Perfect Index for a Certain Condition ==
== Adaptive build decision ==
In memcp, we use scheme – a lisp dialect – as the internal query plan language. This has one big advantage: Every piece of code is an array that can be examined by our optimizer.


We implemented a helper function <code>func (t *table) iterateIndex(condition scmer) chan uint</code> that takes a condition, finds the perfect index or creates it and then streams all recordIds that ''might'' fit into the condition into a ring buffer (<code>chan uint</code>)
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.


So we define a datatype like:
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.
type columnboundaries struct{
        col string
        lower scmer
        upper scmer
}
And then collect all conditions into a variable <code>cols</code> of the type <code>[]columnbounbdaries</code>. For doing so, we implemented a recursive function <code>traverseCondition(condition scmer)</code> that scans the condition for <code>equal?</code>, <code><</code>, <code>></code>, <code><=</code>, <code>>=</code> as well as <code>BETWEEN ... AND ...</code> and <code>IN</code> expressions. Whenever a column value is compared against a constant, we can fill in a <code>columnboundaries</code> object.


After collecting all boundaries, we sort <code>cols</code> according to the following rules:
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.


* <code>equals?</code> is more selective than <code><</code> or <code>></code> comparisons, so we put all boundaries with <code>lower == upper</code> first
See [[Data Auto Sharding and Auto Indexing]], [[Scan]], and [[Query Planner and Physical Lowering]].
* An index scan can only consider one range column (as long as we don’t use spatial indices), so we can only keep one boundary with <code>lower != upper</code>
* To save memory, we sort all <code>equals?</code>-boundaries alphabetically by the column name, so that similar SQL queries can use the same index
* Instead of an index (col1, col2), the already existing index (col1, col2, col3) can be used as an alternative
 
As soon as the perfect index constellation is found, we create the <code>StorageIndex</code> object, but set it to <code>inactive</code> first. We then delegate the task of filling a <code>chan uint</code> to the <code>StorageIndex</code> object by calling <code>func (s *StorageIndex) iterate(lower []scmer, upperLast scmer) chan uint</code>
 
== Automatic Index Building and Cost Calculation ==
We did some measurements on the performance of on-the-fly index building:
> (scan "PLZ" (lambda (Ort) (equal? Ort "Neugersdorf")) (lambda (PLZ Ort) (print PLZ " - " Ort)))
02727 - Neugersdorf
==> "8.275433ms"
> (scan "PLZ" (lambda (Ort) (equal? Ort "Neugersdorf")) (lambda (PLZ Ort) (print PLZ " - " Ort)))
building index on PLZ over [Ort]
02727 - Neugersdorf
==> "18.187862ms"
> (scan "PLZ" (lambda (Ort) (equal? Ort "Neugersdorf")) (lambda (PLZ Ort) (print PLZ " - " Ort)))
02727 - Neugersdorf
==> "43.871µs"
> (scan "PLZ" (lambda (Ort) (equal? Ort "Neugersdorf")) (lambda (PLZ Ort) (print PLZ " - " Ort)))
02727 - Neugersdorf
==> "45.681µs"
> (scan "PLZ" (lambda (Ort) (equal? Ort "Neugersdorf")) (lambda (PLZ Ort) (print PLZ " - " Ort)))
02727 - Neugersdorf
==> "39.021µs"
>
The first query did an unoptimized table scan with 8.3ms
 
The second query did the index build with 18.2ms
 
The third query already uses the index and only needs 42µs – this is a speedup of almost 200x!
 
So you see: A index build is about twice the cost as a full table scan. This means, as soon as a index is used the second time, we can build the index and remove the <code>inactive</code> flag. When we increase <code>savings</code> by 1.0 every time the index is used and build the index at a threshold of 2.0, we will have the optimal heuristic for index creation.
 
When a table is rebuild, we can of course take over our measurements stored in the <code>savings</code> variable to start the index build a bit earlier.
 
== Increasing Cache-Locality by using the B-Heap ==
B-Heaps are a novel concept. They are described in https://github.com/launix-de/memcp/blob/master/storage/index.go but are not implemented yet. They promise more cache-locality while scanning an index.

Revision as of 11:59, 28 August 2026

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.

Retrieved from "https://www.memcp.org/index.php?title=Index_Compression&oldid=336"