What it is
A regular database index is great for exact lookups, but terrible at "find products whose description mentions wireless headphones". Search engines like Elasticsearch and OpenSearch use an inverted index: for every word, a list of the documents that contain it.
| Word | Documents that contain it |
|---|---|
| wireless | 2, 7, 9, 15 |
| headphones | 2, 9, 31 |
| noise | 9, 31, 40 |
Searching "wireless headphones" means intersecting two lists: documents 2 and 9.
How it works
Before indexing, text is broken into words and cleaned up: lowercased, punctuation stripped, and often cut down to a root so "running" and "runs" both match "run". Queries go through the same steps, so they match.
Matching documents then get scored. The classic scoring, BM25, ranks a document higher when the search words appear in it a lot and are rare across all documents. Real products mix in other signals, like popularity, ratings or distance.
The index is split into shards across machines. A query goes to every shard, each returns its top results, and a coordinator merges them.
Trade-offs
The index is updated a little after the database, often around a second, so a new product might not show up in search right away. That's usually fine. Using the search engine as your main database usually isn't, since it's not built for transactions.
In an interview
- Keep the database as the source of truth and explain how changes reach the index.
- Say how results are ranked, not just how they're found.
- Mention how fresh results need to be, and what happens if the indexer falls behind.
Worked example
Searching a product catalog
A store has 50 million products and gets 5,000 searches a second. Searching 'red running shoes' should return relevant results in under 200 ms, and new products should be searchable within a minute.
- Products live in the main database. Every change goes onto a change stream, and an indexer turns each product into a search document: title, description, brand, category, price, rating.
- The indexer breaks text into words, lowercases them and cuts them to roots, so 'Running' and 'runs' both become 'run'.
- The index is split into, say, 10 shards of 5 million products each, with a replica of each shard to share the search load.
- A search for 'red running shoes' goes through the same text cleanup, then to every shard. Each shard finds products with those words, scores them, and returns its top 50.
- A coordinator merges the 10 lists and keeps the best 50 overall. Filters like 'size 10' or 'under $100' are applied on the shards, before scoring.
- The final ranking mixes text relevance with popularity, ratings and stock, so an out-of-stock shoe that matches perfectly doesn't come first.
- Price and stock change often. Those can be checked against the main database for the 50 results on the page, so search never shows a wrong price.
Follow-up questions
Things interviewers tend to ask once you've brought this up.
- How would you build autocomplete?
- Precompute popular queries and product names by prefix, and keep them in memory or a trie, so each keystroke is a quick lookup. Rank suggestions by how often people search them.
- How do you handle typos?
- Fuzzy matching allows a word to be one or two letters off. It's slower, so many systems try an exact search first and only go fuzzy if there are few results.
- What if the indexer falls behind?
- Search shows older data until it catches up. Watch how far behind it is, and alert. Because the change stream keeps the updates, nothing is lost, just late.
- How do you rebuild the whole index?
- Build a new index next to the old one from a full export, replay changes that happened during the build, then switch searches over to the new one.
Common mistakes
- Using SQL LIKE '%shoes%' on a big table.
- Making the search engine the only copy of the data.
- Only talking about finding matches, not ranking them.
- Not saying how changes get into the index, or how fast.
- Treating autocomplete as the same problem as full search.