Set membership: inverted indexes

Why does text search store the transpose of the data, sorted and immutable?

Set membership: invert the relation

The constraint: the thing you want to find is not the key of the thing you store. A document contains many terms. You query by term and want documents. A forward mapping "document to its terms" is useless for that. You must store the transpose: "term to its documents". This is the only family defined by a change of which side is the key, and everything about the inverted index follows from it.

doc 1: "red bicycle damaged"          red     -> [1, 3]
doc 2: "blue bicycle"        ====>    bicycle -> [1, 2, 3]
doc 3: "red bicycle new"              damaged -> [1]
                                      blue    -> [2]

Each list of document ids is called a posting list. Three consequences, all derivable.

Posting lists are sorted by document id, because the query is an intersection. A conjunctive query ("red AND bicycle") needs list(red) ∩ list(bicycle). Intersecting sorted lists is linear in their combined length (walk both with two pointers), not quadratic. Here the sort order is not for range queries. It is for mergeability.

Intersection cost is dominated by the shortest list, so you start there. Posting list lengths follow a Zipf distribution: a few terms appear in most documents, and most terms appear in very few. That skew is the asset. Intersecting smallest-first means a rare term prunes the candidate set before any common term is touched. This is the same pattern as the partial index: skew that is known is skew you exploit. The pathological case is a query made only of high-frequency terms. There the index provides no pruning and the system effectively reads the corpus. Deciding what to do about that (stopword handling, scoring) is a retrieval-quality matter; here we only need to know why it happens. (A stopword is a very common word like "the", whose posting list is a full corpus scan dressed as an index.)

Skip pointers apply the same granularity rule as sparse indexes. Intersecting a short list with a long one means asking the long list again and again: "advance to the first id at or after x". Scanning to find it is linear, so you store a sparse summary over the list and jump. The density question is identical to the sparse index of Index anatomy: if a compressed block holds m postings and must be decompressed whole, one skip entry per block is right and finer is waste. This is the fourth appearance of one idea after the disk block, the sparse SSTable index and the zone map.

Keeping it true. A posting list is a sorted, compressed sequence, so inserting one document would touch every list of every term it contains. The whole family therefore writes immutable segments, merges them in the background and masks deleted documents until the merge: a substrate that cannot update in place grows an indirection layer plus a garbage collector. What that costs in freshness and per-segment query overhead, and how ranking skips most candidates (WAND), are text search's: segments and scoring.