Storing and searching vectors

A vector database stores embeddings and finds the ones closest to a query embedding. Before reaching for one, it is worth knowing how much work that actually is, because the answer surprises people in both directions: far less than expected at small scale, and a genuine engineering problem past a few million vectors. This section measures the crossover, then covers the approximate search that makes the large case possible, the filtering problem that breaks more production systems than anything else here, and keeping an index current.

When you need one at all#

Searching vectors exactly is one matrix multiply. Every embedding is a row, the query is a column, and the result is a similarity per document — which modern hardware does very fast. Measure it before designing around it.

import numpy as np, time

d = 768
for n in (10_000, 100_000, 1_000_000):
    X = np.random.default_rng(0).normal(size=(n, d)).astype(np.float32)
    X /= np.linalg.norm(X, axis=1, keepdims=True)     # so a dot product is cosine
    q = X[0]
    t0 = time.perf_counter()
    for _ in range(5):
        sims = X @ q
        top = np.argpartition(-sims, 10)[:10]         # not a full sort
    print(f"n={n:>9,}  {(time.perf_counter()-t0)/5*1000:6.1f} ms   {X.nbytes/1e9:.2f} GB")

# n=   10,000     1.4 ms   0.03 GB
# n=  100,000    13.9 ms   0.31 GB
# n=1,000,000    97.9 ms   3.07 GB

So the honest rule is about the second column as much as the first. Below roughly a hundred thousand vectors, exact search in memory is simpler and gives perfect recall. Past a few million the memory becomes the constraint before the latency does, and you want an index and a system that owns it. The other reasons to adopt one are real but are not about speed: you want persistence and updates without rebuilding, you want metadata filtering alongside the search, or you want more than one process to query the same index.

Approximate nearest neighbour#

Past the point where exact search stops fitting, you trade exactness for speed. Every method does the same thing underneath: avoid comparing the query against most of the collection. The clearest version to reason about is an inverted file index — cluster the vectors once, then search only the clusters nearest the query.

from sklearn.cluster import KMeans

# Real embeddings are clustered, not uniform: documents fall into topics.
rng = np.random.default_rng(0)
n, d, k, n_topics = 100_000, 128, 10, 400
topics = rng.normal(size=(n_topics, d)).astype(np.float32)
X = topics[rng.integers(0, n_topics, n)] + rng.normal(0, 0.35, (n, d)).astype(np.float32)
X /= np.linalg.norm(X, axis=1, keepdims=True)

km = KMeans(n_clusters=256, n_init=1, random_state=0).fit(X[:20_000])
assign = km.predict(X)
buckets = [np.where(assign == c)[0] for c in range(256)]
cen = km.cluster_centers_ / np.linalg.norm(km.cluster_centers_, axis=1, keepdims=True)

# Search: pick the nprobe nearest clusters, rank only what is inside them.
def search(q, nprobe):
    cs = np.argpartition(-(cen @ q), nprobe)[:nprobe]
    cand = np.concatenate([buckets[c] for c in cs])
    return cand[np.argpartition(-(X[cand] @ q), k)[:k]]

# Measure it against exact search on 200 queries.
qs = X[rng.integers(0, n, 200)] + rng.normal(0, 0.15, (200, d)).astype(np.float32)
qs /= np.linalg.norm(qs, axis=1, keepdims=True)
truth = [set(np.argpartition(-(X @ q), k)[:k]) for q in qs]

for nprobe in (1, 2, 4, 8):
    t0 = time.perf_counter()
    hits = sum(len(set(search(q, nprobe)) & want) for q, want in zip(qs, truth))
    ms = (time.perf_counter() - t0) / len(qs) * 1000
    print(f"nprobe={nprobe:2d}  {ms:5.2f} ms/query  recall {hits / (k * len(qs)):.3f}")

# exact        1.80 ms/query   recall 1.000   (for comparison)
# nprobe= 1    0.08 ms/query   recall 0.932
# nprobe= 2    0.13 ms/query   recall 0.975
# nprobe= 4    0.26 ms/query   recall 0.990
# nprobe= 8    0.46 ms/query   recall 1.000

One detail in that code is load-bearing and is worth saying out loud: the vectors were built with topic structure, because real embeddings have it. Repeating the same measurement on uniformly random vectors gives 0.053 recall at one probe and 0.661 at sixty-four — approximate search collapses. It works in practice because documents genuinely cluster, not because the algorithm is clever, and that is also why recall on your data is something to measure rather than to read off a benchmark.

HNSW, the index most systems actually ship, replaces the clustering with a navigable graph and behaves the same way from the outside: one knob that trades recall for latency, and a recall figure you must measure yourself. Whichever you use, the measurement is the same — run a few hundred real queries through both the index and exact search, and report the overlap.

Metadata filtering, and the bug everyone ships#

Almost every real system needs the search restricted: this tenant, this language, documents this user may see. The naive implementation searches first and filters after, and it fails in a way that looks like an empty page rather than an error. Here two per cent of documents belong to the tenant being filtered to.

tenant = rng.random(n) < 0.02                  # 2% of the collection
sims = X @ X[0]

for fetch in (10, 100, 1000, 10000):
    top = np.argpartition(-sims, fetch)[:fetch]
    print(fetch, tenant[top].sum())

# 10        0     <- the user sees nothing at all
# 100       2     <- fewer than the 10 asked for
# 1000     16
# 10000   162

There are two real fixes. Pre-filter — restrict to the eligible rows first and search within them, which always returns k and is what you want when the filter is very selective, since two thousand candidate rows are exact-searchable in under a millisecond. Or use an index that applies the filter during traversal rather than after it, which most mature vector databases now support and which is the reason to prefer one over a hand-rolled index. Post-filtering with a fixed overfetch is the option to avoid: it is a guess about selectivity that is silently wrong for your smallest customers.

Keeping the index fresh#

Indexes are built from data that changes, and the update path is where these systems rot. Three things need a decision before launch rather than after.

• Deletes. Graph indexes usually tombstone rather than remove, so deleted documents keep occupying the graph and recall drifts until a rebuild. Know your system's answer and how often it compacts.
• Updates. A changed document means a changed embedding; treat it as delete plus insert, and make the identity stable so the old vector cannot survive alongside the new one.
• Re-embedding. Changing embedding model invalidates every vector at once, because vectors from two models are not comparable. This is a migration with a cost you can compute in advance, and it needs a plan for serving during it — usually a second index built in the background and an atomic switch.

The last one is the one that surprises teams, and it is worth pricing before choosing a model rather than after. Re-embedding a few million chunks is hours of throughput and a real bill, and the temptation under that pressure is to keep a model you have outgrown. Knowing the number in advance makes it a decision instead of a constraint.