Autocomplete & Query Suggestions

Overview

Autocomplete has a much tighter latency budget than search itself — it has to feel instant on every keystroke, not just on submit. It’s also a different data problem entirely: instead of “which documents match these terms,” it’s “of all past queries starting with this prefix, which are most popular right now.” Worth treating as its own subsystem rather than an afterthought bolted onto search.

API Design

GET /api/suggest?prefix=mach

// 200 OK
{
  "suggestions": [
    { "query": "machine learning", "volume": 128000 },
    { "query": "machine learning course", "volume": 41000 }
  ]
}

volume (not a relevance score) is the detail worth naming: this endpoint ranks by popularity among past queries, not by textual relevance to a document corpus — a completely different signal from GET /api/search, even though the two look similar from the outside.

Database Schema

Autocomplete doesn’t use a row-and-column schema — its structure is a trie (prefix tree), with each node caching its own top-K completions:

root
 └─ "m"
     └─ "ma"
         └─ "mac"
             └─ "mach" → top-K: ["machine learning" (128k), "machine learning course" (41k), ...]

query_log_stream   -- raw stream of submitted queries, consumed to update the trie

Caching the top-K directly at each prefix node is what makes a lookup O(1) relative to prefix depth, regardless of how many total queries share that prefix — the alternative (scanning all queries starting with “mach” on every request) wouldn’t meet the latency budget.

Basic Approach — Linear Scan Over a Static Query List

How it works

Keep a flat list of past queries with their counts. On a request, scan the list for entries starting with the given prefix and return the top few by count.

Prefix ──▶ Scan Query List ──▶ Filter by prefix ──▶ Sort by count ──▶ Top-K

Tradeoffs

• Pro: No specialized data structure needed — a list and a filter.
• Con: A linear scan on every keystroke is far too slow once the query list has more than a trivial number of entries.
• Con: Static — built once, never reflects what’s popular right now.

Scaled Approach — Trie Built From Query Logs, Offline Refresh

How it works

Build a trie from the historical query log: each character is an edge, each node represents a prefix, and each node precomputes and caches its own top-K most frequent completions. A prefix lookup is just a trie traversal to the matching node followed by returning its cached top-K — no scanning or sorting at request time. The trie is rebuilt on a periodic batch cadence (e.g., nightly) from the latest query logs.

Query Logs ──▶ Batch Job ──▶ Trie (each node caches its own top-K) ──▶ served by lookup

Tradeoffs

• Pro: Lookup latency depends only on prefix length, not on how many total queries share that prefix — comfortably fast enough for keystroke-level use.
• Pro: Precomputing top-K per node means no sorting work happens at request time at all.
• Con: Only as fresh as the last rebuild — a rapidly trending query (breaking news) won’t show up in suggestions until the next batch run.
• Con: The full trie has to fit in memory to serve at low latency, which becomes a real constraint as the query vocabulary grows.

Advanced Approach — Real-Time Updates and Sharded Serving

How it works

Two refinements on top of the batch-built trie:

• Streaming top-K updates: consume the query log stream continuously (the same shape as Twitter’s trending pipeline) and update affected trie nodes’ top-K incrementally as queries come in, instead of waiting for the next full rebuild — so a suddenly popular query shows up in suggestions within minutes.
• Sharding by prefix: once the trie is too large for one machine, split it across servers by top-level prefix (e.g., “a–m” on one shard set, “n–z” on another), so a lookup only ever needs to hit the shard owning that prefix range — no scatter-gather required, unlike search itself.

Query Stream ──▶ Windowed Counter (per prefix) ──▶ Update Trie Node Top-K (incremental)
Lookup ──▶ Route by prefix range ──▶ Owning Shard ──▶ Top-K

Tradeoffs

• Pro: Suggestions reflect real-time popularity instead of yesterday’s batch snapshot, which matters a lot for breaking-news-style query spikes.
• Pro: Prefix-range sharding avoids the scatter-gather cost search itself pays, since a prefix lookup is inherently routable to one shard.
• Con: Incremental updates need care to avoid the same always-popular terms dominating every top-K forever — real systems need time-decay (recent volume weighted more than historical volume) to actually surface what’s trending now.
• Con: Prefix-range sharding can be uneven — far more real queries start with common letters than rare ones, so shard load isn’t naturally balanced and may need finer-grained rebalancing than a simple alphabetic split.

Tech Choices

• Trie (prefix tree) — the standard structure for prefix-based lookup, with each node caching precomputed top-K completions.
• Redis — can back a simpler sorted-set-per-prefix implementation at smaller scale, or cache the hottest prefixes in front of the full trie.
• Streaming query log (Kafka) — feeds real-time top-K updates the same way it feeds trending topics elsewhere in a search or social system.
• Time-decayed counting — weights recent query volume over historical volume so suggestions reflect current popularity, not all-time popularity.

How to Vocalize This in an Interview

Lead with what makes this a different problem from search itself: ranking by popularity among past queries, not relevance to documents. Build up from a static trie to streaming updates only once “what if something goes viral right now” comes up, and if pressed on personalization (per-user history, geo-specific trends), name it explicitly as a real extension that changes the caching story — each user or region would need its own top-K — rather than pretending the base design already handles it.