GCC Code Coverage Report


Directory: src/
File: src/index/index_build.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 444 485 91.5%
Functions: 33 34 97.1%
Branches: 189 254 74.4%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * index_build.c - Shared index build utilities
6 *
7 * Generic helpers for building prism indexes, usable from both
8 * the PostgreSQL IAM build and the standalone CLI.
9 */
10
11 #include <inttypes.h>
12 #include <math.h>
13 #include <string.h>
14
15 #include "algo/kmeans.h"
16 #include "algo/vecops.h"
17 #include "core/log.h"
18 #include "core/memory.h"
19 #include "index/centroid_build.h"
20 #include "index/index_build.h"
21 #include "index/parallel_build.h" /* PrismBlobStore seam (plan/write replay) */
22 #include "index/posting_page.h"
23 #include "quant/fastscan.h"
24
25 /* ----------------------------------------------------------------
26 * Exact internal-centroid collection — see index_build.h
27 * ---------------------------------------------------------------- */
28
29 /*
30 * A collection is the collector's sealed output: the exact centroids
31 * of the internal tree nodes, keyed by where each centroid's
32 * compressed twin sits on disk (centroid page, entry index on that
33 * page). Serialized as one contiguous allocation with no internal
34 * pointers, so it can be handed across the parallel-build seam (a DSM
35 * segment under PostgreSQL, a plain heap allocation standalone) and
36 * consumed in place by any backend that maps it.
37 *
38 * +--------------------------------+
39 * | ExactCentroidCollectionHeader | base, npages, nslots, dim
40 * +--------------------------------+
41 * | uint32_t page_off[npages] | slot base per page, or NONE
42 * +--------------------------------+
43 * | float cents[nslots * dim] | centroids, densely packed
44 * +--------------------------------+
45 *
46 * The collection covers the centroid-page region [base, base +
47 * npages): a
48 * page's page_off element is indexed by its offset from the starting
49 * page (blkno - base). Pages that carry internal entries hold the
50 * index of their first centroid in cents[]; their entries then map
51 * 1:1 and in page-entry order to the following slots, so entry i of
52 * page b scores against cents + (page_off[b - base] + i) * dim. Slot
53 * ranges of different pages are disjoint, but not ordered: cents[] is
54 * appended in tree-write order (post-order serial, per-subtree
55 * parallel), not block order. Leaf-level pages — collection skips
56 * them — hold PRISM_EXACT_INTERNAL_NONE instead.
57 *
58 * An empty collection (collecting off or over budget) is just the header
59 * with npages = 0 and base = InvalidBlockNumber, which no block can
60 * match — the consumer's scoring hook stays inert. nslots and dim are
61 * self-description (sizing and debugging); the view reads only base
62 * and npages, and slot extents come from page_off plus the pages' own
63 * entry counts.
64 *
65 * Lifecycle: the LEADER produces it — it alone streams the tree to
66 * pages, collecting into PrismExactCentroidCollector as it writes —
67 * then sizes and fills the collection from the collector and publishes it
68 * before the tree-ready barrier. The WORKERS attach after that
69 * barrier and wrap it in a PrismExactInternalCentroids view to score
70 * the internal tree levels while routing rows to their posting lists
71 * (and again in the refine pass); they only ever read it. The collection's
72 * memory is deliberately not context-managed and not the collector's:
73 * under PostgreSQL it is a DSM segment (process-shared, refcounted by
74 * the resource-owner machinery — a memory context is process-private
75 * and could not cross the seam), standalone a heap allocation the
76 * leader frees after the threads join. That split also lets the
77 * leader clean up the collector right after serializing, halving the
78 * peak, while the collection lives on until the last worker detaches.
79 * The serial build skips serialization entirely: same process, so its view
80 * points straight into the collector's arrays.
81 */
82 typedef struct ExactCentroidCollectionHeader
83 {
84 BlockNumber base;
85 uint32_t npages;
86 uint32_t nslots;
87 uint32_t dim;
88 } ExactCentroidCollectionHeader;
89
90 /* Fallback initial cents[] capacity (slots) when the caller passes no
91 * expected_slots pre-size; add_node doubles from here. Covers a
92 * typical two-level tree (fan_out + 1 nodes) without regrowing while
93 * staying well under any realistic budget. */
94 #define CENTROID_COLLECTOR_INIT_CAPACITY 256
95
96 void
97 101 prism_exact_centroid_collector_init(
98 PrismExactCentroidCollector *c,
99 Dimension dim,
100 PrismCentroidFormat fmt,
101 BlockNumber base,
102 uint32_t npages,
103 uint64_t max_bytes,
104 uint64_t expected_slots)
105 {
106 101 memset(c, 0, sizeof(*c));
107 101 c->dim = dim;
108 101 c->base = base;
109 101 c->npages = npages;
110 101 c->stride = prism_centroid_max_entries_fmt(dim, fmt);
111 /* Every allocation goes to the collector's dedicated child context
112 * (see the ownership contract on PrismExactCentroidCollector). */
113 101 c->ctx = vs_memctx_create(vs_memctx_current(), "vs exact centroids");
114 101 c->page_off = vs_memctx_alloc(c->ctx, (size_t)npages * sizeof(uint32_t));
115
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 51 times.
101 memset(c->page_off, 0xFF, (size_t)npages * sizeof(uint32_t));
116 101 c->max_bytes = max_bytes;
117 /* Pre-size to the caller's estimate so growth is a rounding case,
118 * never past what the budget admits; an over-budget estimate is
119 * pointless to allocate in full -- collection will latch overflowed
120 * at the boundary anyway. */
121 50 uint64_t cap = expected_slots > 0 ? expected_slots
122
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 53 times.
101 : CENTROID_COLLECTOR_INIT_CAPACITY;
123 101 uint64_t max_cap = max_bytes / ((uint64_t)dim * sizeof(float));
124
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 48 times.
101 if (cap > max_cap)
125 2 cap = max_cap;
126
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50 times.
101 if (cap == 0)
127 ✗ cap = 1;
128 101 c->cap = (uint32_t)cap;
129 101 c->cents = vs_memctx_alloc(c->ctx, (size_t)c->cap * dim * sizeof(float));
130 101 }
131
132 /*
133 * Ensure cents[] holds at least total slots. Reached only when the
134 * init pre-size undershot (per-level rounding in the estimate): grow
135 * geometrically — a fixed-step policy would copy O(n^2) bytes over
136 * the collection's lifetime, doubling copies less than 2x the final
137 * size in total — and clamp the capacity to the budget so the
138 * allocation never overshoots what the caller's budget check admits
139 * (that check guarantees the clamped capacity still fits).
140 */
141 static void
142 281 exact_centroid_collector_reserve(
143 PrismExactCentroidCollector *c, uint32_t total)
144 {
145
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 195 times.
281 if (total <= c->cap)
146 76 return;
147
148 20 uint64_t max_cap = c->max_bytes / ((uint64_t)c->dim * sizeof(float));
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
20 Assert(total <= max_cap);
150 20 uint64_t new_cap = (uint64_t)c->cap * 2;
151
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 20 times.
24 while (new_cap < total)
152 4 new_cap *= 2;
153
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
20 if (new_cap > max_cap)
154 ✗ new_cap = max_cap;
155
156 /* Grow inside the collector's own context, not the streaming
157 * scratch context this is called under (that scratch dies at
158 * the end of the write pass, while the collector must survive
159 * until after the encode scan and the refine pass). The old
160 * array is freed eagerly (a no-op on the standalone arena) so
161 * both generations are never held at once. */
162 10 float *grown =
163 20 vs_memctx_alloc(c->ctx, (size_t)new_cap * c->dim * sizeof(float));
164 20 memcpy(grown, c->cents, (size_t)c->nslots * c->dim * sizeof(float));
165 20 vs_free(c->cents);
166 20 c->cents = grown;
167 20 c->cap = (uint32_t)new_cap;
168 }
169
170 void
171 294 prism_exact_centroid_collector_add_node(
172 PrismExactCentroidCollector *c,
173 BlockNumber first_blk,
174 const float *cents,
175 uint32_t n)
176 {
177
3/4
✓ Branch 0 taken 294 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 198 times.
✓ Branch 3 taken 96 times.
294 if (n == 0 || c->overflowed)
178 2 return;
179
180 /* Enforce the collection budget: degrade to an empty (inert)
181 * collection rather than grow without bound. The arrays are dead
182 * once the flag latches (every consumer checks it first), so
183 * release them right away — the encode scan that follows is the
184 * build's memory peak. */
185 284 uint64_t need = ((uint64_t)c->nslots + n) * c->dim * sizeof(float);
186
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 281 times.
284 if (need > c->max_bytes)
187 {
188
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
3 vs_warn("exact centroid collection over budget (needs more "
189 "than %" PRIu64 " of %" PRIu64 " bytes); build descent "
190 "falls back to estimated internal scoring — consider "
191 "raising the build memory budget",
192 need,
193 c->max_bytes);
194 3 c->overflowed = true;
195 3 prism_exact_centroid_collector_cleanup(c);
196 3 return;
197 }
198
199 281 exact_centroid_collector_reserve(c, c->nslots + n);
200
201 /* The node's entries pack stride per page from first_blk — the same
202 * packing every centroid writer uses (each node starts on a fresh
203 * reserved page). Record each page's slot base and append its
204 * centroids in page-entry order. */
205 281 uint32_t npages_node = (n + c->stride - 1) / c->stride;
206
2/2
✓ Branch 0 taken 281 times.
✓ Branch 1 taken 281 times.
562 for (uint32_t p = 0; p < npages_node; p++)
207 {
208 281 BlockNumber blk = first_blk + p;
209
2/4
✓ Branch 0 taken 281 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 281 times.
281 if (blk < c->base || blk - c->base >= c->npages)
210 {
211 /* Plan/write divergence: a node landed outside the planned
212 * centroid region. Degrade to inert rather than write
213 * page_off out of bounds in release builds. */
214 ✗ Assert(false);
215 c->overflowed = true;
216 prism_exact_centroid_collector_cleanup(c);
217 return;
218 }
219
220 281 uint32_t count = n - p * c->stride;
221
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 86 times.
281 if (count > c->stride)
222 ✗ count = c->stride;
223
224 281 c->page_off[blk - c->base] = c->nslots;
225 281 memcpy(c->cents + (size_t)c->nslots * c->dim,
226 281 cents + (size_t)p * c->stride * c->dim,
227 281 (size_t)count * c->dim * sizeof(float));
228 281 c->nslots += count;
229 }
230 }
231
232 void
233 108 prism_exact_centroid_collector_cleanup(PrismExactCentroidCollector *c)
234 {
235 /* Everything the collector allocated lives in its dedicated
236 * context: one delete releases it all, exactly once (idempotent —
237 * a second call is a no-op). Callers must not run this until the
238 * last view consumer is done. */
239
2/2
✓ Branch 0 taken 101 times.
✓ Branch 1 taken 7 times.
108 if (c->ctx != NULL)
240 101 vs_memctx_delete(c->ctx);
241 108 c->ctx = NULL;
242 108 c->page_off = NULL;
243 108 c->cents = NULL;
244 108 }
245
246 void
247 38 prism_exact_centroid_view(
248 const PrismExactCentroidCollector *c,
249 PrismExactInternalCentroids *view)
250 {
251
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 35 times.
38 if (c->overflowed)
252 {
253 /* Inert view: a zero-page region matches no block. */
254 3 view->cents = NULL;
255 3 view->page_off = NULL;
256 3 view->base = InvalidBlockNumber;
257 3 view->npages = 0;
258 3 return;
259 }
260 35 view->cents = c->cents;
261 35 view->page_off = c->page_off;
262 35 view->base = c->base;
263 35 view->npages = c->npages;
264 }
265
266 uint64_t
267 159 prism_exact_centroid_collection_size(const PrismExactCentroidCollector *c)
268 {
269
4/4
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 90 times.
✓ Branch 2 taken 21 times.
✓ Branch 3 taken 48 times.
159 if (c == NULL || c->overflowed)
270 66 return sizeof(ExactCentroidCollectionHeader);
271 19 return sizeof(ExactCentroidCollectionHeader) +
272 67 (uint64_t)c->npages * sizeof(uint32_t) +
273 67 (uint64_t)c->nslots * c->dim * sizeof(float);
274 }
275
276 void
277 159 prism_exact_centroid_collection_write(
278 const PrismExactCentroidCollector *c, void *collection)
279 {
280 159 ExactCentroidCollectionHeader *hdr = (ExactCentroidCollectionHeader *)
281 collection;
282
283
4/4
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 90 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 67 times.
159 if (c == NULL || c->overflowed)
284 {
285 /* Empty collection: a zero-page region matches no block, so the view
286 * built from it leaves the scoring hook inert. */
287 92 hdr->base = InvalidBlockNumber;
288 92 hdr->npages = 0;
289 92 hdr->nslots = 0;
290 92 hdr->dim = 0;
291 92 return;
292 }
293
294 67 hdr->base = c->base;
295 67 hdr->npages = c->npages;
296 67 hdr->nslots = c->nslots;
297 67 hdr->dim = c->dim;
298
299 67 char *p = (char *)collection + sizeof(*hdr);
300 67 memcpy(p, c->page_off, (size_t)c->npages * sizeof(uint32_t));
301 67 p += (size_t)c->npages * sizeof(uint32_t);
302 67 memcpy(p, c->cents, (size_t)c->nslots * c->dim * sizeof(float));
303 }
304
305 void
306 238 prism_exact_centroid_collection_view(
307 const void *collection, PrismExactInternalCentroids *view)
308 {
309 238 const ExactCentroidCollectionHeader *hdr =
310 (const ExactCentroidCollectionHeader *)collection;
311 238 const char *p = (const char *)collection + sizeof(*hdr);
312
313 238 view->page_off = (const uint32_t *)p;
314 238 view->cents = (const float *)(p + (size_t)hdr->npages * sizeof(uint32_t));
315 238 view->base = hdr->base;
316 238 view->npages = hdr->npages;
317 238 }
318
319 /* Assign each node of a materialized tree its first block, packing nodes
320 * in index order from first_blkno; returns the block after the last. */
321 BlockNumber
322 828 prism_compute_centroid_layout(
323 const HKMeansResult *tree,
324 uint32_t max_entries,
325 BlockNumber first_blkno,
326 BlockNumber *node_first_blkno)
327 {
328 828 BlockNumber next = first_blkno;
329
330
2/2
✓ Branch 0 taken 1240 times.
✓ Branch 1 taken 828 times.
2068 for (uint32_t i = 0; i < tree->nnodes; i++)
331 {
332
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 428 times.
1240 uint32_t n = hk_nodes(tree)[i].nchildren;
333 1240 uint32_t npages = (n + max_entries - 1) / max_entries;
334
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1240 times.
1240 if (npages == 0)
335 ✗ npages = 1;
336 1240 node_first_blkno[i] = next;
337 1240 next += npages;
338 }
339
340 828 return next;
341 }
342
343 /* Write a fully materialized (in-RAM) HKMeansResult tree to centroid
344 * pages. The streamed builders below replace this for the paged builds;
345 * the standalone in-RAM build still writes through it. */
346 void
347 423 prism_write_centroid_tree(
348 VsStorage *storage,
349 const HKMeansResult *tree,
350 Dimension dim,
351 uint32_t fan_out,
352 uint8_t level_offset,
353 PrismCentroidFormat centroid_format,
354 const RaBitQParams *rq_params,
355 const float *global_mean,
356 BlockNumber posting_base,
357 uint32_t head_stride,
358 const BlockNumber *node_first_blkno,
359 const float *pt_centroids,
360 PrismExactCentroidCollector *collector)
361 {
362 /* Leaf child blocks are formula-derived (posting_base + global leaf
363 * index * head_stride), so no O(nlist) posting-head array is needed. Each
364 * node has at most fan_out leaf entries, so this scratch is O(fan_out). */
365 137 BlockNumber *leaf_blks =
366 (posting_base != InvalidBlockNumber)
367 423 ? vs_alloc((size_t)fan_out * sizeof(BlockNumber))
368
1/2
✓ Branch 0 taken 423 times.
✗ Branch 1 not taken.
423 : NULL;
369
370
2/2
✓ Branch 0 taken 660 times.
✓ Branch 1 taken 423 times.
1083 for (uint32_t i = 0; i < tree->nnodes; i++)
371 {
372
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 194 times.
660 const HKMeansNode *node = &hk_nodes(tree)[i];
373 660 bool is_leaf = (node->level == tree->nlevels - 1);
374
375 660 uint16_t flags = is_leaf ? PRISM_CENTROID_FLAG_LEAF : 0;
376
2/2
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 244 times.
660 uint16_t child_count = is_leaf ? 0 : (uint16_t)fan_out;
377
378 214 const BlockNumber *child_blks;
379
3/4
✓ Branch 0 taken 590 times.
✓ Branch 1 taken 70 times.
✓ Branch 2 taken 396 times.
✗ Branch 3 not taken.
660 if (is_leaf && leaf_blks != NULL)
380 {
381
2/2
✓ Branch 0 taken 2966 times.
✓ Branch 1 taken 590 times.
3556 for (uint32_t j = 0; j < node->nchildren; j++)
382 2966 leaf_blks[j] = prism_leaf_head_blkno(
383 2966 posting_base, node->first_leaf + j, head_stride);
384 396 child_blks = leaf_blks;
385 }
386
1/2
✓ Branch 0 taken 70 times.
✗ Branch 1 not taken.
70 else if (!is_leaf)
387 70 child_blks = &node_first_blkno[node->first_child];
388 else
389 ✗ child_blks = NULL;
390
391 /* Pass pt_centroids for leaf nodes only */
392
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 396 times.
660 const float *leaf_pt = (is_leaf && pt_centroids != NULL)
393 ✗ ? pt_centroids +
394 ✗ (size_t)node->first_leaf * dim
395
2/2
✓ Branch 0 taken 396 times.
✓ Branch 1 taken 264 times.
660 : NULL;
396
397 660 prism_centroid_write_node(
398 storage,
399 dim,
400 660 hk_node_centroids(tree, node),
401 660 node->nchildren,
402 centroid_format,
403 660 (uint8_t)(level_offset + node->level),
404 flags,
405 child_count,
406 rq_params,
407 global_mean,
408 child_blks,
409 leaf_pt,
410 660 node_first_blkno[i],
411 collector);
412 }
413
414
1/2
✓ Branch 0 taken 423 times.
✗ Branch 1 not taken.
423 if (leaf_blks != NULL)
415 423 vs_free(leaf_blks);
416 423 }
417
418 /* ----------------------------------------------------------------
419 * Streaming (page-backed) centroid-tree build
420 * ---------------------------------------------------------------- */
421
422 typedef struct RoutingTreeCtx
423 {
424 /* inputs */
425 const float *vectors;
426 Dimension dim;
427 uint32_t nlist;
428 uint32_t fan_out;
429 uint32_t nlevels;
430 DistanceMetric metric;
431 KMeansOptions opts;
432 /* write-phase */
433 VsStorage *storage;
434 PrismCentroidFormat format;
435 const RaBitQParams *rq_params;
436 const float *global_mean;
437 BlockNumber first_posting; /* leaf c's head = first_posting + c *
438 * head_stride */
439 uint32_t head_stride; /* prism_posting_reference_pages(dim) */
440 PrismStreamLeafCb on_leaf;
441 void *on_leaf_arg;
442 /* write-phase: optional exact internal-centroid collection */
443 PrismExactCentroidCollector *collector;
444 /* plan-phase page-count helpers */
445 uint32_t max_ent; /* non-fastscan entries/page */
446 uint32_t fs_gpp; /* fastscan groups/page */
447 /* Node replay: the plan pass records each node's clustering
448 * ({k, centroids, assignments}, recursion order) here, and the write
449 * pass replays it instead of re-running k-means. Both passes require
450 * the store. */
451 PrismBlobStore *store;
452 float *replay_cents; /* write: [fan_out * dim] */
453 /* One node's uint16 assignments, shared by both passes (the plan pass
454 * narrows into it before recording, the replay pass reads records back
455 * into it). Sized once for the root -- the first and largest node --
456 * so it is never grown. */
457 uint16_t *assign_scratch; /* [nvecs] */
458 BlockNumber *leaf_blk_scratch; /* write: [fan_out] leaf head blocks */
459 /* accumulators */
460 uint32_t nleaves; /* running (== next first_leaf) */
461 double *leaf_sum; /* plan only, [dim]: leaf-centroid sum for the
462 * leaf_mean the caller uses as global_mean */
463 uint32_t centroid_pages; /* plan only */
464 BlockNumber next_blk; /* write only: next reserved centroid block */
465 bool ok;
466 } RoutingTreeCtx;
467
468 /*
469 * Write one tree node's centroid page(s) in the node's format: the fastscan
470 * writer carries its own encoder; every other format goes through the
471 * generic encoder + page writer. Shared by the streaming DFS and the
472 * parallel leader's root-page write.
473 */
474 void
475 2298 prism_centroid_write_node(
476 VsStorage *storage,
477 Dimension dim,
478 const float *cents,
479 uint32_t n,
480 PrismCentroidFormat fmt,
481 uint8_t level,
482 uint16_t flags,
483 uint16_t child_count,
484 const RaBitQParams *rq_params,
485 const float *global_mean,
486 const BlockNumber *child_blks,
487 const float *leaf_pt,
488 BlockNumber blkno,
489 PrismExactCentroidCollector *collector)
490 {
491 /* Every internal node of every build shape passes through here; the
492 * leaf level (LEAF flag) is exact-re-ranked per row instead. */
493
4/4
✓ Branch 0 taken 1652 times.
✓ Branch 1 taken 646 times.
✓ Branch 2 taken 288 times.
✓ Branch 3 taken 1364 times.
2298 if (collector != NULL && (flags & PRISM_CENTROID_FLAG_LEAF) == 0)
494 288 prism_exact_centroid_collector_add_node(collector, blkno, cents, n);
495
496
2/2
✓ Branch 0 taken 1412 times.
✓ Branch 1 taken 886 times.
2298 if (fmt == PRISM_CENTROID_FMT_FASTSCAN)
497 /* fastscan carries its own encoder; pt_centroids live on posting
498 * pages, never inline. */
499 1412 prism_centroid_write_fastscan_pages(
500 storage,
501 dim,
502 n,
503 level,
504 flags,
505 rq_params,
506 cents,
507 global_mean,
508 child_blks,
509 blkno);
510 else
511 {
512 202 CentroidEncoderState est;
513 886 CentroidEncoder *enc = centroid_encoder_init(
514 &est, fmt, cents, dim, rq_params, global_mean);
515 886 prism_centroid_write_pages(
516 storage,
517 dim,
518 n,
519 fmt,
520 level,
521 flags,
522 child_count,
523 enc,
524 child_blks,
525 leaf_pt,
526 blkno);
527 }
528 2298 }
529
530 /* Pages one node of `n` entries occupies — must match the writers' packing. */
531 static uint32_t
532 3138 node_npages(const RoutingTreeCtx *c, uint32_t n)
533 {
534
2/2
✓ Branch 0 taken 2312 times.
✓ Branch 1 taken 826 times.
3138 if (c->format == PRISM_CENTROID_FMT_FASTSCAN)
535 {
536 2312 uint32_t ngroups = (n + VS_FASTSCAN_GROUP - 1) / VS_FASTSCAN_GROUP;
537
1/2
✓ Branch 0 taken 164 times.
✗ Branch 1 not taken.
2312 uint32_t gpp = c->fs_gpp ? c->fs_gpp : 1;
538 2312 return (ngroups + gpp - 1) / gpp;
539 }
540
1/2
✓ Branch 0 taken 428 times.
✗ Branch 1 not taken.
826 uint32_t me = c->max_ent ? c->max_ent : 1;
541 826 return (n + me - 1) / me;
542 }
543
544 /*
545 * Write one node's centroid page(s) at the next reserved block (post-order, so
546 * blocks are assigned in write order); returns the node's first block. The
547 * relation is pre-extended by the caller to cover the centroid + posting area,
548 * so writes use reserved blocks rather than appending (posting heads, which
549 * live in the far posting area, are written during this pass too).
550 */
551 static BlockNumber
552 1569 write_node_pages(
553 RoutingTreeCtx *c,
554 const float *cents,
555 uint32_t n,
556 uint32_t level,
557 bool is_leaf,
558 const BlockNumber *child_blks)
559 {
560 1569 uint16_t flags = is_leaf ? PRISM_CENTROID_FLAG_LEAF : 0;
561 1569 BlockNumber start = c->next_blk;
562
563 2778 prism_centroid_write_node(
564 c->storage,
565 1569 c->dim,
566 cents,
567 n,
568 1569 c->format,
569 296 (uint8_t)level,
570 flags,
571 237 is_leaf ? 0 : (uint16_t)c->fan_out,
572
2/2
✓ Branch 0 taken 405 times.
✓ Branch 1 taken 1164 times.
1569 c->rq_params,
573 c->global_mean,
574 child_blks,
575 NULL,
576 start,
577 c->collector);
578
579 1569 c->next_blk += node_npages(c, n);
580 1569 return start;
581 }
582
583 /*
584 * DFS one node. slice[count] are indices into c->vectors (NULL == identity for
585 * the root). Returns the node's first block (write phase) or
586 * InvalidBlockNumber (plan phase). Post-order: children are written before the
587 * parent so the parent's entries can carry their child block numbers.
588 */
589 /* Read exactly nbytes of a node record from the replay store. */
590 static bool
591 4707 replay_read(struct PrismBlobStore *store, void *dst, uint64_t nbytes)
592 {
593 4707 return prism_pbuild_blobstore_get(store, dst, nbytes) == nbytes;
594 }
595
596 /*
597 * Replay one node's clustering record from the blob store into the ctx's
598 * replay scratch. The plan pass wrote, per node in recursion order: the
599 * cluster count k (uint32), the centroids (k * dim floats) and the
600 * per-vector assignments (count uint16s); this reads the same three fields
601 * in the same order. Returns false on a short read or an out-of-range k,
602 * which can only mean the plan and write passes diverged.
603 */
604 static bool
605 1569 replay_node_record(RoutingTreeCtx *c, uint32_t count, uint32_t *out_k)
606 {
607 1569 uint32_t k = 0;
608
609
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1569 times.
1569 if (!replay_read(c->store, &k, sizeof(k)))
610 ✗ return false;
611
3/4
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 1273 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1569 times.
1569 if (k == 0 || k > c->fan_out)
612 ✗ return false;
613
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
1569 if (!replay_read(
614 1569 c->store,
615 1569 c->replay_cents,
616 1569 (uint64_t)k * c->dim * sizeof(float)))
617 ✗ return false;
618
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
1569 if (!replay_read(
619 1569 c->store,
620 1569 c->assign_scratch,
621 1569 (uint64_t)count * sizeof(uint16_t)))
622 ✗ return false;
623
624 1569 *out_k = k;
625 1569 return true;
626 }
627
628 /*
629 * Record one node's clustering into the blob store, in the exact field
630 * order replay_node_record reads back: k, centroids[k * dim],
631 * assignments[count]. Assignments are narrowed to uint16 -- a node
632 * clusters into at most fan_out (<= the meta page's 8-bit fan_out) groups.
633 */
634 static void
635 1569 record_node_clustering(
636 RoutingTreeCtx *c, const KMeansResult *km, uint32_t count)
637 {
638 1569 const size_t assign_nbytes = (size_t)count * sizeof(uint16_t);
639 1569 uint16_t *a16 = c->assign_scratch;
640
641
2/2
✓ Branch 0 taken 538753 times.
✓ Branch 1 taken 1569 times.
540322 for (uint32_t v = 0; v < count; v++)
642 538753 a16[v] = (uint16_t)km->assignments[v];
643
644 1569 prism_pbuild_blobstore_put(c->store, &km->nlist, sizeof(km->nlist));
645 1569 prism_pbuild_blobstore_put(
646 c->store,
647 1569 km->centroids,
648 1569 (uint64_t)km->nlist * c->dim * sizeof(float));
649 1569 prism_pbuild_blobstore_put(c->store, a16, assign_nbytes);
650 1569 }
651
652 /* Compact the non-empty clusters' centroids to the front, preserving
653 * ascending cluster order (descent indexes the kept centroids densely). */
654 static uint32_t
655 1332 compact_nonempty_centroids(
656 float *cents,
657 const uint32_t *counts,
658 uint32_t nclusters,
659 Dimension dim)
660 {
661 1332 uint32_t kept = 0;
662
2/2
✓ Branch 0 taken 11286 times.
✓ Branch 1 taken 1332 times.
12618 for (uint32_t cl = 0; cl < nclusters; cl++)
663 {
664
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 11196 times.
11286 if (counts[cl] == 0)
665 90 continue;
666
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 11171 times.
11196 if (kept != cl)
667 25 memcpy(cents + (size_t)kept * dim,
668 25 cents + (size_t)cl * dim,
669 25 (size_t)dim * sizeof(float));
670 11196 kept++;
671 }
672 1332 return kept;
673 }
674
675 static void plan_node_recurse(
676 RoutingTreeCtx *c,
677 const uint32_t *slice,
678 uint32_t count,
679 uint32_t level);
680 static BlockNumber
681 replay_node_recurse(RoutingTreeCtx *c, uint32_t count, uint32_t level);
682
683 /* Leaf parent, plan side: the non-empty clusters become leaves. Nothing is
684 * written; count the leaf pages, tally the leaves, and fold the kept
685 * centroids into the leaf sum (the global mean's numerator). */
686 static void
687 1332 plan_leaf_parent(
688 RoutingTreeCtx *c, const KMeansResult *km, const uint32_t *counts)
689 {
690 1332 uint32_t kept = 0;
691
2/2
✓ Branch 0 taken 11286 times.
✓ Branch 1 taken 1332 times.
12618 for (uint32_t cl = 0; cl < km->nlist; cl++)
692 {
693
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 11196 times.
11286 if (counts[cl] == 0)
694 90 continue;
695
1/2
✓ Branch 0 taken 11196 times.
✗ Branch 1 not taken.
11196 if (c->leaf_sum != NULL)
696 {
697 11196 const float *lc = km->centroids + (size_t)cl * c->dim;
698
2/2
✓ Branch 0 taken 1363305 times.
✓ Branch 1 taken 11196 times.
1374501 for (Dimension d = 0; d < c->dim; d++)
699 1363305 c->leaf_sum[d] += lc[d];
700 }
701 11196 kept++;
702 }
703 1332 c->centroid_pages += node_npages(c, kept);
704 1332 c->nleaves += kept;
705 1332 }
706
707 /* Internal node, plan side: gather each non-empty child's slice of the
708 * sample and recurse, in ascending cluster order -- the recursion order
709 * that frames the tape -- then count this node's page(s). */
710 static void
711 237 plan_internal_node(
712 RoutingTreeCtx *c,
713 const KMeansResult *km,
714 const uint32_t *counts,
715 const uint32_t *slice,
716 uint32_t count,
717 uint32_t level)
718 {
719 237 uint32_t kept = 0;
720
3/4
✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 237 times.
✓ Branch 2 taken 1344 times.
✗ Branch 3 not taken.
1581 for (uint32_t cl = 0; cl < km->nlist && c->ok; cl++)
721 {
722
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1341 times.
1344 if (counts[cl] == 0)
723 3 continue;
724
725 1341 uint32_t sub_n = counts[cl];
726 1341 uint32_t *sub = vs_alloc((size_t)sub_n * sizeof(uint32_t));
727 1341 uint32_t idx = 0;
728
3/3
✓ Branch 0 taken 76800 times.
✓ Branch 1 taken 2313510 times.
✓ Branch 2 taken 1069 times.
2391379 for (uint32_t v = 0; v < count; v++)
729
2/2
✓ Branch 0 taken 268173 times.
✓ Branch 1 taken 2121865 times.
2390038 if (km->assignments[v] == cl)
730
2/2
✓ Branch 0 taken 59723 times.
✓ Branch 1 taken 208450 times.
268173 sub[idx++] = slice ? slice[v] : v;
731 1341 plan_node_recurse(c, sub, sub_n, level + 1);
732 1341 vs_free(sub);
733 1341 kept++;
734 }
735 237 c->centroid_pages += node_npages(c, kept);
736 237 }
737
738 /*
739 * Plan pass -- writes the tape. Recursive DFS from the given node down
740 * (the mutual recursion runs through plan_internal_node): cluster the
741 * node's slice of the sample (slice[count] indexes c->vectors; NULL =
742 * identity at the root), record the clustering for the replay pass,
743 * descend into the non-empty children, and accumulate the layout totals
744 * (centroid pages, leaves, the leaf-centroid sum) that must be known
745 * before any page can be written.
746 */
747 static void
748 1569 plan_node_recurse(
749 RoutingTreeCtx *c,
750 const uint32_t *slice,
751 uint32_t count,
752 uint32_t level)
753 {
754
2/2
✓ Branch 0 taken 1273 times.
✓ Branch 1 taken 296 times.
1569 if (!c->ok)
755 ✗ return;
756
757
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 1393 times.
1569 uint32_t k = (c->nlevels == 1) ? c->nlist : c->fan_out;
758
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 296 times.
1569 if (k > count)
759 ✗ k = count;
760
761 2842 KMeansResult *km = vs_kmeans(
762 1569 c->vectors,
763 slice,
764 VS_VEC_F32,
765 count,
766 1569 c->dim,
767 k,
768 c->metric,
769 1569 &c->opts);
770
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
1569 if (km == NULL)
771 {
772 ✗ c->ok = false;
773 ✗ return;
774 }
775 1569 c->opts.initial_centroids = NULL; /* root only (matches vs_hkmeans_f32) */
776
777
1/2
✓ Branch 0 taken 1569 times.
✗ Branch 1 not taken.
1569 if (c->store != NULL)
778 1569 record_node_clustering(c, km, count);
779
780 /* Count assignments per cluster (km->cluster_sizes may be stale). */
781 1569 uint32_t *counts = vs_alloc0((size_t)km->nlist * sizeof(uint32_t));
782
3/3
✓ Branch 0 taken 31200 times.
✓ Branch 1 taken 507849 times.
✓ Branch 2 taken 1273 times.
540322 for (uint32_t v = 0; v < count; v++)
783 538753 counts[km->assignments[v]]++;
784
785
2/2
✓ Branch 0 taken 1332 times.
✓ Branch 1 taken 237 times.
1569 if (level == c->nlevels - 1)
786 1332 plan_leaf_parent(c, km, counts);
787 else
788 237 plan_internal_node(c, km, counts, slice, count, level);
789
790 1569 vs_free(counts);
791 1569 vs_kmeans_result_destroy(km);
792 }
793
794 /* Leaf parent, replay side: compact the non-empty clusters into leaves,
795 * write the node's page(s) with the formula-derived leaf head blocks, and
796 * emit each leaf's head page from its resident float centroid. */
797 static BlockNumber
798 1332 replay_leaf_parent(
799 RoutingTreeCtx *c,
800 uint32_t nclusters,
801 const uint32_t *counts,
802 uint32_t level)
803 {
804 1332 float *cents = c->replay_cents;
805 1100 uint32_t kept =
806 1332 compact_nonempty_centroids(cents, counts, nclusters, c->dim);
807
808 /* Cosine routes and encodes against unit-norm references; k-means
809 * means drift below unit norm, so normalize the leaf centroids in
810 * place before the leaf codes and head references are written from
811 * them (the flat-tree path already does). */
812
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 1305 times.
1332 if (c->metric == DISTANCE_COSINE)
813
2/2
✓ Branch 0 taken 246 times.
✓ Branch 1 taken 27 times.
273 for (uint32_t kk = 0; kk < kept; kk++)
814 246 vs_l2_normalize(cents + (size_t)kk * c->dim, c->dim);
815
816 /* Leaf heads are formula-derived (first_posting + global leaf index);
817 * kept <= fan_out, so the pass-lifetime scratch covers every node. */
818 1332 BlockNumber *leaf_blks = NULL;
819
1/2
✓ Branch 0 taken 1332 times.
✗ Branch 1 not taken.
1332 if (c->first_posting != InvalidBlockNumber)
820 {
821 1332 leaf_blks = c->leaf_blk_scratch;
822
2/2
✓ Branch 0 taken 11196 times.
✓ Branch 1 taken 1332 times.
12528 for (uint32_t kk = 0; kk < kept; kk++)
823 11196 leaf_blks[kk] = prism_leaf_head_blkno(
824 11196 c->first_posting, c->nleaves + kk, c->head_stride);
825 }
826 1332 BlockNumber blk = write_node_pages(c, cents, kept, level, true, leaf_blks);
827
828
1/2
✓ Branch 0 taken 1332 times.
✗ Branch 1 not taken.
1332 if (c->on_leaf != NULL)
829
2/2
✓ Branch 0 taken 11196 times.
✓ Branch 1 taken 1332 times.
12528 for (uint32_t kk = 0; kk < kept; kk++)
830 11196 c->on_leaf(
831 c->on_leaf_arg,
832 11196 c->nleaves + kk,
833 11196 cents + (size_t)kk * c->dim);
834 1332 c->nleaves += kept;
835 1332 return blk;
836 }
837
838 /* Internal node, replay side: recurse into each non-empty child in
839 * ascending cluster order -- the same order the plan pass recursed, which
840 * is what keeps the tape in frame -- then write this node's page(s) above
841 * the children. The children's records overwrite the shared replay
842 * scratch, so this node's centroids are snapshotted first. */
843 static BlockNumber
844 237 replay_internal_node(
845 RoutingTreeCtx *c,
846 uint32_t nclusters,
847 const uint32_t *counts,
848 uint32_t level)
849 {
850 237 const size_t vec_nbytes = (size_t)c->dim * sizeof(float);
851 237 const size_t cents_nbytes = (size_t)nclusters * vec_nbytes;
852
853 237 float *my_cents = vs_alloc(cents_nbytes);
854 237 memcpy(my_cents, c->replay_cents, cents_nbytes);
855
856 237 BlockNumber *child_blocks = vs_alloc(
857 64 (size_t)nclusters * sizeof(BlockNumber));
858 237 uint32_t kept = 0;
859
4/5
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 1136 times.
✓ Branch 2 taken 445 times.
✓ Branch 3 taken 1072 times.
✗ Branch 4 not taken.
1581 for (uint32_t cl = 0; cl < nclusters && c->ok; cl++)
860 {
861
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1341 times.
1344 if (counts[cl] == 0)
862 3 continue;
863
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1341 times.
1341 if (kept != cl)
864 ✗ memcpy(my_cents + (size_t)kept * c->dim,
865 ✗ my_cents + (size_t)cl * c->dim,
866 vec_nbytes);
867 1341 child_blocks[kept] = replay_node_recurse(c, counts[cl], level + 1);
868 1341 kept++;
869 }
870
871 237 BlockNumber blk = InvalidBlockNumber;
872
1/2
✓ Branch 0 taken 237 times.
✗ Branch 1 not taken.
237 if (c->ok)
873 237 blk = write_node_pages(c, my_cents, kept, level, false, child_blocks);
874 237 vs_free(child_blocks);
875 237 vs_free(my_cents);
876 237 return blk;
877 }
878
879 /*
880 * Replay pass -- reads the tape. Recursive DFS from the given node down
881 * (the mutual recursion runs through replay_internal_node): consume the
882 * record the plan pass wrote for this node and write its page(s). The
883 * record carries the centroids and the assignments, and each child's size
884 * falls out of the assignment counts, so unlike the plan walker this one
885 * needs no sample vectors and descends on counts alone. Post-order:
886 * children are written before the parent so the parent's entries can carry
887 * their block numbers. Returns the node's first block.
888 */
889 static BlockNumber
890 1569 replay_node_recurse(RoutingTreeCtx *c, uint32_t count, uint32_t level)
891 {
892
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
1569 if (!c->ok)
893 ✗ return InvalidBlockNumber;
894
895 1569 uint32_t nclusters = 0;
896
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1569 times.
1569 if (!replay_node_record(c, count, &nclusters))
897 {
898 ✗ c->ok = false;
899 ✗ return InvalidBlockNumber;
900 }
901
902 /* Count assignments per cluster. */
903 1569 uint32_t *counts = vs_alloc0((size_t)nclusters * sizeof(uint32_t));
904
3/3
✓ Branch 0 taken 31200 times.
✓ Branch 1 taken 507849 times.
✓ Branch 2 taken 1273 times.
540322 for (uint32_t v = 0; v < count; v++)
905 538753 counts[c->assign_scratch[v]]++;
906
907 1273 BlockNumber blk;
908
2/2
✓ Branch 0 taken 1332 times.
✓ Branch 1 taken 237 times.
1569 if (level == c->nlevels - 1)
909 1332 blk = replay_leaf_parent(c, nclusters, counts, level);
910 else
911 237 blk = replay_internal_node(c, nclusters, counts, level);
912
913 1569 vs_free(counts);
914 1569 return blk;
915 }
916
917 /* Shared walker state: tree geometry and page capacities. The plan entry
918 * adds the sample/metric/k-means knobs; the replay entry adds the storage,
919 * tape and replay scratch. */
920 static void
921 456 routing_tree_ctx_init(
922 RoutingTreeCtx *c,
923 Dimension dim,
924 uint32_t nlist,
925 uint32_t fan_out,
926 PrismCentroidFormat format)
927 {
928 456 memset(c, 0, sizeof(*c));
929 456 c->dim = dim;
930 456 c->head_stride = prism_posting_reference_pages(dim);
931 456 c->nlist = nlist;
932 456 c->fan_out = fan_out < 2 ? 2 : fan_out;
933 456 c->nlevels = vs_hkmeans_nlevels(nlist, c->fan_out);
934 456 c->format = format;
935 456 c->max_ent = prism_centroid_max_entries_fmt(dim, format);
936 456 c->fs_gpp = prism_centroid_fastscan_max_groups(dim);
937 456 c->ok = true;
938 456 }
939
940 /* Plan-pass entry ("write the tape"): cluster the sample once, record
941 * every node, and return the layout totals -- see the header comment. */
942 bool
943 228 prism_routing_tree_plan(
944 const float *vectors,
945 uint32_t nvecs,
946 Dimension dim,
947 uint32_t nlist,
948 uint32_t fan_out,
949 DistanceMetric metric,
950 PrismCentroidFormat format,
951 const KMeansOptions *opts,
952 PrismBlobStore *store,
953 PrismStreamTreePlan *out)
954 {
955 204 RoutingTreeCtx c;
956 228 routing_tree_ctx_init(&c, dim, nlist, fan_out, format);
957 /* Only the plan pass clusters, so only it carries the sample, the
958 * metric and the k-means options. */
959 228 c.vectors = vectors;
960 228 c.metric = metric;
961
1/2
✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
228 c.opts = opts ? *opts : (KMeansOptions)VS_KMEANS_OPTIONS_DEFAULT;
962 228 c.store = store;
963 228 c.leaf_sum = vs_alloc0((size_t)dim * sizeof(double));
964
1/2
✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
228 if (store != NULL)
965 {
966 /* Recording narrows each node's assignments into this scratch; the
967 * root -- first and largest -- sizes it for the whole pass. */
968 228 c.assign_scratch = vs_alloc((size_t)nvecs * sizeof(uint16_t));
969 }
970
971 /*
972 * The recursion's per-node scratch (k-means temporaries, index slices,
973 * child-block arrays) lives in its own context so anything a node fails
974 * to free is reclaimed here, at the end of the pass, rather than
975 * accumulating for the rest of the build. This pass-scoped context is
976 * the deliberate leak-containment boundary: node lifetimes nest (a
977 * parent's k-means result and child arrays stay live across its
978 * children), so finer-grained reclamation such as resets at node or
979 * sibling boundaries would free live ancestor state — and would turn a
980 * missed free (a bounded, observable leak) into a use-after-free.
981 * Within a node, explicit frees remain the mechanism; the context caps
982 * their blast radius at one pass. The output (leaf_mean) is allocated
983 * in the caller's context outside the switch.
984 */
985 228 VsMemCtx scratch = vs_memctx_create(NULL, "vs stream plan");
986 228 VsMemCtx old_ctx = vs_memctx_switch(scratch);
987 228 plan_node_recurse(&c, NULL, nvecs, 0);
988 228 vs_memctx_switch(old_ctx);
989 228 vs_memctx_delete(scratch);
990
991
1/2
✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
228 if (c.assign_scratch != NULL)
992 228 vs_free(c.assign_scratch);
993
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 228 times.
228 if (!c.ok)
994 {
995 ✗ vs_free(c.leaf_sum);
996 ✗ return false;
997 }
998
999 228 out->nleaves = c.nleaves;
1000 228 out->nlevels = c.nlevels;
1001 228 out->centroid_pages = c.centroid_pages;
1002 228 out->leaf_mean = vs_alloc((size_t)dim * sizeof(float));
1003
2/2
✓ Branch 0 taken 146280 times.
✓ Branch 1 taken 228 times.
146508 for (Dimension d = 0; d < dim; d++)
1004 146280 out->leaf_mean[d] = c.nleaves > 0
1005 146280 ? (float)(c.leaf_sum[d] / (double)c.nleaves)
1006
1/2
✓ Branch 0 taken 146280 times.
✗ Branch 1 not taken.
146280 : 0.0f;
1007 228 vs_free(c.leaf_sum);
1008 228 return true;
1009 }
1010
1011 /* Replay-pass entry ("read the tape"): stream every centroid + head page
1012 * from the recorded nodes; returns the root block. */
1013 BlockNumber
1014 228 prism_routing_tree_write(
1015 VsStorage *storage,
1016 uint32_t nvecs,
1017 Dimension dim,
1018 DistanceMetric metric,
1019 uint32_t nlist,
1020 uint32_t fan_out,
1021 PrismCentroidFormat format,
1022 const RaBitQParams *rq_params,
1023 const float *global_mean,
1024 PrismBlobStore *store,
1025 BlockNumber first_posting,
1026 BlockNumber first_centroid,
1027 PrismStreamLeafCb on_leaf,
1028 void *on_leaf_arg,
1029 PrismExactCentroidCollector *collector)
1030 {
1031 /* Replay never clusters: everything it needs is on the tape, so it
1032 * takes no sample vectors, metric or k-means options. */
1033
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 228 times.
228 if (store == NULL)
1034 ✗ return InvalidBlockNumber;
1035
1036 204 RoutingTreeCtx c;
1037 228 routing_tree_ctx_init(&c, dim, nlist, fan_out, format);
1038 228 c.metric = metric;
1039 228 c.storage = storage;
1040 228 c.store = store;
1041 {
1042 /* A node clusters into at most fan_out groups (the flat root's k =
1043 * nlist <= fan_out). The assignment scratch covers the root's full
1044 * sample; deeper slices are strictly smaller. */
1045 228 c.replay_cents = vs_alloc((size_t)c.fan_out * dim * sizeof(float));
1046 228 c.assign_scratch = vs_alloc((size_t)nvecs * sizeof(uint16_t));
1047 228 c.leaf_blk_scratch = vs_alloc((size_t)c.fan_out * sizeof(BlockNumber));
1048 }
1049 228 c.rq_params = rq_params;
1050 228 c.global_mean = global_mean;
1051 228 c.first_posting = first_posting;
1052 228 c.next_blk = first_centroid;
1053 228 c.on_leaf = on_leaf;
1054 228 c.on_leaf_arg = on_leaf_arg;
1055 228 c.collector = collector;
1056
1057 /* Same pass-scoped scratch as the PLAN pass -- the leak-containment
1058 * boundary (see the note there). on_leaf runs under it too; its
1059 * allocations must not outlive the call. */
1060 228 VsMemCtx scratch = vs_memctx_create(NULL, "vs stream write");
1061 228 VsMemCtx old_ctx = vs_memctx_switch(scratch);
1062 228 BlockNumber root = replay_node_recurse(&c, nvecs, 0);
1063 228 vs_memctx_switch(old_ctx);
1064 228 vs_memctx_delete(scratch);
1065
1/2
✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
228 if (c.replay_cents != NULL)
1066 228 vs_free(c.replay_cents);
1067
1/2
✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
228 if (c.assign_scratch != NULL)
1068 228 vs_free(c.assign_scratch);
1069
1/2
✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
228 if (c.leaf_blk_scratch != NULL)
1070 228 vs_free(c.leaf_blk_scratch);
1071
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 204 times.
228 return c.ok ? root : InvalidBlockNumber;
1072 }
1073
1074 /* Parallel build: write one worker-built (materialized) subtree's pages at
1075 * its reserved block range, mapping its leaves into the global leaf index
1076 * space -- see the header comment. */
1077 BlockNumber
1078 405 prism_routing_subtree_write(
1079 VsStorage *storage,
1080 const HKMeansResult *subtree,
1081 Dimension dim,
1082 DistanceMetric metric,
1083 uint32_t fan_out,
1084 uint8_t level_offset,
1085 PrismCentroidFormat format,
1086 const RaBitQParams *rq_params,
1087 const float *global_mean,
1088 BlockNumber first_posting,
1089 uint32_t leaf_offset,
1090 BlockNumber first_block,
1091 PrismStreamLeafCb on_leaf,
1092 void *on_leaf_arg,
1093 PrismExactCentroidCollector *collector)
1094 {
1095 405 uint32_t max_ent = prism_centroid_max_entries_fmt(dim, format);
1096
1097 /* Lay the subtree's nodes out at reserved blocks starting at first_block
1098 * (BFS: node 0 = subtree root at first_block). */
1099 405 BlockNumber *nfb = vs_alloc((size_t)subtree->nnodes * sizeof(BlockNumber));
1100 405 (void)prism_compute_centroid_layout(subtree, max_ent, first_block, nfb);
1101
1102 /* Leaf entries link to formula-derived posting heads (first_posting +
1103 * global leaf index); leaf_offset maps the subtree's local leaf indices to
1104 * the global index space. */
1105 /* Subtree node levels are subtree-relative; level_offset places them at
1106 * their absolute depth (the tree root above them is level 0). */
1107 /* Cosine: normalize the subtree's leaf centroids in place before the
1108 * leaf codes and head references are written from them (matches the
1109 * flat-tree path; k-means means drift below unit norm). */
1110
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 391 times.
405 if (metric == DISTANCE_COSINE)
1111 {
1112 14 float *lv = hk_leaf_centroids(subtree);
1113
2/2
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 14 times.
137 for (uint32_t li = 0; li < subtree->nleaves; li++)
1114 123 vs_l2_normalize(lv + (size_t)li * dim, dim);
1115 }
1116
1117 405 prism_write_centroid_tree(
1118 storage,
1119 subtree,
1120 dim,
1121 fan_out,
1122 level_offset,
1123 format,
1124 rq_params,
1125 global_mean,
1126 prism_leaf_head_blkno(
1127 first_posting,
1128 leaf_offset,
1129 prism_posting_reference_pages(dim)),
1130 prism_posting_reference_pages(dim),
1131 nfb,
1132 NULL,
1133 collector);
1134 405 vs_free(nfb);
1135
1136 /* Head pages carry pt_centroid from the resident float leaf centroids. */
1137
1/2
✓ Branch 0 taken 405 times.
✗ Branch 1 not taken.
405 if (on_leaf != NULL)
1138 {
1139 405 const float *leaves = hk_leaf_centroids(subtree);
1140
2/2
✓ Branch 0 taken 2744 times.
✓ Branch 1 taken 405 times.
3149 for (uint32_t i = 0; i < subtree->nleaves; i++)
1141 2744 on_leaf(on_leaf_arg, leaf_offset + i, leaves + (size_t)i * dim);
1142 }
1143
1144 405 return first_block;
1145 }
1146
1147 /* Resolve the tree fan-out when the user left it at the default: sqrt of
1148 * the partition count, falling to cbrt when that exceeds a page's worth of
1149 * children. */
1150 uint32_t
1151 364 prism_auto_fan_out(uint32_t fan_out, uint32_t nlist, uint32_t default_fan_out)
1152 {
1153
3/4
✓ Branch 0 taken 339 times.
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 114 times.
364 if (fan_out != default_fan_out || nlist <= fan_out)
1154 225 return (nlist <= fan_out) ? nlist : fan_out;
1155
1156 139 uint32_t f = (uint32_t)ceil(sqrt((double)nlist));
1157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 139 times.
139 if (f > 256)
1158 ✗ f = (uint32_t)ceil(cbrt((double)nlist));
1159 114 return f;
1160 }
1161
1162 /* Target entries per posting list at this dimension -- see the header. */
1163 uint32_t
1164 2241 prism_target_entries_per_dim(Dimension dim, uint32_t target_pages)
1165 {
1166
2/2
✓ Branch 0 taken 2115 times.
✓ Branch 1 taken 126 times.
2241 if (target_pages == 0)
1167 2115 target_pages = PRISM_DEFAULT_TARGET_PAGES;
1168
1169 2241 uint32_t per_page = prism_posting_page_usable() /
1170 2241 PRISM_POSTING_ENTRY_SIZE(dim);
1171
1172
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2241 times.
2241 if (per_page < 1)
1173 ✗ per_page = 1;
1174
1175 2241 uint32_t target = per_page * target_pages;
1176
1177 147 return target > PRISM_MIN_ENTRIES_PER_LIST ? target
1178 2241 : PRISM_MIN_ENTRIES_PER_LIST;
1179 }
1180
1181 /* Automatic partition count from the (estimated) row count. */
1182 uint32_t
1183 118 prism_auto_nlist(double count, Dimension dim, uint32_t target_pages)
1184 {
1185 /*
1186 * One list per prism_target_entries_per_dim(dim) vectors -- see the header
1187 * for why that is the target. The hierarchical centroid tree keeps routing
1188 * cheap even at a high list count, so nlist scales linearly with the row
1189 * count.
1190 *
1191 * Floor it at sqrt(count): for small tables count/target collapses toward
1192 * a single list, which under-partitions and can starve the k-means build.
1193 * The linear target overtakes the sqrt floor at target^2 rows (65536 at a
1194 * 256-entry target). Back-ends clamp the result to their own nlist
1195 * ceiling.
1196 */
1197
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
118 double c = count > 1.0 ? count : 1.0;
1198 118 uint32_t target = prism_target_entries_per_dim(dim, target_pages);
1199 118 uint32_t linear = (uint32_t)(c / (double)target + 0.5);
1200 118 uint32_t min_lists = (uint32_t)sqrt(c);
1201 118 uint32_t nlist = linear > min_lists ? linear : min_lists;
1202
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 100 times.
118 return nlist < 1 ? 1 : nlist;
1203 }
1204
1205 /*
1206 * Vectors per posting list at a given row count -- the resting size
1207 * maintenance aims each list at. Inverts prism_auto_nlist so the two cannot
1208 * drift apart; see the header for the sqrt-floor regime and the nlist == 0
1209 * convention.
1210 */
1211 uint32_t
1212 20 prism_target_entries_per_list(
1213 double count, uint32_t nlist, Dimension dim, uint32_t target_pages)
1214 {
1215
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
20 double c = count > 1.0 ? count : 1.0;
1216
1217
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
20 if (nlist == 0)
1218 18 nlist = prism_auto_nlist(c, dim, target_pages);
1219
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
20 if (nlist < 1)
1220 ✗ nlist = 1;
1221
1222 20 uint32_t per_list = (uint32_t)(c / (double)nlist + 0.5);
1223
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
20 return per_list < 1 ? 1 : per_list;
1224 }
1225
1226 /* 2nd-nearest cluster from a distance-sorted candidate list, or
1227 * primary_cluster when the runner-up is not within epsilon (no replication
1228 * warranted) -- see the header comment. */
1229 uint32_t
1230 ✗ prism_find_secondary_cluster(
1231 const uint32_t *cand_leaves,
1232 const Distance *cand_dists,
1233 uint32_t ncand,
1234 uint32_t primary_cluster,
1235 Distance primary_dist,
1236 double epsilon)
1237 {
1238 /* Candidates are sorted by ascending distance, so the first one
1239 * that is not the primary is the 2nd-nearest centroid. */
1240 ✗ for (uint32_t i = 0; i < ncand; i++)
1241 {
1242 ✗ if (cand_leaves[i] == primary_cluster)
1243 ✗ continue;
1244
1245 ✗ Distance best2 = cand_dists[i];
1246 ✗ double gap = (double)best2 - (double)primary_dist;
1247 ✗ double gap_ratio = (primary_dist != 0.0)
1248 ✗ ? gap / fabs((double)primary_dist)
1249 ✗ : INFINITY;
1250
1251 ✗ if (gap_ratio <= epsilon)
1252 ✗ return cand_leaves[i];
1253 ✗ break;
1254 }
1255
1256 ✗ return primary_cluster;
1257 }
1258
1259 /*
1260 * SOAR secondary cluster: the leaf (other than the primary) minimizing the
1261 * orthogonality-amplified distance, decomposed so both terms use the SIMD
1262 * vecops kernels:
1263 *
1264 * oa(c) = ||v - c||^2 + lambda * (r_hat . (v - c))^2
1265 * = ||v - c||^2 + lambda * (r_hat.v - r_hat.c)^2
1266 *
1267 * r_hat.v is constant across centroids, so only ||v - c||^2 and r_hat.c are
1268 * per-centroid. Since lambda * (...)^2 >= 0, ||v - c||^2 is a lower bound on
1269 * oa: when it already exceeds the running best we skip the dot product (exact
1270 * pruning — no recall impact).
1271 *
1272 * The search set is `count` leaves: the ids cand_leaves[0..count) when
1273 * cand_leaves is non-NULL, otherwise leaves 0..count (a full scan, called with
1274 * count == nleaves). The candidate form is O(count) rather than O(nleaves);
1275 * because the minimizer always has a small ||v - c||^2 (a far leaf cannot win)
1276 * it lies among the nearest leaves the beam already found, so the result is
1277 * unchanged while scaling to large nlist — where a full scan would read the
1278 * entire (multi-hundred-MB) leaf-centroid array per replicated vector.
1279 */
1280 uint32_t
1281 37549 prism_find_soar_secondary(
1282 const float *vec,
1283 const float *leaf_centroids,
1284 const uint32_t *cand_leaves,
1285 uint32_t count,
1286 Dimension dim,
1287 uint32_t primary_cluster,
1288 const float *normalized_residual,
1289 double lambda)
1290 {
1291 37549 float qrv = vs_dot_product(normalized_residual, vec, dim);
1292 37549 float lam = (float)lambda;
1293 37549 float best_oa = INFINITY;
1294 37549 uint32_t best_c = primary_cluster;
1295
1296
2/2
✓ Branch 0 taken 1342514 times.
✓ Branch 1 taken 37549 times.
1380063 for (uint32_t k = 0; k < count; k++)
1297 {
1298
2/2
✓ Branch 0 taken 124806 times.
✓ Branch 1 taken 1217708 times.
1342514 uint32_t i = cand_leaves ? cand_leaves[k] : k;
1299
2/2
✓ Branch 0 taken 37001 times.
✓ Branch 1 taken 1305513 times.
1342514 if (i == primary_cluster)
1300 37001 continue;
1301
1302 1305513 const float *cent = leaf_centroids + (size_t)i * dim;
1303
1304 1305513 float l2 = vs_l2_distance_squared(vec, cent, dim);
1305
2/2
✓ Branch 0 taken 1175708 times.
✓ Branch 1 taken 129805 times.
1305513 if (l2 >= best_oa)
1306 1175708 continue; /* oa >= l2 >= best_oa: cannot improve */
1307
1308 129805 float rc = vs_dot_product(normalized_residual, cent, dim);
1309 129805 float gap = qrv - rc;
1310 129805 float oa = l2 + lam * gap * gap;
1311
2/2
✓ Branch 0 taken 82653 times.
✓ Branch 1 taken 47152 times.
129805 if (oa < best_oa)
1312 {
1313 1106470 best_oa = oa;
1314 1106470 best_c = i;
1315 }
1316 }
1317
1318 37549 return best_c;
1319 }
1320
1321 /* Log the per-phase build time summary. */
1322 void
1323 249 prism_build_stats_print(const PrismBuildStats *s)
1324 {
1325 /* Per-phase breakdown — the single shared build summary, filled by both
1326 * the PostgreSQL build (via the build-progress seam) and the standalone
1327 * build. */
1328
1/3
✗ Branch 0 not taken.
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
249 vs_log("build: sample %.1fms, kmeans %.1fms, refine %.1fms, setup "
1329 "%.1fms, "
1330 "posting %.1fms, centroid %.1fms, total %.1fms\n",
1331 s->ms_sample,
1332 s->ms_kmeans,
1333 s->ms_refine,
1334 s->ms_setup,
1335 s->ms_posting,
1336 s->ms_centroid,
1337 s->ms_total);
1338
1339 /* Posting-merge sub-detail: only the standalone parallel path populates
1340 * these. Skip the line (and its zeros) when unset — e.g. the PostgreSQL
1341 * build, which tracks posting as one phase. */
1342
3/6
✓ Branch 0 taken 249 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 249 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 249 times.
249 if (s->ms_parallel > 0.0 || s->ms_merge > 0.0 || s->total_pages > 0)
1343 ✗ vs_log("build: posting detail — parallel %.1fms + merge %.1fms, "
1344 "%u workers + leader, %u pages, "
1345 "%u partial pages merged into %u\n",
1346 s->ms_parallel,
1347 s->ms_merge,
1348 s->nworkers,
1349 s->total_pages,
1350 s->merge_input,
1351 s->merge_output);
1352 249 }
1353