GCC Code Coverage Report


Directory: src/
File: src/index/posting_build.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 607 666 91.1%
Functions: 48 49 98.0%
Branches: 199 254 78.3%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * posting_build.c - Posting list construction
6 *
7 * Vector-to-cluster assignment (tree descent, SOAR, boundary
8 * replication) and streaming page builder. The page format (AoS or
9 * fastscan) is selected at init time via page_ops callbacks.
10 */
11
12 #include "vs_config.h"
13
14 #include <math.h>
15 #include <string.h>
16
17 #ifdef VS_HAVE_CBLAS
18 /* See matrix.c for the rationale on the Apple branch. */
19 #ifdef __APPLE__
20 #include <vecLib/cblas_new.h>
21 #else
22 #include <cblas.h>
23 #endif
24 #endif
25
26 #include "algo/distance.h"
27 #include "algo/vecops.h"
28 #include "core/memory.h"
29 #include "index/index_build.h"
30 #include "index/parallel_build.h"
31 #include "index/posting_build.h"
32 #include "index/query_scan.h"
33 #include "quant/fastscan.h"
34
35 /* ================================================================
36 * Vector-to-cluster assignment
37 *
38 * Building a posting list assigns each vector to a PRIMARY cluster and,
39 * when replication is enabled, to a SECONDARY (replica) cluster. These
40 * two use deliberately different methods, because they are different
41 * problems:
42 *
43 * PRIMARY -> tree descent (vs_hkmeans_assign).
44 * The nearest centroid via a greedy descent of the k-means tree:
45 * O(fan_out * nlevels) distance evaluations, a single root-to-leaf
46 * path. Two reasons it is the right tool here:
47 * 1. It is far cheaper than scanning every leaf. For primary we
48 * only need the (approximate) nearest, and a greedy descent
49 * finds it in ~log(nlist) work.
50 * 2. It MATCHES the query path. Queries route to clusters by
51 * descending the same tree, so assigning vectors the same way
52 * makes a vector and a nearby query land in the same cluster.
53 * Assigning by exact-nearest instead would create a
54 * build/query routing mismatch — some vectors would sit in
55 * their exact-nearest leaf that a nearby query's greedy descent
56 * never reaches — which measurably lowers recall. (Measured:
57 * exact brute-force primary was both slower and slightly lower
58 * recall than tree descent.)
59 *
60 * SECONDARY (SOAR + boundary) -> per-vector path in
61 * prism_build_assign_vector: boundary via a wider tree beam
62 * (vs_hkmeans_assign_topk), SOAR via a per-vector SIMD scan
63 * (prism_find_soar_secondary).
64 * ================================================================ */
65
66 static void
67 1000 normalize_vec(float *out, const float *in, Dimension dim)
68 {
69 1000 float norm = 0.0f;
70
2/2
✓ Branch 0 taken 16000 times.
✓ Branch 1 taken 1000 times.
17000 for (Dimension d = 0; d < dim; d++)
71 16000 norm += in[d] * in[d];
72
73
1/2
✓ Branch 0 taken 1000 times.
✗ Branch 1 not taken.
1000 if (norm > 0.0f)
74 {
75 1000 float inv = 1.0f / sqrtf(norm);
76
2/2
✓ Branch 0 taken 16000 times.
✓ Branch 1 taken 1000 times.
17000 for (Dimension d = 0; d < dim; d++)
77 16000 out[d] = in[d] * inv;
78 }
79 else
80 {
81 ✗ memcpy(out, in, dim * sizeof(float));
82 }
83 1000 }
84
85 PrismBuildWorkerBufs
86 18 prism_build_worker_bufs_create(Dimension dim)
87 {
88 18 return (PrismBuildWorkerBufs){
89 18 .norm_buf = vs_alloc(dim * sizeof(float)),
90 18 .residual_buf = vs_alloc(dim * sizeof(float)),
91 18 .cand_leaves = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(uint32_t)),
92 18 .cand_dists = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(Distance)),
93 };
94 }
95
96 void
97 18 prism_build_worker_bufs_free(PrismBuildWorkerBufs *bufs)
98 {
99 18 vs_free(bufs->norm_buf);
100 18 vs_free(bufs->residual_buf);
101 18 vs_free(bufs->cand_leaves);
102 18 vs_free(bufs->cand_dists);
103 18 bufs->norm_buf = NULL;
104 18 bufs->residual_buf = NULL;
105 18 bufs->cand_leaves = NULL;
106 18 bufs->cand_dists = NULL;
107 18 }
108
109 PrismBuildAssignment
110 13600 prism_build_assign_vector(
111 const HKMeansResult *tree,
112 const float *vec,
113 const PrismAssignParams *params,
114 PrismBuildWorkerBufs *bufs)
115 {
116 13600 const Dimension dim = params->dim;
117
118 ✗ Distance min_dist;
119 13600 uint32_t best_c = vs_hkmeans_assign(tree, vec, params->metric, &min_dist);
120
121 13600 const float *enc_vec = vec;
122
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 12600 times.
13600 if (params->metric == DISTANCE_COSINE)
123 {
124 1000 normalize_vec(bufs->norm_buf, vec, dim);
125 1000 enc_vec = bufs->norm_buf;
126 }
127
128 13600 uint32_t secondary = PRISM_INVALID_CLUSTER;
129
130 13600 bool has_soar = params->soar_lambda > 0.0;
131 13600 bool has_boundary = params->boundary_epsilon > 0.0;
132
133
2/4
✓ Branch 0 taken 13600 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 13600 times.
13600 if (has_soar || has_boundary)
134 {
135 ✗ const float *leaves = hk_leaf_centroids(tree);
136
137 /* Beam-descend once for the nearest leaves. These candidates serve
138 * both the boundary test (2nd-nearest) and the SOAR search: the SOAR
139 * objective is minimized by a near leaf, so the secondary is always
140 * among them — avoiding an O(nleaves) full scan per vector, which does
141 * not scale to large nlist. */
142 ✗ uint32_t ncand = vs_hkmeans_assign_topk(
143 tree,
144 enc_vec,
145 ✗ params->metric,
146 PRISM_SECONDARY_TOPK,
147 PRISM_SECONDARY_BEAM_WIDTH,
148 bufs->cand_leaves,
149 bufs->cand_dists);
150
151 ✗ uint32_t boundary_c2 = best_c;
152 ✗ if (has_boundary)
153 ✗ boundary_c2 = prism_find_secondary_cluster(
154 ✗ bufs->cand_leaves,
155 ✗ bufs->cand_dists,
156 ncand,
157 best_c,
158 min_dist,
159 ✗ params->boundary_epsilon);
160
161 ✗ bool should_replicate = has_boundary ? (boundary_c2 != best_c) : true;
162
163 ✗ if (should_replicate)
164 {
165 ✗ if (has_soar)
166 {
167 ✗ const float *cent = leaves + (size_t)best_c * dim;
168 ✗ float *r = bufs->residual_buf;
169 ✗ float norm = 0.0f;
170 ✗ for (Dimension d = 0; d < dim; d++)
171 {
172 ✗ r[d] = enc_vec[d] - cent[d];
173 ✗ norm += r[d] * r[d];
174 }
175 ✗ if (norm > 1e-7f)
176 {
177 ✗ float inv = 1.0f / sqrtf(norm);
178 ✗ for (Dimension d = 0; d < dim; d++)
179 ✗ r[d] *= inv;
180 }
181 ✗ secondary = prism_find_soar_secondary(
182 enc_vec,
183 leaves,
184 ✗ bufs->cand_leaves,
185 ncand,
186 dim,
187 best_c,
188 r,
189 ✗ params->soar_lambda);
190 }
191 else
192 {
193 ✗ secondary = boundary_c2;
194 }
195
196 ✗ if (secondary == best_c)
197 ✗ secondary = PRISM_INVALID_CLUSTER;
198 }
199 }
200
201 13600 return (PrismBuildAssignment){
202 .primary = best_c,
203 .secondary = secondary,
204 .enc_vector = enc_vec,
205 };
206 }
207
208 /* ----------------------------------------------------------------
209 * Compact posting entry (cluster-sorted build path) — see posting_build.h.
210 * ---------------------------------------------------------------- */
211
212 Size
213 1019 prism_posting_entry_size(Dimension dim)
214 {
215 1019 return sizeof(ItemPointerData) + 3 * sizeof(float) + (Size)((dim + 7) / 8);
216 }
217
218 void
219 ✗ prism_posting_entry_encode(
220 const RaBitQParams *params,
221 const float *vec,
222 const float *centroid,
223 Dimension dim,
224 RaBitQData *enc_buf,
225 RaBitQScratch *scratch,
226 ItemPointerData tid,
227 void *out_entry)
228 {
229 ✗ Vec32Ref vref = {.data = vec, .dim = dim};
230 ✗ Vec32Ref cref = {.data = centroid, .dim = dim};
231 ✗ vs_rabitq_encode_into_ex(params, vref, cref, enc_buf, scratch);
232 ✗ float f_error =
233 ✗ vs_rabitq_derive_f_error(enc_buf->f_add, enc_buf->f_rescale, dim);
234
235 ✗ char *p = (char *)out_entry;
236 ✗ memcpy(p, &tid, sizeof(ItemPointerData));
237 ✗ p += sizeof(ItemPointerData);
238 ✗ memcpy(p, &enc_buf->f_add, sizeof(float));
239 ✗ p += sizeof(float);
240 ✗ memcpy(p, &enc_buf->f_rescale, sizeof(float));
241 ✗ p += sizeof(float);
242 ✗ memcpy(p, &f_error, sizeof(float));
243 ✗ p += sizeof(float);
244 ✗ memcpy(p, enc_buf->bits, (size_t)((dim + 7) / 8));
245 ✗ }
246
247 void
248 597082 prism_posting_entry_encode_from_pt(
249 const RaBitQParams *params,
250 const float *pt_residual,
251 Dimension dim,
252 RaBitQData *enc_buf,
253 RaBitQScratch *scratch,
254 ItemPointerData tid,
255 void *out_entry)
256 {
257 /* Page-backed twin of prism_posting_entry_encode: the caller already has
258 * the rotated residual (pt_query - pt_centroid), e.g. from routing + the
259 * head page's pt_centroid, so no float centroid is needed. */
260 597082 vs_rabitq_encode_from_pt(params, pt_residual, enc_buf, scratch);
261 1004722 float f_error =
262 597082 vs_rabitq_derive_f_error(enc_buf->f_add, enc_buf->f_rescale, dim);
263
264 597082 char *p = (char *)out_entry;
265 597082 memcpy(p, &tid, sizeof(ItemPointerData));
266 597082 p += sizeof(ItemPointerData);
267 597082 memcpy(p, &enc_buf->f_add, sizeof(float));
268 597082 p += sizeof(float);
269 597082 memcpy(p, &enc_buf->f_rescale, sizeof(float));
270 597082 p += sizeof(float);
271 597082 memcpy(p, &f_error, sizeof(float));
272 597082 p += sizeof(float);
273 597082 memcpy(p, enc_buf->bits, (size_t)((dim + 7) / 8));
274 597082 }
275
276 void
277 434 prism_build_route_ctx_init(
278 PrismBuildRouteCtx *ctx,
279 PrismQueryState *qs,
280 PrismSorter *sorter,
281 const RaBitQParams *rq_params,
282 VsStorage *storage,
283 BlockNumber first_posting,
284 Dimension dim,
285 double soar_lambda,
286 double boundary_epsilon)
287 {
288 434 ctx->qs = qs;
289 434 ctx->sorter = sorter;
290 434 ctx->rq_params = rq_params;
291 434 ctx->storage = storage;
292 434 ctx->first_posting = first_posting;
293 434 ctx->dim = dim;
294 434 ctx->soar_lambda = soar_lambda;
295 434 ctx->boundary_epsilon = boundary_epsilon;
296
297 576 ctx->cand_pt = vs_alloc(
298 142 (size_t)PRISM_SECONDARY_TOPK * dim * sizeof(float));
299 434 ctx->cand_leaf = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(uint32_t));
300 434 ctx->cand_dist = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(Distance));
301 434 ctx->pt_r = vs_alloc((size_t)dim * sizeof(float));
302 434 ctx->enc_buf = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
303 434 vs_rabitq_scratch_init(&ctx->enc_scratch, dim);
304 434 ctx->entry = vs_alloc(prism_posting_entry_size(dim));
305
306 434 ctx->indtuples = 0;
307 434 ctx->soar_dupes = 0;
308 434 }
309
310 void
311 434 prism_build_route_ctx_cleanup(PrismBuildRouteCtx *ctx)
312 {
313 434 vs_free(ctx->cand_pt);
314 434 vs_free(ctx->cand_leaf);
315 434 vs_free(ctx->cand_dist);
316 434 vs_free(ctx->pt_r);
317 434 vs_free(ctx->enc_buf);
318 434 vs_rabitq_scratch_cleanup(&ctx->enc_scratch);
319 434 vs_free(ctx->entry);
320 434 }
321
322 /* Swap two gathered route candidates (leaf, exact distance, and the
323 * pt_centroid row, via the ctx's pt_r scratch). */
324 static void
325 463447 route_swap_candidates(
326 PrismBuildRouteCtx *ctx, uint32_t a, uint32_t b, Dimension dim)
327 {
328 463447 uint32_t leaf = ctx->cand_leaf[a];
329 463447 Distance dist = ctx->cand_dist[a];
330
331 463447 ctx->cand_leaf[a] = ctx->cand_leaf[b];
332 463447 ctx->cand_dist[a] = ctx->cand_dist[b];
333 463447 ctx->cand_leaf[b] = leaf;
334 463447 ctx->cand_dist[b] = dist;
335
336 463447 float *pa = ctx->cand_pt + (size_t)a * dim;
337 463447 float *pb = ctx->cand_pt + (size_t)b * dim;
338 463447 size_t nbytes = (size_t)dim * sizeof(float);
339 463447 memcpy(ctx->pt_r, pa, nbytes);
340 463447 memcpy(pa, pb, nbytes);
341 463447 memcpy(pb, ctx->pt_r, nbytes);
342 463447 }
343
344 /*
345 * Stamp a serialized posting entry as unreachable: estimated distance
346 * +inf with zero error, so every scan prunes it before it can enter
347 * the top-k threshold heap or the candidate buffer. Used for vectors
348 * with no defined distance under the index metric (a zero-norm vector
349 * under cosine): their exact distance is NaN, but their quantized
350 * estimate would look mid-range -- an impostor entering the top-k
351 * upper-bound heap of every query and falsely tightening its pruning
352 * threshold. The row stays indexed; it just can never be a result.
353 */
354 static void
355 170 mark_entry_unreachable(void *entry)
356 {
357 /* Serialized layout (see prism_posting_entry_encode_from_pt):
358 * [tid][f_add][f_rescale][f_error][bits]. p starts at f_add; the
359 * advance steps over the just-written f_add plus the untouched
360 * f_rescale to land exactly on f_error. */
361 170 char *p = (char *)entry + sizeof(ItemPointerData);
362 170 const float inf = INFINITY;
363 170 const float zero = 0.0f;
364
365 170 memcpy(p, &inf, sizeof(float));
366 170 p += 2 * sizeof(float);
367 170 memcpy(p, &zero, sizeof(float));
368 170 }
369
370 bool
371 561337 prism_build_route_emit(
372 PrismBuildRouteCtx *ctx, const float *vec, ItemPointerData tid)
373 {
374 561337 Dimension dim = ctx->dim;
375
376 /* No defined distance under cosine: encode as unreachable below.
377 * Squared norm -- zero iff the norm is zero -- skips the sqrt on
378 * this per-tuple build path. */
379
4/4
✓ Branch 0 taken 14922 times.
✓ Branch 1 taken 546415 times.
✓ Branch 2 taken 13077 times.
✓ Branch 3 taken 1845 times.
576259 bool degenerate = ctx->qs->index->metric == DISTANCE_COSINE &&
380 14922 vs_l2_norm_squared(vec, dim) == 0.0f;
381
382 /*
383 * Route page-backed, exactly as the query/insert do: descend the centroid
384 * pages, giving the nearest leaves' posting-head blocks + qs->pt_query
385 * (the rotated vector). No in-RAM tree.
386 */
387 561337 uint32_t n = prism_query_route(
388 ctx->qs,
389 vec,
390 PRISM_SECONDARY_TOPK,
391 VS_DISTANCE_MODE_ASYMMETRIC,
392 NULL);
393
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 561337 times.
561337 if (n == 0)
394 ✗ return false;
395
396 561337 bool has_soar = ctx->soar_lambda > 0.0;
397 561337 bool has_boundary = ctx->boundary_epsilon > 0.0;
398
399 /* Gather the beam candidates: leaf index and pt_centroid (the
400 * full-precision float encode reference, read from the head page or,
401 * spilled, its reference chain). The gather is unconditional: the exact
402 * primary re-rank below needs every finalist's pt_centroid, secondary
403 * selection or not. */
404
2/2
✓ Branch 0 taken 13572810 times.
✓ Branch 1 taken 561337 times.
14134147 for (uint32_t i = 0; i < n; i++)
405 {
406 13572810 BlockNumber h = ctx->qs->beam_results[i].posting_head;
407 13572810 ctx->cand_leaf[i] = prism_route_head_to_leaf(
408 ctx->first_posting, h, prism_posting_reference_pages(dim));
409 13572810 prism_posting_reference_read(
410 13572810 ctx->storage, h, dim, ctx->cand_pt + (size_t)i * dim);
411 }
412
413 /*
414 * Exact re-rank of the leaf finalists: the beam's leaf-level distances
415 * are 1-bit estimates whose noise misfiles rows, but each finalist's
416 * full-precision rotated centroid was just gathered, so one O(dim)
417 * distance per candidate recovers the true order (P^T preserves both
418 * L2 and dot products). The re-rank must use the index metric so the
419 * primary matches query-time routing: inner product ranks by -dot,
420 * while L2 and cosine rank by squared L2 (cosine queries and encode
421 * references are unit-normalized, making the two orders identical).
422 * Only the first two positions are order-sensitive -- the primary and,
423 * for the boundary gate, the exact 2nd-nearest -- and SOAR scans all
424 * candidates order-independently, so a top-2 selection suffices.
425 */
426 561337 bool rank_by_dot = ctx->qs->index->metric == DISTANCE_INNER_PRODUCT;
427
2/2
✓ Branch 0 taken 13572810 times.
✓ Branch 1 taken 561337 times.
14134147 for (uint32_t i = 0; i < n; i++)
428 {
429 13572810 const float *cand = ctx->cand_pt + (size_t)i * dim;
430 13572810 ctx->cand_dist[i] =
431 rank_by_dot
432 110000 ? -vs_dot_product(ctx->qs->pt_query, cand, dim)
433
2/2
✓ Branch 0 taken 110000 times.
✓ Branch 1 taken 13462810 times.
13682810 : vs_l2_distance_squared(ctx->qs->pt_query, cand, dim);
434 }
435
436 561337 uint32_t top = (n < 2) ? n : 2;
437
2/2
✓ Branch 0 taken 1040688 times.
✓ Branch 1 taken 561337 times.
1602025 for (uint32_t r = 0; r < top; r++)
438 {
439 1040688 uint32_t best = r;
440
2/2
✓ Branch 0 taken 25543595 times.
✓ Branch 1 taken 1040688 times.
26584283 for (uint32_t i = r + 1; i < n; i++)
441
2/2
✓ Branch 0 taken 1265393 times.
✓ Branch 1 taken 24278202 times.
25543595 if (ctx->cand_dist[i] < ctx->cand_dist[best])
442 1265393 best = i;
443
2/2
✓ Branch 0 taken 463447 times.
✓ Branch 1 taken 577241 times.
1040688 if (best != r)
444 463447 route_swap_candidates(ctx, r, best, dim);
445 }
446
447 /* Primary: encode pt_query - pt_centroid[0] and stream to the sorter. */
448 561337 uint32_t primary = ctx->cand_leaf[0];
449
2/2
✓ Branch 0 taken 81705083 times.
✓ Branch 1 taken 561337 times.
82266420 for (Dimension d = 0; d < dim; d++)
450 81705083 ctx->pt_r[d] = ctx->qs->pt_query[d] - ctx->cand_pt[d];
451 561337 prism_posting_entry_encode_from_pt(
452 ctx->rq_params,
453 561337 ctx->pt_r,
454 dim,
455 ctx->enc_buf,
456 &ctx->enc_scratch,
457 tid,
458 561337 ctx->entry);
459
2/2
✓ Branch 0 taken 125 times.
✓ Branch 1 taken 561212 times.
561337 if (degenerate)
460 125 mark_entry_unreachable(ctx->entry);
461 561337 prism_pbuild_sort_put(ctx->sorter, primary, ctx->entry);
462 561337 ctx->indtuples++;
463
464 /* Secondary (SOAR / boundary), in rotated space over the gathered
465 * candidates (positions index cand_pt). OA scoring and distances are
466 * norm-preserving under P^T, so this matches the float-space result. */
467
3/4
✓ Branch 0 taken 197148 times.
✓ Branch 1 taken 364189 times.
✓ Branch 2 taken 189442 times.
✗ Branch 3 not taken.
561337 if (!has_soar && !has_boundary)
468 189442 return false;
469
470 364189 bool boundary_repl = false;
471
2/4
✓ Branch 0 taken 352765 times.
✓ Branch 1 taken 11424 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
364189 if (has_boundary && n > 1)
472 {
473 352765 double d0 = (double)ctx->cand_dist[0];
474 351937 double gr = (d0 != 0.0) ? ((double)ctx->cand_dist[1] - d0) / fabs(d0)
475
2/2
✓ Branch 0 taken 351937 times.
✓ Branch 1 taken 828 times.
352765 : INFINITY;
476 352765 boundary_repl = gr <= ctx->boundary_epsilon;
477 }
478
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 364189 times.
364189 bool should = has_boundary ? boundary_repl : true;
479 364189 uint32_t sec_pos = 0; /* 0 = primary position = no secondary */
480
2/4
✓ Branch 0 taken 35745 times.
✓ Branch 1 taken 328444 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
364189 if (should && has_soar)
481 ✗ {
482 ✗ float norm = 0.0f;
483
2/2
✓ Branch 0 taken 2810476 times.
✓ Branch 1 taken 35745 times.
2846221 for (Dimension d = 0; d < dim; d++)
484 2810476 norm += ctx->pt_r[d] * ctx->pt_r[d];
485
1/2
✓ Branch 0 taken 35745 times.
✗ Branch 1 not taken.
35745 if (norm > 1e-7f)
486 {
487 35745 float inv = 1.0f / sqrtf(norm);
488
2/2
✓ Branch 0 taken 2810476 times.
✓ Branch 1 taken 35745 times.
2846221 for (Dimension d = 0; d < dim; d++)
489 2810476 ctx->pt_r[d] *= inv;
490 }
491 /* cand_leaves = NULL -> candidate position is the index; primary is
492 * position 0. leaf_centroids = cand_pt (rotated); vec = pt_query. */
493 35745 sec_pos = prism_find_soar_secondary(
494 35745 ctx->qs->pt_query,
495 35745 ctx->cand_pt,
496 NULL,
497 n,
498 dim,
499 0,
500 35745 ctx->pt_r,
501 ctx->soar_lambda);
502 }
503
1/4
✓ Branch 0 taken 328444 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
328444 else if (should && n > 1)
504 {
505 ✗ sec_pos = 1; /* boundary-only: the 2nd-nearest candidate */
506 }
507
508
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 35745 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 35745 times.
35745 if (sec_pos != 0 && ctx->cand_leaf[sec_pos] != primary)
509 {
510
2/2
✓ Branch 0 taken 2810476 times.
✓ Branch 1 taken 35745 times.
2846221 for (Dimension d = 0; d < dim; d++)
511 2810476 ctx->pt_r[d] = ctx->qs->pt_query[d] -
512 2810476 ctx->cand_pt[(size_t)sec_pos * dim + d];
513 35745 prism_posting_entry_encode_from_pt(
514 ctx->rq_params,
515 35745 ctx->pt_r,
516 dim,
517 ctx->enc_buf,
518 &ctx->enc_scratch,
519 tid,
520 35745 ctx->entry);
521
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 35700 times.
35745 if (degenerate)
522 45 mark_entry_unreachable(ctx->entry);
523 35745 prism_pbuild_sort_put(
524 35745 ctx->sorter, ctx->cand_leaf[sec_pos], ctx->entry);
525 35745 ctx->soar_dupes++;
526 35745 return true;
527 }
528 ✗ return false;
529 }
530
531 void
532 597082 prism_posting_entry_add(
533 PrismPostingBuilder *builder, const void *entry, Dimension dim)
534 {
535 597082 const char *p = (const char *)entry;
536 407640 ItemPointerData tid;
537 407640 float f_add, f_rescale, f_error;
538 597082 memcpy(&tid, p, sizeof(ItemPointerData));
539 597082 p += sizeof(ItemPointerData);
540 597082 memcpy(&f_add, p, sizeof(float));
541 597082 p += sizeof(float);
542 597082 memcpy(&f_rescale, p, sizeof(float));
543 597082 p += sizeof(float);
544 597082 memcpy(&f_error, p, sizeof(float));
545 597082 p += sizeof(float);
546 407640 (void)dim;
547 597082 prism_posting_builder_add_encoded(
548 builder, tid, f_add, f_rescale, f_error, (const uint8_t *)p);
549 597082 }
550
551 /* ----------------------------------------------------------------
552 * Shared helpers
553 * ---------------------------------------------------------------- */
554
555 /* Flush MIDDLE page i of a spilled list's head to storage and link it in. */
556 static void
557 304 reference_page_flush_middle(PrismPostingBuilder *builder, uint32_t i)
558 {
559 156 BlockNumber blkno;
560 156 Page page;
561
562
2/2
✓ Branch 0 taken 231 times.
✓ Branch 1 taken 73 times.
304 if (builder->fixed_first_blkno != InvalidBlockNumber)
563 {
564 231 blkno = builder->fixed_first_blkno + i;
565 231 page = vs_storage_write_page(builder->storage, blkno);
566 }
567 else
568 {
569 73 page = vs_storage_new_page(builder->storage, &blkno);
570 }
571 304 prism_posting_reference_page_fill(
572 304 page, builder->cluster_id, builder->dim, i, builder->ref_copy, 0);
573 304 vs_storage_commit_page(builder->storage, blkno);
574
575 304 Page prev = vs_storage_write_page(builder->storage, builder->prev_blkno);
576 304 prism_posting_opaque(prev)->next_blkno = blkno;
577 304 vs_storage_commit_page(builder->storage, builder->prev_blkno);
578 304 builder->prev_blkno = blkno;
579 304 }
580
581 static const PrismPostingPageOps fs_page_ops;
582
583 /*
584 * Reinit the builder's in-memory page (mem_page, the page it fills before
585 * flush_page writes it out) as a spilled list's head END page: the rest of
586 * the reference, then room for the list's first entries in the builder's
587 * format. It takes the place of the format's reinit_page
588 * (page_reinit_as_aos or page_reinit_as_fastscan) once the START and MIDDLE
589 * pages are flushed.
590 */
591 static void
592 542 page_reinit_as_reference_end(PrismPostingBuilder *builder)
593 {
594 542 uint32_t last = builder->ref_pages - 1;
595
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 424 times.
542 uint16_t fmt = builder->page_ops == &fs_page_ops
596 ? PRISM_POSTING_PAGE_FASTSCAN
597 : 0;
598
599 542 prism_posting_reference_page_fill(
600 542 builder->mem_page,
601 builder->cluster_id,
602 542 builder->dim,
603 last,
604 542 builder->ref_copy,
605 fmt);
606
2/3
✗ Branch 1 not taken.
✓ Branch 2 taken 148 times.
✓ Branch 3 taken 394 times.
542 Assert(prism_posting_head_part(
607 prism_posting_opaque(builder->mem_page)->flags) ==
608 PRISM_POSTING_HEAD_END);
609 542 builder->fs.page_ngroups = 0;
610 542 builder->fs.page_code_bytes = 0;
611 542 builder->end_pending = true;
612 1084 builder->end_blkno = builder->fixed_first_blkno != InvalidBlockNumber
613 338 ? builder->fixed_first_blkno + last
614
2/2
✓ Branch 0 taken 479 times.
✓ Branch 1 taken 63 times.
542 : InvalidBlockNumber;
615 542 }
616
617 /*
618 * Flush the in-memory page: write to storage and link
619 * into the chain. Prefers reserved contiguous blocks.
620 */
621 static void
622 24585 flush_page(PrismPostingBuilder *builder)
623 {
624 /*
625 * The first page of a chain (the posting-list head) must always be
626 * materialized, even with no entries: it carries the cluster's centroid
627 * metadata and pt_centroid, anchors the chain, and is where a scan begins.
628 * An empty head arises in the parallel bounded build, where the leader
629 * synthesizes the head while the workers stream the continuations (for
630 * fastscan nothing is merged into the head, so it stays empty). Later
631 * pages are still skipped when they hold no new entries.
632 */
633
6/6
✓ Branch 0 taken 12145 times.
✓ Branch 1 taken 12440 times.
✓ Branch 2 taken 479 times.
✓ Branch 3 taken 11666 times.
✓ Branch 4 taken 141 times.
✓ Branch 5 taken 338 times.
24585 if (!builder->page_dirty && !builder->is_first && !builder->end_pending)
634 542 return;
635
636 19143 BlockNumber blkno;
637 19143 Page spage;
638
4/4
✓ Branch 0 taken 20847 times.
✓ Branch 1 taken 3738 times.
✓ Branch 2 taken 19631 times.
✓ Branch 3 taken 1216 times.
24585 if (builder->is_first && builder->fixed_first_blkno != InvalidBlockNumber)
639 {
640 19631 blkno = builder->fixed_first_blkno;
641 19631 spage = vs_storage_write_page(builder->storage, blkno);
642 }
643
4/4
✓ Branch 0 taken 1014 times.
✓ Branch 1 taken 3940 times.
✓ Branch 2 taken 951 times.
✓ Branch 3 taken 63 times.
4954 else if (builder->end_pending && builder->end_blkno != InvalidBlockNumber)
644 {
645 951 blkno = builder->end_blkno;
646 951 spage = vs_storage_write_page(builder->storage, blkno);
647 }
648 else
649 {
650 4003 spage = vs_storage_new_page(builder->storage, &blkno);
651 }
652 24585 builder->end_pending = false;
653
654 24585 memcpy(spage, builder->mem_page, BLCKSZ);
655 24585 vs_storage_commit_page(builder->storage, blkno);
656
657 24585 bool was_first = builder->is_first;
658
2/2
✓ Branch 0 taken 20847 times.
✓ Branch 1 taken 3738 times.
24585 if (builder->is_first)
659 {
660 20847 builder->head_blkno = blkno;
661 20847 builder->is_first = false;
662 }
663
664
2/2
✓ Branch 0 taken 3266 times.
✓ Branch 1 taken 21319 times.
24585 if (builder->prev_blkno != InvalidBlockNumber)
665 {
666 1316 Page prev =
667 3266 vs_storage_write_page(builder->storage, builder->prev_blkno);
668 3266 prism_posting_opaque(prev)->next_blkno = blkno;
669 3266 vs_storage_commit_page(builder->storage, builder->prev_blkno);
670 }
671 24585 builder->prev_blkno = blkno;
672
673 /* A spilled head is followed by the rest of its reference: at the
674 * reserved blocks after a fixed head (the bulk-built head region strides
675 * by ref_pages), else at fresh pages. The END page, where the entries
676 * start, is written even if it gets none. */
677
4/4
✓ Branch 0 taken 20847 times.
✓ Branch 1 taken 3738 times.
✓ Branch 2 taken 542 times.
✓ Branch 3 taken 20305 times.
24585 if (was_first && builder->spilled)
678 {
679
2/2
✓ Branch 0 taken 304 times.
✓ Branch 1 taken 542 times.
846 for (uint32_t i = 1; i + 1 < builder->ref_pages; i++)
680 304 reference_page_flush_middle(builder, i);
681 542 page_reinit_as_reference_end(builder);
682 542 builder->page_dirty = false;
683 542 return;
684 }
685
686 24043 builder->page_ops->reinit_page(builder);
687 24043 builder->page_dirty = false;
688 }
689
690 /*
691 * Common init for both formats. When pt_centroid is NULL, initializes
692 * a continuation page (no pt_centroid header, overflow flags).
693 */
694 static void
695 12854 builder_init_common(
696 PrismPostingBuilder *builder,
697 VsStorage *storage,
698 const RaBitQParams *params,
699 Dimension dim,
700 uint32_t cluster_id,
701 const float *centroid,
702 const float *pt_centroid,
703 const PrismPostingPageOps *ops,
704 uint16_t first_page_flags)
705 {
706
2/2
✓ Branch 0 taken 149 times.
✓ Branch 1 taken 10751 times.
12854 memset(builder, 0, sizeof(*builder));
707 12854 builder->storage = storage;
708 12854 builder->params = params;
709 12854 builder->dim = dim;
710 12854 builder->cluster_id = cluster_id;
711 12854 builder->centroid = centroid;
712 12854 builder->head_blkno = InvalidBlockNumber;
713 12854 builder->prev_blkno = InvalidBlockNumber;
714 12854 builder->is_first = true;
715
2/2
✓ Branch 0 taken 149 times.
✓ Branch 1 taken 10751 times.
12854 builder->owns_head = prism_posting_is_head_start(first_page_flags);
716 12854 builder->n_entries = 0;
717 12854 builder->page_ops = ops;
718
719 12854 builder->fixed_first_blkno = InvalidBlockNumber;
720 12854 builder->end_blkno = InvalidBlockNumber;
721
722
2/2
✓ Branch 0 taken 149 times.
✓ Branch 1 taken 10751 times.
12854 builder->spilled = prism_posting_spilled(dim);
723 12854 builder->ref_pages = prism_posting_reference_pages(dim);
724 /* A spilled list's START page holds only reference, in either format.
725 * The entries start on the head's END page, after the reference. */
726
3/4
✓ Branch 0 taken 545 times.
✓ Branch 1 taken 12309 times.
✓ Branch 2 taken 545 times.
✗ Branch 3 not taken.
12854 if (builder->spilled && builder->owns_head)
727 {
728
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 545 times.
545 Assert(pt_centroid != NULL);
729 545 builder->ref_copy = vs_alloc((size_t)dim * sizeof(float));
730 545 memcpy(builder->ref_copy, pt_centroid, (size_t)dim * sizeof(float));
731 545 prism_posting_reference_page_fill(
732 545 builder->mem_page, cluster_id, dim, 0, builder->ref_copy, 0);
733 }
734 else
735 {
736 12309 prism_posting_page_init(
737 12309 builder->mem_page, cluster_id, dim, first_page_flags);
738
1/2
✓ Branch 0 taken 12309 times.
✗ Branch 1 not taken.
12309 if (pt_centroid != NULL)
739 12309 memcpy(prism_posting_pt_centroid_mut(builder->mem_page),
740 pt_centroid,
741 1558 dim * sizeof(float));
742 }
743
744
2/2
✓ Branch 0 taken 2270 times.
✓ Branch 1 taken 10584 times.
12854 builder->enc_buf = params ? vs_alloc(VS_RABITQ_DATA_SIZE(dim)) : NULL;
745
2/2
✓ Branch 0 taken 1946 times.
✓ Branch 1 taken 8 times.
2278 if (params)
746 12522 vs_rabitq_scratch_init(&builder->enc_scratch, dim);
747 12854 }
748
749 /* ----------------------------------------------------------------
750 * AoS page ops — one entry per call
751 * ---------------------------------------------------------------- */
752
753 static bool
754 266890 aos_write_entry(
755 PrismPostingBuilder *builder,
756 ItemPointerData tid,
757 float f_add,
758 float f_rescale,
759 float f_error,
760 const uint8_t *bits)
761 {
762
2/2
✓ Branch 1 taken 44973 times.
✓ Branch 2 taken 221917 times.
266890 if (!prism_posting_page_has_room(builder->mem_page))
763 901 return false;
764
765 265742 prism_posting_page_add(
766 221670 builder->mem_page,
767 265742 builder->dim,
768 tid,
769 f_add,
770 f_rescale,
771 f_error,
772 bits,
773 0);
774 265742 return true;
775 }
776
777 static void
778 6226 page_reinit_as_aos(PrismPostingBuilder *builder)
779 {
780 6226 prism_posting_page_init(
781 6226 builder->mem_page, builder->cluster_id, builder->dim, 0);
782 6226 }
783
784 static void
785 5130 aos_finalize(PrismPostingBuilder *builder)
786 {
787 1908 (void)builder;
788 5130 }
789
790 static void
791 5130 aos_cleanup(PrismPostingBuilder *builder)
792 {
793 1908 (void)builder;
794 5130 }
795
796 static const PrismPostingPageOps aos_page_ops = {
797 .write_entry = aos_write_entry,
798 .reinit_page = page_reinit_as_aos,
799 .finalize = aos_finalize,
800 .cleanup = aos_cleanup,
801 };
802
803 /* ----------------------------------------------------------------
804 * Fastscan page ops — buffer 32 entries, pack group, stream it out
805 *
806 * See the fastscan page format in posting_page.h. A group's codes go onto
807 * the page as far as they fit, breaking at chunk boundaries, and continue
808 * on the next page. Its metadata follows on the page where the codes end,
809 * or is deferred to the next page when it does not fit.
810 * ---------------------------------------------------------------- */
811
812 /* Bytes left on the in-memory page for group metadata and codes. */
813 static uint32_t
814 38620 fs_page_bytes_available(const PrismPostingBuilder *builder)
815 {
816 38620 uint16_t flags = prism_posting_opaque((Page)builder->mem_page)->flags;
817 38620 uint32_t used = builder->fs.page_ngroups * PRISM_FASTSCAN_META_BYTES +
818 38620 builder->fs.page_code_bytes;
819
820 /* A spilled list's START page holds only reference. */
821
3/3
✓ Branch 0 taken 33849 times.
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 4744 times.
38620 if (prism_posting_is_reference_only_page(flags, builder->dim))
822 20 return 0;
823 72442 return prism_fastscan_page_space(
824 4744 builder->dim,
825
2/2
✓ Branch 0 taken 30168 times.
✓ Branch 1 taken 3681 times.
73505 prism_posting_has_ref_prefix(flags, builder->dim)) -
826 used;
827 }
828
829 /* Append one group's metadata to the in-memory page. */
830 static void
831 17824 fs_page_write_group_meta(
832 PrismPostingBuilder *builder, const uint8_t *meta, uint32_t lanes)
833 {
834 16103 char *content =
835 17824 prism_posting_page_content(builder->mem_page, builder->dim);
836 17824 char *dst = prism_fastscan_group_base(content, builder->fs.page_ngroups);
837
838 17824 memcpy(dst, meta, PRISM_FASTSCAN_META_BYTES);
839 17824 builder->fs.page_ngroups++;
840 17824 prism_posting_opaque(builder->mem_page)->entry_count += (uint16_t)lanes;
841 17824 builder->page_dirty = true;
842 17824 }
843
844 /* Copy the staged codes in after the page's group metadata. */
845 static void
846 20675 fs_page_write_codes(PrismPostingBuilder *builder)
847 {
848 /* A spilled list's START page holds only reference. */
849
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 939 times.
40355 if (prism_posting_is_reference_only_page(
850
2/2
✓ Branch 1 taken 86 times.
✓ Branch 2 taken 19594 times.
20675 prism_posting_opaque(builder->mem_page)->flags, builder->dim))
851 {
852
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 142 times.
142 Assert(builder->fs.page_ngroups == 0);
853
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 142 times.
142 Assert(builder->fs.page_code_bytes == 0);
854 56 return;
855 }
856
857 19594 char *content =
858 20533 prism_posting_page_content(builder->mem_page, builder->dim);
859 19594 uint8_t *dst =
860 20533 prism_fastscan_page_codes(content, builder->fs.page_ngroups);
861
862 20533 memcpy(dst, builder->fs.page_codes, builder->fs.page_code_bytes);
863 41066 prism_posting_opaque(builder->mem_page)->code_bytes =
864 20533 (uint16_t)builder->fs.page_code_bytes;
865 }
866
867 /* Finish the in-memory page and start the next with the deferred metadata. */
868 static void
869 1639 fs_page_next(PrismPostingBuilder *builder)
870 {
871 1639 fs_page_write_codes(builder);
872 1639 flush_page(builder);
873
874
2/2
✓ Branch 0 taken 928 times.
✓ Branch 1 taken 711 times.
1639 Assert(builder->fs.ndeferred < PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS);
875
2/2
✓ Branch 0 taken 407 times.
✓ Branch 1 taken 1639 times.
2046 for (uint32_t i = 0; i < builder->fs.ndeferred; i++)
876 {
877 407 const uint8_t *meta = builder->fs.deferred +
878 407 (size_t)i * PRISM_FASTSCAN_META_BYTES;
879
880 407 fs_page_write_group_meta(builder, meta, builder->fs.deferred_lanes[i]);
881 }
882 1639 builder->fs.ndeferred = 0;
883 1639 }
884
885 /* Lay out the staged group's metadata. */
886 static void
887 17824 fs_pack_meta(const FsGroupStage *grp, uint8_t *meta)
888 {
889 17824 size_t tids_bytes = VS_FASTSCAN_GROUP * sizeof(ItemPointerData);
890 17824 size_t f_bytes = VS_FASTSCAN_GROUP * sizeof(float);
891 17824 uint32_t mask = 0;
892
893 17824 memcpy(meta, grp->tids, tids_bytes);
894 17824 memcpy(meta + tids_bytes, grp->f_add, f_bytes);
895 17824 memcpy(meta + tids_bytes + f_bytes, grp->f_rescale, f_bytes);
896 17824 memcpy(meta + tids_bytes + 2 * f_bytes, grp->f_error, f_bytes);
897 17824 memcpy(meta + tids_bytes + 3 * f_bytes, &mask, sizeof(mask));
898 17824 }
899
900 /*
901 * Pack the staged group and append it to the stream: codes first, as far
902 * as each page has room, then its metadata. The metadata goes where the
903 * codes end, so the scan finds it on the page it holds when the group's
904 * sums are complete. If it does not fit there, it is deferred to the start
905 * of the next page and the next group's codes fill the space instead.
906 */
907 static void
908 30069 fs_write_group(PrismPostingBuilder *builder)
909 {
910 30069 FsGroupStage *grp = &builder->fs.grp;
911
2/2
✓ Branch 0 taken 12245 times.
✓ Branch 1 taken 17824 times.
30069 if (grp->count == 0)
912 12245 return;
913
914 17824 Dimension dim = builder->dim;
915 17824 uint32_t code_len = VS_FASTSCAN_GROUP_BYTES(dim);
916 16103 uint8_t meta[PRISM_FASTSCAN_META_BYTES];
917
918 17824 fs_pack_meta(grp, meta);
919 17824 vs_fastscan_pack_codes(
920 17824 builder->fs.bits_buf, grp->count, dim, builder->fs.codes_buf);
921
922 17824 uint32_t pos = 0;
923
3/3
✓ Branch 0 taken 3043 times.
✓ Branch 1 taken 19474 times.
✓ Branch 2 taken 16103 times.
38620 while (pos < code_len)
924 {
925 20796 uint32_t left = code_len - pos;
926 20796 uint32_t avail = fs_page_bytes_available(builder);
927 4619 uint32_t take = left <= avail ? left
928
2/2
✓ Branch 0 taken 2824 times.
✓ Branch 1 taken 17972 times.
20796 : avail / PRISM_FASTSCAN_CHUNK_BYTES *
929 PRISM_FASTSCAN_CHUNK_BYTES;
930
931 /* With the most metadata already deferred, this group's could not
932 * be deferred as well, so its codes must not end on this page. That
933 * bounds the groups a scan has in flight. */
934
3/4
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 20648 times.
✓ Branch 2 taken 148 times.
✗ Branch 3 not taken.
20796 if (builder->fs.ndeferred == PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS - 1 &&
935 take == left)
936 148 take = (left - 1) / PRISM_FASTSCAN_CHUNK_BYTES *
937 PRISM_FASTSCAN_CHUNK_BYTES;
938
939
2/2
✓ Branch 0 taken 1555 times.
✓ Branch 1 taken 19241 times.
20796 if (take == 0)
940 {
941 1555 fs_page_next(builder);
942 1555 continue;
943 }
944
945 19241 uint8_t *dst = builder->fs.page_codes + builder->fs.page_code_bytes;
946
947 19241 memcpy(dst, builder->fs.codes_buf + pos, take);
948 19241 builder->fs.page_code_bytes += take;
949 19241 builder->page_dirty = true;
950 19241 pos += take;
951 }
952
953
2/2
✓ Branch 1 taken 17417 times.
✓ Branch 2 taken 407 times.
17824 if (fs_page_bytes_available(builder) >= PRISM_FASTSCAN_META_BYTES)
954 17417 fs_page_write_group_meta(builder, meta, grp->count);
955 else
956 {
957 /* Free space only shrinks, so a later group's metadata can never
958 * land on this page ahead of this one's: metadata stays in group
959 * order. The loop above keeps a group's codes off a page that
960 * already defers the most metadata, so there is always room here. */
961
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 407 times.
407 if (builder->fs.ndeferred >= PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS - 1)
962 ✗ vs_error(
963 VS_EXTENSION_NAME
964 ": fastscan posting builder deferred metadata for too "
965 "many groups");
966
967 407 uint8_t *dst = builder->fs.deferred +
968 407 (size_t)builder->fs.ndeferred *
969 PRISM_FASTSCAN_META_BYTES;
970
971 407 memcpy(dst, meta, PRISM_FASTSCAN_META_BYTES);
972 407 builder->fs.deferred_lanes[builder->fs.ndeferred++] = grp->count;
973 }
974
975 17824 memset(grp, 0, sizeof(*grp));
976 17824 memset(builder->fs.bits_buf,
977 0,
978 17824 (size_t)VS_FASTSCAN_GROUP * VS_RABITQ_BYTES(dim));
979 }
980
981 static bool
982 435738 fs_write_entry(
983 PrismPostingBuilder *builder,
984 ItemPointerData tid,
985 float f_add,
986 float f_rescale,
987 float f_error,
988 const uint8_t *bits)
989 {
990 435738 FsGroupStage *grp = &builder->fs.grp;
991 435738 uint32_t idx = grp->count;
992 435738 uint32_t packed_bytes = VS_RABITQ_BYTES(builder->dim);
993
994 435738 grp->tids[idx] = tid;
995 435738 grp->f_add[idx] = f_add;
996 435738 grp->f_rescale[idx] = f_rescale;
997 435738 grp->f_error[idx] = f_error;
998
2/2
✓ Branch 0 taken 9500 times.
✓ Branch 1 taken 374704 times.
435738 memcpy(builder->fs.bits_buf + (size_t)idx * packed_bytes,
999 bits,
1000 packed_bytes);
1001 435738 grp->count++;
1002
1003
2/2
✓ Branch 0 taken 11033 times.
✓ Branch 1 taken 424705 times.
435738 if (grp->count == VS_FASTSCAN_GROUP)
1004 11033 fs_write_group(builder);
1005
1006 435738 return true;
1007 }
1008
1009 static void
1010 17817 page_reinit_as_fastscan(PrismPostingBuilder *builder)
1011 {
1012 17817 prism_posting_page_init(
1013 17817 builder->mem_page,
1014 builder->cluster_id,
1015 17817 builder->dim,
1016 PRISM_POSTING_PAGE_FASTSCAN);
1017 17817 builder->fs.page_ngroups = 0;
1018 17817 builder->fs.page_code_bytes = 0;
1019 17817 }
1020
1021 static void
1022 19036 fs_finalize(PrismPostingBuilder *builder)
1023 {
1024 19036 fs_write_group(builder);
1025
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 18952 times.
19036 if (builder->fs.ndeferred > 0)
1026 84 fs_page_next(builder);
1027 19036 fs_page_write_codes(builder);
1028 19036 }
1029
1030 static void
1031 19044 fs_cleanup(PrismPostingBuilder *builder)
1032 {
1033 19044 vs_free(builder->fs.bits_buf);
1034 19044 builder->fs.bits_buf = NULL;
1035 19044 vs_free(builder->fs.codes_buf);
1036 19044 builder->fs.codes_buf = NULL;
1037 19044 vs_free(builder->fs.page_codes);
1038 19044 builder->fs.page_codes = NULL;
1039 19044 vs_free(builder->fs.deferred);
1040 19044 builder->fs.deferred = NULL;
1041 19044 }
1042
1043 /* Scratch for a fastscan builder. */
1044 static void
1045 19044 fs_alloc_buffers(PrismPostingBuilder *builder, Dimension dim)
1046 {
1047 19044 uint32_t packed_bytes = VS_RABITQ_BYTES(dim);
1048 19044 builder->fs.bits_buf = vs_alloc((size_t)VS_FASTSCAN_GROUP * packed_bytes);
1049 19044 builder->fs.codes_buf = vs_alloc(VS_FASTSCAN_GROUP_BYTES(dim));
1050 19044 builder->fs.page_codes = vs_alloc(prism_posting_page_usable());
1051 19044 builder->fs.deferred = vs_alloc(
1052 (size_t)(PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS - 1) *
1053 PRISM_FASTSCAN_META_BYTES);
1054 19044 }
1055
1056 static const PrismPostingPageOps fs_page_ops = {
1057 .write_entry = fs_write_entry,
1058 .reinit_page = page_reinit_as_fastscan,
1059 .finalize = fs_finalize,
1060 .cleanup = fs_cleanup,
1061 };
1062
1063 /* ----------------------------------------------------------------
1064 * Public API — init
1065 * ---------------------------------------------------------------- */
1066
1067 void
1068 2781 prism_posting_builder_init(
1069 PrismPostingBuilder *builder,
1070 VsStorage *storage,
1071 const RaBitQParams *params,
1072 Dimension dim,
1073 uint32_t cluster_id,
1074 const float *centroid,
1075 const float *pt_centroid)
1076 {
1077 2781 builder_init_common(
1078 builder,
1079 storage,
1080 params,
1081 dim,
1082 cluster_id,
1083 centroid,
1084 pt_centroid,
1085 &aos_page_ops,
1086 PRISM_POSTING_HEAD_START);
1087 2781 }
1088
1089 void
1090 10073 prism_posting_builder_init_fastscan(
1091 PrismPostingBuilder *builder,
1092 VsStorage *storage,
1093 const RaBitQParams *params,
1094 Dimension dim,
1095 uint32_t cluster_id,
1096 const float *centroid,
1097 const float *pt_centroid)
1098 {
1099 10073 builder_init_common(
1100 builder,
1101 storage,
1102 params,
1103 dim,
1104 cluster_id,
1105 centroid,
1106 pt_centroid,
1107 &fs_page_ops,
1108 PRISM_POSTING_HEAD_START | PRISM_POSTING_PAGE_FASTSCAN);
1109 10073 fs_alloc_buffers(builder, dim);
1110 10073 }
1111
1112 void
1113 12316 prism_posting_builder_init_fmt(
1114 PrismPostingBuilder *builder,
1115 VsStorage *storage,
1116 const RaBitQParams *params,
1117 Dimension dim,
1118 uint32_t cluster_id,
1119 const float *centroid,
1120 const float *pt_centroid,
1121 bool fastscan)
1122 {
1123
2/2
✓ Branch 0 taken 9655 times.
✓ Branch 1 taken 2661 times.
12316 if (fastscan)
1124 9655 prism_posting_builder_init_fastscan(
1125 builder,
1126 storage,
1127 params,
1128 dim,
1129 cluster_id,
1130 centroid,
1131 pt_centroid);
1132 else
1133 2661 prism_posting_builder_init(
1134 builder,
1135 storage,
1136 params,
1137 dim,
1138 cluster_id,
1139 centroid,
1140 pt_centroid);
1141 12316 }
1142
1143 void
1144 11320 prism_posting_builder_adopt_head(
1145 PrismPostingBuilder *builder,
1146 VsStorage *storage,
1147 const RaBitQParams *params,
1148 Dimension dim,
1149 uint32_t cluster_id,
1150 BlockNumber head_blk,
1151 bool fastscan)
1152 {
1153
2/2
✓ Branch 0 taken 883 times.
✓ Branch 1 taken 8879 times.
11320 memset(builder, 0, sizeof(*builder));
1154 11320 builder->storage = storage;
1155 11320 builder->params = params;
1156 11320 builder->dim = dim;
1157 11320 builder->cluster_id = cluster_id;
1158 11320 builder->centroid = NULL; /* entries arrive pre-encoded */
1159 11320 builder->head_blkno = InvalidBlockNumber;
1160 11320 builder->prev_blkno = InvalidBlockNumber;
1161 11320 builder->is_first = true;
1162 11320 builder->owns_head = true;
1163
2/2
✓ Branch 0 taken 975 times.
✓ Branch 1 taken 10345 times.
11320 builder->page_ops = fastscan ? &fs_page_ops : &aos_page_ops;
1164
1165 11320 builder->fixed_first_blkno = head_blk;
1166 11320 builder->end_blkno = InvalidBlockNumber;
1167 11320 builder->adopted_head = true;
1168
2/2
✓ Branch 0 taken 9621 times.
✓ Branch 1 taken 141 times.
11320 builder->spilled = prism_posting_spilled(dim);
1169 11320 builder->ref_pages = prism_posting_reference_pages(dim);
1170
1171
2/2
✓ Branch 0 taken 10845 times.
✓ Branch 1 taken 475 times.
11320 if (!builder->spilled)
1172 {
1173 /* Start from the pre-written head itself: it already carries the
1174 * cluster's header and pt_centroid. It must be empty — the pre-scan
1175 * writer never adds entries. */
1176 10845 Page hp = vs_storage_read_page(storage, head_blk);
1177
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 10845 times.
10845 Assert(prism_posting_opaque(hp)->live_count == 0);
1178 10845 memcpy(builder->mem_page, hp, BLCKSZ);
1179 10845 vs_storage_release_page(storage, head_blk);
1180 }
1181 else
1182 {
1183 /* The pre-written head and its middle reference pages stay as they
1184 * are. The entries start on the head's END page, which the builder
1185 * loads and rewrites in place, already linked. */
1186 334 BlockNumber blk = head_blk;
1187
1188
2/2
✓ Branch 0 taken 1177 times.
✓ Branch 1 taken 475 times.
1652 for (uint32_t i = 0; i < builder->ref_pages; i++)
1189 {
1190 1177 Page p = vs_storage_read_page(storage, blk);
1191 1177 const PrismPostingPageOpaque *op = prism_posting_opaque(p);
1192 1177 BlockNumber next = op->next_blkno;
1193 1177 bool end = i + 1 == builder->ref_pages;
1194
1195
7/7
✓ Branch 0 taken 290 times.
✓ Branch 1 taken 475 times.
✓ Branch 2 taken 561 times.
✓ Branch 3 taken 475 times.
✓ Branch 4 taken 78 times.
✓ Branch 5 taken 431 times.
✓ Branch 6 taken 746 times.
1326 Assert(prism_posting_head_part(op->flags) ==
1196 (end ? PRISM_POSTING_HEAD_END
1197 : i == 0 ? PRISM_POSTING_HEAD_START
1198 : PRISM_POSTING_HEAD_MIDDLE));
1199
3/4
✓ Branch 0 taken 475 times.
✓ Branch 1 taken 702 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 475 times.
1177 Assert(i > 0 || op->live_count == 0);
1200
2/2
✓ Branch 0 taken 475 times.
✓ Branch 1 taken 702 times.
1177 if (end)
1201 {
1202
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 475 times.
475 Assert(op->entry_count == 0);
1203 475 memcpy(builder->mem_page, p, BLCKSZ);
1204 }
1205 1177 vs_storage_release_page(storage, blk);
1206
2/2
✓ Branch 0 taken 702 times.
✓ Branch 1 taken 475 times.
1177 if (!end)
1207 702 blk = next;
1208 }
1209 475 builder->head_blkno = head_blk;
1210 475 builder->is_first = false;
1211 475 builder->end_pending = true;
1212 475 builder->end_blkno = blk;
1213 }
1214
1215 /* No encoder scratch: an adopted head only ever receives pre-encoded
1216 * entries (prism_posting_entry_add from the cluster-keyed sort), and this
1217 * runs once per posting list -- per-list encoder allocations would be
1218 * O(nlist) churn for buffers the raw-vector add path never touches. */
1219 11320 builder->enc_buf = NULL;
1220
1221
2/2
✓ Branch 0 taken 8971 times.
✓ Branch 1 taken 2349 times.
11320 if (fastscan)
1222 8971 fs_alloc_buffers(builder, dim);
1223 11320 }
1224
1225 void
1226 11630 prism_posting_builder_set_first_blkno(
1227 PrismPostingBuilder *builder, BlockNumber blkno)
1228 {
1229 11630 builder->fixed_first_blkno = blkno;
1230 11630 }
1231
1232 void
1233 701480 prism_posting_builder_add_encoded(
1234 PrismPostingBuilder *builder,
1235 ItemPointerData tid,
1236 float f_add,
1237 float f_rescale,
1238 float f_error,
1239 const uint8_t *bits)
1240 {
1241 /* More than one flush when a spilled START page and an END page
1242 * without room come first. */
1243
2/2
✓ Branch 1 taken 1148 times.
✓ Branch 2 taken 701480 times.
702628 while (!builder->page_ops->write_entry(
1244 builder, tid, f_add, f_rescale, f_error, bits))
1245 1148 flush_page(builder);
1246 701480 builder->page_dirty = true;
1247 701480 builder->n_entries++;
1248 701480 }
1249
1250 void
1251 24532 prism_posting_builder_add(
1252 PrismPostingBuilder *builder, ItemPointerData tid, const float *vector)
1253 {
1254 24532 prism_posting_builder_add_ex(builder, tid, vector, false);
1255 24532 }
1256
1257 void
1258 99871 prism_posting_builder_add_ex(
1259 PrismPostingBuilder *builder,
1260 ItemPointerData tid,
1261 const float *vector,
1262 bool unreachable)
1263 {
1264 /* Adopted heads carry no encoder (their entries arrive pre-encoded). */
1265
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 99871 times.
99871 Assert(builder->enc_buf != NULL);
1266
1267 99871 Vec32Ref vref = {.data = vector, .dim = builder->dim};
1268 99871 Vec32Ref cref = {.data = builder->centroid, .dim = builder->dim};
1269 99871 vs_rabitq_encode_into_ex(
1270 builder->params,
1271 vref,
1272 cref,
1273 builder->enc_buf,
1274 &builder->enc_scratch);
1275
1276 99871 float f_add = builder->enc_buf->f_add;
1277 116054 float f_error = vs_rabitq_derive_f_error(
1278 99871 f_add, builder->enc_buf->f_rescale, builder->dim);
1279
1280 /* Same stamp the build and insert paths apply -- see the header. */
1281
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 99791 times.
99871 if (unreachable)
1282 {
1283 80 f_add = INFINITY;
1284 80 f_error = 0.0f;
1285 }
1286
1287 99871 prism_posting_builder_add_encoded(
1288 builder,
1289 tid,
1290 f_add,
1291 83688 builder->enc_buf->f_rescale,
1292 f_error,
1293 99871 builder->enc_buf->bits);
1294 99871 }
1295
1296 BlockNumber
1297 24166 prism_posting_builder_finish(PrismPostingBuilder *builder)
1298 {
1299 24166 builder->page_ops->finalize(builder);
1300
1301 /* An adopted head that received no entries is already final on disk
1302 * (the pre-scan writer stamped it empty): skip the rewrite and the
1303 * restamp below, which would clobber its tail_blkno with an invalid
1304 * chain tail. Keyed on the entry count, since a spilled adoption starts
1305 * past the head rather than on it. */
1306
4/4
✓ Branch 0 taken 11320 times.
✓ Branch 1 taken 12846 times.
✓ Branch 2 taken 2847 times.
✓ Branch 3 taken 8473 times.
24166 if (builder->adopted_head && builder->n_entries == 0)
1307 {
1308 2847 builder->head_blkno = builder->fixed_first_blkno;
1309 2847 return builder->head_blkno;
1310 }
1311
1312 21319 flush_page(builder);
1313
2/2
✓ Branch 0 taken 479 times.
✓ Branch 1 taken 20840 times.
21319 if (builder->end_pending)
1314 479 flush_page(builder);
1315
1316 /*
1317 * Stamp the head's per-cluster metadata from state the builder already
1318 * tracked, so the runtime insert path finds the chain tail in O(1) with no
1319 * walk. prev_blkno is the last page flushed (the chain tail) and n_entries
1320 * is the exact entry count; for a head builder that holds the whole
1321 * chain these values are final.
1322 */
1323
2/4
✓ Branch 0 taken 21319 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 21319 times.
✗ Branch 3 not taken.
21319 if (builder->owns_head && builder->head_blkno != InvalidBlockNumber)
1324 {
1325 21319 Page hp = vs_storage_write_page(builder->storage, builder->head_blkno);
1326 21319 PrismPostingPageOpaque *op = prism_posting_opaque(hp);
1327 21319 op->tail_blkno = builder->prev_blkno;
1328 21319 op->live_count = builder->n_entries;
1329 21319 vs_storage_commit_page(builder->storage, builder->head_blkno);
1330 }
1331
1332 21319 return builder->head_blkno;
1333 }
1334
1335 void
1336 24174 prism_posting_builder_cleanup(PrismPostingBuilder *builder)
1337 {
1338 24174 builder->page_ops->cleanup(builder);
1339
2/2
✓ Branch 0 taken 12522 times.
✓ Branch 1 taken 11652 times.
24174 if (builder->enc_buf != NULL)
1340 {
1341 12522 vs_rabitq_scratch_cleanup(&builder->enc_scratch);
1342 12522 vs_free(builder->enc_buf);
1343 12522 builder->enc_buf = NULL;
1344 }
1345
2/2
✓ Branch 0 taken 545 times.
✓ Branch 1 taken 23629 times.
24174 if (builder->ref_copy != NULL)
1346 {
1347 545 vs_free(builder->ref_copy);
1348 545 builder->ref_copy = NULL;
1349 }
1350 24174 }
1351
1352 /* ----------------------------------------------------------------
1353 * Flat builder — one buffer per cluster (unchanged)
1354 * ---------------------------------------------------------------- */
1355
1356 void
1357 188 prism_flat_posting_builder_init(
1358 PrismFlatPostingBuilder *builder,
1359 const RaBitQParams *params,
1360 Dimension dim,
1361 uint32_t cluster_id,
1362 const float *centroid,
1363 uint32_t count)
1364 {
1365 188 builder->params = params;
1366 188 builder->dim = dim;
1367 188 builder->cluster_id = cluster_id;
1368 188 builder->centroid = centroid;
1369 188 builder->max_entries = count;
1370
1371 188 size_t buf_size = prism_posting_flat_page_size(dim, count);
1372 188 builder->buf = vs_alloc(buf_size);
1373 188 memset(builder->buf, 0, buf_size);
1374 188 prism_posting_flat_init(builder->buf, count, cluster_id);
1375
1376 188 builder->enc_buf = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
1377 188 }
1378
1379 void
1380 12240 prism_flat_posting_builder_add(
1381 PrismFlatPostingBuilder *builder,
1382 ItemPointerData tid,
1383 const float *vector)
1384 {
1385 12240 Dimension dim = builder->dim;
1386
1387 12240 Vec32Ref vref = {.data = vector, .dim = dim};
1388 12240 Vec32Ref cref = {.data = builder->centroid, .dim = dim};
1389 12240 vs_rabitq_encode_into(builder->params, vref, cref, builder->enc_buf);
1390
1391 12240 float f_error = vs_rabitq_derive_f_error(
1392 12240 builder->enc_buf->f_add, builder->enc_buf->f_rescale, dim);
1393
1394 12240 prism_posting_flat_add(
1395 builder->buf,
1396 dim,
1397 tid,
1398 12240 builder->enc_buf->f_add,
1399 12240 builder->enc_buf->f_rescale,
1400 f_error,
1401 12240 builder->enc_buf->bits,
1402 0);
1403 12240 }
1404
1405 char *
1406 188 prism_flat_posting_builder_finish(PrismFlatPostingBuilder *builder)
1407 {
1408 188 return builder->buf;
1409 }
1410
1411 void
1412 188 prism_flat_posting_builder_cleanup(PrismFlatPostingBuilder *builder)
1413 {
1414
1/2
✓ Branch 0 taken 188 times.
✗ Branch 1 not taken.
188 if (builder->enc_buf != NULL)
1415 {
1416 188 vs_free(builder->enc_buf);
1417 188 builder->enc_buf = NULL;
1418 }
1419 188 }
1420
1421 /* See posting_build.h: the route/filter/normalize half of the refine pass,
1422 * shared verbatim by the serial and parallel builds. */
1423 const float *
1424 72600 prism_refine_route_row(
1425 struct PrismQueryState *qs,
1426 BlockNumber first_posting,
1427 const float *vec,
1428 Dimension dim,
1429 bool cosine,
1430 float *scratch,
1431 uint32_t tile_lo,
1432 uint32_t tile_hi,
1433 uint32_t *out_idx)
1434 {
1435 72600 uint32_t n =
1436 72600 prism_query_route(qs, vec, 1, VS_DISTANCE_MODE_ASYMMETRIC, NULL);
1437
1/2
✓ Branch 0 taken 72600 times.
✗ Branch 1 not taken.
72600 if (n == 0)
1438 ✗ return NULL;
1439
1440 72600 uint32_t leaf = prism_route_head_to_leaf(
1441 first_posting,
1442
2/2
✓ Branch 0 taken 48600 times.
✓ Branch 1 taken 24000 times.
72600 qs->beam_results[0].posting_head,
1443 prism_posting_reference_pages(dim));
1444
2/4
✓ Branch 0 taken 48600 times.
✓ Branch 1 taken 24000 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
72600 if (leaf < tile_lo || leaf >= tile_hi)
1445 ✗ return NULL;
1446 48600 *out_idx = leaf - tile_lo;
1447
1448 /* Cosine centroids are trained in normalized space, so the mean must
1449 * average the normalized vectors. */
1450
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48600 times.
48600 if (cosine)
1451 {
1452 ✗ memcpy(scratch, vec, (size_t)dim * sizeof(float));
1453 ✗ vs_l2_normalize(scratch, dim);
1454 ✗ return scratch;
1455 }
1456 ✗ return vec;
1457 }
1458
1459 void
1460 7 prism_refine_write_means(
1461 const double *sums,
1462 const uint64_t *counts,
1463 uint32_t lo,
1464 uint32_t hi,
1465 Dimension dim,
1466 float *scratch,
1467 PrismLeafWriteFn write_head,
1468 void *write_head_ctx)
1469 {
1470
2/2
✓ Branch 0 taken 4284 times.
✓ Branch 1 taken 7 times.
4291 for (uint32_t l = lo; l < hi; l++)
1471 {
1472
2/2
✓ Branch 0 taken 3978 times.
✓ Branch 1 taken 306 times.
4284 if (counts[l - lo] == 0)
1473 3978 continue; /* keep the sample-trained head for an empty leaf */
1474 306 const double *sum = sums + (size_t)(l - lo) * dim;
1475 306 double inv = 1.0 / (double)counts[l - lo];
1476
2/2
✓ Branch 0 taken 36480 times.
✓ Branch 1 taken 306 times.
36786 for (Dimension j = 0; j < dim; j++)
1477 36480 scratch[j] = (float)(sum[j] * inv);
1478 306 write_head(write_head_ctx, l, scratch);
1479 }
1480 7 }
1481
1482 /* See posting_build.h: the one leaf-head writer both builds share. */
1483 void
1484 11622 prism_write_leaf_head(void *arg, uint32_t leaf, const float *centroid)
1485 {
1486 11622 PrismHeadWriteCtx *h = (PrismHeadWriteCtx *)arg;
1487 11622 vs_rabitq_rotate(h->rq_params, centroid, h->pt);
1488
1489 /* The builder's scratch is freed with the context, which the standalone
1490 * arena would otherwise keep for every leaf. */
1491 11622 VsMemCtx outer = vs_memctx_switch(h->leaf_ctx);
1492 10068 PrismPostingBuilder hb;
1493 11622 prism_posting_builder_init_fmt(
1494 &hb,
1495 h->storage,
1496 h->rq_params,
1497 11622 h->dim,
1498 leaf,
1499 centroid,
1500 11622 h->pt,
1501 11622 h->fastscan);
1502 11622 prism_posting_builder_set_first_blkno(
1503 &hb, prism_leaf_head_blkno(h->first_posting, leaf, h->stride));
1504 11622 prism_posting_builder_finish(&hb);
1505 11622 prism_posting_builder_cleanup(&hb);
1506 11622 vs_memctx_switch(outer);
1507 11622 vs_memctx_reset(h->leaf_ctx);
1508 11622 }
1509