| 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 |