Posting List Encoding and the Cost of a Term Lookup

An inverted index maps each term to the list of documents containing it. The list is called a posting list, and a query for two terms is answered by intersecting their lists. Almost every design decision in the structure follows from one fact: posting lists are long, sorted, and highly compressible, and the cost of a query is dominated by the number of list entries decoded rather than by the number of comparisons made.

Delta encoding turns values into gaps

A posting list holds document identifiers in increasing order. Storing each identifier as a 32-bit integer wastes most of the bits, because the values are large — a corpus of a billion documents needs 30 bits — but the gaps between consecutive identifiers are small. A term that appears in one document in a thousand has an average gap of a thousand, which needs ten bits, and common terms have gaps in the single digits.

So the list stores differences: the first identifier, then d₂ − d₁, then d₃ − d₂, and so on. The gaps are non-negative and follow a skewed distribution — many tiny values, a long tail — which is exactly what variable-length codes are designed for. The decoder reconstructs each identifier by accumulating, so a lookup cannot start in the middle of a list without knowing the running total; that constraint drives the design of skip structures.

Variable-length integers and where they lose

The simplest encoding is the variable-byte code: seven payload bits per byte, with the high bit set on every byte except the last. A gap below 128 takes one byte, below 16,384 takes two, and so on. Encoding is a loop of shifts; decoding is a loop of shifts and a branch on the continuation bit.

/* Encode v (a non-negative delta) into buf; returns bytes written. */
size_t vbyte_encode(uint32_t v, uint8_t *buf)
{
    size_t n = 0;
    while (v >= 0x80) {
        buf[n++] = (uint8_t)(v | 0x80);   /* low 7 bits, continuation set */
        v >>= 7;
    }
    buf[n++] = (uint8_t)v;                /* final byte, continuation clear */
    return n;
}

size_t vbyte_decode(const uint8_t *buf, uint32_t *out)
{
    uint32_t v = 0;
    size_t shift = 0, n = 0;
    for (;;) {
        uint8_t b = buf[n++];
        v |= (uint32_t)(b & 0x7F) << shift;
        if (!(b & 0x80)) break;
        shift += 7;
    }
    *out = v;
    return n;
}

The code is simple and its weakness is the branch. Each byte costs a test and a conditional jump, and for a list of a million entries with an average gap under 128, that is a million unpredictable branches. The bit-level alternative packs the same information without byte alignment: a unary length prefix followed by the payload, so a gap of 3 costs four bits rather than eight. That halves the space for small gaps and makes decoding branch-free with a count-leading-zeros instruction, at the cost of unaligned reads and a more complex encoder.

Between the two sits a family of byte-aligned codes that pack several small values into one byte. A scheme that spends two bits of each byte on a selector and the remaining six on a run of fixed-width values can pack three gaps of 1 to 4 into a single byte, which suits the very common case of dense terms. The trade is that the decoder must handle several cases, and the encoder must look ahead.

The compression ratio is the point of all of it. An uncompressed list of a billion identifiers at 4 bytes each is 4 GB; delta-encoded with a variable-byte code and an average gap of a thousand, it is roughly 2 GB, because a gap of 1,000 no longer fits in seven bits and takes two bytes; a bit-level code that spends about eleven bits on such a gap brings it to roughly 1.4 GB. Those are approximations of the arithmetic, not measurements, and the ratio depends entirely on the gap distribution, which varies by term.

Intersecting two lists

A conjunctive query intersects two sorted lists. The merge algorithm walks both, advancing the one with the smaller current identifier, and emits matches. Its cost is linear in the sum of the list lengths, which for two common terms in a large corpus is prohibitive: two lists of ten million entries each require twenty million decoding steps to produce a result set of perhaps a few thousand documents.

Skipping is the standard remedy. Every k-th entry in a list is stored uncompressed as an absolute identifier, forming a skip list over the posting list. The intersection then compares skip points: if the current skip point of list A is below the current identifier of list B, the entire block between them can be skipped without decoding. Choosing k trades space for speed. A small k means many skip points — each one a full-width identifier, so about 4 bytes — and fine-grained skipping; a large k means fewer skip points and more wasted decoding. A common choice puts a skip point every few hundred entries, which costs on the order of one percent of the list’s compressed size.

The skip structure is usually a hierarchy, not a flat array: skip points over skip points, so the search for a skip position is itself logarithmic rather than a linear scan of the skip array. The hierarchy is the same idea as a B-tree’s internal levels, applied to a sorted list, and it is why the intersection of a long list with a short one costs closer to the length of the short list than the sum.

def advance(a, i, target, block):
    """Move i to the first position in a whose value is >= target.

    a is fully decoded here for clarity; a real decoder decodes one block at a
    time and consults the block's stored last identifier before decoding it.
    """
    while (i // block + 1) * block < len(a):
        last = a[min((i // block + 1) * block - 1, len(a) - 1)]
        if last >= target:
            break                      # target may fall inside this block
        i = (i // block + 1) * block   # whole block is below target: skip it
    while i < len(a) and a[i] < target:
        i += 1
    return i

def intersect(a, b, block):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]:
            i = advance(a, i, b[j], block)
        else:
            j = advance(b, j, a[i], block)
    return out

The block-skipping loop compares the last identifier of the block it is about to skip, not its first. Comparing the first identifier only tells you whether the target has already been passed; comparing the block’s last identifier is what decides whether the target can still fall inside that block, and therefore whether the whole block can be skipped without decoding it. The version above recomputes block boundaries from the index, which a real decoder avoids by keeping the skip entries in a separate array of absolute identifiers and walking a cursor through it. With the cursor form, the cost of an intersection is one comparison per skipped block plus one decoded block, which is why a small block size makes the intersection cost track the number of matches rather than the list length.

Impact ordering and the order of intersection

The order in which lists are intersected changes the cost. Intersecting the two shortest lists first produces a small intermediate result that can then be checked against the longer lists one entry at a time, which is cheaper than intersecting long lists first and discarding most of the result. The standard rule processes lists in increasing order of length, and the intermediate result is probed against each subsequent list by binary search or by galloping search rather than by a full merge.

Galloping — also called exponential search — suits this asymmetric case. Given a small set of candidate identifiers and a long sorted list, the search for each candidate starts at the previous position and probes forward with exponentially increasing steps until it overshoots, then binary-searches the bracketed range. For a candidate that is far ahead in the list, the cost is logarithmic in the distance rather than linear.

The remaining cost is the decoding of the long list’s skipped regions, which the skip structure avoids. That is why the skip interval and the impact ordering interact: a query plan that intersects a short list against a long one only needs the skip structure to be fine enough that the number of decoded blocks is proportional to the number of matches, not to the length of the list.

Positional indexes and the space multiplier

A term lookup that must support phrase queries needs more than document identifiers: it needs the positions of the term within each document. Storing positions multiplies the index size, because each posting becomes a document identifier plus a list of positions, and the positions are themselves delta-encoded.

The multiplier is substantial. A positional index is commonly two to three times the size of a document-level index for the same corpus, because every occurrence contributes a position gap. The trade is capability: phrase and proximity queries are impossible without positions, and a document-level index can only answer “contains both terms”, not “contains them adjacent”.

A middle ground stores positions only for terms where phrase queries are plausible, or stores a coarser granularity — a zone or a field identifier rather than an exact offset. Both reduce the multiplier at the cost of precision, and both are choices about which queries the index can answer rather than about how fast it answers them.

Where the structure stops being the right one

Three limits are worth naming.

Very long lists. A stopword that appears in every document has a posting list as long as the collection. Intersecting it is nearly useless — it filters almost nothing — and the standard response is to omit such terms from the index entirely and handle them at query time, or to store them in a form that can be intersected by document number arithmetic rather than by decoding. For a dense list of that kind, the alternative representation is a bitmap over the document space, which stores one bit per document and supports a conjunction with a word-wise AND rather than a decode per posting.

Update cost. A posting list is sorted and compressed, so inserting a document into the middle of a list requires rewriting the list from that point. Real systems avoid this by building immutable segments and merging them, which is the same log-structured approach that B-tree indexes avoid and LSM trees adopt. A query then consults several segments, and the merge of their results is the price of cheap updates.

Compression versus random access. Every compression scheme that stores gaps makes random access impossible without a checkpoint. The skip structure provides checkpoints, and the interval between them sets the granularity of random access. A query that needs to start in the middle of a list pays for decoding from the nearest checkpoint, so the checkpoint interval is a bound on the wasted work per seek.

The index also has a natural relationship to the hash-based structures in this cluster: a term lookup is an exact-match problem over a vocabulary that may hold millions of distinct terms. A minimal perfect hash over the static vocabulary maps a term to its posting list’s offset in a few bits per term, which is exactly the static-dictionary case that structure serves. The posting list’s own layout then determines everything about the query cost after the term has been resolved.