GCC Code Coverage Report


Directory: src/
File: src/index/query_scan.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 300 314 95.5%
Functions: 16 16 100.0%
Branches: 126 152 82.9%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * query_scan.c - Shared query execution for ANN search
6 *
7 * Beam search over centroids, posting list scan with RaBitQ
8 * scoring, and candidate extraction. All buffers are pre-allocated
9 * in init; the per-query path does zero allocations (except rare
10 * topk candidate buffer growth).
11 */
12
13 #include "vs_config.h"
14
15 #include <float.h>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <string.h>
19 #include <time.h>
20
21 #include "algo/topk.h"
22 #include "algo/vecops.h"
23 #include "core/injection.h"
24 #include "core/log.h"
25 #include "core/memory.h"
26 #include "core/platform.h"
27 #include "index/centroid_search.h"
28 #include "index/posting_page.h"
29 #include "index/posting_scan.h"
30 #include "index/query_scan.h"
31 #include "quant/rabitq.h"
32
33 /* ----------------------------------------------------------------
34 * Init / cleanup
35 * ---------------------------------------------------------------- */
36
37 /* Byte budget for the references a spilled probe re-rank keeps for the scan
38 * pass (probe_refs). Without it the buffer is nprobe * dim floats, which a
39 * query can push past 100 MB by raising nprobe. */
40 #define PRISM_PROBE_REFS_MAX_BYTES ((size_t)16 * 1024 * 1024)
41
42 void
43 20794 prism_query_state_init(
44 PrismQueryState *qs,
45 PrismIndexBase *index,
46 uint32_t max_k,
47 uint32_t max_nprobe)
48 {
49 20794 memset(qs, 0, sizeof(*qs));
50 20794 qs->index = index;
51 20794 qs->max_k = max_k;
52 20794 qs->max_nprobe = max_nprobe;
53
54 20794 prism_index_ensure_rabitq(index);
55
56 /*
57 * Everything below is allocated here, including the contexts the top-k
58 * and the centroid scratch create for themselves, so that the whole
59 * state can be released at once. Parented to the caller's current
60 * context, so a caller that never calls cleanup still loses it with
61 * whatever scope it allocated the state in.
62 */
63 20794 qs->memctx = vs_memctx_create(NULL, "vs query state");
64 20794 VsMemCtx caller_ctx = vs_memctx_switch(qs->memctx);
65
66 20794 Dimension dim = index->dim;
67 20794 uint32_t packed_bytes = VS_RABITQ_BYTES(dim);
68
69 /* Query buffers */
70 20794 qs->query_buf = vs_alloc(dim * sizeof(float));
71 20794 qs->pt_query = vs_alloc_aligned(dim * sizeof(float), 64);
72 20794 qs->beam_transformed = vs_alloc_aligned(dim * sizeof(float), 64);
73 20794 qs->cluster_transformed = vs_alloc_aligned(dim * sizeof(float), 64);
74 20794 qs->beam_query_bits = vs_alloc_aligned(packed_bytes, 64);
75 20794 qs->cluster_query_bits = vs_alloc_aligned(packed_bytes, 64);
76
77 /* Wire up query state buffers */
78 20794 qs->beam_qs.transformed = qs->beam_transformed;
79 20794 qs->beam_qs.query_bits = qs->beam_query_bits;
80 20794 qs->cluster_qs.transformed = qs->cluster_transformed;
81 20794 qs->cluster_qs.query_bits = qs->cluster_query_bits;
82
83 20794 vs_rabitq_init_query_constants(&qs->beam_qs, dim);
84 20794 vs_rabitq_init_query_constants(&qs->cluster_qs, dim);
85
86 /* Beam search results + per-scan scratch.
87 * Pre-allocating the scratch here means prism_centroid_beam_search
88 * skips 8 vs_alloc calls and 2 memory-context creations on
89 * every query (the largest remaining source of per-query
90 * allocator traffic after the dedup-gens fix). Sized to the
91 * worst case beam_width == max_nprobe. */
92 20794 qs->beam_results = vs_alloc(max_nprobe * sizeof(PrismCentroidResult));
93 20794 qs->centroid_scratch = prism_centroid_scratch_create(dim, max_nprobe);
94
95 /* Probe-order scratch (exact centroid re-rank of the expanded
96 * probe set; see prism_query_set_probe_expand). */
97 20794 qs->probe_dists = vs_alloc(max_nprobe * sizeof(float));
98 20794 qs->probe_order = vs_alloc(max_nprobe * sizeof(uint32_t));
99 /* probe_refs / probe_entries (spilled layout only) are sized on the
100 * first expanded probe set, to the clusters it routed: dim floats per
101 * cluster is the largest buffer a scan state owns, and a query whose
102 * probe set is never expanded has no use for it. */
103 20794 qs->probe_refs_max = (uint32_t)(PRISM_PROBE_REFS_MAX_BYTES /
104 192 ((size_t)dim * sizeof(float)));
105
106 /* Top-K */
107 20794 vs_topk_init(&qs->topk, max_k);
108
109 /* Candidate extraction buffer */
110 20794 qs->cand_cap = max_k * PRISM_QUERY_CAND_PER_K;
111 20794 qs->candidates = vs_alloc(qs->cand_cap * sizeof(VsTopKEntry));
112
113 /* Result ordering */
114 20794 qs->result_order = vs_alloc(qs->cand_cap * sizeof(uint32_t));
115 20794 qs->result_dists = vs_alloc(qs->cand_cap * sizeof(Distance));
116
117 /* Posting scan iterator */
118 20794 uint32_t max_entries = prism_posting_max_entries(dim);
119 20794 prism_posting_scan_init(
120 &qs->pscan,
121 index->posting_storage,
122 index->page_base,
123 20794 index->params,
124 dim,
125 max_entries);
126
127 20794 vs_memctx_switch(caller_ctx);
128 20794 }
129
130 void
131 20792 prism_query_state_cleanup(PrismQueryState *qs)
132 {
133
2/2
✓ Branch 0 taken 20600 times.
✓ Branch 1 taken 192 times.
20792 if (qs == NULL)
134 ✗ return;
135
136 /*
137 * The pinned page first: it is the one resource the state holds that is
138 * not memory, and deleting the context below would strand it.
139 */
140 20792 prism_posting_scan_cleanup(&qs->pscan);
141
142 /* Sub-contexts before the context that parents them. */
143 20792 vs_topk_cleanup(&qs->topk);
144 20792 prism_centroid_scratch_free(qs->centroid_scratch);
145 20792 qs->centroid_scratch = NULL;
146
147
1/2
✓ Branch 0 taken 20792 times.
✗ Branch 1 not taken.
20792 if (qs->memctx != NULL)
148 {
149 20792 vs_memctx_delete(qs->memctx);
150 20792 qs->memctx = NULL;
151 }
152 }
153
154 /* ----------------------------------------------------------------
155 * Per-query execution
156 * ---------------------------------------------------------------- */
157
158 static const float *
159 658562 prepare_query(PrismQueryState *qs, const float *query)
160 {
161
2/2
✓ Branch 0 taken 204963 times.
✓ Branch 1 taken 453599 times.
658562 if (qs->index->metric != DISTANCE_COSINE)
162 191852 return query;
163
164 14993 Dimension dim = qs->index->dim;
165 14993 memcpy(qs->query_buf, query, dim * sizeof(float));
166 14993 float norm = vs_l2_norm(qs->query_buf, dim);
167
2/2
✓ Branch 0 taken 14867 times.
✓ Branch 1 taken 126 times.
14993 if (norm > 0.0f)
168 14867 vec32_scale(qs->query_buf, 1.0f / norm, qs->query_buf, dim);
169 14993 return qs->query_buf;
170 }
171
172 static uint32_t
173 658562 search_centroids(
174 PrismQueryState *qs,
175 const float *qvec,
176 uint32_t nprobe,
177 VsDistanceMode mode,
178 PrismCentroidSearchStats *beam_stats)
179 {
180 658562 const PrismIndexBase *idx = qs->index;
181 658562 Dimension dim = idx->dim;
182
183 658562 RaBitQQueryState *rqs = NULL;
184
2/2
✓ Branch 0 taken 452307 times.
✓ Branch 1 taken 206255 times.
658562 if (idx->centroid_format == PRISM_CENTROID_FMT_RABITQ ||
185
2/2
✓ Branch 0 taken 6000 times.
✓ Branch 1 taken 16002 times.
22002 idx->centroid_format == PRISM_CENTROID_FMT_FASTSCAN)
186 {
187 608037 vs_rabitq_init_query_state(
188 608037 &qs->beam_qs, qs->pt_query, idx->pt_global_mean, dim, mode);
189 608037 rqs = &qs->beam_qs;
190 }
191
192 1123390 uint32_t beam_w = prism_query_beam_width(
193 658562 nprobe, idx->nlist, idx->fan_out, idx->centroid_beam_scale);
194
195 658562 PrismCentroidSearchState search = {
196 .qstate = rqs,
197 .query = qvec,
198 658562 .storage = idx->centroid_storage,
199 .beam_width = beam_w,
200 .nprobe = nprobe,
201 .dim = dim,
202 658562 .metric = idx->metric,
203 658562 .error_scale = idx->centroid_error_scale,
204 658562 .scratch = qs->centroid_scratch,
205 /* NULL on every query path; only the build route sets it. */
206 658562 .exact_internal = idx->exact_internal,
207 };
208
209 1317124 return prism_centroid_beam_search(
210 &search,
211 658562 idx->first_centroid,
212 658562 idx->nlevels,
213 qs->beam_results,
214 NULL,
215 beam_stats);
216 }
217
218 /* Probe-order refinement factor (prism.probe_expand); see query_scan.h.
219 * Enabled by default: expansion gains saturate around a factor of 2,
220 * so 2.0 captures ~all the recall benefit of exact probe ordering.
221 * 1.0 means no expansion (identity). */
222 static double g_probe_expand = 2.0;
223
224 /* Cap on extra routed candidates. At large nprobe a deep scan already
225 * covers cluster membership, so ordering refinement adds little while
226 * the phase-A cost keeps growing linearly; capping the expansion keeps
227 * the overhead bounded (measured to retain nearly all of the recall
228 * gain at high nprobe). */
229 #define PRISM_PROBE_EXPAND_MAX_EXTRA 256
230
231 void
232 295 prism_query_set_probe_expand(double expand)
233 {
234 295 g_probe_expand = expand;
235 295 }
236
237 /*
238 * Centroid slots the beam keeps at each intermediate level.
239 *
240 * Starts at a fraction of nprobe and is then raised by three floors, each
241 * of which exists because dropping below it loses leaves outright rather
242 * than merely ranking them lower:
243 *
244 * - Routing floor. Below PRISM_CENTROID_BEAM_FLOOR a scaled-down beam saves
245 * almost nothing and mis-routes, so the beam covers every probed list.
246 *
247 * - Coverage floor. A kept set of beam_w parents exposes at most
248 * beam_w * fan_out leaves, so returning nprobe of them needs
249 * ceil(nprobe / fan_out) parents.
250 *
251 * - Probe-everything floor. The coverage floor assumes every child
252 * carries fan_out leaves; an unbalanced tree holds fewer, so once
253 * nprobe covers every leaf the beam keeps whole levels.
254 *
255 * Called by prism_query_execute and by the cost model, which prices a page
256 * read per kept slot per level.
257 */
258 uint32_t
259 659059 prism_query_beam_width(
260 uint32_t nprobe, uint32_t nlist, uint32_t fan_out, double beam_scale)
261 {
262 659059 uint32_t beam_w = (uint32_t)((double)nprobe * beam_scale);
263
264
2/2
✓ Branch 0 taken 430 times.
✓ Branch 1 taken 193304 times.
659059 if (beam_w < 1)
265 430 beam_w = 1;
266
267 659059 uint32_t floor_w = nprobe < PRISM_CENTROID_BEAM_FLOOR
268 ? nprobe
269 : PRISM_CENTROID_BEAM_FLOOR;
270
271
2/2
✓ Branch 0 taken 3862 times.
✓ Branch 1 taken 189872 times.
659059 if (beam_w < floor_w)
272 3862 beam_w = floor_w;
273
274
1/2
✓ Branch 0 taken 659059 times.
✗ Branch 1 not taken.
659059 if (fan_out > 0)
275 {
276 659059 floor_w = (nprobe + fan_out - 1) / fan_out;
277
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 193734 times.
659059 if (beam_w < floor_w)
278 465325 beam_w = floor_w;
279 }
280
281
5/6
✓ Branch 0 taken 309917 times.
✓ Branch 1 taken 349142 times.
✓ Branch 2 taken 145510 times.
✓ Branch 3 taken 48224 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 145510 times.
659059 if (nlist > 0 && nprobe >= nlist && beam_w < nprobe)
282 465325 beam_w = nprobe;
283
284 659059 return beam_w;
285 }
286
287 /*
288 * Leaf clusters the centroid beam routes to when the scan will read nprobe
289 * of them, capped at cap (the most the caller can route to: the scan's beam
290 * capacity, or the number of posting lists).
291 *
292 * Exact centroid formats need no expansion -- their probe order is already
293 * correct -- so those route exactly nprobe. Compressed formats route more
294 * and let phase A re-rank the wider set on exact distances, keeping the
295 * best nprobe of them.
296 *
297 * Called by prism_query_execute and by the cost model, which prices one head
298 * page read per routed cluster.
299 */
300 uint32_t
301 5157 prism_query_routed_clusters(
302 uint32_t nprobe, uint32_t cap, PrismCentroidFormat centroid_format)
303 {
304
4/6
✓ Branch 0 taken 5157 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5115 times.
✓ Branch 3 taken 42 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 4290 times.
5157 if (g_probe_expand <= 1.0 || centroid_format == PRISM_CENTROID_FMT_FLOAT ||
305 centroid_format == PRISM_CENTROID_FMT_HALF)
306 2 return nprobe;
307
308 5115 double expanded = (double)nprobe * g_probe_expand;
309 5115 uint32_t n_route = (uint32_t)(expanded + 0.5);
310
311
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4290 times.
5115 if (n_route > nprobe + PRISM_PROBE_EXPAND_MAX_EXTRA)
312 ✗ n_route = nprobe + PRISM_PROBE_EXPAND_MAX_EXTRA;
313
2/2
✓ Branch 0 taken 3146 times.
✓ Branch 1 taken 1144 times.
5115 if (n_route > cap)
314 3146 n_route = cap;
315
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4290 times.
5115 if (n_route < nprobe)
316 865 n_route = nprobe;
317
318 4290 return n_route;
319 }
320
321 /* qsort comparator for probe_order indices by probe_dists (context via
322 * a file-static base pointer; the scan path is single-threaded per
323 * backend). */
324 static const float *g_probe_sort_dists;
325
326 static int
327 35973 cmp_probe_order(const void *a, const void *b)
328 {
329 35973 float da = g_probe_sort_dists[*(const uint32_t *)a];
330 35973 float db = g_probe_sort_dists[*(const uint32_t *)b];
331
2/2
✓ Branch 0 taken 23173 times.
✓ Branch 1 taken 12800 times.
35973 if (da < db)
332 21015 return -1;
333
2/2
✓ Branch 0 taken 12585 times.
✓ Branch 1 taken 2 times.
12587 if (da > db)
334 12585 return 1;
335 ✗ return 0;
336 }
337
338 static void
339 4660 scan_clusters(
340 PrismQueryState *qs,
341 const PrismCentroidResult *beam_results,
342 uint32_t n_results,
343 uint32_t scan_limit,
344 VsDistanceMode mode,
345 VsTopK *topk,
346 PrismQueryStats *stats)
347 {
348 4660 const PrismIndexBase *idx = qs->index;
349 4660 Dimension dim = idx->dim;
350
351 4660 qs->pscan.storage = idx->posting_storage;
352
353 /*
354 * Warm the cache before the serial per-cluster reads below. Both the
355 * Phase-A re-rank and the scan itself fetch each probed cluster's head
356 * page one at a time; on a cold buffer cache that is a string of
357 * synchronous random reads. Issue async prefetches for every head up
358 * front so the reads overlap. Best-effort and a no-op where the storage
359 * has no prefetch (standalone) or the page is already resident.
360 */
361 4660 uint32_t ref_pages = prism_posting_reference_pages(dim);
362
2/2
✓ Branch 0 taken 48120 times.
✓ Branch 1 taken 4660 times.
52780 for (uint32_t j = 0; j < n_results; j++)
363 {
364 48120 BlockNumber head = beam_results[j].posting_head;
365
366
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48120 times.
48120 if (head == InvalidBlockNumber)
367 ✗ continue;
368 48120 vs_storage_prefetch(qs->pscan.storage, head);
369 /* A spilled list's reference pages follow its head in the bulk-built
370 * region; a split-created list has them wherever the split appended,
371 * so for it this warms a page the gather may not read. */
372
3/3
✓ Branch 0 taken 9632 times.
✓ Branch 1 taken 38108 times.
✓ Branch 2 taken 10630 times.
58370 for (uint32_t r = 1; r < ref_pages; r++)
373 10250 vs_storage_prefetch(qs->pscan.storage, head + r);
374 }
375
376 /*
377 * Phase A (only when the probe set was expanded): re-rank the routed
378 * clusters by EXACT query-centroid distance. The beam's RaBitQ
379 * distances are 1-bit estimates whose noise scrambles the probe
380 * order; each cluster's first posting page stores the full-precision
381 * rotated centroid, so one page read + one O(dim) distance per
382 * candidate recovers the true order. Only the best `scan_limit`
383 * clusters are then scanned.
384 */
385 4660 const uint32_t *order = NULL;
386 4660 uint32_t n_scan = n_results;
387
388
2/2
✓ Branch 0 taken 1195 times.
✓ Branch 1 taken 3465 times.
4660 if (n_results > scan_limit)
389 {
390 /* Clusters past probe_refs_max keep no reference and gather it
391 * again when scanned. */
392 1195 uint32_t want = n_results < qs->probe_refs_max ? n_results
393 : qs->probe_refs_max;
394
395
4/4
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 1047 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 128 times.
1195 if (qs->pscan.pt_ref != NULL && qs->probe_refs_cap < want)
396 {
397 /*
398 * Grow geometrically, up to max_nprobe and the byte budget. The
399 * standalone arena frees nothing until its context goes, and
400 * this one outlives the query -- growing to exactly the size
401 * asked for would keep every smaller buffer from earlier
402 * queries alive.
403 */
404 20 uint32_t cap = qs->probe_refs_cap * 2;
405
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
20 if (cap > qs->max_nprobe)
406 ✗ cap = qs->max_nprobe;
407
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
20 if (cap > qs->probe_refs_max)
408 ✗ cap = qs->probe_refs_max;
409
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 10 times.
20 if (cap < want)
410 6 cap = want;
411
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
20 VsMemCtx caller_ctx = vs_memctx_switch(qs->memctx);
412
413
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
20 if (qs->probe_refs != NULL)
414 {
415 10 vs_free(qs->probe_refs);
416 10 vs_free(qs->probe_entries);
417 }
418 20 qs->probe_refs = vs_alloc((size_t)cap * dim * sizeof(float));
419 20 qs->probe_entries = vs_alloc(cap * sizeof(BlockNumber));
420 20 qs->probe_refs_cap = cap;
421 20 vs_memctx_switch(caller_ctx);
422 }
423
424
2/2
✓ Branch 0 taken 14460 times.
✓ Branch 1 taken 1195 times.
15655 for (uint32_t j = 0; j < n_results; j++)
425 {
426 14460 qs->probe_order[j] = j;
427 14460 qs->probe_dists[j] = FLT_MAX;
428
429 14460 BlockNumber ph = beam_results[j].posting_head;
430
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14460 times.
14460 if (ph == InvalidBlockNumber)
431 ✗ continue;
432
433
2/2
✓ Branch 0 taken 5340 times.
✓ Branch 1 taken 9120 times.
14460 if (qs->pscan.pt_ref != NULL)
434 5340 {
435 /* Spilled: gather once and keep it for the scan pass where
436 * the buffer has a slot, else gather into the scan's own
437 * scratch and keep only the distance. */
438 5340 bool saved = j < qs->probe_refs_cap;
439 5340 float *ref = saved ? qs->probe_refs + (size_t)j * dim
440
2/2
✓ Branch 0 taken 3860 times.
✓ Branch 1 taken 1480 times.
5340 : qs->pscan.pt_ref;
441 5340 BlockNumber entries = prism_posting_reference_read(
442 qs->pscan.storage, ph, dim, ref);
443
444
2/2
✓ Branch 0 taken 3860 times.
✓ Branch 1 taken 1480 times.
5340 if (saved)
445 3860 qs->probe_entries[j] = entries;
446 10680 qs->probe_dists[j] =
447 5340 vs_l2_distance_squared(qs->pt_query, ref, dim);
448 5340 continue;
449 }
450
451 9120 prism_posting_scan_begin_cluster(&qs->pscan, &qs->cluster_qs, ph);
452 9120 const float *pt_cent = prism_posting_scan_pt_centroid(&qs->pscan);
453
1/2
✓ Branch 0 taken 9120 times.
✗ Branch 1 not taken.
9120 if (pt_cent != NULL)
454 9120 qs->probe_dists[j] =
455 9120 vs_l2_distance_squared(qs->pt_query, pt_cent, dim);
456 9120 prism_posting_scan_end_cluster(&qs->pscan);
457 }
458
459 1195 g_probe_sort_dists = qs->probe_dists;
460 1195 qsort(qs->probe_order, n_results, sizeof(uint32_t), cmp_probe_order);
461
462 1195 order = qs->probe_order;
463 1195 n_scan = scan_limit;
464 }
465
466 4660 uint32_t total_pages = 0;
467 4660 uint32_t total_skipped = 0;
468 4660 uint32_t total_entries = 0;
469 4660 uint32_t scanned = 0;
470
471
2/2
✓ Branch 0 taken 40734 times.
✓ Branch 1 taken 4660 times.
45394 for (uint32_t r = 0; r < n_scan; r++)
472 {
473
2/2
✓ Branch 0 taken 7074 times.
✓ Branch 1 taken 33660 times.
40734 uint32_t j = order ? order[r] : r;
474 40734 BlockNumber ph = beam_results[j].posting_head;
475
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40734 times.
40734 if (ph == InvalidBlockNumber)
476 ✗ continue;
477
478 /* Diagnostic: stamp candidates inserted while scanning this cluster
479 * with its scan rank r (the position in the exact-re-ranked probe
480 * order, not the beam index j), so the deepest contributing rank
481 * measures how many probed clusters the query actually needed. */
482 40734 topk->cur_src = r;
483
484
4/4
✓ Branch 0 taken 7074 times.
✓ Branch 1 taken 33660 times.
✓ Branch 2 taken 1990 times.
✓ Branch 3 taken 5084 times.
40734 if (order != NULL && j < qs->probe_refs_cap)
485 1990 prism_posting_scan_begin_cluster_at(
486 &qs->pscan,
487 &qs->cluster_qs,
488 1990 qs->probe_entries[j],
489 1990 qs->probe_refs + (size_t)j * dim);
490 else
491 38744 prism_posting_scan_begin_cluster(&qs->pscan, &qs->cluster_qs, ph);
492
493 40734 const float *pt_cent = prism_posting_scan_pt_centroid(&qs->pscan);
494
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40734 times.
40734 if (pt_cent == NULL)
495 {
496 ✗ prism_posting_scan_end_cluster(&qs->pscan);
497 ✗ continue;
498 }
499
500 40734 vs_rabitq_init_query_state(
501 40734 &qs->cluster_qs, qs->pt_query, pt_cent, dim, mode);
502
503 40734 prism_posting_scan_cluster(&qs->pscan, topk);
504 40734 total_pages += qs->pscan.pages_read;
505 40734 total_skipped += qs->pscan.pages_skipped;
506 40734 total_entries += qs->pscan.entries_scanned;
507 40734 prism_posting_scan_end_cluster(&qs->pscan);
508 40734 scanned++;
509 }
510
511 4660 qs->pscan.storage = NULL;
512
513
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 4292 times.
4660 if (stats != NULL)
514 {
515 368 stats->clusters_scanned = scanned;
516 368 stats->posting_pages_read = total_pages;
517 368 stats->posting_pages_skipped = total_skipped;
518 368 stats->posting_entries_scanned = total_entries;
519 }
520 4660 }
521
522 static uint32_t
523 4660 extract_candidates(PrismQueryState *qs, uint32_t cap)
524 {
525
2/2
✓ Branch 0 taken 138 times.
✓ Branch 1 taken 4522 times.
4660 if (qs->topk.cand_count > qs->cand_cap)
526 {
527 /* Grow geometrically so a run of gradually larger queries does
528 * not realloc+copy on every step to the high-water mark. */
529 138 uint32_t want = qs->cand_cap * 2;
530
2/2
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 54 times.
138 if (want < qs->topk.cand_count)
531 33 want = qs->topk.cand_count;
532 138 qs->cand_cap = want;
533 189 qs->candidates =
534 138 vs_realloc(qs->candidates, qs->cand_cap * sizeof(VsTopKEntry));
535 189 qs->result_order =
536 138 vs_realloc(qs->result_order, qs->cand_cap * sizeof(uint32_t));
537 138 qs->result_dists =
538 138 vs_realloc(qs->result_dists, qs->cand_cap * sizeof(Distance));
539 }
540
541 368 uint32_t ncands;
542 4660 vs_topk_extract_sorted_capped(&qs->topk, qs->candidates, &ncands, cap);
543 4660 qs->ncandidates = ncands;
544 4660 return ncands;
545 }
546
547 /* Monotonic nanosecond clock for per-phase query instrumentation. */
548 static inline uint64_t
549 1335764 prism_query_now_ns(void)
550 {
551 931128 struct timespec ts;
552 1335764 clock_gettime(CLOCK_MONOTONIC, &ts);
553 1335764 return (uint64_t)ts.tv_sec * VS_NS_PER_SEC + (uint64_t)ts.tv_nsec;
554 }
555
556 uint32_t
557 658562 prism_query_route(
558 PrismQueryState *qs,
559 const float *query,
560 uint32_t nprobe,
561 VsDistanceMode mode,
562 PrismCentroidSearchStats *beam_stats)
563 {
564
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 193734 times.
658562 if (nprobe > qs->max_nprobe)
565 ✗ nprobe = qs->max_nprobe;
566
567 658562 PrismCentroidSearchStats local = {0};
568
2/2
✓ Branch 0 taken 189810 times.
✓ Branch 1 taken 468752 times.
658562 PrismCentroidSearchStats *bs = beam_stats ? beam_stats : &local;
569
570 658562 const float *qvec = prepare_query(qs, query);
571 658562 uint64_t t_rot = prism_query_now_ns();
572 658562 vs_rabitq_rotate(qs->index->params, qvec, qs->pt_query);
573 658562 bs->rotation_ns = prism_query_now_ns() - t_rot;
574
575 658562 return search_centroids(qs, qvec, nprobe, mode, bs);
576 }
577
578 /* Cap on the rerank candidate pool (prism.rerank_pool). Candidates are
579 * sorted by approximate distance, so capping keeps the most promising
580 * ones and bounds the exact-distance heap fetches. 0 (default) resolves
581 * to an automatic cap of max(3 * k * nprobe^0.15, candidate-buffer count
582 * / 8): the buffer population directly measures estimate noise, so the
583 * nprobe-scaled floor (fit against rekall's cohere-1m recall-vs-pool
584 * sweep: the pool needed to keep the rerank-induced recall deficit under
585 * 0.1% relative to an unbounded pool, at nprobe in {10,20,40,80,160},
586 * power-law-fits to 30 * nprobe^0.15 for k=10) grows further when noisy
587 * estimates flood the buffer and ranking into just that floor would
588 * silently cap recall far below what the probed clusters contain. A
589 * flat 16 * k floor (this formula's predecessor) was measured
590 * recall-neutral, but oversized at every nprobe on that sweep -- e.g.
591 * 2-4x more pool than needed below nprobe=80, wasting rerank work
592 * without buying recall. -1 disables the cap entirely; positive values
593 * are absolute. The effective cap is never below k, so a cap can never
594 * truncate the result set. */
595 #define PRISM_RERANK_POOL_AUTO_COEFF 3.0
596 #define PRISM_RERANK_POOL_AUTO_EXP 0.15
597
598 static int32_t g_rerank_pool = 0;
599
600 void
601 374 prism_query_set_rerank_pool(int32_t n)
602 {
603 374 g_rerank_pool = n;
604 374 }
605
606 /*
607 * Calculates the size of the rerank pool from k, the number of neighbours
608 * the query will return, and nprobe, the number of posting lists it will
609 * scan -- as far as that can be known without running the scan.
610 *
611 * A return of 0 means the pool is uncapped: it is the value
612 * vs_topk_extract_sorted_capped reads as "keep every survivor", so 0 is
613 * the widest possible pool and not the narrowest. Callers that price the
614 * pool have to special-case it.
615 *
616 * Shared with the cost model, which has to price the fetches the scan will
617 * actually make. The scan adds one term this cannot: a floor at an eighth of
618 * the candidate buffer, which measures estimate noise and so does not exist
619 * until the clusters have been scanned.
620 */
621 uint32_t
622 5187 prism_query_rerank_pool_estimate(uint32_t k, uint32_t nprobe)
623 {
624
2/2
✓ Branch 0 taken 859 times.
✓ Branch 1 taken 4328 times.
5187 if (g_rerank_pool < 0)
625 4 return 0; /* uncapped: every survivor is reranked */
626
627
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 5156 times.
5175 if (g_rerank_pool > 0)
628 {
629 19 uint32_t pool = (uint32_t)g_rerank_pool;
630
631 19 return pool < k ? k : pool;
632 }
633
634 5156 double auto_floor = PRISM_RERANK_POOL_AUTO_COEFF * (double)k *
635 5156 pow((double)nprobe, PRISM_RERANK_POOL_AUTO_EXP);
636 5156 uint32_t pool = (uint32_t)(auto_floor + 0.5);
637
638 5156 return pool < k ? k : pool;
639 }
640
641 uint32_t
642 4660 prism_query_execute(
643 PrismQueryState *qs,
644 const float *query,
645 uint32_t k,
646 uint32_t nprobe,
647 VsDistanceMode mode,
648 bool rerank,
649 PrismQueryStats *stats)
650 {
651
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4292 times.
4660 if (k > qs->max_k)
652 ✗ k = qs->max_k;
653
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4292 times.
4660 if (nprobe > qs->max_nprobe)
654 ✗ nprobe = qs->max_nprobe;
655
656 /* reset_to_k also (re)sizes the heap when k grows between queries —
657 * resetting first and assigning k afterwards left the heap sized for
658 * the previous k. */
659 4660 vs_topk_reset_to_k(&qs->topk, k);
660
661 /* Probe expansion: route extra leaf candidates so phase A of
662 * scan_clusters can pick the best `nprobe` by exact centroid
663 * distance. n_route == nprobe (expand == 1, no expansion) keeps
664 * the classic single-phase behavior. Skipped entirely when the
665 * centroid pages are exact (float/half): the beam distances are
666 * already exact, so there is no ordering noise to correct. */
667 5028 uint32_t n_route = prism_query_routed_clusters(
668 4660 nprobe, qs->max_nprobe, qs->index->centroid_format);
669
670 4660 uint64_t t0 = prism_query_now_ns();
671
672 4660 PrismCentroidSearchStats beam_stats = {0};
673 368 uint32_t ncentroids =
674 4660 prism_query_route(qs, query, n_route, mode, &beam_stats);
675
676 /* prism_query_route already normalized the query into qs->query_buf (for
677 * cosine) via prepare_query; reuse it for the rerank below instead of
678 * re-normalizing (a redundant O(dim) memcpy+norm+scale per query). For
679 * non-cosine metrics prepare_query is a no-op and returns the raw query.
680 */
681 4306 const float *qvec = (qs->index->metric == DISTANCE_COSINE) ? qs->query_buf
682
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 4644 times.
4660 : query;
683
684 4660 uint64_t t1 = prism_query_now_ns();
685
686 /*
687 * The probed heads are chosen and their centroid pages released, but none
688 * of the lists has been opened yet. A concurrent split can replace and
689 * retire a head in this window, which is why the old chain stays readable
690 * until no snapshot can reach it; an isolation test pauses here to hold a
691 * head across exactly that.
692 */
693 368 VS_INJECTION_POINT("prism-scan-routed");
694
695 4660 scan_clusters(
696 4660 qs, qs->beam_results, ncentroids, nprobe, mode, &qs->topk, stats);
697
698 /* Rerank-pool cap: the first `pool` candidates by approximate
699 * distance are the most promising; see prism_query_set_rerank_pool.
700 * Resolved before extraction so the extract can select the capped
701 * prefix instead of fully sorting an unbounded survivor set.
702 *
703 * The automatic cap also scales with the candidate-buffer
704 * population, which directly measures estimate noise: accurate
705 * estimates keep the threshold at the nprobe-scaled floor above,
706 * while noisy estimates (low dimension, wide norm spread) flood
707 * the buffer -- and then ranking into just that floor is
708 * meaningless, silently capping recall well below what the probed
709 * clusters contain. 1/8th of the buffer restores the recall
710 * ceiling at a rerank cost proportionate to the observed noise. */
711 4660 uint32_t pool = prism_query_rerank_pool_estimate(k, nprobe);
712
713 /*
714 * The noise term needs the candidate population, which exists only now
715 * that the clusters have been scanned -- so it cannot be part of the
716 * shared estimate the planner uses.
717 */
718
4/4
✓ Branch 0 taken 4654 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 3582 times.
✓ Branch 3 taken 710 times.
4660 if (g_rerank_pool == 0 && pool < qs->topk.cand_count / 8)
719 3950 pool = qs->topk.cand_count / 8;
720
3/4
✓ Branch 0 taken 4292 times.
✓ Branch 1 taken 368 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4292 times.
4660 if (pool > 0 && pool < k)
721 ✗ pool = k;
722
723 4660 uint32_t ncands = extract_candidates(qs, pool);
724
725 4660 uint64_t t2 = prism_query_now_ns();
726
727 /* Rerank with exact distances if enabled and storage supports it */
728 4660 VsStorage *ps = qs->index->posting_storage;
729
5/8
✓ Branch 0 taken 4654 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 4654 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4654 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4292 times.
✗ Branch 7 not taken.
4660 if (rerank && ncands > 0 && ps != NULL && ps->ops->rerank != NULL)
730 {
731 9308 qs->nresults = vs_storage_rerank(
732 ps,
733 qvec,
734 4654 qs->index->dim,
735 4654 qs->candidates,
736 ncands,
737 k,
738 qs->result_order,
739 qs->result_dists);
740 /* A rerank can keep candidates tied at the k-th distance,
741 * but result consumers size their buffers to k. */
742
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 4635 times.
4654 if (qs->nresults > k)
743 19 qs->nresults = k;
744 }
745 else
746 {
747 6 qs->nresults = ncands < k ? ncands : k;
748
2/2
✓ Branch 0 taken 500 times.
✓ Branch 1 taken 6 times.
506 for (uint32_t i = 0; i < qs->nresults; i++)
749 {
750 500 qs->result_order[i] = i;
751 500 qs->result_dists[i] = qs->candidates[i].distance;
752 }
753 }
754
755 #ifndef NDEBUG
756
2/2
✓ Branch 0 taken 19089 times.
✓ Branch 1 taken 4660 times.
23749 for (uint32_t i = 0; i < qs->nresults; i++)
757 {
758 19089 uint64_t id_i = qs->candidates[qs->result_order[i]].id;
759
2/2
✓ Branch 0 taken 2025937 times.
✓ Branch 1 taken 19089 times.
2045026 for (uint32_t j = i + 1; j < qs->nresults; j++)
760
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2025937 times.
2025937 if (id_i == qs->candidates[qs->result_order[j]].id)
761
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
1993307 vs_warn(VS_EXTENSION_NAME ": duplicate result at positions "
762 "%u and %u",
763 i,
764 j);
765 }
766 #endif
767
768 4660 uint64_t t3 = prism_query_now_ns();
769
770 /* Routing-quality diagnostic: deepest probe rank contributing a final
771 * top-k result. Low values (relative to nprobe) => over-probing; values
772 * near nprobe => neighbors genuinely routed deep (mis-routing). */
773 4660 uint32_t max_rank = 0;
774
3/3
✓ Branch 0 taken 7586 times.
✓ Branch 1 taken 15795 times.
✓ Branch 2 taken 368 times.
23749 for (uint32_t i = 0; i < qs->nresults; i++)
775 {
776 19089 uint32_t r = qs->candidates[qs->result_order[i]].src;
777
2/2
✓ Branch 0 taken 1829 times.
✓ Branch 1 taken 5757 times.
19089 if (r > max_rank)
778 1829 max_rank = r;
779 }
780
781
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 4292 times.
4660 if (stats != NULL)
782 {
783 /* clusters_scanned is set by scan_clusters (actual count). */
784 368 stats->max_contrib_rank = max_rank;
785 368 stats->centroid_pages_read = beam_stats.pages_read;
786 368 stats->centroid_ns = t1 - t0;
787 368 stats->posting_ns = t2 - t1;
788 368 stats->rerank_ns = t3 - t2;
789 368 stats->rotation_ns = beam_stats.rotation_ns;
790 }
791
792 4660 return qs->nresults;
793 }
794
795 uint32_t
796 485 prism_auto_nprobe(uint32_t nlist)
797 {
798 /* See the header: ~0.5 * sqrt(nlist), floored at 10, capped at
799 * 2048, never above nlist. */
800 485 uint32_t nprobe = (uint32_t)ceil(0.5 * sqrt((double)nlist));
801
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 8 times.
485 if (nprobe < 10)
802 6 nprobe = 10;
803
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
485 if (nprobe > 2048)
804 2 nprobe = 2048;
805
4/4
✓ Branch 0 taken 308 times.
✓ Branch 1 taken 177 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 12 times.
485 if (nlist > 0 && nprobe > nlist)
806 296 nprobe = nlist;
807 485 return nprobe;
808 }
809