Search Autocompletelesson 3 of 3 · 3 min read

The Offline Pipeline and Trending Queries

Built offline

Everything your serving tier reads gets built offline, and that pipeline is classic batch processing.

Stream query logs into storage as people search. Then periodically, daily is common, run a job that aggregates counts over a trailing window, weighting recent days higher so last year's fads decay away.

Let a filtering stage earn its keep next. Drop queries below a frequency floor, collapse near-duplicates and normalise case, and run the blocklist for offensive and legally sensitive suggestions.

Take that last one seriously, because it is the stage that generates actual news stories when it fails.

Feed the survivors to your builder, which computes every node's list and emits an immutable snapshot. Your serving machines pull it and swap.

The flaw in a daily batch

Face the flaw built into a daily batch: it is up to 24 hours behind reality. Most of the time nobody notices, because the top suggestions for an everyday word are identical every day.

Watch it fail during breaking news. An earthquake, a transfer rumour, a death, and the freshest queries are exactly the ones people want, and your batch has never heard of them.

Split the problem instead of making your big structure mutable. Run a streaming job counting queries over short windows, flagging terms whose rate spikes against their baseline.

Put those trending candidates into a small separate structure that rebuilds every few minutes, holding tens of thousands of entries rather than millions.

Read both at query time, merge them, and let a trending hit displace your weakest batch suggestion. Your heavyweight structure stays immutable and easy to reason about, and your volatile one stays small enough to rebuild constantly.

Add personalisation the same way if the product needs it. Recent searches from somebody's own history, merged in front of the global results.

Keep it a layer, whatever you do. Baking per-user data into the shared structure multiplies it by your user count. That is the fastest way to stop it fitting in memory.

the shape of it

step 1 of 3

A nightly batch build produces the main trie while a streaming path injects trending queries within minutes, and the service merges the two at request time.

Worked example

During the 2023 transfer window, a sports site's autocomplete becomes a running joke: the day Jude Bellingham signs with Real Madrid, typing 'bell' still suggests last season's queries, and the signing everyone is searching for surfaces 26 hours later when the nightly Spark job catches up. Engagement data backs the mockery: suggestion click-through on trending days drops from 34 percent to 19. Marta's team adds a streaming layer: search events flow through Kafka into a Flink job computing 10-minute windowed counts, and any query whose velocity jumps 20x over its 7-day baseline enters a trending set, rebuilt every 5 minutes and capped at 50,000 entries. The merge rule is one line: a trending match replaces the fifth-ranked batch suggestion. The next big signing shows up in suggestions 11 minutes after the news breaks.

Search Autocomplete: wrapping up

In the real world

01Google Suggest began as engineer Kevin Gibbs's 20 percent project in 2004 and became the default on google.com in 2008; Google has said autocomplete reduces typing by roughly 25 percent on average.
02Google Instant (2010) went further and rendered full results per keystroke, then was retired in 2017 partly because more than half of searches had moved to mobile, where per-keystroke result pages wasted work.
03Elasticsearch's completion suggester stores suggestions in an in-memory FST (finite state transducer), a deliberately constrained, prefix-optimized structure separate from the main inverted index, precisely for the latency budget autocomplete demands.
04Facebook's typeahead (described in its 2010 engineering post) layers data sources by cheapness: the browser cache and recent connections answer first, then aggregated global results merge in, an early production example of the layered-merge serving pattern.
05Google's autocomplete policy team maintains published rules for removing predictions (violence, hate, medical misinformation), and the filtering stage of the pipeline is where those policies are actually enforced.

Questions people ask

Why not query Elasticsearch or the database directly for each keystroke?

Budget. After network time, the server has roughly 10 ms, and autocomplete traffic runs at several times search QPS since it fires per keystroke. A general-purpose query engine can answer prefix queries, but not reliably in single-digit milliseconds at that rate. Purpose-built in-memory structures with precomputed answers turn each request into a pointer walk, which is why even Elasticsearch built a separate in-memory suggester rather than reusing its main index.

How do trending queries appear quickly if the trie rebuilds nightly?

Through a separate streaming path. A stream processor counts queries over minutes-long windows, detects velocity spikes against each term's baseline, and maintains a small trending set rebuilt every few minutes. The serving layer merges this set with the batch trie's results at request time, so the big structure stays immutable while fresh queries surface within minutes.

Where does typo tolerance fit into this design?

Not in the trie, which matches exact prefixes only. Practical systems get most of the value cheaply: the offline pipeline aggregates common misspellings from logs and can index them as alias entries pointing at the corrected suggestion. Full fuzzy matching per keystroke (edit-distance search over an FST) exists in engines like Elasticsearch but costs meaningful latency, so it is usually reserved for the final search, not every keystroke.

Quick review

Trie:: tree where each node is a character. Traverse to prefix node, then find top-k by frequency. O(p + output) time
Memory constraint:: storing all prefixes for 1B queries × avg 10 chars = 10 GB. Use compressed trie or limit depth
Top-k at each node:: precompute and cache top-5 results at each trie node. Avoids DFS on every query
Offline pipeline:: aggregate query logs (Hadoop/Spark) → count frequencies → filter/rank → rebuild trie → push to cache
Update frequency:: rebuild every 1 week (stable) or stream real-time trending queries via Kafka → incremental update
CDN + Redis:: cache popular prefix results (top 1000 prefixes) in Redis. CDN for public (non-personalized) suggestions
Personalization:: blend global popularity with user's own search history. Separate personalized layer on top

the trade-off

Trie mutation is slow. Rebuild offline. High memory for all prefixes. Limit to top N most frequent queries.

in the room

Tests trie design, precomputation vs real-time, offline pipelines, and caching hot paths.

the short version

A batch job builds the trie from logs; a streaming layer keeps it honest during breaking news.