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