Search Systems
Build full-text search on an inverted index: tokenising, matching, ranking in outline, and keeping the index in step with the database.
On this page
A shop has 20 million products. Search runs WHERE title LIKE '%red shoes%'. A pattern that starts with % cannot use an ordinary index, so every search reads every title and description: 20 × 106 × 1 KB = 20 GB per query. At 500 searches a second, that is 10 TB read a second. It also misses "Red Shoe" and "shoes, red", and it cannot say which match is best.
Search engines solve all three with one structure built ahead of time: the inverted index.
The idea
A normal index maps a row to its contents. An inverted index maps each word to the list of documents that contain it, the way the index of a cookbook maps "garlic" to pages 12, 40 and 97. A query looks up each of its words and combines the lists. The work depends on how many documents match, not on how many exist.
The cost: the index is a second copy of your data, built by a separate system, and it is always a little behind the database. The database stays the source of truth; the index is a derived copy you can throw away and rebuild.
From text to tokens
Before indexing, each text goes through an analyser: split into words, lowercase, drop punctuation, and reduce words to a stem so "shoes" and "shoe" match ("running" becomes "run"). The query goes through the same analyser. If the index stems and the query does not, "shoes" finds nothing.
Four products, analysed:
| Doc | Title | Tokens |
|---|---|---|
| 1 | Red Running Shoes | red, run, shoe |
| 2 | Blue running shorts | blue, run, short |
| 3 | Red leather shoe | red, leather, shoe |
| 4 | Red rain jacket | red, rain, jacket |
The inverted index lists, for each token, the sorted ids of the documents that contain it (its postings): red → [1, 3, 4], shoe → [1, 3], run → [1, 2], and one-document lists for the rest. Step through the query "Red shoes".
- query0Red1shoestokens0red1shoe
1The query runs through the same analyser as the documents: "Red shoes" becomes the tokens
redandshoe. - red011324shoe0113
2Look up both postings lists. Each is sorted by document id, which makes combining them cheap.
- red01i1324shoe01j13
- matches
- [1]
3Both lists start at 1. Equal ids mean document 1 has both words: a match. Move both pointers.
- red0113i24shoe0113j
- matches
- [1, 3]
43 and 3: another match. Move both.
- red011324ishoe0113j
- matches
- [1, 3]
- comparisons
- 2
5The shoe list is finished, so no later document can have both words. Document 4 (the red jacket) is never compared against anything.
That merge is the two-pointer pattern: O(a + b) for lists of length a and b. The token dictionary itself is kept sorted or in a structure like a trie, which also answers prefix queries such as "sho" for autocomplete.
Ranking, in outline
Matching finds candidates; ranking orders them. The classic text score, BM25 (a refinement of TF-IDF), rewards three things: the query word appears often in the document (with diminishing returns), the word is rare across all documents (here "shoe" is in 2 of 4 documents and "red" in 3 of 4, so "shoe" says more), and the document is short, so the match is a bigger part of it. On top of that, products add business signals: a match in the title beats one in the description, and popularity, stock and freshness lift results. In an interview, naming those layers is enough.
Keeping the index in step
| Option | Good at | Bad at | Pick it when |
|---|---|---|---|
| Dual write from the app | Simple to start: after writing the database, the app writes the index too. | If the second write fails or the app crashes between them, the two disagree forever. Two writers can also arrive out of order. | Prototypes only. |
| Change data capture Usual default | Every committed change flows from the database's log into a stream, ordered per product; an indexer applies them and can replay after a crash. | More moving parts. The index lags by seconds. | Production systems. The usual answer. |
| Periodic rebuild | Simplest correct option: rebuild the whole index every night and swap it in. | Changes appear only after the next rebuild. Slow for huge catalogues. | Data that changes rarely, and as the recovery path for the other two. |
1A seller renames product 881 to "Red trail shoes". The product service writes only the database, the source of truth.
2The commit lands in the database's change log, and change data capture publishes it to the stream. The app never writes the index.
3The indexer reads the event, analyses the new title, and replaces document 881 in the index. About a second later it is searchable.
4A shopper searches "trail shoes". The query fans out to every index shard; each returns its top 10, and the results are merged into one top 10.
5The service fetches price and stock for those ids from the database (or its cache). The index finds products; the database is trusted for money.
6The indexer crashes. Edits keep committing and pile up in the stream, which keeps them for days. Search shows old titles for a while; nothing is lost.
7On restart it resumes from its last saved position. Each event carries the row's version, and the index ignores any event not newer than the version it holds, so a replayed or late event cannot undo an edit.
Numbers worth remembering
- Index-to-searchable delay with change data capture: usually about a second or a few seconds.
- Index size: number of postings × a few bytes each once compressed (more if you store word positions for phrase search).
- Below a few million documents and simple matching, the database's built-in full-text index is often enough. Say so before adding a cluster.
About how big is the postings data for the product catalogue?
- 20 million products
- About 100 tokens per product after analysis
- About 4 bytes per posting once compressed
Show the working
- 20 × 106 × 100 = 2 × 109 postings
- 2 × 109 × 4 B = 8 × 109 B = 8 GB
Estimate 8 GB (anything from 3 GB to 30 GB is a good answer)
8 GB fits in memory across a few machines, with replicas for query load. Against 20 GB scanned per query, that is the whole case for an index.
In the interview
Add a search index when the requirements include free-text search, typo tolerance, relevance ranking, or filtering on many fields at once. Say three things: what is indexed, how it stays in sync, and what is still read from the database.
Users need to search products by text. Can't the database do it?
For 20 million products with ranking and typo tolerance, I'd add a search index. The database stays the source of truth; the index is fed by change data capture, so it's a second or two behind and can be rebuilt from scratch. Search returns ids, and I read price and stock from the database so a stale index never shows a wrong price.
How do you shard the index?
By document: each shard indexes a slice of products, and a query asks every shard for its top results and merges them. Sharding by term would let a query hit fewer shards, but a single product update would touch many shards, so document sharding is the usual choice.
Follow-ups you should expect:
- "How do you handle typos?" Fuzzy matching within a small edit distance, or indexing character n-grams, at the cost of a bigger index and more candidates to rank.
- "How do you do autocomplete?" A separate, small prefix index of popular queries; see Design Typeahead Search.
- "How do you change the analyser?" Build a new index alongside the old one, replay into it, then switch reads over in one step.
Common mistakes
Postings: trail → [2, 5, 8, 9] and shoe → [1, 5, 9, 12]. Which documents match "trail shoe"?
Why is change data capture preferred over the app writing the index directly?
In a catalogue of 1 million products, "waterproof" appears in 2,000 and "black" in 300,000. For the query "black waterproof", which word should weigh more in ranking?
What to practise next
The change stream that feeds the indexer is covered in message queues and streams, and replaying safely in idempotency and retries. Put prefix search to work in Design Typeahead Search.