The difficult part of search isn't finding a word. It's returning the right results quickly while documents change, users type, and parts of the search infrastructure fail.
Imagine an e-commerce catalog with millions of products. A user types iph, sees suggestions, completes iphone case, applies a price filter, and expects relevant results almost immediately.
A database query can support this at small scale. At larger scale, the system must solve several distinct problems: text retrieval, suggestion generation, ranking, freshness, filtering, and distributed execution. Treating all of them as one database lookup makes the design harder to reason about.
This article develops a search and autocomplete system from requirements through production failure modes. The example is a product catalog, but the underlying techniques also apply to document search, content discovery, and entity search.
1. Requirements: What Are We Actually Building?
Functional requirements
- Search products by keywords across titles, descriptions, and selected attributes.
- Show autocomplete suggestions as users type.
- Rank results by relevance, with optional popularity and recency signals.
- Support filters (brand, category, price, availability) and facets (counts by brand or category).
- Handle pagination and, where useful, typo tolerance.
- Reflect product additions, edits, and deletions within an agreed freshness window.
Suggestions can be query completions (iphone 15 case), entity suggestions (a particular product), or a mixture. This decision affects indexing and ranking; a trie of words is not automatically a complete autocomplete product.
Non-functional requirements
For discussion, assume:
| Dimension | Illustrative target or assumption |
|---|---|
| Catalog | 10 million searchable products |
| Full search | 2,000 requests/second at peak |
| Autocomplete | 10,000 requests/second at peak |
| Full-search latency | P99 below 200 ms |
| Autocomplete latency | P99 below 100 ms |
| Index freshness | Most updates visible within several seconds |
| Availability | Continue serving when individual nodes fail, subject to product correctness rules |
These are design assumptions, not universal search-industry benchmarks. The actual requirements depend on corpus size, languages, query mix, hardware, and product expectations.
A crucial distinction: search correctness, ranking quality, freshness, and availability are different properties. A query can return valid matches in the wrong order; an index can be available but stale; a partial result can be fast but incomplete.
2. Why Not Just Use SQL LIKE?
The simplest implementation queries the transactional database directly:
SELECT id, title
FROM products
WHERE LOWER(title) LIKE '%iphone%'
LIMIT 10;
A leading-wildcard pattern such as %iphone% generally cannot use a conventional B-tree index as an efficient prefix range lookup. On a large table, it may require expensive scanning.
But the correct conclusion is not that relational databases cannot do full-text search. PostgreSQL, for example, supports full-text indexes and trigram-based approaches. Database-native search may be the right choice for a smaller catalog or modest query volume.
A dedicated search engine becomes attractive when we need several capabilities together: inverted indexes, language-aware analysis, flexible ranking, fuzzy matching, faceting, and independent scaling of read-heavy search traffic. The trade-off is another data system and an eventually consistent copy of source data.
Design decision: keep the transactional database authoritative and maintain a separate, query-optimized search index for this example.
For a deeper comparison, see Database vs Dedicated Search Index.
3. High-Level Search & Autocomplete Architecture
WRITE / INDEXING PATH
Product Service
|
v
Source Database (source of truth)
|
v
CDC / Reliable Change Events
|
v
Durable Stream / Queue
|
v
Indexing Workers ----> Transform + Analyze + Version Check
| |
+------------------------------+
| |
v v
Full-Text Search Index Autocomplete Suggestion Index
(inverted index) (prefix / n-gram / precomputed)
READ / QUERY PATH
Browser / App
|
v
Search API / Gateway
|
+---- /suggest ---> Suggestion Cache ---> Suggestion Service
| |
| v
| Prefix Candidates
| |
| Suggestion Ranking
|
+---- /search ----> Result Cache ----> Search Coordinator
|
+-----------+-----------+
| | |
Shard A Shard B Shard C
| | |
+-----------+-----------+
|
Merge / Rank Top-K
|
Search Results
The diagram separates indexing from serving. The search engine does not need to query the source database for every request. That separation protects transactional workloads and allows search capacity to scale independently.
The diagram also shows a dedicated suggestion index. This is a choice for our assumed low-latency, high-autocomplete-QPS workload, not a requirement for every implementation. A unified search engine with prefix queries can be simpler and entirely sufficient.
4. How an Inverted Index Works
A full-text search engine typically uses an inverted index, mapping terms to the documents containing them.
Suppose the catalog contains:
D1: "Wireless iPhone case"
D2: "iPhone fast charger"
D3: "Wireless charging pad"
After suitable text analysis, a simplified index is:
"iphone" -> [D1, D2]
"wireless" -> [D1, D3]
"case" -> [D1]
"charger" -> [D2]
"charging" -> [D3]
A query for wireless iphone can retrieve candidate documents by intersecting or combining the posting lists, depending on AND/OR query semantics. The search engine then scores the candidates.
Real posting lists may also store term frequencies and positions. Positions allow phrase queries to distinguish wireless iphone case from the same words appearing far apart.
Term lookup can be fast, but processing the posting list is not constant-time regardless of corpus size. A common term can appear in millions of documents. Compression, skip structures, and top-k pruning help control that cost.
Text analysis must be compatible
Indexing and querying must use compatible analyzers:
Raw text -> Tokenize -> Normalize -> Optional stemming/synonyms -> Terms
- Normalization: case folding and, when appropriate, accent handling.
- Tokenization: splitting text into meaningful units; language-dependent.
- Stemming/lemmatization: optional normalization of related word forms.
-
Synonyms: domain-specific mappings such as
tvandtelevision. - Field-specific behavior: product titles may be analyzed; SKUs and IDs usually require exact matching.
Applying aggressive stemming to an SKU or brand field can reduce correctness rather than improve it. Likewise, changing an analyzer can require reindexing existing documents, because the stored terms were generated under the previous rules.
For the internals, see Search & Autocomplete — Architecture Deep Dive.
5. Autocomplete System Design: Generating Suggestions
Autocomplete is a different workload from full search. A user may issue several suggestion requests before submitting one search, and the usefulness of a response drops quickly as they type the next character.
The serving pipeline is:
Typed prefix -> Candidate generation -> Suggestion ranking -> Top suggestions
There are several legitimate candidate-generation approaches.
| Approach | Strength | Main trade-off |
|---|---|---|
| Search-engine prefix query | Reuses existing search infrastructure | Shares resources with full search; performance depends on engine and load |
| Edge n-grams | Prefixes are indexed as terms for fast lookup | More index storage and write amplification |
| Trie / FST-like structure | Purpose-built prefix traversal; can precompute top suggestions | Additional update, memory, and operational complexity |
| Precomputed query-log suggestions | Efficient for frequently searched queries | Requires freshness, spam filtering, and safe handling of query logs |
Trie example
For the terms car, card, and care, a conceptual trie looks like:
(root)
|
c
|
a
|
r ("car")
/ \
d e
("card") ("care")
Looking up car finds the node for that prefix. Retrieving the best suggestions can still require traversing many descendants unless the structure maintains precomputed top-k suggestions at nodes. Prefix lookup and ranking are separate operations.
Edge n-grams example
For iphone, index prefixes such as:
ip, iph, ipho, iphon, iphone
Then a query for iph can match the corresponding prefix term. In practice, minimum and maximum prefix lengths should be configured deliberately: indexing every single-character prefix may be wasteful, and very short prefixes often produce noisy suggestions.
Ranking suggestions
Prefix matching only produces candidates. Suggestions can then be ordered by:
- Historical search or selection frequency.
- Recent trending activity.
- Locale, language, and category context.
- Optional personalization.
- Safety, policy, and abuse controls.
Never treat raw query-log popularity as automatically trustworthy. Bots, spam, inappropriate queries, and old trends can distort the list. Query logs may also contain sensitive user input, so aggregation and retention need appropriate privacy controls.
For this example, a dedicated suggestion index helps isolate autocomplete latency from expensive full-text searches. It remains a workload-driven decision, not a universally superior architecture.
6. Preventing Autocomplete Request Storms
Without client-side controls, a user typing iphone could issue six requests in quick succession. Across many active users, this is a meaningful traffic multiplier.
Use a combination of:
- Debouncing: wait a short, tuned interval after typing before requesting suggestions.
- Minimum prefix length: avoid expensive, low-value one-character requests where the product allows it.
-
Cancellation or stale-response suppression: prevent a slow response for
ipfrom replacing newer results foriphone. - Server-side rate limits: protect shared resources from abusive clients or bursts.
- Caching hot prefixes: popular prefixes often have excellent reuse.
Cancellation is an optimization, not a correctness guarantee: a request may already have reached the server. The client should still ignore responses that do not correspond to its latest input.
A practical API might be:
GET /suggest?q=iph&locale=en-US&limit=8
GET /search?q=iphone%20case&category=accessories&sort=relevance&limit=20
The service should bound input length, expansion complexity, and returned suggestion count. The cache key must include any locale, market, or other context that changes the response.
7. Search Ranking: Retrieval Is Not Relevance
An inverted index answers which documents might match. It does not, by itself, determine which matches are most useful.
A practical ranking pipeline is:
Query
|
v
Candidate retrieval + eligibility filters
|
v
First-stage lexical ranking (for example, BM25)
|
v
Optional re-ranking of a bounded top-N set
|
v
Final eligibility / business rules + top-K results
BM25 is a common lexical baseline. It rewards matches on distinctive terms, considers term frequency with diminishing returns, and normalizes for document length. It is more nuanced than simply counting keyword occurrences.
An optional second-stage ranker can incorporate popularity, recency, category relevance, or personalization. Running an expensive model on a bounded candidate set controls re-ranking cost, not the cost of retrieving candidates from the index.
Business rules need care. If an out-of-stock product must never be shown, filtering it only after selecting the top 10 could leave too few results even when valid products exist lower down. Apply hard eligibility constraints early enough to preserve the requested result count, or retrieve enough additional candidates to satisfy them.
When the optional re-ranker fails, the system can fall back to lexical ranking, preserving search availability with reduced relevance quality.
8. Filters, Facets, and Typo Tolerance
These features are related but not interchangeable.
Filters constrain eligibility: brand = Apple, price <= 500, or in_stock = true. They generally should not change textual relevance scores unless that is a deliberate ranking rule.
Facets aggregate the matching set: for example, how many eligible products fall into each brand or price range. Facets may be expensive on large result sets or high-cardinality fields. Their semantics must be defined carefully, especially whether a facet's own filter is included when computing its counts.
Typo tolerance expands potential matches. Common techniques include edit-distance matching, n-grams, and spelling correction. They can improve recall, but broad fuzzy matching on a two-character query may expand into an enormous set of candidate terms.
Use bounded edit distance, minimum query length, and query-complexity limits. Exact-match identifiers such as SKUs should generally not receive the same fuzzy treatment as natural-language titles.
9. Keeping the Search Index Up to Date
The source database is authoritative; the search index is a derived view. Product updates need to reach the index reliably.
A typical pipeline is:
Committed DB change
|
v
CDC or reliably published event
|
v
Durable log / queue
|
v
Indexer: validate -> transform -> version-check
|
v
Search index (+ suggestion index when applicable)
|
v
Refresh / visibility to queries
CDC is one option, not the only one. Application-emitted events and scheduled imports can also work. If an application writes the database and separately publishes an event, it must address the dual-write failure gap (for example, through a transactional outbox).
Duplicate and out-of-order updates
Consider the same product receiving:
Update v11: price = 120
Update v12: price = 100
If v12 is applied first and a delayed v11 is then applied without checking versions, search shows the wrong price. The indexer must reject stale updates based on a trustworthy, monotonically increasing per-document version. A wall-clock updated_at timestamp alone may not be reliable enough if timestamps collide or clocks are inconsistent.
Deletes require the same care. A delayed pre-delete update must not resurrect a deleted product. The system needs version-aware tombstone handling or an equivalent mechanism that prevents stale resurrection.
Indexing lag is not just queue lag
Even after an indexer successfully writes a document, the search engine may not expose it to normal queries until a refresh. Observed freshness includes both pipeline delay and index visibility delay, plus any applicable result-cache staleness.
Reducing refresh intervals can improve freshness but increases indexing/segment-management work. A freshness target should therefore be an explicit product requirement.
Full reindexing without taking search offline
Changing analyzers, mappings, or transformations can require rebuilding the corpus. A safer approach is:
- Create a new versioned index.
- Bulk-load a consistent source snapshot.
- Apply and catch up on changes made during the rebuild.
- Validate counts, sample documents, deletes, and search quality.
- Switch the serving alias or routing layer to the new index.
- Retain the old index briefly for rollback.
The snapshot and change stream need a well-defined handoff position; otherwise updates made during the rebuild can be missed. Do not destructively rebuild the only live index and assume rollback will be easy.
10. Caching Search Results Correctly
Popular queries repeat, making caching attractive. But a cache key based only on the raw query string is often incorrect.
Two requests for iphone can produce different responses depending on:
- Filters and sort order.
- Locale, region, or tenant.
- Pagination cursor or page.
- Ranking/index version.
- Personalization or user-specific eligibility.
Cache only across requests that are genuinely allowed to share the same response. Authorization or tenant boundaries must never be lost through cache-key normalization.
Cache key = normalized query + filters + sort + locale
+ page/cursor + index/ranker version
+ relevant access/personalization context
Choose TTLs according to query reuse and freshness requirements; there is no universally correct 60-second TTL. For personalized queries with little full-response reuse, caching candidates or reusable components may work better.
Cache stampede
Suppose the cache absorbs 80% of incoming search requests. The index normally receives 20%. If the cache disappears and incoming demand stays the same, index-facing traffic can rise by approximately:
1 / (1 - 0.80) = 5x
That is an example derived from an assumed hit rate, not a universal multiplier. Request coalescing, TTL jitter, stale-while-revalidate where acceptable, capacity headroom, and load shedding can limit the damage.
11. Sharding, Replication, and Scatter-Gather
When one search node cannot efficiently hold or serve the corpus, distribute documents across shards.
Hash-based document sharding
A document ID hash can spread documents relatively evenly. A broad keyword query may then need to reach every relevant shard, because matching documents could be anywhere.
Routed sharding
Routing by tenant, region, or category can reduce query fan-out when the query specifies that routing dimension. It can also create skew: one very large tenant may produce a hot shard.
Scatter-gather query execution
Search Coordinator
/ | \
Shard A Shard B Shard C
top-K top-K top-K
\ | /
Merge + Global Top-K
Each shard produces its best local candidates; the coordinator merges them. For a straightforward global top-K under a consistent comparable scoring function, retrieving K from each shard is sufficient before global merging. Additional candidates may be required by a subsequent global re-ranking stage, pagination strategy, or other engine-specific behavior; oversampling is not inherently necessary just because results are sharded.
Distributed search is sensitive to tail latency: a single slow shard can delay the response. Replicas improve availability and read capacity, but do not guarantee uninterrupted or perfectly fresh service. If no replica of a required shard responds, the system must explicitly choose to fail the query or return clearly marked partial results.
For a product catalog, partial results may be acceptable. For legal discovery or financial reporting, silently omitting a shard's results could be unacceptable.
12. Pagination: Why Deep OFFSET Becomes Expensive
Simple pagination is easy to explain:
-- Conceptual syntax; actual search-engine APIs differ.
OFFSET 10000 LIMIT 20
In a distributed search, deep offset pagination may require shards to collect many more results than the 20 shown to the user, increasing work with page depth. Changes between requests can also cause duplicates or omissions.
Search-after/cursor pagination carries the sort position of the last result, including a deterministic tie-breaker such as document ID:
{
"query": "iphone case",
"limit": 20,
"search_after": [8.42, "product_991823"]
}
The example assumes a score-descending, ID-tiebroken sort; the actual cursor and comparison rules must match the engine's configured ordering. A cursor avoids repeatedly skipping earlier results, but it does not freeze the underlying result set. If stable multi-page results matter, combine it with point-in-time/snapshot semantics supported by the engine.
13. Production Failure Scenarios
A design is incomplete if it only describes the happy path. These are the failures most likely to change our architectural choices.
| Failure | User-visible impact | Response |
|---|---|---|
| Search shard unavailable | Errors, higher latency, or incomplete results | Route to healthy replica; otherwise follow explicit fail/partial policy |
| Cache outage | Search cluster receives sudden extra traffic | Request coalescing, headroom, load shedding |
| Indexer backlog | Newly changed products remain stale in search | Monitor oldest event age, retain backlog, scale catch-up capacity |
| Lost CDC events / retention gap | Index may permanently diverge | Reconcile against source; rebuild when replay is impossible |
| Bad analyzer/index deployment | Wrong matches or degraded relevance despite healthy servers | Versioned indexes, validation, alias rollback |
| Old update arrives after delete | Deleted product reappears | Source-version checks and durable tombstone semantics |
| Hot prefix or expensive fuzzy query | CPU spikes, increased tail latency | Cache hot prefixes; bound expansions, deadlines, and query complexity |
| Ranking dependency fails | Search relevance degrades | Fall back to first-stage lexical ranking |
| Autocomplete index lags | Search finds a product that suggestions omit | Separate freshness monitoring and defined suggestion-update cadence |
Monitor more than availability
A search service can return HTTP 200 while its results are wrong. Useful measurements include:
- Search and autocomplete P50/P95/P99 latency, error rate, and QPS.
- Per-shard latency, timeouts, load, and replica health.
- Cache hit rate, hot-key pressure, and upstream request coalescing.
- Indexing backlog, oldest unprocessed event age, and end-to-end freshness.
- Source/index divergence checks, delete correctness, and failed indexing events.
- Zero-result rate, relevance regression tests, and other quality signals interpreted in context.
For more failure walkthroughs, see Search & Autocomplete — Failure & Scale Scenarios.
14. Major Architecture Trade-offs
| Decision | Simpler option | When added complexity may be justified |
|---|---|---|
| Search engine | Database-native full-text search | High QPS, sophisticated ranking/facets, independent scaling |
| Autocomplete | Search-engine prefix queries | Dedicated suggestion index for latency isolation or specialized ranking |
| Prefix representation | Edge n-grams | Trie/FST or precomputed suggestions for specific memory/update/latency goals |
| Change propagation | Batch import or polling | CDC or reliable domain events for tighter freshness |
| Ranking | Lexical relevance only | Re-rank bounded candidates for richer relevance signals |
| Cache | Cache common final responses | Cache candidates/components when full responses have low reuse |
| Sharding | Hash by document ID | Routing by tenant/domain when queries can exploit it |
| Pagination | Shallow offset | Search-after for deep pages; snapshot for stable multi-page views |
| Shard failure | Fail the query | Marked partial results when the product tolerates incompleteness |
The correct design is the simplest architecture that meets the stated requirements. A trie, CDC pipeline, separate ranking service, and multiple caching layers should each have a reason to exist. Adding all of them by default is not a sign of a stronger design.
See the full Trade-offs & Decisions discussion for the alternatives behind these choices.
15. Search & Autocomplete System Design Interview Questions
Why not use the primary database for search?
For small workloads, we may. At higher scale, a dedicated index provides search-specific structures and independent scaling. Avoid claiming SQL databases cannot perform full-text search.
What's the difference between an inverted index and a trie?
An inverted index maps terms to matching documents. A trie organizes prefixes for efficient completion lookup. They answer different questions, and autocomplete does not necessarily require a trie.
How do you handle typos?
Use bounded fuzzy matching, n-grams, or spelling correction where appropriate. Keep exact identifiers exact and prevent broad short-prefix expansions.
How does a new product become searchable?
A committed source change reaches an indexer through CDC or reliable events, is applied with version checks, and becomes visible after the search engine's refresh. The process is usually eventually consistent.
What happens if indexing stops for 30 minutes?
Search can continue serving stale results. Recovery requires the missing events to remain available and the indexer to catch up faster than new events arrive. If event history is lost, reconciliation or reindexing is necessary.
Why use BM25 and then a re-ranker?
BM25 gives an efficient lexical baseline. A bounded re-ranking stage can use richer signals without scoring the entire corpus with an expensive model.
How do you prevent autocomplete from overwhelming the backend?
Debounce, ignore stale responses, enforce minimum prefix lengths where suitable, cache common prefixes, and apply server-side rate and complexity limits.
What happens when a shard is down?
Try a healthy replica. If no copy is available, either fail the query or return results explicitly marked as partial, depending on whether incompleteness is acceptable.
How do you change analyzers without downtime?
Build a new index from a snapshot, replay intervening changes, validate, switch the serving alias, and retain the old version for rollback.
Why not use OFFSET for page 500?
Deep offset work grows with depth and results can shift between requests. Search-after avoids repeated skipping; point-in-time semantics can provide a stable view when required.
For a broader question bank, see Search & Autocomplete — Interview Perspective.
Final Takeaways
A reliable search system separates the source of truth from the search-optimized view, and separates candidate retrieval from ranking. Autocomplete introduces another latency-sensitive workload whose candidate generation, ranking, and request controls deserve explicit design decisions.
The most important production details are easy to overlook: compatible text analyzers, version-aware indexing, safe delete handling, refresh lag, correct cache keys, bounded expensive queries, shard failure semantics, and rebuilds that do not destroy the live index.
None of these mechanisms is a universal prescription. Start with the actual search experience, traffic, freshness, and correctness requirements; introduce complexity only where those requirements justify it.
Top comments (1)
Really thoughtful post! Documenting real-world engineering hurdles and actionable solutions like this brings immense value to the community.