Vector databases and ANN indexes

The big idea

Finding the chunks nearest to a query vector is easy to state: compute the distance to every stored vector and keep the closest k. That is exact search, and for a few hundred thousand vectors it is fine. At 100 million vectors of 1,024 dimensions, it means about 100 billion multiply-adds per query, far too slow for an interactive product.

Approximate nearest neighbourApproximate nearest neighbour search: finding vectors that are very likely, but not guaranteed, to be the closest to a query, by searching only a small, well-chosen part of the data. (ANN) indexes give up a guarantee to win that speed. They organise the vectors so that a query only examines a small, well-chosen fraction of them, and they find the true nearest neighbours most of the time. The fraction of true neighbours found is the recallFor nearest neighbour search, the share of the true k nearest neighbours that the approximate search returns, for example 0.95 when it finds 95 of every 100., and every index has knobs that trade recall against latency and memory.

Think of finding the house nearest to an address in a country. You do not measure the distance to every house. You go to the right region, then the right town, then the right street, and only then compare houses. You could occasionally miss a closer house just across a regional border, but you will be very fast.

How it works

Exact search and when it is enough

Brute force is perfectly accurate, needs no index and handles any filter. With vectors in memory and optimised matrix code it searches hundreds of thousands of vectors in milliseconds, and GPUs push that further. If your corpus is small, start here. ANN indexes earn their complexity when the corpus or the query rate grows.

HNSW: a graph you walk

HNSWHierarchical Navigable Small World: an ANN index made of layered proximity graphs, searched by greedy hops from a sparse top layer down to a dense bottom layer. links each vector to a handful of its near neighbours, forming a graph you can walk: from any point, step to whichever neighbour is closer to the query, and repeat until no neighbour is closer. On one flat graph that walk can take many short steps. HNSW adds layers, like a skip list: every point is on layer 0, a random subset is also on layer 1, a smaller subset on layer 2, and so on, with the top layer of each point chosen with exponentially decaying probability. Upper layers have few points and long links, so a search crosses the space in a few hops, then descends and refines.

At layer 0, instead of following a single best path, the search keeps a list of the best ef candidates found so far and keeps expanding them. A larger ef examines more nodes and misses less. The build has its own knobs: M, the number of links per point, and an ef for construction. HNSW gives excellent recall and latency, but the graph lives in memory alongside the vectors, and deleting points is awkward.

IVF: search only nearby clusters

An IVFInverted file index: an ANN index that clusters vectors with k-means and, at query time, scans only the vectors in the few clusters whose centroids are nearest to the query. index runs k-means to split the vectors into many clusters, say thousands, and stores each cluster's members in a list. A query is compared with the cluster centroids, and only the nprobe nearest clusters are scanned. If the true neighbour sits just across a cluster boundary in a cluster that was not probed, it is missed; raising nprobe fixes that at the cost of scanning more. IVF uses less memory than HNSW and builds fast, but needs training data for the clusters and degrades if the data drifts away from them.

Product quantization: compress the vectors

At very large scale, the vectors themselves no longer fit in memory. Product quantizationA compression method that splits each vector into sub-vectors and replaces each with the ID of its nearest centroid in a small learned codebook, so a vector is stored in a few bytes. (PQ) cuts each vector into, say, 64 sub-vectors, learns a codebook of 256 centroids for each slot, and stores only the 64 one-byte centroid IDs: a 4 KB vector becomes 64 bytes. Distances are approximated from precomputed tables. It is often combined with IVF (IVF-PQ), with the best candidates re-scored using full vectors kept on disk.

Recall versus latency

Every knob, ef, nprobe, PQ code size, moves you along the same curve: more work per query buys higher recall. Measure recall@k against brute-force results on a sample of real queries, then pick the cheapest setting that meets your target, often 0.95 or higher. A recall of 0.97 is usually invisible to users when a reranker reorders the top results afterwards ( Hybrid search and reranking ).

Filtering

Real queries come with conditions: only this customer's documents, only 2025, only English. Filtering after the ANN search can leave you with too few results, because most of the top k were filtered out. Filtering before the search can break the graph or cluster structure if the filter is very selective. Vector databases handle this with filter-aware search, partitions per tenant, or a fallback to brute force over the small filtered set. Test your actual filters, not just unfiltered recall.

pgvector or a dedicated vector database

You can add a vector column and HNSW or IVF indexes to PostgreSQL with the pgvector extension, and keep vectors in the same database as the rest of your data, with transactions, joins and familiar operations. Dedicated vector databases add features for scale: distributed indexes, quantisation, hybrid keyword search, multi-tenancy and fast filtered search. For millions of vectors with modest query rates, the database you already run is often enough.

Try it

The graph is built in a simplified way (each layer links points to their nearest neighbours on that layer); real HNSW inserts points one at a time and prunes links with a heuristic.

Try this:

1. At ef = 1, press Step repeatedly. Three greedy hops cross the upper layers, then the search descends and walks layer 0. It stops after computing 15 distances instead of 90, and misses the true nearest point (green ring): greedy search got stuck in a local optimum.
2. Set ef to 2 and Run to end. Keeping two candidates finds the true nearest after 22 distances. Over all 247 test queries, recall rises from 88 percent at ef = 1 to 100 percent at ef = 8, while average work rises only from about 18 to 26 distances.
3. Drag the query to the far corners and step again. Notice how few points the top layers have, and how the first hops cover most of the distance.

Going deeper

IVF in code

Twenty thousand vectors, 100 k-means clusters, and a search that scans only the nprobe nearest clusters:

# Exact search vs an IVF index: cluster the vectors, then scan only the nprobe nearest clusters.
import numpy as np

rng = np.random.default_rng(0)
n, dim, k = 20_000, 32, 10
centres = rng.normal(size=(50, dim)) * 3
X = (centres[rng.integers(0, 50, n)] + rng.normal(size=(n, dim))).astype(np.float32)
Q = (centres[rng.integers(0, 50, 200)] + rng.normal(size=(200, dim))).astype(np.float32)

def exact(q, k):                                   # brute force: compare with every vector
    return np.argsort(((X - q) ** 2).sum(1))[:k]

# Build: a few rounds of k-means to get 100 cluster centroids, then assign every vector.
C = X[rng.choice(n, 100, replace=False)]
for _ in range(8):
    assign = np.argmin(((X[:, None, :] - C[None]) ** 2).sum(2), axis=1)
    C = np.array([X[assign == c].mean(0) if (assign == c).any() else C[c] for c in range(100)])
lists = [np.where(assign == c)[0] for c in range(100)]

def ivf(q, k, nprobe):                             # search only the closest clusters
    near = np.argsort(((C - q) ** 2).sum(1))[:nprobe]
    ids = np.concatenate([lists[c] for c in near])
    return ids[np.argsort(((X[ids] - q) ** 2).sum(1))[:k]], len(ids)

truth = [set(exact(q, k)) for q in Q]
print(f"brute force: scans {n:,} vectors per query, recall@{k} = 1.000")
for nprobe in (1, 2, 4, 8, 16):
    res = [ivf(q, k, nprobe) for q in Q]
    recall = np.mean([len(set(ids) & t) / k for (ids, _), t in zip(res, truth)])
    scanned = np.mean([s for _, s in res])
    print(f"IVF nprobe={nprobe:2}: scans {scanned:7,.0f} ({100 * scanned / n:4.1f}%), recall@{k} = {recall:.3f}")

brute force: scans 20,000 vectors per query, recall@10 = 1.000
IVF nprobe= 1: scans     332 ( 1.7%), recall@10 = 0.787
IVF nprobe= 2: scans     570 ( 2.9%), recall@10 = 0.940
IVF nprobe= 4: scans   1,178 ( 5.9%), recall@10 = 0.996
IVF nprobe= 8: scans   2,260 (11.3%), recall@10 = 1.000
IVF nprobe=16: scans   4,240 (21.2%), recall@10 = 1.000

Scanning one cluster, 1.7 percent of the data, already finds 79 percent of the true top 10. Four clusters, under 6 percent of the data, reach 0.996. That is the whole ANN bargain in one table: a few percent of the work for nearly all of the answers.

Memory budgets

For HNSW, plan for the vectors plus the graph links (with M = 16, about 32 links of 4 bytes per vector on layer 0), all in RAM. A billion vectors at 1,024 float32 dimensions is about 4 TB of vectors alone, which is why billion-scale systems use PQ codes in memory and full vectors on disk ( Embedding and indexing ).

Updates and deletes

HNSW supports inserts well but handles deletes with tombstones and periodic rebuilds; IVF needs re-clustering when data drifts. Plan for re-indexing as an operation, not an emergency.

Trade-offs

Common mistakes

• Reaching for a distributed vector database for a corpus brute force could search in milliseconds.
• Never measuring recall, so a misconfigured index silently returns worse results.
• Testing unfiltered queries, then shipping selective filters that return too few results.
• Sizing memory for the vectors but forgetting the graph links and growth.
• Tuning ef or nprobe for benchmark speed without checking the recall on real queries.

In the wild

Check yourself

Recap