How Vector Databases Search a Million Vectors Without Checking a Million

Take the word "king." Your database does not store the word. It stores a vector: a list of 768 numbers that place king at a point in space, where words used in similar ways sit nearby.

That one move changes the whole problem. "Find something similar" becomes "find the nearest point." And finding the nearest point in a space of hundreds of dimensions turns out to be the search your normal database index genuinely cannot do.

Meaning becomes a place

An embedding model reads enormous amounts of text and learns to place each word (or sentence, or image) at a point, so that things used in similar contexts land near each other. Closeness is usually measured with cosine similarity: how aligned two vectors are, ignoring their length.

from sentence_transformers import SentenceTransformer, util

model = SentenceTransformer("all-mpnet-base-v2")  # 768 dimensions
vecs = model.encode(["king", "queen", "bicycle"], normalize_embeddings=True)

print(util.cos_sim(vecs[0], vecs[1]))  # king vs queen   -> ~0.63
print(util.cos_sim(vecs[0], vecs[2]))  # king vs bicycle -> ~0.16

king lands near queen and far from bicycle. "Similar meaning" is now just "small distance."

Why brute force scores every vector

To find the closest vector to a query, the simple approach compares the query to every stored vector and keeps the best:

best, best_score = None, -1
for v in all_vectors:        # N vectors
    s = dot(query, v)        # normalized vectors, so dot product = cosine
    if s > best_score:
        best_score, best = s, v

That is O(N times d). With 768 dimensions, a million vectors is roughly a million dot products for a single search. On my machine a simple CPU scan of 1,000,000 vectors took about 38 ms per search, which extrapolates to a few seconds at 100,000,000. A service doing thousands of searches a second cannot live there.

Why your B-tree index can't save you

The instinct from the earlier posts in this series is "add an index." But a B-tree gives you exactly one sorted order. Sort every vector by dimension 0 and you are blind to the other 767. Two vectors can be neighbors in the full space and sit thousands of positions apart in that single sort.

In one run, the true nearest word to "coffee" was "starbucks" (similarity 0.69). Sorted by a single dimension, starbucks sat 3,333 positions away from coffee. The closest thing inside a small window of that sort was "meals" at 0.44: wrong, and weaker.

A composite index does not fix it either. Multiple indexed columns still produce one lexicographic order, not an ordering by distance. Sorted order answers ranges. Similarity is not a range.

The small-world idea

Here is the turn. Think of six degrees of separation: most of your friends are local, but a few know someone far away, and those few long-range links let a message cross the world in about six hops.

Do the same to vectors. Give each one a short list of neighbors, including a few distant ones. Now search is a walk: start somewhere, and keep hopping to whichever neighbor is closer to your query. On a flat graph this already works, but it can crawl, taking many small steps or getting stuck one hop short of the best answer.

HNSW: jump, then refine

HNSW (Hierarchical Navigable Small World, Malkov and Yashunin, 2016) fixes the crawl by adding layers, like a skip list for a graph.

• Top layer: a sparse "airport" map. A few vectors, long jumps across the whole space.
• Middle layers: "highways."
• Bottom layer: every vector, the "streets," for the final precise step.

You enter at the top, take big jumps to get roughly there, then drop down a layer and refine, again and again, until the streets put you on the exact neighbor. A single search touches a tiny fraction of the data.

import hnswlib

index = hnswlib.Index(space="cosine", dim=768)
index.init_index(max_elements=len(vectors), M=16, ef_construction=200)
index.add_items(vectors, ids)

index.set_ef(50)   # the accuracy vs speed dial
labels, distances = index.knn_query(query, k=10)

The honest trade

HNSW is approximate. It can miss, and misses are silent, so you tune it against a recall target. ef_search is the dial: higher looks at more candidates, so recall goes up and speed goes down.

On my run, on the same 20,000 real embeddings:

• brute force, exact: 1.23 ms per search
• HNSW, ef_search = 50: 0.62 ms per search, recall@10 = 99.9%
• HNSW, ef_search = 200: 2.06 ms per search, recall@10 = 100%

Notice the last line: at 20,000 vectors, cranking ef past a point makes HNSW slower than brute force. Approximate search wins because it scales differently: an exact scan is linear in N, HNSW is roughly logarithmic, so the gap widens as your dataset grows. At a million or a hundred million, brute force is hopeless and HNSW is still fast.

Who runs this

HNSW is one of the most common indexes under semantic search and the retrieval step of AI chatbots:

• pgvector (inside Postgres you already run)
• Weaviate (dedicated engine, self-hosted or managed)
• Pinecone (managed)

One rule of thumb: start with pgvector in the database you already operate, and graduate to a dedicated engine when RAM, traffic, filtering, or ops actually force you. It is not the only vector index (IVF, PQ, DiskANN, hybrid search all exist), and not every AI search uses it.

Watch it happen

The full episode builds the meaning-map, shows why the B-tree fails, and descends through the HNSW layers:

Numbers are from a demo on my machine, one model everywhere (all-mpnet-base-v2, 768 dims, 20,000 real words). The one-by-one counter is an animation; the per-check cost is measured and the totals are arithmetic. The million and hundred-million scan times are a linear estimate from a simple CPU run, not a universal speed. The HNSW vs brute-force numbers are measured on the 20,000 vectors with hnswlib. Also worth knowing: "similar" here means "used in similar contexts," not synonyms, so opposites like good and bad can score high.

Which vector database are you using, and what pushed you to it?