Page Compression: Prefix, Dictionary, and the Cost of Decoding

A page is written and read as a whole block, and most of its bytes are redundant. Keys share prefixes, timestamps share high-order bits, status columns cycle through a handful of values, and text repeats the same words. Compression converts that redundancy into fewer bytes on the device, and the question that decides whether it is worth doing is not the compression ratio but where the decompression work lands relative to the operations around it.

Three places compression can sit

The first choice is what is compressed, and it determines the cost structure entirely.

Transparent block compression compresses the page as an opaque byte string and stores it in fewer device blocks, decompressing on read into a full-size in-memory page. The device sees fewer bytes; the engine sees an ordinary page. This is what file-system-level or tablespace-level compression does, and it is the least invasive option because nothing above the I/O layer knows it happened.

Page-internal compression encodes individual records or columns within the page while keeping the page structure intact. The directory still points at records, but a record’s bytes are in a compressed representation and must be decoded before its fields can be read. This allows partial decompression: a query that reads one column of a wide row does not decode the others, if the layout groups columns together.

Dictionary and code compression replaces frequent values with small integers and stores the mapping once per page or per file. The savings depend on cardinality: a column with ten distinct values can be encoded in four bits per row, while a column that is nearly unique gains nothing and costs the dictionary.

The second choice is when decompression happens, and this is the one with architectural consequences. Decompressing at read time into the buffer pool means the pool holds uncompressed pages: memory usage is unchanged, and the benefit is entirely in I/O bytes. Decompressing on demand, field by field, means the pool can hold the compressed form and fit more logical pages in the same memory — but every access pays a decode, and the pool’s page identifier no longer maps to a fixed-size frame.

Prefix truncation and the sorted-page advantage

The cheapest useful compression in an index exploits the fact that a B-tree page is sorted. Adjacent keys share a prefix, often a long one: timestamps within the same hour, strings under the same namespace, composite keys with a repeated leading column.

Prefix truncation stores, for each key, only the bytes that differ from its predecessor, plus a length. Reconstruction requires decoding keys in order from the start of the page, because key n depends on key n−1. That dependency is the trade: a binary search within the page is no longer possible without first materializing the keys, so either the page keeps a sparse set of restart points — every 16th key stored in full — or the search degrades to a scan. The restart points are what make the format searchable; a page with restart points every 16 keys costs an average of 8 decodes to locate a key, plus the binary search over the restart array.

/* Front coding with restart points: decode forward from the nearest anchor. */
static int decode_key(const uint8_t *base, uint32_t target_idx,
                      const uint32_t *restart_offsets,
                      const uint16_t *restart_lengths, key_t *out) {
    uint32_t r = target_idx / RESTART_INTERVAL;
    uint32_t off = restart_offsets[r];
    memcpy(out->buf, base + off, restart_lengths[r]);
    out->len = restart_lengths[r];
    for (uint32_t i = r * RESTART_INTERVAL + 1; i <= target_idx; i++) {
        uint32_t shared = base[off];          /* bytes shared with previous key */
        uint32_t suffix = base[off + 1];
        memcpy(out->buf + shared, base + off + 2, suffix);
        out->len = shared + suffix;           /* prefix is already in place */
        off += 2 + suffix;
    }
    return 0;
}

The format above is the shape used by LevelDB’s block format and by several index implementations: a shared-length byte, a suffix-length byte, and the suffix. The decode is a forward walk, so the cost of a lookup depends on the distance from the nearest restart point, not on the page size.

Dictionaries and the cardinality threshold

A per-page dictionary is worth building when a column has low cardinality relative to the page’s row count. The arithmetic is straightforward: a dictionary of d entries with average length L costs d·(L + overhead) bytes, and each row’s value is replaced by an index of ⌈log₂ d⌉ bits. The encoding wins when the per-row saving exceeds the dictionary cost amortized over the rows on the page.

Two failure modes follow. A page with few rows cannot amortize a dictionary, so the same column may be dictionary-encoded on one page and stored raw on another, which means the reader must handle both encodings. And a dictionary built from a sample that does not represent the page’s values produces entries that are never referenced, or values that fall outside the dictionary and must be stored as exceptions. Both are handled by storing a per-page encoding descriptor in the page header — a few bytes that tell the reader which encodings are active — at the cost of a branch on every field access.

Global dictionaries, shared across all pages of a column, amortize far better but introduce a dependency: the dictionary must be loaded before any page can be decoded, and it must be versioned so that pages written under an older dictionary remain readable. This is why global dictionaries in column stores are immutable once written and are referenced by an identifier stored in each page.

Run-length and delta encoding

Sorted data admits stronger compression than prefix sharing. If a column is sorted and clustered, consecutive values often differ by small amounts, so delta encoding stores the differences rather than the values. A timestamp column with one-second resolution stored as 64-bit values becomes a sequence of small integers, each of which fits in one or two bytes with a variable-length encoding.

Run-length encoding collapses repeated values into a value and a count. It is extremely effective on data that arrives in runs — a status column in an append-only log, a sorted dimension key — and useless on randomly ordered data, where the average run length is close to one and each run costs more to store than the value it replaces.

Both encodings make random access expensive. Reaching the n-th value in a run-length-encoded block requires summing counts from the start of the block; reaching the n-th delta requires summing all preceding deltas. Column stores solve this with a sparse index that records cumulative counts at block boundaries, so a lookup starts from the nearest boundary and decodes forward. That is the same restart-point idea as prefix truncation, applied at a coarser granularity.

Where the decode cost lands

The decisive question is whether decompression competes with the operations that would otherwise use the CPU. For a scan of a large table, the alternative to decompression is reading more bytes from the device; if the device is the bottleneck, compression is a pure win because the CPU work is free relative to the saved I/O. If the data is already in memory — a buffer pool that holds the working set — the alternative to decompression is nothing, and the decode is pure cost.

That is why compression settings that help an I/O-bound analytic workload can hurt a latency-sensitive transactional one. A point lookup that decompresses a 16 KiB page to read 100 bytes pays the full page decode, and the decode is serial work on the critical path of a single query. Prefix-truncated index pages mitigate this because decoding stops at the target key, but block-compressed heap pages do not: the unit of decompression is the whole block.

Compression also interacts badly with the buffer pool’s accounting. If the pool holds compressed pages, the frame size is variable, and the fixed-size frame array no longer maps one-to-one to pages. Engines that do this use a separate cache for compressed blocks, sized by bytes rather than by frames, with eviction over variable-size objects — a different data structure, not a parameter change. The pool’s hash table also changes meaning: a page identifier maps to a compressed block that must be decompressed into a scratch buffer, and that scratch buffer is a shared resource that must be latched, reintroducing the contention that per-frame buffers avoided.

What compression does to the write path

A compressed page that is modified must be decompressed, modified, and recompressed before it can be written. That is three operations where the uncompressed path had one, and it means the compressed representation cannot be updated in place unless the modification preserves the compressed size — which for a variable-length encoding it generally does not.

Two strategies exist. Compress on write: keep the pool uncompressed, and compress as part of the flush path. The cost is a CPU burst during checkpointing, when many pages are flushed at once, and the benefit is that the pool is unaffected. Compress in place: store compressed pages in the pool and decompress into a scratch area on access. The cost is the scratch area and the decode on every access; the benefit is a pool that holds several times more logical data.

The second strategy is the one that changes capacity planning, because it decouples pool memory from logical page count. A pool of a given size holds more pages, which reduces misses, which reduces I/O — a gain that compounds with the compression ratio rather than merely saving bytes on the device.

Measuring whether it helps

The useful metric is not the compression ratio but the change in total work per query. Compression reduces bytes read and increases cycles spent decoding. On a device whose read bandwidth is the constraint, the first dominates; on a CPU-bound workload with a warm cache, the second does. A ratio of two to one on page bytes is typical for structured data with prefix and dictionary encoding, and higher for sorted or repetitive data, but the ratio alone says nothing about whether the trade is favourable.

There is a third effect that is easy to miss: compressed pages reduce the write amplification of the page flush itself, because fewer bytes are written per page. That reduction propagates to every layer below — the log, the doublewrite copy, the device’s own indirection — which is why the accounting in write amplification across the storage stack treats the compressed page size as the base unit rather than the logical page size. The page format that compression must preserve, including the item directory that survives compression unchanged, is described in slotted page layout.