Design search autocomplete and Top-K
How do you suggest “paneer” after two letters, in 50 milliseconds?
Why does the search box show pasta for pav?
By autumn the app lists about 2,000 home cooks and 30,000 dishes. Most lunches now start in the search box on the home screen.
At 12:20 a student in a hostel room types p, a, v. He wants pav bhaji. The box shows nothing. Then “Pakoda, half plate”. Then “Pasta”. Then pav bhaji flickers in for a moment and is replaced by the list for p.
The cause is in the first version of the search box. It sends every keystroke to the server, and the server asks the orders database for dishes whose name starts with those letters, ranked by how often they were ordered in the last 90 days. The database counts nine million order lines to answer each keystroke. The answers come back slowly, and not always in the order they were asked. The kitchen’s order screen slows down with them, because it shares the database with everyone who is still deciding what to eat.
Compare the counter, where customers order in person. When someone says “pa”, the cook already knows: pav bhaji, then paneer tikka. Nobody counts last year’s slips while the customer stands there. When a new dish gets popular, the counter knows by the evening, and that is soon enough.
What the counter cannot do is hold the favourites for every beginning of 30,000 dishes, change them as tastes change, and answer 200,000 customers between two keystrokes. Before reading on, put a number on each of two things: how often the ranking needs to change, and how often a keystroke arrives. The design follows from the gap between those two numbers.
Pause and predict Every keystroke counts nine million order lines. The counter answers “pa” at once because the answer is already known. What should the server do instead?
What must never go wrong?
Suggestions sit between a customer and their lunch. Two rules follow. They must never slow down ordering, and they must never suggest a dish the kitchen has withdrawn, or a word nobody should see.
Core entities, in two minutes
A Search (what someone finally searched for, and when), a Query score (a normalised query and its decayed popularity), a Prefix table (prefix → top five queries, built and published as one version), and a Block (a query staff have removed).
The estimate that changes the design
Requests: 120,000 searches x 4 = 480,000 a day, 5.6 a second on average and about 56 a second at a tenfold lunch peak. That is small.
The table: assume 200,000 distinct queries over 90 days (spelling variants included). Store prefixes up to 10 characters, at about 80 bytes an entry (the prefix, five short ids, map overhead).
Pause and predict Where should a table of every prefix and its top five live?
At 50 million searches a day the same arithmetic gives about 2,300 requests a second (7,000 at a threefold peak) and, with an assumed 100 million distinct queries, an 80 GB upper bound. That table must be trimmed and sharded. The design stays the same; only the machines change.
The obvious version, and how it breaks
The first version needs no new parts. A route in the ordering app runs one query per keystroke:
SELECT d.name, count(*) AS n FROM order_lines l JOIN dishes d ON d.id = l.dish_id WHERE d.name ILIKE 'pa%' AND l.created_at > now() - interval '90 days' GROUP BY d.name ORDER BY n DESC LIMIT 5;It ranks correctly and it is always fresh. It breaks three ways at lunch:
- It does the work at read time. Finding dishes that start with “pa” can use an index (with PostgreSQL’s
text_pattern_ops, see lesson 2.4). Counting their order lines cannot: it reads every matching line in 90 days, for every keystroke, and the answer is the same for everyone. - It asks on every keystroke. An eight-letter search is eight requests. On a slow connection the replies can arrive out of order, which is why pav bhaji flickered in and vanished.
- It counts the wrong thing. Orders record what people bought, and the searches record what they looked for. A dish nobody can find never gets ordered, so it never gets suggested. And nothing fades: last year’s festival sweet still ranks on its old orders.
In numbers: 120,000 searches x 8 keystrokes is 960,000 queries a day, about 111 a second at the lunch peak.
Pause and predict Each of those 111 queries a second takes 600 ms of database time. How many cores are busy counting?
A mental model
- Trie
- A tree of characters: each node is a prefix, and its children add one more letter. Walking down p → a → v reaches the node for “pav”, under which sits every query starting with “pav”.
- For example: The nodes for “pa” and “pav” are separate. If each node also stores its top five queries, a lookup is a walk of three steps and a read.
- Top-k
- The k highest-ranked items. For autocomplete, the k most popular queries that start with a prefix, with k about 5 to 10.
- For example: Top 3 for “pa”: pav bhaji, paneer tikka, palak paneer.
The build job picks each top five with a small heap of size k, one pass over the counts. Heaps and top-k in Coding Patterns.
Rebuild hourly, or count as it happens?
One goal is that a trending dish appears the moment it trends. The other is numbers that can be checked.
Freshness has value: a national food app whose trends move in minutes might need the stream. At the kitchen’s scale tastes change over days, an hourly table is fresher than the counter ever was, and the batch job is the one thing a two-person team can rerun and trust.
What to remember
- Autocomplete is a precomputed read: rank once at build time, store the top few for every prefix, and answer each keystroke with one lookup.
- Split the read path (phone, edge, in-memory table) from the build path (log, hourly job, versioned snapshot). Neither touches the orders database.
- Once each node stores its top k, a trie and a flat prefix table hold the same lists. Choose the container by how the table is shipped and sharded.
- Popularity needs decay, or last year’s favourite never leaves.
- A count-min sketch counts in fixed memory, never under, and within ε x total with probability 1 − δ: good for heavy hitters in huge streams, unnecessary when an exact map fits.
Rank the suggestions when nobody is waiting, so a keystroke is one lookup.
In the real world
Real autocomplete adds what this toy leaves out: spelling tolerance (“panir” finds paneer), several scripts and transliteration, personal and local signals blended with global popularity, filters against offensive or manipulated suggestions, and ranking models trained on what people click as well as what they type. Large engines shard the prefix table across many machines and cache the short prefixes at the edge and in the browser.
The core stays what you built: rank in advance, look up at once, and let popularity fade. The same idea, doing the work when data is written so reads are cheap, returns in the news feed (lesson 4.3), and the sorted set behind a live ranking returns in the leaderboard side quest.