Typeahead: The Only Feature Whose Deadline Is Set by the User's Hands

Almost every system in this series is allowed to be slow occasionally. A payment can take 600 milliseconds. A feed can take 300. Nobody has ever cancelled a subscription because a search results page took half a second.

Typeahead is the exception, and the reason is not that users are more impatient about it. It is that the deadline is set by something you do not control: the interval between two keystrokes. A suggestion that arrives after the user has typed the next character is not slow, it is wrong — it is answering a query that no longer exists. That single constraint determines the entire architecture, and it is why typeahead is usually built as a completely separate system from the search it feeds into.

The budget, and who spends it

A reasonably fast typist leaves about 150 milliseconds between characters. That is the whole budget: network there, index lookup, ranking, network back, render. Set the index to a single region serving the world and the round trip alone eats it, before the server has done anything at all.

The first thing this kills is the instinct to reach for your existing search cluster. A full-text query that takes 90 milliseconds is a perfectly good search query and a hopeless typeahead query, because it leaves nothing for the network. Typeahead is not “search, but faster”. It is a different data structure with a different job.

The second thing it kills is the belief that debouncing is a performance fix. Set the debounce to 150 milliseconds and watch the bar: the total goes up, because a debounce is pure added delay. What it actually buys is fewer requests — a user typing a ten-character query fires ten requests without it and perhaps three with it, which is a 70% reduction in load and an increase in latency for every request you do send. It is a cost control, not a speed-up, and it is worth doing for that reason alone. Sixty milliseconds is about right; past a hundred the interface starts to feel hesitant.

Two more client-side pieces are not optional. Cancel in-flight requests when a new keystroke arrives, or the responses will arrive out of order and the list will flicker between answers to different prefixes — and if you cannot cancel, stamp each request with its prefix and drop any response that does not match the current input. And cache locally: users backspace constantly, and the answer for hote is one they already had a moment ago.

Precompute the answer, not the search

Now the server side, which has one idea in it.

The obvious structure is a trie: every query in your log is a path from the root, and the completions for a prefix are the leaves below that prefix’s node. Type a long prefix and this is genuinely cheap. Now delete characters back down to one or two and watch the node count, because that is the shape of the problem — a short prefix subtends most of the corpus, and short prefixes are what every user types first, on every session. The naive implementation is slowest exactly where the traffic is.

The fix is to stop doing the work at query time. Store the top ten completions at every node, precomputed. A lookup becomes: walk down as many characters as the user typed, read the list, return it. No ranking, no traversal, no dependence on how much sits below.

The costs are honest and both are real. Memory goes up by roughly ten entries per node, and for a real query log that is a large multiple of the raw data — which is fine, because the whole structure is small enough to hold in RAM on every server, and holding it in RAM is what makes the 2-millisecond lookup possible. And the lists are now stale by construction: they reflect the popularity snapshot from whenever they were last built.

That staleness is usually the right trade. Rebuild the whole structure offline from the last N days of query logs, ship it as an immutable artifact, and have servers load it atomically — old structure serving until the new one is ready, then a pointer swap. Suggestions that are a few hours behind are not a bug for the long tail. They are a bug for a breaking news term that did not exist this morning, which is why real systems run a small, separate, fast-moving layer for trending terms and merge it in at query time.

Where the suggestions come from

The structure above assumes a query log. On day one you do not have one, and the cold start is the part that gets hand-waved.

The bootstrap sources, roughly in order of how well they work: your catalogue itself (product names, article titles — real strings users might plausibly type), your search logs if you have search but not typeahead yet, and category or tag names. What you should not do is seed from an external corpus of general web queries, because your users’ vocabulary is not the internet’s and the mismatch is immediately visible.

Once traffic exists, the log needs cleaning before it becomes an index, and every step here exists because of something that went wrong for somebody. Normalise: lowercase, collapse whitespace, strip punctuation that carries no meaning — otherwise iPhone 16 and iphone 16 are two entries competing for the same slot. Count distinct users, not queries, or a single script running one search ten thousand times becomes your top suggestion. Weight by recency, because a query log with no decay is a monument to what was popular two years ago; an exponential decay with a half-life of a couple of weeks is a reasonable default. And weight by outcome, not just frequency where you can — a query that people type and then abandon is a query that did not work, and promoting it teaches more people to fail the same way.

The last one is worth stating plainly because it is the difference between a suggestion list and a good one: the best signal is not what people searched for, it is what people searched for and then clicked on.

The parts nobody mentions

Typos are most of your traffic. A user typing restauarnt gets zero completions from a strict prefix match, and this is not rare. The usual answer is not fuzzy matching at query time — too slow — but generating common misspellings offline and adding them as extra paths pointing at the correct term. Edit distance one covers the overwhelming majority.

Personalisation breaks the precomputation. The moment suggestions depend on who is asking, you cannot store one list per node. The workable version is to keep the global list precomputed and re-rank the ten results against a small per-user signal — recent searches, mostly — in the client or in a cheap final step. Fetch ten, show five, reorder using something you already have locally.

The index is not the search index and should not try to be. Typeahead answers “what do people type”, search answers “what documents exist”. They are built from different sources, updated on different schedules, and the attempt to unify them is the most common way this project goes wrong.

Suggestions are a data leak. They are built from user queries, which means an unfiltered index will happily complete a prefix with someone’s email address, an internal project name, or a private document title. You need a frequency floor — a query typed by fewer than N distinct users never enters the index — plus an explicit blocklist. This is not a nice-to-have; it is the failure mode that ends up in a news article.

Empty state is a product decision. What the box shows before a character is typed is free real estate that costs nothing to serve: recent searches, popular queries, or nothing at all. Deciding it is cheaper than defaulting to a blank dropdown.

The short version

The deadline is the next keystroke, roughly 150 milliseconds, and the network takes a large share of it before your code runs. That is why typeahead is a separate system from search rather than a faster mode of it, and why moving the index closer to the user beats almost any optimisation of the lookup.

Precompute the top ten at every trie node. The naive subtree walk is cheapest for long prefixes and most expensive for the one- and two-character prefixes that constitute nearly all of your traffic, so query-time ranking is slowest exactly where it is used most. Pay memory, rebuild offline, swap the structure atomically, and accept that popularity data is a few hours stale — then bolt a small trending layer on the side for the terms where that matters.

On the client: debounce around sixty milliseconds knowing it is a load control rather than a speed-up, cancel or discard responses that no longer match the current input, and cache locally because people backspace. And put a frequency floor on the index before launch, not after someone’s email address autocompletes for a stranger.