Benchmarking vector indexes

Nearly every database has vector search now, and every one of them has a blog post with a big number in it. Almost none of those numbers can be checked, because the thing that makes them meaningful is usually missing. We built a vector-bench to stop guessing. You name the engines you want, build them from pinned versions, put each one in the same container on the same cores with the same data, run the same measurements against all of them, and write a report. This post is about how it measures. If you work with databases but haven’t touched vectors yet, the first half is the part you need. What’s being indexed An embedding is a fixed-length array of floats that comes out of a model. The useful property is that semantically similar inputs land close together when you measure the distance between them. Two distance measures cover almost everything. L2 is an ordinary straight-line distance, the Pythagorean one, extended to however many dimensions you have. Cosine Similarity  measures the angle between two vectors and ignores their length. Which one applies is decided by the model that produced the embeddings. It isn’t a choice you get to make at query time, and getting it wrong is a good way to produce nonsense. So the query you want is “the 10 rows whose vectors are nearest this one”: MySQL 1 SELECT id FROM documents ORDER BY distance(embedding, ?) LIMIT 10; That 10 is k. Now the problem. Answering that exactly means computing the distance from your query vector to every single row, then sorting. No B-tree or hash index helps, because neither one can order a million points by proximity in 1536 dimensions. Exact vector search is a full table scan with a lot of arithmetic bolted on. A vector index gives up exactness to avoid that. It looks at a few thousand promising candidates instead of every row and returns the best it found. That’s the approximate nearest neighbour search, or ANN. It’s usually right. “Usually” is doing a lot of work in that sentence, and pinning it down is most of what this benchmark does. To score that you need to know the right answer in the first place. That’s the ground truth: the true nearest neighbours for every query, computed once by brute force with no index involved. The public ANN datasets ship theirs alongside the vectors, and without it you couldn’t score an approximate index at all. This is the number that makes everything else meaningful, and it’s the one most vector search claims leave out. That omission is the reason this project exists. The two kinds of vector index Almost every database that has added vector search picked one of two designs. They attack the same problem from opposite ends, and which one you have decides what you’re allowed to tune. HNSW HNSW stands for Hierarchical Navigable Small World, which is a mouthful for something fairly intuitive. If you’ve ever implemented a skip list, you already have the shape of it. It’s a graph of vectors built in layers. Every vector is a node, linked to some number of its nearest neighbours. The top layer has few nodes and its links jump long distances across the data. Each layer below has more nodes and shorter links. A search starts at the top and keeps hopping to whichever neighbour is closer to the query. When nothing is closer, it drops a layer and carries on, until it runs out of layers. Two settings matter: M is how many links each node keeps. It’s fixed when the index is built. Higher M means a better-connected graph and better recall, at the cost of a slower build and a bigger index. ef_search is how many candidates the search keeps track of while it walks. It’s a session variable, so you can change it per query. Turn it up and the search visits more nodes, gets better recall, and runs slower. There’s ef_construction too, the same idea applied while the index is being built. Not every engine lets you set it, which turns out to matter when you try to compare them fairly. IVF IVF stands for Inverted File. It partitions the data instead of linking it, not unlike list partitioning on a table. At build time it groups the vectors into nlist clusters, each with a representative vector at its centre. At query time it compares the query against those representatives, picks the closest nprobe clusters, and searches only inside them. It builds much faster than HNSW and uses less memory, but usually gives worse recall at the same speed. It misses when the true neighbour happens to sit just outside the clusters it looked in. We only test engines running HNSW, which is what most databases shipped. Putting an IVF engine on the same chart would mostly measure the gap between two algorithms rather than how well anybody implemented one, so IVF-only engines get their own bucket. Why one number is never enough Recall isn’t a property of an engine. It’s a setting, and ef_search is the dial. Here’s one HNSW index on one machine, same data, same queries. The only difference is that on the first row the search tracks 10 candidate nodes as it walks the graph, and on the second it tracks 800: 12 ef_search=10 3,678 queries/sec recall 0.9593ef_search=800 409 queries/sec recall 0.9987 Keeping 800 candidates instead of 10 finds a better answer and takes nine times as long. Both rows are honest measurements of the same index on the same hardware. Which is why “our database does 3,678 vector queries a second” tells you nothing. You don’t know how often it was handing back the wrong rows, and the person quoting it may not know either. The reverse is just as empty: recall with no throughput next to it is free, because recall 1.0 is always available if you turn the index off and scan the table. Every measurement here is a pair. If you take one thing from this post, take that. What the harness puts on each engine One table per engine. An id, an integer tag column used only by the filtered tests, the vector, and an HNSW index on it at a configured M. MySQL 12345 CREATE TABLE t1 (id INTEGER PRIMARY KEY,tag INTEGER NOT NULL,v VECTOR(1536)); Then two queries, plain top-k and the same search restricted to a subset of rows: 12 SELECT id FROM t1 ORDER BY distance(v, ?) LIMIT 10;SELECT id FROM t1 WHERE tag < ? ORDER BY distance(v, ?) LIMIT 10; tag holds values 0 to 99 spread evenly, so tag < 10 passes about 10% of rows and tag < 1 about 1%. That’s how we control selectivity. Every engine writes all of this differently. Some declare the index inside CREATE TABLE, others want a separate CREATE INDEX, and the distance functions have different names everywhere. Translating that is the driver’s job, and the drivers are the only engine-specific code in the whole harness. Every engine also has at least one setup detail that will quietly wreck your numbers. PostgreSQL, for instance, stores oversized values out of line in what it calls TOAST, and a 1536-dimension vector counts as oversized. Unless the column is set to STORAGE PLAIN, every single distance comparison pays for an extra fetch. It’s one line of DDL. Miss it and you publish PostgreSQL looking slow for a reason that has nothing to do with its vector search, and you’d never know from the results. What we measure Recall against throughput. Iterate ef_search against a fixed index, record recall and QPS at each point, repeat at a few values of M. k=10 throughout. The query vectors come from the dataset’s own held-out query set, never from the rows we loaded, because searching for a vector that’s already in the index is a much easier problem and would flatter everybody equally. The two settings behave completely differently, and it shapes how long a run takes. ef_search is a session variable, so iterating it reuses the index that’s already built and each extra point costs almost nothing. M is baked into the index, so every value of M means dropping the table and loading the entire dataset again. On a million 1536-dimension vectors that’s hours per value. Hence many ef_search points and very few M values. Build cost. Wall time, rows per second, index size on disk, peak memory. This is the easiest place in the whole benchmark to publish a misleading number, because engines don’t build the index the same way. Engines can build indexes either incrementally, bulk, or both. What does that mean? Incremental. The graph is updated on every INSERT. Loading is slow, but when the last row lands the index is finished and the table is ready to query. Bulk. All the rows load first, then the whole graph gets built in one pass. Much faster in total, but the table can’t answer a vector query until the build finishes. Those are two different operations. One engine in our set does both, and its bulk path loaded 18 times more rows per second than its own incremental path. Same engine, same data, same machine, 18x apart. So a bulk number from one engine put next to an incremental number from another doesn’t compare engines at all. It compares two ways of building an index, and the ratio looks impressive enough that people quote it anyway. We measure both paths on any engine that has both, and the report says which is which. Peak memory comes from the server’s container, with the database as the only thing running in it. The harness runs in a separate container and reaches the server over a private network. That separation matters more than it sounds. The client holds the entire dataset in memory, several GB of Python arrays. If it shared a container with the database, the container’s memory accounting would count those arrays as database memory, and every memory figure we published would be inflated by whatever the client happened to be holding.