Design: Query Autocomplete

The Problem

Design a system that suggests 5 to 10 search query completions as a user types. Suggestions must appear within 100ms of each keystroke. The system handles 50,000 queries per second and must work across web and mobile clients.

High-Level Architecture

  User types: "how to m"
              │
              ▼
  ┌───────────────────────────────┐
  │ STEP 1: PREFIX MATCHING       │  (~2ms)
  │ Trie lookup or prefix index   │
  │ Output: ~100 candidate queries│
  └───────────────────────────────┘
              │
              ▼
  ┌───────────────────────────────┐
  │ STEP 2: RANKING               │  (~5ms)
  │ Score by popularity + recency │
  │ + personalization              │
  │ Output: Top 10 suggestions    │
  └───────────────────────────────┘
              │
              ▼
  ┌───────────────────────────────┐
  │ STEP 3: FILTERING             │  (~1ms)
  │ Remove offensive / harmful    │
  │ Apply diversity constraints   │
  │ Output: Final 5-8 suggestions │
  └───────────────────────────────┘

Step 1: Prefix Matching

Store a corpus of historical search queries in a data structure optimized for prefix lookup:

Option A: Trie (Prefix Tree)

• Store each historical query character by character.
• When user types "how to m", traverse the trie to the "m" node and collect all stored completions below it.
• Extremely fast for exact prefix matching.

Option B: Sorted Index with Binary Search

• Store all historical queries sorted alphabetically.
• Binary search to find the range of queries starting with the typed prefix.
• Simpler to implement and update than a trie.

Option C: Elasticsearch Completion Suggester

• Use a dedicated autocomplete index backed by finite state transducers.
• Handles fuzzy matching (typos) out of the box.

At scale, the query corpus might contain billions of unique queries. Keep only the top 10 million most frequent queries in the active index and refresh daily.

Step 2: Ranking

Once you have 100 candidate completions matching the prefix, rank them:

1. Global Popularity: How many times has this query been searched by all users in the last 30 days? Popular queries rank higher.
2. Recency / Trending: Queries trending in the last hour get a boost. This surfaces current events ("election results", "world cup score").
3. Personalization: If the user recently searched for "how to make pasta", suggest "how to make pasta sauce" higher than "how to make paper airplanes".
4. Query Quality: Longer, more specific queries are often more useful than very short generic ones.

A simple scoring formula:

$$\text{Score} = w_1 \cdot \log(\text{Frequency}) + w_2 \cdot \text{RecencyBoost} + w_3 \cdot \text{PersonalBoost}$$

Step 3: Filtering

Before returning suggestions to the user:

• Blocklist Check: Remove suggestions matching offensive or harmful query patterns.
• Deduplication: Remove near-duplicate suggestions ("how to make bread" and "how to make a bread").
• Diversity: Ensure suggestions cover different intents (do not show 5 variations of the same query).

Data Pipeline

Continuously update the suggestion corpus:

1. Log all completed searches (queries that users actually executed, not abandoned).
2. Aggregate query frequencies daily using a batch pipeline (Spark).
3. Compute trending queries using a streaming pipeline (Flink) that detects sudden frequency spikes.
4. Rebuild the prefix index periodically with updated frequency counts.

Say this out loud

Query autocomplete matches typed prefixes against a corpus of historical queries stored in a trie or sorted index. Candidate completions are ranked by popularity, recency, and personalization. Results are filtered for offensive content and deduplicated before displaying 5 to 8 suggestions within 100ms of each keystroke.

Followups to expect

1. How do you handle typos in partial queries? Use fuzzy matching (edit distance 1 to 2) during prefix lookup, or correct the prefix using a spelling correction model before trie traversal.
2. How do you prevent autocomplete from amplifying misinformation? Suppress suggestions related to unverified claims, conspiracy theories, or content flagged by fact-checkers using a content policy blocklist.