Typeahead & autocomplete

An online bookstore wants suggestions under its search box. To make the numbers real, give it a real catalog: the 60,435 distinct English titles in Project Gutenberg's public catalog. A reader typing "pride and prejudice" presses 19 keys, and each one changes the query: p, pr, pri, prid, and so on. A box that asks the server on every key sends up to 19 queries for one search.

Each of those answers has a tight deadline. About 0.1 second is the limit for a response to feel instantaneous, and 1 second the limit before the user's flow of thought is interrupted. When Facebook rebuilt its search box to show results while typing, more than 100 ms to retrieve a result made the typeahead stutter. That budget covers the network round trip, the lookup, the ranking and drawing the list.

A general-purpose search query doesn't fit in it reliably, so typeahead is built differently:

• Match prefixes, with an index designed for them.
• Precompute the best answers for the prefixes people type most.
• Cache answers in the browser and at the edge, so most keystrokes never reach a server.
• Discard stale answers, so a slow response for "pri" never overwrites the answer for "prim".

The simplest rule completes the whole title from its first character. In the Gutenberg catalog that rule hits a wall at once: 20,482 of the 60,435 titles, 34%, start with "the ". A reader who types "the" gets a third of the store, and one who types "prejudice" gets nothing, because no title starts with it.

So typeahead usually matches prefixes of each word. Elasticsearch shows the two common designs side by side:

The completion suggester can still match mid-title words: index several inputs per book, such as the full title and the title without a leading "The". The suggester is for guiding users to results as they type, not for spell correction. Its fuzzy option tolerates a typo or two in the prefix, which matters on phones.

An edge n-gram is a prefix of a word stored as its own term: "prejudice" is indexed as p, pr, pre, prej and so on, so a lookup for "prej" is an exact match on a term (Search & inverted indexes). It trades index size for query speed, the usual bargain in typeahead.

A trie stores strings by their characters, one level per character, so all strings with the same prefix share a path. Finding the completions of "pri" means walking three levels and collecting what lies below. The walk is fast; collecting and ranking everything below a short prefix is not, because a one-letter prefix has thousands of completions.

The shape of real prefixes points to the fix. Counting the distinct prefixes of the Gutenberg titles at each length:

Few short prefixes, each matching many titles; many long prefixes, each matching few. For the median title, 3,128 titles share its first character, 170 its first three, and only 6 its first eight:

So the expensive answers are exactly the ones worth storing. Keep the best few completions, say 10, at each trie node for the first several characters, computed offline, and a lookup becomes one walk and one read. Longer prefixes match so few titles that ranking them on the fly is cheap. Short prefixes are also the most repeated across users, which makes their answers ideal for caching.

Ten slots, thousands of candidates: ranking decides what the reader sees. Google's predictions reflect real searches: its systems look for common queries that match what was typed, and also consider the query's language and location, trending interest, and the searcher's past searches, so breaking news can appear quickly. For the bookstore, the inputs might be:

• Popularity: how often each title was searched for and bought, recomputed daily.
• Freshness: recent rises, so a book in the news climbs within hours (Count-Min Sketch & top-K).
• Personal context: the reader's own recent searches and purchases.

Personal signals can't be precomputed for every user and prefix. Facebook's typeahead handled this by splitting the work across several search services queried in parallel, one of them a global service whose results had no personalization at all. An aggregator merged and ranked their results. It also returned only ids; the web tier then fetched names and pictures and checked that the searcher was allowed to see each result.

The bookstore follows the same split. Global suggestions for a prefix are the same for everyone, so they are precomputed and cached. The reader's own history is small enough to rank per request, or to send to the browser in advance.

The fastest query is the one not sent. Facebook's typeahead loaded each user's friends, pages, groups and events into the browser as soon as the search box got focus, so those results appeared with no further request; only when the local results weren't enough did the browser ask the server, and it cached those answers too. Three client habits cut traffic further:

• Prefetch likely data when the box gets focus.
• Cache by prefix in the browser: the answer for "pri" can be filtered locally for "prim" when it held every match.
• Wait briefly after a keystroke before sending, so a fast typist's intermediate prefixes are skipped.

Responses can also arrive out of order. A reader looking for a primer types "pri", then "prim". The request for "pri" may hit a slow server and return after the one for "prim":

The fix is two lines of discipline. Each response carries the query it answers, and the client shows it only if that still matches the box. Older requests are canceled when a new one starts, which browsers support with AbortController, so the server and network stop spending time on answers nobody will see.

On the server side, the path for a global suggestion has layers, each answering the commonest prefixes before the next is asked:

Building is the slow part, which is why it happens offline. The completion suggester's structures are costly to build; a daily batch job (Batch processing) counts searches and sales per title, recomputes the top completions per prefix, and ships a new index that servers swap in atomically. New titles that must appear sooner, such as a book launched today, go into a small, separately updated index that is merged at query time.

The index for 60,435 titles fits easily in memory: at 36.6 characters on average, the titles are about 2.2 MB of text, so every server can hold a full copy and any of them can answer any prefix: no sharding, no fan-out, and copies added for throughput (Scalability). A catalog of hundreds of millions of items would need to be sharded, and then the merge step is where the latency budget goes.

A suggestion is the product speaking, not the user. Google's autocomplete tries to prevent predictions that are violent, sexually explicit, hateful, disparaging or dangerous, and when one slips through, removes that prediction and closely related variations. Blocking a prediction doesn't stop anyone typing the full query.

For a bookstore built from search logs, two risks follow. Popular searches can include offensive phrases, so suggestions pass through a block list before they are published. And search logs contain what individual readers typed, so a phrase searched by a single person must never become a suggestion others see: suggestions come only from queries made by many different readers, or from the catalog itself.