AI & LLM systems
Vector search - nearest neighbours, approximately
Why similarity search uses an approximate index that trades recall for speed, and how filters break it.
What this board gets wrong on purpose
The tension
MID-SELECTIVITY FILTERS ARE NOT SOLVED HERE. The planner brute-forces filters that match under 0.1 percent of a shard and post-filters ones that match over 20 percent, and in between it searches the IVF index while skipping non-matching vectors - which, for a filter matching 2 percent of vectors clustered in a few lists, returns three results instead of ten or ten wrong ones, at full latency. Nothing alerts on it because recall is measured on a 1-in-1,000 sample of unfiltered-looking traffic. The second unresolved thing is DRIFT: the IVF centroids were trained on last quarter's data, new content lands in a few overfull lists, and both latency and recall degrade gradually until somebody schedules a full re-train and rebuild of 1 billion vectors. And deletes are tombstones, so a collection with heavy churn searches through dead vectors until compaction runs.
Practise this as an interview
Take Vector search - nearest neighbours, approximately as a timed system design interview on a blank board - on your own, with the requirements to check yourself against, or with a candidate you invite.
Start here
Why this design
Every retrieval-augmented chatbot, semantic search box, "more like this" rail and duplicate detector sits on a vector index, and "design a vector database" has become a standard deep system design question. It is a good one because the naive answer - store the vectors, compute distances - is correct and useless, and the real answer is a set of trade-offs with numbers on them: memory against recall, recall against latency, freshness against index quality, and filters against all three. Interviewers want to hear "approximate", then "recall@k", then which index and why it fits, then what a WHERE clause does to it.
What you will learn
- Why exact kNN over 1 billion x 768 dimensions is 3 TB scanned per query, and what recall@10 = 0.95 actually promises.
- How HNSW (a layered navigable graph) and IVF-PQ (k-means clusters plus product-quantised codes) work, and why 96-byte codes plus NVMe rescoring beats 3.3 TB of RAM here.
- How nprobe, ef_search and the rescore depth move you along the recall/latency curve.
- Why filters break ANN, and how a planner chooses between brute force, filtered search and post-filtering from selectivity.
- Why writes are an LSM: a mutable HNSW segment, sealed immutable IVF-PQ segments, tombstones and compaction.
- Why scatter-gather over 16 shards makes p99 a tail-of-tails problem, and why hedged requests fix it.
- Why recall must be sampled continuously against exact search, or nobody knows it has dropped.
How to read this board
- Press Play: ASK, PLAN, SEARCH (one shard of sixteen drawn), and the MEASURE box that is the only thing that knows if the answers are right.
- Then the bottom row, WRITE: log, mutable segment, seal, build, publish, compact.
- 1 · Requirements, 2 · Capacity, 3 · Storage, 4 · Availability, 5 · How it works, 6 · Deployment.
- Then the DATA MODEL - the control plane that knows which segments, built with which centroids, make up each shard.
1 · Requirements
Ask these before drawing anything
- How many vectors, how many dimensions, and how fast does the set grow? 1 billion, 768-d, 10,000 upserts a second here. At 1 million vectors a flat scan in one process is fine and none of this board is needed.
- Which distance? Cosine, dot product or L2. Normalise at write time and cosine becomes dot product, which every index handles best.
- What recall is acceptable, and is anyone measuring it? 0.95 recall@10 is a common target. A team that cannot state its recall has an index whose quality is unknown.
- What filters, and how selective? Tenant, language, date, access group. "Most queries filter to one tenant, and the largest tenant is 8 percent of the data" changes the design more than any other answer.
- How fresh must a write be? Searchable in a second (mutable segment) or in an hour (batch build)? The cost difference is a whole layer.
- Do deletes have to be immediate? For a right-to-erasure request, yes - which is why tombstones are checked at query time rather than waiting for compaction.
Functional
- Upsert and delete vectors with an external id, a tenant and attributes; searchable within 2 seconds.
- Query: top-k (k <= 100) nearest by cosine, with an optional filter expression over attributes, returning ids, scores and attributes.
- Per-collection configuration of dimensions, metric and index parameters; one embedding model per collection.
- Online rebuilds: re-train centroids and rebuild all segments without stopping queries.
Non-functional
- 5,000 queries per second; p50 15 ms, p99 50 ms inside the service.
- recall@10 >= 0.95 on unfiltered queries and >= 0.90 on filtered ones, measured on sampled live traffic against exact search.
- No acknowledged write lost (it is in the log before the ack). Deleted vectors never returned after the delete is acknowledged.
- Losing a node degrades latency, never correctness: every shard has two replicas.
Out of scope
- Producing the embeddings - the caller does, or the query API calls a model for text queries.
- Hybrid lexical search (BM25) - often fused with this, but a separate index.
- Cross-collection joins. A vector index is not a database and should not pretend to be one.
The rest of this board
Available on Tier Slate
This page publishes the question. The answer — 5 more written pages, a 9-step narrated walkthrough and a 6-table schema — is the board itself, and it opens in Tierslate.
- 5written pages
- 9walkthrough steps
- 6tables47 columns
5 pages behind this one
- Capacity estimation
- Storage estimation
- Availability
- How it works
- Deployment plan
More boards
Retrieval, model serving and the GPU that sets the bill.