Indexing in vector databases
Without an index, finding the nearest vector means comparing the query against every stored vector — linear in the corpus and hopeless past a few hundred thousand. An index organises the vectors so most of them are never examined, and pays for that with recall: it may miss a true neighbour.
Overview
Why exact search stops working
A flat index stores the vectors and compares the query with every one. It is exact, trivially correct, and the right answer for small collections — and the cost is O(n·d) per query, so a million 768-dimensional vectors is around 768 million multiply-adds for a single search.
It is also the ground truth. To measure any approximate index's recall you need the true neighbours, and a flat search over a sample is how you get them.
Parameters
Visualisation
—Readout
What to watch
- Exact search touches every vector; the cost is linear in the corpus.
- An index skips most of them, and can miss a true neighbour.
- Recall, latency and memory — pick two.
Indexing in vector databases: A Practical Guide
What does a vector database index actually do, and why can't it just compare every vector?
What an index buys and what it costs
Every approximate index prunes: it organises vectors so that most can be skipped without being compared. That turns a linear scan into something closer to logarithmic, and introduces the possibility of missing a genuine neighbour because the structure routed the search elsewhere.
So the metric is recall@k: of the k true nearest neighbours, how many did the index return? 0.95 is typical and usually fine for RAG, where a reranker sees the top 50 anyway. It is not fine for deduplication or exact matching.
The families, briefly
IVF clusters the vectors and searches only the nearest few clusters. Cheap to build, and it misses neighbours that sit just across a cluster boundary.
HNSW builds a navigable small-world graph and walks it greedily. Best recall-for-latency, and the highest memory — it stores the graph as well as the vectors. This is the default in most vector databases; see ANN indexing.
Product quantization compresses each vector into a short code, cutting memory by an order of magnitude at some cost to recall. Usually combined with IVF rather than used alone.
Also note what an index does not do: filtering by metadata is a separate problem, and combining it with vector search is where most vector databases differ from each other — see permission filtering.
Measuring recall, which needs a ground truth
An approximate index is a lossy structure, so "is it working?" is a measurement rather than an assumption. The measurement needs the true answers, which means a flat exact search over a sample — typically a few hundred held-out queries, run once, stored.
Then recall@k is the overlap between what the index returned and what the exact search returned. Track it as a deployment check: an index rebuilt with different parameters, or a library upgraded, can quietly lose recall while every latency dashboard stays green.
What counts as good depends on what sits downstream. For RAG feeding a reranker that sees the top 50, 0.9 is comfortable — a missed neighbour at rank 40 changes nothing. For deduplication, near-duplicate detection or anything where a miss is a correctness bug rather than a quality one, approximate search is the wrong tool and a flat index over a filtered subset is usually fast enough.
Filtering, updates and the parts that are not the ANN algorithm
Two problems decide most real vector-database choices, and neither is about nearest-neighbour search.
Metadata filtering. Restricting to a tenant, a date range or a permission set fights the index, because the graph or the clustering was built over everything. Pre-filtering can disconnect a graph traversal; post-filtering silently returns fewer results. How a database handles this is the main thing that distinguishes them — see permission filtering.
Updates and deletes. HNSW does not delete gracefully: removing a node can disconnect the graph, so implementations tombstone and rebuild periodically. If your corpus changes hourly, the rebuild cost may matter more than query latency, and IVF's cheaper updates start to look attractive despite worse recall-for-latency.
Benchmarks almost always measure static-corpus query performance, which is the easy half.
What a vector database stores
Three things per record, and all three matter:
The vector — the embedding, typically 384 to 1,536 floats.
The payload — the text itself, or a reference to it, so the retrieved chunk can be put in a prompt.
The metadata — source, date, document type, permissions, heading path. This is what makes filtering possible, and it must be populated at indexing time; adding a field later means re-indexing.
The index is the structure built over the vectors so that a nearest-neighbour query does not have to compare against all of them. Everything else the database provides — persistence, filtering, updates, replication — is why you use one rather than a NumPy array.
The indexing pipeline
for doc in documents:
chunks = chunk(doc) # 1. split
vecs = model.encode([c.text for c in chunks], # 2. embed, batched
normalize_embeddings=True, batch_size=64)
store.upsert([ # 3. write
{"id": c.id, "vector": v, "payload": {"text": c.text,
"source": doc.id,
"heading": c.heading,
"acl": doc.acl,
"updated": doc.updated}}
for c, v in zip(chunks, vecs)
])Four things in that snippet are the ones that go wrong in practice.
Batch the embedding calls. One call per chunk is dominated by overhead; batches of 32–128 are several times faster.
Normalise once, here. Then every query is a dot product rather than a cosine computation.
Use deterministic ids derived from the source and chunk position, so re-indexing a changed document replaces its chunks rather than duplicating them.
Upsert, not insert. Re-running the pipeline should be idempotent, and it will be run again.
Keeping the index fresh
Documents change, and a stale index is a correctness problem rather than a performance one — a retrieved chunk from a superseded policy will be used confidently.
Three strategies:
Full rebuild. Re-index everything on a schedule. Simple, and it wastes work and leaves a window where the index is being rebuilt.
Incremental upsert. Track a content hash per document; re-embed only what changed. This is what most systems should do.
Change-data capture. Subscribe to source-system events and update on write. Lowest latency, most integration work.
The detail that catches people: deletions. When a document is removed, its chunks must be removed too. Most indexes handle deletes with tombstones, so space and quality degrade until a compaction or rebuild. Plan for periodic rebuilds even with incremental updates.
Also plan for re-embedding. Changing the embedding model invalidates the entire index, because vectors from different models are not comparable. Record which model produced the index, and treat a model upgrade as a full rebuild — ideally into a new collection, with an atomic switch.
What is stored, and what happens when it changes
The ANN algorithm gets the attention, and the operational half decides whether a system survives contact with a corpus that changes. This works through what a record actually holds, what an update costs, and the staleness that follows from the answer.
Things to try
- Set clusters probed to 1. Recall collapses — most true neighbours live in clusters the search never opened.
- Raise probes until recall reaches 1.0. You are now comparing against the whole corpus: an exact search with extra steps.
- Raise clusters with probes fixed. Finer clusters mean fewer comparisons and lower recall — the same trade from the other direction.
What to remember
Without an index, finding the nearest vector means comparing against every stored vector. An index prunes most of them and pays for it in recall, so the metric is recall@k measured against an exact search. Recall, latency and memory are the three knobs, and every index type exposes them under different names.
Filtering, and the interaction that surprises people
Real queries carry constraints: only this user's documents, only from the last year, only policies.
Two ways to apply them:
Pre-filter — restrict the candidate set, then search within it. Correct, and it can defeat the index structure, because the graph or clusters were built over everything.
Post-filter — search, then discard non-matching results. Fast, and it can return fewer than k results, or none, when the top matches are all filtered away.
Modern vector databases implement filtered search that navigates the index while respecting the predicate, which is the right answer and why using a real database beats a raw index library once filtering matters.
For permissions specifically, the filter must be applied inside the search, server-side. Retrieving first and filtering in the application means documents the user cannot see have already influenced which results came back — and in the worst case, their content has already crossed a trust boundary.
Choosing a store
| Store | Character |
|---|---|
| FAISS | A library, not a service — fast, in-process, no persistence layer |
| Qdrant | Rust, strong filtering, good defaults |
| Weaviate | Built-in hybrid search and modules |
| Milvus | Built for very large scale, more operational weight |
| pgvector | Postgres extension — one database for everything |
| Pinecone / hosted | Managed, no operations, per-vector pricing |
| Elasticsearch / OpenSearch | Strong BM25 plus vector support — hybrid in one system |
Two observations that save a lot of unnecessary infrastructure.
Below about 100,000 vectors, you may not need any of these. A NumPy array plus a dot product is exact and fast, and a million-vector brute-force search takes tens of milliseconds with a good BLAS.
pgvector is often the right answer for a system that already uses Postgres. One database to operate, transactional consistency with the rest of the data, and SQL for the filtering. It is slower than a dedicated store at very large scale, and that scale is further away than most projects reach.
Operational details worth deciding up front
Collection layout. One collection per tenant isolates cleanly and multiplies index overhead; one collection with a tenant field in the metadata scales better and relies on filtering being correct.
Backups. The index is derivable from the documents, so the question is whether re-indexing is acceptable as recovery. For a large corpus that may be hours, which argues for snapshotting.
Monitoring. Track query latency percentiles, recall against a periodic exact-search sample, index size, and the age of the oldest un-refreshed document.
Cost. Memory-resident indexes are priced by vector count and dimension. Reducing dimensions from 1,536 to 384 is a fourfold saving and often a small accuracy cost — some models support truncating dimensions deliberately.
Questions people ask
Do I need a vector database? Below 100k vectors, no. Above that, yes — as much for filtering, persistence and updates as for the index.
How do I handle document updates? Deterministic ids plus upsert, driven by a content hash. And plan periodic rebuilds to clean up deletions.
What happens if I change embedding models? The whole index must be rebuilt. Version it and switch atomically.
Should the text live in the vector store? Convenient, and for large documents a reference to a document store is cleaner. Either way the retrieved text must be reachable.
How do I enforce permissions? Filter inside the search, server-side, on metadata written at indexing time. Never filter after retrieval.
Can I store several vectors per document? Yes, and it is common — one per chunk, or several representations (dense, sparse, per-language) per chunk.
Recap in one screen
- Store the vector, the text and the metadata — and populate metadata at indexing time, because adding it later means re-indexing.
- Batch the embedding calls, normalise once, use deterministic ids, and upsert.
- Update incrementally by content hash, and rebuild periodically to reclaim deleted space.
- Filtering must happen inside the search for permissions to be enforced correctly.
- Below 100k vectors a plain array is enough; pgvector is often the pragmatic choice above that.