Why is a database LIKE query too slow for autocomplete at peak?

It collects and sorts all matches on every key press, tens of thousands of times a second

Databases cannot match prefixes

It collects and sorts all matches on every key press, tens of thousands of times a second

What does each node of the prefix tree save, to make answers fast?

The top few most popular names under it, already sorted

The full list of every matching name

The top few most popular names under it, already sorted

What does debouncing do?

Waits for a short pause in typing before asking, so fewer requests are sent

Removes duplicate names from results

Waits for a short pause in typing before asking, so fewer requests are sent

How should a new version of the prefix index go live?

Build it on the side, then switch every server to it at once

Edit the live index name by name

Build it on the side, then switch every server to it at once

Delete the old index first, then build

Design Search Autocomplete

By the Syncfusion DevTutorials team · Last updated October 20, 2026

Suggest dishes as customers type: prefix trees with saved top answers, debouncing, caching popular prefixes and rebuilding rankings from logs.

Type "bir" into QuickBite's search box and you expect "Biryani", "Biryani House" and "Bisi Bele Bath" to appear before you type the next letter. That is search autocomplete, also called typeahead.

It looks like a small feature, but it is one of the busiest parts of the app. Every key press can create a request, and each answer must arrive faster than a person types, about 50 ms. A normal database search is usually too slow for that.

The main idea: prepare autocomplete suggestions ahead of time, keep them in memory, and send far fewer requests than there are key presses.

What You Will Learn

In this case study, you will:

Write the requirements for autocomplete.
Estimate requests per second and see why typing creates so many requests.
Store names in a prefix tree, with the top answers saved at each step.
Reduce requests with debouncing and a cache for popular prefixes.
Keep suggestions fresh using search logs in the background.
Build the design on the canvas and test it at dinner time.

This builds on Lesson 2 (Estimation), Lesson 5 (Caching), Lesson 6 (Indexes) and Lesson 9 (Queues and Background Work).

Step 1: Requirements

What It Must Do (Functional)

Suggest the top 5 dishes and restaurants that start with what the customer typed.
Rank by popularity: the most-ordered match comes first.
Stay current: a new restaurant or a dish that becomes popular appears within a day.

How Well It Must Do It (Non-Functional)

Very fast: p99 under 50 ms, or the suggestions lag behind typing.
Always available: if suggestions fail, search still works; it just feels worse.
Busy: many requests per search, especially during the dinner peak.

Out of Scope

Spelling correction ("biriyani" → "biryani") and personalised ranking. Both can be added on top of the same design later.

Step 2: Estimate

One search can create many requests because people type one letter at a time.

Measure	Per second
Searches	1,000
Requests if every key asks ("biryani" is 7 letters)	7,000

At the real dinner peak, people type, delete and retype. Because of this, QuickBite sees about 30,000 autocomplete requests a second.

The actual searches themselves are only about 1,000 a second.

QuickBite has about 2 million dish and restaurant names, about 18 characters each. With roughly 10 times extra for tree pointers and saved top-5 lists, the prefix index needs about 0.36 GB of memory.

That is less than half a gigabyte.

Every suggest server can hold the entire index in memory, making lookups extremely fast.

Step 3: Why Not Just Query the Database?

SELECT name FROM dishes WHERE name LIKE 'bir%' ORDER BY orders DESC LIMIT 5 works, and an index on name helps find the matches.

But for every request, the database still has to:

Find all matching names.
Sort them by popularity.
Keep only the top 5 results.

Doing that for a few users is fine.

Doing that 30,000 times a second quickly overloads the database.

In the sandbox, the database runs out of capacity long before that.

Step 4: A Prefix Tree With Saved Answers

A prefix tree (also called a trie) stores names letter by letter.

Each step down the tree adds one letter.

All names starting with "bi" sit under the "bi" node.

The idea that makes it fast is simple:

Save the top 5 answers at every node ahead of time.

When someone searches for "bi", the system:

Walks down two letters.
Finds the matching node.
Returns the saved answers.

No searching.

No sorting.

The best answers are already waiting. Step through a tiny tree that keeps the top 3 at each node:

Here is the same idea in code:

Build a tiny prefix tree with a saved top list at each node

const dishes = [
  ["biryani", 950], ["burger", 900], ["bisi bele bath", 300],
  ["biryani house", 700], ["butter chicken", 850], ["bun maska", 120],
];

const root = { top: [], kids: {} };
for (const [name, orders] of dishes) {
  let node = root;
  for (const ch of name) {
    node.kids[ch] ??= { top: [], kids: {} };
    node = node.kids[ch];
    node.top.push([name, orders]);
    node.top.sort((a, b) => b[1] - a[1]);
    node.top = node.top.slice(0, 3); // keep the best 3 for this example
  }
}

function suggest(prefix) {
  let node = root;
  for (const ch of prefix) node = node?.kids[ch];
  return node ? node.top.map(([n]) => n).join(", ") : "(none)";
}

console.log(`b   -> ${suggest("b")}`);
console.log(`bi  -> ${suggest("bi")}`);
console.log(`bu  -> ${suggest("bu")}`);

Expected output:

b   -> biryani, burger, butter chicken
bi  -> biryani, biryani house, bisi bele bath
bu  -> burger, butter chicken, bun maska

Building the tree is slow, but it happens only once a day or once an hour in the background.

Answering a request takes only a few steps.

Step 5: Send Fewer Requests

Debounce on the Phone

Most people type several letters very quickly.

If the app sends a request after every key press, many of those requests become unnecessary because another key is pressed almost immediately.

Debouncing means waiting for a short pause before sending the request.

A common value is about 150 ms.

Step through one customer typing "biryani" with a pause in the middle:

Here is the same idea in code:

Debounce: only ask after a 150 ms pause

const keyTimes = [0, 90, 170, 260, 340, 900, 980]; // ms when each key was pressed
const pause = 150;

let requests = 0;
for (let i = 0; i < keyTimes.length; i++) {
  const next = keyTimes[i + 1];
  if (next === undefined || next - keyTimes[i] >= pause) requests++;
}
console.log(`Keys: ${keyTimes.length}, requests with debounce: ${requests}`);

Expected output:

Keys: 7, requests with debounce: 2

Seven key presses become only two requests.

Across all users, QuickBite measured that debouncing reduces traffic from about 30,000 requests a second to roughly 12,000 requests a second.

Cache the Popular Prefixes

Some prefixes appear much more often than others.

Examples:

Many users search for these prefixes every day.

Since the answers are usually the same, they are perfect candidates for caching.

A cache in front of the prefix index can answer most requests in about a millisecond.

The chart compares how many requests still reach the prefix index at different cache hit ratios.

Only cache misses reach the index. A 90% hit ratio cuts 12,000 requests a second down to 1,200.

Short prefixes are the busiest and the easiest to cache. Thousands of users search for "b" or "bi", but very few search for "biryani hou", so even a small cache removes a huge amount of traffic.

Step 6: Keeping Suggestions Fresh

Suggestions should change as customer behaviour changes.

The rankings come from what people search for and what they order.

Every completed search is recorded.

These logs help QuickBite understand:

what customers search for;
which dishes are becoming popular;
which restaurants are trending.

Writing logs should not slow down autocomplete requests.

So suggest servers place log events into a queue, and log workers write them to the database.

Once a day (or once an hour), a background job:

Reads the logs.
Calculates popularity.
Rebuilds the prefix tree.
Creates new top lists.

The suggest servers then load the new tree. Step through the whole loop:

Never rebuild the tree on the live servers. Build the new tree separately, then switch to it in one step, so customers never see incomplete or wrong suggestions.

Step 7: Build It on the Canvas and Test It

Open the design sandbox.

The canvas starts with Phones sending a request on every keystroke, 2 load balancers, 3 suggest servers and a database.

Select Phones and enable debouncing.

Check	Passes when
Peak load	p99 at most 50 ms, under 0.1% errors
Lose any one machine	Any one load balancer, suggest server, cache node, index server or database copy dies. Errors under 1%, p99 under 150 ms
Cost	At most $1,600 a month
Requirements	Search logs go through a queue to log workers, which write to the database

Make QuickBite's search suggestions keep up with typing

Run the starting design first and watch the database.

Then add:

A prefix index
A cache
Debouncing

one at a time.

What you will probably find:

Database queries for every prefix overload the database and most requests fail.
Without debouncing, request volume stays too high and costs increase.
One cache node or one index server works until it fails, then the remaining servers become overloaded.
A design that passes: Phones with debounce, 2 load balancers, 3 suggest servers, 2 cache nodes, 2 prefix index servers, a queue, a log worker and 2 database copies. It costs $1,600 a month, and p99 is about 8 ms.

Common Mistakes

Mistake	Wrong	Correct	Why it happens
Querying the database	A LIKE query on every key press.	A prefix tree with saved top answers, in memory.	The query is correct and fast with test data.
A request per key	The app asks after every letter.	Debounce for about 150 ms.	It is the simplest code to write.
Sorting at request time	Find all matches, then sort them.	Store each node's top list ahead of time.	It feels wasteful to precompute answers nobody may ask for.
Logging inline	The suggest request writes the search log.	A queue and log workers.	One extra database write looks cheap.
Updating in place	Changing the live index name by name.	Build a new index, then switch at once.	It avoids holding two copies in memory for a moment.

Practice

What to Remember

Autocomplete is very busy and very fast.
One search can create many requests because users type one letter at a time.
Use a prefix tree (trie) in memory.
Save the top answers at every node.
Debounce on the phone to reduce unnecessary requests.
Cache popular prefixes to reduce load even further.
Collect search logs through a queue.
Rebuild the autocomplete index in the background.
Switch to a new index all at once.