5 — Finding the nearest ones quickly

Chapter 4 turned the site into 3,951 passages, each with a 768-number vector, and turned a question into one more vector. Finding the passages that answer the question means finding the vectors with the highest cosine similarity to the question’s vector. So far that has meant computing the similarity with every passage and sorting.

That’s called brute force, or exact search, and it’s worth measuring before replacing it. This chapter times it, then builds the two index structures most vector databases use, IVF and HNSW, small enough to read in full. It measures what each one gives up for its speed. Then it does the same search inside PostgreSQL with the pgvector extension, which is where the assistant’s passages will live from here on.

Timings are from one Mac (Apple M3 Pro, 18 GB) shared with other work, so treat small differences as noise. The vectors are the 3,951 passage embeddings from chapter 4 (nomic-embed-text, 768 dimensions, unit length). The queries are 100 real questions. To get them, llama3 (8B, Q4_0) wrote one question for each of 100 randomly chosen passages, for example “How do I efficiently merge overlapping intervals?” and “What happens to the threads in a warp that don’t meet the condition in the if statement?”. Each question was embedded with the search_query: prefix.

How fast is brute force?

Because the vectors have length 1, cosine similarity is a dot product, and scoring every passage is one matrix–vector product. Picking the top five doesn’t need a full sort. argpartition finds the five largest in linear time, and only those five get sorted:

def brute(X, q, k):
    s = X @ q                                  # one dot product per passage
    top = np.argpartition(-s, k)[:k]           # the k best, unordered
    return top[np.argsort(-s[top])]            # order just those k

For each query, the time below is the best of three runs, and the table reports the median over the queries.

The real corpus takes 66 microseconds per question. Embedding the question with Ollama, measured in chapter 6, takes far longer than that, and generating the answer takes seconds. For this site, brute force is the right answer, and nothing in the rest of this chapter makes the assistant noticeably faster.

The two larger rows show where that stops being true. They’re synthetic: the real vectors copied 10 and 50 times, with random noise added to each copy and the result normalized again. They’re only there to measure time against size. Ten times the data took 24 times as long, because 12 MB fits in the chip’s caches and 121 MB doesn’t. From there, the cost tracks memory: the 607 MB set was scanned at about 68 GB/s, which means the multiplication is waiting on memory, not on arithmetic. On that trend, a million passages (3 GB of vectors) would take something like 45 ms per query on this machine. That figure is an extrapolation, not a measurement. Ten million would take seconds, before any other user asks anything.

Brute force has a cost proportional to the number of vectors, and it reads every one of them. To be faster, a search has to skip most of them. If it skips some, it may skip the right one. The rest of this chapter is about that trade.

Measuring what an index gives up

An approximate index returns some five passages quickly. The question is how often they’re the same five that brute force would have returned. That’s measured as recall@5: for each query, the fraction of the true top five (from brute force) that the index also returned, averaged over the 100 queries. A recall of 0.95 means that, on average, 4.75 of the five passages are the right ones.

Recall here is measured against brute force, not against whether a passage actually answers the question. An index can’t do better than the embeddings it searches. Chapter 4 already showed that the true top five is sometimes wrong. That’s a separate problem, and the later chapters take it on.

Two more numbers are worth recording besides time. One is the number of dot products per query, which measures the work done regardless of language or machine. The other is the extra memory the index needs on top of the vectors.

IVF: search only the nearby buckets

The inverted file index (IVF) splits the vectors into groups ahead of time and, at query time, searches only the groups nearest to the query.

The groups come from k-means clustering. Pick nlist starting centers, assign every vector to its nearest center, move each center to the average of its vectors, and repeat. For unit vectors the averaging step normalizes the center again, so that the dot product still works as the measure (“spherical” k-means). Each center then owns a list of vector ids: its inverted list.

At query time, compare the query with all the centers, take the nprobe closest, and search exhaustively within only those lists.

class IVF:
    def __init__(self, X, nlist, iters=20, seed=0):
        rng = np.random.default_rng(seed)
        C = X[rng.choice(len(X), nlist, replace=False)].copy()
        for _ in range(iters):                       # spherical k-means
            assign = np.argmax(X @ C.T, axis=1)
            for j in range(nlist):
                m = X[assign == j]
                if len(m):
                    c = m.sum(0); C[j] = c / np.linalg.norm(c)
        self.X, self.C = X, C
        assign = np.argmax(X @ C.T, axis=1)
        self.lists = [np.where(assign == j)[0] for j in range(nlist)]

    def search(self, q, k, nprobe):
        near = np.argsort(-(self.C @ q))[:nprobe]    # closest centers
        ids = np.concatenate([self.lists[j] for j in near])
        s = self.X[ids] @ q                          # exact search inside them
        return ids[np.argsort(-s)[:k]]

With 63 lists (about the square root of 3,951), building took 0.05 seconds. The lists are uneven: the smallest has 13 passages, the median 58 and the largest 139. Topics on this site aren’t evenly sized, and k-means follows the data. The extra memory is the 63 centers plus a list id for each vector: 0.21 MB.

Searching one list finds fewer than half of the true top five. The reason is in the geometry. A question about, say, partitioning in Kafka sits between the “Kafka” cluster and the “partitioning” cluster, and its nearest neighbors are split between them. The nearest center isn’t where all the nearest vectors are, and that’s especially true near cluster boundaries, which is where many real questions land. Probing more lists fixes it, but the cost grows quickly. Reaching 0.95 recall took 16 of the 63 lists, about 30% of the data.

On time, the index loses to brute force from nprobe 8 upward on this corpus. Gathering the vectors from scattered lists (self.X[ids] copies them) costs more than one straight pass over 12 MB. The dot-product column shows the real saving. At a million vectors, with the same proportions, nprobe 8 would read about 16% of the data instead of all of it.

HNSW: walk a graph toward the query

HNSW (Hierarchical Navigable Small World, from Malkov and Yashunin) takes a different approach. Instead of buckets, it builds a graph. Each vector is a node, linked to a handful of its near neighbors. To search, start somewhere, look at the current node’s neighbors, move to whichever is closest to the query, and repeat until no neighbor is closer. That greedy walk works well when every node also has a few long-range links that cross the space quickly.

The “hierarchical” part provides those long links. Every node is in layer 0. A random few are also in layer 1, fewer still in layer 2, and so on, with the probability falling geometrically. The upper layers are sparse, so their links span long distances. A search enters at the top, walks greedily to the closest node there, drops a layer and continues from that point, and only at layer 0 does a wider search.

The wider search keeps a list of the ef best candidates found so far instead of a single current node. It keeps expanding the closest unexpanded candidate until none of them could improve the list. A larger ef means more of the graph explored, higher recall and more work.

Here is the search part:

def _search_layer(self, q, entries, ef, l):
    X, G = self.X, self.layers[l]
    visited = set(entries)
    d0 = [(-float(X[e] @ q), e) for e in entries]
    cand = list(d0); heapq.heapify(cand)                   # closest first
    best = [(-d, e) for d, e in d0]; heapq.heapify(best)   # worst of the best on top
    while cand:
        d, c = heapq.heappop(cand)
        if d > -best[0][0] and len(best) >= ef:
            break                        # nothing left can improve the list
        nbrs = [n for n in G.get(c, ()) if n not in visited]
        if not nbrs:
            continue
        visited.update(nbrs)
        ds = -(X[nbrs] @ q)              # distances to all unvisited neighbors
        for dn, n in zip(ds.tolist(), nbrs):
            if len(best) < ef or dn < -best[0][0]:
                heapq.heappush(cand, (dn, n))
                heapq.heappush(best, (-dn, n))
                if len(best) > ef:
                    heapq.heappop(best)
    return sorted((-nd, n) for nd, n in best)

def search(self, q, k, ef):
    ep = [self.entry]
    for l in range(self.top, 0, -1):     # greedy descent through the sparse layers
        ep = [self._search_layer(q, ep, 1, l)[0][1]]
    W = self._search_layer(q, ep, max(ef, k), 0)
    return np.array([n for _, n in W[:k]])

Building the graph uses the same search. Each new vector draws a random top layer with level = int(-ln(U) * mL), where mL = 1/ln(M). It then searches for its ef_construction nearest existing nodes on each layer from that level down, and links to up to M of them (2M on layer 0). The choice of which M matters. The paper’s heuristic keeps a candidate only if it is closer to the new node than to any neighbor already kept. That favors links in different directions over a tight bunch of near-duplicates, and it’s what keeps the graph navigable on clustered data like this. When a neighbor ends up with too many links, its list is pruned with the same rule.

def _select(self, base, cands, m):
    X, kept = self.X, []
    for d, c in cands:                       # closest candidates first
        if all(-(X[c] @ X[k]) > d for k in kept):
            kept.append(c)
            if len(kept) == m:
                break
    return kept

The whole class, insertion included, is about 90 lines. With M = 16 and ef_construction = 64, the defaults pgvector also uses, building over the 3,951 passages took 2.2 seconds in pure Python. The graph came out with 3 layers holding 3,951, 231 and 19 nodes, and 62,654 directed links, about 16 per passage. Stored as 32-bit ids, the links take 0.25 MB. Python’s lists and dicts take several times that, but a compiled implementation stores something close to the compact figure.

Compare the two indexes at roughly equal work. With about 640 dot products, IVF (nprobe 8) reaches 0.894 recall, and HNSW reaches 0.986 with 508. For 0.95 or better, HNSW needs about 300 dot products, IVF about 1,165. The graph spends its work much better because each step moves toward the query instead of scanning a bucket that only roughly matches.

The time column tells the opposite story, and it’s worth being honest about. Even at ef = 5, this HNSW is no faster than brute force (0.067 ms against 0.066 ms), and at ef = 40 it’s five times slower. Each step of the walk is a few Python operations on a handful of vectors. Brute force is one call into an optimized matrix routine that streams through memory. At 3,951 vectors, interpreter overhead dominates everything. The dot-product count is the number that carries over to a compiled implementation and a larger corpus, and the next section shows the real thing.

The trade, in one place

IVF is cheap to build and easy to reason about. Its weakness is boundaries, and the fact that its clusters are fixed at build time: add many passages on a new topic and they all land in whichever old list is nearest, until the index is rebuilt. HNSW gets much more recall per unit of work and accepts inserts one at a time. Its costs are a slower build, more memory for links and harder deletes, because removing a node means repairing the links that ran through it. Both have one dial (nprobe, ef) that trades recall for speed at query time, and in both cases the right setting comes from measuring recall on real queries, as above.

Production libraries add compression on top of this. Product quantization stores each vector as a few bytes of codes instead of 3 KB of floats, at some cost in precision. FAISS combines it with IVF, for example. For a corpus of this size it isn’t needed.

The same search in PostgreSQL

The assistant needs more than vectors. It needs the passage text, the page it came from, the section heading, and the ability to filter by track or update one document without rebuilding everything. That’s a database’s job, and pgvector adds vector columns, distance operators and both index types to PostgreSQL.

PostgreSQL isn’t installed on this Mac. The pgserver Python package bundles a PostgreSQL build with pgvector, so it runs inside a Python virtual environment with no system install. It needed Python 3.12, because the package has no build for 3.14 yet. It provided PostgreSQL 16.2 and pgvector 0.6.2. That pgvector version dates from March 2024, and the current release is 0.8.7 (changelog). Two later features that matter below, the halfvec type (0.7.0) and iterative index scans (0.8.0), are therefore described here from the documentation but weren’t tested.

import pgserver, psycopg

srv = pgserver.get_server("./pgdata")            # starts a private PostgreSQL
con = psycopg.connect(srv.get_uri(), autocommit=True)

The table

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE chunks (
    id        int PRIMARY KEY,
    track     text NOT NULL,        -- blog, kernel, gpu, design, dsa, essays
    url       text NOT NULL,        -- /design/07-caching
    section   text,                 -- nearest heading, for citations
    body      text NOT NULL,
    embedding vector(768) NOT NULL
);

The 3,951 rows went in with COPY, with each vector written as a text literal like [0.0504,0.0546,...]. That took 0.82 seconds. The table, text included, is 19 MB.

Operators

pgvector defines a distance operator for each measure (README):

The inner product is negated because PostgreSQL index scans only run in ascending order, so “largest inner product” has to be written as “smallest negative inner product”. For unit vectors all three produce the same ranking. Cosine distance is used here because it’s the clearest to read, and it stays correct if a non-normalized vector ever gets in. The nearest five passages are an ordinary ORDER BY ... LIMIT:

SELECT id, url, section, 1 - (embedding <=> $1) AS similarity
FROM chunks
ORDER BY embedding <=> $1
LIMIT 5;

Exact search in SQL

With no vector index, PostgreSQL scans every row, computes the distance and keeps the best five with a top-N heap sort. From EXPLAIN ANALYZE, with the 768 numbers of the query vector replaced by [...]:

Limit (actual time=4.443..4.444 rows=5 loops=1)
  ->  Sort (actual time=4.443..4.443 rows=5 loops=1)
        Sort Key: ((embedding <=> '[...]'::vector))
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Seq Scan on chunks (actual time=0.004..4.323 rows=3951 loops=1)
Execution Time: 4.447 ms

That’s 4.58 ms per query (median of 100, measured from Python, round trip included). It’s 70 times slower than the numpy version, because each row is a separate tuple to read and a separate function call, not one pass of a matrix routine. It’s still far below anything a person would notice. Exact search in PostgreSQL also has a simple property that approximate search lacks: it’s always right, and it has no settings.

HNSW in pgvector

CREATE INDEX chunks_hnsw ON chunks
    USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 64);

The operator class has to match the operator in the query (vector_cosine_ops for <=>), or the planner can’t use the index. Building it took 0.83 seconds, and the index is 15 MB: larger than the 12.1 MB of vectors, because an HNSW index stores its own copy of every vector next to the links. The same query now uses it:

Limit (actual time=0.360..0.374 rows=5 loops=1)
  ->  Index Scan using chunks_hnsw on chunks (actual time=0.359..0.373 rows=5 loops=1)
        Order By: (embedding <=> '[...]'::vector)
Execution Time: 0.393 ms

The search-time dial is hnsw.ef_search, 40 by default, set per session or per transaction:

SET hnsw.ef_search = 100;

This is the compiled version of the Python graph above, and the shape matches. It’s about 20 times faster than the exact scan at the default setting, with 0.994 recall, which means one wrong passage in about every 33 queries’ worth of top-five results.

IVFFlat in pgvector

CREATE INDEX chunks_ivf ON chunks
    USING ivfflat (embedding vector_cosine_ops) WITH (lists = 63);
SET ivfflat.probes = 16;

The README suggests starting with rows / 1000 lists for up to a million rows, and sqrt(lists) probes. Here that would be 4 lists, which is barely an index, so 63 lists were used to match the numpy version. IVFFlat builds its clusters from the rows present at CREATE INDEX time, so it should be created after the data is loaded. The build took 0.27 seconds and the index is 16 MB.

The default of one probe returns about half of the right passages on this corpus, which matches the numpy IVF closely (0.488). Nothing errors and nothing warns: the query simply returns worse results. This is the main operational risk with approximate indexes. A setting that silently lowers quality has to be measured, and measured again whenever the data changes.

Filtering: the trap

The assistant will often want to search part of the site: only the kernel track, say, or only the chapters a reader has open. In SQL that’s just a WHERE clause:

SELECT id FROM chunks
WHERE track = 'kernel'
ORDER BY embedding <=> $1
LIMIT 5;

With the HNSW index in place, this returned far fewer than five rows. For the same 100 questions, with ef_search at its default of 40:

The plan shows why:

Limit (actual time=0.205..0.205 rows=0 loops=1)
  ->  Index Scan using chunks_hnsw on chunks (actual time=0.205..0.205 rows=0 loops=1)
        Order By: (embedding <=> '[...]'::vector)
        Filter: (track = 'blog'::text)
        Rows Removed by Filter: 40
Execution Time: 0.208 ms

The index scan produced its 40 candidates (ef_search), the filter removed all 40 because none were blog passages, and the query returned zero rows. pgvector’s documentation states this directly: with approximate indexes, filtering is applied after the index is scanned, so a condition matching 10% of rows leaves about 4 of the 40 candidates on average. Even the broadest filter, a quarter of the corpus, came up short on more than half the questions. No error is raised. The application just gets fewer results, or none.

Several fixes were measured, all on the blog filter:

Raising ef_search helps slowly and costs time. At 400 it still returned only half the rows. The two approaches that work are the opposite of each other.

When the filter is selective, skip the vector index. A B-tree on track finds the 108 blog rows, and computing 108 exact distances is trivial. The planner chooses that plan when no vector index competes:

CREATE INDEX chunks_track ON chunks (track);

Limit (actual time=0.111..0.112 rows=5 loops=1)
  ->  Sort (actual time=0.111..0.111 rows=5 loops=1)
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Bitmap Heap Scan on chunks (actual time=0.006..0.107 rows=108 loops=1)
              Recheck Cond: (track = 'blog'::text)
              ->  Bitmap Index Scan on chunks_track (actual time=0.002..0.002 rows=108 loops=1)
Execution Time: 0.116 ms

With both the B-tree and the HNSW index present, though, the planner picked the HNSW index again, and the result went back to 0.55 rows. The planner’s cost estimates don’t account for the filter emptying the candidate list.

When a filter value is common and fixed, build an index for it. A partial index covers only the matching rows, so every candidate it returns passes the filter:

CREATE INDEX chunks_hnsw_blog ON chunks
    USING hnsw (embedding vector_cosine_ops) WHERE track = 'blog';

It took 440 kB and returned exact results at 0.11 ms. The planner can only use a partial index when it can prove the query’s condition implies the index’s condition. With the track sent as a bind parameter, it did so in a fresh session. In one run where the same prepared statement had already been planned before the partial index existed, it kept using the full index and returned 0.55 rows. Writing the literal value into the SQL text removes the doubt.

pgvector 0.8.0 added a third option, iterative index scans (SET hnsw.iterative_scan = strict_order or relaxed_order). When the filter leaves too few rows, the index scan continues past ef_search, up to a limit (hnsw.max_scan_tuples, 20,000 by default). That addresses this problem directly, but the bundled 0.6.2 doesn’t have it, so it’s untested here.

The general rule from these measurements is that an approximate index plus a filter needs a test that counts the rows returned, not just one that checks the query runs.

Memory and type

The vectors are 32-bit floats, 3 KB each. pgvector’s halfvec type (0.7.0 and later) stores 16-bit floats instead, halving the table and index, and the vector type accepts at most 2,000 dimensions for indexing (4,000 for halfvec). At 768 dimensions and 3,951 rows none of this matters. At ten million rows, the HNSW index alone would be around 40 GB by the ratio measured here, and choices like these decide whether it fits in RAM.

Where this leaves things

For this site, searching is solved, and was never really the bottleneck. Brute force takes 66 microseconds in numpy and under 5 ms as an exact scan in PostgreSQL. HNSW in pgvector cuts that to about a quarter of a millisecond at 0.994 recall. Small implementations of IVF and HNSW showed where the speed comes from and what it costs. IVF loses neighbors at cluster boundaries unless it probes many lists. HNSW gets much more recall per unit of work, at the cost of memory and build time. And approximate indexes combined with a WHERE clause can silently return almost nothing.

The passages now live in a PostgreSQL table with their text, source page and section, and the nearest ones can be found by meaning, with or without a filter. What’s missing is everything around that query: reading the site’s files, cutting them into passages, building a prompt from what comes back, and getting llama3 to answer from it and cite its sources. Chapter 6 puts the pieces together into a working assistant and runs it on real questions.