GCC Code Coverage Report


Directory: src/
File: src/index/parallel_build.h
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 60 63 95.2%
Functions: 17 20 85.0%
Branches: 19 25 76.0%

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.h - Parallel index build (worker + leader shared decls)
6 *
7 * Phased parallel build, barrier-synchronized:
8 * Sampling: workers cooperatively scan the heap into a bounded,
9 * budget-sized sample region (a dedicated segment, released once
10 * clustering is done).
11 * Clustering: root k-means over the sample (leader reduces between
12 * iterations), then per-root-child subtrees in batched ring slots;
13 * the leader records each batch's layout and spills the subtree
14 * blobs, then streams every centroid + head page to disk by itself.
15 * Refine (when subsampled): workers route the full table page-backed
16 * and accumulate per-leaf means; the leader rewrites the heads.
17 * Posting: workers route + encode into a cluster-keyed shared sort;
18 * the leader merges runs and writes the posting lists.
19 */
20
21 #ifndef PRISM_PARALLEL_BUILD_H
22 #define PRISM_PARALLEL_BUILD_H
23
24 /*
25 * Back-end primitives the parallel build runs on. The standalone shims live in
26 * src/standalone/; a PostgreSQL build uses the real PG headers. This guard is
27 * the single place that switch is made — the standalone headers carry no PG
28 * branch of their own.
29 */
30 #ifdef VS_STANDALONE
31 #include "standalone/barrier.h"
32 #include "standalone/pg_compat.h" /* Size, BlockNumber, ItemPointerData, Relation */
33 #include "standalone/shm_toc.h"
34 #else
35 #include <postgres.h>
36
37 #include <storage/barrier.h>
38 #include <storage/block.h>
39 #include <storage/dsm.h>
40 #include <storage/itemptr.h>
41 #include <storage/shm_toc.h>
42 #include <utils/rel.h>
43 #endif
44
45 #include <inttypes.h>
46
47 #include "algo/hkmeans.h"
48 #include "core/log.h"
49 #include "core/memory.h"
50 #include "core/types.h"
51 #include "index/centroid_page.h" /* PrismCentroidFormat */
52 #include "index/posting_build.h"
53 #include "index/storage.h" /* VsStorage */
54 #include "quant/rabitq.h"
55
56 /* Forward decl so prism_build_scan's prototype can reference it without
57 * pulling in the executor headers; callers that pass one already have the full
58 * type.
59 */
60 struct IndexInfo;
61
62 /*
63 * Per-vector build scan callback (back-end-neutral): the PG scan adapter
64 * unwraps each heap tuple's Datum to the vector's data pointer, and the
65 * standalone work-stealing scan points straight into its vector array. The tid
66 * is the real heap TID under PG and a reversibly-synthesized one in
67 * standalone.
68 */
69 typedef void (*PrismBuildScanCb)(
70 void *state, ItemPointerData tid, const float *vec);
71
72 /* ----------------------------------------------------------------
73 * shm_toc region keys (the toc is a DSM segment in PG, a heap arena in
74 * standalone). A few regions are PG-only (WAL/buffer usage, query text) but
75 * their keys live here with the rest for one contiguous numbering.
76 * ---------------------------------------------------------------- */
77
78 #define PRISM_DSM_KEY_SHARED UINT64CONST(0xB000000000000001)
79 #define PRISM_DSM_KEY_WAL_USAGE UINT64CONST(0xB000000000000006)
80 #define PRISM_DSM_KEY_BUFFER_USAGE UINT64CONST(0xB000000000000007)
81 #define PRISM_DSM_KEY_QUERY_TEXT UINT64CONST(0xB000000000000008)
82 #define PRISM_DSM_KEY_BARRIER UINT64CONST(0xB000000000000009)
83 #define PRISM_DSM_KEY_SAMPLES UINT64CONST(0xB00000000000000A)
84 #define PRISM_DSM_KEY_CENTROIDS UINT64CONST(0xB00000000000000B)
85 #define PRISM_DSM_KEY_KM_WORKERS UINT64CONST(0xB00000000000000C)
86 #define PRISM_DSM_KEY_ROOT_ASSIGN UINT64CONST(0xB00000000000000E)
87 #define PRISM_DSM_KEY_SORTSHARED UINT64CONST(0xB000000000000012)
88 /* Page-backed phase-3 routing: the global mean, published by the leader before
89 * the tree-ready barrier so workers route exactly as the query/insert paths
90 * do. The posting-head base (see prism_leaf_head_blkno) is a scalar in
91 * PrismBuildShared, not a shared array. */
92 #define PRISM_DSM_KEY_GLOBAL_MEAN UINT64CONST(0xB000000000000014)
93
94 /* ----------------------------------------------------------------
95 * PrismBuildShared — back-end-neutral shared build state
96 *
97 * Immutable config set by the leader before the workers start, plus counters
98 * the workers update concurrently during the posting scan under a lock the
99 * back-end owns (prism_pbuild_worker_add_counts). Each back-end embeds this as
100 * the first member of its own struct carrying the back-end-specific state —
101 * for PG, the relation OIDs, query id, the spinlock, and a trailing
102 * ParallelTableScanDesc (see PrismBuildSharedPg in parallel_backend.c).
103 * ---------------------------------------------------------------- */
104
105 typedef struct PrismBuildShared
106 {
107 /* Immutable — set by the leader before launch */
108 Dimension dim;
109 DistanceMetric metric;
110 uint32_t nlist;
111 uint32_t fan_out;
112 double soar_lambda;
113 double boundary_epsilon;
114 bool fastscan;
115 PrismCentroidFormat centroid_format;
116 uint64_t rabitq_seed;
117 /* Planned as 1 + planned workers (it sizes the per-participant DSM
118 * regions), then narrowed by prism_pbuild_launch to 1 + the workers that
119 * actually started when the launch falls short. Work partitioned by
120 * participant must use this count; region sizing keeps the planned
121 * value and leaves the tail slots unused. */
122 int nparticipants;
123 /* CREATE INDEX CONCURRENTLY: the leader scans with an MVCC snapshot and
124 * participants take weak relation locks. Workers must mark their rebuilt
125 * IndexInfo concurrent too, or heapam's snapshot/OldestXmin check trips.
126 */
127 bool concurrent;
128 /* Posting sort work budget (KB); PG sets it from maintenance_work_mem,
129 * standalone leaves it 0 (its in-memory sorter ignores it). The shared
130 * phase-3 code reads this instead of the PG-only GUC. */
131 int work_mem_kb;
132
133 /* K-means config */
134 uint32_t max_samples_per_worker;
135 uint32_t km_max_iterations;
136 float km_tolerance;
137 uint32_t km_k; /* root k-means k (= fan_out) */
138
139 /* Refine gate input, set at setup: the sample-per-leaf threshold below
140 * which a subsampled build refines the leaf encode references on the
141 * full table (0 = refinement off; standalone leaves it 0). Whether the
142 * build IS subsampled is decided empirically from the sampling pass:
143 * each participant counts the live rows its scan saw next to the rows
144 * it kept, and kept < seen means the sample excludes real rows. */
145 uint32_t refine_threshold;
146
147 /* The refine decision. The LEADER makes it after clustering -- the
148 * actual leaf count is only known then, and dividing the collected
149 * samples by the worst-case leaf bound would understate samples-per-leaf
150 * and refine too eagerly -- and publishes it before the tree-ready
151 * barrier. Workers read it after that barrier, so leader and workers
152 * gate the refine phase (and its barriers) identically. */
153 bool refine;
154
155 /* Tile capacity (leaves) of the refine accumulator that overlays the
156 * sample region once sampling is done; sized at setup
157 * (the back-end bounds it by its memory budget AND the sample region's
158 * size, since the overlay lives inside that region). */
159 uint32_t refine_tile_cap;
160
161 /* Counters — updated concurrently under the back-end's lock */
162 double reltuples;
163 double indtuples;
164 double soar_dupes;
165
166 /* K-means convergence — set by leader between barriers */
167 bool km_converged;
168
169 /* Per-child subtree blob slot size (bytes) in the child-subtrees region;
170 * set by the leader before launch so workers can index their slot. */
171 /* Written by the leader after root assignment (see the subtree-ring
172 * seam); workers read it after the ring barrier. */
173 uint64_t subtree_slot_size;
174
175 /* Page-backed routing knobs (mirror the prism.centroid_* GUCs), so
176 * phase-3 workers build a PrismIndexBase that routes identically to
177 * the query path. fastscan_bits is the FASTSCAN centroid bit width
178 * (base.fastscan when the centroid format is FASTSCAN; 0 otherwise). */
179 float centroid_error_scale;
180 float centroid_beam_scale;
181 int fastscan_bits;
182
183 /* Published by the leader after the streaming tree write: the
184 * centroid-tree root block (workers' phase-3
185 * PrismIndexBase.first_centroid) and the tree depth (base.nlevels). The
186 * tree itself lives only on pages.
187 */
188 BlockNumber first_centroid;
189 uint8_t nlevels;
190
191 /* Published by the leader before phase 3: the first posting-head block.
192 * Cluster c's head is formula-derived (prism_leaf_head_blkno), so workers
193 * map a routed head block back to its leaf arithmetically
194 * (prism_route_head_to_leaf) — no O(nlist) head array. */
195 BlockNumber first_posting;
196 } PrismBuildShared;
197
198 /* ----------------------------------------------------------------
199 * K-means sampling: per-worker sample slots in DSM
200 *
201 * Layout: [sample_counts[nparticipants]] [rows_seen[nparticipants]] then
202 * [samples[worker_id][max_per_worker * dim]] packed.
203 * ---------------------------------------------------------------- */
204
205 typedef struct PrismDsmSamples
206 {
207 uint32_t nparticipants;
208 uint32_t max_per_worker;
209 Dimension dim;
210 /* counts[nparticipants] (rows kept), then MAXALIGN'd
211 * seen[nparticipants] (live rows the sampling scan visited; kept < seen
212 * means the sample is a strict subset of the table -- 64-bit, since a
213 * participant's scan share is unbounded and a wrapped counter would
214 * silently flip the refine gate), then the per-worker sample blocks
215 * (samples[worker][max_per_worker * dim]) packed right after. */
216 uint32_t counts[];
217 } PrismDsmSamples;
218
219 static inline uint32_t *
220 5894 prism_dsm_sample_counts(PrismDsmSamples *s)
221 {
222
4/4
✓ Branch 0 taken 776 times.
✓ Branch 1 taken 569 times.
✓ Branch 2 taken 46 times.
✓ Branch 3 taken 90 times.
5758 return s->counts;
223 }
224
225 static inline uint64_t *
226 3078 prism_dsm_sample_seen(PrismDsmSamples *s)
227 {
228 1991 return (uint64_t *)MAXALIGN(s->counts + s->nparticipants);
229 }
230
231 static inline float *
232 2313 prism_dsm_worker_samples(PrismDsmSamples *s, int worker_id)
233 {
234 /* The sample blocks begin after counts[] and seen[]. */
235 2313 float *samples = (float *)(prism_dsm_sample_seen(s) + s->nparticipants);
236 2313 return samples + (size_t)worker_id * s->max_per_worker * s->dim;
237 }
238
239 static inline Size
240 412 prism_dsm_samples_size(
241 int nparticipants, uint32_t max_per_worker, Dimension dim)
242 {
243 412 Size sz = offsetof(PrismDsmSamples, counts);
244 412 sz += (Size)nparticipants * sizeof(uint32_t);
245 412 sz = MAXALIGN(sz);
246 412 sz += (Size)nparticipants * sizeof(uint64_t);
247 412 sz += (Size)nparticipants * max_per_worker * dim * sizeof(float);
248
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 47 times.
412 return sz;
249 }
250
251 /* ----------------------------------------------------------------
252 * Root assignments: per-worker uint32_t[max_per_worker] in DSM
253 *
254 * After root k-means converges, each worker stores its root
255 * assignments here. Used to filter samples during child k-means.
256 * ---------------------------------------------------------------- */
257
258 typedef struct PrismDsmRootAssign
259 {
260 uint32_t nparticipants;
261 uint32_t max_per_worker;
262 /* assignments[worker][max_per_worker] packed contiguously. */
263 uint32_t assignments[];
264 } PrismDsmRootAssign;
265
266 static inline uint32_t *
267 2076 prism_dsm_root_assignments(PrismDsmRootAssign *ra, int worker_id)
268 {
269 2076 return ra->assignments + (size_t)worker_id * ra->max_per_worker;
270 }
271
272 static inline Size
273 306 prism_dsm_root_assign_size(int nparticipants, uint32_t max_per_worker)
274 {
275 306 Size sz = offsetof(PrismDsmRootAssign, assignments);
276 306 sz += (Size)nparticipants * max_per_worker * sizeof(uint32_t);
277 306 return sz;
278 }
279
280 /* ----------------------------------------------------------------
281 * K-means shared centroids in DSM
282 *
283 * centroids[nlist * dim] + norms_c[nlist]
284 * Written by leader between barriers, read by workers during
285 * assignment.
286 * ---------------------------------------------------------------- */
287
288 static inline Size
289 259 prism_dsm_centroids_size(uint32_t nlist, Dimension dim)
290 {
291 259 return (Size)nlist * dim * sizeof(float) + (Size)nlist * sizeof(float);
292 }
293
294 static inline float *
295 1240 prism_dsm_centroids(char *base)
296 {
297 1240 return (float *)base;
298 }
299
300 /* ----------------------------------------------------------------
301 * Child subtrees: per-root-child HKMeansResult blobs in DSM
302 *
303 * After the root k-means splits the samples into fan_out groups, each group's
304 * subtree is built independently and written, as a contiguous HKMeansResult,
305 * into a fixed-size slot. The batched streaming build keeps only a bounded
306 * ring of nparticipants slots resident (each participant owns slot
307 * participant_id; the leader streams each batch to pages before the next batch
308 * reuses the ring), so the region is O(nparticipants * slot_size), independent
309 * of the partition count. The leader sizes the slot only after root
310 * assignment -- a subtree can never hold more leaves than its child's
311 * samples, which caps the slot far below the analytic worst case -- and
312 * creates the ring as its own segment then (the subtree-ring seam below);
313 * the slot size travels in PrismBuildShared.subtree_slot_size.
314 * ---------------------------------------------------------------- */
315
316 static inline Size
317 70 prism_dsm_child_subtrees_size(uint32_t nslots, uint64_t slot_size)
318 {
319 70 return (Size)nslots * (Size)slot_size;
320 }
321
322 static inline char *
323 516 prism_dsm_child_subtree(char *base, uint32_t slot, uint64_t slot_size)
324 {
325 516 return base + (Size)slot * (Size)slot_size;
326 }
327
328 /*
329 * Worst-case leaf count for a tree targeting `nlist` leaves at this fan_out:
330 * fan_out^nlevels (clamped to >= nlist). The exact leaf count isn't known
331 * until k-means runs, so the parallel build uses this to size its DSM regions
332 * up front, then narrows to the real tree->nleaves afterward.
333 *
334 * Accumulating in 64 bits keeps a product past UINT32_MAX an error rather
335 * than a truncation: every DSM region is sized from this, so a wrapped count
336 * describes a smaller tree than the one being built. The reloption bounds
337 * keep the product under 2^32 today, which is what makes the ceiling a
338 * guard on those bounds rather than a limit callers meet.
339 */
340 static inline uint32_t
341 163 prism_max_nlist(uint32_t nlist, uint32_t fan_out)
342 {
343 163 uint32_t nlevels = vs_hkmeans_nlevels(nlist, fan_out);
344 163 uint64_t max_nlist = 1;
345
3/3
✓ Branch 0 taken 230 times.
✓ Branch 1 taken 190 times.
✓ Branch 2 taken 47 times.
467 for (uint32_t l = 0; l < nlevels; l++)
346 {
347 304 max_nlist *= fan_out;
348
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 304 times.
304 if (max_nlist > UINT32_MAX)
349
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
74 vs_error(
350 "prism: %u levels at fan_out %u reach %" PRIu64
351 " leaves, past the largest addressable count "
352 "(nlist %u); decrease fan_out or nlist",
353 nlevels,
354 fan_out,
355 max_nlist,
356 nlist);
357 }
358
1/2
✓ Branch 0 taken 163 times.
✗ Branch 1 not taken.
163 return max_nlist < nlist ? nlist : (uint32_t)max_nlist;
359 }
360
361 static inline float *
362 768 prism_dsm_norms_c(char *base, uint32_t nlist, Dimension dim)
363 {
364 /* norms_c[nlist] sits right after centroids[nlist * dim]. */
365
2/2
✓ Branch 1 taken 46 times.
✓ Branch 2 taken 90 times.
768 return prism_dsm_centroids(base) + (size_t)nlist * dim;
366 }
367
368 /* ----------------------------------------------------------------
369 * K-means per-worker accumulators in DSM
370 *
371 * Per worker: centroid_sums[nlist * dim] + centroid_cnts[nlist]
372 * + cost (1 float)
373 * ---------------------------------------------------------------- */
374
375 static inline Size
376 4071 prism_dsm_km_worker_size(uint32_t nlist, Dimension dim)
377 {
378 4071 return (Size)nlist * dim * sizeof(float) + (Size)nlist * sizeof(uint32_t) +
379 sizeof(float);
380 }
381
382 static inline Size
383 643 prism_dsm_km_workers_size(int nparticipants, uint32_t nlist, Dimension dim)
384 {
385 690 return (Size)nparticipants * prism_dsm_km_worker_size(nlist, dim);
386 }
387
388 static inline float *
389 5220 prism_dsm_km_worker_sums(
390 char *base, uint32_t nlist, Dimension dim, int worker_id)
391 {
392 8648 return (float *)(base +
393
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 90 times.
3700 (size_t)worker_id * prism_dsm_km_worker_size(nlist, dim));
394 }
395
396 static inline uint32_t *
397 4724 prism_dsm_km_worker_cnts(
398 char *base, uint32_t nlist, Dimension dim, int worker_id)
399 {
400 /* cnts[nlist] sits right after sums[nlist * dim]. */
401
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 90 times.
3204 return (uint32_t *)(prism_dsm_km_worker_sums(base, nlist, dim, worker_id) +
402 2932 (size_t)nlist * dim);
403 }
404
405 static inline float *
406 4092 prism_dsm_km_worker_cost(
407 char *base, uint32_t nlist, Dimension dim, int worker_id)
408 {
409 /* cost sits right after cnts[nlist]. */
410
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 90 times.
4092 return (float *)(prism_dsm_km_worker_cnts(base, nlist, dim, worker_id) +
411 nlist);
412 }
413
414 /* ----------------------------------------------------------------
415 * Per-worker posting output in DSM
416 *
417 * active[nlist] per worker, packed contiguously: a flag per cluster marking
418 * which lists this worker wrote into.
419 * ---------------------------------------------------------------- */
420
421 static inline Size
422 prism_dsm_worker_output_size(uint32_t nlist, int nparticipants)
423 {
424 return (Size)nparticipants * nlist * sizeof(bool);
425 }
426
427 static inline bool *
428 prism_dsm_worker_active(char *base, uint32_t nlist, int worker_id)
429 {
430 return (bool *)(base + (Size)worker_id * nlist * sizeof(bool));
431 }
432
433 /* ----------------------------------------------------------------
434 * Shared callbacks — used by both leader and workers
435 * ---------------------------------------------------------------- */
436
437 typedef struct SampleCbState
438 {
439 float *samples;
440 uint32_t count;
441 uint64_t seen;
442 uint32_t max_samples;
443 uint32_t stride;
444 uint32_t stride_counter;
445 Dimension dim;
446 DistanceMetric metric;
447 } SampleCbState;
448
449 /*
450 * Shared sampling logic, called per live tuple with a raw vector pointer (no
451 * Datum) so the same code serves both back-ends. prism_build_scan feeds it:
452 * the PG scan unwraps each heap tuple's Datum, the standalone scan passes its
453 * in-memory vectors directly.
454 */
455 extern void
456 prism_sample_cb(void *state, ItemPointerData tid, const float *vec);
457
458 extern void prism_km_assign_and_accumulate(
459 const float *samples,
460 uint32_t nsamples,
461 const float *centroids,
462 const float *norms_c,
463 uint32_t nlist,
464 Dimension dim,
465 DistanceMetric metric,
466 float *out_sums,
467 uint32_t *out_cnts,
468 float *out_cost);
469
470 /*
471 * Build ONE root-child's subtree into `slot`. Used by the batched streaming
472 * build, where each participant builds one child per batch into a ring slot
473 * indexed by participant (so only nparticipants subtrees are resident) and the
474 * leader streams each to pages.
475 */
476 extern void prism_build_child_subtree(
477 uint32_t child,
478 uint32_t child_count,
479 int nparticipants,
480 PrismDsmSamples *dsm_samples,
481 PrismDsmRootAssign *dsm_ra,
482 const float *root_cents,
483 uint32_t nlist,
484 uint32_t fan_out,
485 Dimension dim,
486 DistanceMetric metric,
487 uint32_t km_max_iterations,
488 char *slot,
489 uint64_t slot_size);
490
491 /*
492 * Per-batch leader callback for the batched subtree stream. Fired only on the
493 * leader (participant 0), between the two per-batch barriers, so it can read
494 * the batch's finished subtrees from the slots [0, batch_size) before they are
495 * reused. children[s] is the child id whose subtree sits in slot s (the batch
496 * schedule is largest-first, not sequential).
497 */
498 typedef void (*PrismBatchCb)(
499 void *arg,
500 const uint32_t *children,
501 uint32_t batch_size,
502 char *subtrees_base,
503 uint64_t slot_size);
504
505 /*
506 * Batched subtree build shared by the leader (participant 0) and workers:
507 * in ceil(km_k / nparticipants) batches, each participant clusters one root
508 * child's subtree into its ring slot, then (leader only) batch_cb consumes
509 * the batch -- recording its layout and spilling the blobs for the
510 * leader-only streaming write that follows; two barriers per batch keep all
511 * participants in lockstep. Children are scheduled largest-first (LPT, by
512 * root-assigned sample count with an id tie-break): every batch runs at the
513 * pace of its slowest subtree, so the skewed children go into the full
514 * batches and the tail batch gets the small ones. The schedule derives from
515 * shared state, so every participant computes it identically with no
516 * coordination; out_child_order (leader passes a km_k buffer, workers NULL)
517 * returns it so the blob replay can place each subtree at its child's
518 * reserved range. Called identically by leader and workers (workers pass
519 * batch_cb = NULL), so the barrier sequence matches by construction; one
520 * invocation per build.
521 */
522 extern void prism_pbuild_stream_subtrees(
523 int participant_id,
524 int nparticipants,
525 PrismDsmSamples *dsm_samples,
526 PrismDsmRootAssign *dsm_ra,
527 const float *root_cents,
528 uint32_t km_k,
529 uint32_t nlist,
530 uint32_t fan_out,
531 Dimension dim,
532 DistanceMetric metric,
533 uint32_t km_max_iterations,
534 char *subtrees_base,
535 uint64_t slot_size,
536 Barrier *barrier,
537 PrismBatchCb batch_cb,
538 void *cb_arg,
539 uint32_t *out_child_order);
540
541 /*
542 * Per-participant execution of phases 1, 2, and 2b, shared by the leader
543 * (participant 0) and the workers — see the contract on the definitions in
544 * parallel_build_worker.c. Each runs its phase's per-participant work and the
545 * phase barrier(s); the leader-only seed/reduce in the k-means phase is gated
546 * on participant_id == 0. prism_pbuild_exec_kmeans returns the iteration count
547 * (for the leader's timing log).
548 */
549 extern void prism_pbuild_exec_sampling(
550 int participant_id,
551 Relation heap,
552 Relation index,
553 struct IndexInfo *index_info,
554 PrismBuildShared *shared,
555 PrismDsmSamples *dsm_samples,
556 Barrier *barrier);
557
558 extern uint32_t prism_pbuild_exec_kmeans(
559 int participant_id,
560 PrismBuildShared *shared,
561 PrismDsmSamples *dsm_samples,
562 char *centroids_base,
563 char *km_workers_base,
564 Barrier *barrier);
565
566 extern void prism_pbuild_exec_root_assign(
567 int participant_id,
568 PrismBuildShared *shared,
569 PrismDsmSamples *dsm_samples,
570 PrismDsmRootAssign *dsm_ra,
571 char *centroids_base,
572 Barrier *barrier);
573
574 /* ----------------------------------------------------------------
575 * Full-table leaf-centroid refinement (parallel)
576 *
577 * A single shared accumulator (sums[nleaves*dim] + counts[nleaves]) holds the
578 * per-leaf running mean for all participants -- one copy, independent of the
579 * worker count, so it scales to fine nlist where per-worker accumulators would
580 * not. Concurrent updates are guarded by a striped lock array owned by the
581 * back-end (prism_pbuild_accum_lock/unlock); contention is low because rows
582 * spread across nleaves leaves. sums accumulate in double so the refined
583 * means match the serial build bit-for-bit at any table size.
584 * ---------------------------------------------------------------- */
585
586 #define PRISM_REFINE_LOCK_STRIPES 256
587
588 typedef struct PrismDsmRefineAccum
589 {
590 uint32_t nleaves;
591 Dimension dim;
592 /* double sums[nleaves * dim], then uint64 counts[nleaves], packed after.
593 */
594 double sums[FLEXIBLE_ARRAY_MEMBER];
595 } PrismDsmRefineAccum;
596
597 static inline double *
598 6 prism_dsm_refine_sums(PrismDsmRefineAccum *a)
599 {
600 6 return a->sums;
601 }
602
603 static inline uint64_t *
604 6 prism_dsm_refine_counts(PrismDsmRefineAccum *a)
605 {
606 6 return (uint64_t *)(a->sums + (size_t)a->nleaves * a->dim);
607 }
608
609 static inline Size
610 prism_dsm_refine_accum_size(uint32_t nleaves, Dimension dim)
611 {
612 Size sz = offsetof(PrismDsmRefineAccum, sums);
613 sz += (Size)nleaves * dim * sizeof(double);
614 sz += (Size)nleaves * sizeof(uint64_t);
615 return sz;
616 }
617
618 /*
619 * Leaves per refine tile: the accumulator holds at most this many leaves, so
620 * it is a bounded constant (cap_bytes, derived from maintenance_work_mem and
621 * MaxAllocSize by the caller) rather than O(nleaves). nleaves above it just
622 * means more re-scanned tiles, not a bigger allocation. The DSM region is
623 * sized for this (capacity = accum->nleaves); the leader and workers derive
624 * the tile count from it identically, so they stay in barrier lockstep.
625 */
626 static inline uint32_t
627 50 prism_refine_tile_leaves(uint32_t nleaves, Dimension dim, uint64_t cap_bytes)
628 {
629 50 uint64_t per_leaf = (uint64_t)dim * sizeof(double) + sizeof(uint64_t);
630 50 uint64_t t = cap_bytes / (per_leaf ? per_leaf : 1);
631
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50 times.
50 if (t < 1)
632 ✗ t = 1;
633 50 if (t > nleaves)
634 t = nleaves;
635 50 return (uint32_t)t;
636 }
637
638 /*
639 * The per-refined-leaf head writer is the shared PrismLeafWriteFn from
640 * posting_build.h: the leader rewrites each leaf's posting-list head with
641 * the full-table pt_centroid; workers pass NULL (they never divide/write).
642 */
643
644 /*
645 * Refine the leaf encode references on the whole table, page-backed (one
646 * pass; routing reads only the centroid pages, which refine never rewrites,
647 * so the assignment is a fixed point): every row is routed exactly as the
648 * query/insert do (prism_query_route k=1 over the centroid pages, head ->
649 * leaf), per-leaf means
650 * accumulate into the tiled DSM accumulator, and the leader rewrites each
651 * leaf's head-page pt_centroid to the full-table mean. Both leader
652 * (participant 0) and workers call it; gated by shared->refine so they
653 * run the same barriers. The workers route with their own page-backed qs; the
654 * leader passes qs == NULL (it does not scan) and a write_head callback.
655 * Leaves are processed in tiles of accum->nleaves, so the accumulator stays
656 * bounded regardless of nlist.
657 */
658 extern void prism_pbuild_exec_refine_paged(
659 int participant_id,
660 Relation heap,
661 Relation index,
662 struct IndexInfo *index_info,
663 PrismBuildShared *shared,
664 struct PrismQueryState *qs,
665 BlockNumber first_posting,
666 PrismDsmRefineAccum *accum,
667 Barrier *barrier,
668 PrismLeafWriteFn write_head,
669 void *write_head_ctx);
670
671 /* Striped lock seam for the refine accumulator (back-end owns the locks). */
672 extern void prism_pbuild_accum_lock(PrismBuildShared *shared, uint32_t stripe);
673 extern void
674 prism_pbuild_accum_unlock(PrismBuildShared *shared, uint32_t stripe);
675
676 /*
677 * Scan every vector cooperatively, invoking cb per live tuple. Back-end seam:
678 * the PG implementation (parallel_backend_pg.c) drives a parallel heap scan
679 * and unwraps each tuple; the standalone implementation iterates its in-memory
680 * vector array. allow_sync/progress are PG table_index_build_scan flags,
681 * ignored in standalone. Returns the number of heap tuples this participant
682 * scanned; the posting pass accumulates those into shared->reltuples so the
683 * build reports the table's true row count (index_update_stats writes it to
684 * pg_class.reltuples).
685 */
686 extern double prism_build_scan(
687 Relation heap,
688 Relation index,
689 struct IndexInfo *indexInfo,
690 PrismBuildShared *shared,
691 bool allow_sync,
692 bool progress,
693 PrismBuildScanCb cb,
694 void *state);
695
696 /* ----------------------------------------------------------------
697 * Worker entry point — registered with CreateParallelContext
698 * ---------------------------------------------------------------- */
699
700 extern void prism_parallel_build_main(dsm_segment *seg, shm_toc *toc);
701
702 /* ----------------------------------------------------------------
703 * Worker lifecycle seam — back-end-specific (parallel_backend.c for PG)
704 *
705 * Runtime handles for one participant. prism_pbuild_worker_attach fills it
706 * when the worker joins the build; prism_pbuild_worker_detach tears it down.
707 * The PG version opens the heap/index relations and reports instrumentation;
708 * the standalone version takes the shared state and vectors directly and joins
709 * a thread barrier.
710 * ---------------------------------------------------------------- */
711
712 typedef struct PrismPBuildWorker
713 {
714 PrismBuildShared *shared;
715 Barrier *barrier;
716 Relation heapRel;
717 Relation indexRel;
718 int worker_id;
719 Dimension dim;
720 } PrismPBuildWorker;
721
722 extern void prism_pbuild_worker_attach(shm_toc *toc, PrismPBuildWorker *w);
723 extern void prism_pbuild_worker_detach(shm_toc *toc, PrismPBuildWorker *w);
724
725 /*
726 * Page-backed phase-3 routing storage seam — back-end-specific. Workers read
727 * centroid + posting head pages while routing, so each needs a VsStorage over
728 * the index. PG (separate process) opens one on the worker's indexRel;
729 * standalone (threads) returns the leader's shared in-memory store published
730 * via prism_pbuild_publish_storage before launch. Release is a no-op for
731 * standalone.
732 */
733 extern void
734 prism_pbuild_publish_storage(PrismBuildShared *shared, VsStorage *s);
735 extern VsStorage *prism_pbuild_worker_storage(PrismPBuildWorker *w);
736 extern void prism_pbuild_worker_storage_release(VsStorage *s);
737
738 /*
739 * Accumulate one worker's tuple counts into the shared state under the
740 * back-end's lock (the lock lives in the back-end's derived shared struct).
741 * heap_tuples is the participant's posting-scan share of the heap; the sum
742 * across participants is the table's row count, returned to PostgreSQL as
743 * IndexBuildResult.heap_tuples.
744 */
745 extern void prism_pbuild_worker_add_counts(
746 PrismBuildShared *shared,
747 double indtuples,
748 double soar_dupes,
749 double heap_tuples);
750
751 /* ----------------------------------------------------------------
752 * Leader launch/teardown seam — back-end-specific (parallel_backend.c for PG)
753 *
754 * prism_pbuild_launch starts the workers and blocks until the whole party has
755 * attached to the phase barrier (returning false, after teardown, if none
756 * started). Fewer workers can start than were planned (the launch competes
757 * for the max_parallel_workers pool), so launch narrows
758 * shared->nparticipants to the party that actually attached. Every phase
759 * that partitions work by participant reads the count after at least one
760 * barrier, which orders the narrowing write ahead of the read.
761 * prism_pbuild_teardown frees the parallel context. The standalone versions
762 * spawn/join threads and free the shared arena. (struct ParallelContext is
763 * PostgreSQL's; standalone provides its own definition.)
764 * ---------------------------------------------------------------- */
765
766 struct ParallelContext;
767 struct WalUsage;
768 struct BufferUsage;
769
770 extern void prism_pbuild_teardown(struct ParallelContext *pcxt);
771
772 /*
773 * Sample-region seam. The k-means sample is the build's largest working set
774 * (up to the whole memory budget), but it is dead once the subtrees are
775 * clustered -- long before the posting sort claims its own budget. The PG
776 * back-end therefore keeps it in a dedicated DSM segment handed back through
777 * this seam right after the refine pass (the refine accumulator overlays the
778 * then-dead sample region, so it rides along for free), keeping the build's
779 * peak at one budget instead of stacking sample + accumulator + sort.
780 * Workers attach at startup and every participant releases independently;
781 * the segment is destroyed with the last detach. The standalone back-end
782 * keeps the samples in its arena (it does not bound memory) and treats
783 * release as a no-op.
784 */
785 extern PrismDsmSamples *prism_pbuild_samples_attach(
786 shm_toc *toc, PrismBuildShared *shared, void **seg_out);
787 extern void prism_pbuild_samples_release(PrismDsmSamples *samples, void *seg);
788
789 /* Subtree-ring seam: leader creates the ring (own segment) after root
790 * assignment and publishes the slot size; workers attach after the ring
791 * barrier; everyone releases when the subtree batches are done. */
792 extern char *prism_pbuild_subtree_ring_create(
793 PrismBuildShared *shared,
794 int nparticipants,
795 uint64_t slot_size,
796 void **seg_out);
797 extern char *
798 prism_pbuild_subtree_ring_attach(PrismBuildShared *shared, void **seg_out);
799 extern void prism_pbuild_subtree_ring_release(void *seg);
800
801 /* Exact-internal-centroids seam: the leader serializes the exact
802 * centroid collection (prism_exact_centroid_collection_write, a few MB
803 * even at very large nlist) it gathered while streaming the tree, and
804 * publishes it before the tree-ready barrier; workers attach after that
805 * barrier and hook it into their phase-2.5/3 routing base
806 * (PrismIndexBase.exact_internal). PG uses a dedicated DSM segment whose
807 * handle travels in the back-end shared struct; standalone shares the
808 * leader's allocation. Every participant releases when its routing is
809 * done; the segment dies with the last detach. */
810 extern char *prism_pbuild_exact_centroids_create(
811 PrismBuildShared *shared, uint64_t nbytes, void **seg_out);
812 extern char *
813 prism_pbuild_exact_centroids_attach(PrismBuildShared *shared, void **seg_out);
814 extern void prism_pbuild_exact_centroids_release(void *seg);
815
816 /* One histogram over the shared root assignments: out_counts[km_k] = how
817 * many samples landed in each root child. Every participant derives the
818 * same counts (same shared data); the leader additionally sizes the
819 * subtree-ring slot from them. */
820 extern void prism_pbuild_count_children(
821 PrismDsmSamples *dsm_samples,
822 PrismDsmRootAssign *dsm_ra,
823 int nparticipants,
824 uint32_t km_k,
825 uint32_t *out_counts);
826
827 /*
828 * The refine accumulator overlays the (dead) sample region: same base
829 * address, initialized by the leader after the last sample use and before
830 * the tree-ready barrier that workers pass ahead of the refine phase.
831 */
832 static inline PrismDsmRefineAccum *
833 ✗ prism_pbuild_refine_overlay(PrismDsmSamples *samples)
834 {
835 ✗ return (PrismDsmRefineAccum *)samples;
836 }
837
838 extern bool prism_pbuild_launch(
839 struct ParallelContext *pcxt,
840 Barrier *barrier,
841 PrismBuildShared *shared);
842
843 /* ----------------------------------------------------------------
844 * Leader-only subtree blob store — back-end-specific spillable storage
845 *
846 * The PLAN pass produces every subtree exactly once; the leader appends each
847 * blob here and, after computing the block layout, reads them back in the
848 * same order to stream centroid + head pages -- reading a blob back costs
849 * far less than re-running its clustering, and the streaming needs no
850 * worker participation. The PG implementation is a BufFile temp file: small
851 * blob sets stay
852 * in the kernel page cache, large ones spill to pgsql_tmp, so build memory
853 * stays bounded regardless of the partition count. Standalone keeps the
854 * blobs in memory (in-memory engine). Sequential put/rewind/get only.
855 * ---------------------------------------------------------------- */
856
857 typedef struct PrismBlobStore PrismBlobStore;
858
859 extern PrismBlobStore *prism_pbuild_blobstore_begin(void);
860 extern void prism_pbuild_blobstore_put(
861 PrismBlobStore *bs, const void *blob, uint64_t size);
862 extern void prism_pbuild_blobstore_rewind(PrismBlobStore *bs);
863 /* Read the next blob into buf (capacity max_size); returns its size. */
864 extern uint64_t
865 prism_pbuild_blobstore_get(PrismBlobStore *bs, void *buf, uint64_t max_size);
866 extern void prism_pbuild_blobstore_end(PrismBlobStore *bs);
867
868 /* ----------------------------------------------------------------
869 * Build configuration — back-end-neutral input to the setup seam
870 *
871 * The fields the setup seam needs to size and populate the shared state. The
872 * PG path fills this from its opclass-resolved PrismBuildParams; the
873 * standalone path fills it from its own config. Keeping it neutral lets one
874 * setup-seam signature serve both back-ends.
875 * ---------------------------------------------------------------- */
876
877 typedef struct PrismBuildConfig
878 {
879 Dimension dim;
880 DistanceMetric metric;
881 PrismCentroidFormat centroid_format;
882 uint32_t nlist;
883 uint32_t fan_out;
884 double soar_lambda;
885 double boundary_epsilon;
886 bool fastscan;
887 /* CREATE INDEX CONCURRENTLY: take weak locks + an MVCC scan snapshot. */
888 bool concurrent;
889 } PrismBuildConfig;
890
891 /* ----------------------------------------------------------------
892 * Leader setup seam — back-end-specific (parallel_backend.c for PG)
893 *
894 * Leader-side runtime state: the parallel context, the shared regions, and the
895 * derived sizes. prism_pbuild_setup_shared allocates and populates them (a DSM
896 * segment + regions in PG, a heap arena in standalone) and fills this struct;
897 * the rest of the driver consumes it. Returns false (after teardown) if the
898 * back-end could not start. The WalUsage/BufferUsage fields are PG
899 * instrumentation, unused in standalone.
900 * ---------------------------------------------------------------- */
901
902 typedef struct PrismPBuildLeader
903 {
904 struct ParallelContext *pcxt;
905 PrismBuildShared *shared;
906 Barrier *barrier;
907 PrismDsmSamples *dsm_samples;
908 /* Back-end token for releasing the sample region early (PG: the DSM
909 * segment the samples live in; standalone: NULL). */
910 void *sample_seg;
911 char *centroids_base;
912 float *cents;
913 char *km_workers_base;
914 PrismDsmRootAssign *dsm_ra;
915 struct WalUsage *walusage;
916 struct BufferUsage *bufferusage;
917 int nparticipants;
918 uint32_t km_k;
919 uint32_t max_per_worker;
920 Dimension dim;
921 uint32_t nlist;
922 uint64_t rabitq_seed;
923 uint32_t fan_out;
924 Size dsm_total; /* committed DSM chunk bytes (for the
925 planned-allocation introspection line) */
926 } PrismPBuildLeader;
927
928 extern bool prism_pbuild_setup_shared(
929 PrismPBuildLeader *lead,
930 Relation heap,
931 Relation index,
932 const PrismBuildConfig *config,
933 int nworkers);
934
935 /*
936 * Re-initialize the scan for the posting pass (the sampling pass consumed the
937 * first). Back-end seam: resets the PG parallel-scan descriptor or, in
938 * standalone, the work-stealing cursor.
939 */
940 extern void prism_pbuild_rescan(Relation heap, PrismBuildShared *shared);
941
942 /* ----------------------------------------------------------------
943 * Posting sort seam — cluster-keyed external sort of encoded entries.
944 *
945 * Back-end seam (like prism_build_scan): the PG back-end implements it with a
946 * parallel tuplesort whose shared coordinator (Sharedsort) lives in the build
947 * DSM; the standalone back-end with per-participant in-memory arrays merged
948 * and sorted by cluster. The shared phase-3 code
949 * (parallel_build_worker/leader) calls only this seam, so the posting build
950 * stays bounded by maintenance_work_mem without the standalone core depending
951 * on PostgreSQL's tuplesort.
952 *
953 * Lifecycle:
954 * leader, in setup_shared before launch: size the DSM region with
955 * prism_pbuild_sort_shared_size(); after launch:
956 * prism_pbuild_sort_shared_init(). each worker: begin(is_leader=false) ->
957 * put... -> performsort -> end. leader: begin(is_leader=true) ->
958 * performsort -> getnext... -> end. Entries are fixed-size opaque blobs sorted
959 * by the uint32 cluster key. `seg` and `region` are void* to keep PostgreSQL
960 * types out of the shared header (the PG impl casts seg to dsm_segment*);
961 * `region` is the PRISM_DSM_KEY_SORTSHARED chunk.
962 * ---------------------------------------------------------------- */
963 typedef struct PrismSorter PrismSorter;
964
965 extern Size prism_pbuild_sort_shared_size(int nparticipants);
966 extern void
967 prism_pbuild_sort_shared_init(void *region, int nparticipants, void *seg);
968 extern PrismSorter *prism_pbuild_sort_begin(
969 void *region,
970 void *seg,
971 int participant,
972 int nparticipants,
973 bool is_leader,
974 uint32_t entry_size,
975 int work_mem_kb);
976 extern void prism_pbuild_sort_put(
977 PrismSorter *sorter, uint32_t cluster, const void *entry);
978 extern void prism_pbuild_sort_performsort(PrismSorter *sorter);
979 extern bool prism_pbuild_sort_getnext(
980 PrismSorter *sorter, uint32_t *cluster, const void **entry);
981 extern void prism_pbuild_sort_end(PrismSorter *sorter);
982
983 /*
984 * Build every cluster's posting list from a populated (not yet performsorted)
985 * cluster-keyed sorter. Shared by the serial build and the parallel leader:
986 * performsort, then read entries grouped by cluster and write each list with a
987 * single resident page builder. Cluster c's head is the formula first_posting
988 * + c (a pre-extended head region); continuation pages are appended at the end
989 * of the relation and chained, so no O(nlist) reserve is needed. Ends the
990 * sorter.
991 */
992 extern void prism_posting_build_lists(
993 PrismSorter *sorter,
994 VsStorage *storage,
995 uint32_t nlist,
996 Dimension dim,
997 bool fastscan,
998 const RaBitQParams *rq_params,
999 BlockNumber first_posting);
1000
1001 /* ----------------------------------------------------------------
1002 * Parallel build entry — shared driver (parallel_build_leader.c)
1003 *
1004 * Runs sampling + k-means + the bounded streaming posting build over the heap
1005 * (its vectors) into storage, returning the centroid tree and per-list posting
1006 * heads. Returns false if parallelism could not start, so the caller falls
1007 * back to a serial build. The PG caller fills config from its resolved build
1008 * params; the standalone caller fills it from its index config.
1009 *
1010 * prog is the build-progress reporting seam (phases + % to
1011 * pg_stat_progress_create_index, per-phase stats under prism.log_build_stats).
1012 * The PG caller passes its PrismBuildProgress so the parallel phases surface
1013 * the same way the serial ones do; the standalone caller passes NULL (the seam
1014 * is a no-op stub there).
1015 * ---------------------------------------------------------------- */
1016
1017 struct PrismBuildProgress; /* index/build_progress.h */
1018
1019 extern bool do_parallel_build(
1020 Relation heap,
1021 Relation index,
1022 struct IndexInfo *index_info,
1023 const PrismBuildConfig *config,
1024 VsStorage *storage,
1025 struct PrismBuildProgress *prog,
1026 /* No in-RAM tree is materialized; the streamed tree's shape (leaf
1027 * count + depth) comes back through these for the caller's metadata
1028 * write. *out_nlist == 0 means the heap had no indexable rows. */
1029 uint32_t *out_nlist,
1030 uint8_t *out_tree_nlevels,
1031 double *out_heap_tuples,
1032 double *out_indtuples,
1033 double *out_soar_dupes,
1034 /* The build routes page-backed, so it writes the centroid pages +
1035 * heads into `storage` before the scan and computes the global mean;
1036 * *out_global_mean is the (owned) mean the centroid pages encode
1037 * against, so the caller's metadata write matches. May be NULL. */
1038 float **out_global_mean,
1039 /* The posting-head base: cluster c's head is
1040 * prism_leaf_head_blkno(*out_first_posting, c, stride).
1041 * Callers that need to locate head pages after the build (e.g. the
1042 * standalone driver + its tests) capture it; may be NULL. */
1043 BlockNumber *out_first_posting);
1044
1045 #endif /* PRISM_PARALLEL_BUILD_H */
1046