Prefix Compression and Suffix Truncation in Index Pages

Keys in an index are rarely random. They are timestamps that share a date, identifiers that share a prefix, strings that share a namespace, composite keys whose leading column is a low-cardinality status. Storing each key whole pays for the shared bytes once per entry, and in a page of adjacent sorted keys the shared bytes are most of the page. Compression exploits that, and the price is a search that can no longer binary search the page directly.

The layout that makes the sharing visible

A compressed leaf page stores, for each entry, the length of the prefix it shares with the previous entry, the length of the remaining suffix, and the suffix bytes. Entries are laid out sequentially, so recovering an entry requires knowing the previous one: entry $i$‘s key is the first shared[i] bytes of entry $i-1$‘s key followed by entry $i$‘s suffix.

The first entry of the page has no predecessor and is therefore stored with its prefix length set to zero — the whole key. That is not a quirk; it is what makes the page independently readable. A reader that lands on the page from the internal node’s separator has no state from the previous page, so the first key must be self-contained. The same rule applies at the level of the compressed block inside a file: the first key of every block is stored whole, and those keys are what the block index records.

The savings are large when the prefix is large. Take two adjacent keys of 30 bytes each, order:2024-03-17T09:15:22.481Z and order:2024-03-17T09:15:22.913Z. They share the first 26 bytes, so the second entry is a shared-length byte, a suffix-length byte, and 4 suffix bytes — 6 bytes against 30, a factor of five on that entry. Not every pair in the page shares as much, and the first entry of the page shares nothing, so the realized saving over a whole page is smaller than the best case, but a factor of two to four on a timestamp-keyed page is ordinary. The fanout arithmetic then improves by the same factor, which is the point: compression is not primarily about disk space, it is about how many keys fit in a page, and therefore how shallow the tree is and how much of it stays cached.

Restart points and the cost of a sequential dependency

A search inside a compressed page cannot binary search entries, because reaching the middle entry requires decoding every entry before it. The shape of the dependency is visible in the decode loop:

/* Decode entries [restart, target] into prev, leaving the key at target there.
 * Each iteration needs the previous key's bytes, so the loop cannot be
 * vectorised or reordered: it is a chain of dependent loads. */
static void decode_to(const uint8_t *base, int restart, int target, key *prev)
{
    const uint8_t *p = base + offset_of(restart);
    prev->len = read_u16(p);                 /* restart entries are whole keys */
    memcpy(prev->bytes, p + 2, prev->len);
    p += 2 + prev->len;
    for (int i = restart + 1; i <= target; i++) {
        uint32_t shared = *p++;              /* prefix shared with prev */
        uint32_t suffix = *p++;
        memcpy(prev->bytes + shared, p, suffix);
        prev->len = shared + suffix;
        p += suffix;
    }
}

The loop is short and the arithmetic is trivial; the cost is that each iteration must finish before the next address is known. The standard resolution is to break the page into groups and store the first entry of each group uncompressed. Those positions are restart points: a search binary searches the restart array, decodes forward from the chosen restart point, and finds the target. A page with 256 entries and restart points every 16 has 16 restart keys, so locating the group costs 4 comparisons and locating the entry within the group costs up to 16 decodes: 20 steps against 8 for a binary search over an uncompressed page of the same entry count, and against 256 for a linear decode of the whole page. The interval sets where between those two extremes the page sits.

The interval is a direct trade. A longer interval compresses better, because fewer entries are stored whole, and searches within a group decode more entries. A shorter interval searches faster and stores more full keys. The optimum depends on whether the page is read often enough for search cost to dominate, which is why some formats let the interval be configured per column family and why the default tends toward a small power of two rather than a large one.

Decoding forward is cheap per entry but it is a serial dependency chain: each entry’s length fields must be read before the next entry’s position is known. On a modern processor that chain is a sequence of dependent loads with unpredictable addresses, and each may miss. A page with 16-entry groups therefore has a search cost measured in cache misses rather than in comparisons, and the reason a compressed page can be slower to search than an uncompressed one even though it holds more keys is precisely this chain. The win comes at the level above: fewer pages means fewer page reads, and a page read is much more expensive than a handful of cache misses.

Suffix truncation is a different mechanism

Prefix compression exploits what adjacent keys share. Suffix truncation exploits what they do not: when a leaf splits, the separator written to the parent need only distinguish the two halves, so it can be cut to the shortest prefix that still separates them.

The rule is a consequence of the routing convention. With separators belonging to the right child, a separator $s$ between a left leaf whose maximum is $L$ and a right leaf whose minimum is $R$ must satisfy $L < s \le R$. Any string in that interval works, and the shortest such string is what truncation stores.

Computing it is a byte walk over the two boundary keys. Take the common prefix of $L$ and $R$, then look at the first byte where they differ. Let $L$‘s byte there be $l$ and $R$‘s be $r$, with $l < r$. A separator of the common prefix plus a single byte in the range $(l, r]$ satisfies $L < s \le R$ and is one byte longer than the common prefix, no matter how long $R$ is. If $l + 1 = r$ the only choice is $r$ itself, and the separator is the common prefix plus $R$‘s byte, which is a prefix of $R$. If $l + 1 < r$, any byte strictly between them also works and produces a separator that is a prefix of neither boundary key.

When $L$ is a prefix of $R$ there is no differing byte, and the shortest separator is $L$ with one byte appended, chosen above the next byte of $R$ if the encoding leaves room. That is the case where truncation saves least: the separator is as long as the shorter boundary key plus one byte.

The saving therefore depends on how much of $R$ extends past the point where the two keys diverge. A leaf boundary between invoice-2024-000981 and invoice-2024-001004 diverges at the sixteenth byte, where 9 meets 1, so the separator is the fifteen shared bytes plus 1, three bytes shorter than the right key. A boundary between abc and abcd saves nothing, because the shorter key is a prefix of the longer and the separator must be four bytes.

One consequence is that a truncated separator may be a prefix of keys in the right leaf, or a string that appears in no leaf at all. Both are safe for routing, because routing only compares. They are not safe for a consumer that treats an internal page as a source of key values, which is why scans that read keys from the index read leaf pages only.

For integer keys, truncation rarely helps because the encoding is fixed-width. For string keys with a common prefix it is the dominant win, and it is why an index on long strings can have a fanout close to that of an index on short ones. Formats that combine it with prefix compression store the truncated separator as the entry in the internal page, so the internal page’s keys are not keys at all but fragments, and the routing predicate must be evaluated against fragments rather than against values.

What compression does to updates

An entry’s compressed size depends on its predecessor, so inserting an entry in the middle of a page can change the encoded size of the entry after it. The shared-prefix length of the following entry is computed against the new predecessor, and it may be longer or shorter. This means an insert is not a local byte edit; the page must be rebuilt from the insertion point to the end, or at least have its following entries re-encoded.

The cost is bounded by the page, and a page rebuild is what the engine does anyway when it inserts into a page with no free space. But it changes the calculus for in-place updates: an engine that tries to insert a few bytes into a page without rebuilding it cannot do so under prefix compression, because the byte offsets after the insertion point all shift and the length fields change. The usual implementation decodes the page into an array of offsets on first access, works on the decoded form, and re-encodes on write. That is more work per modification and much less work per read, which suits read-heavy indexes and is why write-heavy indexes often disable page-level prefix compression in favour of block-level compression applied to whole pages.

Whole-page compression is the alternative: compress the page as a unit with a general-purpose algorithm, decompress on read, recompress on write. It compresses better in many cases, because a general algorithm can exploit structure that prefix compression ignores, and it makes every access pay a decompression cost even for a search that would have touched one entry. The choice between per-entry prefix compression and whole-page compression is therefore a choice about where to put the cost: in the search inside the page, or in every access to the page.

Deduplication and the many-versions case

An index on a low-cardinality column has long runs of identical keys, and prefix compression handles them poorly: each entry shares its entire key with the predecessor, so the suffix is empty and the entry is two length bytes plus the tie-breaker. The tie-breaker is what makes the entries distinct, and it is also what makes the run incompressible.

Some engines deduplicate: a page stores the distinct key once and then a list of row identifiers that share it. The encoding is a posting list per key rather than an entry per key, which collapses a long run into one key plus a delta-encoded list of identifiers. The search becomes a search for the key followed by a scan of the list, and the page holds far more rows than an entry-per-row layout. The cost is that the list must be scanned for every lookup of a duplicated key, which is fine for a lookup returning few rows and poor for one returning many, and the list must be split across pages when it outgrows one, which reintroduces the boundary problem that unique keys avoid.

The same mechanism, taken to its extreme, is the posting list of an inverted index, where the key is a term and the payload is the set of documents. The index page then holds one key and a compressed list, and the boundary between the index and the search structure disappears. That is the point at which the access path has become a different data structure, and the compression techniques are the same ones: delta encoding, block packing, and restart points.

Measuring whether compression paid

The effect of compression is visible in three places, and they can disagree. Page count falls, which reduces the height and the buffer pool footprint. Search cost inside a page rises, which raises CPU per lookup. Write cost per modification rises, because re-encoding touches the rest of the page. An index that is read once per write benefits; one that is written once per read does not.

The honest measure is the product: pages touched per operation times cost per page, with the cost per page including the decode. A tree that drops from four levels to three because of compression saves a page read on a fraction of lookups and pays a decode on every page it does touch, and whether that is a win depends on how many of the pages were cached. That is why compression settings are workload parameters rather than universal defaults, and why the concurrent descent machinery that protects the page during a rebuild has to be aware of the encoding, since a latch held across a decode and re-encode is held much longer than a latch around an in-place byte write.