| 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 |