How do delta, frame-of-reference and bit-packing encodings compress an integer column?

## The shared idea An integer column declared as 64-bit almost never needs 64 bits per value. These three encodings exist to close that gap, and they compose into one pipeline: **make the numbers small, then store small numbers narrowly.** ## Frame of reference Pick a reference point for the block — normally the minimum — store it once in the block header, and store every value as its offset from that reference. ``` values : 1000 1004 1007 1009 1015 min : 1000 offsets: 0 4 7 9 15 ``` The offsets now need only enough bits to express the block's *range*, not its magnitude. This is why the scope is per block and not per column: a block covering one hour of Unix timestamps has a range of at most 3600, so twelve bits per value suffice even though the absolute values are ten digits long. A column-wide frame would have a range spanning years and save far less. ## Delta Instead of a shared reference, subtract each value's **predecessor**. Monotonic data is the target: auto-increment ids, insert timestamps, sequence numbers. ``` values : 1000 1004 1007 1009 1015 deltas : 1000 +4 +3 +2 +6 ``` When the spacing is itself regular — a metric sampled every ten seconds — a second differencing pass (delta-of-delta) turns the stream into near-zeros, which is why time-series columns compress extraordinarily well. Delta's weakness is that values may decrease, so residuals are signed; encoders zigzag them into unsigned form so that small negatives stay small. Its structural cost is more important: reconstructing value *n* requires summing everything before it, so a delta block is decoded sequentially. Frame-of-reference keeps positional access — value *n* is at a known bit offset — which matters when the engine wants to fetch a few rows rather than the whole block. ## Bit-packing Neither of the above saves anything until the narrow residuals stop being stored in wide machine words. Bit-packing writes each residual using `ceil(log2(max_residual + 1))` bits, tightly, across word boundaries. ``` offsets 0,4,7,9,15 -> max 15 -> 4 bits each 5 values x 4 bits = 20 bits, versus 5 x 64 = 320 bits ``` The width is stored per block. Unpacking is cheap arithmetic — shifts and masks — which is exactly why these encodings are called "lightweight": their decode cost is small enough that the reduced I/O virtually always wins. ## Outliers and exceptions One extreme value in a block would force every value to the outlier's width and wreck the ratio. The standard fix is to bit-pack at a width that covers the bulk of the values and store the handful of exceeding values separately with their positions — the patched frame-of-reference family. The lesson generalises: **a block's cost is driven by its widest residual**, so an unexpected sentinel value like a far-future timestamp or a `-1` placeholder can quietly cost you several bits per row across an entire block. ## Composition and choice A real encoder chains these: choose delta or frame-of-reference (or both — delta first, then a frame over the deltas), then bit-pack, then hand the result to the general byte codec. Which chain wins depends on the data: - **Sorted or near-sorted, monotonic:** delta, then bit-pack. Best case in the whole family. - **Unsorted but clustered in a narrow range:** frame-of-reference, then bit-pack. Delta would produce large signed swings here. - **Low distinct count regardless of range:** a dictionary over the integers beats both, because the code width follows cardinality rather than range. - **Random wide values — hashes, random ids, encrypted keys:** none of them help. There is no monotonicity, no narrow range, no repetition. The column is stored plain and only the general codec contributes, modestly. Recognising this case is worth more in an interview than reciting the encodings. ## Why sortedness keeps reappearing Every member of this family is sensitive to order. Sorting shrinks deltas to their minimum and narrows each block's range, so the same integer column can differ severalfold in size purely by load order. That is the practical hook: if an integer column compresses badly, ask whether it is monotonic, whether the block range is narrow, and whether a different load order would make either true. ## Interview framing Say the pipeline out loud — *reduce magnitude, then reduce width, then patch the outliers* — and name which input shape suits which reducer. Then add the access-path nuance: delta trades random access for ratio, frame-of-reference does not.