Inverted Indexes and Postings Lists

Scanning ten million documents for a query term takes time proportional to the corpus. Looking the term up in a dictionary that maps it to the list of documents containing it takes time proportional to how many documents contain it. For a term appearing in 200 documents, that is a difference of five orders of magnitude, and it is the entire reason full-text search at scale is possible.

An inverted index has two parts. The dictionary maps each term to a pointer and a document frequency, and is small enough to keep in memory. The postings list for each term is a sorted sequence of document IDs, usually with per-document term frequencies and sometimes positions.

Why the list is sorted, and what it costs

Sorting postings by document ID is the decision everything else depends on. It makes conjunctive queries an intersection of sorted lists, computable in a single merge pass in \(O(n_1 + n_2)\) rather than by hashing or nested loops. It makes gap encoding possible. And it lets the index support skipping.

The cost is that ranked retrieval cannot simply read the front of the list. A list sorted by score would let you stop after \(k\) entries, but it would break intersection and could not be compressed nearly as well. Impact-ordered indexes make exactly this trade and are used in score-at-a-time systems; document-ordered indexes remain the default because they support Boolean structure, phrase queries, and incremental updates.

Positional information is expensive: storing every occurrence position typically multiplies index size several times over, and it exists to support phrase and proximity queries. Many systems keep a positional index for a subset of fields or drop it entirely when phrase search is not required.

Compression by gap encoding

A postings list of ascending document IDs is stored as the differences between consecutive entries, the d-gaps. The transformation matters because gaps are small for frequent terms: a term in 20% of a 10-million-document corpus has average gap 5, needing three bits rather than the 24 bits a raw ID would take.

The encodings trade compression against decode speed. Variable-byte uses one continuation bit per byte and decodes very fast, at poor compression on small values. Elias-Fano encodes a monotone sequence near its information-theoretic bound and supports random access, which is what makes skipping cheap. PForDelta and SIMD-BP128 pack fixed-width blocks so a whole block decodes with vector instructions, handling outliers separately.

The right question is never "which compresses best" but where the system is bound. A disk-resident index is I/O bound and wants aggressive compression; an in-memory index is CPU bound and wants a codec whose decode loop vectorises.

Skip pointers and the shape of a query

Long postings lists carry skip pointers at intervals, so intersecting a rare term with a common one can jump forward in the common list rather than scanning it. With skips every \(\sqrt{n}\) entries, intersecting a list of length \(m\) against one of length \(n\) costs roughly \(O(m\sqrt{n})\) rather than \(O(n)\), which is why query latency depends far more on the rarest term than on the commonest.

This is also the reason stopword handling still matters. A query containing "the" touches a postings list covering most of the corpus, and although modern dynamic pruning handles it far better than stopword removal did, the asymmetry between rare and common terms remains the dominant cost structure.

When it breaks

Updates are the hard part. Inserting a document means touching one postings list per distinct term in it, and compressed lists cannot be edited in place. Real systems write immutable segments and merge them in the background, so an index is a small set of segments queried together, and deletions are tombstones applied at query time. Lucene's segment architecture is the canonical implementation and the source of its refresh-interval and merge-policy tuning knobs.

Term-at-a-time and document-at-a-time behave differently under memory pressure. Document-at-a-time processing walks all query terms' lists in parallel, keeping one heap of \(k\) candidates and enabling early termination. Term-at-a-time processes one list fully before the next, requiring an accumulator per candidate document, which is fine for short queries and expensive for long ones.

Vocabulary growth is not linear but does not stop. Heaps' law says distinct terms grow roughly as \(O(n^\beta)\) with \(\beta\) around 0.4 to 0.6, so the dictionary keeps growing with the corpus. Most of that tail is rare terms, misspellings and identifiers, and it is why dictionary compression and term hashing exist.

An inverted index only matches terms that appear. No amount of index engineering retrieves a document that shares meaning and no vocabulary with the query, which is the vocabulary mismatch problem that expansion, learned sparse retrieval and dense embedding methods each attack from a different direction.