GCC Code Coverage Report

Directory: src/
File: src/index/posting_build.c
Date: 2026-09-30 11:11:31
Exec Total Coverage
Lines: 467 526 88.8%
Functions: 40 41 97.6%
Branches: 119 166 71.7%
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 14 prism_build_worker_bufs_create(Dimension dim)
87 {
88 14 return (PrismBuildWorkerBufs){
89 14 .norm_buf = vs_alloc(dim * sizeof(float)),
90 14 .residual_buf = vs_alloc(dim * sizeof(float)),
91 14 .cand_leaves = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(uint32_t)),
92 14 .cand_dists = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(Distance)),
93 };
94 }
95
96 void
97 14 prism_build_worker_bufs_free(PrismBuildWorkerBufs *bufs)
98 {
99 14 vs_free(bufs->norm_buf);
100 14 vs_free(bufs->residual_buf);
101 14 vs_free(bufs->cand_leaves);
102 14 vs_free(bufs->cand_dists);
103 14 bufs->norm_buf = NULL;
104 14 bufs->residual_buf = NULL;
105 14 bufs->cand_leaves = NULL;
106 14 bufs->cand_dists = NULL;
107 14 }
108
109 PrismBuildAssignment
110 11400 prism_build_assign_vector(
111 const HKMeansResult *tree,
112 const float *vec,
113 const PrismAssignParams *params,
114 PrismBuildWorkerBufs *bufs)
115 {
116 11400 const Dimension dim = params->dim;
117
118 ✗ Distance min_dist;
119 11400 uint32_t best_c = vs_hkmeans_assign(tree, vec, params->metric, &min_dist);
120
121 11400 const float *enc_vec = vec;
122
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 10400 times.
 11400 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 11400 uint32_t secondary = PRISM_INVALID_CLUSTER;
129
130 11400 bool has_soar = params->soar_lambda > 0.0;
131 11400 bool has_boundary = params->boundary_epsilon > 0.0;
132
133
2/4
✓ Branch 0 taken 11400 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 11400 times.
 11400 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 11400 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 807 prism_posting_entry_size(Dimension dim)
214 {
215 807 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 564506 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 564506 vs_rabitq_encode_from_pt(params, pt_residual, enc_buf, scratch);
261 958650 float f_error =
262 564506 vs_rabitq_derive_f_error(enc_buf->f_add, enc_buf->f_rescale, dim);
263
264 564506 char *p = (char *)out_entry;
265 564506 memcpy(p, &tid, sizeof(ItemPointerData));
266 564506 p += sizeof(ItemPointerData);
267 564506 memcpy(p, &enc_buf->f_add, sizeof(float));
268 564506 p += sizeof(float);
269 564506 memcpy(p, &enc_buf->f_rescale, sizeof(float));
270 564506 p += sizeof(float);
271 564506 memcpy(p, &f_error, sizeof(float));
272 564506 p += sizeof(float);
273 564506 memcpy(p, enc_buf->bits, (size_t)((dim + 7) / 8));
274 564506 }
275
276 void
277 341 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 341 ctx->qs = qs;
289 341 ctx->sorter = sorter;
290 341 ctx->rq_params = rq_params;
291 341 ctx->storage = storage;
292 341 ctx->first_posting = first_posting;
293 341 ctx->dim = dim;
294 341 ctx->soar_lambda = soar_lambda;
295 341 ctx->boundary_epsilon = boundary_epsilon;
296
297 341 ctx->cand_pt = vs_alloc(
298 (size_t)PRISM_SECONDARY_TOPK * dim * sizeof(float));
299 341 ctx->cand_leaf = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(uint32_t));
300 341 ctx->cand_dist = vs_alloc(PRISM_SECONDARY_TOPK * sizeof(Distance));
301 341 ctx->pt_r = vs_alloc((size_t)dim * sizeof(float));
302 341 ctx->enc_buf = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
303 341 vs_rabitq_scratch_init(&ctx->enc_scratch, dim);
304 341 ctx->entry = vs_alloc(prism_posting_entry_size(dim));
305
306 341 ctx->indtuples = 0;
307 341 ctx->soar_dupes = 0;
308 341 }
309
310 void
311 341 prism_build_route_ctx_cleanup(PrismBuildRouteCtx *ctx)
312 {
313 341 vs_free(ctx->cand_pt);
314 341 vs_free(ctx->cand_leaf);
315 341 vs_free(ctx->cand_dist);
316 341 vs_free(ctx->pt_r);
317 341 vs_free(ctx->enc_buf);
318 341 vs_rabitq_scratch_cleanup(&ctx->enc_scratch);
319 341 vs_free(ctx->entry);
320 341 }
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 456480 route_swap_candidates(
326 PrismBuildRouteCtx *ctx, uint32_t a, uint32_t b, Dimension dim)
327 {
328 456480 uint32_t leaf = ctx->cand_leaf[a];
329 456480 Distance dist = ctx->cand_dist[a];
330
331 456480 ctx->cand_leaf[a] = ctx->cand_leaf[b];
332 456480 ctx->cand_dist[a] = ctx->cand_dist[b];
333 456480 ctx->cand_leaf[b] = leaf;
334 456480 ctx->cand_dist[b] = dist;
335
336 456480 float *pa = ctx->cand_pt + (size_t)a * dim;
337 456480 float *pb = ctx->cand_pt + (size_t)b * dim;
338 456480 size_t nbytes = (size_t)dim * sizeof(float);
339 456480 memcpy(ctx->pt_r, pa, nbytes);
340 456480 memcpy(pa, pb, nbytes);
341 456480 memcpy(pb, ctx->pt_r, nbytes);
342 456480 }
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 530818 prism_build_route_emit(
372 PrismBuildRouteCtx *ctx, const float *vec, ItemPointerData tid)
373 {
374 530818 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 13722 times.
✓ Branch 1 taken 517096 times.
✓ Branch 2 taken 11877 times.
✓ Branch 3 taken 1845 times.
 544540 bool degenerate = ctx->qs->index->metric == DISTANCE_COSINE &&
380 13722 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 530818 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 530818 times.
 530818 if (n == 0)
394 ✗ return false;
395
396 530818 bool has_soar = ctx->soar_lambda > 0.0;
397 530818 bool has_boundary = ctx->boundary_epsilon > 0.0;
398
399 /* Gather the beam candidates: leaf index and pt_centroid (read from each
400 * head page -- the full-precision float encode reference). The gather is
401 * unconditional: the exact primary re-rank below needs every finalist's
402 * pt_centroid, secondary selection or not. */
403
2/2
✓ Branch 0 taken 13294466 times.
✓ Branch 1 taken 530818 times.
 13825284 for (uint32_t i = 0; i < n; i++)
404 {
405 13294466 BlockNumber h = ctx->qs->beam_results[i].posting_head;
406 13294466 ctx->cand_leaf[i] = prism_route_head_to_leaf(ctx->first_posting, h);
407 13294466 Page hp = vs_storage_read_page(ctx->storage, h);
408 15752428 memcpy(ctx->cand_pt + (size_t)i * dim,
409 13294466 prism_posting_pt_centroid(hp),
410 13294466 (size_t)dim * sizeof(float));
411 13294466 vs_storage_release_page(ctx->storage, h);
412 }
413
414 /*
415 * Exact re-rank of the leaf finalists: the beam's leaf-level distances
416 * are 1-bit estimates whose noise misfiles rows, but each finalist's
417 * full-precision rotated centroid was just gathered, so one O(dim)
418 * distance per candidate recovers the true order (P^T preserves both
419 * L2 and dot products). The re-rank must use the index metric so the
420 * primary matches query-time routing: inner product ranks by -dot,
421 * while L2 and cosine rank by squared L2 (cosine queries and encode
422 * references are unit-normalized, making the two orders identical).
423 * Only the first two positions are order-sensitive -- the primary and,
424 * for the boundary gate, the exact 2nd-nearest -- and SOAR scans all
425 * candidates order-independently, so a top-2 selection suffices.
426 */
427 530818 bool rank_by_dot = ctx->qs->index->metric == DISTANCE_INNER_PRODUCT;
428
2/2
✓ Branch 0 taken 13294466 times.
✓ Branch 1 taken 530818 times.
 13825284 for (uint32_t i = 0; i < n; i++)
429 {
430 13294466 const float *cand = ctx->cand_pt + (size_t)i * dim;
431 13294466 ctx->cand_dist[i] =
432 rank_by_dot
433 110000 ? -vs_dot_product(ctx->qs->pt_query, cand, dim)
434
2/2
✓ Branch 0 taken 110000 times.
✓ Branch 1 taken 13184466 times.
 13404466 : vs_l2_distance_squared(ctx->qs->pt_query, cand, dim);
435 }
436
437 530818 uint32_t top = (n < 2) ? n : 2;
438
2/2
✓ Branch 0 taken 986214 times.
✓ Branch 1 taken 530818 times.
 1517032 for (uint32_t r = 0; r < top; r++)
439 {
440 986214 uint32_t best = r;
441
2/2
✓ Branch 0 taken 25071900 times.
✓ Branch 1 taken 986214 times.
 26058114 for (uint32_t i = r + 1; i < n; i++)
442
2/2
✓ Branch 0 taken 1212816 times.
✓ Branch 1 taken 23859084 times.
 25071900 if (ctx->cand_dist[i] < ctx->cand_dist[best])
443 1212816 best = i;
444
2/2
✓ Branch 0 taken 456480 times.
✓ Branch 1 taken 529734 times.
 986214 if (best != r)
445 456480 route_swap_candidates(ctx, r, best, dim);
446 }
447
448 /* Primary: encode pt_query - pt_centroid[0] and stream to the sorter. */
449 530818 uint32_t primary = ctx->cand_leaf[0];
450
2/2
✓ Branch 0 taken 30053701 times.
✓ Branch 1 taken 530818 times.
 30584519 for (Dimension d = 0; d < dim; d++)
451 30053701 ctx->pt_r[d] = ctx->qs->pt_query[d] - ctx->cand_pt[d];
452 530818 prism_posting_entry_encode_from_pt(
453 ctx->rq_params,
454 530818 ctx->pt_r,
455 dim,
456 ctx->enc_buf,
457 &ctx->enc_scratch,
458 tid,
459 530818 ctx->entry);
460
2/2
✓ Branch 0 taken 125 times.
✓ Branch 1 taken 530693 times.
 530818 if (degenerate)
461 125 mark_entry_unreachable(ctx->entry);
462 530818 prism_pbuild_sort_put(ctx->sorter, primary, ctx->entry);
463 530818 ctx->indtuples++;
464
465 /* Secondary (SOAR / boundary), in rotated space over the gathered
466 * candidates (positions index cand_pt). OA scoring and distances are
467 * norm-preserving under P^T, so this matches the float-space result. */
468
3/4
✓ Branch 0 taken 176165 times.
✓ Branch 1 taken 354653 times.
✓ Branch 2 taken 170362 times.
✗ Branch 3 not taken.
 530818 if (!has_soar && !has_boundary)
469 170362 return false;
470
471 354653 bool boundary_repl = false;
472
2/4
✓ Branch 0 taken 346793 times.
✓ Branch 1 taken 7860 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 354653 if (has_boundary && n > 1)
473 {
474 346793 double d0 = (double)ctx->cand_dist[0];
475 1039598 double gr = (d0 != 0.0) ? ((double)ctx->cand_dist[1] - d0) / fabs(d0)
476
2/2
✓ Branch 0 taken 346012 times.
✓ Branch 1 taken 781 times.
 346793 : INFINITY;
477 346793 boundary_repl = gr <= ctx->boundary_epsilon;
478 }
479
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 354653 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 354653 bool should = has_boundary ? boundary_repl : true;
480 354653 uint32_t sec_pos = 0; /* 0 = primary position = no secondary */
481
2/4
✓ Branch 0 taken 33688 times.
✓ Branch 1 taken 320965 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 354653 if (should && has_soar)
482 ✗ {
483 ✗ float norm = 0.0f;
484
2/2
✓ Branch 0 taken 1908518 times.
✓ Branch 1 taken 33688 times.
 1942206 for (Dimension d = 0; d < dim; d++)
485 1908518 norm += ctx->pt_r[d] * ctx->pt_r[d];
486
1/2
✓ Branch 0 taken 33688 times.
✗ Branch 1 not taken.
 33688 if (norm > 1e-7f)
487 {
488 33688 float inv = 1.0f / sqrtf(norm);
489
2/2
✓ Branch 0 taken 1908518 times.
✓ Branch 1 taken 33688 times.
 1942206 for (Dimension d = 0; d < dim; d++)
490 1908518 ctx->pt_r[d] *= inv;
491 }
492 /* cand_leaves = NULL -> candidate position is the index; primary is
493 * position 0. leaf_centroids = cand_pt (rotated); vec = pt_query. */
494 33688 sec_pos = prism_find_soar_secondary(
495 33688 ctx->qs->pt_query,
496 33688 ctx->cand_pt,
497 NULL,
498 n,
499 dim,
500 0,
501 33688 ctx->pt_r,
502 ctx->soar_lambda);
503 }
504
1/4
✓ Branch 0 taken 320965 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 320965 else if (should && n > 1)
505 {
506 ✗ sec_pos = 1; /* boundary-only: the 2nd-nearest candidate */
507 }
508
509
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 33688 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 33688 times.
 33688 if (sec_pos != 0 && ctx->cand_leaf[sec_pos] != primary)
510 {
511
2/2
✓ Branch 0 taken 1908518 times.
✓ Branch 1 taken 33688 times.
 1942206 for (Dimension d = 0; d < dim; d++)
512 1908518 ctx->pt_r[d] = ctx->qs->pt_query[d] -
513 1908518 ctx->cand_pt[(size_t)sec_pos * dim + d];
514 33688 prism_posting_entry_encode_from_pt(
515 ctx->rq_params,
516 33688 ctx->pt_r,
517 dim,
518 ctx->enc_buf,
519 &ctx->enc_scratch,
520 tid,
521 33688 ctx->entry);
522
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 33643 times.
 33688 if (degenerate)
523 45 mark_entry_unreachable(ctx->entry);
524 33688 prism_pbuild_sort_put(
525 33688 ctx->sorter, ctx->cand_leaf[sec_pos], ctx->entry);
526 33688 ctx->soar_dupes++;
527 33688 return true;
528 }
529 ✗ return false;
530 }
531
532 void
533 564506 prism_posting_entry_add(
534 PrismPostingBuilder *builder, const void *entry, Dimension dim)
535 {
536 564506 const char *p = (const char *)entry;
537 394144 ItemPointerData tid;
538 394144 float f_add, f_rescale, f_error;
539 564506 memcpy(&tid, p, sizeof(ItemPointerData));
540 564506 p += sizeof(ItemPointerData);
541 564506 memcpy(&f_add, p, sizeof(float));
542 564506 p += sizeof(float);
543 564506 memcpy(&f_rescale, p, sizeof(float));
544 564506 p += sizeof(float);
545 564506 memcpy(&f_error, p, sizeof(float));
546 564506 p += sizeof(float);
547 394144 (void)dim;
548 564506 prism_posting_builder_add_encoded(
549 builder, tid, f_add, f_rescale, f_error, (const uint8_t *)p);
550 564506 }
551
552 /* ----------------------------------------------------------------
553 * Shared helpers
554 * ---------------------------------------------------------------- */
555
556 /*
557 * Flush the in-memory page: write to storage and link
558 * into the chain. Prefers reserved contiguous blocks.
559 */
560 static void
561 20565 flush_page(PrismPostingBuilder *builder)
562 {
563 /*
564 * The first page of a chain (the posting-list head) must always be
565 * materialized, even with no entries: it carries the cluster's centroid
566 * metadata and pt_centroid, anchors the chain, and is where a scan begins.
567 * An empty head arises in the parallel bounded build, where the leader
568 * synthesizes the head while the workers stream the continuations (for
569 * fastscan nothing is merged into the head, so it stays empty). Later
570 * pages are still skipped when they hold no new entries.
571 */
572
3/4
✓ Branch 0 taken 10959 times.
✓ Branch 1 taken 9606 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10959 times.
 20565 if (!builder->page_dirty && !builder->is_first)
573 ✗ return;
574
575 17795 BlockNumber blkno;
576 17795 Page spage;
577
4/4
✓ Branch 0 taken 19745 times.
✓ Branch 1 taken 820 times.
✓ Branch 2 taken 18742 times.
✓ Branch 3 taken 1003 times.
 20565 if (builder->is_first && builder->fixed_first_blkno != InvalidBlockNumber)
578 {
579 18742 blkno = builder->fixed_first_blkno;
580 18742 spage = vs_storage_write_page(builder->storage, blkno);
581 }
582 else
583 {
584 1823 spage = vs_storage_new_page(builder->storage, &blkno);
585 }
586
587 20565 memcpy(spage, builder->mem_page, BLCKSZ);
588 20565 vs_storage_commit_page(builder->storage, blkno);
589
590
2/2
✓ Branch 0 taken 19745 times.
✓ Branch 1 taken 820 times.
 20565 if (builder->is_first)
591 {
592 19745 builder->head_blkno = blkno;
593 19745 builder->is_first = false;
594 }
595
596
2/2
✓ Branch 0 taken 820 times.
✓ Branch 1 taken 19745 times.
 20565 if (builder->prev_blkno != InvalidBlockNumber)
597 {
598 482 Page prev =
599 820 vs_storage_write_page(builder->storage, builder->prev_blkno);
600 820 prism_posting_opaque(prev)->next_blkno = blkno;
601 820 vs_storage_commit_page(builder->storage, builder->prev_blkno);
602 }
603 20565 builder->prev_blkno = blkno;
604
605 20565 builder->page_ops->reinit_page(builder);
606 20565 builder->page_dirty = false;
607 }
608
609 /*
610 * Common init for both formats. When pt_centroid is NULL, initializes
611 * a continuation page (no pt_centroid header, overflow flags).
612 */
613 static void
614 11962 builder_init_common(
615 PrismPostingBuilder *builder,
616 VsStorage *storage,
617 const RaBitQParams *params,
618 Dimension dim,
619 uint32_t cluster_id,
620 const float *centroid,
621 const float *pt_centroid,
622 const PrismPostingPageOps *ops,
623 uint16_t first_page_flags)
624 {
625 11962 memset(builder, 0, sizeof(*builder));
626 11962 builder->storage = storage;
627 11962 builder->params = params;
628 11962 builder->dim = dim;
629 11962 builder->cluster_id = cluster_id;
630 11962 builder->centroid = centroid;
631 11962 builder->head_blkno = InvalidBlockNumber;
632 11962 builder->prev_blkno = InvalidBlockNumber;
633 11962 builder->is_first = true;
634 11962 builder->owns_head = (first_page_flags & PRISM_POSTING_PAGE_FIRST) != 0;
635 11962 builder->n_entries = 0;
636 11962 builder->page_ops = ops;
637
638 11962 builder->fixed_first_blkno = InvalidBlockNumber;
639
640 11962 prism_posting_page_init(
641 11962 builder->mem_page, cluster_id, dim, first_page_flags);
642
1/2
✓ Branch 0 taken 11962 times.
✗ Branch 1 not taken.
 11962 if (pt_centroid != NULL)
643 11962 memcpy(prism_posting_pt_centroid_mut(builder->mem_page),
644 pt_centroid,
645 dim * sizeof(float));
646
647
2/2
✓ Branch 0 taken 11641 times.
✓ Branch 1 taken 321 times.
 11962 builder->enc_buf = params ? vs_alloc(VS_RABITQ_DATA_SIZE(dim)) : NULL;
648
2/2
✓ Branch 0 taken 11641 times.
✓ Branch 1 taken 321 times.
 11962 if (params)
649 11641 vs_rabitq_scratch_init(&builder->enc_scratch, dim);
650 11962 }
651
652 /* ----------------------------------------------------------------
653 * AoS page ops — one entry per call
654 * ---------------------------------------------------------------- */
655
656 static bool
657 239275 aos_write_entry(
658 PrismPostingBuilder *builder,
659 ItemPointerData tid,
660 float f_add,
661 float f_rescale,
662 float f_error,
663 const uint8_t *bits)
664 {
665
2/2
✓ Branch 1 taken 43614 times.
✓ Branch 2 taken 195661 times.
 239275 if (!prism_posting_page_has_room(builder->mem_page))
666 266 return false;
667
668 238794 prism_posting_page_add(
669 195446 builder->mem_page,
670 238794 builder->dim,
671 tid,
672 f_add,
673 f_rescale,
674 f_error,
675 bits,
676 0);
677 238794 return true;
678 }
679
680 static void
681 4670 aos_reinit_page(PrismPostingBuilder *builder)
682 {
683 4670 prism_posting_page_init(
684 4670 builder->mem_page,
685 builder->cluster_id,
686 4670 builder->dim,
687 PRISM_POSTING_PAGE_OVERFLOW);
688 4670 }
689
690 static void
691 4202 aos_finalize(PrismPostingBuilder *builder)
692 {
693 1880 (void)builder;
694 4202 }
695
696 static void
697 4202 aos_cleanup(PrismPostingBuilder *builder)
698 {
699 1880 (void)builder;
700 4202 }
701
702 static const PrismPostingPageOps aos_page_ops = {
703 .write_entry = aos_write_entry,
704 .reinit_page = aos_reinit_page,
705 .finalize = aos_finalize,
706 .cleanup = aos_cleanup,
707 };
708
709 /* ----------------------------------------------------------------
710 * Fastscan page ops — buffer 32 entries, pack group
711 * ---------------------------------------------------------------- */
712
713 /*
714 * Pack the current group into fastscan SoA layout and write it
715 * to the in-memory page.
716 */
717 static void
718 28572 fs_write_group(PrismPostingBuilder *builder)
719 {
720 28572 FsGroupStage *grp = &builder->fs.grp;
721
2/2
✓ Branch 0 taken 15537 times.
✓ Branch 1 taken 13035 times.
 28572 if (grp->count == 0)
722 55 return;
723
724 16510 Dimension dim = builder->dim;
725
726 16510 PrismPostingPageOpaque *op = prism_posting_opaque(builder->mem_page);
727 16510 char *content = prism_posting_page_content(builder->mem_page, dim);
728
729 16510 uint32_t g = builder->fs.groups_on_page;
730
731 17538 memcpy(prism_fastscan_group_tids(content, g, dim),
732 16510 grp->tids,
733 VS_FASTSCAN_GROUP * sizeof(ItemPointerData));
734 17538 memcpy(prism_fastscan_group_f_add(content, g, dim),
735 16510 grp->f_add,
736 VS_FASTSCAN_GROUP * sizeof(float));
737 17538 memcpy(prism_fastscan_group_f_rescale(content, g, dim),
738 16510 grp->f_rescale,
739 VS_FASTSCAN_GROUP * sizeof(float));
740 17538 memcpy(prism_fastscan_group_f_error(content, g, dim),
741 16510 grp->f_error,
742 VS_FASTSCAN_GROUP * sizeof(float));
743
744 16510 vs_fastscan_pack_codes(
745 16510 builder->fs.bits_buf, grp->count, dim, builder->fs.codes_buf);
746 17538 memcpy(prism_fastscan_group_codes(content, g, dim),
747 16510 builder->fs.codes_buf,
748 16510 VS_FASTSCAN_GROUP_BYTES(dim));
749
750 16510 op->entry_count += (uint16_t)grp->count;
751 16510 builder->fs.groups_on_page++;
752 16510 builder->page_dirty = true;
753
754 16510 memset(grp, 0, sizeof(*grp));
755 16510 memset(builder->fs.bits_buf,
756 0,
757 16510 (size_t)VS_FASTSCAN_GROUP * VS_RABITQ_BYTES(dim));
758 }
759
760 static bool
761 401133 fs_write_entry(
762 PrismPostingBuilder *builder,
763 ItemPointerData tid,
764 float f_add,
765 float f_rescale,
766 float f_error,
767 const uint8_t *bits)
768 {
769 401133 FsGroupStage *grp = &builder->fs.grp;
770 401133 uint32_t idx = grp->count;
771 401133 uint32_t packed_bytes = VS_RABITQ_BYTES(builder->dim);
772
773 401133 grp->tids[idx] = tid;
774 401133 grp->f_add[idx] = f_add;
775 401133 grp->f_rescale[idx] = f_rescale;
776 401133 grp->f_error[idx] = f_error;
777
2/2
✓ Branch 0 taken 9186 times.
✓ Branch 1 taken 360143 times.
 401133 memcpy(builder->fs.bits_buf + (size_t)idx * packed_bytes,
778 bits,
779 packed_bytes);
780 401133 grp->count++;
781
782
2/2
✓ Branch 0 taken 10147 times.
✓ Branch 1 taken 390986 times.
 401133 if (grp->count == VS_FASTSCAN_GROUP)
783 {
784
2/2
✓ Branch 0 taken 250 times.
✓ Branch 1 taken 9897 times.
 10147 if (builder->fs.groups_on_page >= builder->fs.max_groups)
785 250 flush_page(builder);
786 10147 fs_write_group(builder);
787 }
788
789 401133 return true;
790 }
791
792 static void
793 15895 fs_reinit_page(PrismPostingBuilder *builder)
794 {
795 15895 prism_posting_page_init(
796 15895 builder->mem_page,
797 builder->cluster_id,
798 15895 builder->dim,
799 PRISM_POSTING_PAGE_OVERFLOW | PRISM_POSTING_PAGE_FASTSCAN);
800 15895 builder->fs.groups_on_page = 0;
801 15895 builder->fs.max_groups = prism_fastscan_max_groups(builder->dim, false);
802 15895 }
803
804 static void
805 18425 fs_finalize(PrismPostingBuilder *builder)
806 {
807
2/2
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 18336 times.
 18425 if (builder->fs.groups_on_page >= builder->fs.max_groups)
808 89 flush_page(builder);
809 18425 fs_write_group(builder);
810 18425 }
811
812 static void
813 18425 fs_cleanup(PrismPostingBuilder *builder)
814 {
815 18425 vs_free(builder->fs.bits_buf);
816 18425 builder->fs.bits_buf = NULL;
817 18425 vs_free(builder->fs.codes_buf);
818 18425 builder->fs.codes_buf = NULL;
819 18425 }
820
821 static const PrismPostingPageOps fs_page_ops = {
822 .write_entry = fs_write_entry,
823 .reinit_page = fs_reinit_page,
824 .finalize = fs_finalize,
825 .cleanup = fs_cleanup,
826 };
827
828 /* ----------------------------------------------------------------
829 * Public API — init
830 * ---------------------------------------------------------------- */
831
832 void
833 2321 prism_posting_builder_init(
834 PrismPostingBuilder *builder,
835 VsStorage *storage,
836 const RaBitQParams *params,
837 Dimension dim,
838 uint32_t cluster_id,
839 const float *centroid,
840 const float *pt_centroid)
841 {
842 2321 builder_init_common(
843 builder,
844 storage,
845 params,
846 dim,
847 cluster_id,
848 centroid,
849 pt_centroid,
850 &aos_page_ops,
851 PRISM_POSTING_PAGE_FIRST);
852 2321 }
853
854 void
855 9641 prism_posting_builder_init_fastscan(
856 PrismPostingBuilder *builder,
857 VsStorage *storage,
858 const RaBitQParams *params,
859 Dimension dim,
860 uint32_t cluster_id,
861 const float *centroid,
862 const float *pt_centroid)
863 {
864 9641 builder_init_common(
865 builder,
866 storage,
867 params,
868 dim,
869 cluster_id,
870 centroid,
871 pt_centroid,
872 &fs_page_ops,
873 PRISM_POSTING_PAGE_FIRST | PRISM_POSTING_PAGE_FASTSCAN);
874
875 9641 uint32_t packed_bytes = VS_RABITQ_BYTES(dim);
876 9641 builder->fs.bits_buf = vs_alloc((size_t)VS_FASTSCAN_GROUP * packed_bytes);
877 9641 builder->fs.codes_buf = vs_alloc(VS_FASTSCAN_GROUP_BYTES(dim));
878 9641 builder->fs.max_groups = prism_fastscan_max_groups(dim, true);
879 9641 }
880
881 void
882 11609 prism_posting_builder_init_fmt(
883 PrismPostingBuilder *builder,
884 VsStorage *storage,
885 const RaBitQParams *params,
886 Dimension dim,
887 uint32_t cluster_id,
888 const float *centroid,
889 const float *pt_centroid,
890 bool fastscan)
891 {
892
2/2
✓ Branch 0 taken 9316 times.
✓ Branch 1 taken 2293 times.
 11609 if (fastscan)
893 9316 prism_posting_builder_init_fastscan(
894 builder,
895 storage,
896 params,
897 dim,
898 cluster_id,
899 centroid,
900 pt_centroid);
901 else
902 2293 prism_posting_builder_init(
903 builder,
904 storage,
905 params,
906 dim,
907 cluster_id,
908 centroid,
909 pt_centroid);
910 11609 }
911
912 void
913 10665 prism_posting_builder_adopt_head(
914 PrismPostingBuilder *builder,
915 VsStorage *storage,
916 const RaBitQParams *params,
917 Dimension dim,
918 uint32_t cluster_id,
919 BlockNumber head_blk,
920 bool fastscan)
921 {
922
2/2
✓ Branch 0 taken 821 times.
✓ Branch 1 taken 8730 times.
 10665 memset(builder, 0, sizeof(*builder));
923 10665 builder->storage = storage;
924 10665 builder->params = params;
925 10665 builder->dim = dim;
926 10665 builder->cluster_id = cluster_id;
927 10665 builder->centroid = NULL; /* entries arrive pre-encoded */
928 10665 builder->head_blkno = InvalidBlockNumber;
929 10665 builder->prev_blkno = InvalidBlockNumber;
930 10665 builder->is_first = true;
931 10665 builder->owns_head = true;
932
2/2
✓ Branch 0 taken 875 times.
✓ Branch 1 taken 9790 times.
 10665 builder->page_ops = fastscan ? &fs_page_ops : &aos_page_ops;
933
934 10665 builder->fixed_first_blkno = head_blk;
935 10665 builder->adopted_head = true;
936
937 /* Start from the pre-written head itself: it already carries the
938 * cluster's header and pt_centroid. It must be empty — the pre-scan
939 * writer never adds entries. */
940 10665 Page hp = vs_storage_read_page(storage, head_blk);
941
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 10665 times.
 10665 Assert(prism_posting_opaque(hp)->live_count == 0);
942 10665 memcpy(builder->mem_page, hp, BLCKSZ);
943 10665 vs_storage_release_page(storage, head_blk);
944
945 /* No encoder scratch: an adopted head only ever receives pre-encoded
946 * entries (prism_posting_entry_add from the cluster-keyed sort), and this
947 * runs once per posting list -- per-list encoder allocations would be
948 * O(nlist) churn for buffers the raw-vector add path never touches. */
949 10665 builder->enc_buf = NULL;
950
951
2/2
✓ Branch 0 taken 8784 times.
✓ Branch 1 taken 1881 times.
 10665 if (fastscan)
952 {
953 8784 uint32_t packed_bytes = VS_RABITQ_BYTES(dim);
954 8784 builder->fs.bits_buf = vs_alloc(
955 (size_t)VS_FASTSCAN_GROUP * packed_bytes);
956 8784 builder->fs.codes_buf = vs_alloc(VS_FASTSCAN_GROUP_BYTES(dim));
957 8784 builder->fs.max_groups = prism_fastscan_max_groups(dim, true);
958 }
959 10665 }
960
961 void
962 10959 prism_posting_builder_set_first_blkno(
963 PrismPostingBuilder *builder, BlockNumber blkno)
964 {
965 10959 builder->fixed_first_blkno = blkno;
966 10959 }
967
968 void
969 639927 prism_posting_builder_add_encoded(
970 PrismPostingBuilder *builder,
971 ItemPointerData tid,
972 float f_add,
973 float f_rescale,
974 float f_error,
975 const uint8_t *bits)
976 {
977
2/2
✓ Branch 0 taken 481 times.
✓ Branch 1 taken 639446 times.
 639927 if (!builder->page_ops
978 639927 ->write_entry(builder, tid, f_add, f_rescale, f_error, bits))
979 {
980 481 flush_page(builder);
981 481 builder->page_ops
982 481 ->write_entry(builder, tid, f_add, f_rescale, f_error, bits);
983 }
984 639927 builder->page_dirty = true;
985 639927 builder->n_entries++;
986 639927 }
987
988 void
989 682 prism_posting_builder_add(
990 PrismPostingBuilder *builder, ItemPointerData tid, const float *vector)
991 {
992 682 prism_posting_builder_add_ex(builder, tid, vector, false);
993 682 }
994
995 void
996 71544 prism_posting_builder_add_ex(
997 PrismPostingBuilder *builder,
998 ItemPointerData tid,
999 const float *vector,
1000 bool unreachable)
1001 {
1002 /* Adopted heads carry no encoder (their entries arrive pre-encoded). */
1003
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 71544 times.
 71544 Assert(builder->enc_buf != NULL);
1004
1005 71544 Vec32Ref vref = {.data = vector, .dim = builder->dim};
1006 71544 Vec32Ref cref = {.data = builder->centroid, .dim = builder->dim};
1007 71544 vs_rabitq_encode_into_ex(
1008 builder->params,
1009 vref,
1010 cref,
1011 builder->enc_buf,
1012 &builder->enc_scratch);
1013
1014 71544 float f_add = builder->enc_buf->f_add;
1015 86244 float f_error = vs_rabitq_derive_f_error(
1016 71544 f_add, builder->enc_buf->f_rescale, builder->dim);
1017
1018 /* Same stamp the build and insert paths apply -- see the header. */
1019
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 71464 times.
 71544 if (unreachable)
1020 {
1021 80 f_add = INFINITY;
1022 80 f_error = 0.0f;
1023 }
1024
1025 71544 prism_posting_builder_add_encoded(
1026 builder,
1027 tid,
1028 f_add,
1029 56844 builder->enc_buf->f_rescale,
1030 f_error,
1031 71544 builder->enc_buf->bits);
1032 71544 }
1033
1034 BlockNumber
1035 22627 prism_posting_builder_finish(PrismPostingBuilder *builder)
1036 {
1037 22627 builder->page_ops->finalize(builder);
1038
1039 /* An adopted head that received no entries is already final on disk
1040 * (the pre-scan writer stamped it empty): skip the rewrite and the
1041 * restamp below, which would clobber its tail_blkno with an invalid
1042 * chain tail. */
1043
6/6
✓ Branch 0 taken 10665 times.
✓ Branch 1 taken 11962 times.
✓ Branch 2 taken 10346 times.
✓ Branch 3 taken 319 times.
✓ Branch 4 taken 2882 times.
✓ Branch 5 taken 7464 times.
 22627 if (builder->adopted_head && builder->is_first && !builder->page_dirty)
1044 {
1045 2882 builder->head_blkno = builder->fixed_first_blkno;
1046 2882 return builder->head_blkno;
1047 }
1048
1049 19745 flush_page(builder);
1050
1051 /*
1052 * Stamp the head's per-cluster metadata from state the builder already
1053 * tracked, so the runtime insert path finds the chain tail in O(1) with no
1054 * walk. prev_blkno is the last page flushed (the chain tail) and n_entries
1055 * is the exact entry count; for a head builder that holds the whole
1056 * chain these values are final.
1057 */
1058
2/4
✓ Branch 0 taken 19745 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 19745 times.
✗ Branch 3 not taken.
 19745 if (builder->owns_head && builder->head_blkno != InvalidBlockNumber)
1059 {
1060 19745 Page hp = vs_storage_write_page(builder->storage, builder->head_blkno);
1061 19745 PrismPostingPageOpaque *op = prism_posting_opaque(hp);
1062 19745 op->tail_blkno = builder->prev_blkno;
1063 19745 op->live_count = builder->n_entries;
1064 19745 vs_storage_commit_page(builder->storage, builder->head_blkno);
1065 }
1066
1067 19745 return builder->head_blkno;
1068 }
1069
1070 void
1071 22627 prism_posting_builder_cleanup(PrismPostingBuilder *builder)
1072 {
1073 22627 builder->page_ops->cleanup(builder);
1074
2/2
✓ Branch 0 taken 11641 times.
✓ Branch 1 taken 10986 times.
 22627 if (builder->enc_buf != NULL)
1075 {
1076 11641 vs_rabitq_scratch_cleanup(&builder->enc_scratch);
1077 11641 vs_free(builder->enc_buf);
1078 11641 builder->enc_buf = NULL;
1079 }
1080 22627 }
1081
1082 /* ----------------------------------------------------------------
1083 * Flat builder — one buffer per cluster (unchanged)
1084 * ---------------------------------------------------------------- */
1085
1086 void
1087 150 prism_flat_posting_builder_init(
1088 PrismFlatPostingBuilder *builder,
1089 const RaBitQParams *params,
1090 Dimension dim,
1091 uint32_t cluster_id,
1092 const float *centroid,
1093 uint32_t count)
1094 {
1095 150 builder->params = params;
1096 150 builder->dim = dim;
1097 150 builder->cluster_id = cluster_id;
1098 150 builder->centroid = centroid;
1099 150 builder->max_entries = count;
1100
1101 150 size_t buf_size = prism_posting_flat_page_size(dim, count);
1102 150 builder->buf = vs_alloc(buf_size);
1103 150 memset(builder->buf, 0, buf_size);
1104 150 prism_posting_flat_init(builder->buf, count, cluster_id);
1105
1106 150 builder->enc_buf = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
1107 150 }
1108
1109 void
1110 10000 prism_flat_posting_builder_add(
1111 PrismFlatPostingBuilder *builder,
1112 ItemPointerData tid,
1113 const float *vector)
1114 {
1115 10000 Dimension dim = builder->dim;
1116
1117 10000 Vec32Ref vref = {.data = vector, .dim = dim};
1118 10000 Vec32Ref cref = {.data = builder->centroid, .dim = dim};
1119 10000 vs_rabitq_encode_into(builder->params, vref, cref, builder->enc_buf);
1120
1121 10000 float f_error = vs_rabitq_derive_f_error(
1122 10000 builder->enc_buf->f_add, builder->enc_buf->f_rescale, dim);
1123
1124 10000 prism_posting_flat_add(
1125 builder->buf,
1126 dim,
1127 tid,
1128 10000 builder->enc_buf->f_add,
1129 10000 builder->enc_buf->f_rescale,
1130 f_error,
1131 10000 builder->enc_buf->bits,
1132 0);
1133 10000 }
1134
1135 char *
1136 150 prism_flat_posting_builder_finish(PrismFlatPostingBuilder *builder)
1137 {
1138 150 return builder->buf;
1139 }
1140
1141 void
1142 150 prism_flat_posting_builder_cleanup(PrismFlatPostingBuilder *builder)
1143 {
1144
1/2
✓ Branch 0 taken 150 times.
✗ Branch 1 not taken.
 150 if (builder->enc_buf != NULL)
1145 {
1146 150 vs_free(builder->enc_buf);
1147 150 builder->enc_buf = NULL;
1148 }
1149 150 }
1150
1151 /* See posting_build.h: the route/filter/normalize half of the refine pass,
1152 * shared verbatim by the serial and parallel builds. */
1153 const float *
1154 72600 prism_refine_route_row(
1155 struct PrismQueryState *qs,
1156 BlockNumber first_posting,
1157 const float *vec,
1158 Dimension dim,
1159 bool cosine,
1160 float *scratch,
1161 uint32_t tile_lo,
1162 uint32_t tile_hi,
1163 uint32_t *out_idx)
1164 {
1165 72600 uint32_t n =
1166 72600 prism_query_route(qs, vec, 1, VS_DISTANCE_MODE_ASYMMETRIC, NULL);
1167
1/2
✓ Branch 0 taken 72600 times.
✗ Branch 1 not taken.
 72600 if (n == 0)
1168 ✗ return NULL;
1169
1170 72600 uint32_t leaf = prism_route_head_to_leaf(
1171
2/2
✓ Branch 0 taken 48600 times.
✓ Branch 1 taken 24000 times.
 72600 first_posting, qs->beam_results[0].posting_head);
1172
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)
1173 ✗ return NULL;
1174 48600 *out_idx = leaf - tile_lo;
1175
1176 /* Cosine centroids are trained in normalized space, so the mean must
1177 * average the normalized vectors. */
1178
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48600 times.
 48600 if (cosine)
1179 {
1180 ✗ memcpy(scratch, vec, (size_t)dim * sizeof(float));
1181 ✗ vs_l2_normalize(scratch, dim);
1182 ✗ return scratch;
1183 }
1184 ✗ return vec;
1185 }
1186
1187 void
1188 7 prism_refine_write_means(
1189 const double *sums,
1190 const uint64_t *counts,
1191 uint32_t lo,
1192 uint32_t hi,
1193 Dimension dim,
1194 float *scratch,
1195 PrismLeafWriteFn write_head,
1196 void *write_head_ctx)
1197 {
1198
2/2
✓ Branch 0 taken 4287 times.
✓ Branch 1 taken 7 times.
 4294 for (uint32_t l = lo; l < hi; l++)
1199 {
1200
2/2
✓ Branch 0 taken 3993 times.
✓ Branch 1 taken 294 times.
 4287 if (counts[l - lo] == 0)
1201 3993 continue; /* keep the sample-trained head for an empty leaf */
1202 294 const double *sum = sums + (size_t)(l - lo) * dim;
1203 294 double inv = 1.0 / (double)counts[l - lo];
1204
2/2
✓ Branch 0 taken 35712 times.
✓ Branch 1 taken 294 times.
 36006 for (Dimension j = 0; j < dim; j++)
1205 35712 scratch[j] = (float)(sum[j] * inv);
1206 294 write_head(write_head_ctx, l, scratch);
1207 }
1208 7 }
1209
1210 /* See posting_build.h: the one leaf-head writer both builds share. */
1211 void
1212 10959 prism_write_leaf_head(void *arg, uint32_t leaf, const float *centroid)
1213 {
1214 10959 PrismHeadWriteCtx *h = (PrismHeadWriteCtx *)arg;
1215 10959 vs_rabitq_rotate(h->rq_params, centroid, h->pt);
1216
1217 9845 PrismPostingBuilder hb;
1218 10959 prism_posting_builder_init_fmt(
1219 &hb,
1220 h->storage,
1221 h->rq_params,
1222 10959 h->dim,
1223 leaf,
1224 centroid,
1225 10959 h->pt,
1226 10959 h->fastscan);
1227 10959 prism_posting_builder_set_first_blkno(&hb, h->first_posting + leaf);
1228 10959 prism_posting_builder_finish(&hb);
1229 10959 prism_posting_builder_cleanup(&hb);
1230 10959 }
1231