Autocomplete / Typeahead
Showing top suggestions as soon as the user types 2-3 letters, within 100 ms on every keystroke.
21.1 Why is it used?
- The user does not have to type everything, search is faster, and spelling mistakes are fewer.
- Showing popular and trending queries first raises conversion (for example 'iphone 16' during a sale).
- A request goes out on every keystroke, so traffic is many times the main search traffic - the system must be very fast and cheap.
- Personalization: suggestions based on the user's past searches and location.
21.2 How it works
- Trie (prefix tree): each node is a character, the path is the prefix; pre-store the top-K popular completions at each node so the lookup is O(prefix length).
- Redis sorted sets (ZSET): one ZSET per prefix holding queries with a score (frequency); ZREVRANGE gives the top 10, ZINCRBY raises the count.
- Redis ZRANGEBYLEX: all terms in a single sorted set at score 0, with a lexicographic range for prefix matching.
- Elasticsearch completion suggester: fast prefix suggestions based on an in-memory FST; search_as_you_type / edge n-gram fields are also options.
- Data pipeline: search logs to Kafka -> a batch/stream job counts each query's frequency -> trie/ZSET rebuild (every hour/day).
- Client side optimizations: debounce (wait ~100-300 ms), send a request only after 2-3 characters, browser/CDN caching of popular prefixes.
- Ranking: frequency + recency (trending) + personalization; filtering offensive/blocked terms is essential.
- Fuzzy/typo tolerance: suggesting 'samsung' even for 'samsng' using edit distance.
- 1.User: types 'bir' (Swiggy app, 200 ms debounce)
- 2.CDN / edge cache: popular prefix cached city-wise; hit = instant answer
- 3.Suggest service: runs on a cache miss
- 4.Redis ZSET: ZREVRANGE suggest:blr:bir 0 9
- 5.Blocked words: filter offensive terms
- 6.Re-rank: the user ordered Hyderabadi biryani before, so it goes first
- 7.Suggestions ~30-50 ms: 1. hyderabadi biryani 2. biryani 3. birthday cake 4. biryani rice
- 1.Trie: root -> b -> bi -> bir
- 2.top-K @ 'bir': biryani, birthday cake, biryani rice
- 3.top-K @ 'bu': burger, butter naan
- 4.Redis ZSET key suggest:blr:bir: biryani 9820, birthday cake 4310, biryani rice 1250
- 5.ZINCRBY suggest:blr:bir 1 biryani: count +1
- 1.Search events: what the user searched
- 2.Kafka: search-logs topic
- 3.Flink job: counts every 5 min
- 4.ZINCRBY: updates Redis ZSETs
- 5.Nightly batch: trims to top-N
Mistake: calling on every keystroke without debounce -> 5-10x useless load on the backend. Mistake: LIKE 'bir%' on the main DB -> slow at scale; use a trie / ZSET / ES suggester
21.3 Tools you can use
| Tool | Type | How it is used |
|---|---|---|
| Redis (Sorted Sets) | In-memory data store | Prefix -> ZSET of top queries with score; sub-ms reads, live popularity update with ZINCRBY. |
| Elasticsearch / OpenSearch Completion Suggester | Search engine feature | completion field type, fast prefix suggestions through an FST; with fuzzy and context (category) filters. |
| Custom in-memory Trie service | Self-built service (Java/Go) | Top-K cached trie in memory, rebuilt by an offline job, sharded by prefix; at big scale like Google/LinkedIn. |
| Algolia | SaaS search | Query Suggestions and instant search out of the box, typo tolerance built in. |
| Kafka + Spark/Flink | Data pipeline | Computing query frequency from search logs to refresh the suggestion data. |
21.4 Comparison: Trie vs Redis Sorted Sets vs Elasticsearch Completion Suggester
| Point | Custom Trie | Redis Sorted Sets | ES Completion Suggester |
|---|---|---|---|
| Speed | Fastest, in-process memory | Sub-ms, with a network hop | Few ms, fast |
| Build effort | High, own code + sharding | Medium, simple commands | Low, mapping + data index |
| Live updates | Hard, mostly periodic rebuild | Easy, real-time with ZINCRBY | Reindex/update the document |
| Fuzzy / typo | You must implement it yourself | No (your own logic) | Built-in fuzzy option |
| Memory | Can be optimized (top-K per node) | A ZSET per prefix, more memory | FST is compact, kept in heap |
| Scaling | Prefix-based sharding by yourself | Redis Cluster | Shards + replicas |
| Best for | Google-scale, ultra-low latency | Trending queries, simple setup | Catalog/product name suggestions |
21.5 When to choose which
- Redis ZSET: you want to build quickly and need live updates of trending/popular queries.
- ES completion suggester: you already have Elasticsearch and want to suggest product names/brands with fuzzy.
- Custom Trie: very large scale and strict latency (<10 ms), with a dedicated team.
- Algolia: you want a managed solution with no infra.
- Always add client debounce + CDN/browser caching, whatever the backend is.
21.6 Real-world example
Real world: Swiggy/Zomato dish search typeahead (a hypothetical scenario)
- The user types 'bir'; after a 200 ms debounce the app sends /suggest?q=bir.
- The request checks the CDN/edge cache - the result for a popular prefix like 'bir' is cached city-wise.
- On a cache miss the suggest service runs ZREVRANGE suggest:blr:bir 0 9 in Redis - 'biryani', 'birthday cake' and so on.
- Results are re-ranked by the personalization layer: the user ordered Hyderabadi biryani earlier, so it goes up.
- The response comes in ~30-50 ms; the user selects 'biryani' and the full search runs.
- Every search event goes to Kafka; a Flink job updates query counts every 5 minutes (ZINCRBY).
- At night a batch job removes old, less popular entries and trims the ZSET size to top-N.
21.7 Interview tips
- Common mistake: sending a request on every keystroke without debounce - 5-10x useless load on the backend.
- Common mistake: running LIKE 'bir%' on the main search DB - slow at scale. Not filtering offensive/blocked words is also wrong - it can damage the brand's image.
- Interview tip: be sure to mention precomputed top-K at each trie node and the offline rebuild pipeline.
- Numbers worth quoting: target latency < 100 ms per keystroke, debounce 100-300 ms, trie lookup O(prefix length).