The whole course ▾

System Design · Lesson 26 of 39 · Week 6

Search: inverted indexes and typeahead

Updated 22 Oct 2026 · By Akshay, software engineer, India · 5 min read

A customer types "paneer" into QuickBite's search, and waits four seconds. Two million dishes, one slow query. Today: search.

The video for this lesson is coming soon.

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

QuickBite in this lesson

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

LIKE percent paneer
Customer app
Menus
service
Menus DB
2 million dishes
search: paneer
LIKE '%paneer%'
full scan: 4 s
no ranking, no typos

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

The inverted index
Word -> dishes
->
paneer -> 12, 87, 203…
->
tikka -> 12, 45, 310…
->
pizza -> 87, 99, 512…
How a search runs
1
Look up each word's list
2
Intersect: paneer AND pizza -> 87
3
Score the matches, sort, top 20

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

Typos, plurals and synonyms
Normalise every word
Lowercase: Paneer = paneer
Stem: rolls -> roll
Synonyms: cottage cheese -> paneer
Fuzzy: paner -> paneer
RANKING, IN ONE LINE
Rarewordsinimportant
fieldsscorehighest;then
boostpopular,nearbyand
openrestaurants.

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

Running a search engine
Menus
service
Menus DB
the source
of truth
Change
stream
CDC
into
Kafka
Indexer
Search
cluster
shards and
replicas
Customer
app
edit a dish
1
every
change
2
3
update
index
4
search
Inside the cluster
->
The index is split into shards
->
Each shard has replicas
->
Every shard answers; results
merged

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

Results while you type
Typeahead
1
Index prefixes: p, pa, pan, pane…
2
Top suggestions per prefix, precomputed
3
Wait 100 ms between keystrokes
4
Cache the popular prefixes
TWO DIFFERENT JOBS
Searchfindsmatching
dishes;typeahead
suggestssearches,from
asmall,precomputedset.

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

In the interview
SAY THIS IN THE INTERVIEW
SearchinElasticsearch:
aninvertedindex,
shardedandreplicated,
keptinsyncbyCDC.
Follow-ups to expect
->
Why not search the database?
->
How fresh are the results?
->
How do you rank?
THE COMMON MISTAKE
Treatingthesearch
indexasthesourceof
truth:it'sacopy,rebuilt
fromthedatabase.

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

Quick check
?
Why can't a B-tree index
speed up LIKE '%paneer%'?
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"?
Dish 87: the only one in both
lists.
Remember
Inverted index: word ->
documents
Normalise: lowercase, stem,
synonyms, typos
The database is truth; search
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.

Quick check

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.

Practise with flashcardsYour progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.