GCC Code Coverage Report


Directory: src/
File: src/pg/build.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 450 465 96.8%
Functions: 14 14 100.0%
Branches: 158 217 72.8%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * build.c - Index build for prism
6 *
7 * Serial build phases (do_serial_build; the parallel shape lives in
8 * parallel_build_leader.c and falls back here when no workers launch):
9 * 1. Resolve dimension, metric, centroid format, nlist, fan_out
10 * 2. Sample vectors for clustering (BlockSampler + reservoir)
11 * 3. Routing-tree PLAN pass: cluster the sample once, recording each
12 * node into a spillable blob store, and size the page layout
13 * 4. Pre-extend the relation for the centroid pages + posting heads
14 * 5. Routing-tree WRITE pass: replay the recorded nodes and stream
15 * every centroid page and posting-head page (pt_centroid resident)
16 * 6. Optional leaf refinement (prism.leaf_refine_threshold) re-centers
17 * the head encode references from the full table
18 * 7. Single heap scan: route each row page-backed (the same
19 * prism_query_route the query/insert use) into the cluster-keyed sort,
20 * then build each posting list
21 * 8. Write the metadata page (final tuple count) and WAL-log
22 *
23 * Block layout:
24 * Block 0: Metadata page
25 * Blocks 1..C: Centroid pages (streamed before the scan)
26 * Blocks C+1..H: Posting-list head pages (leaf c at C+1+c)
27 * Blocks H+1..N: Posting continuation pages (appended during the scan)
28 *
29 * Memory layout:
30 * build_ctx — all build-phase allocations; deleted in one shot
31 * tmp_ctx — per-tuple scratch; reset after each callback
32 */
33
34 #include <postgres.h>
35
36 #include <access/heaptoast.h>
37 #include <access/htup_details.h>
38 #include <access/table.h>
39 #include <access/tableam.h>
40 #include <access/xloginsert.h>
41 #include <catalog/index.h>
42 #include <common/pg_prng.h>
43 #include <math.h>
44 #include <miscadmin.h>
45 #include <portability/instr_time.h>
46 #include <utils/memutils.h>
47 #include <utils/rel.h>
48 #include <utils/sampling.h>
49
50 #include "algo/distance.h"
51 #include "algo/hkmeans.h"
52 #include "algo/kmeans.h"
53 #include "algo/vecops.h"
54 #include "build.h"
55 #include "core/log.h"
56 #include "index/centroid_build.h"
57 #include "index/centroid_page.h"
58 #include "index/index_base.h"
59 #include "index/index_build.h"
60 #include "index/parallel_build.h"
61 #include "index/posting_build.h"
62 #include "index/posting_page.h"
63 #include "index/query_scan.h"
64 #include "meta.h"
65 #include "pg/bufstorage.h"
66 #include "quant/rabitq.h"
67 #include "support_pg.h"
68 #include "typeinfo.h"
69 #include "types/vec16.h"
70 #include "types/vec32.h"
71
72 /* ----------------------------------------------------------------
73 * Build state (PrismBuildParams is in build.h, shared with the
74 * parallel leader)
75 * ---------------------------------------------------------------- */
76
77 typedef struct PrismBuildState
78 {
79 PrismBuildParams params;
80
81 double indtuples; /* total count */
82 double soar_dupes; /* replicated SOAR vectors */
83
84 /*
85 * Posting entries are streamed into a cluster-keyed tuplesort during the
86 * heap scan, then read back grouped by cluster so the build holds only ONE
87 * posting-page builder at a time. This bounds build memory to
88 * maintenance_work_mem (the tuplesort stays in RAM until it exceeds it,
89 * then spills); per-cluster resident builders would cost O(nlist) memory.
90 */
91 /* Posting entries are RaBitQ-encoded during the scan (relative to the
92 * assigned cluster centroid) and fed to a cluster-keyed sorter — the same
93 * PrismSorter seam the parallel build uses, here in non-parallel mode (no
94 * coordinate). The shared build loop (prism_posting_build_lists) reads
95 * them back grouped by cluster and writes one resident page builder at a
96 * time.
97 */
98 PrismSorter *sorter;
99 RaBitQParams *rq_params;
100
101 /* Sampling */
102 float *samples; /* [max_samples * dim] row-major */
103 int nsamples; /* current sample count */
104 int max_samples; /* target sample count */
105 double rowstoskip; /* reservoir sampling state */
106
107 ReservoirStateData rstate;
108
109 /* PG context */
110 Relation heap;
111 Relation index;
112 struct IndexInfo *index_info;
113 MemoryContext build_ctx; /* all build allocations */
114 MemoryContext tmp_ctx; /* per-tuple scratch */
115
116 PrismBuildProgress *prog; /* phase/progress reporting seam (serial path) */
117
118 /*
119 * Page-backed assignment (routes each row the same way the query/insert
120 * do, so the in-RAM tree is not needed for the scan). qs holds the routing
121 * state; route is the shared route+encode+emit context (also used by the
122 * parallel posting workers), which references qs and the sorter.
123 */
124 PrismQueryState qs;
125 PrismBuildRouteCtx route;
126
127 /*
128 * Column type bound to this index's dimension, with the conversion buffer
129 * it needs. Held on the state because both callbacks run under a tmp_ctx
130 * that is reset after every tuple.
131 */
132 Vec32Access input;
133 } PrismBuildState;
134
135 /* ----------------------------------------------------------------
136 * Helpers
137 * ---------------------------------------------------------------- */
138
139 /* ----------------------------------------------------------------
140 * Sampling
141 * ---------------------------------------------------------------- */
142
143 static void
144 262238 sample_callback(
145 Relation index,
146 ItemPointer tid,
147 Datum *values,
148 bool *isnull,
149 bool tuple_is_alive,
150 void *state)
151 {
152 262238 PrismBuildState *bs = (PrismBuildState *)state;
153
154 262238 (void)index;
155 262238 (void)tid;
156 262238 (void)tuple_is_alive;
157
158
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 262215 times.
262238 if (isnull[0])
159 23 return;
160
161 262215 MemoryContext old_ctx = MemoryContextSwitchTo(bs->tmp_ctx);
162
163 262215 Dimension dim = bs->params.dim;
164 262215 Vec32Ref vref = vec32_read(&bs->input, values[0]);
165 262215 const float *src = vref.data;
166 262215 const size_t vec_nbytes = (size_t)dim * sizeof(float);
167
168
2/2
✓ Branch 0 taken 256215 times.
✓ Branch 1 taken 6000 times.
262215 if (bs->nsamples < bs->max_samples)
169 {
170 256215 memcpy(bs->samples + (size_t)bs->nsamples * dim, src, vec_nbytes);
171 256215 bs->nsamples++;
172 }
173 else
174 {
175
2/2
✓ Branch 0 taken 5460 times.
✓ Branch 1 taken 540 times.
6000 if (bs->rowstoskip < 0)
176 5460 bs->rowstoskip = reservoir_get_next_S(
177 5460 &bs->rstate, bs->nsamples, bs->max_samples);
178
179
2/2
✓ Branch 0 taken 5460 times.
✓ Branch 1 taken 540 times.
6000 if (bs->rowstoskip <= 0)
180 {
181 10920 int k = (int)(bs->max_samples *
182 5460 sampler_random_fract(&bs->rstate.randstate));
183
2/4
✓ Branch 0 taken 5460 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 5460 times.
5460 Assert(k >= 0 && k < bs->max_samples);
184 5460 memcpy(bs->samples + (size_t)k * dim, src, vec_nbytes);
185 }
186 6000 bs->rowstoskip -= 1;
187 6000 bs->nsamples++;
188 }
189
190 262215 MemoryContextSwitchTo(old_ctx);
191 262215 MemoryContextReset(bs->tmp_ctx);
192 }
193
194 static void
195 204 sample_rows(PrismBuildState *bs)
196 {
197 204 BlockNumber totalblocks = RelationGetNumberOfBlocks(bs->heap);
198 204 BlockSamplerData bsampler;
199
200 204 bs->rowstoskip = -1;
201
202 204 BlockSampler_Init(
203 &bsampler,
204 totalblocks,
205 bs->max_samples,
206 pg_prng_uint32(&pg_global_prng_state));
207 204 reservoir_init_selection_state(&bs->rstate, bs->max_samples);
208
209
2/2
✓ Branch 2 taken 6826 times.
✓ Branch 3 taken 204 times.
7030 while (BlockSampler_HasMore(&bsampler))
210 {
211 6826 BlockNumber targblock = BlockSampler_Next(&bsampler);
212
213 6826 table_index_build_range_scan(
214 bs->heap,
215 bs->index,
216 bs->index_info,
217 false,
218 true,
219 false,
220 targblock,
221 1,
222 sample_callback,
223 (void *)bs,
224 NULL);
225 }
226 204 }
227
228 /* ----------------------------------------------------------------
229 * Build callback — single-pass: route each row page-backed,
230 * stream encoded entries into the cluster-keyed sorter
231 * ---------------------------------------------------------------- */
232
233 static void
234 262238 build_callback(
235 Relation index,
236 ItemPointer tid,
237 Datum *values,
238 bool *isnull,
239 bool tuple_is_alive,
240 void *state)
241 {
242 262238 PrismBuildState *bs = (PrismBuildState *)state;
243
244 262238 (void)index;
245 262238 (void)tuple_is_alive;
246
247
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 262215 times.
262238 if (isnull[0])
248 23 return;
249
250 262215 MemoryContext old_ctx = MemoryContextSwitchTo(bs->tmp_ctx);
251
252 262215 Vec32Ref vref = vec32_read(&bs->input, values[0]);
253
254 /* Route + encode + stream via the shared page-backed helper (the parallel
255 * posting workers use the very same call). tmp_ctx is reset after every
256 * tuple, so nothing reachable from this call may allocate memory that
257 * outlives the callback: the route context's buffers (candidates, batch,
258 * encode scratch) are all preallocated for exactly this reason. */
259 262215 prism_build_route_emit(&bs->route, vref.data, *tid);
260
261
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 262200 times.
262215 if (((uint64_t)bs->route.indtuples % 10000) == 0)
262 15 prism_build_report_progress(bs->prog, bs->route.indtuples);
263
264 262215 MemoryContextSwitchTo(old_ctx);
265 262215 MemoryContextReset(bs->tmp_ctx);
266 }
267
268 /* ----------------------------------------------------------------
269 * Write metadata page
270 * ---------------------------------------------------------------- */
271
272 static void
273 249 write_meta_page(
274 VsStorage *storage,
275 Dimension dim,
276 uint8_t nlevels,
277 uint8_t fan_out,
278 BlockNumber first_centroid,
279 BlockNumber first_posting,
280 uint32_t ncentroid_pages,
281 uint32_t nlist,
282 PrismCentroidFormat centroid_format,
283 DistanceMetric metric,
284 uint64_t rabitq_seed,
285 bool fastscan,
286 const float *global_mean)
287 {
288 /* Block 0 must already exist (extended or new_page'd by caller).
289 * Use write_page to write in-place. */
290 249 Page page = vs_storage_write_page(storage, 0);
291
292
2/2
✓ Branch 0 taken 219 times.
✓ Branch 1 taken 30 times.
249 PageInit(page, BLCKSZ, PRISM_META_SIZE(dim));
293
294 249 PrismMetaPage *meta = (PrismMetaPage *)PageGetSpecialPointer(page);
295 249 meta->magic = PRISM_META_MAGIC;
296 249 meta->dim = dim;
297 249 meta->nlevels = nlevels;
298 249 meta->centroid_format = (uint8_t)centroid_format;
299 249 meta->first_centroid = first_centroid;
300 249 meta->first_posting = first_posting;
301 249 meta->ncentroid_pages = ncentroid_pages;
302 249 meta->nlist = nlist;
303 249 meta->metric = (uint8_t)metric;
304 249 meta->fan_out = (uint8_t)fan_out;
305 249 meta->flags = fastscan ? PRISM_META_FLAG_FASTSCAN : 0;
306 249 meta->reserved = 0;
307 249 meta->rabitq_seed = rabitq_seed;
308
309
2/2
✓ Branch 0 taken 219 times.
✓ Branch 1 taken 30 times.
249 if (prism_meta_mean_inline(dim))
310 219 memcpy(prism_meta_global_mean(meta), global_mean, dim * sizeof(float));
311
312 249 vs_storage_commit_page(storage, 0);
313
314 /* A mean too wide for the metapage spills into the reference pages
315 * right after it, reserved by the layout and chained like a posting
316 * list's reference; amcache gathers them once per backend. */
317
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 219 times.
249 uint32_t npages = prism_global_mean_pages(dim);
318
2/2
✓ Branch 1 taken 92 times.
✓ Branch 2 taken 249 times.
341 for (uint32_t i = 0; i < npages; i++)
319 {
320 92 BlockNumber blk = PRISM_GLOBAL_MEAN_BLKNO + i;
321 92 Page p = vs_storage_write_page(storage, blk);
322
323 92 prism_posting_reference_page_fill(
324 p, PRISM_GLOBAL_MEAN_CLUSTER, dim, i, global_mean, 0);
325
2/2
✓ Branch 0 taken 62 times.
✓ Branch 1 taken 30 times.
92 if (i + 1 < npages)
326 62 prism_posting_opaque(p)->next_blkno = blk + 1;
327 92 vs_storage_commit_page(storage, blk);
328 }
329 249 }
330
331 /* ----------------------------------------------------------------
332 * Helpers: resolve metric and centroid format from opclass/relopts
333 * ---------------------------------------------------------------- */
334
335 static DistanceMetric
336 254 prism_get_metric(Relation index)
337 {
338 254 FmgrInfo *procinfo = index_getprocinfo(index, 1, PRISM_METRIC_PROC);
339 254 return (DistanceMetric)DatumGetInt32(
340 FunctionCall1Coll(procinfo, InvalidOid, (Datum)0));
341 }
342
343 static PrismCentroidFormat
344 254 prism_resolve_format(Relation index, DistanceMetric metric, Dimension dim)
345 {
346 254 PrismOptions *opts = (PrismOptions *)index->rd_options;
347 469 int cc = (opts != NULL) ? opts->centroid_compression
348
2/2
✓ Branch 0 taken 215 times.
✓ Branch 1 taken 39 times.
254 : PRISM_CENTROID_COMPRESSION_AUTO;
349 215 int cfs = (opts != NULL) ? opts->centroid_fastscan
350 : PRISM_FASTSCAN_MODE_AUTO;
351
352 /*
353 * RaBitQ centroids estimate L2 distance, which routes correctly for
354 * L2 and (normalized) cosine but not inner product. ON forces it and
355 * errors for inner product; AUTO compresses everything except inner
356 * product; OFF disables it.
357 */
358 254 bool compressed;
359
3/3
✓ Branch 0 taken 83 times.
✓ Branch 1 taken 158 times.
✓ Branch 2 taken 13 times.
254 switch (cc)
360 {
361 83 case PRISM_CENTROID_COMPRESSION_ON:
362
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 82 times.
83 if (metric == DISTANCE_INNER_PRODUCT)
363
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
1 ereport(ERROR,
364 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
365 errmsg("centroid_compression=on is not supported "
366 "with vec32_ip_ops")));
367 compressed = true;
368 break;
369 case PRISM_CENTROID_COMPRESSION_OFF:
370 compressed = false;
371 break;
372 158 default: /* AUTO */
373 158 compressed = (metric != DISTANCE_INNER_PRODUCT);
374 158 break;
375 }
376
377 /*
378 * Uncompressed centroids are full vectors on a centroid page; past the
379 * dimension where one fits (2036 float32, 4072 float16) there is no
380 * such page. Inner product has no compressed alternative (RaBitQ
381 * centroids estimate L2), so it ends here; L2 and cosine only reach
382 * this with centroid_compression=off.
383 */
384
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 154 times.
158 if (!compressed)
385 {
386 34 PrismCentroidFormat fmt =
387 17 prism_index_type_info(index)->centroid_format;
388
389
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 14 times.
17 if (prism_centroid_max_entries_fmt(dim, fmt) == 0)
390
3/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 2 times.
4 ereport(ERROR,
391 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
392 errmsg("uncompressed centroids do not fit a page at %d "
393 "dimensions",
394 dim),
395 errhint(metric == DISTANCE_INNER_PRODUCT
396 ? "Inner product routes on uncompressed "
397 "centroids, which fit up to 2036 "
398 "dimensions as float32 (vec32) and "
399 "4072 as float16 (vec16). Use the L2 "
400 "or cosine operator class; normalized "
401 "embeddings rank the same under "
402 "cosine."
403 : "Leave centroid_compression at its "
404 "default.")));
405 }
406
407 /*
408 * FASTSCAN centroids are a packed layout over the RaBitQ-compressed
409 * representation, so they require compression (and, like RaBitQ
410 * centroids, don't apply to inner product). The layout stores fixed
411 * 32-candidate groups, so past the dimension where a group no
412 * longer fits a page it cannot be used at all. AUTO uses it exactly
413 * where it is available; ON errors where it is not.
414 */
415
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 243 times.
250 bool cfs_fits = prism_centroid_fastscan_max_groups(dim) > 0;
416
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 243 times.
250 if (cfs == PRISM_FASTSCAN_MODE_ON)
417 {
418
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
7 if (metric == DISTANCE_INNER_PRODUCT)
419 ✗ ereport(ERROR,
420 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
421 errmsg("centroid_fastscan=on is not supported "
422 "with vec32_ip_ops")));
423
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
7 if (!compressed)
424 ✗ ereport(ERROR,
425 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
426 errmsg("centroid_fastscan=on requires "
427 "centroid_compression")));
428
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
7 if (!cfs_fits)
429 ✗ ereport(ERROR,
430 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
431 errmsg("centroid_fastscan=on does not support "
432 "%d dimensions",
433 dim)));
434 }
435
4/4
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 74 times.
✓ Branch 2 taken 27 times.
✓ Branch 3 taken 149 times.
250 if (compressed && cfs != PRISM_FASTSCAN_MODE_OFF && cfs_fits)
436 return PRISM_CENTROID_FMT_FASTSCAN;
437
438
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 87 times.
101 if (compressed)
439 return PRISM_CENTROID_FMT_RABITQ;
440
441 /* Uncompressed centroids follow the column type. Resolved directly rather
442 * than through the per-backend cache: there is no metadata page to
443 * populate that cache from until this build writes one. */
444 14 return prism_index_type_info(index)->centroid_format;
445 }
446
447 /*
448 * Resolve the posting-page format. Fastscan works at every dimension the
449 * index supports, so AUTO and ON both mean fastscan.
450 */
451 static bool
452 250 prism_resolve_fastscan(Relation index)
453 {
454 250 PrismOptions *opts = (PrismOptions *)index->rd_options;
455 213 int fs = (opts != NULL) ? opts->fastscan : PRISM_FASTSCAN_MODE_AUTO;
456
457 250 return fs != PRISM_FASTSCAN_MODE_OFF;
458 }
459
460 static uint32_t
461 250 prism_get_fan_out(Relation index)
462 {
463 250 PrismOptions *opts = (PrismOptions *)index->rd_options;
464
1/2
✓ Branch 0 taken 213 times.
✗ Branch 1 not taken.
213 if (opts != NULL && opts->fan_out >= PRISM_MIN_FAN_OUT)
465 213 return (uint32_t)opts->fan_out;
466 return PRISM_DEFAULT_FAN_OUT;
467 }
468
469 static void
470 257 resolve_build_params(
471 Relation heap, Relation index, PrismBuildParams *p, double *est_rows)
472 {
473
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 257 times.
257 Dimension dim = (Dimension)TupleDescAttr(index->rd_att, 0)->atttypmod;
474
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 257 times.
257 if (dim == 0)
475 ✗ ereport(ERROR,
476 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
477 errmsg("column does not have dimensions")));
478
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 257 times.
257 if (dim > VEC32_MAX_DIM)
479 ✗ ereport(ERROR,
480 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
481 errmsg("column cannot have more than %d dimensions",
482 VEC32_MAX_DIM)));
483
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 254 times.
257 if (!prism_index_dim_supported(dim))
484
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
3 ereport(ERROR,
485 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
486 errmsg("prism indexes do not support %d dimensions", dim),
487 errdetail(
488 "Any dimension up to %d is supported. Above it "
489 "the dimension must be a power of two times an "
490 "odd factor of at most %d, such as 2048, 3072, "
491 "4096, 6144 or 8192, and %d is the ceiling.",
492 PRISM_INDEX_NARROW_MAX_DIM,
493 VS_FAST_ROTATE_K_MAX,
494 PRISM_INDEX_MAX_DIM)));
495
496 254 p->dim = dim;
497 254 p->metric = prism_get_metric(index);
498 254 p->centroid_format = prism_resolve_format(index, p->metric, dim);
499
2/2
✓ Branch 0 taken 213 times.
✓ Branch 1 taken 37 times.
250 p->fan_out = prism_get_fan_out(index);
500
501 /* nlist: use relopt if set, otherwise auto from sqrt(reltuples).
502 * The row estimate is computed once and surfaced to the caller (the
503 * progress-reporting total needs it too): the never-analyzed
504 * fallback samples heap pages, and sampling twice would double that
505 * cost and could even disagree with itself on a growing heap. */
506 250 PrismOptions *opts = (PrismOptions *)index->rd_options;
507
2/2
✓ Branch 0 taken 213 times.
✓ Branch 1 taken 37 times.
250 uint32_t nlist_opt = (opts != NULL) ? (uint32_t)opts->nlist : 0;
508 213 uint32_t tpages_opt = (opts != NULL) ? (uint32_t)opts->target_pages : 0;
509
510 250 *est_rows = prism_estimate_heap_tuples(heap);
511
512
2/2
✓ Branch 0 taken 154 times.
✓ Branch 1 taken 96 times.
250 if (nlist_opt > 0)
513 154 p->nlist = nlist_opt;
514 else
515 96 p->nlist = prism_auto_nlist(*est_rows, p->dim, tpages_opt);
516
517 /* Clamped on both paths: the parallel build sizes its DSM regions from
518 * this, and the bound an explicit nlist passes through is applied by
519 * the reloption parser in another file. */
520
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 250 times.
250 if (p->nlist > PRISM_MAX_NLIST)
521 ✗ p->nlist = PRISM_MAX_NLIST;
522
523 500 p->fan_out =
524 250 prism_auto_fan_out(p->fan_out, p->nlist, PRISM_DEFAULT_FAN_OUT);
525
526
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 213 times.
213 p->kmeans_nredo = (opts != NULL && opts->kmeans_nredo > 0)
527 ? (uint32_t)opts->kmeans_nredo
528
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 213 times.
250 : 1;
529
530 213 p->soar_lambda = (opts != NULL) ? opts->soar_lambda
531 213 : PRISM_DEFAULT_SOAR_LAMBDA;
532 37 p->boundary_epsilon = (opts != NULL) ? opts->boundary_epsilon
533 213 : PRISM_DEFAULT_BOUNDARY_EPSILON;
534
2/2
✓ Branch 0 taken 213 times.
✓ Branch 1 taken 37 times.
250 p->fastscan = prism_resolve_fastscan(index);
535
536 /* The exact-centroid collection size is known from the resolved
537 * shape alone, so an under-budgeted maintenance_work_mem can be
538 * reported now — at build start, before the expensive phases —
539 * with the setting that would fit. The collector still enforces
540 * the budget against the real size at collection time. */
541
2/2
✓ Branch 0 taken 236 times.
✓ Branch 1 taken 14 times.
250 if (p->centroid_format == PRISM_CENTROID_FMT_RABITQ ||
542 p->centroid_format == PRISM_CENTROID_FMT_FASTSCAN)
543 {
544 236 uint64_t expected =
545
2/2
✓ Branch 0 taken 183 times.
✓ Branch 1 taken 53 times.
236 prism_exact_centroid_expected_bytes(p->nlist, p->fan_out, dim);
546
1/2
✓ Branch 0 taken 236 times.
✗ Branch 1 not taken.
236 uint64_t budget = prism_exact_centroid_budget(
547 (uint64_t)maintenance_work_mem);
548
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 235 times.
236 if (expected > budget)
549
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
1 vs_warn("maintenance_work_mem is likely too small for exact "
550 "centroid collection (about " UINT64_FORMAT
551 " kB needed for nlist=%u, fan_out=%u; the budget is "
552 "one eighth of maintenance_work_mem): the build will "
553 "fall back to estimated internal scoring — raise "
554 "maintenance_work_mem to at least " UINT64_FORMAT " kB",
555 expected / 1024 + 1,
556 p->nlist,
557 p->fan_out,
558 expected * 8 / 1024 + 1);
559 }
560 250 }
561
562 /*
563 * Estimated heap row count. Uses the planner's reltuples when available,
564 * else samples real pages and counts normal line pointers (no
565 * visibility checks -- dead-but-unpruned rows count, like reltuples
566 * right after a bulk delete). Feeds the automatic partition count and
567 * the pg_stat_progress_create_index total.
568 *
569 * The density is measured rather than derived from the vector width
570 * because any width formula must assume a storage strategy, and a wrong
571 * assumption is catastrophic in both directions: a TOASTed column's
572 * main-fork rows are ~64 bytes where the dimension predicts kilobytes
573 * (undercounting rows two orders of magnitude), while a PLAIN-stored
574 * vector column holds ~2 rows per page where the TOAST assumption
575 * predicts ~128 (overcounting 64x -- and the automatic partition count
576 * inherits the error, sharding the index into starved clusters).
577 */
578 double
579 622 prism_estimate_heap_tuples(Relation heap)
580 {
581
2/2
✓ Branch 0 taken 460 times.
✓ Branch 1 taken 162 times.
622 if (heap->rd_rel->reltuples > 0)
582 460 return heap->rd_rel->reltuples;
583
584 162 BlockNumber nblocks = RelationGetNumberOfBlocks(heap);
585
2/2
✓ Branch 0 taken 151 times.
✓ Branch 1 taken 11 times.
162 if (nblocks == 0)
586 return 0;
587
588 151 uint32_t samples = Min(nblocks, 32);
589 151 double rows = 0;
590
591
2/2
✓ Branch 0 taken 978 times.
✓ Branch 1 taken 151 times.
1129 for (uint32_t i = 0; i < samples; i++)
592 {
593 978 BlockNumber blkno = (BlockNumber)(((uint64_t)nblocks *
594 978 (2 * (uint64_t)i + 1)) /
595 978 (2 * samples));
596 978 Buffer buf = ReadBuffer(heap, blkno);
597
598 978 LockBuffer(buf, BUFFER_LOCK_SHARE);
599 978 Page page = BufferGetPage(buf);
600
601 /* An extended-but-unwritten page has pd_lower == 0, where
602 * PageGetMaxOffsetNumber underflows; such pages hold no rows. */
603
1/2
✓ Branch 0 taken 978 times.
✗ Branch 1 not taken.
978 if (!PageIsNew(page))
604 {
605
1/2
✓ Branch 0 taken 978 times.
✗ Branch 1 not taken.
978 OffsetNumber max = PageGetMaxOffsetNumber(page);
606
2/2
✓ Branch 0 taken 62842 times.
✓ Branch 1 taken 978 times.
63820 for (OffsetNumber off = FirstOffsetNumber; off <= max; off++)
607 {
608
1/2
✓ Branch 0 taken 62842 times.
✗ Branch 1 not taken.
62842 if (ItemIdIsNormal(PageGetItemId(page, off)))
609 62842 rows += 1;
610 }
611 }
612 978 UnlockReleaseBuffer(buf);
613 }
614 151 return rows / samples * nblocks;
615 }
616
617 /* ----------------------------------------------------------------
618 * Sample and cluster vectors
619 * ---------------------------------------------------------------- */
620
621 /*
622 * Draw the maintenance_work_mem-bounded k-means sample into bs->samples (left
623 * resident for the caller to cluster + free), normalize it for cosine, and
624 * resolve the leaf target against the sample size. A heap with no indexable
625 * rows yields one synthetic sample and a single-cluster target, so the
626 * build always proceeds.
627 */
628 static void
629 204 sample_for_build(
630 PrismBuildState *bs, uint32_t *out_nlist, bool *out_subsampled)
631 {
632 204 Dimension dim = bs->params.dim;
633 204 uint32_t nlist = bs->params.nlist;
634
635 /* Bound the sample buffer by maintenance_work_mem (and MaxAllocSize). The
636 * tree is trained on this sample; leaf centroids are refined on the full
637 * table by a later (page-backed) refine pass when subsampling loses
638 * quality. */
639 204 const uint64_t vec_nbytes = (uint64_t)dim * sizeof(float);
640
641 204 uint64_t ideal_samples = Max((uint64_t)10000, (uint64_t)nlist * 256);
642 204 uint64_t budget = (uint64_t)maintenance_work_mem * 1024 / vec_nbytes;
643 204 uint64_t alloc_cap = MaxAllocSize / vec_nbytes;
644 204 uint64_t cap = Min(budget, alloc_cap);
645 204 if (cap < 10000)
646 cap = 10000;
647 204 *out_subsampled = ideal_samples > cap;
648 204 bs->max_samples = (int)Min(ideal_samples, cap);
649
650 204 bs->nsamples = 0;
651 204 bs->samples = palloc((size_t)bs->max_samples * vec_nbytes);
652
653 204 sample_rows(bs);
654
655
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 201 times.
204 if (bs->nsamples > bs->max_samples)
656 3 bs->nsamples = bs->max_samples;
657
658
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 192 times.
204 if (bs->params.metric == DISTANCE_COSINE)
659 {
660 /*
661 * Normalize the sample onto the unit sphere, dropping zero-norm
662 * vectors: they carry no direction, so under cosine they sit at
663 * the origin -- far from every real point -- and k-means drags
664 * centroids toward them, warping the encode references (and so
665 * the distance estimates) for every vector in the affected
666 * subtree. They stay in the posting lists like any other row;
667 * they just don't get a vote on the clustering.
668 *
669 * Dropped here, by compacting the retained sample, rather than
670 * at collection time: the reservoir offers every live heap row,
671 * so a collection-time check would compute an O(dim) norm per
672 * table row to filter out a tiny fraction, while this pass
673 * touches only the <= max_samples retained rows (and copies
674 * nothing at all when no zeros were sampled). The cost is a
675 * sample budget short by the sampled-zero count -- in expectation
676 * the table's zero fraction, far below k-means run-to-run
677 * variance -- and slots spent on zeros bought nothing before
678 * this pass existed either. nlist is clamped to the compacted
679 * count below, so even a zero-heavy table degrades to fewer
680 * leaves rather than starved ones (all-zero degenerates to the
681 * synthetic single-cluster build).
682 */
683 int kept = 0;
684
2/2
✓ Branch 0 taken 8042 times.
✓ Branch 1 taken 12 times.
8054 for (int i = 0; i < bs->nsamples; i++)
685 {
686 8042 float *v = bs->samples + (size_t)i * dim;
687 8042 float norm_sq = vs_l2_norm_squared(v, dim);
688
689
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 7998 times.
8042 if (norm_sq == 0.0f)
690 44 continue;
691 7998 vec32_scale(v, 1.0f / sqrtf(norm_sq), v, dim);
692 /* The buffer is a dense row-major matrix consumed directly
693 * by k-means, so a dropped row leaves a hole that must be
694 * closed: shift each kept row down over it. Until the first
695 * drop, kept == i and rows stay normalized in place. */
696
2/2
✓ Branch 0 taken 2998 times.
✓ Branch 1 taken 5000 times.
7998 if (kept != i)
697 2998 memcpy(bs->samples + (size_t)kept * dim,
698 v,
699 (size_t)dim * sizeof(float));
700 7998 kept++;
701 }
702 12 bs->nsamples = kept;
703 }
704
705
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 195 times.
204 if (bs->nsamples == 0)
706 {
707 /*
708 * No indexable rows (empty table, or every row dead or NULL).
709 * Synthesize one unit-basis sample so the normal machinery
710 * emits a valid single-cluster index: the sample only shapes
711 * the leaf centroid -- the heap scan that fills posting lists
712 * still contributes nothing -- and later inserts route to that
713 * leaf like any single-cluster index (empty posting heads are
714 * a supported shape; every cluster gets one). A unit vector
715 * rather than zeros keeps the centroid safe for cosine
716 * normalization and the RaBitQ norm factors. Clustering
717 * quality after bulk loading comes from REINDEX, exactly as
718 * for any index built far below its final row count.
719 */
720 9 bs->samples = repalloc(bs->samples, vec_nbytes);
721 9 bs->max_samples = 1;
722 9 memset(bs->samples, 0, vec_nbytes);
723 9 bs->samples[0] = 1.0f;
724 9 bs->nsamples = 1;
725 }
726
727 204 if ((uint32_t)bs->nsamples < nlist)
728 nlist = (uint32_t)bs->nsamples;
729
730 204 *out_nlist = nlist;
731 204 }
732
733 /* ----------------------------------------------------------------
734 * Serial build
735 * ---------------------------------------------------------------- */
736
737 /* ----------------------------------------------------------------
738 * Page-backed leaf refinement (streaming build)
739 *
740 * The streaming write trained the centroids on the
741 * maintenance_work_mem-bounded sample. When that subsampled, refine the
742 * per-leaf encode reference on the full table: route every row page-backed to
743 * its leaf (the same routing the scan + query use), accumulate per-leaf means,
744 * and rewrite each leaf's head-page pt_centroid to the full-table mean. This
745 * tightens the RaBitQ residuals (the dominant recall factor) for every vector
746 * in the leaf. The accumulator is tiled to a bounded ceiling (like the posting
747 * reserve), so memory stays O(maintenance_work_mem) regardless of nlist;
748 * nleaves above the tile just means more (re-scanned) tiles. Routing stays on
749 * the sample-trained centroid pages, so a single pass reaches the fixed point
750 * (assignments do not shift).
751 * ---------------------------------------------------------------- */
752
753 typedef struct RefineHeadState
754 {
755 PrismQueryState *qs;
756 BlockNumber first_posting; /* see prism_leaf_head_blkno */
757 uint32_t nlist;
758 Dimension dim;
759 bool cosine;
760 MemoryContext tmp_ctx;
761 double *sums; /* [tile * dim], indexed by leaf - tile_lo */
762 uint64_t *cnts; /* [tile] */
763 float *scratch; /* [dim] normalized copy for cosine */
764 uint32_t tile_lo;
765 uint32_t tile_hi;
766 } RefineHeadState;
767
768 static void
769 60000 refine_head_cb(
770 Relation index,
771 ItemPointer tid,
772 Datum *values,
773 bool *isnull,
774 bool tuple_is_alive,
775 void *state)
776 {
777 60000 RefineHeadState *rs = (RefineHeadState *)state;
778
779 60000 (void)index;
780 60000 (void)tid;
781 60000 (void)tuple_is_alive;
782
783
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 60000 times.
60000 if (isnull[0])
784 ✗ return;
785
786 60000 MemoryContext old_ctx = MemoryContextSwitchTo(rs->tmp_ctx);
787
788 60000 const float *vin = Vec32ToRef(DatumGetVec32(values[0])).data;
789 60000 uint32_t idx;
790 120000 const float *v = prism_refine_route_row(
791 60000 rs->qs,
792 rs->first_posting,
793 vin,
794 60000 rs->dim,
795 60000 rs->cosine,
796 rs->scratch,
797 rs->tile_lo,
798 rs->tile_hi,
799 &idx);
800
2/2
✓ Branch 0 taken 36000 times.
✓ Branch 1 taken 24000 times.
60000 if (v != NULL)
801 {
802 36000 double *sum = rs->sums + (size_t)idx * rs->dim;
803
2/2
✓ Branch 0 taken 2304000 times.
✓ Branch 1 taken 36000 times.
2340000 for (Dimension j = 0; j < rs->dim; j++)
804 2304000 sum[j] += v[j];
805 36000 rs->cnts[idx]++;
806 }
807
808 60000 MemoryContextSwitchTo(old_ctx);
809 60000 MemoryContextReset(rs->tmp_ctx);
810 }
811
812 static void
813 3 serial_refine_heads(
814 PrismBuildState *bs,
815 PrismHeadWriteCtx *headctx,
816 PrismQueryState *qs,
817 BlockNumber first_posting,
818 uint32_t nlist)
819 {
820 3 Dimension dim = bs->params.dim;
821
822 3 uint64_t cap_bytes =
823 3 Min((uint64_t)maintenance_work_mem * 1024, (uint64_t)MaxAllocSize);
824
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
3 uint32_t tile = prism_refine_tile_leaves(nlist, dim, cap_bytes);
825
826 12 RefineHeadState rs = {
827 .qs = qs,
828 .first_posting = first_posting,
829 .dim = dim,
830 3 .cosine = (bs->params.metric == DISTANCE_COSINE),
831 3 .tmp_ctx = bs->tmp_ctx,
832 3 .sums = palloc((size_t)tile * dim * sizeof(double)),
833 3 .cnts = palloc((size_t)tile * sizeof(uint64_t)),
834 3 .scratch = palloc((size_t)dim * sizeof(float)),
835 };
836
837
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
8 for (uint32_t lo = 0; lo < nlist; lo += tile)
838 {
839 5 uint32_t hi = Min(lo + tile, nlist);
840 5 rs.tile_lo = lo;
841 5 rs.tile_hi = hi;
842 5 memset(rs.sums, 0, (size_t)(hi - lo) * dim * sizeof(double));
843 5 memset(rs.cnts, 0, (size_t)(hi - lo) * sizeof(uint64_t));
844
845 5 table_index_build_scan(
846 bs->heap,
847 bs->index,
848 bs->index_info,
849 true,
850 false,
851 refine_head_cb,
852 (void *)&rs,
853 NULL);
854
855 5 prism_refine_write_means(
856 5 rs.sums,
857 5 rs.cnts,
858 lo,
859 hi,
860 dim,
861 rs.scratch,
862 prism_write_leaf_head,
863 headctx);
864 }
865
866 3 pfree(rs.sums);
867 3 pfree(rs.cnts);
868 3 pfree(rs.scratch);
869 3 }
870
871 /*
872 * Serial build fallback, mirroring do_parallel_build's role for the
873 * non-parallel path. Streams the centroid tree straight to pages (no in-RAM
874 * tree, no O(nlist*dim) blob), then scans the heap once through build_callback
875 * (page-backed routing) to fill the posting lists.
876 *
877 * No in-RAM tree is materialized; the streamed tree's shape (leaf count +
878 * depth) comes back through out_nlist/out_tree_nlevels. Posting-list heads
879 * are formula-derived (prism_leaf_head_blkno), so no head array is returned.
880 * A heap with no indexable rows still builds: the sampler substitutes one
881 * synthetic sample and the result is a valid single-cluster index with an
882 * empty posting head. The serial path writes its own metadata page; the
883 * caller must not finalize again.
884 */
885 static void
886 204 do_serial_build(
887 PrismBuildState *bs,
888 VsStorage *storage,
889 uint64_t rabitq_seed,
890 uint32_t *out_nlist,
891 uint8_t *out_tree_nlevels,
892 float **out_global_mean,
893 double *out_heap_tuples,
894 double *out_indtuples,
895 double *out_soar_dupes)
896 {
897 204 const PrismBuildParams *p = &bs->params;
898 204 Dimension dim = p->dim;
899
900 204 *out_nlist = 0;
901 204 *out_tree_nlevels = 0;
902
903 204 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_SAMPLE);
904
905 204 uint32_t target_nlist = 0;
906 204 bool subsampled = false;
907 204 sample_for_build(bs, &target_nlist, &subsampled);
908
909 204 KMeansOptions km_opts = VS_KMEANS_OPTIONS_DEFAULT;
910 204 km_opts.algorithm = KMEANS_ALGO_LLOYD;
911 204 km_opts.nredo = p->kmeans_nredo;
912
913 /*
914 * Plan pass: cluster the sample once and discover the tree shape (leaf
915 * count, depth, centroid page count, leaf-centroid mean) without
916 * writing. Each node's clustering is recorded in a spillable blob store
917 * (BufFile-backed, so the resident cost stays one node) and the write
918 * pass below replays it instead of running k-means again -- the same
919 * single-clustering shape as the parallel build's subtree store.
920 * target_nlist (not the resolved leaf count) drives both passes.
921 */
922 204 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_KMEANS);
923 204 PrismBlobStore *node_store = prism_pbuild_blobstore_begin();
924 204 PrismStreamTreePlan plan;
925
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 204 times.
204 if (!prism_routing_tree_plan(
926 204 bs->samples,
927 204 (uint32_t)bs->nsamples,
928 dim,
929 target_nlist,
930 204 p->fan_out,
931 204 p->metric,
932 204 p->centroid_format,
933 &km_opts,
934 node_store,
935 &plan))
936 ✗ ereport(ERROR,
937 (errcode(ERRCODE_INTERNAL_ERROR),
938 errmsg("hierarchical k-means failed")));
939 204 prism_pbuild_blobstore_rewind(node_store);
940
941 204 uint32_t nlist = plan.nleaves;
942 204 bs->params.nlist = nlist;
943
944 /*
945 * Re-center the encoder on the leaf-centroid mean the plan pass reported
946 * (the write pass reproduces the identical tree). The in-RAM-tree build
947 * centers on the mean of the leaf centroids, not the per-vector sample
948 * mean, and the quantization quality of every centroid and posting code
949 * depends on this anchor.
950 */
951 /* The streamed pages encode against the leaf-centroid mean the plan
952 * pass accumulated. */
953 204 const size_t vec_nbytes = (size_t)dim * sizeof(float);
954
955 204 float *global_mean = palloc(vec_nbytes);
956
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 192 times.
204 memcpy(global_mean, plan.leaf_mean, vec_nbytes);
957
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 192 times.
204 if (p->metric == DISTANCE_COSINE)
958 12 vs_l2_normalize(global_mean, dim);
959 204 vs_free(plan.leaf_mean);
960 204 plan.leaf_mean = NULL;
961
962 204 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_SETUP);
963 204 RaBitQParams *rq_params = vs_rabitq_create(dim, rabitq_seed);
964
965 /* Centroid area is [first_centroid, first_posting); block 0 is metadata,
966 * followed by the mean's reference pages when it does not fit there. */
967
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 175 times.
204 BlockNumber first_centroid = prism_first_centroid_blkno(dim);
968 204 BlockNumber first_posting = first_centroid + plan.centroid_pages;
969
970 /*
971 * Head blocks are formula-derived (prism_leaf_head_blkno): a contiguous
972 * head region of nlist heads at a fixed stride. Pre-extend the relation to
973 * cover metadata + centroid + head region so the streaming write can place
974 * centroids at reserved blocks and each leaf's head page already exists
975 * when the write pass emits it; continuation pages are appended past the
976 * head region during prism_posting_build_lists. No O(nlist) reserve
977 * arrays.
978 */
979 204 prism_build_reserve_layout(
980 storage,
981 prism_leaf_head_blkno(
982 first_posting, nlist, prism_posting_reference_pages(dim)));
983
984 /*
985 * Write pass: stream the centroid pages (reserved blocks, post-order, root
986 * last) and, per leaf, its head page carrying pt_centroid. Both build and
987 * query then route page-backed over these centroid pages; the metadata
988 * page is written after the scan, when the tuple count is final.
989 */
990 204 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_CENTROID);
991
992 /* Exact internal-centroid collection for the build descent (see
993 * PrismExactCentroidCollector in index_build.h). */
994 204 PrismExactCentroidCollector exact_centroids = {0};
995 204 PrismExactCentroidCollector *collector =
996
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 168 times.
204 prism_exact_centroid_enabled(plan.nlevels, p->centroid_format)
997 ? &exact_centroids
998 : NULL;
999 32 if (collector != NULL)
1000
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
64 prism_exact_centroid_collector_init(
1001 collector,
1002 dim,
1003 p->centroid_format,
1004 first_centroid,
1005 plan.centroid_pages,
1006 prism_exact_centroid_budget((uint64_t)maintenance_work_mem),
1007
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
32 prism_exact_centroid_expected_slots(p->nlist, p->fan_out));
1008
1009 204 PrismHeadWriteCtx headctx;
1010 204 prism_head_write_ctx_init(
1011 204 &headctx, storage, rq_params, dim, p->fastscan, first_posting);
1012 408 BlockNumber root = prism_routing_tree_write(
1013 storage,
1014 204 (uint32_t)bs->nsamples,
1015 dim,
1016 204 p->metric,
1017 target_nlist,
1018 204 p->fan_out,
1019 204 p->centroid_format,
1020 rq_params,
1021 global_mean,
1022 node_store,
1023 first_posting,
1024 first_centroid,
1025 prism_write_leaf_head,
1026 &headctx,
1027 collector);
1028 204 prism_pbuild_blobstore_end(node_store);
1029 204 prism_head_write_ctx_cleanup(&headctx);
1030 204 pfree(bs->samples);
1031 204 bs->samples = NULL;
1032
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 204 times.
204 if (root == InvalidBlockNumber)
1033 ✗ ereport(ERROR,
1034 (errcode(ERRCODE_INTERNAL_ERROR),
1035 errmsg("streaming centroid write failed")));
1036
1037 /*
1038 * Page-backed routing: build a PrismIndexBase from the just-written index
1039 * so the scan routes each row exactly as the query/insert do
1040 * (prism_query_route over the centroid pages). Assignment uses no in-RAM
1041 * tree. The base is stack-local but outlives the scan (all within this
1042 * function); qs holds it by pointer until prism_query_state_cleanup below.
1043 */
1044 204 PrismIndexBase idx_base;
1045 /* Route the build for accuracy, not query speed: the build-time routing
1046 * constants rather than the query-tuned GUCs (see PRISM_BUILD_CENTROID_*
1047 * in posting_build.h). */
1048 408 prism_build_router_base_init(
1049 &idx_base,
1050 rq_params,
1051 storage,
1052 dim,
1053 204 (uint8_t)plan.nlevels,
1054 root,
1055 204 p->metric,
1056 204 p->centroid_format,
1057 prism_fastscan_bits,
1058 PRISM_BUILD_CENTROID_ERROR_SCALE,
1059 PRISM_BUILD_CENTROID_BEAM_SCALE,
1060 bs->params.fan_out,
1061 nlist,
1062 rabitq_seed,
1063 global_mean,
1064 204 palloc(vec_nbytes));
1065 /* Build-only accuracy hook: score the internal tree levels against the
1066 * exact centroids collected during the streaming write (the query and
1067 * insert paths never set this; see PrismExactInternalCentroids). */
1068 204 PrismExactInternalCentroids exact_view;
1069
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 172 times.
204 if (collector != NULL)
1070 {
1071 32 prism_exact_centroid_view(collector, &exact_view);
1072 32 idx_base.exact_internal = &exact_view;
1073 }
1074 204 prism_query_state_init(&bs->qs, &idx_base, 1, PRISM_SECONDARY_TOPK);
1075
1076 /*
1077 * When the sample was budget-limited AND the leaves are sample-thin
1078 * (below prism.leaf_refine_threshold samples per leaf -- a leaf's encode
1079 * reference is a sample mean whose error shrinks with its count, so
1080 * well-fed leaves gain nothing from the extra scan), refine each leaf's
1081 * encode reference on the full table (page-backed, bounded) before the
1082 * encode scan.
1083 */
1084
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 200 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 1 times.
204 if (subsampled && bs->nsamples >= bs->max_samples &&
1085
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
3 prism_leaf_refine_threshold > 0 &&
1086 3 (uint32_t)bs->nsamples / Max(nlist, 1) <
1087
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
3 (uint32_t)prism_leaf_refine_threshold)
1088 {
1089 3 instr_time t_ref_start;
1090 3 INSTR_TIME_SET_CURRENT(t_ref_start);
1091 3 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_REFINE);
1092
1093 3 PrismHeadWriteCtx rhead;
1094 3 prism_head_write_ctx_init(
1095 3 &rhead, storage, rq_params, dim, p->fastscan, first_posting);
1096 3 serial_refine_heads(bs, &rhead, &bs->qs, first_posting, nlist);
1097 3 prism_head_write_ctx_cleanup(&rhead);
1098
1099 3 instr_time t_ref_end;
1100 3 INSTR_TIME_SET_CURRENT(t_ref_end);
1101 3 INSTR_TIME_SUBTRACT(t_ref_end, t_ref_start);
1102
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
3 elog(LOG,
1103 "prism: page-backed leaf refinement %.1fms -- structure from a "
1104 "%d-sample subsample, %u leaf encode references refined on the "
1105 "full "
1106 "table",
1107 INSTR_TIME_GET_MILLISEC(t_ref_end),
1108 bs->max_samples,
1109 nlist);
1110 }
1111
1112 /*
1113 * Cluster-keyed sorter: the scan streams every posting entry here (keyed
1114 * by cluster); prism_posting_build_lists then reads them back grouped by
1115 * cluster and builds each list with a single resident page builder. Memory
1116 * is bounded by maintenance_work_mem (the sort spills if exceeded),
1117 * so no O(nlist) array of resident builders exists.
1118 *
1119 * region == NULL: a plain, non-parallel cluster-keyed sort. Same seam the
1120 * parallel leader uses.
1121 */
1122 204 bs->rq_params = rq_params;
1123 204 bs->sorter = prism_pbuild_sort_begin(
1124 NULL,
1125 NULL,
1126 0,
1127 0,
1128 true,
1129 204 (uint32_t)prism_posting_entry_size(dim),
1130 maintenance_work_mem);
1131
1132 /* Shared route+encode+emit context (same helper the parallel workers use).
1133 */
1134 204 prism_build_route_ctx_init(
1135 &bs->route,
1136 &bs->qs,
1137 bs->sorter,
1138 rq_params,
1139 storage,
1140 first_posting,
1141 dim,
1142 204 p->soar_lambda,
1143 204 p->boundary_epsilon);
1144
1145 /* Reports the scan phase and fires the "prism-build-load" test hook (see
1146 * the seam): lets an isolation test observe the in-progress serial build.
1147 */
1148 204 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_SCAN);
1149
1150 204 instr_time t_serial_start;
1151 204 INSTR_TIME_SET_CURRENT(t_serial_start);
1152
1153 204 double heap_tuples = table_index_build_scan(
1154 bs->heap,
1155 bs->index,
1156 bs->index_info,
1157 true,
1158 true,
1159 build_callback,
1160 (void *)bs,
1161 NULL);
1162
1163 204 instr_time t_serial_scan;
1164 204 INSTR_TIME_SET_CURRENT(t_serial_scan);
1165 204 INSTR_TIME_SUBTRACT(t_serial_scan, t_serial_start);
1166
1167 /*
1168 * Sort entries by cluster, then build each cluster's posting list with a
1169 * single resident page builder, in cluster order. Empty clusters still get
1170 * an (empty) head page, matching the previous per-cluster behavior.
1171 */
1172 204 prism_build_report_phase(bs->prog, PRISM_BUILD_PHASE_POSTING);
1173 204 prism_posting_build_lists(
1174 bs->sorter,
1175 storage,
1176 nlist,
1177 dim,
1178 204 p->fastscan,
1179 rq_params,
1180 first_posting);
1181 204 bs->sorter = NULL; /* ended by prism_posting_build_lists */
1182
1183 204 bs->indtuples = bs->route.indtuples;
1184 204 bs->soar_dupes = bs->route.soar_dupes;
1185 204 prism_build_route_ctx_cleanup(&bs->route);
1186 204 prism_query_state_cleanup(&bs->qs);
1187
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 172 times.
204 if (collector != NULL)
1188 32 prism_exact_centroid_collector_cleanup(collector);
1189
1190
1/2
✓ Branch 1 taken 204 times.
✗ Branch 2 not taken.
204 elog(LOG,
1191 "prism: serial build scan %.1fms, "
1192 "%.0f tuples, %.0f soar_dupes, %u clusters",
1193 INSTR_TIME_GET_MILLISEC(t_serial_scan),
1194 bs->indtuples,
1195 bs->soar_dupes,
1196 nlist);
1197
1198 /* Metadata page (needs the final tuple count). first_centroid is the root
1199 * block, which the streaming write placed last. This path finalizes the
1200 * centroid pages + metadata itself, so the caller's tail does WAL only. */
1201 204 write_meta_page(
1202 storage,
1203 dim,
1204 204 (uint8_t)plan.nlevels,
1205 204 (uint8_t)p->fan_out,
1206 root,
1207 first_posting,
1208 plan.centroid_pages,
1209 nlist,
1210 204 p->centroid_format,
1211 204 p->metric,
1212 rabitq_seed,
1213 204 p->fastscan,
1214 global_mean);
1215 204 *out_nlist = nlist;
1216 204 *out_tree_nlevels = (uint8_t)plan.nlevels;
1217 204 *out_global_mean = global_mean;
1218 204 *out_heap_tuples = heap_tuples;
1219 204 *out_indtuples = bs->indtuples;
1220 204 *out_soar_dupes = bs->soar_dupes;
1221 204 }
1222
1223 /* ----------------------------------------------------------------
1224 * Main build entry point
1225 * ---------------------------------------------------------------- */
1226
1227 IndexBuildResult *
1228 258 prism_build(Relation heap, Relation index, struct IndexInfo *index_info)
1229 {
1230 /*
1231 * Refuse expression indexes.
1232 *
1233 * Rerank fetches the heap tuple and reads the indexed value with
1234 * slot_getattr(slot, indkey.values[0]) -- and for an expression index
1235 * PostgreSQL stores 0 there, keeping the expression tree in indexprs
1236 * instead. attnum 0 reads tts_values[-1] and hands the garbage to
1237 * pg_detoast_datum, which segfaults the backend (measured: the crash is
1238 * in pg_rerank_readstream, not theoretical).
1239 *
1240 * Supporting them means doing at rerank time what the build already does
1241 * -- evaluating the index expression over the fetched tuple -- which
1242 * needs an ExprState and ExprContext live across the whole rerank loop
1243 * and an evaluation per candidate, in the hottest path there is. Worth
1244 * doing; not worth smuggling in as a crash fix.
1245 */
1246
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 257 times.
258 if (index->rd_index->indkey.values[0] == InvalidAttrNumber)
1247
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
1 ereport(ERROR,
1248 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1249 errmsg("prism indexes do not support index expressions"),
1250 errhint("Index the column directly, or materialize the "
1251 "expression into a column and index that.")));
1252
1253 257 MemoryContext caller_ctx = CurrentMemoryContext;
1254 257 MemoryContext build_ctx = AllocSetContextCreate(
1255 CurrentMemoryContext, "prism build", ALLOCSET_DEFAULT_SIZES);
1256 257 MemoryContextSwitchTo(build_ctx);
1257
1258 /* 1. Initialize build state and resolve parameters */
1259 257 PrismBuildState bs = {0};
1260 257 bs.heap = heap;
1261 257 bs.index = index;
1262 257 bs.index_info = index_info;
1263 257 bs.build_ctx = build_ctx;
1264 257 bs.tmp_ctx = AllocSetContextCreate(
1265 build_ctx, "prism build tuple", ALLOCSET_DEFAULT_SIZES);
1266
1267 257 double est_rows;
1268 257 resolve_build_params(heap, index, &bs.params, &est_rows);
1269
1270 250 const PrismBuildParams *p = &bs.params;
1271 250 Dimension dim = p->dim;
1272 250 uint64_t rabitq_seed = VS_RABITQ_BUILD_SEED;
1273
1274 /* Resolved once, directly -- no metadata page exists yet for the
1275 * per-backend cache to read. The per-tuple callbacks follow the pointer.
1276 */
1277 250 bs.input = vec32_access(prism_index_type_info(index), dim, build_ctx);
1278
1279 /*
1280 * Build introspection: one reporting context the serial and parallel paths
1281 * share, so pg_stat_progress_create_index advances through the same phases
1282 * either way and (when prism.log_build_stats is on) per-phase stats land
1283 * in the server log.
1284 */
1285 250 PrismBuildStats stats = {0};
1286 250 PrismBuildProgress prog;
1287 250 prism_build_progress_begin(
1288 &prog,
1289 250 index_info->ii_ParallelWorkers > 0,
1290 prism_log_build_stats,
1291 build_ctx,
1292 &stats,
1293 est_rows);
1294 250 bs.prog = &prog;
1295
1296 250 VsPgStorage storage;
1297 250 vs_pg_storage_init(&storage, index, NULL, p->metric);
1298 250 storage.build_mode = true;
1299
1300 250 double heap_tuples = 0;
1301 250 double indtuples = 0;
1302 250 double soar_dupes = 0;
1303 250 float *global_mean = NULL;
1304 /* Posting-area start block, surfaced by the parallel build so the finalize
1305 * can record it in the metadata page (vacuum skips the centroid region).
1306 */
1307 250 BlockNumber meta_first_posting = InvalidBlockNumber;
1308
1309 /* The streamed tree's shape, from whichever build path ran (0 leaves =
1310 * empty heap). The serial path writes its own metadata page; the
1311 * parallel path leaves it for the finalize below (it needs the final
1312 * tuple count). */
1313 250 uint32_t built_nlist = 0;
1314 250 uint8_t built_nlevels = 0;
1315
1316 /* Try parallel build first (sampling + k-means + posting) */
1317 250 bool did_parallel = false;
1318
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 203 times.
250 if (index_info->ii_ParallelWorkers > 0)
1319 {
1320 /*
1321 * Estimate the leaf count up front.
1322 *
1323 * A parallel build allocates its shared-memory (DSM) regions before
1324 * the workers run, and DSM segments cannot be resized once created.
1325 * Several of those regions are sized per leaf (centroids, posting
1326 * heads, per-cluster assignment state), so the leader has to commit to
1327 * a leaf count at allocation time — but the real count is only known
1328 * after k-means clusters the sample, which happens inside the
1329 * workers. hkmeans targets `nlist` leaves at this fan_out but can
1330 * produce up to fan_out^nlevels of them, so we size every per-leaf
1331 * region for that worst-case upper bound here, then narrow to the
1332 * actual built leaf count below.
1333 *
1334 * nlist and fan_out are already resolved (resolve_build_params).
1335 */
1336 47 uint32_t requested_nlist = p->nlist;
1337 47 uint32_t max_nlist = prism_max_nlist(p->nlist, p->fan_out);
1338
1339 47 bs.params.nlist = max_nlist;
1340
1341 47 PrismBuildConfig cfg = {
1342 47 .dim = bs.params.dim,
1343 47 .metric = bs.params.metric,
1344 47 .centroid_format = bs.params.centroid_format,
1345 .nlist = bs.params.nlist,
1346 47 .fan_out = bs.params.fan_out,
1347 47 .soar_lambda = bs.params.soar_lambda,
1348 47 .boundary_epsilon = bs.params.boundary_epsilon,
1349 47 .fastscan = bs.params.fastscan,
1350 47 .concurrent = index_info->ii_Concurrent,
1351 };
1352
1353 /* do_parallel_build reports every phase through the seam (sampling,
1354 * k-means, subtrees, refine, setup, scan, posting) and fires
1355 * the per-phase test hooks, so no phase is set here. */
1356 47 did_parallel = do_parallel_build(
1357 heap,
1358 index,
1359 index_info,
1360 &cfg,
1361 &storage.base,
1362 &prog,
1363 &built_nlist,
1364 &built_nlevels,
1365 &heap_tuples,
1366 &indtuples,
1367 &soar_dupes,
1368 /* do_parallel_build routes page-backed: it wrote the centroid
1369 * + head pages into the index before the scan and returns the
1370 * global mean it used (so the metadata write below matches).
1371 * It does NOT write the metadata page (needs the final tuple
1372 * count), so the finalize below still runs. */
1373 &global_mean,
1374 /* Surfaced for the metadata page: the posting-area start block
1375 * lets vacuum skip the centroid region without scanning it. */
1376 &meta_first_posting);
1377
1378
3/4
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 45 times.
46 if (did_parallel && built_nlist == 0)
1379 {
1380 /*
1381 * The parallel path found no indexable rows (a non-empty heap
1382 * whose rows are all dead or NULL can reach it). It wrote no
1383 * pages for the zero-leaf layout, so the serial fallback below
1384 * -- whose sampler substitutes a synthetic sample and emits a
1385 * valid single-cluster index -- starts from a clean relation.
1386 * Enforced at runtime: falling back onto a relation the
1387 * parallel path already wrote to would corrupt the index.
1388 */
1389 ✗ if (RelationGetNumberOfBlocks(index) > 1)
1390 ✗ ereport(ERROR,
1391 (errcode(ERRCODE_INTERNAL_ERROR),
1392 errmsg("parallel index build reported no leaves "
1393 "but wrote %u pages",
1394 RelationGetNumberOfBlocks(index))));
1395
1396 /* The zero-leaf return leaves out_global_mean NULL today;
1397 * free defensively so a future change to that contract
1398 * cannot leak the parallel mean when the serial build
1399 * replaces it. */
1400 ✗ if (global_mean != NULL)
1401 {
1402 ✗ pfree(global_mean);
1403 ✗ global_mean = NULL;
1404 }
1405 did_parallel = false;
1406 }
1407
1408 45 if (did_parallel && built_nlist > 0)
1409 45 bs.params.nlist = built_nlist;
1410 else if (!did_parallel)
1411 {
1412 /* The worst-case bound exists only to size the parallel DSM
1413 * regions. The serial fallback clusters from scratch, so it must
1414 * target the requested partition count, not the sizing bound. */
1415 1 bs.params.nlist = requested_nlist;
1416 }
1417 }
1418
1419 46 if (!did_parallel)
1420 {
1421 /* Serial fallback: sample, cluster, build. Always emits at least
1422 * one leaf, even when the heap has no indexable tuples. */
1423 204 do_serial_build(
1424 &bs,
1425 &storage.base,
1426 rabitq_seed,
1427 &built_nlist,
1428 &built_nlevels,
1429 &global_mean,
1430 &heap_tuples,
1431 &indtuples,
1432 &soar_dupes);
1433 }
1434
1435 /* Both paths produce at least one leaf now: a heap with no indexable
1436 * rows builds a single-cluster index around a synthetic centroid (see
1437 * sample_for_build), so inserts route and scans return empty.
1438 * Enforced at runtime: finalizing a zero-leaf layout would produce a
1439 * broken index. */
1440
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 249 times.
249 if (built_nlist == 0)
1441 ✗ ereport(ERROR,
1442 (errcode(ERRCODE_INTERNAL_ERROR),
1443 errmsg("index build produced no clusters")));
1444
1445
2/2
✓ Branch 0 taken 147 times.
✓ Branch 1 taken 102 times.
249 if (soar_dupes > 0)
1446
1/2
✓ Branch 1 taken 147 times.
✗ Branch 2 not taken.
147 elog(LOG,
1447 "prism: replicated %.0f vectors "
1448 "(%.1f%% of %.0f, lambda=%.4g)",
1449 soar_dupes,
1450 100.0 * soar_dupes / indtuples,
1451 indtuples,
1452 bs.params.soar_lambda);
1453
1454 /* Finalize: write centroid pages + metadata (unless the build path already
1455 * did — the serial page-backed path writes them itself), then WAL-log the
1456 * whole index. */
1457 {
1458
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 204 times.
249 if (did_parallel)
1459 {
1460 /* The parallel build wrote its centroid + head pages before the
1461 * scan but left the metadata page for here (it needs the final
1462 * tuple count); the serial path wrote its own. first_posting
1463 * comes from the build and lets vacuum skip the centroid region
1464 * without scanning it. */
1465
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 44 times.
45 BlockNumber fc = prism_first_centroid_blkno(dim);
1466
1467
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 45 times.
45 Assert(global_mean != NULL);
1468
1469 45 write_meta_page(
1470 &storage.base,
1471 dim,
1472 built_nlevels,
1473 45 (uint8_t)p->fan_out,
1474 fc,
1475 meta_first_posting,
1476 45 meta_first_posting - prism_first_centroid_blkno(dim),
1477 built_nlist,
1478 45 p->centroid_format,
1479 45 p->metric,
1480 rabitq_seed,
1481 45 p->fastscan,
1482 global_mean);
1483 }
1484 249 prism_build_report_phase(&prog, PRISM_BUILD_PHASE_WAL);
1485 /*
1486 * WAL-log the built pages only when the relation is WAL-logged, the
1487 * same guard every core index AM (GiST/GIN/SP-GiST) applies here.
1488 * Temp relations and same-transaction builds under wal_level=minimal
1489 * skip this: emitting WAL for them is wasted volume, and doing so
1490 * against a session-local temp relfilenode is something no core AM
1491 * does. (Unlogged tables never reach this path -- their build is
1492 * rejected up front in prism_buildempty.)
1493 *
1494 * page_std = false, and it has to be. The flag promises the standard
1495 * page layout, which lets the full-page image omit everything between
1496 * pd_lower and pd_upper as free space. prism keeps its entries there
1497 * -- pd_lower stays at SizeOfPageHeaderData and pd_upper at pd_special
1498 * on a posting page -- so a standard image would carry the header and
1499 * the opaque and nothing else. The primary would be fine, since its
1500 * pages are already on disk; a streaming standby, which has only the
1501 * WAL, would restore every page with its entries zeroed while the
1502 * opaque still reported them present. See t/001_replication.pl.
1503 *
1504 * The insert path solves the same problem the other way, by covering
1505 * the hole (pd_lower = pd_upper) before GenericXLog; that is not an
1506 * option here because centroid pages use pd_lower for their own
1507 * capacity accounting.
1508 */
1509
5/8
✓ Branch 0 taken 247 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 245 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
249 if (RelationNeedsWAL(index))
1510 245 log_newpage_range(
1511 index,
1512 MAIN_FORKNUM,
1513 0,
1514 RelationGetNumberOfBlocks(index),
1515 false);
1516 }
1517
1518 /* Flush the final phase timing + emit the build summary (heap_ctx is read
1519 * here, so this must run before build_ctx is deleted below). */
1520 249 prism_build_progress_end(&prog);
1521
1522 /* Cleanup */
1523
1524 249 MemoryContextSwitchTo(caller_ctx);
1525 249 MemoryContextDelete(build_ctx);
1526
1527 249 IndexBuildResult *result = palloc0(sizeof(IndexBuildResult));
1528 249 result->heap_tuples = heap_tuples;
1529 249 result->index_tuples = indtuples;
1530 249 return result;
1531 }
1532
1533 char *
1534 7 prism_buildphasename(int64 phasenum)
1535 {
1536 /* Single source of truth for the phase names (index/build_progress.c),
1537 * shared with the build logs so the two never drift. */
1538 7 return unconstify(char *, prism_build_phase_name((int)phasenum));
1539 }
1540