Search and nearby

Part of the free System Design course on LogicWiz, in the chapter: Storage engines, search and geo. The interactive whiteboard exercises and simulations run in the app.

Week 10, Day 3: "mlik" returns nothing

"A customer typed 'mlik' and we showed 'No results'. We sell a hundred and forty kinds of milk."

Kabir, reading a support ticket aloud

Why LIKE '%milk%' does not scale

SwiftKart's first search box ran one SQL query: find products whose name is LIKE '%milk%'. The % means "any text here". It worked with a small catalogue. It fails at scale for three reasons.

Speed. A B-tree index on the name is sorted by the start of the name, like a phone book. It can find names that start with "milk". But a word in the middle has no place in that order. So the leading % forces the database to read every row. With about 200,000 products and 2,000 searches a second at the evening peak, that is 400 million row checks a second.

Relevance. It returns matches in no useful order. "Milkybar" matches "milk" as well as a litre of milk does.

Typos. "mlik" matches nothing.

Search needs a different index.

The inverted index: a textbook index for your catalogue

The index at the back of a textbook lists each word with the pages it appears on. An inverted index does the same for products:

  1. Tokenise each product, which means splitting its text into words (terms): "Amul Taaza Toned Milk 500 ml" becomes amul, taaza, toned, milk, 500, ml. Lowercase everything and reduce simple plurals, so "Eggs" is stored as egg.
  2. For each term, keep a posting list: the sorted ids of the products that contain it. milk → 12, 87, 403, and so on.
  3. To answer "toned milk", fetch both posting lists and keep the ids in both.

Because the lists are sorted, finding the ids in both is a quick merge. Say "toned" appears in 40 products and "milk" in 2,000. The work grows with those two lists, not with the 200,000-product catalogue.

The index is a derived copy. The catalogue database stays the source of truth. When a product changes, an event goes to an indexer, a worker that updates the search engine a second or two later. Elasticsearch and OpenSearch are the common choices. Both are built on the inverted index of Lucene, an open-source search library.

Ranking: which milk comes first?

"Milk" has 2,000 matches and the phone shows ten. Choosing those ten decides whether search feels good. Three ideas guide the choice:

  • Term frequency: a product that mentions a word more is more likely about it, with diminishing returns (the tenth mention adds little).
  • Rarer words matter more: of 200,000 products, "milk" appears in 2,000 (1 in 100) and "toned" in 40 (1 in 5,000). Matching "toned" says much more about what the shopper wants. So it gets more weight.
  • Shorter fields count more: "milk" in a four-word title beats "milk" buried in a long description.

The standard formula that combines these is called BM25. It is the default in Lucene-based engines such as Elasticsearch and OpenSearch. Shops then add their own signals: in stock at your nearest store, popular, on offer.

Meera's first plan was simple: "Search is a database query with a better index." Kabir pointed out that this covers only matching, the easy half. Choosing the order of 2,000 matches is what makes search good, and that is ranking, not lookup.

Two quick extras. Typo tolerance allows a small edit distance, the number of single-letter changes between two words. "mlik" to "milk" is one swap of neighbouring letters. "panner" to "paneer" is one changed letter. Engines typically allow no edits for very short words, one for short words and two for longer ones.

Autocomplete must answer within about 50 ms per keystroke, so it is served from memory. For each prefix ("pan", "pane"), it keeps a precomputed list of the most popular completions.

Riders near this store: why a plain index fails

Now a different question. The Koramangala dark store has an order ready and needs a rider within 2 km. Every rider's latitude and longitude arrives every few seconds.

Try a normal index on latitude. "Latitude within 2 km of the store" selects a strip a few kilometres tall. That strip runs across the entire width of India, full of riders in other cities. The database must then check longitude row by row. An index on (latitude, longitude) together does not help. It is sorted by latitude first, so it still scans the whole strip. A sorted list can serve a range on one dimension, not two at once. You need an index where points that are close on the map are close in the index.

Geohash cells and quadtrees

A geohash cuts the world into a grid, then cuts each cell again and again. It names each cell with a short string. A longer string is a smaller cell, and points in the same cell share the same prefix. Rough sizes:

  • 5 characters: about 5 km by 5 km.
  • 6 characters: about 1.2 km by 0.6 km.
  • 7 characters: about 150 m across.

The key idea: two dimensions become one string. So "riders in this cell" becomes an ordinary key lookup or prefix query that any database or cache can serve.

The query for a 2 km radius:

  1. Compute the store's 5-character cell.
  2. Fetch riders in that cell and its 8 neighbours.
  3. Compute the exact distance to each and keep those within 2 km, nearest first.

Why the neighbours? Because of cell borders. A rider may be 100 m from the store but across the border. That rider sits in a different cell, sometimes with a completely different prefix. Searching only the store's own cell misses them. With 5 km cells, the 3 × 3 block reaches at least one full cell (roughly 5 km) from the store in every direction. That comfortably covers 2 km.

At 10,000 pings a second, some pings cross a border. Each one moves the rider from one cell's set to another. An in-memory store handles this easily.

A quadtree solves the same problem with cells that change size. Start with one square for the city. Whenever a square holds more than, say, 100 riders, split it into four. Repeat. Busy Koramangala ends up with tiny squares and the empty outskirts with large ones. It suits uneven density but usually lives in one service's memory. Geohash is simpler and fits any key-value store.

📌 Summary: An inverted index maps each word to the products containing it; BM25 ranking picks the top ten. For "nearby", geohash cells turn a location into a string key. Always search the 8 neighbouring cells.

What Meera learns next

SwiftKart can now store, search and locate. Next week: the newest kind of system on the board, and how to design one that calls a large language model.

Check your understanding

  1. Search runs WHERE name LIKE '%milk%' on 200,000 products, and there is a B-tree index on name. Why is it still slow?
  2. A shopper searches "toned milk". "milk" appears in 2,000 products and "toned" in 40. Under BM25-style ranking, which word does more to decide the top results?
  3. Nearby search looks only in the store's own geohash cell. A rider 100 m from the store is never found. What is the fix?