sql/vecindex: performance exploration arc — what worked and what didn't (SIMD, query prep, KV pushdown)

**Summary:**

This issue catalogues a multi-week performance exploration of C-SPANN vector search (`pkg/sql/vecindex`), documenting both the optimizations that paid off and the ones that didn't — each with benchmarks. The goal is to give anyone working on vecindex perf a map of the terrain: which ideas to build on, and which ground has already been covered without result.

Environment unless noted: single-node Apple M-series for memstore/SQL microbenchmarks; multi-node roachprod (3× server + 1 loadgen) on GCE `t2a-standard-4` (arm64) and `n2-standard-4` (amd64) for cluster benchmarks. Primary datasets: `dbpedia-openai-100k-angular` and `dbpedia-openai-1000k-angular` (1536-dim). Tools: `pkg/cmd/vecbench` (`--memstore` and SQL provider) and `pkg/workload/vecann`. Recall reported as recall@10.

---

**What worked (with benchmarks):**

**1. ARM64 NEON SIMD kernels for the float32 vector primitives** (#152090, #152091)

Profiles showed ~38% of search CPU in `num32.Dot`/`SquaredNorm`/`MinIdx`/`MaxIdx` and gonum axpy/scal fallbacks, nearly all from `RaBitQuantizer.EstimateDistances`. Hand-written NEON kernels (16 floats/iteration, 4 independent accumulators to hide FMLA latency):

- Microbench (1536-dim): `Dot` 461ns → 34ns; `Quantize` 2.2×; `EstimateDistances` 1.8×.
- End-to-end memstore, `dbpedia-100k`: **1.7–2.1× search QPS at identical recall** across beams (beam 32: 1107 → 1929 QPS, p50 0.89ms → 0.51ms); ~15% faster index build.
- Caveat: Go assembler has no FP-vector mnemonics (FADD/FSUB/FMUL/FMINNM/FMAXNM) — emitted as `WORD` directives behind `#define` macros. SIMD reductions sum in a different lane order, so results differ from generic in the final ULPs; two exact-expectation tests were loosened to tolerances.

**2. Quantize the query once per operation, not once per partition** (#152097)

`EstimateDistances` re-derived and re-quantized the query for every partition visited (7 passes over the query vector each). Hoisted out via the RaBitQ split-query identity ` = ( − ) / ‖q−c‖`, with the query-independent `` factor (CodeCentroidDots) computed at quantization time.

- Memstore, `dbpedia-100k`: **+11–22% search QPS at recall parity** (beam 16: 3137 → 3817 QPS @ 86.99% vs 86.82%); build ~15% faster.
- A near-centroid fallback (‖q−c‖ < ‖q‖/2) bounds query-quantization error amplification; without it, offset-euclidean data (`fashion-mnist-784`) showed a ~0.2pp recall ceiling gap.

**3. Persist CodeCentroidDots in the KV encoding so the SQL path benefits** (#152097)

The factor above was memstore-only until persisted. Added to the per-vector KV entry behind a version-byte discriminator (legacy entries always begin with `0x00`, new format prefixed `0x01`; mixed partitions fall back safely), gated on a cluster version.

- SQL A/B (same binary, env toggle), `dbpedia-100k`: **+2–12% QPS** (largest at small beams), tail latency up to **−22% p95**, recall within noise. Gains are smaller than memstore because the SQL path also pays KV reads and re-rank.

**4. Push partition scoring down to the leaseholder** (#152100) — the big win

Search previously shipped every candidate partition's raw quantized rows (~10–20× wire size) to the gateway for scoring. A new read-only ranged `VectorSearchRequest` scores at the replica and returns only small scored tuples (~16B each).

- Multi-node A/B, `dbpedia-100k`, beam sweep 8–128, cluster setting `sql.vecindex.pushdown.enabled`:
- **Inter-node network: amd64 ~74% reduction** (15.6/16.4 GB on vs 60.6/62.3 GB off), **arm64 ~57%**.
- Latency: amd64 (low RTT) **p50 −2.9% → −22.3%** growing with beam, **QPS +2.6% → +28.4%**; arm64 RTT-floored (worker→region distance) so compressed but correctly signed.
- **Recall exact parity on/off on both arches** — server-side scoring returns bit-identical rankings to the raw-fallback path (key correctness result).
- ~9–11% of partitions hit the raw-fallback path (near-centroid / root partition) across both arches.

---

**What didn't work (with benchmarks):**

**1. NEON popcount kernel for the RaBitQ 4-plane loop — negative**

The popcount loop is the top remaining cost in `EstimateDistances`. A correct NEON kernel was **slower than scalar on Apple Silicon: 13.7ns vs 7.8ns per 1536-dim code**, because Go already intrinsifies `bits.OnesCount64` to the NEON `CNT` instruction per word, letting the scalar loop use both scalar and vector pipes. Not integrated. Revisit **only** for x86 AVX-512 `VPOPCNTQ` (8×64-bit popcounts/instruction).

**2. NEON query-quantization kernel in isolation — marginal**

The split-out quantization arithmetic (FSUB/FDIV/FADD/FRINTM, bit-exact) is **5.1× faster on the op (865ns → 169ns, 1536-dim)** but delivered only **~1–2% end-to-end** (within noise), because the remaining scalar bit-plane packing chain then dominates the packing region. It became worthwhile only once combined with win #2 (hoisting query prep out of the per-partition loop).

**3. SIMD does not raise the aggregate throughput ceiling — the most important negative**

Hypothesis: under a saturated cluster where CPU runs hot, SIMD's contribution to scoring would surface as higher total throughput. Tested directly with a `crdb_nosimd` build tag (hand-written SIMD kernels → scalar/gonum fallback) for a same-cluster A/B, `dbpedia-openai-1000k-angular`, concurrency sweep [1,4,16,32,64,128,256,512], 45s/point. Run first on **identical arm64 hardware** (NEON vs scalar), then reproduced on **identical amd64 hardware** with hand-written AVX2+FMA kernels vs the `crdb_nosimd` scalar/gonum path.

| config | c=1 QPS | ceiling QPS | knee |
|---|---|---|---|
| arm NEON | 63 | ~560 | c=256 |
| arm scalar (`crdb_nosimd`) | 59 | ~553 | c=256 |
| amd AVX2 | 107 | ~640 | c=128 |
| amd generic (`crdb_nosimd`) | 105 | ~640 | c=128 |

- **On both arches, SIMD vs no-SIMD are within run-to-run noise at every concurrency >1, at identical CPU%.** arm NEON vs scalar: ratios 0.97–1.06. amd AVX2 vs generic (matched warm-start protocol, back-to-back on the same `n2-standard-4` cluster): +2.2% at c=1, then −1.5% to +0.7% at c≥16 — the lines cross. SIMD's only real win is single-query latency at c=1 (~7% arm, ~2% amd).
- The amd rows use a warm-start protocol (60s warmup before each sweep) so their absolute QPS sits above the arm rows; the point is the *within-arch* delta, and both arches show the same null result. The amd microbenchmarks confirm the AVX2 kernels themselves are fast (1536-dim, ns/op: `Dot` 1810→137 ≈13×, `L2SquaredDistance` 1824→139 ≈13×) — they just don't move the aggregate ceiling.
- Throughput plateaus at **~54–59% measured CPU** on both arches — the system stops scaling *before* CPU saturates. The ceiling is set by **per-query latency (sequential multi-level C-SPANN tree descent), not distance-scoring speed.**

**Implication:** scoring CPU is a small fraction of per-query cost at scale. SIMD is still worth keeping (single-query latency, and minimizing footprint so other work isn't starved of cycles), but it is not a throughput lever. The throughput levers are (a) cutting data shipped across the network — the KV pushdown win above — and (b) reducing per-query descent latency/coordination.

**4. Adaptive search (Z-score beam sizing) is not a reliable throughput lever — negative**

Follow-up to negative #3 (the throughput ceiling is per-query descent latency, not scoring CPU). Adaptive search is an existing, currently-disabled mechanism (`DisableAdaptiveSearch=true` in `manager.go`) that sizes each level's beam by the Z-score of the parent results' distance spread — `adjustedBeamSize = beamSize * 2^(-zscore)`, clamped to `[beam/2, beam*2]` (`searcher.go`). The hypothesis was that shrinking the beam on easy queries would buy recall that could be cashed back as throughput at a lower beam.

**Methodology (the load-bearing correction):** an optimization that changes the accuracy/work trade-off must be judged at **fixed recall** (leaf-scans@recall, or qps@recall), never at fixed beam — beam is only the dial used to reach an operating point, and an optimization that raises recall is a legitimate *throughput* candidate because you can lower the beam to give the recall back. Recall is also squirrelly: rebuilding the same dataset with a different seed reshuffles the partitioning and swings recall by several points, so a single build is not enough. We therefore built **8 seeds** each of `dbpedia-openai-100k-angular` and `fashion-mnist-784-euclidean` (each build done with adaptive **on** so the global `CVStats` are warm), then beam-swept the *same* index adaptive-OFF vs adaptive-ON and interpolated leaf-scans and qps at fixed recall per seed (per-seed stdev on leaf-scans@recall is tiny, ±0.5–1.3%).

Result — adaptive-ON minus adaptive-OFF, as a % (negative leaf-scans = adaptive better; positive qps = adaptive better):

| recall | dbpedia leaf | dbpedia qps | fashion leaf | fashion qps |
|---|---|---|---|---|
| 88% | −5.7% (help) | +11.5% | +8.3% (hurt) | −2.8% |
| 90% | −2.2% (help) | +9.6% | +9.3% (hurt) | −2.7% |
| 95% | +10.8% (hurt) | −6.0% | −2.0% (help) | +5.4% |
| 99% | +34.2% (hurt) | −23.6% | −17.1% (help) | +18.6% |

- The two datasets are **near mirror-images: the sign is opposite at every shared recall level.** dbpedia helps below ~91% recall and hurts above; fashion hurts below ~92% and helps at/above ~95%. **No recall operating point wins on both datasets.**
- Adaptive is *not* inert — it produces real, several-percent wins per dataset — but which direction it moves is dataset- and operating-point-dependent, so it cannot ship as a fixed default; it would need per-workload calibration to be safe.
- **Decisive point (still holds):** beam size only changes *partitions-per-level* (rows scanned), never the *level count*. The 3-level descent stays 3 levels regardless of beam, so even where adaptive helps it cannot remove a single sequential RTT — it operates on the exact rows-per-batch axis that negative #3 already showed does not move the distributed ceiling.

**Implication:** adaptive search is a dataset-dependent accuracy/work knob, not a reliable throughput default, and does not justify the KV-path plumbing it would require (persisting `IndexStats` in KV, wiring the global stats-merge trigger — `OnAddOrRemoveVector`, reachable today only via `Index.Insert/Delete`, not the production `SearchForInsert/SearchForDelete` DML path — a version gate, async best-effort stats write, and a live kill-switch). The remaining descent-latency lever is cutting the RTT *count* itself, not the work per RTT (see next steps). Full writeup and the reusable seed-sweep harness: `docs/tech-notes/vecindex-kv-pushdown/results/adaptive-search.md`.

---

**Next steps / open questions:**

- [x] Add amd64 AVX2 SIMD kernels for `num32` (`Dot`/`SquaredNorm`/`L2SquaredDistance` + element-wise add/sub/mul/scale; 8-lane YMM, 4 FMA accumulators, runtime `cpu.X86.HasAVX2 && HasFMA` dispatch). Done and confirmed above: ~13× on the scoring microbenchmarks but no change to the aggregate throughput ceiling (same null result as NEON). Query-quantization was intentionally left scalar on x86 (it was the ~1–2% NEON non-result). Remaining x86-only opportunity: RaBitQ popcount via AVX-512 `VPOPCNTQ` (8×64-bit popcounts/instruction) — the exact kernel that was a *negative* on NEON; still worth trying since it targets the top remaining scoring cost, though the ceiling result above tempers expectations for throughput.
- [ ] Quantify pushdown's isolated win at 1M scale with a `sql.vecindex.pushdown.enabled=false` comparison sweep.
- [x] Attack the descent-latency ceiling via **adaptive search** — negative, see "What didn't work" #4. Adaptive beam sizing changes work-per-level, not the level/RTT count, so it cannot lower the RTT-bound ceiling; left disabled.
- [ ] Attack the descent-latency ceiling via **cutting the RTT count** (the live lever): cache the root + upper-interior (level-2) partitions on the gateway with bounded staleness (async background refresh) so the descent scores them locally, eliminating 1–2 of the ~4 sequential round-trips. Correctness holds because stale structure degrades a *query* to recall loss, not incorrectness, and serving is gated to read-only searches (inserts/deletes/fixups still read consistently). Unlike adaptive search this targets the level/RTT count directly. Note: the originally-paired idea of fusing the rerank / full-vector fetch into the leaf batch was found **not viable** on the SQL path — the SQL searcher sets `SkipRerank`, so the rerank is a mandatory, data-dependent `LookupJoin` to the primary index that fetches user-selected columns and cannot be folded into the leaf `SearchPartitions` batch.
- [ ] Reduce KV serialization/transport cost (shipping raw KV byte blocks rather than separately-encoded rows) — the same slow-scan / byte-movement bottleneck that limits OLAP scans; complementary to pushdown.
- [ ] Investigate the ~9–11% raw-fallback rate (near-centroid / root-partition path) — is it reducible?

**Related:** #152090, #152091, #152097, #152100, #143106 (meta)

Epic CRDB-42943

Jira issue: CRDB-67015

Start with the existing results in docs/tech-notes/vecindex-kv-pushdown/results/adaptive-search.md and the vecindex entry points manager.go and searcher.go. Use pkg/cmd/vecbench and pkg/workload/vecann to understand the documented benchmark methodology, then choose and scope one open question such as the 1M-scale pushdown comparison. Done means the selected experiment has reproducible results and the findings are recorded with the relevant benchmark context.

Written by the indexing model from the issue text.