Posting List Compression

A web-scale index has TRILLIONS of (term, doc_id) pairs. Storing them naively at 4 bytes per doc_id would be terabytes. Compression cuts this by 5-10x.

Three classic techniques:

Delta encoding: posting lists are sorted ascending; store differences instead of absolute values.

[42, 100, 105, 200, 1000]
becomes
[42, 58, 5, 95, 800]    (deltas)

Deltas are smaller numbers — easier to compress.

Variable-byte encoding (VByte): small numbers take fewer bytes. Each byte carries 7 payload bits, most-significant group first, and spends its 8th bit as a flag. Values 0-127 fit in one byte, 128-16383 in two, and so on.

Which way round is the flag? Two conventions exist and they are byte-for-byte incompatible, so this is the first thing to pin down when you implement or read one. The classic IR convention — the one this course uses — sets the high bit on the last byte of an integer, as a terminator; continuation bytes leave it clear. (Protobuf varints do the reverse: high bit set means more follows. Same idea, mirrored flag, incompatible bytes.)

42  = 0101010                 -> 0xaa           (0x2a | 0x80: single byte, terminated)
58  = 0111010                 -> 0xba           (0x3a | 0x80)
800 = 0000110 0100000         -> 0x06 0xa0      (0x06 continues, 0x20 | 0x80 terminates)

A decoder therefore shifts 7 bits at a time into an accumulator and emits the value the moment it reads a byte with the high bit set. The trap: write the flag the other way round and every single-byte value silently decodes as a continuation, so your decoder runs off the end of the buffer instead of returning a wrong number — a confusing failure to debug from the symptom alone.

Block-based compression: group postings into blocks (128 doc IDs); compress each block. PForDelta, Simple9, Roaring Bitmaps.

For boolean intersection over compressed lists, you typically decompress on the fly. Skip lists store decompressed positions every K postings to enable jumps.

Lucene uses a combination: VByte + skip lists + occasional block recompression. Modern systems (Tantivy, Bleve) refine the same.

For this lesson: implement VByte encode/decode of a single posting list.