GCC Code Coverage Report


Directory: src/
File: src/index/centroid_search.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 321 379 84.7%
Functions: 7 7 100.0%
Branches: 138 187 73.8%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * centroid_search.c - Beam search over centroid tree
6 *
7 * Implements level-by-level descent through centroid pages using
8 * format-aware distance computation. RaBitQ pages use approximate
9 * distance with error bounds; float and half pages use exact L2
10 * distance (error = 0). Candidate selection uses VsTopK for
11 * error-bound-aware pruning.
12 */
13
14 #include "vs_config.h"
15
16 #include <math.h>
17 #include <string.h>
18
19 #include "algo/topk.h"
20 #include "algo/vecops.h"
21 #include "core/log.h"
22 #include "core/memory.h"
23 #include "index/centroid_search.h"
24 #include "types/vec16.h"
25
26 /* ----------------------------------------------------------------
27 * Internal candidate for beam search
28 * ---------------------------------------------------------------- */
29 typedef struct Candidate
30 {
31 BlockNumber child_blkno; /* next level's page (or posting head) */
32 ItemPointerData origin; /* (page, entry) this came from */
33 Distance distance;
34 Distance error; /* symmetric error (0 for exact) */
35 } Candidate;
36
37 /* ----------------------------------------------------------------
38 * Per-scan scratch (public allocation; see centroid_search.h)
39 *
40 * Holds the candidate-buffer pair and score-page scratch that beam
41 * search previously palloc'd per call. Allocated once at scan setup
42 * and reused across all queries on the scan.
43 * ---------------------------------------------------------------- */
44 struct PrismCentroidScratch
45 {
46 /* Owning context, captured at scratch_create: every buffer below
47 * lives here until scratch_free. Beam search runs under whatever
48 * context the caller routes from — during index builds that is a
49 * per-row scratch context reset after every tuple — so any lazy
50 * (re)allocation of a scratch buffer must go to this context, never
51 * to the current one. */
52 VsMemCtx memctx;
53 uint32_t cand_cap; /* size of buf_a / buf_b */
54 uint32_t max_per_page; /* size of the f_add..symmetric_scratch arrays */
55 Candidate *buf_a;
56 Candidate *buf_b;
57 float *f_add;
58 float *f_rescale;
59 Distance *distances;
60 Distance *lower_bounds;
61 float *multi_scratch;
62 uint32_t *symmetric_scratch;
63 /* Reusable top-K + extraction buffer for select_topk_bounded.
64 * Avoids creating a fresh memctx + ub_heap + ub_ids + candidates
65 * + entries-buf on every beam-search level (was 2 sets of 4 allocs
66 * + 2 memctx creates per query). The VsTopK is initialised once
67 * at scratch_create with the worst-case k; select_topk_bounded
68 * calls vs_topk_reset_to_k() to adjust between levels. */
69 VsTopK level_topk;
70 VsTopKEntry *entries_buf;
71 uint32_t entries_cap;
72 /* Fastscan LUT used by the FASTSCAN centroid format. The LUT only
73 * depends on the query (qstate->transformed), which is constant
74 * for the entire centroid descent — so we build it once per query
75 * and reuse for every FASTSCAN page. fs_lut_valid is cleared at
76 * the start of every beam-search call. */
77 uint8_t *fs_lut;
78 uint32_t fs_lut_bytes;
79 float fs_lut_delta;
80 float fs_lut_bias;
81 bool fs_lut_valid;
82 };
83
84 PrismCentroidScratch *
85 20810 prism_centroid_scratch_create(Dimension dim, uint32_t max_beam_width)
86 {
87 20810 uint32_t max_per_page = prism_centroid_max_entries(dim);
88
89 /* A kept node's children can span two pages when fan_out exceeds
90 * the per-page entry capacity (e.g. fan_out 74 vs 72 entries at
91 * dim 768), so a level can expose up to beam * 2 pages of
92 * candidates; sizing by pages * capacity keeps the buffer an upper
93 * bound and stops the level scan from silently truncating the
94 * farthest kept parent's tail children. */
95 20810 uint32_t cand_cap = max_beam_width * max_per_page * 2;
96
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 202 times.
20810 if (cand_cap < max_per_page * 4)
97 6 cand_cap = max_per_page * 4;
98
99 /* The scratch owns a dedicated child context: every buffer —
100 * including later growth, which can run under a caller's per-row
101 * reset context — lives and dies with it, and cleanup is a single
102 * context delete. */
103 20602 VsMemCtx ctx =
104 20810 vs_memctx_create(vs_memctx_current(), "vs centroid scratch");
105 20810 VsMemCtx old_ctx = vs_memctx_switch(ctx);
106 20810 PrismCentroidScratch *s = vs_alloc(sizeof(PrismCentroidScratch));
107
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20810 times.
20810 if (s == NULL)
108 {
109 ✗ vs_memctx_switch(old_ctx);
110 ✗ vs_memctx_delete(ctx);
111 ✗ return NULL;
112 }
113
114 20810 s->memctx = vs_memctx_current();
115 20810 s->cand_cap = cand_cap;
116 20810 s->max_per_page = max_per_page;
117 20810 s->buf_a = vs_alloc(cand_cap * sizeof(Candidate));
118 20810 s->buf_b = vs_alloc(cand_cap * sizeof(Candidate));
119 20810 s->f_add = vs_alloc(max_per_page * sizeof(float));
120 20810 s->f_rescale = vs_alloc(max_per_page * sizeof(float));
121 20810 s->distances = vs_alloc(max_per_page * sizeof(Distance));
122 20810 s->lower_bounds = vs_alloc(max_per_page * sizeof(Distance));
123 20810 s->multi_scratch = vs_alloc(max_per_page * sizeof(float));
124 20810 s->symmetric_scratch = vs_alloc(max_per_page * sizeof(uint32_t));
125
126 /* Reusable top-K and extract buffer (resized to actual k per
127 * select_topk_bounded call). Initial k=max_beam_width is just
128 * a starting size — the reset path repalloc's within the
129 * topk's memctx for different k. */
130 20810 vs_topk_init(&s->level_topk, max_beam_width);
131 20810 s->entries_cap = max_beam_width * 4;
132
2/2
✓ Branch 0 taken 20199 times.
✓ Branch 1 taken 611 times.
20810 if (s->entries_cap < 64)
133 20199 s->entries_cap = 64;
134 20810 s->entries_buf = vs_alloc(s->entries_cap * sizeof(VsTopKEntry));
135
136 /* Fastscan LUT (worst-case hacc size for this dim). Allocated
137 * once and reused for every centroid page scored in the
138 * FASTSCAN format. The LUT depends on the query so it's rebuilt
139 * per page; the buffer is reusable. */
140 20810 s->fs_lut_bytes = VS_FASTSCAN_LUT_HACC_BYTES(dim);
141 20810 s->fs_lut = vs_alloc(s->fs_lut_bytes);
142 20810 vs_memctx_switch(old_ctx);
143 208 return s;
144 }
145
146 void
147 20808 prism_centroid_scratch_free(PrismCentroidScratch *s)
148 {
149
2/2
✓ Branch 0 taken 20600 times.
✓ Branch 1 taken 208 times.
20808 if (s == NULL)
150 ✗ return;
151 20808 vs_topk_cleanup(&s->level_topk);
152 /* Everything the scratch owns — struct included — lives in its
153 * context; one delete frees it all. */
154 20808 vs_memctx_delete(s->memctx);
155 }
156
157 /*
158 * Build-time exact-scoring hook: resolve a page's exact-centroid slots,
159 * or NULL when the hook is unset, the page lies outside the collected
160 * region, or the page carries no internal entries (the leaf level).
161 */
162 static const float *
163 5287471 exact_internal_slots(
164 const PrismCentroidSearchState *state,
165 BlockNumber page_blkno,
166 Dimension dim)
167 {
168 5287471 const PrismExactInternalCentroids *ex = state->exact_internal;
169
170
4/4
✓ Branch 0 taken 5102306 times.
✓ Branch 1 taken 185165 times.
✓ Branch 2 taken 3978293 times.
✓ Branch 3 taken 1124013 times.
5287471 if (ex == NULL || page_blkno < ex->base ||
171
2/2
✓ Branch 0 taken 2956453 times.
✓ Branch 1 taken 1021840 times.
3978293 page_blkno - ex->base >= ex->npages)
172 102724 return NULL;
173
174 3978293 uint32_t off = ex->page_off[page_blkno - ex->base];
175
2/2
✓ Branch 0 taken 1207218 times.
✓ Branch 1 taken 2771075 times.
3978293 if (off == PRISM_EXACT_INTERNAL_NONE)
176 969840 return NULL;
177 289378 return ex->cents + (size_t)off * dim;
178 }
179
180 /*
181 * Score all centroids on a single page, appending to candidates.
182 * Returns the new candidate count.
183 *
184 * Dispatches based on page data format:
185 * RABITQ → batch multi-candidate scoring via cs
186 * FLOAT → vs_l2_distance_squared (exact, error=0)
187 * HALF → vs_f16_l2_squared (exact, error=0)
188 */
189 static uint32_t
190 5725609 score_page(
191 const PrismCentroidSearchState *state,
192 Page page,
193 BlockNumber page_blkno,
194 Dimension dim,
195 Candidate *cands,
196 uint32_t cand_count,
197 uint32_t cand_cap,
198 PrismCentroidScratch *cs)
199 {
200 5725609 PrismCentroidPageOpaque *opaque = PRISM_CENTROID_OPAQUE(page);
201 5725609 uint16_t count = opaque->entry_count;
202 5725609 PrismCentroidFormat fmt = prism_centroid_page_format(page);
203
204 /* The on-disk entry_count drives every loop below -- the RABITQ
205 * branch fills the max_per_page-sized scratch arrays with `count`
206 * entries, and the other branches read `count` entries off the page.
207 * A count past the format's real capacity (corruption, a truncated
208 * write) would overrun the scratch or read past the page, so reject
209 * it loudly rather than act on it. The RABITQ capacity equals the
210 * scratch size the state was built with (prism_centroid_max_entries). */
211 5725609 uint32_t max_entries = prism_centroid_max_entries_fmt(dim, fmt);
212
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5725609 times.
5725609 if (count > max_entries)
213 ✗ vs_error(
214 VS_EXTENSION_NAME
215 ": centroid page %u has an invalid entry count (%u > %u); "
216 "the index may be corrupted -- REINDEX it",
217 page_blkno,
218 (unsigned)count,
219 max_entries);
220
221
2/2
✓ Branch 0 taken 4463021 times.
✓ Branch 1 taken 1262588 times.
5725609 if (count == 0)
222 ✗ return cand_count;
223
224 /* Build-time hook: when the build collected this page's exact float
225 * centroids (internal levels only; see PrismExactInternalCentroids), score
226 * them with exact L2 instead of the RaBitQ estimate. The estimated
227 * formats approximate the original-space squared L2 (the rotation is
228 * norm-preserving), so this is the same quantity with the estimate
229 * noise removed (error = 0). Exact formats (FLOAT/HALF) never take
230 * this path — they are exact already, including their metric
231 * handling. */
232
4/4
✓ Branch 0 taken 4372931 times.
✓ Branch 1 taken 1352678 times.
✓ Branch 2 taken 72000 times.
✓ Branch 3 taken 138024 times.
5725609 if (fmt == PRISM_CENTROID_FMT_RABITQ || fmt == PRISM_CENTROID_FMT_FASTSCAN)
233 {
234 5287471 const float *exact = exact_internal_slots(state, page_blkno, dim);
235
236
2/2
✓ Branch 0 taken 289378 times.
✓ Branch 1 taken 4998093 times.
5287471 if (exact != NULL)
237 {
238 52000 char *content = (char *)PageGetContents(page);
239
240
3/4
✓ Branch 0 taken 1141154 times.
✓ Branch 1 taken 289378 times.
✓ Branch 2 taken 172000 times.
✗ Branch 3 not taken.
1430532 for (uint16_t i = 0; i < count && cand_count < cand_cap; i++)
241 {
242 969154 BlockNumber child;
243
244
2/2
✓ Branch 0 taken 1007154 times.
✓ Branch 1 taken 134000 times.
1141154 if (fmt == PRISM_CENTROID_FMT_FASTSCAN)
245 1007154 child = prism_centroid_fastscan_group_child(
246 content,
247 i / VS_FASTSCAN_GROUP,
248 1007154 dim)[i % VS_FASTSCAN_GROUP];
249 else
250 134000 child = prism_centroid_meta(page, i)->child_blkno;
251
252 1141154 cands[cand_count].child_blkno = child;
253 1141154 ItemPointerSet(&cands[cand_count].origin, page_blkno, i);
254 2282308 cands[cand_count].distance = vs_l2_distance_squared(
255 1141154 state->query, exact + (size_t)i * dim, dim);
256 1141154 cands[cand_count].error = 0.0f;
257 1141154 cand_count++;
258 }
259 52000 return cand_count;
260 }
261 }
262
263
4/5
✓ Branch 0 taken 1326117 times.
✓ Branch 1 taken 420689 times.
✓ Branch 2 taken 3671976 times.
✓ Branch 3 taken 17449 times.
✗ Branch 4 not taken.
5436231 switch (fmt)
264 {
265 1326117 case PRISM_CENTROID_FMT_RABITQ:
266 {
267 1326117 uint32_t data_size = VS_RABITQ_DATA_SIZE(dim);
268
269 /* Gather f_add/f_rescale in reverse order
270 * (page data grows backward: entry 0 at highest address) */
271
2/2
✓ Branch 0 taken 15110954 times.
✓ Branch 1 taken 1326117 times.
16437071 for (uint16_t i = 0; i < count; i++)
272 {
273 3357530 const RaBitQData *d =
274 15110954 prism_centroid_data(page, count - 1 - i, dim);
275 15110954 cs->f_add[i] = d->f_add;
276 15110954 cs->f_rescale[i] = d->f_rescale;
277 }
278
279 /* bits_base = last entry's bits (lowest address) */
280 1633670 const uint8_t *bits_base =
281 1326117 prism_centroid_data(page, count - 1, dim)->bits;
282
283 /* Batch distance + error bound computation. With error_scale = 0
284 * (the default) the pruning bounds are multiplied by zero anyway,
285 * so skip computing them entirely: the batch functions take a
286 * NULL lower_bounds and omit the per-entry error derivation (a
287 * divide + sqrt per centroid that also blocks vectorization of
288 * the distance-apply loop). */
289 1326117 bool want_bounds = (state->error_scale != 0.0f);
290
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1326117 times.
1326117 Distance *lb = want_bounds ? cs->lower_bounds : NULL;
291
292
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1326111 times.
1326117 if (state->qstate->mode == VS_DISTANCE_MODE_SYMMETRIC)
293 6 vs_rabitq_distance_batch_symmetric_with_bound(
294 6 state->qstate,
295 6 cs->f_add,
296 6 cs->f_rescale,
297 bits_base,
298 data_size,
299 count,
300 dim,
301 cs->distances,
302 lb,
303 cs->symmetric_scratch);
304 else
305 1326111 vs_rabitq_distance_batch_multi_with_bound(
306 1018558 state->qstate,
307 1326111 cs->f_add,
308 1326111 cs->f_rescale,
309 bits_base,
310 data_size,
311 count,
312 dim,
313 cs->distances,
314 lb,
315 cs->multi_scratch);
316
317 /* Build candidates (result j → page entry count-1-j) */
318
3/4
✓ Branch 0 taken 15110954 times.
✓ Branch 1 taken 1326117 times.
✓ Branch 2 taken 11753424 times.
✗ Branch 3 not taken.
16437071 for (uint16_t j = 0; j < count && cand_count < cand_cap; j++)
319 {
320 15110954 uint16_t page_idx = count - 1 - j;
321 3357530 const PrismCentroidEntryMeta *meta =
322 15110954 prism_centroid_meta(page, page_idx);
323
324 15110954 cands[cand_count].child_blkno = meta->child_blkno;
325 15110954 ItemPointerSet(&cands[cand_count].origin, page_blkno, page_idx);
326 15110954 cands[cand_count].distance = cs->distances[j];
327 18468484 cands[cand_count].error = want_bounds
328 ✗ ? state->error_scale *
329 ✗ (cs->distances[j] -
330 ✗ cs->lower_bounds[j])
331
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15110954 times.
15110954 : 0.0f;
332 15110954 cand_count++;
333 }
334 1018564 break;
335 }
336 420689 case PRISM_CENTROID_FMT_FLOAT:
337 {
338 /* Hoist query norm out of the inner loop: it depends only on
339 * the query, not the centroid, but was previously recomputed
340 * for every entry (one full norm² per centroid scored). */
341 420689 float norm_q = (state->metric == DISTANCE_COSINE)
342 2002 ? vs_l2_norm_squared(state->query, dim)
343
2/2
✓ Branch 0 taken 2002 times.
✓ Branch 1 taken 418687 times.
420689 : 0.0f;
344
345
3/4
✓ Branch 0 taken 3652499 times.
✓ Branch 1 taken 420689 times.
✓ Branch 2 taken 396076 times.
✗ Branch 3 not taken.
4073188 for (uint16_t i = 0; i < count && cand_count < cand_cap; i++)
346 {
347 3652499 const PrismCentroidEntryMeta *meta = prism_centroid_meta(page, i);
348 3652499 const float *fvec = prism_centroid_float_data(page, i, dim);
349 3256423 Distance dist;
350
351
3/3
✓ Branch 0 taken 145001 times.
✓ Branch 1 taken 62062 times.
✓ Branch 2 taken 3445436 times.
3652499 switch (state->metric)
352 {
353 145001 case DISTANCE_INNER_PRODUCT:
354 145001 dist = -vs_dot_product(state->query, fvec, dim);
355 145001 break;
356 62062 case DISTANCE_COSINE:
357 {
358 62062 float dot = vs_dot_product(state->query, fvec, dim);
359 62062 float norm_v = vs_l2_norm_squared(fvec, dim);
360 62062 float denom = sqrtf(norm_q * norm_v);
361
2/2
✓ Branch 0 taken 62000 times.
✓ Branch 1 taken 62 times.
62062 dist = (denom > 0.0f) ? 1.0f - dot / denom : 1.0f;
362 ✗ break;
363 }
364 3445436 default: /* L2 */
365 3445436 dist = vs_l2_distance_squared(state->query, fvec, dim);
366 3445436 break;
367 }
368
369 3652499 cands[cand_count].child_blkno = meta->child_blkno;
370 3652499 ItemPointerSet(&cands[cand_count].origin, page_blkno, i);
371 3652499 cands[cand_count].distance = dist;
372 3652499 cands[cand_count].error = 0.0f;
373 3652499 cand_count++;
374 }
375 138018 break;
376 }
377 3671976 case PRISM_CENTROID_FMT_FASTSCAN:
378 {
379 /* Fastscan centroid pages: same RaBitQ codes as the RABITQ
380 * format but rearranged into 32-vector groups so we can
381 * score them with vs_fastscan_accumulate (~150 M vec/s on
382 * Graviton 4) instead of the per-vector kernel used by the
383 * RABITQ branch above.
384 *
385 * Layout per group section:
386 * BlockNumber child_blkno[32]
387 * float f_add[32]
388 * float f_rescale[32]
389 * float f_error[32]
390 * uint8_t codes[nsq_pairs*32]
391 *
392 * The LUT depends on the query (and via qstate->transformed,
393 * implicitly on the cluster's centroid for posting scans;
394 * for centroid descent the relevant query state is the
395 * pre-cluster qstate->transformed which is just P^T*query
396 * minus the global_mean rotation already absorbed by
397 * pt_global_mean). It is rebuilt once per centroid page
398 * scored. Amortising the LUT build across all 32 entries in
399 * a group is the whole reason this is faster than the
400 * per-vector kernel. */
401 /* Build the LUT once per query — qstate->transformed is
402 * constant across the whole centroid descent, so we cache
403 * the LUT bytes + lut_delta + lut_bias in PrismCentroidScratch
404 * and reuse them on every subsequent FASTSCAN page. */
405
2/2
✓ Branch 0 taken 386775 times.
✓ Branch 1 taken 3285201 times.
3671976 if (!cs->fs_lut_valid)
406 {
407 386775 vs_fastscan_build_lut_hacc(
408 386775 state->qstate->transformed,
409 dim,
410 cs->fs_lut,
411 &cs->fs_lut_delta,
412 &cs->fs_lut_bias);
413 386775 cs->fs_lut_valid = true;
414 }
415 3671976 float lut_delta = cs->fs_lut_delta;
416 3671976 float lut_bias = cs->fs_lut_bias;
417
418 3671976 float g_add = state->qstate->g_add;
419 3671976 float sum_t = state->qstate->sum_transformed;
420 3671976 float inv_sqrt_d = state->qstate->inv_sqrt_d;
421 3671976 float g_error = state->qstate->g_error;
422 3671976 float err_mult = state->qstate->error_multiplier;
423
424 3671976 char *content = (char *)PageGetContents(page);
425 3671976 uint32_t entry_count = count;
426 3671976 uint32_t ngroups = (entry_count + VS_FASTSCAN_GROUP - 1) /
427 VS_FASTSCAN_GROUP;
428
429 3617976 int32_t accum[VS_FASTSCAN_GROUP];
430
431
2/2
✓ Branch 0 taken 3671976 times.
✓ Branch 1 taken 3671976 times.
7343952 for (uint32_t g = 0; g < ngroups; g++)
432 {
433 3671976 uint32_t g_start = g * VS_FASTSCAN_GROUP;
434 3671976 uint32_t g_count = entry_count - g_start;
435
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 54000 times.
3671976 if (g_count > VS_FASTSCAN_GROUP)
436 ✗ g_count = VS_FASTSCAN_GROUP;
437
438 3617976 const BlockNumber *child = (const BlockNumber *)
439 3671976 prism_centroid_fastscan_group_child(content, g, dim);
440 3617976 const float *f_add_arr =
441 3671976 prism_centroid_fastscan_group_f_add(content, g, dim);
442 3617976 const float *f_rescale_arr =
443 3671976 prism_centroid_fastscan_group_f_rescale(content, g, dim);
444 3617976 const float *f_error_arr =
445 3671976 prism_centroid_fastscan_group_f_error(content, g, dim);
446 3617976 const uint8_t *codes =
447 3671976 prism_centroid_fastscan_group_codes(content, g, dim);
448
449 3671976 vs_fastscan_accumulate_hacc(codes, cs->fs_lut, accum, dim);
450
451
3/4
✓ Branch 0 taken 162000 times.
✓ Branch 1 taken 34302459 times.
✓ Branch 2 taken 3779976 times.
✗ Branch 3 not taken.
38082435 for (uint32_t v = 0; v < g_count && cand_count < cand_cap; v++)
452 {
453 /* De-quantise the LUT accumulator the same way the
454 * posting fastscan path does (see prune_group_neon
455 * in posting_scan.c). */
456 34410459 float binary_ip = (float)accum[v] * lut_delta + lut_bias;
457 34410459 float final_dot = (2.0f * binary_ip - sum_t) * inv_sqrt_d;
458
459 34410459 Distance est = f_add_arr[v] + g_add -
460 34410459 2.0f * f_rescale_arr[v] * final_dot;
461 /* Matches rabitq_lower_bound(): err_margin =
462 * multiplier * f_error * g_error, plus a small
463 * floating-point margin proportional to |est|.
464 * error_scale = 0 (the default) zeroes the margin, so
465 * skip the arithmetic in that case. */
466 34410459 Distance err = 0.0f;
467
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34410459 times.
34410459 if (state->error_scale != 0.0f)
468 ✗ err = state->error_scale *
469 ✗ (err_mult * f_error_arr[v] * g_error +
470 ✗ 1e-5f * fabsf(est));
471
472 34410459 uint32_t page_idx = g_start + v;
473 34410459 cands[cand_count].child_blkno = child[v];
474 34410459 ItemPointerSet(
475 162000 &cands[cand_count].origin, page_blkno, page_idx);
476 34410459 cands[cand_count].distance = est;
477 34410459 cands[cand_count].error = err;
478 34410459 cand_count++;
479 }
480 }
481 3671976 break;
482 }
483 17449 case PRISM_CENTROID_FMT_HALF:
484 {
485 17449 float norm_q = (state->metric == DISTANCE_COSINE)
486 ✗ ? vs_l2_norm_squared(state->query, dim)
487
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17449 times.
17449 : 0.0f;
488
489
3/4
✓ Branch 0 taken 140135 times.
✓ Branch 1 taken 17449 times.
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
157584 for (uint16_t i = 0; i < count && cand_count < cand_cap; i++)
490 {
491 140135 const PrismCentroidEntryMeta *meta = prism_centroid_meta(page, i);
492 140135 const half *hvec = prism_centroid_half_data(page, i, dim);
493 140095 Distance dist;
494
495
2/3
✓ Branch 0 taken 1001 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 139134 times.
140135 switch (state->metric)
496 {
497 1001 case DISTANCE_INNER_PRODUCT:
498 1001 dist = -vs_f16_dot_product(hvec, state->query, dim);
499 1001 break;
500 ✗ case DISTANCE_COSINE:
501 {
502 ✗ float dot = vs_f16_dot_product(hvec, state->query, dim);
503 ✗ float norm_v = vs_f16_norm_sq(hvec, dim);
504 ✗ float denom = sqrtf(norm_q * norm_v);
505 ✗ dist = (denom > 0.0f) ? 1.0f - dot / denom : 1.0f;
506 ✗ break;
507 }
508 139134 default: /* L2 */
509 139134 dist = vs_f16_l2_squared(hvec, state->query, dim);
510 139134 break;
511 }
512
513 140135 cands[cand_count].child_blkno = meta->child_blkno;
514 140135 ItemPointerSet(&cands[cand_count].origin, page_blkno, i);
515 140135 cands[cand_count].distance = dist;
516 140135 cands[cand_count].error = 0.0f;
517 140135 cand_count++;
518 }
519 6 break;
520 }
521 }
522
523 1210588 return cand_count;
524 }
525
526 /* ----------------------------------------------------------------
527 * Top-K selection via VsTopK (error-bound-aware)
528 *
529 * Selects the best candidates using VsTopK pruning. Candidates
530 * with lower_bound >= threshold are pruned. With overlapping
531 * error intervals, may return more than k entries.
532 *
533 * Results are placed sorted in out[0..return_count).
534 * out must not alias cands.
535 * ---------------------------------------------------------------- */
536 static uint32_t
537 929390 select_topk_bounded(
538 PrismCentroidScratch *scratch,
539 Candidate *cands,
540 uint32_t count,
541 uint32_t k,
542 Candidate *out,
543 uint32_t out_cap)
544 {
545
2/2
✓ Branch 0 taken 706516 times.
✓ Branch 1 taken 222874 times.
929390 if (count == 0)
546 ✗ return 0;
547
548 /* Reuse the per-scan topk and extract buffer instead of allocating
549 * new ones every level; vs_topk_reset_to_k is O(1) unless k grows
550 * past the allocated capacity. */
551 929390 VsTopK *topk = &scratch->level_topk;
552 929390 vs_topk_reset_to_k(topk, k);
553
554 /* Centroid candidates have unique ids (the buf index), so we can
555 * skip the O(k) per-insert dedup scan. */
556
3/3
✓ Branch 0 taken 12483540 times.
✓ Branch 1 taken 42194535 times.
✓ Branch 2 taken 706516 times.
55384591 for (uint32_t i = 0; i < count; i++)
557 54455201 vs_topk_insert_unique(topk, cands[i].distance, cands[i].error, i);
558
559 /* entries_buf must hold topk->cand_count survivors; grow if needed.
560 * Grow in the scratch's owning context: this runs under whatever
561 * context the route was issued from — during index builds a per-row
562 * scratch context that is reset after every tuple — while the buffer
563 * must survive for the scratch's whole lifetime. */
564
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 929383 times.
929390 if (topk->cand_count > scratch->entries_cap)
565 {
566 7 uint32_t new_cap = scratch->entries_cap * 2;
567
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
7 while (new_cap < topk->cand_count)
568 ✗ new_cap *= 2;
569 7 vs_free(scratch->entries_buf);
570 13 scratch->entries_buf = vs_memctx_alloc(
571 6 scratch->memctx, new_cap * sizeof(VsTopKEntry));
572 7 scratch->entries_cap = new_cap;
573 }
574
575 706516 uint32_t nresults;
576 929390 vs_topk_extract_sorted_unique(topk, scratch->entries_buf, &nresults);
577
578
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 929390 times.
929390 if (nresults > out_cap)
579 ✗ nresults = out_cap;
580
581
2/2
✓ Branch 0 taken 15729348 times.
✓ Branch 1 taken 929390 times.
16658738 for (uint32_t i = 0; i < nresults; i++)
582 {
583 15729348 uint32_t idx = (uint32_t)scratch->entries_buf[i].id;
584 15729348 out[i] = cands[idx];
585 15729348 out[i].distance = scratch->entries_buf[i].distance;
586 15729348 out[i].error = scratch->entries_buf[i].error;
587 }
588
589 222874 return nresults;
590 }
591
592 /*
593 * Emit all of a centroid page's children as candidates without scoring.
594 *
595 * Used when a level's selection cannot reject anything (keep >= entry
596 * count): the distances would exist only to rank candidates for a
597 * selection that keeps them all, and the next level re-scores its own
598 * children from scratch, so computing them is pure waste. Candidates
599 * are emitted with zero distance/error.
600 */
601 static uint32_t
602 389050 emit_page_children(
603 Page page,
604 BlockNumber page_blkno,
605 Dimension dim,
606 Candidate *cands,
607 uint32_t cand_count,
608 uint32_t cand_cap)
609 {
610 389050 PrismCentroidPageOpaque *opaque = PRISM_CENTROID_OPAQUE(page);
611 389050 uint16_t count = opaque->entry_count;
612 389050 PrismCentroidFormat fmt = prism_centroid_page_format(page);
613
614
2/2
✓ Branch 0 taken 227206 times.
✓ Branch 1 taken 161844 times.
389050 if (fmt == PRISM_CENTROID_FMT_FASTSCAN)
615 {
616 227206 char *content = (char *)PageGetContents(page);
617 227206 uint32_t ngroups = (count + VS_FASTSCAN_GROUP - 1) / VS_FASTSCAN_GROUP;
618
619
2/2
✓ Branch 0 taken 227206 times.
✓ Branch 1 taken 227206 times.
454412 for (uint32_t g = 0; g < ngroups; g++)
620 {
621 227206 uint32_t g_start = g * VS_FASTSCAN_GROUP;
622 227206 uint32_t g_count = count - g_start;
623
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6000 times.
227206 if (g_count > VS_FASTSCAN_GROUP)
624 ✗ g_count = VS_FASTSCAN_GROUP;
625
626 221206 const BlockNumber *child = (const BlockNumber *)
627 227206 prism_centroid_fastscan_group_child(content, g, dim);
628
629
3/4
✓ Branch 0 taken 2083088 times.
✓ Branch 1 taken 227206 times.
✓ Branch 2 taken 18000 times.
✗ Branch 3 not taken.
2310294 for (uint32_t v = 0; v < g_count && cand_count < cand_cap; v++)
630 {
631 2083088 cands[cand_count].child_blkno = child[v];
632 2083088 ItemPointerSet(
633 2083088 &cands[cand_count].origin, page_blkno, g_start + v);
634 2083088 cands[cand_count].distance = 0.0f;
635 2083088 cands[cand_count].error = 0.0f;
636 2083088 cand_count++;
637 }
638 }
639 6000 return cand_count;
640 }
641
642
3/4
✓ Branch 0 taken 1442121 times.
✓ Branch 1 taken 161844 times.
✓ Branch 2 taken 898488 times.
✗ Branch 3 not taken.
1603965 for (uint16_t i = 0; i < count && cand_count < cand_cap; i++)
643 {
644 1442121 const PrismCentroidEntryMeta *meta = prism_centroid_meta(page, i);
645
646 1442121 cands[cand_count].child_blkno = meta->child_blkno;
647 1442121 ItemPointerSet(&cands[cand_count].origin, page_blkno, i);
648 1442121 cands[cand_count].distance = 0.0f;
649 1442121 cands[cand_count].error = 0.0f;
650 1442121 cand_count++;
651 }
652 112096 return cand_count;
653 }
654
655 uint32_t
656 658680 prism_centroid_beam_search(
657 const PrismCentroidSearchState *state,
658 BlockNumber first_centroid_blkno,
659 uint8_t nlevels,
660 PrismCentroidResult *results,
661 float *centroid_vecs,
662 PrismCentroidSearchStats *stats)
663 {
664
8/8
✓ Branch 0 taken 658678 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 193848 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 193846 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 193844 times.
658680 if (state == NULL || results == NULL || nlevels == 0 ||
665
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 464828 times.
464828 first_centroid_blkno == InvalidBlockNumber)
666 8 return 0;
667
668 658672 Dimension dim = state->dim;
669 658672 uint32_t beam_width = state->beam_width;
670 658672 uint32_t nprobe = state->nprobe;
671
672 /* Caller-owned scratch: pre-allocated buffers for candidate
673 * arrays and per-page batch scoring. Avoids 8 palloc + 2 memctx
674 * creations per query — a meaningful chunk of the allocator
675 * traffic on the hot path.
676 *
677 * If state->scratch is NULL we fall back to a one-shot
678 * allocation. The fallback exists for tests and ad-hoc callers;
679 * production query paths (PrismQueryState / PrismQueryCtx)
680 * pre-allocate and pass it in. */
681 658672 PrismCentroidScratch *scratch = state->scratch;
682 658672 PrismCentroidScratch *owned_scratch = NULL;
683
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 658666 times.
658672 if (scratch == NULL)
684 {
685 6 owned_scratch = prism_centroid_scratch_create(dim, beam_width);
686
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
6 if (owned_scratch == NULL)
687 ✗ return 0;
688 6 scratch = owned_scratch;
689 }
690 658672 uint32_t cand_cap = scratch->cand_cap;
691 658672 Candidate *buf_a = scratch->buf_a;
692 658672 Candidate *buf_b = scratch->buf_b;
693
694 /* Invalidate the per-query fastscan LUT cache. Built lazily on
695 * first FASTSCAN page encountered, then reused for all subsequent
696 * pages in this query. */
697 658672 scratch->fs_lut_valid = false;
698
699 /* centroid_vecs: will be used later for copying centroid vectors */
700 464828 (void)centroid_vecs;
701
702 /*
703 * buf_a accumulates raw candidates from score_page.
704 * buf_b receives the topk-selected survivors.
705 * After selection, buf_b becomes the live set for expansion.
706 */
707
708 658672 uint32_t centroid_pages_read = 0;
709
710 /* beam_width is the intermediate-level keep; the leaf level always
711 * returns nprobe (see keep below), and beam_width*fan_out >= nprobe
712 * covers the top-nprobe leaves, so beam_width may be < nprobe. */
713
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 193844 times.
658672 if (beam_width < 1)
714 ✗ beam_width = 1;
715
716
2/2
✓ Branch 0 taken 427692 times.
✓ Branch 1 taken 230980 times.
658672 uint32_t level0_keep = (nlevels == 1) ? nprobe : beam_width;
717
718 /* Level 0: read root centroid page(s), score ALL centroids.
719 *
720 * Fast path: when the root is a single page whose entry count does
721 * not exceed the level-0 keep, selection cannot reject anything —
722 * scoring would rank candidates for a no-op selection, and level 1
723 * re-scores its own children anyway. Emit the children directly
724 * and skip both the scoring and the top-K pass. */
725 658672 uint32_t raw_count = 0;
726 658672 bool level0_full = false;
727 658672 BlockNumber blkno = first_centroid_blkno;
728
729
2/2
✓ Branch 0 taken 660385 times.
✓ Branch 1 taken 658672 times.
1319057 while (blkno != InvalidBlockNumber)
730 {
731 660385 Page page = vs_storage_read_page(state->storage, blkno);
732 660385 PrismCentroidPageOpaque *opaque = PRISM_CENTROID_OPAQUE(page);
733 660385 centroid_pages_read++;
734
735
4/4
✓ Branch 0 taken 658672 times.
✓ Branch 1 taken 1713 times.
✓ Branch 2 taken 656963 times.
✓ Branch 3 taken 1709 times.
660385 if (raw_count == 0 && opaque->next_blkno == InvalidBlockNumber &&
736
4/4
✓ Branch 0 taken 572891 times.
✓ Branch 1 taken 84072 times.
✓ Branch 2 taken 389050 times.
✓ Branch 3 taken 183841 times.
656963 opaque->entry_count <= level0_keep && nlevels > 1)
737 {
738 270954 raw_count =
739 389050 emit_page_children(page, blkno, dim, buf_a, 0, cand_cap);
740 389050 level0_full = true;
741 }
742 else
743 {
744 271335 raw_count = score_page(
745 state,
746 page,
747 blkno,
748 dim,
749 buf_a,
750 raw_count,
751 cand_cap,
752 scratch);
753 }
754
755 660385 BlockNumber next_blkno = opaque->next_blkno;
756 660385 vs_storage_release_page(state->storage, blkno);
757 660385 blkno = next_blkno;
758 }
759
4/4
✓ Branch 0 taken 387712 times.
✓ Branch 1 taken 270960 times.
✓ Branch 2 taken 75744 times.
✓ Branch 3 taken 118094 times.
658672 if (stats && !level0_full)
760 269618 stats->dist_calcs += raw_count;
761
762 /* Select top-K from level 0 into buf_b (skipped when the fast path
763 * already kept everything).
764 *
765 * Error-bound-aware selection via VsTopK: keeps the beam_width
766 * candidates with smallest upper bounds, plus any additional
767 * candidates whose lower bound overlaps the threshold. For
768 * exact formats (error=0) this returns exactly beam_width. */
769 464828 Candidate *live;
770 464828 Candidate *expand_buf;
771 464828 uint32_t cand_count;
772
773
2/2
✓ Branch 0 taken 311970 times.
✓ Branch 1 taken 346702 times.
658672 if (level0_full)
774 {
775 118096 live = buf_a;
776 118096 expand_buf = buf_b;
777 118096 cand_count = raw_count;
778 }
779 else
780 {
781 269622 cand_count = select_topk_bounded(
782 scratch, buf_a, raw_count, level0_keep, buf_b, cand_cap);
783 269622 live = buf_b;
784 269622 expand_buf = buf_a;
785 }
786
787 /* Intermediate levels: expand winners via child_blkno */
788
2/2
✓ Branch 0 taken 659768 times.
✓ Branch 1 taken 658672 times.
1318440 for (uint8_t level = 1; level < nlevels; level++)
789 {
790 147126 uint32_t next_count = 0;
791
792
2/2
✓ Branch 0 taken 5454274 times.
✓ Branch 1 taken 659768 times.
6114042 for (uint32_t i = 0; i < cand_count; i++)
793 {
794 5454274 BlockNumber child_blkno = live[i].child_blkno;
795
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5454274 times.
5454274 if (child_blkno == InvalidBlockNumber)
796 ✗ continue;
797
798 1186840 BlockNumber cb = child_blkno;
799
2/2
✓ Branch 0 taken 5454274 times.
✓ Branch 1 taken 5454274 times.
10908548 while (cb != InvalidBlockNumber)
800 {
801 5454274 Page page = vs_storage_read_page(state->storage, cb);
802 5454274 centroid_pages_read++;
803 5454274 next_count = score_page(
804 state,
805 page,
806 cb,
807 dim,
808 expand_buf,
809 next_count,
810 cand_cap,
811 scratch);
812 5454274 PrismCentroidPageOpaque *opaque = PRISM_CENTROID_OPAQUE(page);
813 5454274 BlockNumber nb = opaque->next_blkno;
814 5454274 vs_storage_release_page(state->storage, cb);
815 5454274 cb = nb;
816 }
817 }
818
2/2
✓ Branch 0 taken 659762 times.
✓ Branch 1 taken 6 times.
659768 if (stats)
819 659762 stats->dist_calcs += next_count;
820
821 /* Select winners into live; expand_buf is the raw input. */
822
2/2
✓ Branch 0 taken 278794 times.
✓ Branch 1 taken 380974 times.
659768 uint32_t keep = (level == nlevels - 1) ? nprobe : beam_width;
823 659768 cand_count = select_topk_bounded(
824 scratch, expand_buf, next_count, keep, live, cand_cap);
825 }
826
827 /* Build results in caller-owned memory (cap at nprobe) */
828 658672 uint32_t result_count = cand_count < nprobe ? cand_count : nprobe;
829
2/2
✓ Branch 0 taken 13800282 times.
✓ Branch 1 taken 658672 times.
14458954 for (uint32_t i = 0; i < result_count; i++)
830 {
831 13800282 results[i].posting_head = live[i].child_blkno;
832 13800282 results[i].distance = live[i].distance;
833 13800282 results[i].error = live[i].error;
834 }
835
836 /* Extract centroid vectors for winning clusters.
837 * Only meaningful for FLOAT/HALF centroid pages — RaBitQ is a
838 * lossy binary encoding, so the full-precision centroid cannot
839 * be recovered. RaBitQ callers must obtain pt_centroid from its
840 * dedicated location (e.g., the first posting page). Skip the
841 * loop entirely rather than re-reading pages for nothing. */
842
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 658672 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
658672 if (centroid_vecs != NULL && result_count > 0 && state->qstate == NULL)
843 {
844 ✗ BlockNumber prev_blk = InvalidBlockNumber;
845 ✗ Page prev_page = NULL;
846
847 ✗ for (uint32_t i = 0; i < result_count; i++)
848 {
849 ✗ BlockNumber blk = ItemPointerGetBlockNumber(&live[i].origin);
850 ✗ OffsetNumber idx = ItemPointerGetOffsetNumber(&live[i].origin);
851
852 ✗ Page page;
853 ✗ if (blk == prev_blk)
854 {
855 ✗ page = prev_page;
856 }
857 else
858 {
859 ✗ if (prev_page != NULL)
860 ✗ vs_storage_release_page(state->storage, prev_blk);
861 ✗ page = vs_storage_read_page(state->storage, blk);
862 ✗ centroid_pages_read++;
863 ✗ prev_blk = blk;
864 ✗ prev_page = page;
865 }
866
867 ✗ float *dst = centroid_vecs + (size_t)i * dim;
868 ✗ PrismCentroidFormat fmt = prism_centroid_page_format(page);
869
870 ✗ switch (fmt)
871 {
872 ✗ case PRISM_CENTROID_FMT_FLOAT:
873 {
874 ✗ const float *src = prism_centroid_float_data(page, idx, dim);
875 ✗ memcpy(dst, src, dim * sizeof(float));
876 ✗ break;
877 }
878 ✗ case PRISM_CENTROID_FMT_HALF:
879 {
880 ✗ const half *src = prism_centroid_half_data(page, idx, dim);
881 ✗ for (Dimension d = 0; d < dim; d++)
882 ✗ dst[d] = vs_half_to_float(src[d]);
883 ✗ break;
884 }
885 ✗ case PRISM_CENTROID_FMT_RABITQ:
886 case PRISM_CENTROID_FMT_FASTSCAN:
887 /* Unreachable — both are lossy binary encodings and
888 * the outer guard skips this branch when the page
889 * format isn't FLOAT/HALF. */
890 ✗ break;
891 }
892 }
893
894 ✗ if (prev_page != NULL)
895 ✗ vs_storage_release_page(state->storage, prev_blk);
896 }
897
898
2/2
✓ Branch 0 taken 658666 times.
✓ Branch 1 taken 6 times.
658672 if (stats)
899 658666 stats->pages_read = centroid_pages_read;
900
901
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 658666 times.
658672 if (owned_scratch != NULL)
902 6 prism_centroid_scratch_free(owned_scratch);
903
904 193844 return result_count;
905 }
906