Bit Packing & Delta

Most numeric columns don't need 8 bytes per value. A column of HTTP status codes (100-599) needs ~10 bits. Bit-packing exploits this.

Bit-pack:

• Find min, max in batch.
• bits_needed = ceil(log2(max - min + 1)).
• Subtract min from each value. Pack in bits_needed bits.

values: 1000, 1003, 1001, 1005, 1002
min:    1000, range = 5, bits = 3
deltas: 0, 3, 1, 5, 2
packed: 000 011 001 101 010 → 15 bits = 2 bytes (padded)

vs naive: 5 * 4 bytes = 20 bytes. 10x savings.

Frame-of-reference (FOR): store min once, then deltas. Same idea generalized.

Delta encoding: store first value + each subsequent diff:

values: 1000, 1010, 1015, 1100
deltas: 1000, 10, 5, 85

When values are monotonically increasing (timestamps, IDs), deltas are small → bit-pack them tighter.

Combined: delta + bit-pack + RLE. Each layer reduces.

Example, timestamps in seconds (10-digit ints):

• Delta: 1, 1, 1, 2, 1, 0, 1 (small)
• Bit-pack: 2 bits each (max delta = 2 in this batch)
• RLE: (1, 4) (2, 1) (0, 1) (1, 1) → tiny

Original: 80 bytes. Compressed: a few bytes.

Variable byte encoding (VByte):

• Each byte's high bit = continuation.
• Small values = 1 byte; large values = many bytes.
• Used in inverted indices, Protobuf varints.

These encodings COMPOSE. Real columns are typed: column store auto-picks the best chain.

Decoding cost: bit-unpacking is bit-shift loops. SIMD can vectorize. Still cheaper than raw I/O.