GCC Code Coverage Report


Directory: src/
File: src/index/parallel_build_leader.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 323 335 96.4%
Functions: 5 5 100.0%
Branches: 99 130 76.2%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * parallel_build_leader.c - PG parallel index build, leader side
6 *
7 * The leader sets up the DSM, launches workers, participates in the
8 * sampling + k-means phases as worker_id 0, streams the centroid tree to
9 * pages, then (phase 3) merges the workers' cluster-keyed sorted runs and
10 * builds each posting list. Head blocks are formula-derived
11 * (prism_leaf_head_blkno), so no per-partition head array is materialized.
12 * Returns false if parallelism could not start, so the caller falls back to a
13 * serial build.
14 */
15
16 #ifdef VS_STANDALONE
17 #include "standalone/instr_time.h"
18 #include "standalone/parallel_ctx.h" /* ParallelContext + lifecycle */
19 #include "standalone/pg_compat.h"
20 #else
21 #include <postgres.h>
22
23 #include <access/parallel.h>
24 #include <access/table.h>
25 #include <access/tableam.h>
26 #include <access/xloginsert.h>
27 #include <catalog/index.h>
28 #include <commands/progress.h>
29 #include <common/pg_prng.h>
30 #include <executor/instrument.h>
31 #include <miscadmin.h>
32 #include <pgstat.h>
33 #include <portability/instr_time.h>
34 #include <tcop/tcopprot.h>
35 #include <utils/backend_progress.h>
36 #include <utils/memutils.h>
37 #include <utils/rel.h>
38 #include <utils/sampling.h>
39 #include <utils/wait_event.h>
40 #endif
41
42 #include <inttypes.h>
43 #include <math.h>
44
45 #include "algo/distance.h"
46 #include "algo/hkmeans.h"
47 #include "algo/kmeans.h"
48 #include "algo/kmeans_internal.h"
49 #include "algo/vecops.h"
50 #include "core/log.h"
51 #include "core/memory.h"
52 #include "index/build_progress.h"
53 #include "index/centroid_build.h"
54 #include "index/centroid_page.h"
55 #include "index/index_build.h"
56 #include "index/parallel_build.h"
57 #include "index/posting_build.h"
58 #include "index/posting_page.h"
59 #include "quant/fastscan.h"
60 #include "types/vec16.h"
61 #include "types/vec32.h"
62
63 #ifndef VS_STANDALONE
64 #include "build.h"
65 #include "meta.h"
66 #include "storage.h"
67 #include "support_pg.h"
68 #endif
69
70 /*
71 * Build every cluster's posting list from a populated (not yet performsorted)
72 * cluster-keyed sorter. Shared by the serial build and the parallel leader:
73 * performsort, then read entries grouped by cluster and write each list with a
74 * single resident page builder (head at prism_leaf_head_blkno, continuations
75 * appended at the relation's end and chained). Ends the sorter.
76 *
77 * Why iterate clusters 0..nlist rather than just draining the sorter until it
78 * is empty: EVERY cluster needs a posting-list head, including clusters that
79 * received no vectors. The centroid tree's leaf entries reference
80 * first_posting
81 * + c for every c in [0, nlist) (see prism_write_centroid_tree), so an empty
82 * cluster still needs a valid (empty) head block to point at. A loop over the
83 * cluster index emits a head for every cluster uniformly — an empty cluster's
84 * inner while simply does not run and finish() returns an empty head. A
85 * drain-until-empty loop would only produce heads for clusters present in the
86 * stream and would have to separately backfill empty heads for gap clusters
87 * and for all trailing clusters past the last one seen.
88 *
89 * This REQUIRES (and assumes) the sorter returns entries in ascending cluster
90 * order, matching the 0..nlist iteration order: the sorter is keyed on the
91 * cluster id (PG tuplesort on the int4 key; standalone qsort by cluster), so
92 * all entries for a cluster are contiguous and clusters appear in increasing
93 * order. Thus while walking c upward, any remaining entry has cur_cluster >= c
94 * (it equals c for a non-empty cluster, or is greater when c is empty). The
95 * asserts below make that contract explicit: an out-of-order key would pair
96 * entries with the wrong cluster, and an out-of-range id (>= nlist) would
97 * never match any c and be silently dropped (leaving the sorter non-empty at
98 * the end).
99 */
100 void
101 355 prism_posting_build_lists(
102 PrismSorter *sorter,
103 VsStorage *storage,
104 uint32_t nlist,
105 Dimension dim,
106 bool fastscan,
107 const RaBitQParams *rq_params,
108 BlockNumber first_posting)
109 {
110 355 prism_pbuild_sort_performsort(sorter);
111
112 /*
113 * Each list's head was pre-written with its pt_centroid (P^T * centroid,
114 * the RaBitQ encode reference) during the centroid build: adopt it and
115 * append the sorted entries in place. No second head construction, no
116 * in-RAM float centroids — the tree can be freed before this runs — and
117 * a cluster with no entries keeps its on-disk head untouched.
118 */
119 355 uint32_t cur_cluster = 0;
120 355 const void *entry = NULL;
121 355 bool have = prism_pbuild_sort_getnext(sorter, &cur_cluster, &entry);
122
123 /* Each list's builder scratch goes in a context reset after the list,
124 * since the standalone arena frees nothing on its own. Only the builder
125 * runs in it: the sorter's next entry must outlive the reset. */
126 249 VsMemCtx list_ctx =
127 355 vs_memctx_create(vs_memctx_current(), "prism posting list");
128
3/3
✓ Branch 0 taken 1554 times.
✓ Branch 1 taken 9868 times.
✓ Branch 2 taken 249 times.
11671 for (uint32_t c = 0; c < nlist; c++)
129 {
130 /* Head block of cluster c is formula-derived; the head region
131 * [first_posting, first_posting + nlist * stride) was pre-extended and
132 * its pt_centroid written during the centroid streaming. Continuation
133 * pages are appended at the relation's end and chained (no per-cluster
134 * reserve), so no O(nlist) reserve arrays are needed. Adopt the
135 * pre-written head and append in place: no second head construction,
136 * and a cluster with no entries keeps its on-disk head untouched. */
137 11316 BlockNumber head_blk = prism_leaf_head_blkno(
138 first_posting, c, prism_posting_reference_pages(dim));
139 9762 PrismPostingBuilder hb;
140 11316 VsMemCtx outer = vs_memctx_switch(list_ctx);
141 11316 prism_posting_builder_adopt_head(
142 &hb, storage, rq_params, dim, c, head_blk, fastscan);
143
2/2
✓ Branch 0 taken 9724 times.
✓ Branch 1 taken 38 times.
11316 vs_memctx_switch(outer);
144
145 /* Ascending, grouped order: a pending entry is never for a cluster we
146 * already finished. If it were < c we would have skipped its head. */
147
4/4
✓ Branch 0 taken 11278 times.
✓ Branch 1 taken 38 times.
✓ Branch 2 taken 9724 times.
✓ Branch 3 taken 1554 times.
11316 Assert(!have || cur_cluster >= c);
148
149
4/4
✓ Branch 0 taken 608015 times.
✓ Branch 1 taken 383 times.
✓ Branch 2 taken 597082 times.
✓ Branch 3 taken 10933 times.
608398 while (have && cur_cluster == c)
150 {
151 597082 prism_posting_entry_add(&hb, entry, dim);
152 597082 have = prism_pbuild_sort_getnext(sorter, &cur_cluster, &entry);
153 }
154
155 11316 outer = vs_memctx_switch(list_ctx);
156 11316 (void)prism_posting_builder_finish(&hb);
157 11316 prism_posting_builder_cleanup(&hb);
158 11316 vs_memctx_switch(outer);
159 11316 vs_memctx_reset(list_ctx);
160 }
161 355 vs_memctx_delete(list_ctx);
162
163 /* Every entry must have landed in some cluster's list. A leftover entry
164 * means an id >= nlist (out of range) that matched no c and would
165 * otherwise be silently dropped. */
166
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 355 times.
355 Assert(!have);
167 355 prism_pbuild_sort_end(sorter);
168 355 }
169
170 /* ----------------------------------------------------------------
171 * Batched streaming tree build — leader-side callbacks
172 * ---------------------------------------------------------------- */
173
174 /* PLAN-pass batch callback: record each subtree's leaf count + centroid-page
175 * count (no writes) so the leader can size the reserve + block layout, and
176 * keep the blob in the spillable store for the streaming pass to read back
177 * in the same (child) order. */
178 typedef struct PlanCbArg
179 {
180 uint32_t *nleaves_arr; /* [km_k] */
181 uint32_t *pages_arr; /* [km_k] */
182 uint32_t max_ent;
183 uint32_t subtree_nlevels; /* actual depth of the (uniform) subtrees */
184 Dimension dim;
185 double *leaf_sum; /* [dim] leaf-centroid sum across all subtrees, for
186 * the leaf_mean the leader uses as global_mean */
187 PrismBlobStore *store; /* subtree blobs, in child order */
188 } PlanCbArg;
189
190 static void
191 146 plan_batch_cb(
192 void *arg,
193 const uint32_t *children,
194 uint32_t bs,
195 char *base,
196 uint64_t slot_size)
197 {
198 146 PlanCbArg *a = (PlanCbArg *)arg;
199
2/2
✓ Branch 0 taken 323 times.
✓ Branch 1 taken 146 times.
469 for (uint32_t s = 0; s < bs; s++)
200 {
201 111 const HKMeansResult *sub = (const HKMeansResult *)
202 323 prism_dsm_child_subtree(base, s, slot_size);
203 323 uint32_t child = children[s];
204 323 BlockNumber *nfb = vs_alloc((size_t)sub->nnodes * sizeof(BlockNumber));
205 /* Subtrees are built to a uniform depth, so any non-empty one gives
206 * the streamed tree's subtree depth (full depth = this + 1 root
207 * level). */
208
1/2
✓ Branch 0 taken 323 times.
✗ Branch 1 not taken.
323 if (sub->nleaves > 0)
209 323 a->subtree_nlevels = sub->nlevels;
210 323 a->nleaves_arr[child] = sub->nleaves;
211 646 a->pages_arr[child] = (uint32_t)
212 323 prism_compute_centroid_layout(sub, a->max_ent, 0, nfb);
213 323 vs_free(nfb);
214
215
1/2
✓ Branch 0 taken 323 times.
✗ Branch 1 not taken.
323 if (a->leaf_sum != NULL)
216 {
217 323 const float *lc = hk_leaf_centroids(sub);
218
2/2
✓ Branch 0 taken 2231 times.
✓ Branch 1 taken 323 times.
2554 for (uint32_t l = 0; l < sub->nleaves; l++)
219
2/2
✓ Branch 0 taken 865970 times.
✓ Branch 1 taken 2231 times.
868201 for (Dimension d = 0; d < a->dim; d++)
220 865970 a->leaf_sum[d] += lc[(size_t)l * a->dim + d];
221 }
222
223 323 prism_pbuild_blobstore_put(a->store, sub, sub->total_size);
224 }
225 146 }
226
227 /* What both routing-tree shapes hand back to do_parallel_build: the layout
228 * facts the leader publishes to the workers before phase 3. */
229 typedef struct TreeLayout
230 {
231 BlockNumber first_posting; /* see prism_leaf_head_blkno */
232 BlockNumber root_blk; /* tree root page */
233 uint8_t nlevels; /* written depth */
234 uint32_t nlist; /* actual leaf count */
235 } TreeLayout;
236
237 /*
238 * Assemble and write the routing tree for the hierarchical shape
239 * (nlevels >= 2): each participant builds the subtree of every root child
240 * it owns; the leader records each batch's layout counts (PLAN), computes
241 * the block layout and the leaf-centroid mean, pre-extends the relation,
242 * replays the spilled subtree blobs to pages, and writes the root page
243 * above them. Fills global_mean and the layout the caller publishes.
244 */
245 static bool
246 70 build_routing_tree_batched(
247 PrismBuildShared *shared,
248 VsStorage *storage,
249 PrismBuildProgress *prog,
250 PrismDsmSamples *dsm_samples,
251 PrismDsmRootAssign *dsm_ra,
252 float *cents,
253 uint32_t km_k,
254 uint32_t nlist,
255 uint32_t fan_out,
256 Barrier *barrier,
257 RaBitQParams *rq_params,
258 uint32_t max_ent,
259 BlockNumber first_centroid,
260 float *global_mean,
261 PrismExactCentroidCollector *collector,
262 TreeLayout *out)
263 {
264 70 Dimension dim = shared->dim;
265 70 int nparticipants = shared->nparticipants;
266 70 PrismCentroidFormat fmt = shared->centroid_format;
267
268 /* Size the ring slot from the actual per-child sample counts: a subtree
269 * can never hold more leaves than the samples routed to its root child,
270 * which caps the slot far below the analytic worst case (nlist here is
271 * the worst-case sizing bound, up to fan_out x the requested count). */
272 70 uint32_t max_cc = 1;
273 {
274 70 uint32_t *child_count = vs_alloc0((size_t)km_k * sizeof(uint32_t));
275 70 prism_pbuild_count_children(
276 dsm_samples, dsm_ra, nparticipants, km_k, child_count);
277
3/3
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 165 times.
✓ Branch 2 taken 20 times.
397 for (uint32_t c = 0; c < km_k; c++)
278
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 100 times.
327 if (child_count[c] > max_cc)
279 112 max_cc = child_count[c];
280 70 vs_free(child_count);
281 }
282 70 uint32_t nlist_c = (nlist + fan_out - 1) / fan_out;
283 20 uint64_t slot_size =
284 70 vs_hkmeans_max_blob_size_capped(nlist_c, fan_out, dim, max_cc);
285
286 /* The slot must fit one allocation (the leader reads each spilled blob
287 * back through a palloc'd buffer), which also keeps the blob format's
288 * 32-bit interior offsets valid. */
289
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 70 times.
70 if (slot_size > (uint64_t)MaxAllocSize)
290 ✗ vs_error(
291 "prism: subtree slot %llu MB exceeds the allocation limit "
292 "(nlist %u, fan_out %u); increase fan_out or decrease nlist",
293 (unsigned long long)(slot_size >> 20),
294 nlist,
295 fan_out);
296 /* The ring is the build's only region outside the sample budget; hold
297 * it to the same standard. work_mem_kb == 0 = unbudgeted back-end. */
298
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 50 times.
70 if (shared->work_mem_kb > 0 &&
299 20 (uint64_t)nparticipants * slot_size >
300
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
20 (uint64_t)shared->work_mem_kb * 1024)
301 ✗ vs_error(
302 "prism: subtree ring %llu MB exceeds maintenance_work_mem "
303 "(nlist %u, fan_out %u); increase maintenance_work_mem or "
304 "fan_out",
305 (unsigned long long)(((uint64_t)nparticipants * slot_size) >>
306 20),
307 nlist,
308 fan_out);
309
310 /* Ring barrier: create + publish (handle, slot size) before arriving;
311 * the workers attach after. */
312 70 void *ring_seg = NULL;
313 70 char *subtrees_base = prism_pbuild_subtree_ring_create(
314 shared, nparticipants, slot_size, &ring_seg);
315
2/3
✓ Branch 0 taken 50 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
70 vs_debug(
316 "prism: subtree ring %d x %llu KB (largest child %u samples)",
317 nparticipants,
318 (unsigned long long)(slot_size >> 10),
319 max_cc);
320 70 BarrierArriveAndWait(barrier, WAIT_EVENT_PARALLEL_CREATE_INDEX_SCAN);
321
322 70 uint32_t *nleaves_arr = vs_alloc0((size_t)km_k * sizeof(uint32_t));
323 70 uint32_t *pages_arr = vs_alloc0((size_t)km_k * sizeof(uint32_t));
324
325 /* PLAN pass: build subtrees, discover leaf + page counts (and the
326 * leaf-centroid sum for global_mean). */
327 70 prism_build_report_phase(prog, PRISM_BUILD_PHASE_SUBTREES);
328 207 PlanCbArg planarg = {
329 .nleaves_arr = nleaves_arr,
330 .pages_arr = pages_arr,
331 .max_ent = max_ent,
332 .subtree_nlevels = 1,
333 .dim = dim,
334 69 .leaf_sum = vs_alloc0((size_t)dim * sizeof(double)),
335 69 .store = prism_pbuild_blobstore_begin(),
336 };
337 /* The batch schedule is largest-first; the blob store receives the
338 * subtrees in that order, so the replay below needs the same order
339 * to place each blob at its child's reserved block range. */
340 69 uint32_t *child_order = vs_alloc((size_t)km_k * sizeof(uint32_t));
341 69 prism_pbuild_stream_subtrees(
342 0,
343 nparticipants,
344 dsm_samples,
345 dsm_ra,
346 cents,
347 km_k,
348 nlist,
349 fan_out,
350 dim,
351 shared->metric,
352 shared->km_max_iterations,
353 subtrees_base,
354 slot_size,
355 barrier,
356 plan_batch_cb,
357 &planarg,
358 child_order);
359
360 /* Every batch is consumed into the blob store; the ring is dead before
361 * the write pass starts. */
362 69 prism_pbuild_subtree_ring_release(ring_seg);
363
364 /* Root page(s) occupy the reserved block(s) at first_centroid;
365 * subtrees follow, so meta.first_centroid stays 1 (root written last,
366 * in place). */
367 69 uint32_t root_pages = (km_k + max_ent - 1) / max_ent;
368 69 uint32_t *leaf_off = vs_alloc((size_t)km_k * sizeof(uint32_t));
369 69 uint32_t *block_off = vs_alloc((size_t)km_k * sizeof(uint32_t));
370 69 uint32_t lo = 0;
371 69 BlockNumber bo = 0;
372
3/3
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 161 times.
✓ Branch 2 taken 19 times.
392 for (uint32_t c = 0; c < km_k; c++)
373 {
374 323 leaf_off[c] = lo;
375 323 block_off[c] = (uint32_t)bo;
376 323 lo += nleaves_arr[c];
377 323 bo += pages_arr[c];
378 }
379 69 uint32_t actual_nlist = lo;
380 69 BlockNumber subtree_base = first_centroid + root_pages;
381 69 BlockNumber first_posting = subtree_base + bo;
382
383 /* The centroid-page region [first_centroid, first_posting) is now
384 * sized; the streaming pass below collects every internal node's
385 * exact centroids into it (the root included). */
386
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 6 times.
69 if (collector != NULL)
387
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
63 prism_exact_centroid_collector_init(
388 collector,
389 dim,
390 fmt,
391 first_centroid,
392 63 (uint32_t)(first_posting - first_centroid),
393
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
63 prism_exact_centroid_budget(shared->work_mem_kb),
394 prism_exact_centroid_expected_slots(actual_nlist, fan_out));
395
396 /* Leaf-centroid mean from the PLAN pass -> the encoder centering. */
397
2/2
✓ Branch 0 taken 42108 times.
✓ Branch 1 taken 69 times.
42177 for (Dimension d = 0; d < dim; d++)
398 42108 global_mean[d] = actual_nlist > 0 ? (float)(planarg.leaf_sum[d] /
399 42108 (double)actual_nlist)
400
1/2
✓ Branch 0 taken 42108 times.
✗ Branch 1 not taken.
42108 : 0.0f;
401
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 66 times.
69 if (shared->metric == DISTANCE_COSINE)
402 3 vs_l2_normalize(global_mean, dim);
403 69 vs_free(planarg.leaf_sum);
404 69 planarg.leaf_sum = NULL;
405
406 /* Head blocks are formula-derived (prism_leaf_head_blkno): a contiguous
407 * head region of actual_nlist heads at a fixed stride. Pre-extend the
408 * relation to cover the centroid pages + the head region so the write
409 * pass can write both at reserved blocks; continuation pages are
410 * appended past it during prism_posting_build_lists. No O(nlist) reserve
411 * arrays. */
412 69 prism_build_reserve_layout(
413 storage,
414 prism_leaf_head_blkno(
415 first_posting,
416 actual_nlist,
417 prism_posting_reference_pages(dim)));
418
419 /* Streaming pass: read each subtree blob back from the store (child
420 * order matches the append order) and stream its centroid + head
421 * pages to the reserved block range, then the root page. Leader-only:
422 * the PLAN pass already produced every subtree, so the workers have
423 * nothing to contribute here and run no barriers for this phase. */
424 69 prism_build_report_phase(prog, PRISM_BUILD_PHASE_CENTROID);
425 69 BlockNumber *subtree_root_blk = vs_alloc(
426 50 (size_t)km_k * sizeof(BlockNumber));
427 19 PrismHeadWriteCtx head;
428 69 prism_head_write_ctx_init(
429 69 &head, storage, rq_params, dim, shared->fastscan, first_posting);
430 69 HKMeansResult *blob = vs_alloc(slot_size);
431 69 prism_pbuild_blobstore_rewind(planarg.store);
432
3/3
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 161 times.
✓ Branch 2 taken 19 times.
392 for (uint32_t i = 0; i < km_k; i++)
433 {
434 /* Blobs arrive in the largest-first batch order; c is the child
435 * whose reserved block range this blob belongs to. */
436 323 uint32_t c = child_order[i];
437 323 (void)prism_pbuild_blobstore_get(planarg.store, blob, slot_size);
438 323 BlockNumber base_blk = subtree_base + block_off[c];
439 323 subtree_root_blk[c] = prism_routing_subtree_write(
440 storage,
441 blob,
442 dim,
443 shared->metric,
444 fan_out,
445 1, /* subtrees hang off the level-0 root */
446 fmt,
447 rq_params,
448 global_mean,
449 first_posting,
450 323 leaf_off[c],
451 base_blk,
452 prism_write_leaf_head,
453 &head,
454 collector);
455 }
456 69 vs_free(blob);
457 69 vs_free(child_order);
458 69 prism_pbuild_blobstore_end(planarg.store);
459 69 planarg.store = NULL;
460
461 /* Root centroid page at the reserved first_centroid (children =
462 * subtree roots). Written last, but in place, so first_centroid
463 * stays 1. */
464 69 BlockNumber root_blk = first_centroid;
465 69 prism_centroid_write_node(
466 storage,
467 dim,
468 cents,
469 km_k,
470 fmt,
471 0,
472 0,
473 50 (uint16_t)fan_out,
474 rq_params,
475 global_mean,
476 subtree_root_blk,
477 NULL,
478 root_blk,
479 collector);
480
481 69 prism_head_write_ctx_cleanup(&head);
482 69 vs_free(subtree_root_blk);
483 69 vs_free(leaf_off);
484 69 vs_free(block_off);
485 69 vs_free(nleaves_arr);
486 69 vs_free(pages_arr);
487
488 69 out->first_posting = first_posting;
489 69 out->root_blk = root_blk;
490 69 out->nlevels = (uint8_t)(planarg.subtree_nlevels + 1);
491 69 out->nlist = actual_nlist;
492 69 return true;
493 }
494
495 /*
496 * Assemble and write the routing tree for the flat shape (nlevels == 1):
497 * the root k-means centroids already ARE the leaves, so stream the
498 * one-level tree directly (root = leaf-parent page at first_centroid).
499 * Fills global_mean and the layout the caller publishes; false when the
500 * flat carrier cannot be built.
501 */
502 static bool
503 82 build_routing_tree_flat(
504 PrismBuildShared *shared,
505 VsStorage *storage,
506 PrismBuildProgress *prog,
507 float *cents,
508 uint32_t km_k,
509 uint32_t fan_out,
510 RaBitQParams *rq_params,
511 uint32_t max_ent,
512 BlockNumber first_centroid,
513 float *global_mean,
514 TreeLayout *out)
515 {
516 82 Dimension dim = shared->dim;
517 82 PrismCentroidFormat fmt = shared->centroid_format;
518
519 /* Flat (nlevels == 1): cents already holds every leaf centroid; stream
520 * the one-level tree directly (root = leaf-parent at first_centroid).
521 */
522
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 78 times.
82 if (shared->metric == DISTANCE_COSINE)
523
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 4 times.
45 for (uint32_t c = 0; c < km_k; c++)
524 41 vs_l2_normalize(cents + (size_t)c * dim, dim);
525
526 82 HKMeansResult *flat = vs_hkmeans_build_flat(cents, km_k, fan_out, dim);
527
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 56 times.
82 if (flat == NULL)
528 ✗ return false;
529
530 82 uint32_t actual_nlist = flat->nleaves;
531 82 BlockNumber *nfb = vs_alloc((size_t)flat->nnodes * sizeof(BlockNumber));
532 26 uint32_t centroid_pages = (uint32_t)
533 82 prism_compute_centroid_layout(flat, max_ent, 0, nfb);
534 82 vs_free(nfb);
535 82 BlockNumber first_posting = first_centroid + centroid_pages;
536
537 /* Leaf-centroid mean -> the encoder centering (flat tree in hand). */
538 82 vec32_mean(hk_leaf_centroids(flat), actual_nlist, dim, global_mean);
539
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 78 times.
82 if (shared->metric == DISTANCE_COSINE)
540 4 vs_l2_normalize(global_mean, dim);
541
542 /* Head region: actual_nlist strided slots at first_posting (leaf c ->
543 * head first_posting + c * stride, the stride being the reference page
544 * count). Pre-extend to cover centroid + head region; continuations
545 * append past it. No O(nlist) reserve. */
546 82 prism_build_reserve_layout(
547 storage,
548 prism_leaf_head_blkno(
549 first_posting,
550 actual_nlist,
551 prism_posting_reference_pages(dim)));
552
553 82 prism_build_report_phase(prog, PRISM_BUILD_PHASE_CENTROID);
554 26 PrismHeadWriteCtx head;
555 82 prism_head_write_ctx_init(
556 82 &head, storage, rq_params, dim, shared->fastscan, first_posting);
557 82 BlockNumber root_blk = prism_routing_subtree_write(
558 storage,
559 flat,
560 dim,
561 shared->metric,
562 fan_out,
563 0, /* the flat tree IS the root level */
564 fmt,
565 rq_params,
566 global_mean,
567 first_posting,
568 0,
569 first_centroid,
570 prism_write_leaf_head,
571 &head,
572 /* the flat tree's only level is the leaf level — nothing
573 * internal to collect */
574 NULL);
575 82 prism_head_write_ctx_cleanup(&head);
576
577 82 out->first_posting = first_posting;
578 82 out->root_blk = root_blk;
579 82 out->nlevels = (uint8_t)flat->nlevels;
580 82 out->nlist = actual_nlist;
581 82 vs_free(flat);
582 82 return true;
583 }
584
585 bool
586 153 do_parallel_build(
587 Relation heap,
588 Relation index,
589 struct IndexInfo *index_info,
590 const PrismBuildConfig *config,
591 VsStorage *storage,
592 struct PrismBuildProgress *prog,
593 uint32_t *out_nlist,
594 uint8_t *out_tree_nlevels,
595 double *out_heap_tuples,
596 double *out_indtuples,
597 double *out_soar_dupes,
598 float **out_global_mean,
599 BlockNumber *out_first_posting)
600 {
601 153 int nworkers = index_info->ii_ParallelWorkers;
602
603 153 *out_nlist = 0;
604 153 *out_tree_nlevels = 0;
605
1/2
✓ Branch 0 taken 153 times.
✗ Branch 1 not taken.
153 if (out_first_posting)
606 153 *out_first_posting = InvalidBlockNumber;
607
1/2
✓ Branch 0 taken 153 times.
✗ Branch 1 not taken.
153 if (out_global_mean)
608 153 *out_global_mean = NULL;
609
610 47 PrismPBuildLeader lead;
611
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 153 times.
153 if (!prism_pbuild_setup_shared(&lead, heap, index, config, nworkers))
612 ✗ return false;
613
614 153 ParallelContext *pcxt = lead.pcxt;
615 153 PrismBuildShared *shared = lead.shared;
616 153 Barrier *barrier = lead.barrier;
617 153 PrismDsmSamples *dsm_samples = lead.dsm_samples;
618 153 char *centroids_base = lead.centroids_base;
619 153 float *cents = lead.cents;
620 153 char *km_workers_base = lead.km_workers_base;
621 153 PrismDsmRootAssign *dsm_ra = lead.dsm_ra;
622 153 WalUsage *walusage = lead.walusage;
623 153 BufferUsage *bufferusage = lead.bufferusage;
624 153 int nparticipants = lead.nparticipants;
625 153 uint32_t km_k = lead.km_k;
626 153 Dimension dim = lead.dim;
627 153 uint32_t nlist = lead.nlist;
628 153 uint64_t rabitq_seed = lead.rabitq_seed;
629 153 uint32_t fan_out = lead.fan_out;
630
631 /*
632 * Introspection: name the dataset-scaling allocations up front (always
633 * logged, regardless of the GUC) so an OOM in any of them is
634 * pre-explained, and record the committed DSM size so the per-phase memory
635 * lines can add it. nlist here is the worst-case upper bound (the tree is
636 * not built yet).
637 */
638 153 prism_build_report_dsm_bytes(prog, (uint64_t)lead.dsm_total);
639 153 prism_build_report_planned_alloc(
640 prog,
641 153 (uint64_t)prism_dsm_samples_size(
642 nparticipants, lead.max_per_worker, dim),
643 /* The tree is streamed to pages from a bounded ring of subtree
644 * slots (part of dsm_total); it is never held whole in memory. */
645 0,
646 153 (uint64_t)lead.dsm_total);
647
648 47 instr_time t_launch_start;
649 153 INSTR_TIME_SET_CURRENT(t_launch_start);
650
651 /*
652 * The leader participates in every phase, so it joins the dynamic barrier
653 * as a party (workers attach the same way as they start). Attaching before
654 * launching workers guarantees the leader is counted before any worker can
655 * arrive, so the barrier never advances a phase without it.
656 */
657 153 BarrierAttach(barrier);
658
659 /* ---- Launch workers + wait until they've all attached ---- */
660
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 152 times.
153 if (!prism_pbuild_launch(pcxt, barrier, shared))
661 {
662 /* Teardown already ran; hand the sample segment back too so the
663 * serial fallback starts from a clean budget. */
664 1 prism_pbuild_samples_release(dsm_samples, lead.sample_seg);
665 1 return false;
666 }
667
668 /* The launch may have narrowed the participant count to the party that
669 * actually attached; partition the phases below over that count. */
670 152 nparticipants = shared->nparticipants;
671
672 /* ==== Leader participates in all phases as worker_id=0 ==== */
673
674 /* ---- Phase 1: sampling (leader runs the worker body as participant 0)
675 * ---- */
676 152 prism_build_report_phase(prog, PRISM_BUILD_PHASE_SAMPLE);
677 152 prism_pbuild_exec_sampling(
678 0, heap, index, index_info, shared, dsm_samples, barrier);
679
680 46 instr_time t_sample_end;
681 152 INSTR_TIME_SET_CURRENT(t_sample_end);
682 152 INSTR_TIME_SUBTRACT(t_sample_end, t_launch_start);
683
2/3
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 46 times.
152 vs_debug(
684 "prism: phase 1 (sampling) %.1fms",
685 INSTR_TIME_GET_MILLISEC(t_sample_end));
686
687 46 instr_time t_km_start;
688 152 INSTR_TIME_SET_CURRENT(t_km_start);
689
690 /* ---- Phase 2: root k-means. The leader runs the worker body as
691 * participant 0; inside it additionally seeds the initial centroids and
692 * reduces the per-iteration accumulators (gated on participant 0). ---- */
693 152 prism_build_report_phase(prog, PRISM_BUILD_PHASE_KMEANS);
694 152 uint32_t km_iters = prism_pbuild_exec_kmeans(
695 0, shared, dsm_samples, centroids_base, km_workers_base, barrier);
696
697 {
698 46 instr_time t_km_elapsed;
699 152 INSTR_TIME_SET_CURRENT(t_km_elapsed);
700 152 INSTR_TIME_SUBTRACT(t_km_elapsed, t_km_start);
701
2/3
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 46 times.
152 vs_debug(
702 "prism: root kmeans %.1fms (%u iters, k=%u)",
703 INSTR_TIME_GET_MILLISEC(t_km_elapsed),
704 km_iters,
705 km_k);
706 }
707
708 /*
709 * Compute nlevels to decide flat vs hierarchical assembly. For
710 * nlevels == 1 (flat) the root k-means already produced every leaf, so
711 * the tree is built from the centroids directly. For nlevels >= 2 each
712 * participant builds the full subtree — to whatever depth nlist/fan_out
713 * needs — for the root children it owns, and the leader streams each to
714 * centroid pages a batch at a time (no in-RAM whole-tree assembly).
715 */
716 152 uint32_t nlevels = vs_hkmeans_nlevels(nlist, fan_out);
717
718 /* ---- Phase 2b: root assignment (leader as participant 0). ---- */
719 152 prism_pbuild_exec_root_assign(
720 0, shared, dsm_samples, dsm_ra, centroids_base, barrier);
721
722 /* ---- Batched streaming tree build --------------------------------------
723 * Workers build per-root-child subtrees into a bounded ring of slots; the
724 * leader records each batch's layout counts, keeps the blobs in a
725 * spillable store, and streams them to centroid pages. Peak subtree DSM is
726 * nparticipants slots, independent of nlist.
727 * ------------------------------ */
728 152 prism_build_report_phase(prog, PRISM_BUILD_PHASE_SETUP);
729 152 RaBitQParams *rq_params = vs_rabitq_create(dim, rabitq_seed);
730 152 PrismCentroidFormat fmt = shared->centroid_format;
731 152 uint32_t max_ent = prism_centroid_max_entries_fmt(dim, fmt);
732
733 /*
734 * global_mean = mean of the LEAF centroids (the encoder centering) -- an
735 * unweighted per-cluster mean, not the per-vector sample mean. The
736 * quantization quality of every centroid and posting code depends on this
737 * anchor. Pages are written only after the PLAN pass has built every
738 * subtree, so
739 * the leaf-centroid sum is accumulated there (plan_batch_cb) and the mean
740 * is ready before any page is encoded. Filled per branch below.
741 */
742 152 const size_t vec_nbytes = (size_t)dim * sizeof(float);
743 152 float *global_mean = vs_alloc(vec_nbytes);
744
745
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 45 times.
152 BlockNumber first_centroid = prism_first_centroid_blkno(dim);
746 152 BlockNumber first_posting = 0;
747 152 BlockNumber root_blk = InvalidBlockNumber;
748
749 /* Exact internal-centroid collection for the phase-2.5/3 build
750 * descent (see PrismExactCentroidCollector in index_build.h). */
751 152 PrismExactCentroidCollector exact_centroids = {0};
752
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 26 times.
152 PrismExactCentroidCollector *collector =
753 132 prism_exact_centroid_enabled(nlevels, fmt) ? &exact_centroids
754
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 62 times.
106 : NULL;
755
756 46 TreeLayout layout;
757 46 bool tree_ok;
758
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 82 times.
152 if (nlevels >= 2)
759 70 tree_ok = build_routing_tree_batched(
760 shared,
761 storage,
762 prog,
763 dsm_samples,
764 dsm_ra,
765 cents,
766 km_k,
767 nlist,
768 fan_out,
769 barrier,
770 rq_params,
771 max_ent,
772 first_centroid,
773 global_mean,
774 collector,
775 &layout);
776 else
777 82 tree_ok = build_routing_tree_flat(
778 shared,
779 storage,
780 prog,
781 cents,
782 km_k,
783 fan_out,
784 rq_params,
785 max_ent,
786 first_centroid,
787 global_mean,
788 &layout);
789
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 106 times.
✓ Branch 2 taken 26 times.
152 if (!tree_ok)
790 {
791 ✗ if (collector != NULL)
792 ✗ prism_exact_centroid_collector_cleanup(collector);
793 ✗ vs_free(global_mean);
794 ✗ prism_pbuild_samples_release(dsm_samples, lead.sample_seg);
795 ✗ WaitForParallelWorkersToFinish(pcxt);
796 ✗ prism_pbuild_teardown(pcxt);
797 ✗ return false;
798 }
799 151 nlist = layout.nlist;
800 151 first_posting = layout.first_posting;
801 151 root_blk = layout.root_blk;
802 151 const uint8_t out_nlevels = layout.nlevels;
803
804 /* Publish the exact internal-node centroids the tree write collected,
805 * for the workers' phase-2.5/3 build descent (exact-centroid seam; must
806 * precede the tree-ready barrier). Without a collector the collection
807 * is an empty header and the workers' scoring hook stays inert. */
808 151 void *exact_seg = NULL;
809 151 char *exact_cents = prism_pbuild_exact_centroids_create(
810 shared,
811 prism_exact_centroid_collection_size(collector),
812 &exact_seg);
813 151 prism_exact_centroid_collection_write(collector, exact_cents);
814
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 88 times.
151 if (collector != NULL)
815 63 prism_exact_centroid_collector_cleanup(collector);
816
817 /* Publish the routing state the workers read in phase 3: nlist, the tree
818 * root block + depth, the posting-head base (leaf c's head = first_posting
819 * + c), the global mean, and the page store. */
820 151 shared->nlist = nlist;
821 151 shared->first_centroid = root_blk;
822 151 shared->nlevels = out_nlevels;
823 151 shared->first_posting = first_posting;
824
1/2
✓ Branch 0 taken 151 times.
✗ Branch 1 not taken.
151 if (out_first_posting)
825 151 *out_first_posting = first_posting;
826 {
827 45 float *dsm_gmean =
828 151 shm_toc_lookup(pcxt->toc, PRISM_DSM_KEY_GLOBAL_MEAN, false);
829 151 memcpy(dsm_gmean, global_mean, vec_nbytes);
830 }
831 151 prism_pbuild_publish_storage(shared, storage);
832
833
1/2
✓ Branch 0 taken 151 times.
✗ Branch 1 not taken.
151 if (out_global_mean)
834 151 *out_global_mean = global_mean; /* caller owns it (metadata write) */
835 else
836 ✗ vs_free(global_mean);
837
838 /* No in-RAM tree exists; the caller's metadata write needs only the
839 * shape. */
840 151 *out_nlist = nlist;
841 151 *out_tree_nlevels = out_nlevels;
842
843 /* The refine decision, now that the actual leaf count is known: refine
844 * only when the sample was bounded below the table AND the leaves are
845 * sample-thin -- a leaf's encode reference is a sample mean whose error
846 * shrinks with its sample count, so past the threshold the full-table
847 * scan recomputes what the sample already got right. Published before
848 * the ready barrier; workers gate the refine phase (and its barriers)
849 * on it after that barrier. */
850 {
851 151 uint64_t collected = 0;
852 151 uint64_t seen = 0;
853
2/2
✓ Branch 0 taken 381 times.
✓ Branch 1 taken 151 times.
532 for (int t = 0; t < nparticipants; t++)
854 {
855 381 collected += prism_dsm_sample_counts(dsm_samples)[t];
856 381 seen += prism_dsm_sample_seen(dsm_samples)[t];
857 }
858 /* kept < seen means the sampling scans skipped real rows, so the
859 * sample is a strict subset of the table (kept == seen means the
860 * sample IS the table -- nothing to refine from). */
861
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
3 shared->refine = shared->refine_threshold > 0 && collected < seen &&
862
4/6
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 148 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
154 shared->refine_tile_cap > 0 && nlist > 0 &&
863
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
3 collected / nlist <
864
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
45 (uint64_t)shared->refine_threshold;
865
3/5
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 45 times.
✓ Branch 3 taken 106 times.
✗ Branch 4 not taken.
151 vs_debug(
866 "prism: refine gate: kept=%" PRIu64 " seen=%" PRIu64
867 " nlist=%u threshold=%u -> %s",
868 collected,
869 seen,
870 nlist,
871 shared->refine_threshold,
872 shared->refine ? "refine" : "skip");
873 }
874
875 /* The samples are dead (their last readers were the subtree builders);
876 * lay the refine accumulator over them before the ready barrier so the
877 * workers -- who pass that barrier ahead of the refine phase -- see an
878 * initialized header. */
879 151 PrismDsmRefineAccum *refine_accum = NULL;
880
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 149 times.
151 if (shared->refine)
881 {
882 2 refine_accum = prism_pbuild_refine_overlay(dsm_samples);
883 2 refine_accum->nleaves = shared->refine_tile_cap;
884 2 refine_accum->dim = dim;
885 }
886
887 /* Initialize the shared cluster sorter for the launched-worker count
888 * BEFORE the ready barrier, so it is ready when workers attach in phase 3.
889 * The leader merges only (it does not sort a share). */
890 45 void *sortshared =
891 151 shm_toc_lookup(pcxt->toc, PRISM_DSM_KEY_SORTSHARED, false);
892 151 prism_pbuild_sort_shared_init(
893 151 sortshared, pcxt->nworkers_launched, pcxt->seg);
894
895 /* Barrier: centroid/head pages written + routing state published + sorter
896 * ready; workers build their page-backed router next. */
897 151 BarrierArriveAndWait(barrier, WAIT_EVENT_PARALLEL_CREATE_INDEX_SCAN);
898
899 /* ---- Phase 2.5: page-backed full-table refine (only when subsampled)
900 * ---- The workers route + accumulate; the leader (participant 0) clears
901 * the tiled accumulator, resets the scan per tile, and rewrites each
902 * leaf's head-page pt_centroid to the full-table mean. Gated on
903 * shared->refine, matching the workers, so the internal barriers stay
904 * in lockstep. */
905
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 149 times.
151 if (shared->refine)
906 {
907 2 prism_build_report_phase(prog, PRISM_BUILD_PHASE_REFINE);
908 2 PrismDsmRefineAccum *accum = refine_accum;
909 2 PrismHeadWriteCtx rhead;
910 2 prism_head_write_ctx_init(
911 &rhead,
912 storage,
913 rq_params,
914 dim,
915 2 shared->fastscan,
916 first_posting);
917 2 prism_pbuild_exec_refine_paged(
918 0,
919 heap,
920 index,
921 index_info,
922 shared,
923 NULL,
924 first_posting,
925 accum,
926 barrier,
927 prism_write_leaf_head,
928 &rhead);
929 2 prism_head_write_ctx_cleanup(&rhead);
930 }
931
932 /* Phase 3: workers scan + route page-backed + encode + sort; the leader
933 * merges. Reported exactly once -- the seam fires the "prism-build-load"
934 * test hook, and a 'wait' attached there must pause the build a single
935 * time -- and before the scan-reset barrier below releases the workers,
936 * so progress reflects the whole (multi-hour at scale) scan. */
937 151 prism_build_report_phase(prog, PRISM_BUILD_PHASE_SCAN_PARALLEL);
938
939 /* The samples (and the refine overlay riding in them) are dead; hand the
940 * segment back before the posting sort claims its own memory budget. */
941 151 prism_pbuild_samples_release(dsm_samples, lead.sample_seg);
942 151 dsm_samples = NULL;
943
944 /* Re-init the scan for the posting phase (the refine passes above consumed
945 * it). Guarded by the barrier below so no worker scans before the reset.
946 */
947 151 prism_pbuild_rescan(heap, shared);
948
949 /* Barrier: scan reset for the posting phase; workers start the page-backed
950 * posting scan+sort. */
951 151 BarrierArriveAndWait(barrier, WAIT_EVENT_PARALLEL_CREATE_INDEX_SCAN);
952
953 45 instr_time t_scan_start;
954 151 INSTR_TIME_SET_CURRENT(t_scan_start);
955
956 /* Barrier: wait until every worker has finished sorting its run, then
957 * merge and build. The leader does not scan; the workers cover the heap.
958 */
959 151 BarrierArriveAndWait(barrier, WAIT_EVENT_PARALLEL_CREATE_INDEX_SCAN);
960 151 BarrierDetach(barrier);
961
962 151 WaitForParallelWorkersToFinish(pcxt);
963
964 45 instr_time t_scan_end;
965 151 INSTR_TIME_SET_CURRENT(t_scan_end);
966 151 INSTR_TIME_SUBTRACT(t_scan_end, t_scan_start);
967
968
2/2
✓ Branch 0 taken 230 times.
✓ Branch 1 taken 151 times.
381 for (int i = 0; i < pcxt->nworkers_launched; i++)
969 88 InstrAccumParallelQuery(&bufferusage[i], &walusage[i]);
970
971 151 *out_heap_tuples = shared->reltuples;
972 151 *out_indtuples = shared->indtuples;
973 151 *out_soar_dupes = shared->soar_dupes;
974
975 /* The workers cover the heap cooperatively while the leader blocks on the
976 * scan barrier above, so there is no leader-side loop to advance the % mid
977 * scan; publish the final scanned count now that the workers have
978 * finished.
979 */
980 151 prism_build_report_progress(prog, shared->indtuples);
981
982 45 instr_time t_merge_start;
983 151 INSTR_TIME_SET_CURRENT(t_merge_start);
984
985 /*
986 * Merge the workers' sorted runs and build each cluster's posting list
987 * with a single resident page builder, in cluster order (same loop as the
988 * serial path). Entries arrive grouped by cluster, so there is no
989 * partial-page fold and no chain to splice.
990 */
991 151 prism_build_report_phase(prog, PRISM_BUILD_PHASE_POSTING);
992 347 PrismSorter *sorter = prism_pbuild_sort_begin(
993 sortshared,
994 151 pcxt->seg,
995 0,
996 pcxt->nworkers_launched,
997 true,
998 151 (uint32_t)prism_posting_entry_size(dim),
999 shared->work_mem_kb);
1000 151 prism_posting_build_lists(
1001 sorter,
1002 storage,
1003 nlist,
1004 dim,
1005 151 shared->fastscan,
1006 rq_params,
1007 first_posting);
1008
1009 151 uint32_t total_pages = RelationGetNumberOfBlocks(index) - first_posting;
1010
1011 45 instr_time t_merge_end;
1012 151 INSTR_TIME_SET_CURRENT(t_merge_end);
1013 151 INSTR_TIME_SUBTRACT(t_merge_end, t_merge_start);
1014
1015
2/3
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 45 times.
151 vs_debug(
1016 "prism: parallel streaming build with %d workers, "
1017 "%u clusters, %u pages, "
1018 "scan+drain %.1fms, finalize %.1fms",
1019 pcxt->nworkers_launched,
1020 nlist,
1021 total_pages,
1022 INSTR_TIME_GET_MILLISEC(t_scan_end),
1023 INSTR_TIME_GET_MILLISEC(t_merge_end));
1024
1025 /* Workers detached from the exact-centroid collection when routing ended;
1026 * the leader's release is the last and frees it. */
1027 151 prism_pbuild_exact_centroids_release(exact_seg);
1028
1029 151 prism_pbuild_teardown(pcxt);
1030
1031 151 return true;
1032 }
1033