Vector Databases Explained: Exact vs Approximate Nearest Neighbours

Semantic search, recommendations and retrieval-augmented generation all end in the same question: given one vector, which stored vectors are nearest to it? A vector database answers that quickly over millions of rows. The part interviews probe is that the fast answer is usually approximate: what that costs, how to measure it, and how it interacts with filters.

The problem it solves

An embedding model turns text, images or audio into a fixed-length list of numbers, placed so that related items sit close together. "Find documents like this one" becomes "find the vectors most similar to this one", usually by cosine similarity, which equals the dot product for vectors normalised to length 1; the cosine similarity article covers the maths.

The exact method scores the query against every stored vector and keeps the best k. It is always correct and costs one full pass per query: nothing for a few thousand vectors, far too slow for a hundred million at many queries per second.

The intuition

An approximate nearest neighbour (ANN) index trades a little accuracy for a lot of speed by not looking at most of the collection.

The simplest family to picture is the inverted file index. At build time, representative points called centroids are chosen, and every vector is filed under its nearest centroid, splitting the collection into cells of neighbours. At query time, compare the query with the centroids only, pick the few nearest cells, and score just the vectors inside them. The number of cells probed is the dial: more cells, more work, fewer misses.

The miss is the catch. A true neighbour just across a cell boundary is never scored, with no error and no warning; the results simply look slightly worse. So ANN quality is measured as recall@k: of the true top k found by exact search, what fraction did the index return? You measure it offline, on sample queries, by running both.

Other index families make the same trade in different ways; a popular one, HNSW, walks a layered graph of neighbours instead of scanning cells. As of September 2026, both inverted-file and graph indexes are common in dedicated vector databases and in vector extensions for relational databases such as PostgreSQL's pgvector.

Two practical rules sit alongside the index. First, similarity knows nothing about permissions: to search only one customer's documents, the database needs a metadata filter applied as part of the search, not after it. Second, one collection, one model, one dimension: vectors from different embedding models live in unrelated spaces, so comparing them is meaningless even when the lengths happen to match.

Watch it run

The animation opens with the one question a vector database answers: which stored vectors sit nearest this one? Three of them are named, a, b and c, and the rest of the collection is grey. A query vector arrives: [1, 0]. Brute force scores it against every single row, which is correct, and linear. Vector a points exactly where the query does, so it scores 1.00. Vector c is almost the same direction at 0.90, a near-match, not a duplicate. And b shares nothing with the query at all, so it scores 0.00. Rank and take the top two, a and c, and that is the whole query. Then the collection grows, and scanning every row stops working, so an index groups neighbours into cells. A query then touches one neighbourhood instead of the whole collection. The catch: a true neighbour just outside the cell is missed silently, and the results merely look worse. Similarity has no idea who may see what, so a metadata filter restricts the search first. And every vector in one collection must share one model and one dimension, or distances mean nothing.

The code

Exact search on the animation's three vectors, scored by dot product as in the lesson:

import heapq

def score(u, v):
    return sum(x * y for x, y in zip(u, v))            # dot product: cosine when both have length 1

def exact_top_k(store, q, k):
    """Brute force: score every stored vector, keep the k best. Correct, and linear."""
    return heapq.nlargest(k, store, key=lambda key: score(store[key], q))

store = {"a": [1, 0], "b": [0, 1], "c": [0.9, 0.1]}
q = [1, 0]
print({key: score(v, q) for key, v in store.items()})   # {'a': 1, 'b': 0, 'c': 0.9}
print(exact_top_k(store, q, 2))                         # ['a', 'c']

A toy model of an inverted-file index, not a production vector database: 3,000 unit vectors in 8 dimensions, bunched around 20 themes, filed into 30 cells. For 40 queries it measures recall@10 and the share of the collection scanned as more cells are probed:

import math
import random

random.seed(24)
DIM = 8
centres = [[random.gauss(0, 1) for _ in range(DIM)] for _ in range(20)]

def unit(v):
    n = math.sqrt(sum(x * x for x in v))
    return [x / n for x in v]

def sample():                                           # points bunched around 20 themes
    c = random.choice(centres)
    return unit([x + random.gauss(0, 0.35) for x in c])

vectors = {f"doc{i}": sample() for i in range(3000)}
queries = [sample() for _ in range(40)]

class ToyIVF:
    """Toy model of an inverted-file index: vectors grouped into cells around centroids."""
    def __init__(self, store, n_cells, seed=0):
        rng = random.Random(seed)
        self.store = store
        self.centroids = [store[k] for k in rng.sample(sorted(store), n_cells)]
        self.cells = [[] for _ in range(n_cells)]
        for key, v in store.items():                    # each vector lives in its nearest cell
            self.cells[max(range(n_cells), key=lambda i: score(self.centroids[i], v))].append(key)

    def search(self, q, k, n_probe):
        nearest = heapq.nlargest(n_probe, range(len(self.cells)), key=lambda i: score(self.centroids[i], q))
        candidates = [key for i in nearest for key in self.cells[i]]
        top = heapq.nlargest(k, candidates, key=lambda key: score(self.store[key], q))
        return top, len(candidates)

index = ToyIVF(vectors, n_cells=30)
for n_probe in (1, 3, 10, 30):
    found = scanned = 0
    for qv in queries:
        truth = set(exact_top_k(vectors, qv, 10))
        top, n = index.search(qv, 10, n_probe)
        found += len(truth & set(top))
        scanned += n
    print(n_probe, f"recall@10={found / (10 * len(queries)):.2f}",
          f"scanned={scanned / (len(vectors) * len(queries)):.0%}")
# 1 recall@10=0.78 scanned=7%
# 3 recall@10=0.96 scanned=15%
# 10 recall@10=1.00 scanned=38%
# 30 recall@10=1.00 scanned=100%

One cell scans 7% of the collection and misses over a fifth of the true neighbours; three cells scan 15% and find 96%. Probing every cell is exact search again.

Filters and dimensions. Filtering after the top 10 leaves one result for tenant t3; filtering first returns a full 10. And a naive scorer does not even notice a length mismatch, because zip stops at the shorter vector, so the collection must check on insert:

tenant = {key: f"t{i % 5}" for i, key in enumerate(vectors)}
qv = queries[0]
post = [key for key in exact_top_k(vectors, qv, 10) if tenant[key] == "t3"]
allowed = {key: v for key, v in vectors.items() if tenant[key] == "t3"}
pre = exact_top_k(allowed, qv, 10)
print(len(post), len(pre), all(tenant[key] == "t3" for key in pre))   # 1 10 True

print(score([1, 0, 0], [1, 0]))                        # 1   zip() stops at the shorter one

class Collection:
    def __init__(self, dim, model):
        self.dim, self.model, self.rows = dim, model, {}

    def insert(self, key, vector, model):
        if len(vector) != self.dim or model != self.model:
            raise ValueError("one collection, one model, one dimension")
        self.rows[key] = vector

col = Collection(dim=2, model="embed-v1")
col.insert("a", [1, 0], "embed-v1")
try:
    col.insert("x", [1, 0, 0], "embed-v2")
except ValueError as e:
    print(e)                                            # one collection, one model, one dimension

Checked on 150 seeded random collections. The heap-based exact search must equal a full sort, recall must never drop as more cells are probed, and probing every cell must return exactly the brute-force answer:

rng = random.Random(24)
ok = True
for _ in range(150):
    dim = rng.randint(2, 6)
    data = {f"v{i}": [rng.uniform(-1, 1) for _ in range(dim)] for i in range(rng.randint(5, 80))}
    k, cells = rng.randint(1, 8), rng.randint(1, 5)
    q = [rng.uniform(-1, 1) for _ in range(dim)]
    brute = sorted(data, key=lambda key: -sum(x * y for x, y in zip(data[key], q)))[:k]
    ok &= exact_top_k(data, q, k) == brute
    ivf = ToyIVF(data, min(cells, len(data)), seed=rng.randint(0, 999))
    recalls = [len(set(ivf.search(q, k, p)[0]) & set(brute)) for p in range(1, len(ivf.cells) + 1)]
    ok &= recalls == sorted(recalls) and recalls[-1] == len(brute)   # more cells never hurts; all cells is exact
print(ok)                                              # True

The complexity

• Exact search: O(n × d) per query for n vectors of d dimensions, plus O(n log k) to keep the top k.
• Inverted file: O(c × d) to rank c centroids, plus the vectors in the probed cells, roughly n × probes / c when cells are balanced.
• Building the index: a pass that assigns every vector to a cell; in real systems the centroids come from clustering, and the index must be rebuilt or rebalanced as the data drifts.

Where it goes wrong

• Never measuring recall. Missed neighbours are silent; keep a set of queries with exact answers and track recall@k.
• Filtering after the search. A narrow filter can leave far fewer than k results, or none.
• Mixing embedding models. Re-embed the whole collection when the model changes.
• Reaching for an ANN index too early. For small collections, exact search is simpler and correct.

When it shows up in interviews

It shows up in machine learning system design as the retrieval layer of RAG, and in general design rounds as "how would you find similar items at scale?". Expect follow-ups on recall versus latency, multi-tenant filtering, and upgrading the embedding model. The exact version is a plain top-k with a heap over similarity scores.

How to say it in an interview

"A vector database answers nearest-neighbour queries over embeddings. Exact search is correct but linear, so at scale I use an approximate index, such as an inverted file that probes only the nearest few cells, or a graph index like HNSW. The trade-off is recall: a neighbour outside the probed cells is missed silently, so I measure recall@k against exact search on sample queries and tune the number of probes. I apply tenant or permission filters inside the search, not after it, and keep one embedding model and dimension per collection."