How web search works

You type four words into a box and, a quarter of a second later, ten results come back from an index of tens of billions of pages. It feels like one operation. It is really a pipeline of fairly simple ideas, each of which is easy to understand on its own and slightly astonishing when you see how far it has been pushed.

I have spent much of my working life on search — enterprise search, content platforms, more Lucene indexes than I care to count — and the thing I most wish someone had shown me early on is that there is no magic in it. There is text processing, a big sorted dictionary, some careful arithmetic and a lot of engineering to make it fast. This exploration walks through those pieces in the order a document meets them, with the site’s own search tools embedded along the way. Everything runs in your browser; poke at it as you read.

Step one: turning text into terms

A search engine never searches text. It searches terms: normalised tokens that came out of an analyser. Before a page is indexed, and again when you type a query, the text goes through the same chain: character filters (strip HTML, map odd characters), a tokeniser that splits the stream into words, and a sequence of token filters that lower-case, drop very common words and cut words down to a stem. If the document and the query go through the same chain, "Running" in one and "runs" in the other can meet in the middle.

Here is Elasticsearch’s english analyser, rebuilt stage by stage.

The english analyser: tokeniser, possessive stemmer, lowercase, stop words, keyword marker and Porter stemmer, one stage at a time.Open full tool →

Try this. Scroll down to the token stream and read it top to bottom. The sample sentence is The QUICK brown foxes jumped over the lazy dog’s bone. Running runners ran!

Watch the first stemmer turn dog’s into dog — that is the possessive filter, and it runs before lower-casing.
The stop filter removes both the tokens, but notice that the positions jump from 0 to 1 and from 5 to 7. The gaps are kept on purpose, so that a phrase query later knows the words were not really adjacent.
The Porter stemmer gives fox, jump, run, runner — and lazi. Stems are not words; they only have to be consistent. It also leaves ran alone: Porter strips suffixes, it does not know irregular verbs.
Switch the analyser at the top to standard and the stems disappear. Now a search for "fox" would not match "foxes". Switch to keyword and the whole sentence becomes one term — exactly what you want for a product code or a tag, and useless for prose.

That last experiment is the first real lesson of search: most "the search engine is broken" complaints are analysis problems. The document had the word; the analyser turned it into something the query never produced.

Step two: the inverted index

Once text is terms, the engine builds an inverted index: for every term, the list of documents that contain it. That list is called a postings list, and each entry — a posting — records the document ID, how many times the term appears (the term frequency, tf) and, if phrase search is wanted, the positions.

The same tool shows the index the english analyser builds over four tiny documents.

Four documents, seven distinct terms: each with its document frequency, total frequency, BM25 idf and postings.Open full tool →

Try this.

Find fox. It appears in all four documents (df 4), including "brown foxes and quick dogs", because the stemmer folded foxes into fox. Its idf is tiny: a term in every document says almost nothing about which one you want.
Compare jump, lazi and over, each in one document with an idf more than ten times larger. Rare terms carry the signal.
Look at the Field lengths and norms table under the index. Lucene stores each field’s length in a single byte, exact up to 23 and approximate after that. We will need those lengths in a moment, when we score.
Edit the documents. Add a line that says "the the the the" and watch it contribute nothing at all — the stop filter has already thrown those words away.

That is the whole shape of the index. A query for quick fox becomes "fetch the postings for quick, fetch the postings for fox, and combine them". The interesting questions are how to store lists with billions of entries, and how to combine them without reading all of them.

Step three: making postings small

A web index is dominated by its postings. If you stored every document ID as a 32-bit integer you would spend four bytes per posting, and for a term like "the" (if you kept it) or "online" that is a great many bytes. The trick that makes postings small is to store the gaps between sorted IDs — the d-gaps — rather than the IDs themselves. Common terms have small gaps, and small numbers can be written in very few bits.

The postings lab builds an index from a synthetic collection of 5,000 documents whose word frequencies follow Zipf’s law, as real language does, and compresses it every way you might reasonably try.

Bits per posting under every codec, for docID gaps, term frequencies and positions, on 5,000 Zipf-distributed documents.Open full tool →

Try this.

Read the docIDs column. Uncompressed is 32 bits a posting; VByte (Lucene’s old VInt: seven bits a byte, the eighth says "more follows") gets it under 10; Golomb and Rice coding, which are close to optimal when documents are scattered at random, get it near 6. The whole index drops from 3.66 MB to around 550 KB.
Now look at Simple-9, FOR-128, PForDelta and Lucene’s PForUtil. They are a bit or two worse than Golomb per posting, and that is the point: they pack 128 values at a fixed bit width so that a CPU can unpack them with shifts and masks, often with SIMD, instead of decoding bit by bit. Search engines trade a few per cent of space for several times the decoding speed.
Term frequencies compress superbly with γ or Golomb (about 1.4 bits), because nearly every tf is 1.
Roaring bitmaps look poor here at 18 bits a posting. They store document IDs, not gaps, and shine on dense lists and set operations — filters, mostly, rather than scored text.
Scroll down, pick a single term, and look at its gaps written out bit by bit.

Step four: not reading the whole list

Compression makes postings small enough to keep in memory. It does not stop a query for three common words from touching millions of documents. The second trick is to avoid scoring documents that cannot make the top ten.

The idea behind MaxScore and WAND is pleasingly simple. Each term has an upper bound: the best score it could possibly contribute to any document. Keep a heap of the best k results found so far; its lowest score is the threshold θ. A document that only contains terms whose upper bounds add up to less than θ cannot get in, so there is no need to score it — or even to stop at it. Block-Max WAND refines this with a maximum per block of 128 postings, so it can skip whole blocks.

The top 5 by BM25 over 5,000 documents: exhaustive scoring against MaxScore, WAND and Block-Max WAND, then step by step.Open full tool →

Try this.

Look at the Docs scored column. Exhaustive term-at-a-time and document-at-a-time scoring both score 3,463 documents. MaxScore scores 53. WAND and Block-Max WAND land around a hundred. Every row has a tick in Same top-k: the pruning is exact, not an approximation.
Notice why: the query’s first term, le, is in 3,111 documents but its upper bound is only 0.404, while the rare vuzesevi can contribute 2.417. Once the heap fills with documents that contain the rare words, the common term on its own can never compete.
Raise k from 5 to 100. The threshold rises more slowly, so pruning helps less — one reason engines retrieve a modest candidate set cheaply and rerank it with something heavier.
Use Step by step with WAND and watch the pivot: the first document at which the running sum of upper bounds could beat θ. Everything before it is skipped.

Step five: scoring a match with BM25

Retrieval finds the documents; scoring puts them in order. For thirty years the workhorse has been BM25, and it is still the first-stage scorer in Lucene, Elasticsearch and OpenSearch. For each query term it multiplies an idf (how rare the term is) by a tf factor (how often it appears here), with two knobs:

k1 controls saturation: how quickly repeating a word stops helping.
b controls length normalisation: how much a long field is penalised for being long.

BM25 on six short documents: “Lucene” three times barely beats “Lucene” once.Open full tool →

Try this.

The preset searches for lucene in the short-versus-long set. "Lucene Lucene Lucene" scores 0.395 and plain "Lucene" scores 0.390. Three times the term frequency buys about one per cent. That is saturation, and it is why keyword stuffing stopped working.
Look at the Classic TF-IDF column on the right. Lucene’s old scorer, which grows with √tf, ranks the one-word title first by a wide margin. Two formulas, two different answers.
Drag k1 to 3. Repetition keeps paying for longer and the gap widens. Drag it to 0 and tf stops mattering at all.
Drag b to 1 (or open example=length-norm) and length normalisation is total: a one-word document is the "densest" possible match, and the two Lucene-only documents tie.
Open the Curves tab to see the shapes behind these numbers: the tf curve flattening towards k1 + 1, the length curve tilting with b, and idf falling as a term gets common.
Click a row for Lucene’s full explain output, term by term.

BM25 is rarely the last word now. Production systems add field boosts, freshness, popularity, link-based authority and, increasingly, a learned model or a vector similarity on top. The Hybrid tab of the same tool fuses BM25 with toy embeddings using reciprocal rank fusion, which is how many teams combine lexical and semantic search today. But nearly all of them still use something like BM25 to pick the first few thousand candidates, because it is cheap, explainable and works straight off the inverted index.

Step six: knowing whether the ranking is any good

Change k1, add a boost, swap in a reranker — is the result better? Opinions are free, so search teams measure. The classic method is a set of queries with relevance judgements: people grade how useful each document is for each query, and metrics turn a ranked list of grades into a number.

One ranking with grades 3, 2, 3, 0, 1, 2 and two relevant documents never retrieved: precision, recall, AP, RR, nDCG and ERR.Open full tool →

Try this.

Read the coloured squares: the grades of the six results in rank order, and two dashed ones for relevant documents the system missed. Precision at 6 is 0.83 (five of six are relevant), but recall is only 0.71 because of the two it never found.
nDCG@6 is 0.785. DCG rewards high grades near the top, discounting each rank logarithmically; dividing by the ideal ordering (3, 3, 3, 2, 2, 2) makes it a number between 0 and 1.
Swap the 0 and the 3 in the grades box and watch nDCG drop. Put the best document last and it drops further. Position matters more than presence.
Try the ERR vs nDCG button. ERR models a user who stops at the first good result, so one perfect answer on top is nearly all it cares about; nDCG keeps counting.
For comparing two systems properly, see the Compare tab in the full tool (example=pooled-trec): 25 queries, BM25 against a reranker, and four significance tests that tell you whether the difference is real or noise.

Judged collections are expensive, so large engines lean on behaviour as well: clicks, dwell time, and interleaving, which merges two rankings into one list and lets real users' clicks vote. The Interleaving tab simulates exactly that.

Step seven: one index, many machines

Everything so far would run happily on one machine for a few million documents. The web is not a few million documents. Search engines split the index into shards — usually by document, so each shard holds a complete inverted index for its slice of the collection — and every query goes to every shard. Each shard returns its own top results with their scores, and a coordinator merges them.

Elasticsearch does exactly this inside a cluster, and the simulator shows it message by message.

Query then fetch: scatter to one copy of every shard, merge the candidates, fetch only the winners — then deep pagination and a slow node.Open full tool →

Try this.

Press Start. The first step scatters a search for error to one copy of each of the four shards; each returns only the IDs and scores of its own top five. The coordinating node merges those twenty candidates and only then fetches the five winning documents. Fetching every candidate’s full text would be far more expensive.
The narration points out something subtle: each shard scores with its own term statistics, so the same document could get a different idf on a different shard. On a big, well-mixed index the differences wash out; on a tiny one they can reorder results.
Keep going to Deep pagination. Asking for results 61–70 makes every shard return its top 70. This is why search engines cap how deep you can page, and why search_after exists.
The last steps slow one node down. A search waits for its slowest shard, so one sick machine slows every query that touches it — until adaptive replica selection learns to route around it.
Open the Fan-out tab. With a per-shard p99 of 60 ms and a 1% chance of any shard being slow, a search that touches 20 shards meets at least one slow shard 18% of the time, and its p99 is 126 ms — twice the p99 of any single shard. Drag the shard count up to see why this is called the tail at scale.

Step eight: the whole search engine

A web-scale engine wraps that core in a great deal more: crawlers and a document stream, a real-time index for pages published minutes ago next to the big batch-built index, a result cache (a surprising share of queries are repeats), query understanding (spelling, synonyms, intent), and a tree of root and mixer servers that fan each query out to thousands of index leaves and merge the answers. Each shard is replicated, partly for safety and mostly for throughput.

The system design tool has that architecture as a simulation, with an experiment that makes one leaf slow.

A web-scale search engine under load: one replica of one index shard becomes five times slower.Open full tool →

Try this.

Let the run play. Before the change at 5 s, p99 sits around 115 ms. After it, one replica of one shard is five times slower and p99 roughly triples while the error rate stays near zero. Nothing is "down"; the system is just slow, which is the hardest kind of failure to notice.
Find the slow leaf in the diagram: it is the busiest box, while its peers look normal.
Try Slow leaf, blind routing in the experiments list. Without least-loaded routing the damage is worse; with it, work steers away from the sick replica. Hedged requests — send the same request to a second replica after a short delay and take whichever answers first — trim the remaining tail.
Try Result cache cold and watch the index shards take the full load the cache was absorbing.
Switch from Simulate to Design or Deep dives for the architecture laid out box by box, or to Interview card for the condensed version.

Putting it together

Follow one query through what you have just played with. The words you type go through the same analyser the documents did, becoming terms. The root server sends those terms to every shard. Each shard decodes compressed postings lists, block by block, and uses upper bounds to skip documents that cannot make its top k. The survivors are scored with BM25 — and, these days, rescored by something more expensive. The root merges each shard’s best, fetches titles and snippets for the winners and returns them. Somewhere else, a team is measuring last week’s change with nDCG and interleaving to decide whether it stays.

None of the individual steps is hard. What makes web search remarkable is that each of them has been squeezed for decades: a few bits per posting, a few hundred documents scored out of millions, a few milliseconds per shard, and a tail latency watched as closely as the average.

Where to go next

The full tools, each with far more than the embeds show:

Analyzer and inverted-index playground — build your own analyser, try synonym graphs and edge n-grams for autocomplete, and phrase queries with slop.
Postings lab — compression codecs bit by bit, AND/OR intersection with skip pointers and galloping search, and MaxScore, WAND and BMW step by step.
Relevance and scoring explainer — BM25 in full, multi-field queries, function scores for popularity and recency, and hybrid search.
Ranking metrics — load your own TREC runs and judgements, compare systems with significance tests, and simulate interleaving.
Elasticsearch, simulated — indexing, near-real-time refresh, segments and merges, node failure and master elections.
System design interviews — the web search engine as a 60-minute mock interview, with the estimator to size it.
Vector search — the other half of modern retrieval.

And from my own work: ViewScene, a desktop tool for looking inside real Lucene indexes, and building a full social network from scratch, which has search as one of its parts.