Search & Autocomplete — Architecture Deep Dive

Splitting raw text into individual terms — usually on whitespace and punctuation, though this gets more nuanced for languages without clear word boundaries (e.g. Chinese, Japanese).

Reducing case variation ("iPhone" and "iphone" should typically match) and sometimes accent/diacritic folding ("café" vs "cafe").

Stemming crudely truncates words toward a common root ("running" → "run", "runs" → "run") using rules, sometimes producing non-words. Lemmatization uses vocabulary/grammar knowledge to find the dictionary base form, at higher computational cost. Neither is universally applied — some fields (brand names, SKUs, exact-match identifiers) should not be stemmed at all.

Very common words ("the", "a", "is") are sometimes removed to shrink index size and reduce noise in scoring. This is domain-dependent — stopword removal can break phrase queries or meaningful short queries (e.g. a band literally named "The The").

Different languages need different tokenization, stemming and stopword rules. A single multilingual corpus commonly needs a per-field or per-document language-aware analyzer, not one global pipeline.

Expanding or rewriting terms so that "sneaker" also matches documents containing "trainer", or "tv" matches "television". Synonym rules are typically applied at index time, query time, or both, depending on the desired trade-off between index size and query flexibility.

Not every field should be analyzed the same way. A product title field is usually analyzed (tokenized, lowercased, maybe stemmed) for relevance matching, while a sku or status field is usually kept as an exact keyword field for precise filtering and sorting, not textual relevance.

Posting lists are typically kept sorted by document ID, which allows efficient merge-style intersection (AND) and union (OR) across multiple terms' posting lists — similar to merging two sorted arrays.

Matching a phrase like "wireless iphone case" isn't just an AND of three terms — it requires that the position of "iphone" is one more than "wireless", and "case" one more than "iphone", in the same document and field. This is only possible if position information was stored at index time.

Posting lists for common terms can be very long. Techniques such as delta encoding (storing the gap between consecutive document IDs rather than the IDs themselves, since gaps are usually small numbers) and variable-length integer encoding substantially reduce storage and I/O cost.

For very long posting lists, skip pointers let a query jump ahead in a sorted posting list instead of stepping through every entry — useful when intersecting a long list against a much shorter one. Search engines also use techniques (score-sorted postings, dynamic pruning) to stop early once they're confident the current top-k can't be beaten, rather than scoring every candidate.

A multi-term query can require all terms to match (AND — intersect posting lists) or any term to match (OR — union posting lists), with most real systems using OR-with-scoring-preference for match quality (documents matching more terms score higher) rather than strict boolean AND.

Require adjacent-position matches across terms in the same field, as covered above — more expensive than a simple term match because position lists must be checked, not just presence.

A query against an exact keyword-style field (e.g. status: "active") is a direct term lookup with no analysis; a query against an analyzed text field goes through the same tokenizer/stemmer/synonym pipeline as indexing did, so the query terms end up compatible with the indexed terms.

Matching all terms starting with a given prefix ("iph*") — the mechanism autocomplete relies on, covered in more depth later in this page.

Matching terms within some edit distance of the query term, covered in its own section next — it materially expands the set of terms that must be considered.

A filter clause (e.g. category = "electronics", price <= 500) constrains which documents are eligible without necessarily contributing to the relevance score, and can typically be cached/reused more efficiently than a scored clause. A scoring clause (a keyword match) determines both eligibility and how strongly a document should rank. Conflating the two is a common design mistake — see Filters & Facets below.

Match query terms against index terms within some edit distance (insertions, deletions, substitutions) — e.g. "iphoen" matching "iphone" at edit distance 2. This expands a single query term into a set of index terms to look up.

Break terms into overlapping character sequences (e.g. trigrams: "iph", "pho", "hon", "one") and index those instead of/alongside whole terms, so partial character overlap can still produce a match even with a typo.

Suggest or silently substitute a corrected query ("Did you mean: iphone?") using a dictionary, edit distance, or a model trained on query logs — distinct from directly fuzzy-matching every term.

For high-traffic queries, precompute common misspelling → correct-query mappings from historical query logs rather than computing fuzzy matches live for every request.

Many systems only enable fuzzy matching once the query reaches a minimum length (e.g. 3-4 characters), since short queries have too many plausible fuzzy matches to be useful or cheap.

Bounding edit distance to 1-2 keeps the expanded term set manageable; higher distances rarely improve relevance meaningfully while sharply increasing cost.

Exact-match and range filtering is typically served by structures optimized for that purpose (sorted/columnar value structures, exact-match term dictionaries for keyword fields) rather than the same scored full-text structures used for relevance.

Facet aggregation over a high-cardinality field (thousands of distinct brand values, for example) or over a very large matching set can be considerably more expensive than just retrieving top-k results — it's proportional to the matching-set size and field cardinality, not a fixed cost.

Every distinct combination of filters is effectively a distinct query for caching purposes. A product search page with 8 filterable facets can produce an enormous number of realistic filter combinations — this dramatically increases cache-key cardinality and lowers effective hit rate versus caching keyword-only queries. See Search Cache Design below.

Reuse the existing full-text search infrastructure's native prefix-query capability. Simpler operationally (one system to run), but performance depends heavily on the specific engine, query type and concurrent load — it may or may not reliably hit an aggressive latency budget under heavy full-text query traffic sharing the same cluster.

At index time, generate and index every prefix of a term ("iphone" → "i", "ip", "iph", "ipho", "iphon", "iphone") as separate indexed terms. Query-time prefix matching becomes a fast, direct term lookup — at the cost of a meaningfully larger index (write amplification proportional to average term length) and index-time cost.

A dedicated tree/automaton structure purpose-built for prefix traversal. Can be very compact and efficient for prefix lookup and, if top-k completions are precomputed per node, can turn suggestion retrieval into a single lookup rather than a full subtree walk. Operational complexity, memory footprint and update cost vary considerably by implementation — it is not automatically cheaper or simpler than the alternatives above.

Precompute a ranked suggestion list per prefix from historical query logs ("what did users who typed this prefix actually search for?"). Excellent for popular, frequently-repeated queries, but needs explicit handling for freshness (new/trending queries), decay of old trends, and spam/inappropriate-suggestion filtering — a raw query log is not automatically a safe suggestion source.

How often a term or query has historically been searched or selected — the most common baseline signal for autocomplete ranking.

Recently surging query volume can matter more than long-run historical popularity, especially around news, events or product launches.

How well the candidate actually matches the typed prefix (exact prefix match vs a looser fuzzy match) — a factor when suggestions blend multiple generation sources.

The same prefix can warrant different suggestions in different languages, regions or storefronts.

Suggestions can be weighted by the section of the product a user is browsing, or by category-specific popularity.

A user's own search/purchase history can re-rank or supplement generic popularity-based suggestions, at the cost of added complexity and reduced suggestion cacheability.

Wait a short interval (commonly on the order of 100-200ms, tuned per product) after the last keystroke before firing a request, so a fast typist doesn't generate one request per character.

When a newer keystroke fires a new request, cancel or ignore the in-flight request for a now-stale prefix, so its (delayed) response doesn't overwrite a newer, more relevant one.

Skip firing a request at all until the query reaches a minimum length, since very short prefixes (1-2 characters) tend to be the least useful and most expensive to serve well.

Autocomplete's per-user request rate is inherently higher than full search's — rate limiting needs to be calibrated for that shape, not reuse full-search limits directly.

Very short and very common prefixes ("a", "ip", "sh") are requested extremely often across many users and are excellent, high-reuse cache candidates.

Attach a monotonically increasing request sequence number (or timestamp) to each autocomplete request; the client only applies a response if it's the response to the most recent request it issued, discarding responses to superseded requests even if they arrive out of order over the network.

Every change event needs a stable identifier for which document it applies to, so updates and deletes for the same document can be correctly correlated.

A monotonically increasing version or sequence number from the source (an updated_at timestamp, a row version, an LSN) that lets the indexer detect and reject stale updates.

Applying the same update event twice must produce the same index state as applying it once — necessary because most delivery pipelines are at-least-once, not exactly-once, so duplicate events are expected, not exceptional.

A delete event must actually remove (or mark removed) the document from the index — including correctly handling the case where a delete event arrives before, or racing with, an update event for the same document.

The pipeline (broker redelivery, connector retries, at-least-once semantics) can and will redeliver the same event. Idempotent upserts, keyed on document ID and applied only if the version increases, absorb this safely.

Network/broker/partition behavior can deliver events out of sequence. Without version checking, a delayed older update can silently overwrite a newer one.

A document that consistently fails to index (malformed data, a schema mismatch) should retry with backoff and eventually land in a dead-letter queue rather than blocking the pipeline indefinitely or being silently dropped.

The gap between a source change being committed and it becoming visible in the search index — driven by pipeline throughput, batching, and downstream refresh behavior (see next section).

A more aggressive (more frequent) refresh interval makes new documents searchable sooner, at the cost of more frequent segment creation and more background merge work competing for the same CPU/I/O resources serving live queries.

This is a second, independent source of indexing lag beyond pipeline lag (covered above): even after a document reaches the search node, it may sit in a buffered, not-yet-refreshed state briefly before becoming queryable. Total observed freshness is pipeline lag plus refresh lag.

Changing tokenization, stemming, synonym rules or field mappings affects how existing documents were analyzed — old documents need to be re-analyzed under the new rules to match consistently.

Adding a new field used for ranking or filtering that existing documents don't yet have populated.

A damaged index (bad deployment, storage fault, bug) may need to be rebuilt from the authoritative source rather than repaired in place.

A significant change to how source data is transformed into indexed documents.

Pull a bounded candidate set from the inverted index using term matches and filters — this stage cares about eligibility and a fast first-pass score, not final precision.

Score the candidate set with a comparatively cheap lexical relevance function. BM25 is the standard baseline here.

A smaller top-N slice of the first-stage results (not the full candidate set) can be re-scored with more expensive signals or models — this bounds the expensive stage's cost independent of how large the full candidate/match set was.

Final adjustments — promoted placements, eligibility exclusions (out-of-stock, region-restricted), diversity constraints — applied after relevance ranking, where appropriate for the product.

Search-after pagination is efficient, but it is not automatically immune to the underlying document set or ranking changing between page requests — if ranking/index contents shift mid-pagination, results can still move relative to what was on a previous page. Where stronger consistency is genuinely required (rare for typical product search, more relevant for some compliance/audit use cases), point-in-time or snapshot semantics can pin the view a pagination session sees, at additional resource cost.

The query text after the same normalization applied at index/analysis time — so "iPhone " and "iphone" hit the same cache entry rather than being treated as different queries.

Every applied filter (category, price range, in-stock) is part of what makes a response valid for that cache entry — two requests with the same query text but different filters are different queries.

An explicit sort order (price ascending, newest first) changes the response and must be part of the key.

Multi-region or multi-tenant systems can return entirely different result sets for the same query text depending on locale, storefront or tenant.

Each page (or cursor position) is effectively a distinct response.

If the ranking model or index version changes, previously cached responses may reflect stale ranking logic — the model/index version should be part of the key, or the cache should be invalidated on ranking changes.

Where personalization exists but is bucketed into a manageable number of segments (rather than being fully per-user), the segment can be included in the key without collapsing to a per-user cache with near-zero reuse.

Cache lifetime is a workload-dependent tuning decision, not a universal constant — see Trade-offs → Cache TTL vs Freshness.

Proactively invalidating a cached search result when the underlying documents change is hard in general, since many different queries could be affected by one document update — most systems rely on TTL expiry rather than precise invalidation.

Collapse many concurrent identical requests (same full cache key) into a single upstream query, fanning the one result out to all waiters — this is the primary defense against thundering-herd spikes on cache expiry, independent of TTL length.

Serve a slightly-expired cached entry immediately while asynchronously refreshing it in the background, trading a small amount of staleness for consistently low latency, even right at TTL expiry.

Caching "no results found" responses can protect the cluster from repeated expensive misses, but must be done carefully — a genuinely fixed typo or a newly-added document could turn a correct empty result into a stale incorrect one if the negative-cache TTL is too long.

Partition documents across shards by a hash of the document ID. Produces well-balanced document distribution across shards, but since any document could be on any shard, a broad keyword query generally must be sent to every shard to find all matches — it doesn't inherently reduce fan-out.

Route documents (and, correspondingly, queries that specify that key) to a specific shard or shard subset based on a meaningful key — a query that specifies "tenant X" or "category: electronics" only needs to hit the shard(s) holding that tenant/category, meaningfully reducing fan-out for queries that can supply the routing key. The trade-off: this risks uneven shard sizes if some tenants/categories are much larger than others (a hot-shard risk, covered in Failure & Scale Scenarios), and complicates any query that genuinely needs to search across categories/tenants.

Because a document that's only the 5th-best match on its own shard could still be the true global 3rd-best overall, each shard typically needs to return somewhat more than the final desired top-k ("oversample") for the coordinator to reliably compute the correct global top-k after merging — returning only the exact final page size per shard risks silently missing legitimately better-ranked results that happened to land on a less-represented shard.

The coordinator's response time is bounded by the slowest shard it queried, not the average — so more shards queried generally means higher exposure to tail latency from any single slow or degraded shard, plus more merge work at the coordinator.

Each shard typically has one or more replicas holding a copy of that shard's data, allowing reads to be served from any replica and providing a fallback if the primary is unavailable.

Exactly how writes propagate to replicas, how promotion happens on primary failure, and what consistency a replica read offers relative to the primary all vary by system and configuration — this module deliberately does not bind these mechanics to one vendor's exact behavior.

If a specific replica or the primary for a shard is unavailable, the coordinator can often route that shard's portion of the query to a different available replica instead, without failing the whole query.

If a system chooses to return partial results rather than failing outright, that partial-ness must be explicitly surfaced (a response flag, a UI indicator, a logged/monitored event) rather than silently presented as a complete result set — a user (or a downstream system) treating a partial result as complete can draw wrong conclusions, especially for any product where completeness matters (compliance search, financial reporting search).