12.6.3 — Vector Search at Scale

Cartwise's catalogue has 10 million products, each embedded as a 384-number vector by the model in 12.6.2. At the evening peak, the search bar receives about 2,000 queries a second, and each must return results within about 100 milliseconds, including everything else the search service does. The vector part of the job gets perhaps 20 of those milliseconds.

The straightforward way to search is to compare the query with every product and keep the best. That is the exact k-nearest-neighbour search of 12.3.5, and it is worth costing before dismissing:

• Memory to scan. 10 million vectors × 384 numbers × 4 bytes ≈ 15.4 gigabytes, read in full for every single query.
• Arithmetic. 10 million dot products of 384 multiplications each ≈ 3.8 billion multiply-adds per query.
• Time. Reading 15 gigabytes at a typical server memory speed of a few tens of gigabytes per second takes a large fraction of a second, per query.

At 2,000 queries a second, that is thousands of times more work than one machine can do. The way out is to give up a guarantee that turns out not to matter: instead of finding the nearest products with certainty, find products that are almost certainly among the nearest, while checking only a tiny fraction of the catalogue. That is approximate nearest neighbour search, ANN for short, and every vector database is built on it.

1. How to measure an approximate search

Before choosing an index, you need a way to measure how much accuracy you have traded. The standard measure is recall@k: run the exact search and the approximate search for the same queries, and ask what fraction of the true top k results the approximate search found. If the exact top 10 for a query are 10 particular products and the index returns 9 of them, recall@10 is 0.9. Averaged over a test set of queries, a good production index is typically tuned to a recall@10 of around 0.95 to 0.99, at a tiny fraction of the cost.

Notice that this is recall of the index, measured against exact vector search, not the relevance of results to the customer. A perfect index faithfully returns the nearest vectors; whether those vectors are good products for the query is the embedding model's job. Mixing up the two is a common source of confused debugging: if search results are poor, first check whether exact search would have returned better ones. If it would not, no index tuning will help.

Every index below has a dial that trades recall against speed, and choosing an index is really choosing a curve and then a point on it.

2. IVF: search only the nearby neighbourhoods

The first idea is to sort the catalogue into neighbourhoods ahead of time, then search only the neighbourhoods near the query. This is an inverted file index, or IVF. ("Inverted file" is an old search-engine term for an index that maps from a key to the list of items filed under it; here the key is a neighbourhood.)

An inverted file index. The space is split into cells around centroids found by k-means. A query is compared with the centroids, then only with the products in the few nearest cells (green); everything else is skipped. Opening more cells raises recall and cost together.

Building it. Run the k-means clustering from 12.3.6 on the product vectors to find, say, 4,096 centroids. File every product under its nearest centroid. Each centroid's list holds on average 10{,}000{,}000 / 4{,}096 \approx 2{,}441 products.

Searching it. Compare the query with the 4,096 centroids, pick the few nearest, and compare the query exactly only with the products filed under those. How many cells to open is the dial, usually called nprobe. With nprobe = 16, the search makes 4{,}096 + 16 \times 2{,}441 \approx 43{,}000 comparisons instead of 10 million: about 230 times less work.

Why open more than one cell? Look at the query in the figure. It sits near the border of its cell, so some of its true nearest neighbours live in the cell next door. Opening only the single nearest cell would miss them. Opening the 16 nearest catches nearly all of them. Raising nprobe raises recall and cost together, and you tune it on a test set until recall@10 reaches your target.

IVF is simple and memory-efficient, but it must be trained (the k-means step) on data that looks like the real catalogue, and if the catalogue changes a lot, for example a whole new product category arrives, the cells stop fitting the data and the index needs rebuilding.

3. HNSW: a road network for vectors

The most widely used ANN index today is HNSW, which stands for hierarchical navigable small world, published by Yury Malkov and Dmitry Yashunin in 2016. It is a graph: every product is a node, linked to a handful of nearby products. To search, you start somewhere, look at your current node's neighbours, move to whichever neighbour is closest to the query, and repeat until no neighbour is closer. Walking a graph greedily like this is fast, because each step only checks a few neighbours.

A single flat graph has a problem: if you start far from the query, the walk takes many small steps to cross the space. HNSW solves this the way road networks do.

HNSW as a road network. The top layer holds a few products with long links, the bottom layer holds every product with short local links. A search (red) takes a long jump on the top layer, drops down, takes shorter jumps, and finishes with a few local steps on the bottom layer.

Every product is in the bottom layer, with short links to its close neighbours, like local streets. A random fraction of products are also placed in the layer above, with longer links, like main roads; a smaller fraction again in the layer above that, like motorways. A search starts at the top, takes a few long greedy jumps towards the query, drops to the next layer from wherever it ended up, takes shorter jumps, and finishes on the bottom layer with a few precise local steps. The number of steps grows roughly with the logarithm of the catalogue size, so ten times more products means only a few more steps. The "small world" in the name refers to networks where any two nodes are connected by a short chain of links, like the "six degrees of separation" between people.

HNSW has three settings that matter. M is how many links each node keeps: more links mean better recall and more memory. efConstruction is how hard the builder searches for good links when adding each product: higher means a better graph and slower building. efSearch is the dial at query time, how many candidate nodes the search keeps in play as it walks: higher means better recall and slower queries. HNSW typically gives excellent recall at very low latency and supports adding new products without a full rebuild, which is why it is the default in most vector databases. Its cost is memory: the links take extra space on top of the vectors, and the whole graph is usually kept in RAM.

4. Product quantisation: compress the vectors themselves

Both indexes above still keep the full vectors in memory, 15.4 gigabytes of them. Product quantisation, or PQ, shrinks the vectors themselves, and it works by an elegant idea.

Cut each 384-number vector into 48 short pieces of 8 numbers each. For each of the 48 positions, run k-means over all products' pieces at that position to find 256 typical pieces, a small "codebook". Now store each product's piece as just the number of its nearest typical piece, from 0 to 255, which fits in one byte. Each product becomes 48 bytes instead of 384 \times 4 = 1{,}536 bytes: 32 times smaller, and the whole catalogue drops from 15.4 gigabytes to under half a gigabyte. "Product" in the name refers to the mathematical idea of combining independent pieces, not to Cartwise's products.

Searching compressed vectors is fast too. For a query, compute in advance its distance to all 256 typical pieces at each of the 48 positions: a small table of 48 \times 256 numbers. The approximate distance to any stored product is then just 48 table lookups added up, one per piece, with no multiplication of long vectors at all.

The compression loses detail, so PQ is usually combined with the others: IVF to choose which cells to search, PQ to store the vectors in those cells cheaply, and then a final step that re-scores the best few hundred candidates using their full, uncompressed vectors from disk to get the exact order right. The simpler scalar quantisation from 12.6.2, storing each number in one byte instead of four, is a gentler 4-times saving and is often used with HNSW.

A third family is worth knowing by name: locality-sensitive hashing, which cuts the space with random flat planes and gives each vector a short code of which side of each plane it falls on, so that close vectors tend to get the same code. It was the classic approach and is simple to understand, but on modern embeddings graph and cluster indexes usually beat it.

5. In code: FAISS and pgvector

FAISS (Facebook AI Similarity Search) is an open-source library from Meta's research lab, released in 2017, that implements all of these indexes and is what many vector databases use underneath. Here is the IVF-plus-PQ combination on stand-in data:

import numpy as np, faiss

d, n = 384, 1_000_000
rng = np.random.default_rng(0)
X = rng.standard_normal((n, d)).astype("float32")
faiss.normalize_L2(X)                                       # (1) unit length: inner product = cosine

quantizer = faiss.IndexFlatIP(d)                            # (2) holds the centroids
index = faiss.IndexIVFPQ(quantizer, d, 1024, 48, 8,         # (3) 1,024 cells, 48 pieces, 8 bits each
                         faiss.METRIC_INNER_PRODUCT)
index.train(X[:100_000])                                    # (4) learn centroids and codebooks
index.add(X)                                                # (5) file and compress every vector
index.nprobe = 16                                           # (6) the recall dial

q = X[:5]
scores, ids = index.search(q, 10)                           # (7) top 10 per query
print(ids[:, 0])     # each query's top hit should usually be itself → [0 1 2 3 4] (typically)

Line (1) normalises every vector so that the inner product (FAISS's name for the dot product) equals cosine similarity, as 12.6.2 explained. Line (2) creates the small exact index that holds the cell centroids. Line (3) creates the IVF-PQ index: 1,024 cells, each vector cut into 48 pieces, each piece stored in 8 bits. Line (4) trains it, running k-means for the cells and for the 48 codebooks, on a sample of the data. Line (5) files and compresses all million vectors. Line (6) sets how many cells to open per query. Line (7) searches, returning the top 10 scores and product IDs for each query. Because the queries here are stored vectors themselves, their own ID should usually come back first; with compression it occasionally will not, which is exactly what recall measures.

For many companies, the simplest good answer is to keep vectors in the database they already run. pgvector is an extension for PostgreSQL, the database from Part 7, that adds a vector column type and HNSW and IVF indexes, so product vectors live in the same table as price and stock:

CREATE EXTENSION vector;
ALTER TABLE products ADD COLUMN embedding vector(384);                     -- (1)
CREATE INDEX ON products USING hnsw (embedding vector_cosine_ops);         -- (2)

SELECT id, title
FROM products
WHERE in_stock AND price < 5000                                            -- (3)
ORDER BY embedding <=> $1                                                  -- (4)
LIMIT 10;

Line (1) adds a 384-number vector column. Line (2) builds an HNSW index on it for cosine distance. Line (3) filters with ordinary conditions. Line (4) orders by cosine distance to the query vector passed in as $1; <=> is pgvector's cosine-distance operator. Putting vectors next to the rest of the data means one system to back up, secure and keep consistent, and pgvector handles tens of millions of vectors well. Dedicated vector databases such as Qdrant, Milvus, Weaviate or the hosted Pinecone earn their place at larger scales, with heavy filtering, or when you want vector search as a separately scaled service.

6. The problem every real system hits: filters

The SQL above quietly raises the hardest practical problem in vector search. Customers rarely want "the nearest products". They want "the nearest products that are in stock, under ₹5,000, and deliverable to my pin code". There are two naive ways to combine a filter with an ANN index, and both break.

Search first, filter after. Ask the index for the top 10, then remove the ones that fail the filter. If only 2 percent of products pass the filter, you will usually be left with nothing. Asking for the top 1,000 and filtering helps, but there is no safe number: a very selective filter can still empty it.

Filter first, search after. Find every product passing the filter, then search only those. With an exact search over the filtered set, this is correct, but if the filter keeps a million products, you are back to exhaustive search. And you cannot use the prebuilt graph or cells, because they were built over all products.

Real systems handle this inside the index: the search walks the HNSW graph or the IVF cells while checking each candidate against the filter, and keeps going until it has enough products that pass. Vector databases differ a great deal in how well they do this, and it is the most important thing to test when choosing one, using your real filters and their real selectivity. A common design choice that avoids the worst cases is to partition the index by a filter that is almost always applied, for example one index per country or per store, so that filters within each partition are less extreme.

7. Running it in production

A few operational facts decide whether vector search is pleasant or painful to run.

Updates and deletes. Products are added, edited and removed all day. HNSW handles inserts well; deletes are often only marked, with the space reclaimed when the index is rebuilt, so a heavily churning catalogue needs periodic rebuilds. IVF cells drift as the catalogue changes and need retraining occasionally.

Memory. HNSW wants the vectors and the graph in RAM. Budget for it explicitly: 10 million 384-number vectors are 15.4 gigabytes as 4-byte floats before the graph's links, or about a quarter of that with one-byte quantisation.

Re-embedding. As 12.6.2 explained, a new embedding model means new vectors for everything. Build the new index alongside the old one and switch over in one move.

Measuring. Keep a set of test queries with their exact top-10 results, and check the index's recall@10 after every rebuild or settings change. A silently degraded index looks exactly like a slightly worse embedding model.

What the interviewer will push on

"How does a vector database find nearest neighbours quickly?" They are checking that you know exact search is linear in the catalogue size and that ANN trades a little recall for huge speed. A good answer explains at least one index properly, IVF's cells and nprobe or HNSW's layered graph, and names the dial that trades recall for speed.

"How do you know the index is good enough?" They want recall@k against exact search on a held-out query set, and the distinction between index recall and result relevance. The common wrong answer conflates the two.

"How would you search ten million vectors with metadata filters?" This is the separating question. A strong answer explains why both post-filtering and pre-filtering break with selective filters, and mentions filtered graph traversal or partitioning by a common filter.

"How much memory does it need?" They are checking you can do the arithmetic: count × dimensions × bytes, plus index overhead, and how quantisation and PQ cut it.

Volunteer this: when search quality is poor, run exact search on a few failing queries before touching the index. If exact search also returns bad products, the problem is the embedding model or the text you embedded, and no index setting will fix it.

Recall

• Exact search over 10 million 384-number vectors reads about 15.4 GB per query, far too slow. Approximate nearest neighbour search checks a tiny fraction. Quality is measured by recall@k against exact search, which is index quality, not result relevance.
• An inverted file index (IVF) uses k-means cells and searches only the nprobe nearest cells: about 43,000 comparisons instead of 10 million in the example.
• HNSW is a layered graph like a road network: long jumps on sparse top layers, local steps at the bottom. Settings M, efConstruction, efSearch; fast, updatable, memory-hungry.
• Product quantisation cuts vectors into pieces stored as codebook numbers (48 bytes instead of 1,536) and computes distances by table lookup; usually combined with IVF and full-vector re-scoring.
• FAISS implements the indexes; pgvector adds them to PostgreSQL next to the rest of the data. Filters are the hard part: post-filtering empties results, pre-filtering loses the index; good systems filter during traversal or partition by common filters. Rebuild for deletes, budget RAM, re-embed on model changes, and track recall.

Self-test: With 8,192 cells over 10 million products and nprobe of 8, roughly how many comparisons does IVF make? A filter keeps 0.5 percent of products and you post-filter the top 100: how many results do you expect? How many bytes does PQ use per vector with 64 pieces of 8 bits?

Next: 12.6.4 Keyword and Hybrid Search — embeddings understand meaning but blur exact details like model numbers and sizes; the last search page brings back keyword search, explains how it handles typos, and combines both into the hybrid search real systems use.