Bit packing, front coding, nulls and floats

Why do the remaining encodings cost more in decoding than in space, and what does the hardware decide for them?

Bit packing

Idea. Remove the leading zeros uniformly across a block and pack the values next to each other, without aligning them to bytes. If the width is w bits, the ratio is 64 / w (or 32 / w for 32-bit values).

width 3 bits:  5 → 101,  2 → 010,  7 → 111      stored as  101010111...

The space argument is trivial. The interesting part is entirely in decoding.

• Taking values out of a packed stream needs shifts and masks that cross word boundaries: roughly two to four operations per value in plain scalar code.
• The vectorized (SIMD) version is fast only if the shift amounts are constants known at compile time. So implementations generate a separate unrolled routine for each bit width: 32 or 64 distinct routines ("kernels") per encoding. A single generic routine with a variable shift runs 3–5× slower.

Note what this really costs. It is not development time. It is instruction cache. Sixty-four specialized kernels per encoding, times several encodings, and the working set of the decode loop no longer fits in the L1 instruction cache (the small fast memory that holds the code the CPU is running). The specialization win is real, and the limit on it is a hardware resource that nobody budgets.

Block size is a tug-of-war between two forces:

• Larger blocks spread the frame and header cost over more values (a fixed cost sets a batch size: wants bigger).
• Larger blocks are more likely to contain an outlier that widens everything (variance cost: wants smaller).

The balance lands at 64–128 values. This is not a coincidence: 128 values × 4 bits = 512 bits = 64 bytes, exactly one cache line, and the common widths line up with SIMD register boundaries. The hardware's geometry sets a compression parameter.

Some systems round widths up to 1, 2 or 4 bytes. They give away up to fifteen bits per value in return for a faster, branch-free decode. This is the ratio-versus-speed dial inside one mechanism, and on a local-NVMe workload it is usually the right choice.

Prefix compression (front coding)

Idea. For sorted strings, store the length of the prefix shared with the previous string, plus the part that differs.

https://tradewind.example/parcels/1001      → (0, "https://tradewind.example/parcels/1001")
https://tradewind.example/parcels/1002      → (37, "2")
https://tradewind.example/parcels/1017      → (36, "17")

Sorted keys share long prefixes by construction: URLs, file paths, hierarchical IDs and, notably, the string dictionaries of dictionary encoding. This is why front coding and dictionary encoding combine so naturally.

It has the same sequential dependency as delta (each string is rebuilt from the previous one) and the same fix: restart points. Store a full key every r entries, and keep an array of offsets to the restarts. To search, do a binary search over the restarts and then a linear scan inside one group.

Deriving the restart interval

Counting comparisons, the cost is log₂(N / r) + r / 2 (binary search steps plus the average scan length). Minimizing this naively gives r ≈ 3. Yet every real system uses about 16. The naive derivation is wrong because it counts comparisons instead of cache misses. The binary search over restarts is random access (each step is likely a cache miss). The linear scan inside a group is sequential, so the hardware prefetcher (which loads the next memory lines early) hides its cost.

Give a binary step a weight of α times a linear step. The optimum becomes r ≈ 2α / ln 2. With α between 5 and 8, this gives r between about 14 and 23. The universal 16 comes straight from the memory hierarchy.

And it is universal: the data blocks of SSTables (the sorted files of LSM databases), key compression inside B-tree pages, and Parquet dictionary pages all use front coding with restarts every 8–32 entries. Three systems, designed independently, at three levels of the stack, with one interval. When independent designs converge this strongly, the cause is a constraint, not a fashion.

Constant and null suppression

These look like degenerate cases. They are in fact where a surprising share of real-world savings comes from, because real tables are full of degenerate columns: deprecated fields, feature flags, tenant identifiers that are constant inside one partition, columns that are entirely null for whole date ranges.

The first requirement: such a column must cost O(1) per chunk, not O(N). The second: its statistics should answer predicates without any read at all (if the chunk's min = max = 5, WHERE x = 7 skips the chunk).

Null representation has a clean crossover

• A validity bitmap costs N bits (one bit per row).
• A sparse position list costs m × log₂ N bits for m present values (each position needs log₂ N bits).

They are equal when m / N = 1 / log₂ N. For a chunk of a million rows, log₂ N ≈ 20, so the crossover is at about 5% density. Above 5% of values present: use the bitmap. Below: use positions.

This is the same dense-versus-sparse crossover that Roaring bitmaps face. Roaring is a compressed bitmap format that, for each chunk of 65,536 values, looks at the data and picks either a plain bitmap or a sorted list of positions. "Inspect the data, then choose the representation per chunk" is the defining idea of this whole stage, applied to a different problem. Two mechanisms from different fields arrived at the same decision with no shared history.

Float compression

Start with why floats resist compression. An IEEE-754 double has 1 sign bit, 11 exponent bits and 52 mantissa bits. Real measurement data usually has a narrow range of exponents, which compresses well. But the low mantissa bits are essentially random: they are either sensor noise or the binary leftover of a decimal value that has no exact binary form (0.1 cannot be written exactly in binary). The order-0 entropy of a typical double column is 30–50 bits, which limits any general-purpose codec to about 1.5–2×.

(For Tradewind this is why lat and lon stay large even in a well-tuned file.)

Gorilla's XOR

Gorilla uses sequential similarity. It XORs each value with the previous one. If the two values share the sign, the exponent and the high mantissa bits, the result has many leading and trailing zero bits. Identical values emit a single bit. Other values emit: the count of leading zeros, the length of the meaningful bits, and the meaningful bits themselves, with a one-bit mode that reuses the window of the previous value. On Facebook's metrics, 59% of values collapsed to one bit. The average was 1.37 bytes per point (timestamp plus value) against 16 bytes raw, about 12× overall.

The boundary is specific. XOR works when values change slowly relative to their size. Near a zero crossing, the exponent changes on nearly every sample (going from 1.0 to 0.99 already changes the exponent field), so a signal that oscillates around zero defeats it completely. It also has the same serial dependency as delta.

ALP: decimals in disguise

ALP is the more interesting idea, and the more general lesson. Its observation: most floats in production are decimals in disguise. Prices, sensor readings and percentages are values that began with two or three significant decimal digits and became doubles only because someone picked a column type. So ALP searches for exponents (e, f) such that x × 10^e × 10^−f round-trips exactly to an integer. When it finds them, it stores integers and passes them to the integer tools: frame of reference plus bit-packing. When this fails, it falls back to splitting the mantissa. It beats the XOR family clearly on real data and decodes at several GB/s, because its hot path is the same bit-unpacking routine that everything else in this stage already uses.

The lesson reaches beyond floats: ALP wins by discovering that the real type of the data is not its declared type. The schema said double; the real domain was fixed-point with two decimals. Once the real domain is recovered, ordinary tools apply.

The meta-problem: choosing the encoding

Every mechanism above is a conditional bet, so a writer must choose per column and per block. There are three strategies in practice:

1. Static rules by type (for example, "strings: dictionary").
2. Sample and estimate on about 1% of the values.
3. Exhaustive trial of the candidates, keeping the best.

Encodings can be cascaded: dictionary then FOR then bit-packing, or delta then FOR then bit-packing. So the search space is a tree two or three levels deep, and modern formats do a sampled cascade search.

This sets the cost asymmetry of the stage: the read side is nearly free, and the write side pays for a search. It is a search cost, not only a compute cost, and that is a different thing to budget. It is why bulk-loading a well-encoded table can take several times longer than writing the same rows uncompressed, while costing nothing at query time. It also means the right amount of effort is a direct function of the read-to-write ratio: data that is read often deserves more search.