Design search autocomplete
A trie of top queries served in milliseconds - prefix lookups, cached suggestions, and ranking by popularity as you type.
9 min read
Autocomplete looks like a search feature. It is really a latency problem in disguise: the suggestions have to be on screen before your finger leaves the next key.
Every keystroke is a search request
The obvious implementation runs a prefix query against the log of past searches on every keypress. It works beautifully with ten thousand rows and a hundred users. The arithmetic stops working well before you are a real product.
Every character is a round trip, so request volume is search volume multiplied by query length, and each request has a budget of a few dozen milliseconds. A suggestion that arrives after the next keystroke is worse than none: it flickers. No amount of indexing makes a general-purpose database answer that fast at that rate. You need a structure built for exactly one question.
A tree where the path is the prefix
A trie (a prefix tree) stores each past query one character per node, so the path from the root spells the query. Finding everything that starts with “tr” is not a search at all: it is two hops, then a subtree.
Locating the prefix costs one hop per character typed and nothing else. Ten queries or ten billion, finding “tr” is two hops; the dataset's size only affects what you find when you arrive. The trie is rebuilt offline from aggregated search logs, because autocomplete is read-heavy and perfectly happy to be an hour out of date.
The first letter is the expensive one
Walking to the node is cheap and constant. Gathering and ranking everything beneath it is neither, and the shorter the prefix, the bigger the subtree. The worst case is the very first keystroke, which every single search makes.
The fix trades memory for time: store the top five completions at every node when the trie is built. Answering any prefix becomes a walk to the node plus reading five stored entries, whatever lies below. It multiplies the trie's size, and it is worth it, because the trie is rebuilt offline anyway and reads outnumber rebuilds by millions to one. Real systems add the remaining layers: shard the trie by prefix, cache the hottest prefixes at the edge, and filter what may be suggested at all.
The short version
- Every keystroke is a request, so load is searches times characters, each with a ~100 ms budget.
- A trie finds a prefix in one hop per character, independent of dataset size.
- Short prefixes have huge subtrees; store the top-k at every node to make them instant.
- Rebuild offline from logs; suggestions can be an hour stale.