RinhaDeBackend::Ivf

IVF runtime query against the AOSOA-8 dim-interleaved block layout produced by IvfBuilder. Reads the centroids, cell-to-block offsets, and the block-major reference data through the mmapped binary file.

Query algorithm:

1. Compute distance from query to each of the k centroids.
2. Pick the nprobe nearest centroids.
3. Scan the blocks in those nprobe cells with the multi-stage AOSOA-8 inner kernel + insertion-sorted top-K.

Three cell-level early-exits are applied between cells:

a. Triangle-inequality pruning. For each probed cell c with centroid distance D_c = sqrt(centroid_dist_sq[c]) and precomputed radius R_c (max distance from centroid to any vector in c), no vector in cell c can beat the current top-5 worst distance W if (D_c - R_c)² >= W (and D_c > R_c). Skip the whole cell.

b. Per-cell bounding-box pruning. Tighter than (a) in high-dim corners. For each probed cell c with bbox [bbox_min[c], bbox_max[c]], the minimum possible squared distance from query to any vector in the box is sum_j max(bbox_min[c][j] - query[j], 0, query[j] - bbox_max[c][j])². If that already >= W, skip the cell. Exact pruning.

c. Decision-aware outer break. Probed cells are sorted ascending by D_c. Once the next probed cell satisfies (D_{p+1} - R_max)² >= W with R_max = max_cell_radius, no remaining cell can possibly displace the current top-5. The fraud count is locked — break.

Inside each block (AOSOA-8 dim-interleaved):

• 8 vectors per block, dim-interleaved as [d0_v0..d0_v7, d1_v0..d1_v7, ..., d13_v0..d13_v7]. With --mcpu=haswell --mattr=+avx2,+fma LLVM lowers the per-dim 8-wide squared-difference loop to (i32 path):

  vpmovsxwd ymm0, [block + d*16] ; 8 i16 → 8 i32 vpsubd ymm1, ymm0, ymm_qd ; 8 i32 differences vpmulld ymm2, ymm1, ymm1 ; 8 i32 squares vpmovsxdq ymm3, ymm2_lo ; 4 i64 widened vpaddq ymm_acc_lo, ymm_acc_lo, ymm3 vextracti128 + vpmovsxdq ymm4 ; 4 i64 high half vpaddq ymm_acc_hi, ymm_acc_hi, ymm4

  producing 8 partial squared distances per dim instead of 1 squared distance per row in the old layout.

• Multi-stage early exit at d=4 and d=8: if every one of the 8 partial sums already exceeds the current top-5 worst, skip the remainder of the block.

• Top-5 insertion sort runs once per block, scanning the 8 finished partial sums against worst. Slots that early-exited have all-lanes >= worst, so the same scan correctly admits nothing.

Pad slots and alignment-pad blocks (carrying IvfBuilder::PAD_SENTINEL = Int16::MAX on every lane) produce squared distances ≥ ~7.3 × 10⁹ vs any production query (lanes ∈ [-10000, 10000]) — well above any real worst-case real-row L² (~5.6 × 10⁹) — so they cannot enter the top-5 ranking and the block scan needs no per-slot validity bookkeeping.

All three cell skips preserve exact answers: no recall loss, just CPU saved.