skip to content

Why are document IDs in a postings list stored as deltas, and how does variable-byte encoding compress them?

level: seniorimportance: should knowfreq 35%

answer

  1. The IDs only ever go up
  2. Store the difference, not the value
  3. Common terms have the smallest gaps
  4. Seven payload bits, one flag bit
  5. You can no longer jump to posting number ten

basics

~20 s

Postings are sorted ascending, so storing gaps instead of absolute IDs turns large numbers into small ones. Variable-byte encoding then spends one byte on small gaps and more only when needed, using seven payload bits per byte plus a continuation flag.

solid answer

~60 s

Document IDs in a postings list are strictly ascending, which makes them highly compressible. **Delta (gap) encoding** stores the difference from the previous ID rather than the ID itself: `[3, 5, 12, 13, 200]` becomes `[3, 2, 7, 1, 187]`. For a common term the list is dense, so gaps are tiny even when the absolute IDs run into the hundreds of millions. **Variable-byte encoding** then exploits that: each byte carries seven bits of payload and one flag bit indicating whether the number continues, so values under 128 cost a single byte instead of four. The two techniques compose — deltas make the values small, varbyte makes small values cheap — and together they cut postings size dramatically, which matters because postings are read from disk or page cache on every query. The cost is that the list is no longer randomly addressable: you must decode from a known starting point, which is exactly why postings carry skip structures with absolute IDs at intervals. Modern engines often replace plain varbyte with block-oriented bit packing that decodes many postings at once.

code

python · 14 lines
python
# doc ids -> gaps
ids = [3, 5, 12, 13, 200]
gaps = [3, 2, 7, 1, 187]   # each is the distance from the previous id

def vbyte(n):
    out = bytearray()
    while True:
        b = n & 0x7F              # seven payload bits
        n >>= 7
        if n:
            out.append(b)         # more bytes follow
        else:
            out.append(b | 0x80)  # this convention flags the final byte
            return bytes(out)

go deeper

for a junior

Recognise that postings are sorted ascending and that storing the gap between IDs makes the numbers small; that alone is the core idea worth recalling here.

for a middle

Explain the seven-payload-bits-plus-flag layout of variable-byte encoding, work a small example end to end, and say why gap size depends on how common the term is rather than on corpus size.

for a senior

Show the systems consequence: compression is a latency lever because postings dominate query I/O, and delta encoding destroys random access, which is why skip checkpoints storing absolute IDs exist.

for a principal

Own the trade-off curve between compression ratio and decode throughput — tighter bit-level codes versus branch-free block packing — and treat postings footprint as a cache-residency decision that shapes hardware sizing.

## Why postings compress so well A postings list is a sorted sequence of increasing integers. That is a best case for compression, and it matters because postings are the bulk of index bytes and are read on every query. Halving postings size roughly halves the I/O and doubles how much of the working set fits in page cache, so compression here is a latency feature, not just a storage feature. ## Delta encoding Because the IDs ascend, each one can be represented as its distance from the previous one. Absolute IDs `[3, 5, 12, 13, 200]` become gaps `[3, 2, 7, 1, 187]` (the first is the gap from zero). Nothing is lost — the decoder rebuilds absolutes by running a prefix sum — but the magnitude of the numbers collapses. The key insight is that gap size is inversely related to term frequency in the corpus. A term appearing in one document in three has an average gap near three, regardless of whether the corpus has ten thousand or a hundred million documents. So the *most expensive* lists — the long ones for common terms — are exactly the ones that compress best. Rare terms have big gaps but only a handful of postings, so their poor compression ratio costs almost nothing in absolute bytes. This is also why document IDs are usually assigned densely and in insertion order, and why some systems deliberately reorder documents before building an index so that similar documents receive nearby IDs, tightening the gaps further. ## Variable-byte encoding A fixed 32-bit integer wastes most of its bits on small numbers. Variable-byte (VByte) encoding uses seven bits of each byte for payload and the remaining bit as a flag marking whether the number continues into the next byte. Conventions differ over whether the flag marks "more to come" or "this is the last byte"; both are in use and either is fine to describe as long as you are consistent. The result: values 0–127 take one byte, up to 16,383 take two, and so on. On a dense postings list where most gaps are single digits, this is close to a four-fold saving over fixed-width integers, and decoding is a simple loop with shifts and masks. ## Beyond varbyte: block codecs VByte's weakness is that it is byte-aligned and branchy: every byte requires a test of the flag bit, which is bad for modern CPUs that dislike unpredictable branches. Contemporary engines therefore usually encode postings in fixed-size *blocks* — a batch of consecutive gaps at a time — and bit-pack the whole block to the width of its largest value, which is branch-free and vectorises well. Variants handle outliers by storing exceptions separately so one huge gap does not widen the whole block. Whichever codec is chosen, the delta step in front of it is unchanged; the codec is only the second half of the story. There are also non-byte-aligned schemes such as Elias-Gamma and Golomb codes, which achieve tighter ratios but decode more slowly, and modern engines generally trade a little size for a lot of decode speed. ## The consequence: no random access Delta encoding is inherently sequential. To learn the tenth document ID you must decode the first nine gaps, and with variable-width bytes you cannot even compute where a posting starts without decoding what precedes it. Both properties break random access, and query execution needs random-ish access constantly — a conjunctive query wants to jump the common term's list forward to a candidate ID from the rare term's list. The fix is structural: postings carry a skip index recording, at regular intervals, an *absolute* document ID together with the byte offset where decoding may resume. A forward jump becomes: consult the skip entries to find the last checkpoint at or before the target, seek there, and decode forward only within that block. Block codecs make this natural, since block boundaries are already the resumption points. ## What to say and what not to say Say: postings are ascending, so store gaps; gaps are small for common terms, and small values are cheap under a variable-length code; the trade is sequential-only access, repaired by skip checkpoints holding absolute IDs. Do not claim a specific compression ratio or codec for a particular product unless you know it — the mechanism is the point, and inventing a number is the fastest way to lose credibility on a question like this.

  • Why do the longest postings lists compress the best?
    Because gap size tracks how common the term is, not how large the corpus is. A term in one document out of three produces average gaps near three however many documents exist, so its very long list is packed at roughly a byte per posting. Rare terms produce large gaps but have few postings, so their weaker ratio costs almost nothing overall.
  • What does delta encoding cost you at query time, and how is that repaired?
    It makes the list sequential-only: you cannot read the Nth posting without decoding everything before it, and variable-width bytes hide where postings begin. Engines repair this with a skip index that stores, at intervals, an absolute document ID plus the byte offset at which decoding can restart, so a forward jump decodes only one block.
  • Why have block-based bit-packing codecs largely displaced plain variable-byte encoding?
    Variable-byte decoding tests a flag bit per byte, producing unpredictable branches that stall modern CPUs. Packing a fixed block of gaps to the bit width of the block's largest value removes the branches entirely and decodes with vector instructions, so throughput rises even when the raw compression ratio is similar. Outlying large values are stored as exceptions so they do not widen the block.

saying these in an interview costs you the question

  • Claims deltas save space regardless of sort order
  • Says variable-byte uses all eight bits for payload
  • Thinks a compressed postings list still allows random access
  • States a specific compression ratio with no basis
  • Believes rare terms are the ones that compress well

context

resolving links…