Design search autocomplete

System design Mid-level Python 3.13+ PostgreSQL 17+ Reviewed By Best Latest Apps

Pick the fix

Each keystroke runs SELECT ... WHERE q LIKE 'ab%' ORDER BY count DESC LIMIT 5 on Postgres, and p99 is 400 ms. Best direction?

Options
Hint 1 of 1

What can be computed ahead of time?

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A Precompute top-5 per prefix and serve from memory or Redis

Correct. One lookup per keystroke.

The suggestions for a prefix change slowly, so compute them ahead of time. Each keystroke then becomes one key lookup in memory instead of a LIKE scan and sort on the database.

Why not the others?
  • B Add more Postgres replicas only. Still a sort per keystroke.
  • C Remove the LIMIT. Returns more rows, slower.
  • D Send a request every 10 ms. More load.

30-second answer

Precompute the top suggestions for every prefix from query logs (a trie or a prefix → top-k table), rebuilt by a batch or streaming job, and serve them from memory or Redis so each keystroke is a single lookup in a few milliseconds. Clients debounce keystrokes and cache recent prefixes; the CDN can cache popular short prefixes. Filter offensive terms and personalise lightly by merging a user's recent searches on the client or at the edge.

Practise saying it · 35 s. No recording, just a timer

Design autocomplete.

Say your answer out loud, then check which of these points you covered:

  • Top-k per prefix, precomputed
  • Serve from memory
  • Debounce + client cache
  • Batch or streaming rebuild
  • Filter terms

Deep dive

Top-k per prefix makes reads O(1) at the cost of storage.

Shard by prefix; hot short prefixes may need replicas.

Search engines like OpenSearch offer completion suggesters.

Measure keystroke-to-suggestion latency on real devices.

Common mistakes

  • Running a LIKE 'abc%' query per keystroke on the main database.
  • No debouncing on the client.
  • Rebuilding the whole index synchronously.

Senior take & follow-ups

Precomputed top-k per prefix, in-memory serving, client debounce and caching, update pipeline.

Follow-up questions

Think of your answer first, then open the hint.

  1. How fresh must suggestions be?

    Show hint

    Usually hours; trending topics may need a streaming path.

  2. Why debounce?

    Show hint

    Fewer requests without hurting perceived speed.

Related questions

Suggest a fix if something here is wrong or out of date.