Search suggestion (autocomplete) returns candidate completions for a partial query in under 100ms. The system must handle millions of prefix queries per second, rank results by relevance or popularity, and update suggestions as new content is indexed. Three architectures cover the design space: a trie in Redis for exact-prefix matching, Elasticsearch’s completion suggester for full-text matching with fuzzy support, and a precomputed prefix table for simple but scalable implementations.
Core Data Model (Prefix Table Approach)
-- Precompute all prefixes for each suggestion at index time
CREATE TABLE SearchSuggestion (
prefix VARCHAR(100) NOT NULL,
suggestion VARCHAR(255) NOT NULL,
score INT NOT NULL DEFAULT 0, -- query frequency, popularity
category VARCHAR(50), -- 'product', 'user', 'location'
entity_id BIGINT, -- reference to the actual entity
PRIMARY KEY (prefix, suggestion)
);
CREATE INDEX idx_suggestion_prefix_score ON SearchSuggestion(prefix, score DESC);
-- Populate: for "apple iphone", insert rows for:
-- prefix="a" -> "apple iphone"
-- prefix="ap" -> "apple iphone"
-- prefix="app" -> "apple iphone"
-- ... up to the full query or max prefix length
-- Example population function:
def index_suggestion(text: str, score: int, category: str, entity_id: int):
words = text.lower().split()
prefixes = set()
for i, word in enumerate(words):
# Generate prefixes starting at each word position
prefix = ""
for char in (" ".join(words[i:])):
prefix += char
if len(prefix) >= 2: # minimum prefix length
prefixes.add(prefix)
for prefix in prefixes:
db.execute("""
INSERT INTO SearchSuggestion (prefix, suggestion, score, category, entity_id)
VALUES (%s, %s, %s, %s, %s)
ON CONFLICT (prefix, suggestion) DO UPDATE
SET score = EXCLUDED.score
""", [prefix, text, score, category, entity_id])Redis Sorted Set Approach (Production Standard)
def index_suggestion_redis(text: str, score: int):
"""Store all prefixes in Redis sorted sets, scored by popularity."""
text_lower = text.lower()
pipe = redis.pipeline()
prefix = ""
for char in text_lower:
prefix += char
if len(prefix) >= 2:
# Sorted set key per prefix, score = popularity
pipe.zadd(f"suggest:{prefix}", {text_lower: score})
# Cap each prefix set at 20 entries to bound memory
pipe.zremrangebyrank(f"suggest:{prefix}", 0, -21)
pipe.expire(f"suggest:{prefix}", 86400) # 24h TTL
pipe.execute()
def get_suggestions(prefix: str, limit: int = 8) -> list[str]:
key = f"suggest:{prefix.lower()}"
# ZREVRANGE: highest score first
results = redis.zrevrange(key, 0, limit - 1)
return [r.decode() for r in results]
# Memory estimate:
# 1M unique suggestions, avg 20 chars, avg 10 prefixes each
# = 10M sorted set members at ~50 bytes each = 500MB Redis
# Acceptable for a dedicated suggestion Redis instanceElasticsearch Completion Suggester
# Best for full-text search with fuzzy matching and multi-word suggestions
# Index mapping:
PUT /products
{
"mappings": {
"properties": {
"suggest": {
"type": "completion",
"analyzer": "simple",
"preserve_separators": true,
"preserve_position_increments": true,
"max_input_length": 50
},
"popularity": {"type": "integer"}
}
}
}
# Index a document:
POST /products/_doc/1
{
"name": "Apple iPhone 15",
"suggest": {
"input": ["apple iphone 15", "iphone 15", "iphone"],
"weight": 9850 # popularity score
}
}
# Query for suggestions (Python):
def es_suggest(prefix: str) -> list[str]:
result = es.search(index='products', body={
"suggest": {
"product_suggest": {
"prefix": prefix,
"completion": {
"field": "suggest",
"size": 8,
"fuzzy": {"fuzziness": 1} # tolerate 1 typo
}
}
}
})
options = result['suggest']['product_suggest'][0]['options']
return [o['text'] for o in options]Updating Scores from Search Analytics
def update_suggestion_scores():
"""Nightly job: recompute scores from last 7 days of search events."""
popular = db.fetchall("""
SELECT query, COUNT(*) as freq
FROM SearchEvent
WHERE occurred_at > NOW() - INTERVAL '7 days'
AND result_count > 0 -- only queries that returned results
GROUP BY query
ORDER BY freq DESC
LIMIT 100000
""")
pipe = redis.pipeline()
for row in popular:
query = row['query'].lower().strip()
score = row['freq']
prefix = ""
for char in query:
prefix += char
if len(prefix) >= 2:
pipe.zadd(f"suggest:{prefix}", {query: score}, xx=False)
pipe.zremrangebyrank(f"suggest:{prefix}", 0, -21)
pipe.execute()Key Interview Points
- Response time target is <50ms — Redis sorted sets deliver ~1ms; database prefix queries (LIKE ‘prefix%’) with a B-tree index deliver ~10-20ms for small tables, unacceptable at scale.
- Cap the number of candidates per prefix (top 20 by score) — unbounded sorted sets waste memory and slow down ZREVRANGE as the set grows.
- Dedup at query time: if a user types “ap”, the suggestions for “app” and “apple” both share the “ap” prefix set — no deduplication needed since they’re stored as distinct entries in the sorted set.
- Personalization: blend global popularity scores with per-user search history. Store user-specific boosts separately and merge at query time: final_score = 0.7 * global_score + 0.3 * personal_score.
- Cold start: populate suggestions from product/content catalog at launch, scored by number of views or purchases, before any user search data exists.
- Minimum prefix length of 2 characters prevents explosion of single-character prefix sets (every word shares the same one-character prefix).
Search autocomplete and suggestion system design is discussed in Google system design interview questions.
Search suggestion and product autocomplete design is covered in Amazon system design interview preparation.
Search suggestion and people search autocomplete design is discussed in LinkedIn system design interview guide.