Delta packing: nine numbers in sixteen bits
Runs of identical deltas and repeated types collapse into a single count-and-value pair. Here are the exact bits a bit-level columnar encoding writes, plus the case where this stops working.
Related: Trees as columns
Real data has rhythm. Ids go up by one, flags repeat and records share a shape. After columnar restructuring puts like next to like, the encoding stores that rhythm directly instead of storing every value. All bit strings below were checked against the reference implementation.
Collapsing a run
Numbers are delta-coded against the previous number. A small step costs a 2-bit selector 00 plus a 3-bit delta code, so 5 bits. The array [1, 2, 3, 4, 5, 6, 7, 8, 9] is nine steps of +1, which would cost 45 bits written out one by one. When three or more equal codes occur in a row, the encoder writes a run instead: the escape 00 111, a short count, and the repeated code once.
- run escape
- delta +1
Value links and types are run-packed too (from four equal codes up), so length barely matters: the integers 1 to 100 encode in 9 bytes, and 1 to 1,000 in 13. The run gets longer, but it is still stored once.
The same trick for types
Every value has a 3-bit type tag, and 000 is reserved as a run escape. Five non-negative integers in a row (type 100) become escape, count and type: 000 01101 100.
Booleans go one step further. An all-true column is just the 2-bit mode 01, with no body at all.
Floats without IEEE 754
The encoding does not store floats as 64-bit IEEE doubles. Inside a document, a float is a small header that combines sign and precision, followed by an integer mantissa. For -3.14 the precision is 2. The header is (2 + 1) + 4 for negative, which gives 7 and is written 01 0111. It is followed by 314 as a LEB128 literal, 11 10111010 00000010. The whole value is 24 bits. MessagePack spends 9 bytes: a marker plus a float64.
The decimal form is lossless when it is defined exactly: take the shortest decimal that rounds to v, let p be its number of fractional digits, and let the mantissa be its digits read as an integer. Decoding m · 10^−p with correct rounding then returns v. The shortest round-tripping decimal of a double has at most 17 significant digits, so for |v| < 10^17 the mantissa is below 10^17 < 2^57 and takes at most 9 LEB128 bytes. A full-precision double therefore costs more than its 8 IEEE bytes. The decimal form pays off for values with few digits, like the −3.14 above.
Where packing stops working
All numbers share one delta chain, in document order. That is ideal for a column of ids, but a time series like [{t: 1700000000, v: 98}, {t: 1700000060, v: 101}, …] alternates between a timestamp near 1.7 billion and a value that is orders of magnitude smaller. No step between consecutive numbers falls in the delta range of −3 to +3, so every number becomes a literal. On a benchmark of 1,000 such rows (t increasing by 60, v a random walk from 100 with integer steps of −5 to +5) the output is 21% larger than MessagePack (14,040 bytes against 11,617). Two remedies suggest themselves. Keep the first sentence. Replace ‘I have not measured how much either would recover. The paper measures this and the other cases where the encoding loses.’ with ‘The paper measures this loss and the other cases where the encoding is larger.’ Delta-of-delta coding on a per-path chain for t would turn the constant stride of 60 into a repeated code that a run can absorb. Trees as columns compares grouping by kind with grouping by path.