The whole course ▾
System Design · Lesson 26 of 39 · Week 6
Search: inverted indexes and typeahead
A customer types "paneer" into QuickBite's search, and waits four seconds. Two million dishes, one slow query. Today: search.
New System Design videos go up at 6 pm. Subscribe on YouTube so you don't miss it.
Got a doubt? Ask in the comments under the video.Subscribe
Searching QuickBite's 2 million dishes.
QuickBite is the food delivery app we grow through the course, from one server to millions of orders.
LIKE percent paneer
QuickBite now has fifty thousand restaurants and two million dishes. Customers expect to type a word and see results before they've finished typing it.
Today, search is a single SQL query. The customer app sends the word paneer to the menus service, which asks the menus DB for every dish whose name or description is like percent paneer percent: containing that word anywhere at all.
Remember lesson ten? An index can't help here. The word could be anywhere in the text, so the B-tree's sorted order is useless, and the database reads all two million rows: four seconds. And even when it's fast, the results are poor. A typo, like paner, finds nothing. Paneer tikka and a pizza with a little paneer come back in random order. And paneer pizza needs both words, in any order. Databases aren't built for this. Search engines are.
The inverted index
Every search engine, from Google to the search box in your email, is built on one simple data structure.
Instead of storing each dish's text and searching through it, flip it around. For every word, keep a list of the dishes that contain it. Paneer: dishes twelve, eighty-seven, two hundred and three. Tikka: twelve, forty-five. Pizza: eighty-seven, ninety-nine. That's an inverted index, inverted because it maps words to documents, instead of documents to words. It's the index at the back of a textbook, once again. The lists are compressed tightly, which is why they stay fast even at enormous sizes.
Now search for paneer pizza. Look up each word's list: one lookup per word. Intersect the lists: only dish eighty-seven appears in both. Then score each match: is the word in the dish's name, or buried in a long description? Is it a rare word, or a common one? Sort by score, and return the top twenty. A few milliseconds, even across millions of dishes. Each list is kept sorted by dish ID, so intersecting two lists is a single quick walk through both.
Typos, plurals and synonyms
A raw inverted index is fast, but fussy. The magic of good search happens before a single word is stored.
Every word goes through the same steps, both when dishes are indexed, and when a customer searches. Lowercase it, so Paneer with a capital matches paneer. Stem it, so rolls and roll become the same word. Add synonyms, so cottage cheese finds paneer. And allow fuzzy matches, words one or two letters apart, so paner, with a typo, still finds paneer. Each step makes more of the right dishes match.
And ranking, in one line. A match scores higher when the word is rare across all dishes, and appears in an important field like the name. Elasticsearch's default formula, called BM25, does exactly that. Then QuickBite adds its own boosts: popular dishes, nearby restaurants, and ones that are open right now. Ranking is where search teams spend most of their time.
Running a search engine
You don't build this yourself. You run a search engine, like Elasticsearch or OpenSearch, alongside your database.
The menus DB stays the source of truth: dishes are created and edited there, by the menus service. Every change flows out through a change stream: change data capture, which reads the database's own change log, the same one replicas use, into Kafka. An indexer reads that stream and updates the search cluster. And the customer app's searches go straight to the search cluster, never touching the database at all. And if the index is ever damaged, it's rebuilt from the database.
Inside, the index is split into shards, so two million dishes, or two billion, spread across many machines. Each shard has replicas, for speed and for safety. A search goes to every shard at once, each returns its best twenty, and the results are merged: lesson twelve's scatter and gather, used on purpose. A changed dish shows up in search about a second later, which is perfectly fine for menus.
Results while you type
One more expectation: suggestions after just two or three letters.
Typeahead works differently. Index prefixes: p, pa, pan, pane, so every partial word is a quick lookup. Better still, keep the top suggestions for each prefix precomputed, from what people actually search for. On the phone, wait about a hundred milliseconds after each keystroke, so a fast typist sends one request, not seven. And cache the popular prefixes, because half of all searches start with the same few letters.
Notice these are two different jobs. Full search finds dishes that match a query. Typeahead suggests the query itself, from a small, precomputed list, and it must answer in tens of milliseconds. Lesson thirty-three designs typeahead properly, at Google's scale.
In the interview
Search appears in almost every product question: dishes, products, people, places, posts.
Say it like this: search runs on Elasticsearch, an inverted index, sharded and replicated, kept in sync from the database by change data capture through Kafka. The database stays the source of truth, and the index is a copy that can always be rebuilt from it.
Then expect these. Why not search the database? Text search needs an inverted index, and searching would slow down the database's real job. How fresh are the results? About a second behind, through the change stream. And how do you rank? Text relevance first, like BM25, then business boosts: popularity, distance, and whether the restaurant is open. And dish names typed in different spellings, like paneer and panir? Add common spellings as synonyms, or index how the words sound.
The common mistake: writing new dishes straight into the search engine, and nowhere else. Search clusters are built for finding things, not for keeping them safe. The database is the truth, and the index is a copy.
Quick check
Why can't a B-tree index speed up LIKE '%paneer%'?
Show the answer
Because the word can be anywhere in the text; a sorted index only helps with the start.
paneer → 12, 87, 203 and pizza → 87, 99. Which dish matches "paneer pizza"?
Show the answer
Dish 87: the only one in both lists.
Remember: an inverted index maps each word to the documents that contain it. Normalise every word: lowercase, stems, synonyms and typos. And the database is the truth, while the search index is a copy, kept in sync. Tomorrow: finding the riders nearest to a restaurant.
Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.