Autocomplete System Design: Tries, Ranking and Latency

The search box gets slow, jumpy and wrong just when traffic peaks. Each keystroke becomes a database query, the replies arrive late and out of order, and the order of suggestions ignores what people actually want. This is the problem autocomplete system design solves.

Picture a common setup. An Indian home-goods marketplace sells bedsheets, cushion covers, brass diyas and kitchen racks from a few thousand sellers. The setup is made up, but the problem is real.

The team's first autocomplete took one afternoon. Each keystroke sent the text typed so far to the server. The server ran a prefix query on the products table, sorted the matches by name and returned five.

On a normal day it worked. Then the Diwali sale opened at 8 pm and the search box received about 2,000 keystrokes a second (made up). Three things went wrong at once.

• Slow. Suggestions took almost a second to appear. The same database also served checkout, so orders slowed down too.
• Jumbled. Replies came back out of order. A shopper who had typed bedsh saw old lists for be and bed flash past first.
• Wrong order. Names were sorted alphabetically, so bed bug spray sat above bedsheet, although shoppers searched for bedsheet forty times more often.

A quieter problem hid underneath. Shoppers typed diwali lights and gift for mom, and no product name carried those words. Suggestions should come from what people search, not from product names.

Autocomplete system design is building a service that takes a prefix and returns the few most likely full queries, fast enough to feel instant. A prefix is the letters typed so far. Typeahead is another name for the same feature.

Three more words come up again and again.

• Suggestion: one full phrase offered below the search box, such as bedsheet king size. The marketplace shows five under every prefix.
• Top-k: the k highest-scoring suggestions for a prefix. Here k is 5, so the top-k list for bed is the five best phrases that start with bed.
• Latency: how long one request takes, here from the keystroke to suggestions on screen. Teams often track p99, the time within which 99 of every 100 requests finish.

The team wrote its requirements as plain promises.

• Show up to 5 suggestions for any prefix from 1 to 50 characters long.
• Show them within 150 ms of the shopper's last keystroke, for 99 of every 100 requests.
• Rank by what shoppers actually search for and buy, not by product name.
• Reflect new trends within an hour, and sudden spikes within minutes.
• Keep answering if a server dies. A broken search box costs sales, while slightly old suggestions cost almost nothing.

Here is the design the team ended up with. Notice that the suggestion servers never touch the product database. Five parts in it may be new to you.

• A CDN, or content delivery network, keeps copies of replies on servers near users.
• A load balancer spreads requests across several identical servers.
• Kafka is a durable log of events that other jobs read later, at their own pace.
• Object storage keeps whole files, such as one snapshot of the trie.
• Redis is a fast in-memory data store, used here for short-lived counts.

The serving half answers keystrokes from memory. The building half makes a fresh trie every hour. They meet only at the snapshot, one file that holds a whole trie.

Autocomplete needs to feel instant, which in practice means suggestions on screen within about 100 to 150 milliseconds of the last keystroke. Any slower, and the list starts to describe text the shopper has already typed past.

Jakob Nielsen's usability guidance, first published in 1993, gives three limits. About 0.1 second feels instant. About 1 second keeps the user's flow of thought, and about 10 seconds is how long attention holds.

A search box lives at the first limit. A typist at 60 words a minute presses about five keys a second, one every 200 ms, counting a word as five keystrokes as typing tests do. At 120 words a minute, it is one every 100 ms.

So the team set a latency budget: one total time, split into slices, with each part of the system owning a slice. If the total goes over, the team knows which slice to look at.

Look at the trie lookup row: 5 ms out of 150. The network takes far more, so making the server faster alone barely helps.

Debounce: what a short wait really buys

Debouncing means waiting until calls stop for a set time, then acting once. MDN's web docs use this exact case: when the user pauses typing, start giving suggestions.

The catch is that with the usual trailing-edge debounce, which acts after the pause, the wait adds straight to every suggestion. A short wait also merges little. With 50 ms, a key 200 ms after the last one still sends its own request.

We simulated typing bedsheet king size: 18 keys, 150 to 250 ms apart, with a longer pause around each space (made-up timings). Waits of 50 ms and 150 ms both sent 18 requests. A 300 ms wait sent 5.

So the team kept the 50 ms wait only to merge keys that land almost together, and relied on the caches to carry the load. A 300 ms wait would cut requests but break the 150 ms budget by itself.

Dropping replies that arrive late

Fixing the jumbled list needs one rule on the phone: show a reply only if it matches what is in the box right now. The app ignores any reply for an older prefix.

A trie makes autocomplete fast because reaching a prefix takes one step per letter typed, no matter how many phrases you store. You say trie like try.

A trie is a tree of letters. The root stands for the empty prefix. Each child adds one letter, so the path b, e, d leads to the node for bed. Every phrase that starts with bed lives somewhere below that node.

The naive version: find the node, then sort

A plain trie finds the node quickly, but ranking what lies below it is slow. The prefix b may have tens of thousands of phrases under it, and sorting them on every keystroke eats the budget.

Hsu and Ottaviano make the same point in their 2013 paper on top-k completion. A plain trie must sort the matches by score. When short prefixes match millions of strings, they call that prohibitive in speed.

We measured it in Python on 2 lakh (200,000) common English words from the open-source wordfreq library. For the prefix s, a plain trie collected 20,320 words and sorted them in about 32 ms. That is our sandbox, not your phone, but it is far past a 5 ms slice.

The fix: store the answer on every node

The usual fix is to precompute. Each node stores its own top 5 list when the trie is built. A lookup then walks a few letters and reads one ready list, with no sorting at all.

Think of the paanwala at the corner of your lane. Each morning he folds his most asked-for paans and keeps them on a tray. You say meetha, and he reaches for the tray without thinking.

• The customer's first word is the prefix.
• The ready tray is a node's top 5 list.
• Folding paans in the morning is the hourly build.
• Folding extra when a new flavour suddenly sells is the trending layer, which comes later.

Where the picture breaks: the paanwala keeps one tray, while a trie keeps a tray on every node. That is lakhs of trays, which is why memory becomes the real cost.

In the diagram below, follow the letters from the root. Each note shows the ready list stored on that node, cut to three phrases to fit.

Bedsheet sits in the list of every node on its path, eight nodes in all, one per letter. That is the trade: extra memory in return for never sorting. The paper warns that this space scales poorly as k grows.

Here is a small version in Python that you can run as it is. The scores are made up and stand in for the ranking step in the next section.

def new_node():
    return {"kids": {}, "top": []}    # top: best (score, phrase) pairs below

def insert(root, phrase, score, k=5):
    node = root
    for ch in phrase:
        node = node["kids"].setdefault(ch, new_node())
        node["top"].append((score, phrase))
        node["top"].sort(reverse=True)
        del node["top"][k:]           # keep only the k best

def suggest(root, prefix):
    node = root
    for ch in prefix.lower():
        node = node["kids"].get(ch)
        if node is None:
            return []
    return [phrase for _, phrase in node["top"]]

root = new_node()
scores = {"bedsheet": 100, "brass diya": 90, "bucket": 80, "bed cover": 70,
          "bean bag": 60, "bedside lamp": 50, "bean bag cover": 40, "beach towel": 30}
for phrase, score in scores.items():
    insert(root, phrase, score)        # insert each phrase once per build

print(suggest(root, "Beds"))   # ['bedsheet', 'bedside lamp']
print(suggest(root, "bed"))    # ['bedsheet', 'bed cover', 'bedside lamp']
print(suggest(root, "x"))      # []

The lines that matter are inside insert. The append and sort lines keep each node's list in score order, and the del line drops anything past the fifth. That is the precompute step, done once per build.

Two details matter if you reuse this code. Insert each phrase once per build, because a second insert lists it twice. The root's own list stays empty, which is fine because the app never sends an empty prefix.

Do you need to build your own trie?

Not always. The table compares the four options the team considered.

Elasticsearch is a widely used search engine. Its documentation says the completion suggester uses data structures that are fast to search, costly to build and stored in memory. A weight on each suggestion decides its rank.

In Redis, a sorted set keeps members in order of a score. The team still chose its own service, because the ranking rules are the product.

Rank suggestions by a score built from your own logs: how often a phrase is searched, how often it leads to an order, and how recently. Then filter out anything you should never show.

The raw material is the search log. Every finished search writes one event: the phrase, the time, and any click or order that followed. Half-typed prefixes are never counted.

• Searches: how many times the phrase was searched. This is the base of the score.
• Orders: how many of those searches ended in an order. A phrase that sells beats one that leads nowhere.
• Recency: how long ago those searches happened. Diwali lights is huge in October and nearly useless in March.
• Results: whether the phrase returns any products today. A popular phrase with zero results is dropped.

Recency needs care. If you add up every search since launch, last Diwali's phrases win for months. The team uses time decay instead: each day's counts are weighted by their age, and the weight halves every seven days.

In the code below, daily_counts holds one tuple per day for a single phrase. An order counts like five searches. That five is a business choice, not a rule of nature.

HALF_LIFE_DAYS = 7
ORDER_WEIGHT = 5          # one order counts like five searches

def phrase_score(daily_counts):
    """daily_counts: (days_ago, searches, orders) tuples for one phrase."""
    score = 0.0
    for days_ago, searches, orders in daily_counts:
        weight = 0.5 ** (days_ago / HALF_LIFE_DAYS)   # halves every 7 days
        score += weight * (searches + ORDER_WEIGHT * orders)
    return round(score)

print(phrase_score([(0, 900, 60), (1, 700, 40)]))   # 2015

The weight line does the decay. Today's counts get weight 1, last week's get 0.5, and counts from 30 days ago get about 0.05. Run the file and it prints 2015.

Filtering what you must never show

Ranking decides the order. Filtering, run before the build, decides what appears at all.

• Rare phrases: drop any phrase searched by fewer than 20 different shoppers. Rare phrases can hold private details, like a name or phone number someone pasted.
• Blocked words: remove offensive or unsafe phrases, using a list the team keeps up to date.
• Dead ends: remove phrases that return no products today.
• Near duplicates: merge bedsheet, bed sheet and bedsheets into one suggestion, so five slots show five different ideas.

Rebuild the trie from logs on a schedule, such as every hour, and swap the new copy in whole. For sudden spikes between builds, add a small trending layer that updates every few minutes.

Finished searches flow into Kafka. Every hour, a builder job reads the last 30 days of counts and makes a new trie.

The builder writes the trie as one snapshot file to object storage, such as Amazon S3. Each suggestion server notices the new file, loads it into memory beside the old trie, then switches over in one step.

Servers never edit a live trie, so a shopper never sees a half-built one. If a bad build slips through, the team points the servers back to the previous snapshot.

The swap has a memory cost people forget. For a moment, each server holds the old trie and the new one. A 1.8 GB trie needs about 3.6 GB of memory during the swap, so size servers for two copies.

1. 1

   Collect

   Finished searches land in Kafka with the phrase, the time, and any clicks and orders that followed.

2. 2

   Count

   A worker adds up searches and orders per phrase per day, counting each shopper once.

3. 3

   Score and filter

   Apply the decay score, then drop rare, blocked, dead-end and duplicate phrases.

4. 4

   Build

   Insert the surviving phrases into a new trie, with the top 5 stored on every node.

5. 5

   Check

   Compare with the last build. If the phrase count drops sharply or a blocked word appears, stop and alert the on-call engineer.

6. 6

   Publish

   Write the snapshot to object storage. Servers load it beside the old trie, then swap to it in one step.

Catching a spike within minutes

An hourly build is too slow for some moments. Say a viral video makes brass urlis trend, and searches for them jump tenfold in twenty minutes (made up).

The trending layer counts phrases over the last 15 minutes in Redis. Phrases searched far above their usual rate go into a short trending list, filtered like everything else.

Suggestion servers merge that list with the trie's list at lookup time. A trending phrase can take at most one of the five slots, so a mistake there cannot crowd out the main suggestions.

Scale autocomplete by copying the whole trie onto several servers and caching replies close to users. Split the trie across machines only when it no longer fits in one server's memory.

Estimate memory before you draw shards

The team did the maths first. After filtering, it keeps about 20 lakh (2 million) phrases of 18 characters on average. With no shared prefixes at all, that is 3.6 crore (36 million) trie nodes.

Say each node needs about 50 bytes in a compact layout: five 4-byte phrase ids for its top list, plus links to its children. The whole trie then needs about 1.8 GB.

That is a ceiling, and real data sits well under it. In our 2 lakh word test, shared prefixes cut 14.5 lakh letters to 4.4 lakh nodes. Most nodes, 93% of them, had fewer than five phrases below them, so the stored lists held 1.6 phrases on average.

The paper warns that top-k space scales poorly with k. On our word list the growth was gentler: raising k from 5 to 20 grew the stored lists by 24%, because few nodes have twenty phrases below them.

Traffic is easy to estimate too. The marketplace sees about 30 lakh searches a day, each sending about 12 suggestion requests. If the caches answer two of every three, 1.2 crore a day reach the servers.

That is roughly 140 requests a second, and a sale hour brings ten times that. Both numbers are small for modern servers, so the team runs six identical copies across two zones, which are separate data centres.

When you do need to split the trie

A much larger service, with billions of phrases, cannot hold everything on one machine. It splits the trie into shards, pieces kept on different servers. Splitting by the first letters of the prefix sends most lookups to exactly one shard.

The catch is hot spots. In our 2 lakh word list, 20,320 words start with s and only 396 with x. Splitting by first letter alone overloads some servers, so busy letters get split further by measured traffic. If s becomes sa, sb and so on, the lookup for s alone spans shards, so keep the top lists for such short prefixes in a small extra table.

Caching suggestions near the shopper

The cheapest request is one that never reaches a server. Suggestions for a prefix are the same for every shopper, so the team caches them in two places.

• On the phone: replies stay in app memory for a few minutes. When a shopper presses backspace, the earlier list comes back with no network at all.
• At the CDN: its edge servers sit in or near the shopper's city. There are only a few dozen one-letter prefixes, and every query starts with one, so short prefixes stay hot in the edge cache.

HTTP caching rules control how long a copy lives. RFC 9111, the HTTP caching standard, says a response with max-age becomes stale once its age passes that many seconds. The team sends max-age=300, five minutes.

To check it on your own endpoint, fetch a suggestion with curl -s -D - -o /dev/null followed by the URL. It sends a normal GET request, the same kind the app sends, and prints only the response headers, so read the cache-control line. You should see max-age=300 on the shared suggestion list, and private on any personal response, if you serve one.

Follow one request below. Notice that most requests stop at one of the two caches.

A database prefix query costs little for long prefixes and a lot for short ones, because it must read every match before it can sort them by score. Short prefixes are also the ones every shopper types first.

We tested this on PostgreSQL 16.15 with the same 2 lakh words and a score column. Two findings surprised the team.

• A normal index on the phrase column was ignored. LIKE 'bed%' is SQL for text starting with bed, and with a language-aware collation it read the whole table.
• An index built with text_pattern_ops, which compares text letter by letter, fixed the lookup. The PostgreSQL docs describe this for databases not using the C locale. The sorting cost stayed.

A collation is the set of rules a database uses to compare and sort text. The C locale compares raw bytes, which is why a default index works there for LIKE. EXPLAIN ANALYZE runs a query and prints its plan with real row counts.

CREATE INDEX phrases_prefix ON phrases (phrase text_pattern_ops);

EXPLAIN ANALYZE
SELECT phrase FROM phrases
WHERE phrase LIKE 's%'
ORDER BY score DESC
LIMIT 5;
-- look for the index scan line: its actual rows=N
-- is every phrase starting with s (20320 in our test),
-- then: Sort Method: top-N heapsort (keeps only the best 5)

For the prefix s, PostgreSQL read 20,320 rows to return 5 and took about 6 to 16 ms across our runs. For beds, it read 13 rows in about 0.1 ms. Your timings will differ. On your own table, the rows figure equals the number of phrases that start with s.

So the database is fine for long prefixes and worst on the shortest, busiest ones. That is the opposite of what a search box needs, and it puts checkout traffic in the same queue.

Autocomplete handles typos with fuzzy matching: it also accepts phrases whose start is one or two edits away from what was typed. An edit is one letter added, removed or changed.

Shoppers type bedsheat and cushon all day. With exact matching, those return nothing, and an empty list feels broken.

Fuzzy lookup walks the trie more widely. At each letter it may also try a nearby path, spending one edit each time. With a limit of one edit, cushon still reaches cushion.

This costs speed, because each allowed edit multiplies the paths to check. On our 2 lakh word trie, our fuzzy walk for cushon visited 90 nodes with no edits allowed, because it also tests sibling letters, the other branches at each node. It visited 2,971 nodes with one edit allowed, and 23,994 with two.

So the team allows one edit, only from the third letter on, and only when exact matching finds fewer than five phrases. Exact matches always rank first.

Elasticsearch's completion suggester sets similar limits, as of its October 2026 docs. By default, fuzzy suggestions need at least 3 typed characters, and the first character is not checked for typos. Suggestions sharing the longest prefix with the query score higher. Its fuzzy option also counts swapping two neighbouring letters as one edit.

Explain it as two halves, a fast serving path and a slower building path, and tie every choice back to the latency budget.

1. 1

   Pin down the requirements

   Ask how many suggestions, how fresh, whether they are personal, and the latency target. Propose p99 under about 150 ms from the keystroke.

2. 2

   Estimate the size

   Work out phrases, memory and requests per second out loud. Small numbers mean full copies; huge numbers mean shards.

3. 3

   Define the API

   The API is the call the app makes. Here it is one read call that takes a prefix and returns up to five phrases. Logging finished searches is a separate write path.

4. 4

   Choose the data structure

   A trie with the top k stored on every node. Say why a plain trie or a database query is too slow for short prefixes.

5. 5

   Explain ranking and freshness

   Scores from searches, orders and decay. An hourly offline build, a snapshot swap with room for two copies, and a small trending layer.

6. 6

   Cover speed and safety

   Debounce, phone and CDN caches, late-reply checks, copies across zones, and filters for rare or offensive phrases.