Dinesh/ Blog
systems

Designing for Scale · Typeahead and Search Autocomplete

Prefix lookup, top-k maintenance and hot prefixes. A source-bounded lesson with worked reasoning, failure analysis and explicit runtime limitations.

9 min read
Checking device speech…
Lesson preparation & details

Level: advanced

Designing for scale · Lesson 7 of 20 ↗
Loading this browser’s progress…

By the end, you should be able to

  • Prefix lookup, top-k maintenance and hot prefixes
  • If complete queries are hash-sharded, where does a request for prefix “sy” go?

Bring with you

Sources checked: . A source check does not change the publication or update date.

Editorial review: · What review means

In this article · 13 sections

The problem this post solves

Autocomplete returns a useful bounded list while someone types. Choose the end-to-end latency and freshness targets with the product; fifty milliseconds is an example budget, not a law that makes all database implementations impossible. Include client/network time, request cancellation, language/normalization rules, eligibility and abuse/privacy controls. A fast unsafe suggestion is not a successful result.

Start with the corpus size, update rate and ranking function. An indexed prefix query may be enough; PostgreSQL 16 documents B-tree support for anchored constant LIKE 'foo%' patterns, with locale/operator-class requirements. It does not promise performance for every collation, parameterization or popularity ranking. Compare an index, trie, finite-state representation or search service against the same workload rather than claiming LIKE always takes seconds or locks the whole database.

First principles

Prefix matching and ranking are different operations. An ordered index may locate strings in a prefix range without already ordering them by popularity. A trie reaches the matching subtree without sorting every string, but still needs a strategy for selecting its best suggestions. If a prefix has a million descendants, enumerating all of them at request time may exceed the budget. Precomputed top-k summaries trade memory and update work for bounded serving work; that is an option derived from the query, not proof that every workload requires it.

Define the score: count in a recent window, decayed popularity, editorial relevance or a personalized function. A global top-five popularity cache cannot necessarily answer a user's personalized top-five request. Specify tie-breaking, locale and safety filtering consistently between build and serve. Otherwise identical prefixes can produce nondeterministic or unauthorized output despite a correct data structure.

The Trie Data Structure

A trie follows symbols along a root-to-node path. For the ASCII examples below, a symbol is one character. Unicode code points, normalized text and user-perceived characters are not interchangeable; choose a normalization and locale policy before extending this fixture. Inserting sys:10, system:50 and sync:20 produces shared s → y nodes, then branches through s and n. The word sys can end at an internal node that also has descendants. Keep an explicit terminal marker/value rather than assuming only leaves are complete queries.

The Optimization: Caching Top Queries at the Node

For prefix sy, the ranked descendants are system:50, sync:20, sys:10. If k=2, cache only the first two references at that node. A lookup traverses p prefix symbols and copies k references: O(p+k) for this representation, plus serialization proportional to the returned text bytes. It is not O(1) independent of input/output length. Without the summary, enumerating m matching words and sorting them costs additional work, with an ordinary sort using O(m log m) comparisons.

This complete deterministic implementation rebuilds a small trie from already normalized ASCII counts. It is not a memory-efficient production index or an incremental update engine. The top lists store references to query/count tuples; full text transmission still has a cost.

def build_trie(counts, k=2):
    if type(k) is not int or k <= 0:
        raise ValueError("positive integer k required")
    root = {"children": {}, "top": [], "terminal": None}
    for query, count in counts.items():
        if not isinstance(query, str) or not query or not query.isascii():
            raise ValueError("fixture requires nonempty normalized ASCII queries")
        if type(count) is not int or count < 0:
            raise ValueError("nonnegative integer count required")
        node = root
        for character in [None, *query]:
            if character is not None:
                node = node["children"].setdefault(
                    character, {"children": {}, "top": [], "terminal": None})
            node["top"] = sorted(node["top"] + [(query, count)],
                                 key=lambda pair: (-pair[1], pair[0]))[:k]
        node["terminal"] = count
    return root
 
def suggest(root, prefix):
    node = root
    for character in prefix:
        if character not in node["children"]:
            return []
        node = node["children"][character]
    return [query for query, _ in node["top"]]
 
trie = build_trie({"sys": 10, "system": 50, "sync": 20})
assert suggest(trie, "sy") == ["system", "sync"]
assert suggest(trie, "sys") == ["system", "sys"]
assert suggest(trie, "missing") == []
assert suggest(build_trie({"ab": 5, "aa": 5}), "a") == ["aa", "ab"]
assert suggest(trie, "") == ["system", "sync"]  # explicit fixture policy
print("prefix, internal terminal, tie, absent and empty-prefix cases passed")

Each insertion updates summaries along its path; this deliberately simple builder sorts a list of at most k+1 candidates at each visited node. Production builders may use a different aggregation/compression strategy. For n distinct prefix nodes, storing k references per node can approach O(nk) reference space before strings, node maps and allocator overhead. Count decreases/deletions are especially important: removing the winner can require recovering a candidate previously excluded from the summary, not merely decrementing one cached score.

Architecture

Architecture
Figure text equivalent — labels and relationships
  • Node “Client prefix request” (square).
  • Node “Autocomplete API” (square).
  • Node “Current versioned suggestion index” (square).
  • Node “Eligible submitted-query events” (square).
  • Node “Durable intake with privacy policy” (square).
  • Node “Normalize, deduplicate and aggregate window” (square).
  • Node “Safety and eligibility filtering” (square).
  • Node “Build and validate immutable index” (square).
  • Node “Publish version pointer” (square).
  • “Client prefix request” leads to “Autocomplete API”. Line: normal; ends: arrow point.
  • “Autocomplete API” leads to “Current versioned suggestion index”. Line: normal; ends: arrow point.
  • “Client prefix request” leads to “Eligible submitted-query events”. Line: normal; ends: arrow point.
  • “Eligible submitted-query events” leads to “Durable intake with privacy policy”. Line: normal; ends: arrow point.
  • “Durable intake with privacy policy” leads to “Normalize, deduplicate and aggregate window”. Line: normal; ends: arrow point.
  • “Normalize, deduplicate and aggregate window” leads to “Safety and eligibility filtering”. Line: normal; ends: arrow point.
  • “Safety and eligibility filtering” leads to “Build and validate immutable index”. Line: normal; ends: arrow point.
  • “Build and validate immutable index” leads to “Publish version pointer”. Line: normal; ends: arrow point.
  • “Publish version pointer” leads to “Current versioned suggestion index”. Line: normal; ends: arrow point.

The Write Path (Data Gathering)

Decide which actions count: submitted searches, selections or another product event. Logging every keystroke is neither required nor automatically privacy-safe. Give events stable identity, rate-limit abuse/bot inflation and define the aggregation window. Normalization may merge strings, so retain a documented display-form policy without retaining unnecessary raw sensitive queries. Rare query strings can identify people even after obvious names are removed; safety requires more than a popularity threshold or a single regular expression.

The Build Path (Trie Construction)

Build from a named input snapshot/window, calculate deterministic scores/ties, filter disallowed strings, and record index version, schema and normalization version. Validate prefix examples, empty/absent results, maximum returned length and newly blocked queries before publication. An immutable build allows an atomic local pointer switch and rollback. Across many servers, publishing a version does not mean every reader changes simultaneously; choose rollout/version semantics and track adoption. Peak memory may include both old and new indexes during a swap.

Incremental or streaming updates are possible when freshness warrants their complexity. They need concurrency control and correct summary repair; real-time maintenance is not mathematically forbidden. An offline base plus a small recent-events overlay can be another choice, with deduplication and score comparability defined at merge time.

The Read Path

Validate and normalize the prefix under the same rules as the index, apply the correct locale and authorization context, and return a bounded list. Debounce and cancel superseded client requests where appropriate; ensure a slow response for sy cannot overwrite a newer result for syst. Version/cache keys and request IDs can prevent that ordering bug.

A local immutable index avoids a network lookup but uses per-process memory and update coordination. A remote materialized prefix table/cache can share capacity but adds network, queueing and dependency failure. Neither guarantees the lowest possible latency, a sub-1ms hop or a universal “web-scale default.” Benchmark tail latency and define what a timeout returns—perhaps no suggestions rather than blocking the user's search submission.

Sharding the Trie

Distinguish hashing complete queries from hashing materialized prefix keys. If complete queries are distributed by hash, all words beginning sy can span shards; a prefix request needs scatter/gather or another prefix index. If every prefix already has its own top-k entry, hashing that exact prefix key can route one lookup to one shard. It does not perfectly balance traffic: a single very hot prefix still maps to one shard.

Alphabetical/range partitioning preserves prefix locality but can be skewed by language and query frequency. Replicate/cache hot short-prefix results or split ranges with an explicit routing map; do not assume a letter gets “exponentially” more traffic without measurement. With per-shard candidate lists, merging local top-k is valid for disjoint items and a shared ranking order; duplicates across shards, post-filtering or personalized scores can require more candidates or a different correctness argument.

Edge Optimization

Cache only under the appropriate privacy/freshness contract. A public generic suggestion list can be keyed by normalized prefix, locale and index version; a personalized response must not be shared across users by a prefix-only CDN key. Use explicit cache directives and bounded lifetimes, not a universal “hours in browser, one hour at edge” rule. An emergency removal of a harmful/private suggestion may require invalidation or short freshness independent of the routine index rebuild cadence. A versioned immutable URL helps normal rollout but does not erase a harmful response already stored by a client.

Failure modes and practice

Exercise: the global sy cache contains system, sync. system is blocked after an abuse review. Is filtering it at response time enough to return the best two safe suggestions? What happens if the server instead fetches only the same two cached entries forever?

Safety and top-k completeness are different

Filtering prevents returning the blocked query, but leaves only sync; it does not discover sys, the next valid candidate. Rebuild/repair the summary, keep an appropriately larger candidate set, or define a safe shorter-result policy. Never fill the second position by reintroducing a blocked item. Cache invalidation and build propagation must follow the removal policy, and the observed response should carry enough version information to debug stale results without logging sensitive query content unnecessarily.

Other failures include inconsistent normalization, unbounded short-prefix fan-out, stale client responses, poisoning of popularity counts and an update that publishes only part of the index. Test each separately rather than treating a fast prefix function as service proof.

What to carry forward

Separate prefix selection, ranking, materialization and sharding. A cached trie lookup is O(prefix length + returned references), not a universal constant-time HTTP operation. Hash partitioning must name the key being hashed. The Python fixture proves the small static lookup/tie behavior; no database latency, Unicode search product or distributed cache was run.

Sources and review boundary

Checked 2026-10-07: PostgreSQL 16 index types for anchored prefix patterns and collation/operator restrictions; RFC 9111 (2022) for explicit caching policy; OWASP authorization guidance for consistently enforced access. Trie complexity follows the displayed loops and bounded output, verified with local fixtures rather than a claimed external benchmark.

Pause / Recall / Apply

Can you explain it without the page?

Close the example. Reconstruct the core idea, then change one assumption. Mark complete when you’re ready; you can always undo it.

Stored in this browser only. No account, no sync. Clearing browser data removes your record.