Vector databases

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.

If your data already lives in Postgres, pgvector lets the vectors live there too, which removes a whole system from the diagram: one database, one backup, one transaction, and joins between your embeddings and everything else you already store. This section is a real 50,000-row index, with the timings, the index size, the recall measured against exact search, and the filtering behaviour that returns an empty page in production while looking entirely correct in code. Every number below came from running it.

A table, a column and a query#

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE chunks (
  id        int primary key,
  document  int,
  tenant    boolean,          -- whatever you will filter on
  content   text,
  embedding vector(384)       -- the dimension is fixed at declaration
);

-- Nearest neighbours by cosine distance. The operator picks the metric:
--   <=>  cosine        <->  L2        <#>  negative inner product
SELECT id, content
FROM chunks
ORDER BY embedding <=> $1
LIMIT 10;

With no index that query is a sequential scan, and for 50,000 rows of 384 dimensions it took 31 ms. The table itself was 80 MB. That is already usable for a small corpus, and it has perfect recall, so do not add an index until the numbers say to.

HNSW index settings#

CREATE INDEX ON chunks
  USING hnsw (embedding vector_cosine_ops)   -- must match the query operator
  WITH (m = 16, ef_construction = 64);

-- Build output on 50,000 rows of 384 dimensions:
--   NOTICE: hnsw graph no longer fits into maintenance_work_mem
--           after 28367 tuples
--   DETAIL: Building will take significantly more time.
--   11.6 seconds, index size 98 MB

Three settings matter and they split cleanly. The operator class has to match the operator you query with — build with vector_cosine_ops and query with the L2 operator and Postgres will simply not use the index, which shows up as a query that was fast in testing and is slow in production. Then m and ef_construction are build-time: higher means a better graph, a larger index and a slower build, and 16 and 64 are sensible defaults. Finally ef_search is query-time, changeable per session, and is the knob you actually tune.

Measuring recall against exact search#

An approximate index has a recall, and you do not know it until you measure it on your own data. The measurement is simple: take a hundred real queries, get the true top ten by forcing a sequential scan, get the indexed top ten, and report the overlap.

-- The ground truth: turn the index off for this session.
SET enable_indexscan = off;
SELECT id FROM chunks ORDER BY embedding <=> $1 LIMIT 10;

-- The indexed answer, at a given ef_search.
SET enable_indexscan = on;
SET hnsw.ef_search = 40;
SELECT id FROM chunks ORDER BY embedding <=> $1 LIMIT 10;

-- Overlap over 100 queries, 50,000 rows:
--   ef_search   recall     query time
--      10        0.974       1.7 ms
--      20        0.994       1.8 ms
--      40        0.995       1.9 ms
--     100        0.995       1.6 ms
--   exact        1.000      31.3 ms

Filters that return too few rows#

This is the one that ships. The query below is correct SQL, it is the obvious thing to write, and on this data it returns nothing at all — for a tenant that has 1,059 matching documents.

SELECT id FROM chunks
WHERE tenant                       -- 1,059 of the 50,000 rows
ORDER BY embedding <=> $1
LIMIT 10;

--  0 rows

EXPLAIN ANALYZE on the same query:
  Index Scan using chunks_embedding_idx on chunks
    (actual time=1.407..1.407 rows=0 loops=1)
    Rows Removed by Filter: 40

The mechanism is that the graph traversal does not know about your WHERE clause. It fetches ef_search candidates by vector distance alone and the filter is applied to whatever comes back, so the rarer the filtered category, the more likely every candidate is rejected. A tenant with two per cent of the rows breaks at the default; a tenant with twenty per cent does not, which is exactly why this reaches production — it works for every customer you tested with.

-- Fix 1: widen the search until enough survive the filter.
SET hnsw.ef_search = 1000;
SELECT id FROM chunks WHERE tenant ORDER BY embedding <=> $1 LIMIT 10;
--  10 rows

-- Fix 2: for a selective filter, skip the index entirely. 1,059 rows
-- is nothing to scan exactly, and the answer is exactly right.
SET enable_indexscan = off;
SELECT id FROM chunks WHERE tenant ORDER BY embedding <=> $1 LIMIT 10;
--  10 rows

-- Fix 3: a partial index per high-traffic tenant, so the graph
-- contains only rows that can survive the filter.
CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops)
  WHERE tenant;

Changing embedding models#

Vectors from two different models are not comparable, so changing model invalidates the entire column at once — there is no incremental path and no way to serve both from one index. The workable migration is a second column, backfilled in the background while the old one keeps serving, an index built on it, then a switch of the query and a drop of the old column. The dimension is declared in the table, so a model with a different width needs the new column regardless.

Price it before you choose the model rather than after. On the numbers above, the index alone was 98 MB for 50,000 chunks, so a few million chunks is tens of gigabytes of index that has to be rebuilt, plus the embedding cost and the hours of throughput to produce them. That figure is what decides whether a model upgrade is a Tuesday or a quarter.