Finding is cheap, scoring is the cost; the inverted index

Why is scoring the real cost of text search, and why is an inverted index columnar storage at its extreme?

CaseConstructed case · Amara at Haatly

One extra word, 200 times slower

Amara sets up a text search cluster. It works, but four things look wrong:

The query red kurta returns in 8 ms. The query the red kurta takes 1.9 seconds, although it only adds one word.
A results page that shows ten items plus category counts ("Kurtas (12,400), Shirts (8,300) ...") is about 40 times slower than the same page without the counts.
A newly published listing is invisible in search for up to a minute. When she shortens the delay to 100 ms, the whole cluster becomes slower even for queries that have nothing to do with fresh items.
A buyer searches for "Apple" (the brand) and also sees fruit-basket listings, and no setting can undo that.

None of these is a bug. Each follows from the design of a text index. We will see why.

Finding is cheap, scoring is the cost

In a mechanism built around broken predicates, text search is the family where the predicate is not hard. Term membership ("does this document contain the word kurta?") is exact set intersection, and an inverted index (explained next) makes it cheap.

What breaks is something else: there is no criterion by which the answer set is right. A hundred thousand documents genuinely contain your words. The system's job is not to find them. It is to decide which ten to show, and that decision is made against a preference that lives in a human head.

That rearranges the cost model. Most systems spend effort on finding matching rows and treat returning them as free. Here, finding is cheap and scoring is the dominant cost, because scoring is per-candidate work over a candidate set that is enormous by construction. So the mechanisms of this article are not really about retrieval. They are about avoiding scoring.

The second structural fact is about distribution. Vocabulary follows a Zipf pattern at both ends: a few terms appear in most documents, and most terms appear in almost none. So a single-term predicate has either catastrophic selectivity (it matches nearly everything) or perfect selectivity (it matches almost nothing), and almost never anything in between. Which one you get is a property of the query, not of the schema. Query cost is data-dependent by nature. (This is Amara's first oddity: "the" is in almost every document.)

The inversion: the inverted index

A document is a variable-length bag of terms. A query is a handful of terms. Scanning documents costs N_docs × terms_per_doc no matter how few terms the query names.

Inverting the mapping means storing, for each term, a sorted list of the ids of documents that contain it. This list is a postings list, and each entry is a posting. Now the cost is proportional to the postings touched by the query's terms: a few lists out of a vocabulary of millions.

Tiny example. Three listings: doc 1 = "red cotton kurta", doc 2 = "blue cotton shirt", doc 3 = "red wool scarf".

red    -> [1, 3]
cotton -> [1, 2]
kurta  -> [1]
blue   -> [2]
shirt  -> [2]
wool   -> [3]
scarf  -> [3]

The query red cotton intersects [1, 3] and [1, 2] and gets [1], without ever looking at document 3's text. (Why intersection starts from the shortest list, and how skip pointers let it jump through a long one, is the cost side of the same index.)

Inversion is columnar storage taken to the extreme

This is a familiar idea at an extreme setting: an inverted index is columnar layout where the schema is the vocabulary. Columnar storage splits data by field, so you read only the fields you need. An inverted index splits by value, so you read only the values you need. Text gets the extreme version because its "fields" number in the millions and any given row populates only about five hundred of them. That shape is unworkable as columns and natural as postings.

The same continuity explains the encoding.

A postings list is a sorted integer sequence, so it is delta-encoded and bit-packed: store gaps between ids, using only as many bits as the gaps need.
When a term is dense enough that the gaps shrink to nothing, the sorted list becomes a bitmap. So bitmap indexes and postings lists are the same mechanism at different densities, and hybrid bitmap formats switch representation per block.

The term dictionary is itself an index

Before you can read a postings list you must look up the term among millions. That is a sorted-string lookup problem with its own structure (the term dictionary). So a search index is a lookup into a lookup. The outer lookup is the reason per-query fixed costs exist at all, which matters when we reach segments.

One line: inversion is columnar storage where the value is the column, and a posting list is a bitmap that is not dense enough yet.