Skip to content

Autocomplete Strategy

1. Decision

Choose Edge-Ngram Tokenization in Elasticsearch/OpenSearch for versatile, multi-word, typo-tolerant prefix search; choose Completion Suggester (FST) for ultra-low latency, in-memory, microsecond prefix completion at massive scale; choose Trie / Radix Tree in Redis for lightweight custom in-memory autocomplete.

2. 30-Second Answer

Autocomplete (Search-As-You-Type) provides instantaneous search suggestions as a user types each keystroke. The three primary engineering strategies are: 1. Edge-Ngram Tokenizer (Elasticsearch/OpenSearch): Splits words into prefix n-grams at index time ("phone" \(\rightarrow\) "p", "ph", "pho"). It utilizes standard inverted indexes, supporting multi-field filtering, sorting, and fuzzy typo matching, but increases index storage size. 2. Completion Suggester (FST) (Lucene / Elasticsearch): Builds an in-memory Finite State Transducer (FST) data structure. It executes sub-millisecond (\(<1\text{ms}\)) prefix lookups entirely in RAM, but cannot handle arbitrary middle-word matching or complex post-filtering. 3. Redis Trie / Sorted Set (ZSET): Stores prefix strings in Redis, leveraging ZRANGEBYLEX or custom Lua scripts for simple microsecond autocomplete.

3. Decision Matrix

Option Best For Avoid When Latency Scalability Consistency Operational Complexity
Edge-Ngram Analyzer (Search Engine) Multi-word autocomplete, fuzzy typo tolerance ("ifone" \(\rightarrow\) "iphone"), contextual category filtering (Brand/Category) Strict sub-millisecond memory requirements, systems with tight disk storage bounds Low (<10ms inverted index lookup) High (Distributed shards scale read traffic) Near Real-Time (NRT ~1s refresh interval) Medium
Completion Suggester (FST) Massive scale, single-phrase instant completion (Google search box style), strict microsecond SLAs Complex multi-field filtering, arbitrary middle-word substring matching, heavy fuzzy matching Ultra-Low (<1ms in-memory FST traversal) High (FST loaded directly into JVM RAM memory) Near Real-Time (NRT ~1s refresh) Medium
Redis Trie / ZSET (ZRANGEBYLEX) Simple, lightweight in-memory autocomplete, tag completion, low infrastructure footprint Advanced relevance scoring (BM25), multi-attribute category facets Sub-millisecond (<1ms in-memory lookup) Scales with Redis RAM memory Strong Low

4. Selection Rules

Requirement Best Choice Rationale / Example
Versatile Product Search Autocomplete + Typos Edge-Ngram Analyzer Handles partial prefix tokens, fuzzy typo matching, and category filtering in 1 query
Ultra-Low Latency Sub-Millisecond Search-As-You-Type Completion Suggester Traverses in-memory Finite State Transducer (FST) in sub-millisecond time
Lightweight App Tag / Username Completion Redis ZSET / Trie ZRANGEBYLEX fetches matching lexicographical prefixes directly from RAM
Search-As-You-Type Across Multiple Word Tokens Edge-Ngram (search_as_you_type) Elasticsearch search_as_you_type field type generates root n-grams automatically
Highlighting Matching Prefix Substrings Edge-Ngram + Highlighter Highlights matching typed prefix letters in bold (<b>pho</b>ne) in search UI

5. Tradeoffs

  1. Edge-Ngram Query Versatility vs Index Storage Inflation
  2. Gain (Edge-Ngram): Supports full boolean queries, category filters, and fuzzy typo matching.
  3. Lose (Edge-Ngram): Index size inflates by 3x–5x due to storing millions of prefix token variations.
  4. Completion Suggester Speed vs Query Flexibility
  5. Gain (FST): Microsecond memory speed; optimized specifically for high-throughput single-phrase completion.
  6. Lose (FST): FST must fit entirely in RAM; does not support arbitrary middle-word matching.
  7. Index-Time Processing vs Query-Time Computation
  8. Gain (Edge-Ngram): Pre-computes prefix tokens at index time so keystroke queries execute as fast simple term lookups.
  9. Lose (Edge-Ngram): Slower write indexing throughput.
  10. Redis Trie Simplicity vs Advanced Relevance Scoring
  11. Gain (Redis): Super simple, zero search engine cluster dependency.
  12. Lose (Redis): Lacks BM25 relevance scoring, document length normalization, and tokenizers.
  13. Fuzzy Typo Matching vs Prefix Match Precision
  14. Gain: Returns relevant results even when user misspells words on mobile keyboards.
  15. Lose: Excessive fuzziness (fuzziness: AUTO) produces noisy, irrelevant suggestions for short 1-2 letter prefixes.

6. Interview Counter Questions

  1. How does an Edge-Ngram Tokenizer split a string like "camera" (min_gram=1, max_gram=4)?
  2. How does a Finite State Transducer (FST) work in Lucene and why is it extremely memory efficient?
  3. What is the difference between ngram and edge_ngram in Elasticsearch?
  4. How do you implement Autocomplete using Redis ZSET and ZRANGEBYLEX?
  5. How does the search_as_you_type field type work in modern Elasticsearch 7.x+?
  6. How do you handle Fuzziness (typo tolerance) for 1-letter vs 3-letter vs 5-letter typed prefixes?
  7. Why shouldn't you run fuzzy queries on 1-letter or 2-letter typed prefixes?
  8. How do you prevent search-as-you-type keystroke queries from overloading backend servers (Debouncing & Throttling)?
  9. How do you rank autocomplete suggestions by popularity (Query Logs / Click-Through Rate)?
  10. How do you cache autocomplete suggestions at the API Gateway or Edge CDN layer?

7. Gold Standard Answers

  1. "camera" (min_gram=1, max_gram=4) \(\rightarrow\) ["c", "ca", "cam", "came"]. It indexes only prefix grams starting from the beginning of the word.
  2. An FST is a directed acyclic graph (DAG) that compresses common string prefixes AND suffixes into a compact byte array stored in RAM, acting as a deterministic finite state machine for sub-millisecond traversal.
  3. ngram creates matches from anywhere in the word ("camera" \(\rightarrow\) "am", "me", "er"). edge_ngram creates matches strictly anchored to the start of the word ("c", "ca", "cam").
  4. Insert strings into ZSET with score 0. ZRANGEBYLEX my_zset "[pho" "[pho\xff" LIMIT 0 10 retrieves 10 matching lexicographical prefix strings instantly from Redis RAM.
  5. search_as_you_type generates an internal set of sub-fields automatically: root field, 2-gram, 3-gram, and edge-ngram fields, optimizing multi-word search-as-you-type out-of-the-box.
  6. Use fuzziness: "AUTO:3,6". Length 0-2: 0 edits (exact prefix match only). Length 3-5: 1 edit allowed. Length 6+: 2 edits allowed.
  7. Running fuzzy matching on 1-2 letter prefixes creates massive FST/inverted index expansion, returning thousands of irrelevant matches and thrashing server CPU.
  8. Client side: Implement Debouncing (wait 150-300ms after last keystroke before sending HTTP request). Server side: Cache prefix responses at API Gateway / Redis.
  9. Multiply BM25 text relevance score by a popularity_score attribute (derived from historical query click-through logs updated asynchronously via Spark/Flink).
  10. Cache common 1-3 letter prefix responses in Redis or CDN Edge for 1 hour. Since top 3-letter prefixes account for 80% of keystroke queries, edge caching offloads backend search nodes.

8. Common Mistakes

  • Using standard ngram instead of edge_ngram, causing middle-word matches to pollute prefix search results.
  • Enabling fuzzy matching (fuzziness = 2) on 1-letter or 2-letter search inputs, destroying search performance.
  • Issuing an HTTP API search request on every single raw keystroke without client-side Debouncing (150-300ms).
  • Expecting Completion Suggester (FST) to support complex multi-field boolean filtering out-of-the-box.
  • Failing to index tie-breaker popularity scores, returning random or non-relevant autocomplete suggestions.

9. Keywords

Autocomplete, Search-As-You-Type, Edge-Ngram, Completion Suggester, FST (Finite State Transducer), Trie, Redis ZRANGEBYLEX, search_as_you_type, Debouncing, Fuzziness AUTO, Popularity Scoring, Prefix Matching.

10. Cheat Sheet

  • Edge-Ngram: Best overall choice. Generates prefix tokens ("c", "ca", "cam"). Supports fuzzy typos, category filters, & BM25 scoring.
  • Completion Suggester (FST): Best for ultra-low latency (<1ms) single-phrase completion. Loads compact FST graph directly in RAM.
  • Redis ZSET: Lightweight in-memory option using ZRANGEBYLEX "[prefix" "[prefix\xff".
  • Fuzziness Rule: Use fuzziness: "AUTO:3,6". ZERO fuzziness for 1-2 letter prefixes to prevent CPU thrashing.
  • Client Rule: Always implement Debouncing (150–300ms) on client UI text inputs to prevent keystroke flood spikes.
  • Edge Caching: Cache top 1–3 letter prefix autocomplete responses in Redis / CDN Edge to offload 80% of keystroke traffic.

11. Related Decisions