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 each 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 times-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.
An index trades exact answers for speed. It organises vectors into a structure — clusters, graphs, trees or compressed codes —. That way, most vectors can be skipped without being compared. The result is approximate nearest-neighbour (ANN) search: faster by orders of size. But with a small chance of missing a genuine neighbour.
The three main families are IVF (inverted file), HNSW (hierarchical navigable small-world graph) and product quantisation. IVF clusters the vectors and searches only the nearest clusters. This trades recall at cluster edges for speed. HNSW builds a layered graph and walks it greedily toward the query — best recall-for-latency, highest memory. Product quantisation compresses each vector into a short code. This cuts memory sharply at some recall cost, and is often combined with IVF.
The metric that matters is recall@k: of the k true nearest neighbours, how many did the index really return? For RAG, 0.95 is often fine because a reranker will re-score the top results anyway. For deduplication or exact matching, a thing less than 1.0 is a data grade problem.
Choosing an index means choosing where on the recall-latency-memory triangle you want to sit. HNSW gives the best recall for a given latency but uses the most memory. IVF-PQ uses the least memory but has lower recall. IVF-flat sits in the middle. The right choice depends on your corpus size, your hardware budget and how much recall loss your use can tolerate.
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.
In this guide
- Why exact search stops working
- What an index buys and what it costs
- The families, briefly
- Gauging recall, which needs a ground truth
- Sifting, updates and the parts that are not the ANN algorithm
- What a vector store stores
- The indexing pipeline
- Keeping the index fresh
- What is stored, and what happens when it changes
- Things to try with Indexing in vector databases
- What to recall
- Sifting, and the link that surprises people
- Choosing a store
- Operational details worth deciding up front
- Questions people ask about Indexing in vector databases
- Indexing in vector databases: recap in one screen
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?
Why exact search stops working
A flat index stores the vectors and compares the query with each 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 times-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.
An index trades exact answers for speed. It organises vectors into a structure — clusters, graphs, trees or compressed codes —. That way, most vectors can be skipped without being compared. The result is approximate nearest-neighbour (ANN) search: faster by orders of size. But with a small chance of missing a genuine neighbour.
The three main families are IVF (inverted file), HNSW (hierarchical navigable small-world graph) and product quantisation. IVF clusters the vectors and searches only the nearest clusters. This trades recall at cluster edges for speed. HNSW builds a layered graph and walks it greedily toward the query — best recall-for-latency, highest memory. Product quantisation compresses each vector into a short code. This cuts memory sharply at some recall cost, and is often combined with IVF.
The metric that matters is recall@k: of the k true nearest neighbours, how many did the index really return? For RAG, 0.95 is often fine because a reranker will re-score the top results anyway. For deduplication or exact matching, a thing less than 1.0 is a data grade problem.
Choosing an index means choosing where on the recall-latency-memory triangle you want to sit. HNSW gives the best recall for a given latency but uses the most memory. IVF-PQ uses the least memory but has lower recall. IVF-flat sits in the middle. The right choice depends on your corpus size, your hardware budget and how much recall loss your use can tolerate.
What an index buys and what it costs
Each approximate index prunes: it organises vectors so that most can be skipped without being compared. That turns a linear scan into a thing closer to logarithmic, and adds the possibility of missing a genuine neighbour. This is 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 often 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 edge.
HNSW builds a navigable small-world graph and walks it greedily. Best recall-for-latency, and the highest memory — it stores the graph and the vectors. This is the default in most vector stores; see ANN indexing.
Product quantization compresses each vector into a short code. This cuts memory by an order of size at some cost to recall. Often combined with IVF rather than used alone.
Also note what an index does not do: sifting by metadata is a separate problem, and combining it with vector search is where most vector stores differ from each other. See permission sifting.
Gauging 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. This means a flat exact search over a sample — often 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 each 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-copy detection or a thing where a miss is a correctness bug. Rather than a grade one, approximate search is the wrong tool and a flat index over a sifted subset is often fast enough.
Sifting, updates and the parts that are not the ANN algorithm
Two problems decide most real vector-store choices, and neither is about nearest-neighbour search.
Metadata sifting. Restricting to a tenant, a date range or a permission set fights the index,. This is because the graph or the clustering was built over all of it. Pre-sifting can disconnect a graph traversal; post-sifting silently returns fewer results. How a store handles this is the main thing that distinguishes them. See permission sifting.
Updates and deletes. HNSW does not delete gracefully: removing a node can disconnect the graph. So implementations tombstone and rebuild at times. 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 speed, which is the easy half.
What a vector store stores
Three things per record, and all three matter:
The vector — the embedding, often 384 to 1,536 floats.
The payload — the text itself, or a guide to it. So the fetched chunk can be put in a prompt.
The metadata — source, date, document type, permissions, heading path. This is what makes sifting doable, and it must be populated at indexing time; adding a field later means re-indexing.
The index is the structure built over the vectors. That way, a nearest-neighbour query does not have to compare against all of them. All of it else the store gives. Persistence, sifting, updates, copying. 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 ruled by cost; batches of 32–128 are a few times faster.
Normalise once, here. Then each query is a dot product rather than a cosine work.
Use deterministic ids derived from the source and chunk spot, so re-indexing a changed document replaces its chunks rather than copying 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 speed one. A fetched chunk from a superseded policy will be used confidently.
Three plans:
Full rebuild. Re-index all of it 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 grade 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 gave 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 really holds, what an update costs. And the staleness that follows from the answer.
Building on the same setup, the next block shows the left cases.
The below block covers the left steps.
The next block goes on with the left demonstrations.
Things to try with Indexing in vector databases
- 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 checks and lower recall. The same trade from the other way.
What to recall
Without an index, finding the nearest vector means comparing against each 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 each index type exposes them under different names.
Sifting, and the link 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 all of it.
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 sifted away.
Modern vector stores implement sifted search that navigates the index while respecting the predicate. This is the right answer and why using a real store beats a raw index library once sifting matters.
For permissions in detail, the filter must be applied inside the search, server-side. Fetching first and sifting in the use means documents the user cannot see have now influenced which results came back. And in the worst case, their content has now crossed a trust edge.
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 unneeded 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 now uses Postgres. One store to run, transactional consistency with the rest of the data, and SQL for the sifting. 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 cost; one collection with a tenant field in the metadata scales better and relies on sifting being correct.
Backups. The index is derivable from the documents, so the question is whether re-indexing is acceptable as fix. 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 precision cost. Some models support truncating dimensions on purpose.
Questions people ask about Indexing in vector databases
Do I need a vector store? Below 100k vectors, no. Above that, yes — as much for sifting, 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? Handy. And for large documents a guide to a document store is cleaner. Either way the fetched 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 a few vectors per document? Yes, and it is common. One per chunk, or a few forms (dense, sparse, per-language) per chunk.
Indexing in vector databases: 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 at times to reclaim deleted space.
- Sifting 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.