Search, indexing and autocomplete

Inverted indexes, analysis and ranking, prefix search with tries, filtering by permissions, index freshness, and when vector search actually belongs in the answer.

Search shows up as a sub-problem in half of all system design questions: messages, products, places, documents, users. You rarely have to design a search engine, but you do have to say how documents get into an index, how the index is sharded, how results are ranked and filtered, and how fresh they are.

The inverted index

A forward index maps document → terms. Search needs the opposite: term → the list of documents that contain it, with positions and frequencies.

"payment" → [ (doc 12, tf 3, pos 4,19,55), (doc 88, tf 1, pos 2), … ]
"failed"  → [ (doc 12, tf 1, pos 5), (doc 91, tf 2, pos 7,31), … ]

A query intersects the posting lists (AND) or unions them (OR), then scores what survives. Posting lists are sorted by document id and compressed; skip pointers let the intersection jump ahead instead of walking every entry.

Analysis is the step before indexing: lower-casing, tokenising, removing stop words, stemming ("payments" → "payment"), and sometimes n-grams for substring matching. The same analyser must run at query time, and changing it means reindexing — a fact interviewers like to probe.

Getting documents into the index

Indexing is asynchronous in every real system: the write path publishes an event, a consumer transforms the record into a document and writes it to the index.

• Freshness is a requirement, not an accident. State it: "a new message is searchable within a second, a product catalogue change within a minute."
• Near-real-time engines buffer writes in memory and refresh into a searchable segment on a short interval; that refresh is what the freshness number really describes.
• Segments are immutable and merged in the background. Deletes are tombstones until a merge; this is why a deleted document can still be counted in totals for a while.
• Always keep the ability to rebuild the index from the source of truth. Indexes are derived data; they will be corrupted at some point and a rebuild path is the answer.

Sharding and replication

Two ways to split an index, and you should know both:

Document partitioning wins almost everywhere. The coordinator fans a query out to every shard, each returns its top k, and the coordinator merges to a global top k. That fan-out is why tail latency is governed by the slowest shard, which is the argument for hedged requests and for keeping shard counts sane.

Replicas serve reads and give you capacity; with document partitioning you can also add replicas to cut tail latency by querying the faster copy.

Ranking

State that ranking runs in stages, because one-stage ranking never survives the follow-up:

1. Retrieval — cheap boolean matching plus a cheap score (BM25, a tuned tf-idf) to get a few thousand candidates per shard.
2. Re-ranking — an expensive model over the few hundred survivors, using features that are costly to compute: recency, popularity, personalisation, click-through history.

BM25 is the honest default to name for text relevance. Then mention the non-text signals that usually matter more in product search: recency, in-stock, geographic distance, and the user's own history.

Filtering and permissions

The hard part of enterprise-ish search is not relevance, it is that a user must never see a document they cannot access. Two approaches:

• Filter inside the index: store the ACL (channel ids, team ids, visibility) as index fields and add them to every query. Fast, correct, but a permission change requires reindexing the affected documents.
• Filter after retrieval: fetch more than you need and drop what the user cannot see. Simple, but pagination becomes wrong and a user with access to little pays a lot of retrieval.

Index-side filtering is the right default; say how permission changes propagate.

Autocomplete and prefix search

Autocomplete is a different problem from search: 10–50 ms budget, a query per keystroke, and a small result set.

• A trie (prefix tree) with the top k completions precomputed at every node turns a keystroke into a pointer walk. Memory is the cost, so the trie usually lives in memory on dedicated servers, sharded by prefix.
• Alternatively, index edge n-grams ("sys", "syst", "syste") as terms, which reuses the search engine at the cost of index size.
• Debounce on the client (about 100 ms), cache aggressively — the head of the distribution is tiny and hot — and bias results by the user's language, location and history.
• Rebuild the completion set from query logs on a schedule; spelling correction is a separate, cheaper path (edit distance on a dictionary, or a "did you mean" from the logs).

Vector search, honestly

Embedding search (ANN over dense vectors with HNSW or IVF) answers "semantically similar" rather than "contains these words". Use it for recommendations, near-duplicate detection, and retrieval for an LLM. Real systems run it alongside keyword search and fuse the two result lists, because vectors are bad at exact matching — product codes, names and quoted phrases.

Say the operational facts: the index lives in memory, recall is a tuning parameter and not a guarantee, and re-embedding the corpus is the cost of changing models.

Numbers

• An inverted index is roughly 20–40% of the size of the text it indexes; with positions and stored fields, budget 50%.
• A shard of 10–50 GB is a comfortable operational size; plan shard count from total size, not from document count.
• Query latency budget: 100–300 ms for full search, 10–50 ms for autocomplete.

Common mistakes

• Making search synchronous with the write, so a search outage blocks writes.
• Forgetting the reindex path, or having no way to rebuild without downtime (use an alias that flips between index versions).
• Paginating deeply: from=10000 makes every shard sort ten thousand results. Use search-after with a stable sort key.
• Ignoring ACLs until the follow-up question.
• Reaching for vector search when the requirement is "find the product with this exact SKU".

Checklist

• How documents reach the index, and the freshness target.
• Partitioning scheme, shard size and fan-out cost.
• Retrieval and re-ranking stages, with the signals in each.
• Permission filtering.
• Rebuild and alias-swap strategy.
• Autocomplete path, if the product has a search box people type into.