Search & Inverted Indexes
Why LIKE '%word%' scans every row while a search engine answers in milliseconds: analyzers, postings lists, BM25 scoring, near-real-time refresh, and scatter-gather across shards that can be slow or gone.
An interactive System Design lesson: 18 steps, about 35 minutes, on a live simulation in your browser.
The engineering blog has 2,000,000 articles in a Postgres table, articles, with a primary key and nothing else. The first version of the search box runs SELECT id, title FROM articles WHERE body LIKE '%replica%'.
Seq Scan, all 250,000 pages, 2.7 s: 416,667 rows come back and 1,583,333 are removed by the filter. The planner guessed 128, because statistics say nothing about what is inside a text. A B-tree cannot help with a leading wildcard ("Indexes & Query Plans" showed why): it is sorted from the first character, and the word can be anywhere.
What you will learn
Searching with LIKE
- A search box on Postgres: LIKE '%word%' is a substring test run on every row: the cost grows with the whole corpus, and the answer has no ranking.
- Ask the search index
The inverted index
- Term to documents, not document to terms: An inverted index maps each term to the documents that contain it. A query reads the lists for its terms, so its cost follows how common the terms are, not how big the corpus is.
- The analyzer: Search matches terms, not text. The analyzer decides what a term is, and it must treat documents and queries the same way or they will never meet.
- Break it: keep the stop words: A term that appears everywhere costs the most to read and tells you the least. Stop words are dropped because they are expensive noise.
Ranking with BM25
- Why a1 comes first: BM25 rewards terms that are rare in the corpus and frequent in the document, with diminishing returns for repetition and a penalty for length.
- Words next to each other
- Drill: a phrase query
Near real time
- Index it, then search for it: Search is near real time: an acknowledged write becomes searchable at the next refresh, not at once.
- One second later
- refresh=wait_for and refresh_interval
Scatter-gather across shards
- One slow shard: A scatter-gather query is as slow as its slowest shard. More shards means more chances that one of them is having a bad moment.
- Break it: lose a shard's primary: Each shard copy is a full copy of that slice of the index. Losing one copy changes nothing for searches as long as another copy of the same shard lives.
- No copy left: A search with a missing shard still returns 200. The only sign is _shards.failed, so a client that ignores it shows users silently incomplete results.
- Drill: where are the shards?
Whose statistics?
- Scores from one shard's point of view: Relevance scores are computed per shard by default. The same document can score differently depending on which shard it lives on, until shards are large enough that their statistics agree.
Recap & playground
- Cheat sheet
- Playground