How does search autocomplete work?

Completions are pre-computed offline and served from memory. Every finished search a user types is logged; a batch job aggregates those logs into query counts and builds a trie — a tree where each edge is a letter, so the path from the root spells a prefix. At every node the build stores the top few most-popular completions beneath it. At request time the service walks the prefix down the trie (one hop per letter) and returns the list already sitting at that node — so a keystroke is answered by reading a cached list, not by scanning the database. Facebook’s typeahead post gives the reason speed matters this much: "spending more than 100 msec to retrieve a result will cause the typeahead to ‘stutter,’ leading to a bad user experience that is almost impossible to compensate for with quality."

Why not just run a database LIKE query on every keystroke?

Because autocomplete fires a query on every keystroke, not once per search — so its request rate is roughly the number of keystrokes per search (often ~20) times the search rate. A service with millions of daily users doing tens of searches each lands in the tens of thousands of autocomplete queries per second, every one of which would be a prefix scan (WHERE query LIKE 'prefix%') that also has to rank the matches. A relational index can find the prefix range but still has to sort the matches by popularity per request, under a sub-100 ms budget, at that rate. The trie moves that sort offline: the ranking is done once at build time and cached at each node, turning per-keystroke work from a scan-and-sort into a single list read.

What is a trie with cached top-k?

A trie is a tree keyed by the characters of a string: the root is the empty prefix, and following an edge labelled with a letter extends the prefix by that letter, so every node corresponds to exactly one prefix. "Cached top-k" means that when the trie is built, each node also stores the k most-popular full queries that live in its subtree, already ranked. Answering a prefix is then two cheap steps: walk down the trie one node per letter to reach the prefix node, and return its stored list. Without the cache the service would have to walk the entire subtree under the prefix, collect every candidate, and sort them on each request — which for a common two-letter prefix can mean visiting dozens of nodes instead of two. Elasticsearch’s completion suggester makes the same trade explicitly: it "is optimized for speed" and "uses data structures that enable fast lookups, but are costly to build and are stored in-memory."

How does autocomplete stay fresh, and what does it miss?

The trie is rebuilt on a schedule — often daily or weekly — from the accumulated query logs, and the new snapshot is shipped to the serving machines to replace the old one. For the vast majority of queries this is honest: what people search for shifts slowly, so a week-old ranking is almost identical to today’s. The thing it misses is a sudden trend. A brand-new query that spikes today has no counts in last week’s logs, so it is absent from the current trie and cannot be suggested until the next build folds it in — which is why real systems bolt a separate, faster-moving trending path onto the slow batch trie rather than trying to make one pipeline do both.

How is an autocomplete trie sharded across machines?

When the trie no longer fits in one machine’s memory it is split by prefix — the a–m sub-tries on one shard, n–z on another, for instance — and a request is routed to the shard owning its first letters. The catch is that prefixes are not evenly used: far more queries begin with common letters than rare ones, so a naive by-letter split overloads the popular shards. The fix is a shard-map manager that assigns prefix ranges to shards by observed load rather than alphabetically, splitting hot ranges across more machines and packing cold ones together, and replicating the hottest shards so several machines can answer the same popular prefixes in parallel.

Design Search Autocomplete

The suggestions that drop down as you type — built from zero. A trie (a tree keyed by letters) with the top few completions pre-computed and cached at every node, so a keystroke is answered by reading a list, not by searching; why a live database query per keystroke dies at ~20× the search rate; the offline pipeline that turns query logs into a fresh trie snapshot; the sub-100 ms serving path; sharding by prefix and the fix for the uneven letters; and the failure sweep whose quietest box is a trending query that stays invisible for a week.

System design · Systems. The source ↗

A free, interactive, animated visual explainer of Design Search Autocomplete — built to be understood, not skimmed.

Questions

How does search autocomplete work?: Completions are pre-computed offline and served from memory. Every finished search a user types is logged; a batch job aggregates those logs into query counts and builds a trie — a tree where each edge is a letter, so the path from the root spells a prefix. At every node the build stores the top few most-popular completions beneath it. At request time the service walks the prefix down the trie (one hop per letter) and returns the list already sitting at that node — so a keystroke is answered by reading a cached list, not by scanning the database. Facebook’s typeahead post gives the reason speed matters this much: "spending more than 100 msec to retrieve a result will cause the typeahead to ‘stutter,’ leading to a bad user experience that is almost impossible to compensate for with quality."
Why not just run a database LIKE query on every keystroke?: Because autocomplete fires a query on every keystroke, not once per search — so its request rate is roughly the number of keystrokes per search (often ~20) times the search rate. A service with millions of daily users doing tens of searches each lands in the tens of thousands of autocomplete queries per second, every one of which would be a prefix scan (WHERE query LIKE 'prefix%') that also has to rank the matches. A relational index can find the prefix range but still has to sort the matches by popularity per request, under a sub-100 ms budget, at that rate. The trie moves that sort offline: the ranking is done once at build time and cached at each node, turning per-keystroke work from a scan-and-sort into a single list read.
What is a trie with cached top-k?: A trie is a tree keyed by the characters of a string: the root is the empty prefix, and following an edge labelled with a letter extends the prefix by that letter, so every node corresponds to exactly one prefix. "Cached top-k" means that when the trie is built, each node also stores the k most-popular full queries that live in its subtree, already ranked. Answering a prefix is then two cheap steps: walk down the trie one node per letter to reach the prefix node, and return its stored list. Without the cache the service would have to walk the entire subtree under the prefix, collect every candidate, and sort them on each request — which for a common two-letter prefix can mean visiting dozens of nodes instead of two. Elasticsearch’s completion suggester makes the same trade explicitly: it "is optimized for speed" and "uses data structures that enable fast lookups, but are costly to build and are stored in-memory."
How does autocomplete stay fresh, and what does it miss?: The trie is rebuilt on a schedule — often daily or weekly — from the accumulated query logs, and the new snapshot is shipped to the serving machines to replace the old one. For the vast majority of queries this is honest: what people search for shifts slowly, so a week-old ranking is almost identical to today’s. The thing it misses is a sudden trend. A brand-new query that spikes today has no counts in last week’s logs, so it is absent from the current trie and cannot be suggested until the next build folds it in — which is why real systems bolt a separate, faster-moving trending path onto the slow batch trie rather than trying to make one pipeline do both.
How is an autocomplete trie sharded across machines?: When the trie no longer fits in one machine’s memory it is split by prefix — the a–m sub-tries on one shard, n–z on another, for instance — and a request is routed to the shard owning its first letters. The catch is that prefixes are not evenly used: far more queries begin with common letters than rare ones, so a naive by-letter split overloads the popular shards. The fix is a shard-map manager that assigns prefix ranges to shards by observed load rather than alphabetically, splitting hot ranges across more machines and packing cold ones together, and replicating the hottest shards so several machines can answer the same popular prefixes in parallel.

Design Search Autocomplete

Questions

Related explainers