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