Epic: vector search — add the recall axis and make cross-engine numbers comparable

[emmanuel-keller]

Tracking issue for finishing the vector-search benchmark. #242 shipped the Bruteforce / HNSW / DiskANN legs and #251 moved them into config/vector.toml. The config surface, holdout query set, per-engine index DDL, build timing and skip semantics all work. This epic covers what is still needed before the numbers are worth publishing.

Origin: #254, which asked for vector benchmarks including "recall@K against a brute-force ground truth". The legs shipped; the recall axis did not.

The problem

An ANN index has a free parameter — ef_search, l_search — that buys latency with accuracy. Turn it down and any index wins any latency comparison. crud-bench currently measures only latency:

• scan_vector_u32 / scan_vector_string return Result<usize>, a row count (src/engine.rs:230-247). The returned ids go to black_box and are dropped.
• OperationResult carries latency percentiles and nothing else (src/result.rs:597-614).

So today's vector rows report how fast an index returns something, with no way to tell a fast index from a broken one. Three legs sitting at three unknown accuracy points are being compared on latency alone.

A single point per algorithm is also the wrong deliverable even once recall exists. ef_search = 64 is one arbitrary spot on a curve; the useful comparison is the curve — what recall an engine reaches at a given latency budget.

Design decision: where ground truth comes from

Two candidates, and the choice depends on what the numbers are for.

The engine's own bruteforce leg as oracle is free and works fine for regression tracking. Where an engine's exact and approximate paths share a distance implementation, a bug is shared and recall still answers "how well does this index approximate exact search under the metric this engine actually implements". Redis satisfies that by construction (one redis_distance_metric feeds both the FLAT and HNSW FT.CREATE, and FLAT is an exact index over the same code). pgvector nearly does — pgvector_ops_for and pgvector_op_for are paired by pgvector's design, and a mismatch declines the index and seq-scans rather than corrupting results.

SurrealDB does not: the index comes from surreal_distance_keyword and the engine's own traversal, while the bruteforce leg is SQL crud-bench assembles from surreal_distance_function + surreal_distance_order (src/surrealdb.rs:97-133) — our code, used by nothing else. 02590bd was exactly a fault in that function, and note which way it fails: the index path was fine, so a self-oracle would have reported near-zero recall for HNSW and DiskANN and sent someone hunting in the wrong codebase.

For cross-engine comparison a self-oracle is disqualifying, which decides it. Recall against engine X's exact search and recall against engine Y's are not the same quantity. A quirk shared between an engine's exact and approximate paths scores high recall against its own slightly-off exact answer while a stricter engine scores lower for identical real quality; and divergent metric definitions leave every engine at ~1.00 against itself with nothing to reveal it. Published ANN comparisons compute ground truth once from the dataset, independent of the engines under test, and a recall number sourced from the engine being measured will be challenged.

Decision: one harness-computed oracle, shared by every engine. It also subsumes the self-oracle — each engine's exact leg gets scored against it too, so bruteforce recall becomes a reported column that should read 1.000, and anything less is a metric divergence or an engine bug surfaced rather than hidden.

The cost is smaller than it looks, because seeding the corpus changes what ground truth is: once the corpus is a pure function of a seed, exact top-k is a pure function of (corpus seed, N, dim, metric, k, query seed) — computed once, cached to disk, reused across every engine and every run. It also removes code: generate the query vectors from their own seed and never insert them, and the read-back path in build_vector_query_set disappears along with its self-match bias and the "engine cannot surface vector reads" skip branch.

Phase 1 — make the numbers publishable

Blocking. Nothing below is worth doing first, and these only make sense landed together.

• Change the KNN return type from Result<usize> to hits (id + distance); keep the existing scan.expect length assertion on top
• Seed the corpus deterministically and record the seed in result metadata — ValueProvider currently seeds from entropy (src/valueprovider.rs:39), so every engine and every run benchmarks different data
• Generate query vectors from their own seed and never insert them, retiring the read-back holdout path
• Compute exact top-k in the harness, cached on the seed; score every engine's approximate and exact legs against it
• Handle ties — count a hit correct within an epsilon of the true k-th distance, or engines that break ties differently show recall gaps that are not real
• Add a clustered vector generator and make it the default; vector:<dim> currently draws every component uniformly (src/valueprovider.rs:424-434), and under distance concentration at 128–3072 dims points are near-equidistant, so graph ANN builds a near-random graph and nothing transfers to real embeddings
• Add a loader for a recognised ANN dataset — competitive numbers will be judged against one
• Report recall (mean and p5) beside latency in the CLI table, CSV, JSON and compare/index.html
• Postgres: hnsw.ef_search is set on one session only, so most KNN clients query at the pgvector default #281 — Postgres ef_search reaches one session in twelve

Phase 2 — complete the tradeoff picture

• Accept a list for the search knob (ef_search = [16, 32, 64, 128, 256]) expanding to several timed runs over one index build — that is the recall/latency curve, at the cost of one build rather than five
• Index footprint per engine: pg_relation_size, FT.INFO's vector_index_sz_mb, on-disk delta for SurrealDB. Build time is already captured (src/result.rs:153); size is not, and it is the axis DiskANN exists to win
• Post-build and post-query RSS, as requested in Feature request: vector-search benchmarks (HNSW + DiskANN) — current scenarios skip the production-critical axis #254 — the OOM characterisation is the point
• Derived figures worth reporting directly: recall at a fixed latency budget, latency at a fixed recall target

Phase 3 — coverage

• pgvectorscale diskann on Postgres — DiskANN currently runs only on SurrealDB (src/surrealdb.rs:755-763), so that column is a self-benchmark with two blanks
• Filtered KNN at several selectivities. The dominant production shape, and where engines diverge most because pre-filter, post-filter and filtered traversal degrade in completely different ways. Ground truth has to be computed per filter
• Dedicated vector engines: Qdrant, then Milvus or Weaviate, then LanceDB
• Insert-into-live-index throughput — where SurrealDB's CONCURRENTLY build has a story worth telling
• Scale tiers and the F16 / I8 element types from Feature request: vector-search benchmarks (HNSW + DiskANN) — current scenarios skip the production-critical axis #254

Phase 4 — hygiene

• SurrealDB: DiskANN search failures are downgraded to NotSupported and render as a clean skip #282 — DiskANN failures hidden as clean skips
• --skip-indexes does not skip vector index builds #283 — --skip-indexes ignores vector index builds
• Revisit the 3072-dimension default in config/vector.toml. At 12 KB per row it turns every create, read and update leg in that config into a vector-payload benchmark. Possibly intentional, but should be a documented choice

Open calls

• Where the ground-truth cache lives: beside each result JSON, or a shared directory keyed on the seed so a six-engine comparison computes it once. The latter is the point of caching but needs a stable location and an invalidation rule
• Whether recall joins OperationResult or sits in a vector-specific sibling — affects --store-results, CSV column order and compare/index.html
• Which recognised dataset. A small standard set keeps CI fast and is the most quotable; a larger one is more representative but adds a download step and minutes per run. Both can coexist