The Inverted Index, and Why Analysis Decides Everything

The naive way to find documents containing "tomato" is to read every document and check. At a million documents that is a million reads per query, and search engines answer in milliseconds, so that is not what happens.

What happens is the same trick as the index at the back of a book: precompute, for every term, the list of documents containing it. At query time, finding "tomato" is one lookup that returns a ready-made list.

Definition: an inverted index maps each term to its postings list: the ids of the documents containing that term, usually with extra per-document detail such as how often the term occurs and at which positions.

The word inverted is the point. A document is naturally a mapping from one id to many words. Search needs the inverse: from one word to many ids. Building and maintaining that inversion, compactly and updatably, is what Lucene and every engine built on it, Elasticsearch, OpenSearch, Solr, spend most of their engineering on.

Everything else in search, scoring, phrase matching, filtering, is machinery layered on top of postings lists. Get comfortable with the lists and the rest of the course has somewhere to stand.

Take three tiny documents and build the index by hand.

Document 1: "red tomato soup". Document 2: "tomato salad". Document 3: "red wine".

Each document is broken into terms, and each term accumulates its postings. The result is a dictionary of terms, each pointing at a sorted list of document ids.

Queries compose by set operations on these lists. "red AND tomato" intersects the two postings lists, giving document 1. "red OR tomato" unions them. Sorted lists make intersection fast, walk both in step, and engines add skip structures so that intersecting a rare term's short list against a common term's long one can leap through the long list rather than crawl it.

Two details in the postings carry most of later lessons. The term frequency per document feeds scoring: a document mentioning tomato five times probably cares more about tomatoes. And the positions enable phrase queries: "tomato soup" as a phrase requires the terms adjacent and in order, which only position data can check.

The index stores terms, and terms are manufactured. Raw text passes through an analysis pipeline before anything reaches a postings list, and each stage is a policy decision:

The output is the term stream that gets indexed, and none of the original spelling survives except as stored, unsearched, source text.

Why so aggressive? Recall. A user typing "run" expects documents saying "running". Every merge in the pipeline is a bet that two surface forms mean the same thing, trading precision, the ability to distinguish them, for recall, the ability to match across them. The whole craft of analysis configuration is placing those bets differently for different fields.

The analysis pipeline runs twice: once at index time over documents, once at query time over what the user typed. The two runs must be compatible, and the reason is mechanical, not conventional.

Matching happens by exact term equality in the index. If indexing stems "running" down to "run" but the query pipeline leaves "running" intact, the query term "running" is looked up against an index that only contains "run": zero results, silently. The document is there; the vocabulary no longer matches.

Gotcha: analysis is baked into the index at write time. Changing the analyzer does nothing for documents already indexed under the old one; the postings were built from the old terms and cannot be reinterpreted. An analyzer change is a reindex of everything, which for a large corpus is a project, not a setting. This is why search teams agonise over analysis choices up front and why blue-green reindexing infrastructure exists.

Deliberate asymmetry does exist: applying synonyms only at query time, for instance, so the synonym list can be updated without reindexing, at some cost in scoring accuracy. That is a considered exception that proves the rule: the two pipelines are one design with two entry points, never two independent configurations.

The classic production incident in this area involves an identifier, and it is worth walking precisely because every e-commerce and B2B search hits it.

This is also the first appearance of this course's recurring theme: the lexical machinery is exact by nature, which makes it wonderful for identifiers and terrible at knowing that laptop and notebook are the same thing. That trade is lesson three's subject.

Real documents are not one blob of text; they are structured: a title, a body, a brand, a price, tags, an SKU. Engines index each field separately, with its own analysis, and this is where schema design earns its keep.

The working vocabulary, in Elasticsearch terms that map directly onto Lucene:

• text fields go through full analysis and feed relevance scoring: titles, descriptions, reviews.
• keyword fields are indexed as single exact terms: SKUs, status values, brand names used for filtering and aggregation.
• numeric, date and boolean fields use specialised structures built for ranges rather than postings-list lookups.
• The same source value can be indexed multiple ways at once, a brand as text for matching and as keyword for the facet sidebar, because matching and filtering genuinely need different representations.

Two schema rules with outsized payoff. Decide per field what question it answers, match it, filter it, sort it, facet it, and index for exactly those, because every representation costs write throughput and disk. And treat mapping changes with the same respect as analyzer changes: most of them also require a reindex, for the same baked-at-write-time reason.

The inverted index is a bet that reads outnumber writes, and it is worth making the bet's terms explicit.

Every document write fans out into updates across every term the document contains, and engines batch these into immutable segments that background processes merge, which is why search engines describe themselves as near-real-time: a written document becomes searchable after the next refresh, typically a second or so, not instantly.

In exchange, reads are spectacular: a query touches only the postings lists of its query terms, each compressed, cache-friendly and skip-listed, regardless of how many millions of documents sit in the corpus.

The bet fails in recognisable situations. Write-dominated workloads with rare queries pay indexing costs for nothing, a log pipeline that mostly archives should think twice about full indexing. Point lookups by id need a key-value store, not postings. Analytical scans over whole columns want columnar storage. The mature architecture pattern is unbundled: a primary database owns the truth, and the search engine holds a derived, denormalised copy fed by change streams, rebuildable at will, which is exactly the posture the reindex-heavy operations above demand anyway.