Postings Lists as Sorted DocID Arrays

An inverted index maps each term to the set of documents that contain it. The set is stored as a postings list: a sequence of document identifiers, in ascending numeric order, with no duplicates. That invariant looks like a storage convention. It is in fact the interface the rest of the engine is built against, and nearly every cost characteristic of a search system follows from it.

A posting is not just an identifier in most real indexes. It carries the term frequency, or the positions at which the term occurs, or both. But the identifier leads every entry, and the ordering applies to it. Once a reader has internalised that a postings list is a sorted array of integers that happens to have some payload attached, the behaviour of query evaluation stops being mysterious.

Ascending order is what makes a list addressable

Document identifiers are assigned when a document enters the index, typically from a counter that only increases. The assignment is arbitrary with respect to content, but it is monotone in time, which means a postings list also records the order in which documents arrived. Ascending order therefore gives three distinct capabilities at once.

The first is set intersection by merge. Two lists can be walked in parallel with a single comparison per step, producing their intersection in time proportional to the sum of their lengths, with no hashing and no auxiliary structure. The second is gap encoding. Because identifiers increase, consecutive entries can be stored as differences, and differences are small when a term is dense, which is where most of the compression in an index comes from. The third is prefix semantics: an iterator positioned at a document identifier can be advanced to any later identifier, so a query can ask for “the next document at or after position 4000” without decoding everything before it.

None of the three survives shuffling the list. A postings list stored in arrival order of postings, or in hashed identifier order, would need a per-term hash table for membership, would lose the locality that makes gap encoding worthwhile, and could not be walked in document order.

Building the order is the indexer’s first real cost. Postings are generated per document, so identifiers arrive already ascending for each term within a document, but not across documents unless the indexer processes documents in identifier order. An in-memory builder either appends into a per-term dynamic array and sorts at flush time, or collects into a per-term hash set and sorts once. Sorting is O(n log n) per term for n postings, which is dominated by the merge pass over the whole collection rather than by any single term. On a 32-bit identifier space an uncompressed list costs 4 bytes per entry; a term appearing in one document in ten of a million-document collection occupies about 400 kilobytes before any compression, and 100 kilobytes or less after gap encoding.

Conjunction is a merge, not a lookup

The textbook evaluation of a two-term AND query walks both lists with two cursors:

def intersect(a, b):
    out = []
    i = j = 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 += 1
        else:
            j += 1
    return out

The loop advances whichever cursor is behind, so it performs at most |a| + |b| comparisons and touches each list once, sequentially. It is also cache-friendly in a way that a hash join is not, because both cursors move forward through contiguous memory and the hardware prefetcher follows them.

The merge is correct for any number of terms, with the caveat that the loop structure should advance the cursor of the currently smallest identifier rather than a fixed pair. A k-term conjunction is the same code with a heap or a linear scan over k cursors to find the minimum, at a cost of k comparisons per step. For small k the linear scan wins because it avoids heap bookkeeping; for large k the heap or a tournament tree wins.

Galloping when the lengths disagree

Term frequencies are heavily skewed. A stopword-like term can appear in a large fraction of the collection while a rare term appears in a handful of documents. Merging a list of 10,000 entries against one of 20 entries by stepping costs 10,000 comparisons to produce at most 20 matches.

The standard fix is to drive the merge from the shorter list and search the longer one. Binary search for each element of the short list gives O(|a| log |b|), which for the sizes above is roughly 20 comparisons of 14 steps each. Exponential search, also called galloping, is better still when the matching positions cluster: it probes forward at distances 1, 2, 4, 8 and so on from the cursor, then binary-searches the bracketing interval. Its cost is proportional to the logarithm of the distance actually skipped, so it adapts to dense regions and sparse ones without a tuning parameter.

Production evaluators choose per pair: step when the lengths are within a small factor, gallop otherwise. The crossover is usually expressed as a ratio of lengths, and the choice is made once per list pair rather than per element.

What the flat layout gives up

A sorted array supports binary search and sequential scan and nothing else. Insertion into the middle of a list means shifting the tail, so an index built this way is immutable between merges. A deleted document cannot be removed from a list without rewriting it, so implementations keep a live-document bitmap and filter matches at query time, which costs one bit test per candidate. Updates are handled by writing a new segment and merging segments later, so the on-disk structure is a set of sorted arrays with overlapping identifier ranges rather than one global array. This is the reason an index with heavy churn tends to have more segments, and why query latency can degrade as segments accumulate.

The second thing given up is random access into compressed regions. Once a list is stored as variable-length encoded blocks, a cursor cannot be moved to an arbitrary byte offset and decoded correctly, because the block boundaries are only discoverable by decoding forward. Implementations restore addressability with a skip structure: every b-th posting, where b is a fixed block length such as 128, has its identifier and byte offset recorded in a separate array. Advancing to a far identifier then costs one search in the skip array plus decoding of at most b entries, instead of a linear pass. The trade is discussed in bit packing and frame-of-reference blocks, which is where the block size is actually chosen.

Payloads change the arithmetic, not the shape

A positional index stores, for each document containing a term, the list of positions where it occurs. A document with twenty occurrences contributes twenty positions to one posting, so the payload can dwarf the identifier, and a positional index is commonly two to four times the size of a non-positional one before compression. The identifier ordering still holds at the outer level, and the inner position arrays are themselves ascending, so the same gap-encoding machinery applies twice. Phrase verification depends on that inner ordering, as positional indexes and phrase verification describes.

Frequencies are cheaper: a small integer per posting, which is often folded into the same compressed block as the identifier gap.

Where document order stops being the useful order

Two important cases break the assumptions above.

Ranked retrieval with early termination wants postings visited in decreasing order of contribution to the score, not in document order, because the top results are what matter and the tail of the list can be abandoned. An index that reorders postings by impact gives up the merge property and buys pruning power, at the price of random identifier access; impact-ordered indexes covers the resulting structure and its costs.

Per-term accumulators, the alternative evaluation strategy, do not need identifier order at all, and can be written against impact-ordered lists without a merge. But they need an accumulator array sized to the collection, which is the trade described in document-at-a-time and term-at-a-time evaluation.

For the common case, though, the sorted array is the whole design: it makes the cheapest possible intersection possible, it makes compression possible, and it makes the index a sequence of memory-mappable runs. The remaining articles in this cluster are largely about how much smaller that array can be made without losing the ability to move a cursor forward.