How Does a Vector Database Work? – Indexes, Search, and Filters
A mechanical walkthrough: how ANN indexes are built, how a query traverses them, how filters interact with search, and what recall tuning costs.
A vector database answers one question quickly: which stored vectors are nearest this one. Everything in its design follows from making that search sublinear while keeping accuracy acceptable.
1. The Problem With Exact Search
Comparing a query against every stored vector is exact and linear. A million vectors of a thousand dimensions is a billion multiplications per query — fine for a script, impossible for an interactive service at scale.
Approximate nearest-neighbour indexes trade a small amount of accuracy for a large amount of speed.
2. Graph-Based Indexes
The most common family builds a navigable graph where each vector links to some near neighbours, across several layers of decreasing sparsity.
A search enters at the top layer, greedily walks toward vectors closer to the query, then descends and repeats. Only a small fraction of the collection is ever examined.
- Build cost is high — neighbours must be selected for every insertion.
- Memory is substantial, since the graph is held alongside the vectors.
- Accuracy is excellent, and tunable at query time by widening the search frontier.
3. Cluster-Based Indexes
An alternative partitions the space into clusters. A query is compared against cluster centroids, then searched only within the nearest few.
Cheaper to build and more compact, at the cost of missing neighbours that sit just across a cluster boundary. Scanning more clusters per query recovers accuracy and costs time.
4. Quantisation
Vectors can be compressed into approximate codes, dramatically reducing memory at some loss of precision. It is frequently combined with the above: quantised vectors for the broad search, full-precision vectors for a re-scoring pass over the top candidates.
5. Filters Are the Hard Part
Real queries constrain by metadata — tenant, date, language, source. Where the filter is applied changes the result:
| Approach | Behaviour | Risk |
|---|---|---|
| Filter after search | Search normally, discard non-matching | A selective filter can leave almost nothing |
| Filter during traversal | Skip non-matching nodes while walking | Harder to implement; keeps recall stable |
| Filter first | Search only a pre-filtered subset | Efficient when the subset is small |
If a system must answer "nearest passages, but only from this tenant", check which strategy it uses before trusting its results.
6. Recall Is a Dial
Approximate means some true neighbours are missed. Every implementation exposes a knob — search frontier width, number of clusters probed — trading recall against latency.
Measure it: embed a query set, compute exact nearest neighbours by brute force on a sample, and compare. Without that measurement, recall is an assumption.
7. What Else the Store Holds
Alongside vectors it keeps the source text, needed for the model to read, and metadata, needed for filtering and citation. Updates and deletions are handled variably — some indexes rebuild segments rather than mutating in place, which matters for corpora that change often.
8. Summary
A vector database builds an approximate index — usually a navigable graph or a cluster partition, often with quantisation — so nearest-neighbour search examines a fraction of the collection.
Recall is a tunable rather than a guarantee, and filtering strategy is the design detail that most affects real-world results. Measure recall on your own data before treating retrieval as solved.