Short answers to what readers ask most about this topic.
How to design search autocomplete at scale: capacity arithmetic, a 100 ms latency budget, tries versus Postgres and Redis, decayed ranking, offline log aggregation, top-K caching and a debounced client.
Matthews Wong
Software Engineer
Key Takeaway
Design search autocomplete by precomputing the top ten suggestions for every query prefix offline from aggregated query logs, ranking them by time-decayed frequency, and serving them from Redis or a CDN by exact prefix key. The client debounces keystrokes and cancels stale requests, and the whole round trip targets about 100 milliseconds.
A product picker on a point-of-sale screen is the smallest autocomplete most developers build: type three letters, see matching items. It works on a few thousand rows with a LIKE query, and it keeps working until the list, the traffic or the typing speed grows enough that every keystroke becomes a database query.
This post is a design exercise, not a case study. Every number comes from stated assumptions with the arithmetic shown, or from a cited source, and none is a benchmark. It covers capacity, latency, the data structure, ranking, offline aggregation, caching and the client, ending with a decision checklist. Plain full-text search is covered in the PostgreSQL full-text search post, and the debounce hook basics in the React debouncing guide, so both stay brief here.
Far more than the search it serves. Search is one request per submitted query, while typeahead can fire one per keystroke. Start with assumptions you can defend, then derive everything else. The block below assumes 5 million daily active users and shows why debouncing alone cuts request volume by 4.75 times.
Assumed inputs (a design exercise, not a measurement):
daily active users = 5,000,000
submitted searches per user = 10 per day
average query length = 20 characters, suggestions start at 2
debounced requests / search = 4 (assumed)
peak vs average = 3x
suggestion response = 10 items x 25 B + 300 B headers = 550 B
Searches and requests
searches per day = 5,000,000 x 10 = 50,000,000
requests per day, debounced = 50,000,000 x 4 = 200,000,000
average requests / s = 200,000,000 / 86,400 = 2,315
peak requests / s = 2,315 x 3 = 6,944
The same traffic with no debounce (one request per keystroke from char 2)
requests per search = 20 - 1 = 19
requests per day = 50,000,000 x 19 = 950,000,000
average requests / s = 950,000,000 / 86,400 = 10,995
reduction from debouncing = 950 / 200 = 4.75x fewer requests
Logging and bandwidth
search log writes / s = 50,000,000 / 86,400 = 579 (submitted searches only)
peak response bandwidth = 6,944 x 550 B = 3.8 MB/s
Cache effect (assumed 80% of requests answered by browser or CDN cache)
requests reaching the app = 6,944 x 0.20 = 1,389 / s at peakTwo conclusions follow. The read path must be a cheap key lookup, because 6,944 peak requests per second of ranking work would be absurd, and the search log is a modest 579 writes per second that a batch insert absorbs easily. The 80 percent cache hit figure is an assumption, but it works only because the URL carries nothing user-specific, a property the caching section protects.
Suggestions that arrive after the user has finished typing are noise, so the budget is tight. Nielsen Norman Group describes 0.1 second as the limit for a response that feels instantaneous, which makes 100 ms a reasonable target. Split it across the stages you control and see how much is left.
Target: about 100 ms, the figure Nielsen Norman Group cites for "feels instant".
Budget per request (network and server numbers are assumptions, measure your own)
network round trip, warm connection = 40 ms
app + one Redis read = 5 ms
render one frame at 60 Hz = 1000 / 60 = 16.7 ms
total = 61.7 ms
slack = 100 - 61.7 = 38.3 ms
What the user feels is measured from the LAST keystroke:
debounce 100 ms + 61.7 ms = 161.7 ms
debounce 50 ms + 61.7 ms = 111.7 ms
A shorter debounce feels faster but sends more requests. It is a dial, not a constant.The slack is small, and the debounce delay is not inside it, because it elapses before the request leaves the browser. That is the real design tension: every millisecond of server work competes with the debounce you wanted to save requests. It is also the argument for precomputation, since a single key lookup leaves room for both.
A trie stores strings by shared prefixes, so finding the node for a prefix costs time proportional to the prefix length, not the number of strings. Store the top ten suggestions on each node and a lookup is a walk plus a copy. The catch is that it lives in one process, so every instance needs the same build and a way to swap it. Compare it with the database-backed options.
| Approach | What it matches | Ranking | Main weakness |
|---|---|---|---|
| In-memory trie with top-K at each node | Exact prefix, cost grows with prefix length | Precomputed per node | Per-process memory; every instance needs the same build |
| Postgres B-tree with text_pattern_ops | Left-anchored LIKE such as ca% | ORDER BY score over every match | Short prefixes match huge row sets that must be sorted |
| Postgres pg_trgm with a GIN index | Anywhere in the string, plus typos via similarity | ORDER BY similarity, then score | Larger index; patterns with no extractable trigrams scan the whole index |
| Redis sorted set per prefix | Exact prefix key lookup | The score is the rank | An offline job must fill it; memory grows with prefix count |
| Redis ZRANGE BYLEX on one set | Left-anchored lexicographic range | Alphabetical only, not by popularity | Cannot rank, and all scores must be equal |
On one VPS I would begin in Postgres, because it is already running and a few hundred thousand queries fit comfortably. The PostgreSQL docs state that text_pattern_ops indexes support LIKE when the database is not in the C locale, and that pg_trgm indexes support LIKE, ILIKE and similarity searches that need not be left-anchored. Use the B-tree for plain prefixes and pg_trgm when you want typo tolerance.
-- Left-anchored prefix match on a B-tree. In a non-C locale the default operator
-- class cannot serve LIKE 'ca%', which is why text_pattern_ops exists.
CREATE INDEX popular_queries_prefix_idx ON popular_queries (q text_pattern_ops);
-- Works, but 'c%' matches a large share of the table, and ORDER BY score then
-- has to sort every match. This is why the production shape is precomputed.
SELECT q FROM popular_queries WHERE q LIKE 'ca%' ORDER BY score DESC LIMIT 10;
-- pg_trgm: typo tolerance and match-anywhere, at the price of a bigger index.
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX popular_queries_trgm_idx ON popular_queries USING gin (q gin_trgm_ops);
SELECT q
FROM popular_queries
WHERE q % 'cofee' -- similarity operator, uses the GIN index
ORDER BY similarity(q, 'cofee') DESC, score DESC
LIMIT 10;The scale step is to stop querying and start looking up. Redis documents ZRANGE with BYLEX for lexicographic ranges, but only for members that share one score, which returns alphabetical order. Popularity ranking needs the other shape: one sorted set per prefix whose score is the rank, written by an offline job and read with a single ZREVRANGE.
# Precomputed top-K per prefix: a sorted set whose score IS the rank.
ZADD sg:v43:ca 362.3 "cat food" 300 "car insurance" 250 "calendar app"
ZREVRANGE sg:v43:ca 0 9 # top 10, highest score first
ZREVRANGE sg:v43:ca 0 9 WITHSCORES # same, with the scores
# Lexicographic range works only when every member has the SAME score (use 0).
# It gives alphabetical order, not popularity, so it filters but cannot rank.
ZADD sg:lex 0 "cat food" 0 "car insurance" 0 "calendar app"
ZRANGE sg:lex "[ca" "[ca\xff" BYLEX LIMIT 0 10
# Publish a new build atomically: write sg:v44:* in the background, then flip.
SET sg:version 44Cap prefix length, for example at 8 characters. Beyond that point users are narrowing a list they already see, so reuse the 8-character list and filter it in the app. The key space then stays bounded no matter how long a query someone types.
Raw counts reward old giants: a query searched 1,000 times last month outranks one that is surging today. Weight each day's count by an exponential decay with a half-life you choose, and sum. The worked example uses a 7-day half-life and shows the order flipping.
score = sum over days of count(day) x 0.5 ^ (age_in_days / half_life)
half_life = 7 days (a choice: shorter reacts to trends faster, longer is steadier)
query A: 1,000 searches, all 14 days ago 1,000 x 0.5 ^ (14 / 7) = 1,000 x 0.25 = 250.0
query B: 400 searches, all 1 day ago 400 x 0.5 ^ (1 / 7) = 400 x 0.906 = 362.3
query C: 300 searches, all today 300 x 0.5 ^ 0 = 300.0
Raw count order: A (1,000), B (400), C (300)
Decayed order: B (362.3), C (300), A (250)The half-life is a product decision, not a constant. A short one makes trending topics surface fast and also lets a one-day spike displace steady favourites, while a long one is stable but slow. Add a minimum count before a query is eligible at all, which also removes one-off typos and rare personal queries.
Never rank on the request path. Log submitted searches, aggregate them into daily counts per normalised query, and run a nightly job that scores each query, expands it into prefixes and keeps the top ten per prefix. In Postgres the whole job is one statement using generate_series and row_number.
-- Nightly job. Input: daily_query_counts(day date, q text, cnt bigint),
-- itself an aggregate of the raw search log. Output: top 10 per prefix.
WITH scored AS (
SELECT lower(trim(q)) AS q,
sum(cnt * power(0.5, (current_date - day) / 7.0)) AS score
FROM daily_query_counts
WHERE day >= current_date - 28
GROUP BY 1
HAVING sum(cnt) >= 5 -- privacy and noise floor
),
prefixes AS (
SELECT left(s.q, n) AS prefix, s.q, s.score
FROM scored s, generate_series(1, 8) AS n
WHERE length(s.q) >= n -- prefixes capped at 8 characters
),
ranked AS (
SELECT prefix, q, score,
row_number() OVER (PARTITION BY prefix ORDER BY score DESC, q) AS rn
FROM prefixes
)
SELECT prefix, q, score FROM ranked WHERE rn <= 10;The output feeds the Redis sets under a new version number, and a single SET flips the version pointer once the build is complete, so readers never see a half-built index. A nightly cycle means suggestions lag by up to a day, which is acceptable for most products. If it is not, add a small online layer that increments scores for fresh queries and merge it later.
Query logs contain what people typed, including names, phone numbers and things they would not want suggested to a stranger. Normalise, enforce the minimum count shown above, filter with a blocklist before publishing, and set a retention period for the raw log. A suggestion shown to everyone is a publication, not an internal metric.
Make the endpoint a pure function of the prefix, so the answer is identical for every user. Then the URL itself is the cache key, and the browser, a CDN and Redis can all hold it. The handler below does one Redis read, bounds its input and sets a public Cache-Control header.
@Get("suggest")
async suggest(
@Query("q") raw: string,
@Res({ passthrough: true }) res: Response,
): Promise<string[]> {
const q = (raw ?? "").trim().toLowerCase();
if (q.length < 2 || q.length > 64) return []; // reject junk before any I/O
const version = (await this.redis.get("sg:version")) ?? "1";
const key = "sg:v" + version + ":" + q.slice(0, 8); // keys stop at 8 characters
const top = await this.redis.zrevrange(key, 0, 9);
// Past 8 characters we reuse the 8-character list and filter it. This can
// return fewer than 10 items; that is the price of a bounded key space.
const out = q.length > 8 ? top.filter((s) => s.startsWith(q)) : top;
// The URL is the cache key: /suggest?q=ca is identical for every user.
res.setHeader("Cache-Control", "public, max-age=300");
return out;
}Check the memory you are signing up for before building it. The arithmetic gives an upper bound, because real prefixes overlap heavily, and that bound fits a modest Redis instance. Measure a sample key rather than trusting the per-entry estimate.
Assumed: 2,000,000 retained queries, prefixes capped at 8 characters.
Upper bound on prefix keys = 2,000,000 x 8 = 16,000,000
(real count is lower: queries share prefixes, e.g. every "cat food" shares "c", "ca", "cat")
Value size = 10 suggestions x 25 B = 250 B, plus about 50 B overhead = 300 B
Upper bound = 16,000,000 x 300 B = 4.8 GB
Smaller option: only materialise prefixes that at least 2 retained queries share
beyond length 3, and serve the rest from the filtered 8-character list.
Check the real footprint with MEMORY USAGE on a sample key, then extrapolate.Treat the five-minute max-age as a freshness decision. Because the nightly job already makes data up to a day old, five minutes of extra staleness costs nothing the user can see, and it is what makes the 80 percent hit assumption plausible.
Debounce so a burst of keystrokes sends one request, and cancel so a slow response can never overwrite a newer one. AbortController is the standard way to cancel a fetch, and an effect cleanup is the natural place to call it. The hook below also keeps an in-memory map, so deleting a character and retyping it costs no request.
import { useEffect, useRef, useState } from "react";
const DEBOUNCE_MS = 100;
const MIN_CHARS = 2;
export function useSuggestions(input: string): string[] {
const [items, setItems] = useState<string[]>([]);
const memo = useRef(new Map<string, string[]>()); // same prefix twice = zero requests
useEffect(() => {
const q = input.trim().toLowerCase();
if (q.length < MIN_CHARS) {
setItems([]);
return;
}
const hit = memo.current.get(q);
if (hit) {
setItems(hit);
return;
}
const controller = new AbortController();
const timer = setTimeout(async () => {
try {
const res = await fetch("/api/suggest?q=" + encodeURIComponent(q), {
signal: controller.signal,
});
if (!res.ok) return;
const data: string[] = await res.json();
memo.current.set(q, data);
setItems(data);
} catch (err) {
if ((err as Error).name !== "AbortError") setItems([]);
}
}, DEBOUNCE_MS);
// Runs on the next keystroke: drop the pending timer AND cancel the
// in-flight request, so a slow answer for "ca" can never overwrite "cat".
return () => {
clearTimeout(timer);
controller.abort();
};
}, [input]);
return items;
}Cancelling only stops the browser waiting; the server may still finish the work, which is cheap here because the answer is one cached lookup. The 100 ms delay is a tunable from the latency budget, not a rule, so choose it against how fast your users actually type.
Pick the lightest design that survives your numbers, and move up only when a measurement forces you to. Answer these in order.
Whichever you choose, write down the assumptions behind the capacity block and revisit them when real traffic arrives. The arithmetic is the part you can check, and a wrong assumption is cheap to correct while it is still on paper.
Autocomplete is a read-heavy lookup disguised as a search problem. Do the expensive ranking offline, key the result by prefix, cache it publicly, and make the client send as few requests as it can. Start with the database you already run, and let measured load, not fashion, move you to tries or Redis.
Sources and further reading