How Search Works

Search feels like magic until you build one. Then it collapses into four steps that never change, and a hundred choices about how to do each step. This series is about those choices. Start here, with the four steps.

Picture a huge library. To find every book that mentions photosynthesis, you could pull each one off the shelf and skim it, which would take a lifetime. Instead you walk to the catalog, look the word up, and it points you straight at the right shelves. Every search engine is a version of that catalog, built so you never have to read the whole library.

The shape of the problem

Every search engine, from grep to Google to a vector database, solves the same problem: you have a large collection of items and a query, and you want the few items most relevant to that query, quickly. The naive approach is to compare the query against every item. That is correct and hopeless: a million documents scanned on every keystroke of an autocomplete box is a million comparisons per keystroke. Search is the art of not doing that.

Four steps recur no matter the technology:

1. Index: process the collection ahead of time into a structure built for lookup.
2. Parse: turn the query into the same shape the index understands.
3. Match: use the index to find candidate items without scanning everything.
4. Rank: order the candidates by relevance and return the top few.

The index is where the cleverness lives, because it is what lets the match step skip the scan.

The inverted index

The oldest and still most common index for text is the inverted index. A normal (forward) index maps a document to its words. An inverted index flips that: it maps each word to the list of documents that contain it. That list is called a postings list.

Make it concrete. Take five tiny documents:

d0: fast red fox
d1: red fast car
d2: quiet fox den
d3: red fast engine
d4: blue fox tail

The inverted index reads them once and records, for each word, where it appears:

fox  → d0, d2, d4
fast → d0, d1, d3
red  → d0, d1, d3
car  → d1

Now a query for fox is not a scan of five documents (or five million). It is a single lookup that returns d0, d2, d4 directly. Multi-word queries combine postings lists with set operations. A search for fox AND fast intersects the two lists, {d0, d2, d4} and {d0, d1, d3}, and keeps only what is in both: just d0. Switch to fox OR fast and you union them instead, returning everything: d0, d1, d2, d3, d4.

This is boolean retrieval, and it is exact: a document either contains the term or it does not. It is fast because the index turned "search" into "look up a key and combine some lists." Every keyword engine, from Lucene to Elasticsearch to OpenSearch, is an elaboration on this one idea.

Here is that exact index made live. Toggle query terms, switch AND and OR, and watch the postings resolve into the matching set (it starts on fox AND fast, which lands on d0, just like above):

Matching is not ranking

Boolean retrieval tells you which documents match. It does not tell you which match best. Search a news archive for fast red fox and a thousand articles contain all three words. Boolean retrieval hands you all thousand, in document-id order, which is no order at all. The one you want could be number 847.

Ranking is the separate step that scores each candidate and sorts them. For text, the classic score is BM25, which rewards documents where the query terms appear often and where those terms are rare across the whole collection: an article matching "photosynthesis" is more informative than one matching "the". Ranking is where most of the quality of a search engine lives, and it is the subject of the next part.

The split matters. Matching narrows a million documents to a thousand cheaply; ranking orders the thousand carefully. Doing the expensive scoring only on the survivors is what keeps search fast.

The two ways to be wrong

There are exactly two failure modes, and they trade off against each other.

• Precision: of the results you returned, how many were actually relevant? Low precision means junk in the results.
• Recall: of all the relevant documents that exist, how many did you return? Low recall means you missed things.

An example makes the difference sharp. Say a support inbox has 8 tickets genuinely about a login bug. Your search returns 10 results, and 6 of them are really about the login bug. Precision is 6 out of 10 returned, so 60 percent. Recall is 6 out of the 8 that exist, so 75 percent. You returned some junk (4 irrelevant results) and you also missed some real ones (2 relevant tickets never showed up).

You can always buy recall by returning more, and precision by returning less: return all 10,000 tickets and recall hits 100 percent while precision collapses; return only the single most confident result and precision is likely 100 percent while recall craters. The whole craft of search is pushing both up at once: returning the relevant things, and only the relevant things. Every technique in this series is, underneath, a different bet on how to win that tradeoff.

Exact is not enough

The inverted index is exact and lexical: it matches the literal word. That is a strength and a cage. Search for car and a document that only says "automobile" will not match, even though it is exactly what you wanted. Type paymnet instead of payment and you get zero results, because that misspelled string is simply not a key in the index. And for some data, such as images, product recommendations, or raw meaning, there are no words to invert at all.

Escaping that cage is what the rest of search is about, and it is why one index type became many. The series ahead:

• Text analysis: how raw text becomes the clean terms an index actually stores.
• Keyword search: BM25, and why term rarity is the whole game.
• Fuzzy and prefix search: matching through typos, and as you type.
• Vector search: turning meaning into geometry so "car" and "automobile" land near each other.
• Approximate nearest neighbor: doing that geometric search fast enough for a billion vectors, the trick behind OpenSearch's vector engine.
• Hybrid search: combining lexical and vector so you keep the strengths of both.
• Reranking: a second, careful pass that reorders the top results.

Four steps, one tradeoff, many indexes. That is the whole shape of it. Next: how ranking actually scores a match.