| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * index_build.c - Shared index build utilities | ||
| 6 | * | ||
| 7 | * Generic helpers for building prism indexes, usable from both | ||
| 8 | * the PostgreSQL IAM build and the standalone CLI. | ||
| 9 | */ | ||
| 10 | |||
| 11 | #include <inttypes.h> | ||
| 12 | #include <math.h> | ||
| 13 | #include <string.h> | ||
| 14 | |||
| 15 | #include "algo/kmeans.h" | ||
| 16 | #include "algo/vecops.h" | ||
| 17 | #include "core/log.h" | ||
| 18 | #include "core/memory.h" | ||
| 19 | #include "index/centroid_build.h" | ||
| 20 | #include "index/index_build.h" | ||
| 21 | #include "index/parallel_build.h" /* PrismBlobStore seam (plan/write replay) */ | ||
| 22 | #include "index/posting_page.h" | ||
| 23 | #include "quant/fastscan.h" | ||
| 24 | |||
| 25 | /* ---------------------------------------------------------------- | ||
| 26 | * Exact internal-centroid collection — see index_build.h | ||
| 27 | * ---------------------------------------------------------------- */ | ||
| 28 | |||
| 29 | /* | ||
| 30 | * A collection is the collector's sealed output: the exact centroids | ||
| 31 | * of the internal tree nodes, keyed by where each centroid's | ||
| 32 | * compressed twin sits on disk (centroid page, entry index on that | ||
| 33 | * page). Serialized as one contiguous allocation with no internal | ||
| 34 | * pointers, so it can be handed across the parallel-build seam (a DSM | ||
| 35 | * segment under PostgreSQL, a plain heap allocation standalone) and | ||
| 36 | * consumed in place by any backend that maps it. | ||
| 37 | * | ||
| 38 | * +--------------------------------+ | ||
| 39 | * | ExactCentroidCollectionHeader | base, npages, nslots, dim | ||
| 40 | * +--------------------------------+ | ||
| 41 | * | uint32_t page_off[npages] | slot base per page, or NONE | ||
| 42 | * +--------------------------------+ | ||
| 43 | * | float cents[nslots * dim] | centroids, densely packed | ||
| 44 | * +--------------------------------+ | ||
| 45 | * | ||
| 46 | * The collection covers the centroid-page region [base, base + | ||
| 47 | * npages): a | ||
| 48 | * page's page_off element is indexed by its offset from the starting | ||
| 49 | * page (blkno - base). Pages that carry internal entries hold the | ||
| 50 | * index of their first centroid in cents[]; their entries then map | ||
| 51 | * 1:1 and in page-entry order to the following slots, so entry i of | ||
| 52 | * page b scores against cents + (page_off[b - base] + i) * dim. Slot | ||
| 53 | * ranges of different pages are disjoint, but not ordered: cents[] is | ||
| 54 | * appended in tree-write order (post-order serial, per-subtree | ||
| 55 | * parallel), not block order. Leaf-level pages — collection skips | ||
| 56 | * them — hold PRISM_EXACT_INTERNAL_NONE instead. | ||
| 57 | * | ||
| 58 | * An empty collection (collecting off or over budget) is just the header | ||
| 59 | * with npages = 0 and base = InvalidBlockNumber, which no block can | ||
| 60 | * match — the consumer's scoring hook stays inert. nslots and dim are | ||
| 61 | * self-description (sizing and debugging); the view reads only base | ||
| 62 | * and npages, and slot extents come from page_off plus the pages' own | ||
| 63 | * entry counts. | ||
| 64 | * | ||
| 65 | * Lifecycle: the LEADER produces it — it alone streams the tree to | ||
| 66 | * pages, collecting into PrismExactCentroidCollector as it writes — | ||
| 67 | * then sizes and fills the collection from the collector and publishes it | ||
| 68 | * before the tree-ready barrier. The WORKERS attach after that | ||
| 69 | * barrier and wrap it in a PrismExactInternalCentroids view to score | ||
| 70 | * the internal tree levels while routing rows to their posting lists | ||
| 71 | * (and again in the refine pass); they only ever read it. The collection's | ||
| 72 | * memory is deliberately not context-managed and not the collector's: | ||
| 73 | * under PostgreSQL it is a DSM segment (process-shared, refcounted by | ||
| 74 | * the resource-owner machinery — a memory context is process-private | ||
| 75 | * and could not cross the seam), standalone a heap allocation the | ||
| 76 | * leader frees after the threads join. That split also lets the | ||
| 77 | * leader clean up the collector right after serializing, halving the | ||
| 78 | * peak, while the collection lives on until the last worker detaches. | ||
| 79 | * The serial build skips serialization entirely: same process, so its view | ||
| 80 | * points straight into the collector's arrays. | ||
| 81 | */ | ||
| 82 | typedef struct ExactCentroidCollectionHeader | ||
| 83 | { | ||
| 84 | BlockNumber base; | ||
| 85 | uint32_t npages; | ||
| 86 | uint32_t nslots; | ||
| 87 | uint32_t dim; | ||
| 88 | } ExactCentroidCollectionHeader; | ||
| 89 | |||
| 90 | /* Fallback initial cents[] capacity (slots) when the caller passes no | ||
| 91 | * expected_slots pre-size; add_node doubles from here. Covers a | ||
| 92 | * typical two-level tree (fan_out + 1 nodes) without regrowing while | ||
| 93 | * staying well under any realistic budget. */ | ||
| 94 | #define CENTROID_COLLECTOR_INIT_CAPACITY 256 | ||
| 95 | |||
| 96 | void | ||
| 97 | 101 | prism_exact_centroid_collector_init( | |
| 98 | PrismExactCentroidCollector *c, | ||
| 99 | Dimension dim, | ||
| 100 | PrismCentroidFormat fmt, | ||
| 101 | BlockNumber base, | ||
| 102 | uint32_t npages, | ||
| 103 | uint64_t max_bytes, | ||
| 104 | uint64_t expected_slots) | ||
| 105 | { | ||
| 106 | 101 | memset(c, 0, sizeof(*c)); | |
| 107 | 101 | c->dim = dim; | |
| 108 | 101 | c->base = base; | |
| 109 | 101 | c->npages = npages; | |
| 110 | 101 | c->stride = prism_centroid_max_entries_fmt(dim, fmt); | |
| 111 | /* Every allocation goes to the collector's dedicated child context | ||
| 112 | * (see the ownership contract on PrismExactCentroidCollector). */ | ||
| 113 | 101 | c->ctx = vs_memctx_create(vs_memctx_current(), "vs exact centroids"); | |
| 114 | 101 | c->page_off = vs_memctx_alloc(c->ctx, (size_t)npages * sizeof(uint32_t)); | |
| 115 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 51 times.
|
101 | memset(c->page_off, 0xFF, (size_t)npages * sizeof(uint32_t)); |
| 116 | 101 | c->max_bytes = max_bytes; | |
| 117 | /* Pre-size to the caller's estimate so growth is a rounding case, | ||
| 118 | * never past what the budget admits; an over-budget estimate is | ||
| 119 | * pointless to allocate in full -- collection will latch overflowed | ||
| 120 | * at the boundary anyway. */ | ||
| 121 | 50 | uint64_t cap = expected_slots > 0 ? expected_slots | |
| 122 |
2/2✓ Branch 0 taken 48 times.
✓ Branch 1 taken 53 times.
|
101 | : CENTROID_COLLECTOR_INIT_CAPACITY; |
| 123 | 101 | uint64_t max_cap = max_bytes / ((uint64_t)dim * sizeof(float)); | |
| 124 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 48 times.
|
101 | if (cap > max_cap) |
| 125 | 2 | cap = max_cap; | |
| 126 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 50 times.
|
101 | if (cap == 0) |
| 127 | ✗ | cap = 1; | |
| 128 | 101 | c->cap = (uint32_t)cap; | |
| 129 | 101 | c->cents = vs_memctx_alloc(c->ctx, (size_t)c->cap * dim * sizeof(float)); | |
| 130 | 101 | } | |
| 131 | |||
| 132 | /* | ||
| 133 | * Ensure cents[] holds at least total slots. Reached only when the | ||
| 134 | * init pre-size undershot (per-level rounding in the estimate): grow | ||
| 135 | * geometrically — a fixed-step policy would copy O(n^2) bytes over | ||
| 136 | * the collection's lifetime, doubling copies less than 2x the final | ||
| 137 | * size in total — and clamp the capacity to the budget so the | ||
| 138 | * allocation never overshoots what the caller's budget check admits | ||
| 139 | * (that check guarantees the clamped capacity still fits). | ||
| 140 | */ | ||
| 141 | static void | ||
| 142 | 281 | exact_centroid_collector_reserve( | |
| 143 | PrismExactCentroidCollector *c, uint32_t total) | ||
| 144 | { | ||
| 145 |
2/2✓ Branch 0 taken 86 times.
✓ Branch 1 taken 195 times.
|
281 | if (total <= c->cap) |
| 146 | 76 | return; | |
| 147 | |||
| 148 | 20 | uint64_t max_cap = c->max_bytes / ((uint64_t)c->dim * sizeof(float)); | |
| 149 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
|
20 | Assert(total <= max_cap); |
| 150 | 20 | uint64_t new_cap = (uint64_t)c->cap * 2; | |
| 151 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 20 times.
|
24 | while (new_cap < total) |
| 152 | 4 | new_cap *= 2; | |
| 153 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
|
20 | if (new_cap > max_cap) |
| 154 | ✗ | new_cap = max_cap; | |
| 155 | |||
| 156 | /* Grow inside the collector's own context, not the streaming | ||
| 157 | * scratch context this is called under (that scratch dies at | ||
| 158 | * the end of the write pass, while the collector must survive | ||
| 159 | * until after the encode scan and the refine pass). The old | ||
| 160 | * array is freed eagerly (a no-op on the standalone arena) so | ||
| 161 | * both generations are never held at once. */ | ||
| 162 | 10 | float *grown = | |
| 163 | 20 | vs_memctx_alloc(c->ctx, (size_t)new_cap * c->dim * sizeof(float)); | |
| 164 | 20 | memcpy(grown, c->cents, (size_t)c->nslots * c->dim * sizeof(float)); | |
| 165 | 20 | vs_free(c->cents); | |
| 166 | 20 | c->cents = grown; | |
| 167 | 20 | c->cap = (uint32_t)new_cap; | |
| 168 | } | ||
| 169 | |||
| 170 | void | ||
| 171 | 294 | prism_exact_centroid_collector_add_node( | |
| 172 | PrismExactCentroidCollector *c, | ||
| 173 | BlockNumber first_blk, | ||
| 174 | const float *cents, | ||
| 175 | uint32_t n) | ||
| 176 | { | ||
| 177 |
3/4✓ Branch 0 taken 294 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 198 times.
✓ Branch 3 taken 96 times.
|
294 | if (n == 0 || c->overflowed) |
| 178 | 2 | return; | |
| 179 | |||
| 180 | /* Enforce the collection budget: degrade to an empty (inert) | ||
| 181 | * collection rather than grow without bound. The arrays are dead | ||
| 182 | * once the flag latches (every consumer checks it first), so | ||
| 183 | * release them right away — the encode scan that follows is the | ||
| 184 | * build's memory peak. */ | ||
| 185 | 284 | uint64_t need = ((uint64_t)c->nslots + n) * c->dim * sizeof(float); | |
| 186 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 281 times.
|
284 | if (need > c->max_bytes) |
| 187 | { | ||
| 188 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
3 | vs_warn("exact centroid collection over budget (needs more " |
| 189 | "than %" PRIu64 " of %" PRIu64 " bytes); build descent " | ||
| 190 | "falls back to estimated internal scoring — consider " | ||
| 191 | "raising the build memory budget", | ||
| 192 | need, | ||
| 193 | c->max_bytes); | ||
| 194 | 3 | c->overflowed = true; | |
| 195 | 3 | prism_exact_centroid_collector_cleanup(c); | |
| 196 | 3 | return; | |
| 197 | } | ||
| 198 | |||
| 199 | 281 | exact_centroid_collector_reserve(c, c->nslots + n); | |
| 200 | |||
| 201 | /* The node's entries pack stride per page from first_blk — the same | ||
| 202 | * packing every centroid writer uses (each node starts on a fresh | ||
| 203 | * reserved page). Record each page's slot base and append its | ||
| 204 | * centroids in page-entry order. */ | ||
| 205 | 281 | uint32_t npages_node = (n + c->stride - 1) / c->stride; | |
| 206 |
2/2✓ Branch 0 taken 281 times.
✓ Branch 1 taken 281 times.
|
562 | for (uint32_t p = 0; p < npages_node; p++) |
| 207 | { | ||
| 208 | 281 | BlockNumber blk = first_blk + p; | |
| 209 |
2/4✓ Branch 0 taken 281 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 281 times.
|
281 | if (blk < c->base || blk - c->base >= c->npages) |
| 210 | { | ||
| 211 | /* Plan/write divergence: a node landed outside the planned | ||
| 212 | * centroid region. Degrade to inert rather than write | ||
| 213 | * page_off out of bounds in release builds. */ | ||
| 214 | ✗ | Assert(false); | |
| 215 | c->overflowed = true; | ||
| 216 | prism_exact_centroid_collector_cleanup(c); | ||
| 217 | return; | ||
| 218 | } | ||
| 219 | |||
| 220 | 281 | uint32_t count = n - p * c->stride; | |
| 221 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 86 times.
|
281 | if (count > c->stride) |
| 222 | ✗ | count = c->stride; | |
| 223 | |||
| 224 | 281 | c->page_off[blk - c->base] = c->nslots; | |
| 225 | 281 | memcpy(c->cents + (size_t)c->nslots * c->dim, | |
| 226 | 281 | cents + (size_t)p * c->stride * c->dim, | |
| 227 | 281 | (size_t)count * c->dim * sizeof(float)); | |
| 228 | 281 | c->nslots += count; | |
| 229 | } | ||
| 230 | } | ||
| 231 | |||
| 232 | void | ||
| 233 | 108 | prism_exact_centroid_collector_cleanup(PrismExactCentroidCollector *c) | |
| 234 | { | ||
| 235 | /* Everything the collector allocated lives in its dedicated | ||
| 236 | * context: one delete releases it all, exactly once (idempotent — | ||
| 237 | * a second call is a no-op). Callers must not run this until the | ||
| 238 | * last view consumer is done. */ | ||
| 239 |
2/2✓ Branch 0 taken 101 times.
✓ Branch 1 taken 7 times.
|
108 | if (c->ctx != NULL) |
| 240 | 101 | vs_memctx_delete(c->ctx); | |
| 241 | 108 | c->ctx = NULL; | |
| 242 | 108 | c->page_off = NULL; | |
| 243 | 108 | c->cents = NULL; | |
| 244 | 108 | } | |
| 245 | |||
| 246 | void | ||
| 247 | 38 | prism_exact_centroid_view( | |
| 248 | const PrismExactCentroidCollector *c, | ||
| 249 | PrismExactInternalCentroids *view) | ||
| 250 | { | ||
| 251 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 35 times.
|
38 | if (c->overflowed) |
| 252 | { | ||
| 253 | /* Inert view: a zero-page region matches no block. */ | ||
| 254 | 3 | view->cents = NULL; | |
| 255 | 3 | view->page_off = NULL; | |
| 256 | 3 | view->base = InvalidBlockNumber; | |
| 257 | 3 | view->npages = 0; | |
| 258 | 3 | return; | |
| 259 | } | ||
| 260 | 35 | view->cents = c->cents; | |
| 261 | 35 | view->page_off = c->page_off; | |
| 262 | 35 | view->base = c->base; | |
| 263 | 35 | view->npages = c->npages; | |
| 264 | } | ||
| 265 | |||
| 266 | uint64_t | ||
| 267 | 159 | prism_exact_centroid_collection_size(const PrismExactCentroidCollector *c) | |
| 268 | { | ||
| 269 |
4/4✓ Branch 0 taken 69 times.
✓ Branch 1 taken 90 times.
✓ Branch 2 taken 21 times.
✓ Branch 3 taken 48 times.
|
159 | if (c == NULL || c->overflowed) |
| 270 | 66 | return sizeof(ExactCentroidCollectionHeader); | |
| 271 | 19 | return sizeof(ExactCentroidCollectionHeader) + | |
| 272 | 67 | (uint64_t)c->npages * sizeof(uint32_t) + | |
| 273 | 67 | (uint64_t)c->nslots * c->dim * sizeof(float); | |
| 274 | } | ||
| 275 | |||
| 276 | void | ||
| 277 | 159 | prism_exact_centroid_collection_write( | |
| 278 | const PrismExactCentroidCollector *c, void *collection) | ||
| 279 | { | ||
| 280 | 159 | ExactCentroidCollectionHeader *hdr = (ExactCentroidCollectionHeader *) | |
| 281 | collection; | ||
| 282 | |||
| 283 |
4/4✓ Branch 0 taken 69 times.
✓ Branch 1 taken 90 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 67 times.
|
159 | if (c == NULL || c->overflowed) |
| 284 | { | ||
| 285 | /* Empty collection: a zero-page region matches no block, so the view | ||
| 286 | * built from it leaves the scoring hook inert. */ | ||
| 287 | 92 | hdr->base = InvalidBlockNumber; | |
| 288 | 92 | hdr->npages = 0; | |
| 289 | 92 | hdr->nslots = 0; | |
| 290 | 92 | hdr->dim = 0; | |
| 291 | 92 | return; | |
| 292 | } | ||
| 293 | |||
| 294 | 67 | hdr->base = c->base; | |
| 295 | 67 | hdr->npages = c->npages; | |
| 296 | 67 | hdr->nslots = c->nslots; | |
| 297 | 67 | hdr->dim = c->dim; | |
| 298 | |||
| 299 | 67 | char *p = (char *)collection + sizeof(*hdr); | |
| 300 | 67 | memcpy(p, c->page_off, (size_t)c->npages * sizeof(uint32_t)); | |
| 301 | 67 | p += (size_t)c->npages * sizeof(uint32_t); | |
| 302 | 67 | memcpy(p, c->cents, (size_t)c->nslots * c->dim * sizeof(float)); | |
| 303 | } | ||
| 304 | |||
| 305 | void | ||
| 306 | 238 | prism_exact_centroid_collection_view( | |
| 307 | const void *collection, PrismExactInternalCentroids *view) | ||
| 308 | { | ||
| 309 | 238 | const ExactCentroidCollectionHeader *hdr = | |
| 310 | (const ExactCentroidCollectionHeader *)collection; | ||
| 311 | 238 | const char *p = (const char *)collection + sizeof(*hdr); | |
| 312 | |||
| 313 | 238 | view->page_off = (const uint32_t *)p; | |
| 314 | 238 | view->cents = (const float *)(p + (size_t)hdr->npages * sizeof(uint32_t)); | |
| 315 | 238 | view->base = hdr->base; | |
| 316 | 238 | view->npages = hdr->npages; | |
| 317 | 238 | } | |
| 318 | |||
| 319 | /* Assign each node of a materialized tree its first block, packing nodes | ||
| 320 | * in index order from first_blkno; returns the block after the last. */ | ||
| 321 | BlockNumber | ||
| 322 | 828 | prism_compute_centroid_layout( | |
| 323 | const HKMeansResult *tree, | ||
| 324 | uint32_t max_entries, | ||
| 325 | BlockNumber first_blkno, | ||
| 326 | BlockNumber *node_first_blkno) | ||
| 327 | { | ||
| 328 | 828 | BlockNumber next = first_blkno; | |
| 329 | |||
| 330 |
2/2✓ Branch 0 taken 1240 times.
✓ Branch 1 taken 828 times.
|
2068 | for (uint32_t i = 0; i < tree->nnodes; i++) |
| 331 | { | ||
| 332 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 428 times.
|
1240 | uint32_t n = hk_nodes(tree)[i].nchildren; |
| 333 | 1240 | uint32_t npages = (n + max_entries - 1) / max_entries; | |
| 334 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1240 times.
|
1240 | if (npages == 0) |
| 335 | ✗ | npages = 1; | |
| 336 | 1240 | node_first_blkno[i] = next; | |
| 337 | 1240 | next += npages; | |
| 338 | } | ||
| 339 | |||
| 340 | 828 | return next; | |
| 341 | } | ||
| 342 | |||
| 343 | /* Write a fully materialized (in-RAM) HKMeansResult tree to centroid | ||
| 344 | * pages. The streamed builders below replace this for the paged builds; | ||
| 345 | * the standalone in-RAM build still writes through it. */ | ||
| 346 | void | ||
| 347 | 423 | prism_write_centroid_tree( | |
| 348 | VsStorage *storage, | ||
| 349 | const HKMeansResult *tree, | ||
| 350 | Dimension dim, | ||
| 351 | uint32_t fan_out, | ||
| 352 | uint8_t level_offset, | ||
| 353 | PrismCentroidFormat centroid_format, | ||
| 354 | const RaBitQParams *rq_params, | ||
| 355 | const float *global_mean, | ||
| 356 | BlockNumber posting_base, | ||
| 357 | uint32_t head_stride, | ||
| 358 | const BlockNumber *node_first_blkno, | ||
| 359 | const float *pt_centroids, | ||
| 360 | PrismExactCentroidCollector *collector) | ||
| 361 | { | ||
| 362 | /* Leaf child blocks are formula-derived (posting_base + global leaf | ||
| 363 | * index * head_stride), so no O(nlist) posting-head array is needed. Each | ||
| 364 | * node has at most fan_out leaf entries, so this scratch is O(fan_out). */ | ||
| 365 | 137 | BlockNumber *leaf_blks = | |
| 366 | (posting_base != InvalidBlockNumber) | ||
| 367 | 423 | ? vs_alloc((size_t)fan_out * sizeof(BlockNumber)) | |
| 368 |
1/2✓ Branch 0 taken 423 times.
✗ Branch 1 not taken.
|
423 | : NULL; |
| 369 | |||
| 370 |
2/2✓ Branch 0 taken 660 times.
✓ Branch 1 taken 423 times.
|
1083 | for (uint32_t i = 0; i < tree->nnodes; i++) |
| 371 | { | ||
| 372 |
2/2✓ Branch 0 taken 20 times.
✓ Branch 1 taken 194 times.
|
660 | const HKMeansNode *node = &hk_nodes(tree)[i]; |
| 373 | 660 | bool is_leaf = (node->level == tree->nlevels - 1); | |
| 374 | |||
| 375 | 660 | uint16_t flags = is_leaf ? PRISM_CENTROID_FLAG_LEAF : 0; | |
| 376 |
2/2✓ Branch 0 taken 416 times.
✓ Branch 1 taken 244 times.
|
660 | uint16_t child_count = is_leaf ? 0 : (uint16_t)fan_out; |
| 377 | |||
| 378 | 214 | const BlockNumber *child_blks; | |
| 379 |
3/4✓ Branch 0 taken 590 times.
✓ Branch 1 taken 70 times.
✓ Branch 2 taken 396 times.
✗ Branch 3 not taken.
|
660 | if (is_leaf && leaf_blks != NULL) |
| 380 | { | ||
| 381 |
2/2✓ Branch 0 taken 2966 times.
✓ Branch 1 taken 590 times.
|
3556 | for (uint32_t j = 0; j < node->nchildren; j++) |
| 382 | 2966 | leaf_blks[j] = prism_leaf_head_blkno( | |
| 383 | 2966 | posting_base, node->first_leaf + j, head_stride); | |
| 384 | 396 | child_blks = leaf_blks; | |
| 385 | } | ||
| 386 |
1/2✓ Branch 0 taken 70 times.
✗ Branch 1 not taken.
|
70 | else if (!is_leaf) |
| 387 | 70 | child_blks = &node_first_blkno[node->first_child]; | |
| 388 | else | ||
| 389 | ✗ | child_blks = NULL; | |
| 390 | |||
| 391 | /* Pass pt_centroids for leaf nodes only */ | ||
| 392 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 396 times.
|
660 | const float *leaf_pt = (is_leaf && pt_centroids != NULL) |
| 393 | ✗ | ? pt_centroids + | |
| 394 | ✗ | (size_t)node->first_leaf * dim | |
| 395 |
2/2✓ Branch 0 taken 396 times.
✓ Branch 1 taken 264 times.
|
660 | : NULL; |
| 396 | |||
| 397 | 660 | prism_centroid_write_node( | |
| 398 | storage, | ||
| 399 | dim, | ||
| 400 | 660 | hk_node_centroids(tree, node), | |
| 401 | 660 | node->nchildren, | |
| 402 | centroid_format, | ||
| 403 | 660 | (uint8_t)(level_offset + node->level), | |
| 404 | flags, | ||
| 405 | child_count, | ||
| 406 | rq_params, | ||
| 407 | global_mean, | ||
| 408 | child_blks, | ||
| 409 | leaf_pt, | ||
| 410 | 660 | node_first_blkno[i], | |
| 411 | collector); | ||
| 412 | } | ||
| 413 | |||
| 414 |
1/2✓ Branch 0 taken 423 times.
✗ Branch 1 not taken.
|
423 | if (leaf_blks != NULL) |
| 415 | 423 | vs_free(leaf_blks); | |
| 416 | 423 | } | |
| 417 | |||
| 418 | /* ---------------------------------------------------------------- | ||
| 419 | * Streaming (page-backed) centroid-tree build | ||
| 420 | * ---------------------------------------------------------------- */ | ||
| 421 | |||
| 422 | typedef struct RoutingTreeCtx | ||
| 423 | { | ||
| 424 | /* inputs */ | ||
| 425 | const float *vectors; | ||
| 426 | Dimension dim; | ||
| 427 | uint32_t nlist; | ||
| 428 | uint32_t fan_out; | ||
| 429 | uint32_t nlevels; | ||
| 430 | DistanceMetric metric; | ||
| 431 | KMeansOptions opts; | ||
| 432 | /* write-phase */ | ||
| 433 | VsStorage *storage; | ||
| 434 | PrismCentroidFormat format; | ||
| 435 | const RaBitQParams *rq_params; | ||
| 436 | const float *global_mean; | ||
| 437 | BlockNumber first_posting; /* leaf c's head = first_posting + c * | ||
| 438 | * head_stride */ | ||
| 439 | uint32_t head_stride; /* prism_posting_reference_pages(dim) */ | ||
| 440 | PrismStreamLeafCb on_leaf; | ||
| 441 | void *on_leaf_arg; | ||
| 442 | /* write-phase: optional exact internal-centroid collection */ | ||
| 443 | PrismExactCentroidCollector *collector; | ||
| 444 | /* plan-phase page-count helpers */ | ||
| 445 | uint32_t max_ent; /* non-fastscan entries/page */ | ||
| 446 | uint32_t fs_gpp; /* fastscan groups/page */ | ||
| 447 | /* Node replay: the plan pass records each node's clustering | ||
| 448 | * ({k, centroids, assignments}, recursion order) here, and the write | ||
| 449 | * pass replays it instead of re-running k-means. Both passes require | ||
| 450 | * the store. */ | ||
| 451 | PrismBlobStore *store; | ||
| 452 | float *replay_cents; /* write: [fan_out * dim] */ | ||
| 453 | /* One node's uint16 assignments, shared by both passes (the plan pass | ||
| 454 | * narrows into it before recording, the replay pass reads records back | ||
| 455 | * into it). Sized once for the root -- the first and largest node -- | ||
| 456 | * so it is never grown. */ | ||
| 457 | uint16_t *assign_scratch; /* [nvecs] */ | ||
| 458 | BlockNumber *leaf_blk_scratch; /* write: [fan_out] leaf head blocks */ | ||
| 459 | /* accumulators */ | ||
| 460 | uint32_t nleaves; /* running (== next first_leaf) */ | ||
| 461 | double *leaf_sum; /* plan only, [dim]: leaf-centroid sum for the | ||
| 462 | * leaf_mean the caller uses as global_mean */ | ||
| 463 | uint32_t centroid_pages; /* plan only */ | ||
| 464 | BlockNumber next_blk; /* write only: next reserved centroid block */ | ||
| 465 | bool ok; | ||
| 466 | } RoutingTreeCtx; | ||
| 467 | |||
| 468 | /* | ||
| 469 | * Write one tree node's centroid page(s) in the node's format: the fastscan | ||
| 470 | * writer carries its own encoder; every other format goes through the | ||
| 471 | * generic encoder + page writer. Shared by the streaming DFS and the | ||
| 472 | * parallel leader's root-page write. | ||
| 473 | */ | ||
| 474 | void | ||
| 475 | 2298 | prism_centroid_write_node( | |
| 476 | VsStorage *storage, | ||
| 477 | Dimension dim, | ||
| 478 | const float *cents, | ||
| 479 | uint32_t n, | ||
| 480 | PrismCentroidFormat fmt, | ||
| 481 | uint8_t level, | ||
| 482 | uint16_t flags, | ||
| 483 | uint16_t child_count, | ||
| 484 | const RaBitQParams *rq_params, | ||
| 485 | const float *global_mean, | ||
| 486 | const BlockNumber *child_blks, | ||
| 487 | const float *leaf_pt, | ||
| 488 | BlockNumber blkno, | ||
| 489 | PrismExactCentroidCollector *collector) | ||
| 490 | { | ||
| 491 | /* Every internal node of every build shape passes through here; the | ||
| 492 | * leaf level (LEAF flag) is exact-re-ranked per row instead. */ | ||
| 493 |
4/4✓ Branch 0 taken 1652 times.
✓ Branch 1 taken 646 times.
✓ Branch 2 taken 288 times.
✓ Branch 3 taken 1364 times.
|
2298 | if (collector != NULL && (flags & PRISM_CENTROID_FLAG_LEAF) == 0) |
| 494 | 288 | prism_exact_centroid_collector_add_node(collector, blkno, cents, n); | |
| 495 | |||
| 496 |
2/2✓ Branch 0 taken 1412 times.
✓ Branch 1 taken 886 times.
|
2298 | if (fmt == PRISM_CENTROID_FMT_FASTSCAN) |
| 497 | /* fastscan carries its own encoder; pt_centroids live on posting | ||
| 498 | * pages, never inline. */ | ||
| 499 | 1412 | prism_centroid_write_fastscan_pages( | |
| 500 | storage, | ||
| 501 | dim, | ||
| 502 | n, | ||
| 503 | level, | ||
| 504 | flags, | ||
| 505 | rq_params, | ||
| 506 | cents, | ||
| 507 | global_mean, | ||
| 508 | child_blks, | ||
| 509 | blkno); | ||
| 510 | else | ||
| 511 | { | ||
| 512 | 202 | CentroidEncoderState est; | |
| 513 | 886 | CentroidEncoder *enc = centroid_encoder_init( | |
| 514 | &est, fmt, cents, dim, rq_params, global_mean); | ||
| 515 | 886 | prism_centroid_write_pages( | |
| 516 | storage, | ||
| 517 | dim, | ||
| 518 | n, | ||
| 519 | fmt, | ||
| 520 | level, | ||
| 521 | flags, | ||
| 522 | child_count, | ||
| 523 | enc, | ||
| 524 | child_blks, | ||
| 525 | leaf_pt, | ||
| 526 | blkno); | ||
| 527 | } | ||
| 528 | 2298 | } | |
| 529 | |||
| 530 | /* Pages one node of `n` entries occupies — must match the writers' packing. */ | ||
| 531 | static uint32_t | ||
| 532 | 3138 | node_npages(const RoutingTreeCtx *c, uint32_t n) | |
| 533 | { | ||
| 534 |
2/2✓ Branch 0 taken 2312 times.
✓ Branch 1 taken 826 times.
|
3138 | if (c->format == PRISM_CENTROID_FMT_FASTSCAN) |
| 535 | { | ||
| 536 | 2312 | uint32_t ngroups = (n + VS_FASTSCAN_GROUP - 1) / VS_FASTSCAN_GROUP; | |
| 537 |
1/2✓ Branch 0 taken 164 times.
✗ Branch 1 not taken.
|
2312 | uint32_t gpp = c->fs_gpp ? c->fs_gpp : 1; |
| 538 | 2312 | return (ngroups + gpp - 1) / gpp; | |
| 539 | } | ||
| 540 |
1/2✓ Branch 0 taken 428 times.
✗ Branch 1 not taken.
|
826 | uint32_t me = c->max_ent ? c->max_ent : 1; |
| 541 | 826 | return (n + me - 1) / me; | |
| 542 | } | ||
| 543 | |||
| 544 | /* | ||
| 545 | * Write one node's centroid page(s) at the next reserved block (post-order, so | ||
| 546 | * blocks are assigned in write order); returns the node's first block. The | ||
| 547 | * relation is pre-extended by the caller to cover the centroid + posting area, | ||
| 548 | * so writes use reserved blocks rather than appending (posting heads, which | ||
| 549 | * live in the far posting area, are written during this pass too). | ||
| 550 | */ | ||
| 551 | static BlockNumber | ||
| 552 | 1569 | write_node_pages( | |
| 553 | RoutingTreeCtx *c, | ||
| 554 | const float *cents, | ||
| 555 | uint32_t n, | ||
| 556 | uint32_t level, | ||
| 557 | bool is_leaf, | ||
| 558 | const BlockNumber *child_blks) | ||
| 559 | { | ||
| 560 | 1569 | uint16_t flags = is_leaf ? PRISM_CENTROID_FLAG_LEAF : 0; | |
| 561 | 1569 | BlockNumber start = c->next_blk; | |
| 562 | |||
| 563 | 2778 | prism_centroid_write_node( | |
| 564 | c->storage, | ||
| 565 | 1569 | c->dim, | |
| 566 | cents, | ||
| 567 | n, | ||
| 568 | 1569 | c->format, | |
| 569 | 296 | (uint8_t)level, | |
| 570 | flags, | ||
| 571 | 237 | is_leaf ? 0 : (uint16_t)c->fan_out, | |
| 572 |
2/2✓ Branch 0 taken 405 times.
✓ Branch 1 taken 1164 times.
|
1569 | c->rq_params, |
| 573 | c->global_mean, | ||
| 574 | child_blks, | ||
| 575 | NULL, | ||
| 576 | start, | ||
| 577 | c->collector); | ||
| 578 | |||
| 579 | 1569 | c->next_blk += node_npages(c, n); | |
| 580 | 1569 | return start; | |
| 581 | } | ||
| 582 | |||
| 583 | /* | ||
| 584 | * DFS one node. slice[count] are indices into c->vectors (NULL == identity for | ||
| 585 | * the root). Returns the node's first block (write phase) or | ||
| 586 | * InvalidBlockNumber (plan phase). Post-order: children are written before the | ||
| 587 | * parent so the parent's entries can carry their child block numbers. | ||
| 588 | */ | ||
| 589 | /* Read exactly nbytes of a node record from the replay store. */ | ||
| 590 | static bool | ||
| 591 | 4707 | replay_read(struct PrismBlobStore *store, void *dst, uint64_t nbytes) | |
| 592 | { | ||
| 593 | 4707 | return prism_pbuild_blobstore_get(store, dst, nbytes) == nbytes; | |
| 594 | } | ||
| 595 | |||
| 596 | /* | ||
| 597 | * Replay one node's clustering record from the blob store into the ctx's | ||
| 598 | * replay scratch. The plan pass wrote, per node in recursion order: the | ||
| 599 | * cluster count k (uint32), the centroids (k * dim floats) and the | ||
| 600 | * per-vector assignments (count uint16s); this reads the same three fields | ||
| 601 | * in the same order. Returns false on a short read or an out-of-range k, | ||
| 602 | * which can only mean the plan and write passes diverged. | ||
| 603 | */ | ||
| 604 | static bool | ||
| 605 | 1569 | replay_node_record(RoutingTreeCtx *c, uint32_t count, uint32_t *out_k) | |
| 606 | { | ||
| 607 | 1569 | uint32_t k = 0; | |
| 608 | |||
| 609 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1569 times.
|
1569 | if (!replay_read(c->store, &k, sizeof(k))) |
| 610 | ✗ | return false; | |
| 611 |
3/4✓ Branch 0 taken 296 times.
✓ Branch 1 taken 1273 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1569 times.
|
1569 | if (k == 0 || k > c->fan_out) |
| 612 | ✗ | return false; | |
| 613 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
|
1569 | if (!replay_read( |
| 614 | 1569 | c->store, | |
| 615 | 1569 | c->replay_cents, | |
| 616 | 1569 | (uint64_t)k * c->dim * sizeof(float))) | |
| 617 | ✗ | return false; | |
| 618 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
|
1569 | if (!replay_read( |
| 619 | 1569 | c->store, | |
| 620 | 1569 | c->assign_scratch, | |
| 621 | 1569 | (uint64_t)count * sizeof(uint16_t))) | |
| 622 | ✗ | return false; | |
| 623 | |||
| 624 | 1569 | *out_k = k; | |
| 625 | 1569 | return true; | |
| 626 | } | ||
| 627 | |||
| 628 | /* | ||
| 629 | * Record one node's clustering into the blob store, in the exact field | ||
| 630 | * order replay_node_record reads back: k, centroids[k * dim], | ||
| 631 | * assignments[count]. Assignments are narrowed to uint16 -- a node | ||
| 632 | * clusters into at most fan_out (<= the meta page's 8-bit fan_out) groups. | ||
| 633 | */ | ||
| 634 | static void | ||
| 635 | 1569 | record_node_clustering( | |
| 636 | RoutingTreeCtx *c, const KMeansResult *km, uint32_t count) | ||
| 637 | { | ||
| 638 | 1569 | const size_t assign_nbytes = (size_t)count * sizeof(uint16_t); | |
| 639 | 1569 | uint16_t *a16 = c->assign_scratch; | |
| 640 | |||
| 641 |
2/2✓ Branch 0 taken 538753 times.
✓ Branch 1 taken 1569 times.
|
540322 | for (uint32_t v = 0; v < count; v++) |
| 642 | 538753 | a16[v] = (uint16_t)km->assignments[v]; | |
| 643 | |||
| 644 | 1569 | prism_pbuild_blobstore_put(c->store, &km->nlist, sizeof(km->nlist)); | |
| 645 | 1569 | prism_pbuild_blobstore_put( | |
| 646 | c->store, | ||
| 647 | 1569 | km->centroids, | |
| 648 | 1569 | (uint64_t)km->nlist * c->dim * sizeof(float)); | |
| 649 | 1569 | prism_pbuild_blobstore_put(c->store, a16, assign_nbytes); | |
| 650 | 1569 | } | |
| 651 | |||
| 652 | /* Compact the non-empty clusters' centroids to the front, preserving | ||
| 653 | * ascending cluster order (descent indexes the kept centroids densely). */ | ||
| 654 | static uint32_t | ||
| 655 | 1332 | compact_nonempty_centroids( | |
| 656 | float *cents, | ||
| 657 | const uint32_t *counts, | ||
| 658 | uint32_t nclusters, | ||
| 659 | Dimension dim) | ||
| 660 | { | ||
| 661 | 1332 | uint32_t kept = 0; | |
| 662 |
2/2✓ Branch 0 taken 11286 times.
✓ Branch 1 taken 1332 times.
|
12618 | for (uint32_t cl = 0; cl < nclusters; cl++) |
| 663 | { | ||
| 664 |
2/2✓ Branch 0 taken 90 times.
✓ Branch 1 taken 11196 times.
|
11286 | if (counts[cl] == 0) |
| 665 | 90 | continue; | |
| 666 |
2/2✓ Branch 0 taken 25 times.
✓ Branch 1 taken 11171 times.
|
11196 | if (kept != cl) |
| 667 | 25 | memcpy(cents + (size_t)kept * dim, | |
| 668 | 25 | cents + (size_t)cl * dim, | |
| 669 | 25 | (size_t)dim * sizeof(float)); | |
| 670 | 11196 | kept++; | |
| 671 | } | ||
| 672 | 1332 | return kept; | |
| 673 | } | ||
| 674 | |||
| 675 | static void plan_node_recurse( | ||
| 676 | RoutingTreeCtx *c, | ||
| 677 | const uint32_t *slice, | ||
| 678 | uint32_t count, | ||
| 679 | uint32_t level); | ||
| 680 | static BlockNumber | ||
| 681 | replay_node_recurse(RoutingTreeCtx *c, uint32_t count, uint32_t level); | ||
| 682 | |||
| 683 | /* Leaf parent, plan side: the non-empty clusters become leaves. Nothing is | ||
| 684 | * written; count the leaf pages, tally the leaves, and fold the kept | ||
| 685 | * centroids into the leaf sum (the global mean's numerator). */ | ||
| 686 | static void | ||
| 687 | 1332 | plan_leaf_parent( | |
| 688 | RoutingTreeCtx *c, const KMeansResult *km, const uint32_t *counts) | ||
| 689 | { | ||
| 690 | 1332 | uint32_t kept = 0; | |
| 691 |
2/2✓ Branch 0 taken 11286 times.
✓ Branch 1 taken 1332 times.
|
12618 | for (uint32_t cl = 0; cl < km->nlist; cl++) |
| 692 | { | ||
| 693 |
2/2✓ Branch 0 taken 90 times.
✓ Branch 1 taken 11196 times.
|
11286 | if (counts[cl] == 0) |
| 694 | 90 | continue; | |
| 695 |
1/2✓ Branch 0 taken 11196 times.
✗ Branch 1 not taken.
|
11196 | if (c->leaf_sum != NULL) |
| 696 | { | ||
| 697 | 11196 | const float *lc = km->centroids + (size_t)cl * c->dim; | |
| 698 |
2/2✓ Branch 0 taken 1363305 times.
✓ Branch 1 taken 11196 times.
|
1374501 | for (Dimension d = 0; d < c->dim; d++) |
| 699 | 1363305 | c->leaf_sum[d] += lc[d]; | |
| 700 | } | ||
| 701 | 11196 | kept++; | |
| 702 | } | ||
| 703 | 1332 | c->centroid_pages += node_npages(c, kept); | |
| 704 | 1332 | c->nleaves += kept; | |
| 705 | 1332 | } | |
| 706 | |||
| 707 | /* Internal node, plan side: gather each non-empty child's slice of the | ||
| 708 | * sample and recurse, in ascending cluster order -- the recursion order | ||
| 709 | * that frames the tape -- then count this node's page(s). */ | ||
| 710 | static void | ||
| 711 | 237 | plan_internal_node( | |
| 712 | RoutingTreeCtx *c, | ||
| 713 | const KMeansResult *km, | ||
| 714 | const uint32_t *counts, | ||
| 715 | const uint32_t *slice, | ||
| 716 | uint32_t count, | ||
| 717 | uint32_t level) | ||
| 718 | { | ||
| 719 | 237 | uint32_t kept = 0; | |
| 720 |
3/4✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 237 times.
✓ Branch 2 taken 1344 times.
✗ Branch 3 not taken.
|
1581 | for (uint32_t cl = 0; cl < km->nlist && c->ok; cl++) |
| 721 | { | ||
| 722 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1341 times.
|
1344 | if (counts[cl] == 0) |
| 723 | 3 | continue; | |
| 724 | |||
| 725 | 1341 | uint32_t sub_n = counts[cl]; | |
| 726 | 1341 | uint32_t *sub = vs_alloc((size_t)sub_n * sizeof(uint32_t)); | |
| 727 | 1341 | uint32_t idx = 0; | |
| 728 |
3/3✓ Branch 0 taken 76800 times.
✓ Branch 1 taken 2313510 times.
✓ Branch 2 taken 1069 times.
|
2391379 | for (uint32_t v = 0; v < count; v++) |
| 729 |
2/2✓ Branch 0 taken 268173 times.
✓ Branch 1 taken 2121865 times.
|
2390038 | if (km->assignments[v] == cl) |
| 730 |
2/2✓ Branch 0 taken 59723 times.
✓ Branch 1 taken 208450 times.
|
268173 | sub[idx++] = slice ? slice[v] : v; |
| 731 | 1341 | plan_node_recurse(c, sub, sub_n, level + 1); | |
| 732 | 1341 | vs_free(sub); | |
| 733 | 1341 | kept++; | |
| 734 | } | ||
| 735 | 237 | c->centroid_pages += node_npages(c, kept); | |
| 736 | 237 | } | |
| 737 | |||
| 738 | /* | ||
| 739 | * Plan pass -- writes the tape. Recursive DFS from the given node down | ||
| 740 | * (the mutual recursion runs through plan_internal_node): cluster the | ||
| 741 | * node's slice of the sample (slice[count] indexes c->vectors; NULL = | ||
| 742 | * identity at the root), record the clustering for the replay pass, | ||
| 743 | * descend into the non-empty children, and accumulate the layout totals | ||
| 744 | * (centroid pages, leaves, the leaf-centroid sum) that must be known | ||
| 745 | * before any page can be written. | ||
| 746 | */ | ||
| 747 | static void | ||
| 748 | 1569 | plan_node_recurse( | |
| 749 | RoutingTreeCtx *c, | ||
| 750 | const uint32_t *slice, | ||
| 751 | uint32_t count, | ||
| 752 | uint32_t level) | ||
| 753 | { | ||
| 754 |
2/2✓ Branch 0 taken 1273 times.
✓ Branch 1 taken 296 times.
|
1569 | if (!c->ok) |
| 755 | ✗ | return; | |
| 756 | |||
| 757 |
2/2✓ Branch 0 taken 176 times.
✓ Branch 1 taken 1393 times.
|
1569 | uint32_t k = (c->nlevels == 1) ? c->nlist : c->fan_out; |
| 758 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 296 times.
|
1569 | if (k > count) |
| 759 | ✗ | k = count; | |
| 760 | |||
| 761 | 2842 | KMeansResult *km = vs_kmeans( | |
| 762 | 1569 | c->vectors, | |
| 763 | slice, | ||
| 764 | VS_VEC_F32, | ||
| 765 | count, | ||
| 766 | 1569 | c->dim, | |
| 767 | k, | ||
| 768 | c->metric, | ||
| 769 | 1569 | &c->opts); | |
| 770 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
|
1569 | if (km == NULL) |
| 771 | { | ||
| 772 | ✗ | c->ok = false; | |
| 773 | ✗ | return; | |
| 774 | } | ||
| 775 | 1569 | c->opts.initial_centroids = NULL; /* root only (matches vs_hkmeans_f32) */ | |
| 776 | |||
| 777 |
1/2✓ Branch 0 taken 1569 times.
✗ Branch 1 not taken.
|
1569 | if (c->store != NULL) |
| 778 | 1569 | record_node_clustering(c, km, count); | |
| 779 | |||
| 780 | /* Count assignments per cluster (km->cluster_sizes may be stale). */ | ||
| 781 | 1569 | uint32_t *counts = vs_alloc0((size_t)km->nlist * sizeof(uint32_t)); | |
| 782 |
3/3✓ Branch 0 taken 31200 times.
✓ Branch 1 taken 507849 times.
✓ Branch 2 taken 1273 times.
|
540322 | for (uint32_t v = 0; v < count; v++) |
| 783 | 538753 | counts[km->assignments[v]]++; | |
| 784 | |||
| 785 |
2/2✓ Branch 0 taken 1332 times.
✓ Branch 1 taken 237 times.
|
1569 | if (level == c->nlevels - 1) |
| 786 | 1332 | plan_leaf_parent(c, km, counts); | |
| 787 | else | ||
| 788 | 237 | plan_internal_node(c, km, counts, slice, count, level); | |
| 789 | |||
| 790 | 1569 | vs_free(counts); | |
| 791 | 1569 | vs_kmeans_result_destroy(km); | |
| 792 | } | ||
| 793 | |||
| 794 | /* Leaf parent, replay side: compact the non-empty clusters into leaves, | ||
| 795 | * write the node's page(s) with the formula-derived leaf head blocks, and | ||
| 796 | * emit each leaf's head page from its resident float centroid. */ | ||
| 797 | static BlockNumber | ||
| 798 | 1332 | replay_leaf_parent( | |
| 799 | RoutingTreeCtx *c, | ||
| 800 | uint32_t nclusters, | ||
| 801 | const uint32_t *counts, | ||
| 802 | uint32_t level) | ||
| 803 | { | ||
| 804 | 1332 | float *cents = c->replay_cents; | |
| 805 | 1100 | uint32_t kept = | |
| 806 | 1332 | compact_nonempty_centroids(cents, counts, nclusters, c->dim); | |
| 807 | |||
| 808 | /* Cosine routes and encodes against unit-norm references; k-means | ||
| 809 | * means drift below unit norm, so normalize the leaf centroids in | ||
| 810 | * place before the leaf codes and head references are written from | ||
| 811 | * them (the flat-tree path already does). */ | ||
| 812 |
2/2✓ Branch 0 taken 27 times.
✓ Branch 1 taken 1305 times.
|
1332 | if (c->metric == DISTANCE_COSINE) |
| 813 |
2/2✓ Branch 0 taken 246 times.
✓ Branch 1 taken 27 times.
|
273 | for (uint32_t kk = 0; kk < kept; kk++) |
| 814 | 246 | vs_l2_normalize(cents + (size_t)kk * c->dim, c->dim); | |
| 815 | |||
| 816 | /* Leaf heads are formula-derived (first_posting + global leaf index); | ||
| 817 | * kept <= fan_out, so the pass-lifetime scratch covers every node. */ | ||
| 818 | 1332 | BlockNumber *leaf_blks = NULL; | |
| 819 |
1/2✓ Branch 0 taken 1332 times.
✗ Branch 1 not taken.
|
1332 | if (c->first_posting != InvalidBlockNumber) |
| 820 | { | ||
| 821 | 1332 | leaf_blks = c->leaf_blk_scratch; | |
| 822 |
2/2✓ Branch 0 taken 11196 times.
✓ Branch 1 taken 1332 times.
|
12528 | for (uint32_t kk = 0; kk < kept; kk++) |
| 823 | 11196 | leaf_blks[kk] = prism_leaf_head_blkno( | |
| 824 | 11196 | c->first_posting, c->nleaves + kk, c->head_stride); | |
| 825 | } | ||
| 826 | 1332 | BlockNumber blk = write_node_pages(c, cents, kept, level, true, leaf_blks); | |
| 827 | |||
| 828 |
1/2✓ Branch 0 taken 1332 times.
✗ Branch 1 not taken.
|
1332 | if (c->on_leaf != NULL) |
| 829 |
2/2✓ Branch 0 taken 11196 times.
✓ Branch 1 taken 1332 times.
|
12528 | for (uint32_t kk = 0; kk < kept; kk++) |
| 830 | 11196 | c->on_leaf( | |
| 831 | c->on_leaf_arg, | ||
| 832 | 11196 | c->nleaves + kk, | |
| 833 | 11196 | cents + (size_t)kk * c->dim); | |
| 834 | 1332 | c->nleaves += kept; | |
| 835 | 1332 | return blk; | |
| 836 | } | ||
| 837 | |||
| 838 | /* Internal node, replay side: recurse into each non-empty child in | ||
| 839 | * ascending cluster order -- the same order the plan pass recursed, which | ||
| 840 | * is what keeps the tape in frame -- then write this node's page(s) above | ||
| 841 | * the children. The children's records overwrite the shared replay | ||
| 842 | * scratch, so this node's centroids are snapshotted first. */ | ||
| 843 | static BlockNumber | ||
| 844 | 237 | replay_internal_node( | |
| 845 | RoutingTreeCtx *c, | ||
| 846 | uint32_t nclusters, | ||
| 847 | const uint32_t *counts, | ||
| 848 | uint32_t level) | ||
| 849 | { | ||
| 850 | 237 | const size_t vec_nbytes = (size_t)c->dim * sizeof(float); | |
| 851 | 237 | const size_t cents_nbytes = (size_t)nclusters * vec_nbytes; | |
| 852 | |||
| 853 | 237 | float *my_cents = vs_alloc(cents_nbytes); | |
| 854 | 237 | memcpy(my_cents, c->replay_cents, cents_nbytes); | |
| 855 | |||
| 856 | 237 | BlockNumber *child_blocks = vs_alloc( | |
| 857 | 64 | (size_t)nclusters * sizeof(BlockNumber)); | |
| 858 | 237 | uint32_t kept = 0; | |
| 859 |
4/5✓ Branch 0 taken 272 times.
✓ Branch 1 taken 1136 times.
✓ Branch 2 taken 445 times.
✓ Branch 3 taken 1072 times.
✗ Branch 4 not taken.
|
1581 | for (uint32_t cl = 0; cl < nclusters && c->ok; cl++) |
| 860 | { | ||
| 861 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1341 times.
|
1344 | if (counts[cl] == 0) |
| 862 | 3 | continue; | |
| 863 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1341 times.
|
1341 | if (kept != cl) |
| 864 | ✗ | memcpy(my_cents + (size_t)kept * c->dim, | |
| 865 | ✗ | my_cents + (size_t)cl * c->dim, | |
| 866 | vec_nbytes); | ||
| 867 | 1341 | child_blocks[kept] = replay_node_recurse(c, counts[cl], level + 1); | |
| 868 | 1341 | kept++; | |
| 869 | } | ||
| 870 | |||
| 871 | 237 | BlockNumber blk = InvalidBlockNumber; | |
| 872 |
1/2✓ Branch 0 taken 237 times.
✗ Branch 1 not taken.
|
237 | if (c->ok) |
| 873 | 237 | blk = write_node_pages(c, my_cents, kept, level, false, child_blocks); | |
| 874 | 237 | vs_free(child_blocks); | |
| 875 | 237 | vs_free(my_cents); | |
| 876 | 237 | return blk; | |
| 877 | } | ||
| 878 | |||
| 879 | /* | ||
| 880 | * Replay pass -- reads the tape. Recursive DFS from the given node down | ||
| 881 | * (the mutual recursion runs through replay_internal_node): consume the | ||
| 882 | * record the plan pass wrote for this node and write its page(s). The | ||
| 883 | * record carries the centroids and the assignments, and each child's size | ||
| 884 | * falls out of the assignment counts, so unlike the plan walker this one | ||
| 885 | * needs no sample vectors and descends on counts alone. Post-order: | ||
| 886 | * children are written before the parent so the parent's entries can carry | ||
| 887 | * their block numbers. Returns the node's first block. | ||
| 888 | */ | ||
| 889 | static BlockNumber | ||
| 890 | 1569 | replay_node_recurse(RoutingTreeCtx *c, uint32_t count, uint32_t level) | |
| 891 | { | ||
| 892 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
|
1569 | if (!c->ok) |
| 893 | ✗ | return InvalidBlockNumber; | |
| 894 | |||
| 895 | 1569 | uint32_t nclusters = 0; | |
| 896 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1569 times.
|
1569 | if (!replay_node_record(c, count, &nclusters)) |
| 897 | { | ||
| 898 | ✗ | c->ok = false; | |
| 899 | ✗ | return InvalidBlockNumber; | |
| 900 | } | ||
| 901 | |||
| 902 | /* Count assignments per cluster. */ | ||
| 903 | 1569 | uint32_t *counts = vs_alloc0((size_t)nclusters * sizeof(uint32_t)); | |
| 904 |
3/3✓ Branch 0 taken 31200 times.
✓ Branch 1 taken 507849 times.
✓ Branch 2 taken 1273 times.
|
540322 | for (uint32_t v = 0; v < count; v++) |
| 905 | 538753 | counts[c->assign_scratch[v]]++; | |
| 906 | |||
| 907 | 1273 | BlockNumber blk; | |
| 908 |
2/2✓ Branch 0 taken 1332 times.
✓ Branch 1 taken 237 times.
|
1569 | if (level == c->nlevels - 1) |
| 909 | 1332 | blk = replay_leaf_parent(c, nclusters, counts, level); | |
| 910 | else | ||
| 911 | 237 | blk = replay_internal_node(c, nclusters, counts, level); | |
| 912 | |||
| 913 | 1569 | vs_free(counts); | |
| 914 | 1569 | return blk; | |
| 915 | } | ||
| 916 | |||
| 917 | /* Shared walker state: tree geometry and page capacities. The plan entry | ||
| 918 | * adds the sample/metric/k-means knobs; the replay entry adds the storage, | ||
| 919 | * tape and replay scratch. */ | ||
| 920 | static void | ||
| 921 | 456 | routing_tree_ctx_init( | |
| 922 | RoutingTreeCtx *c, | ||
| 923 | Dimension dim, | ||
| 924 | uint32_t nlist, | ||
| 925 | uint32_t fan_out, | ||
| 926 | PrismCentroidFormat format) | ||
| 927 | { | ||
| 928 | 456 | memset(c, 0, sizeof(*c)); | |
| 929 | 456 | c->dim = dim; | |
| 930 | 456 | c->head_stride = prism_posting_reference_pages(dim); | |
| 931 | 456 | c->nlist = nlist; | |
| 932 | 456 | c->fan_out = fan_out < 2 ? 2 : fan_out; | |
| 933 | 456 | c->nlevels = vs_hkmeans_nlevels(nlist, c->fan_out); | |
| 934 | 456 | c->format = format; | |
| 935 | 456 | c->max_ent = prism_centroid_max_entries_fmt(dim, format); | |
| 936 | 456 | c->fs_gpp = prism_centroid_fastscan_max_groups(dim); | |
| 937 | 456 | c->ok = true; | |
| 938 | 456 | } | |
| 939 | |||
| 940 | /* Plan-pass entry ("write the tape"): cluster the sample once, record | ||
| 941 | * every node, and return the layout totals -- see the header comment. */ | ||
| 942 | bool | ||
| 943 | 228 | prism_routing_tree_plan( | |
| 944 | const float *vectors, | ||
| 945 | uint32_t nvecs, | ||
| 946 | Dimension dim, | ||
| 947 | uint32_t nlist, | ||
| 948 | uint32_t fan_out, | ||
| 949 | DistanceMetric metric, | ||
| 950 | PrismCentroidFormat format, | ||
| 951 | const KMeansOptions *opts, | ||
| 952 | PrismBlobStore *store, | ||
| 953 | PrismStreamTreePlan *out) | ||
| 954 | { | ||
| 955 | 204 | RoutingTreeCtx c; | |
| 956 | 228 | routing_tree_ctx_init(&c, dim, nlist, fan_out, format); | |
| 957 | /* Only the plan pass clusters, so only it carries the sample, the | ||
| 958 | * metric and the k-means options. */ | ||
| 959 | 228 | c.vectors = vectors; | |
| 960 | 228 | c.metric = metric; | |
| 961 |
1/2✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
|
228 | c.opts = opts ? *opts : (KMeansOptions)VS_KMEANS_OPTIONS_DEFAULT; |
| 962 | 228 | c.store = store; | |
| 963 | 228 | c.leaf_sum = vs_alloc0((size_t)dim * sizeof(double)); | |
| 964 |
1/2✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
|
228 | if (store != NULL) |
| 965 | { | ||
| 966 | /* Recording narrows each node's assignments into this scratch; the | ||
| 967 | * root -- first and largest -- sizes it for the whole pass. */ | ||
| 968 | 228 | c.assign_scratch = vs_alloc((size_t)nvecs * sizeof(uint16_t)); | |
| 969 | } | ||
| 970 | |||
| 971 | /* | ||
| 972 | * The recursion's per-node scratch (k-means temporaries, index slices, | ||
| 973 | * child-block arrays) lives in its own context so anything a node fails | ||
| 974 | * to free is reclaimed here, at the end of the pass, rather than | ||
| 975 | * accumulating for the rest of the build. This pass-scoped context is | ||
| 976 | * the deliberate leak-containment boundary: node lifetimes nest (a | ||
| 977 | * parent's k-means result and child arrays stay live across its | ||
| 978 | * children), so finer-grained reclamation such as resets at node or | ||
| 979 | * sibling boundaries would free live ancestor state — and would turn a | ||
| 980 | * missed free (a bounded, observable leak) into a use-after-free. | ||
| 981 | * Within a node, explicit frees remain the mechanism; the context caps | ||
| 982 | * their blast radius at one pass. The output (leaf_mean) is allocated | ||
| 983 | * in the caller's context outside the switch. | ||
| 984 | */ | ||
| 985 | 228 | VsMemCtx scratch = vs_memctx_create(NULL, "vs stream plan"); | |
| 986 | 228 | VsMemCtx old_ctx = vs_memctx_switch(scratch); | |
| 987 | 228 | plan_node_recurse(&c, NULL, nvecs, 0); | |
| 988 | 228 | vs_memctx_switch(old_ctx); | |
| 989 | 228 | vs_memctx_delete(scratch); | |
| 990 | |||
| 991 |
1/2✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
|
228 | if (c.assign_scratch != NULL) |
| 992 | 228 | vs_free(c.assign_scratch); | |
| 993 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 228 times.
|
228 | if (!c.ok) |
| 994 | { | ||
| 995 | ✗ | vs_free(c.leaf_sum); | |
| 996 | ✗ | return false; | |
| 997 | } | ||
| 998 | |||
| 999 | 228 | out->nleaves = c.nleaves; | |
| 1000 | 228 | out->nlevels = c.nlevels; | |
| 1001 | 228 | out->centroid_pages = c.centroid_pages; | |
| 1002 | 228 | out->leaf_mean = vs_alloc((size_t)dim * sizeof(float)); | |
| 1003 |
2/2✓ Branch 0 taken 146280 times.
✓ Branch 1 taken 228 times.
|
146508 | for (Dimension d = 0; d < dim; d++) |
| 1004 | 146280 | out->leaf_mean[d] = c.nleaves > 0 | |
| 1005 | 146280 | ? (float)(c.leaf_sum[d] / (double)c.nleaves) | |
| 1006 |
1/2✓ Branch 0 taken 146280 times.
✗ Branch 1 not taken.
|
146280 | : 0.0f; |
| 1007 | 228 | vs_free(c.leaf_sum); | |
| 1008 | 228 | return true; | |
| 1009 | } | ||
| 1010 | |||
| 1011 | /* Replay-pass entry ("read the tape"): stream every centroid + head page | ||
| 1012 | * from the recorded nodes; returns the root block. */ | ||
| 1013 | BlockNumber | ||
| 1014 | 228 | prism_routing_tree_write( | |
| 1015 | VsStorage *storage, | ||
| 1016 | uint32_t nvecs, | ||
| 1017 | Dimension dim, | ||
| 1018 | DistanceMetric metric, | ||
| 1019 | uint32_t nlist, | ||
| 1020 | uint32_t fan_out, | ||
| 1021 | PrismCentroidFormat format, | ||
| 1022 | const RaBitQParams *rq_params, | ||
| 1023 | const float *global_mean, | ||
| 1024 | PrismBlobStore *store, | ||
| 1025 | BlockNumber first_posting, | ||
| 1026 | BlockNumber first_centroid, | ||
| 1027 | PrismStreamLeafCb on_leaf, | ||
| 1028 | void *on_leaf_arg, | ||
| 1029 | PrismExactCentroidCollector *collector) | ||
| 1030 | { | ||
| 1031 | /* Replay never clusters: everything it needs is on the tape, so it | ||
| 1032 | * takes no sample vectors, metric or k-means options. */ | ||
| 1033 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 228 times.
|
228 | if (store == NULL) |
| 1034 | ✗ | return InvalidBlockNumber; | |
| 1035 | |||
| 1036 | 204 | RoutingTreeCtx c; | |
| 1037 | 228 | routing_tree_ctx_init(&c, dim, nlist, fan_out, format); | |
| 1038 | 228 | c.metric = metric; | |
| 1039 | 228 | c.storage = storage; | |
| 1040 | 228 | c.store = store; | |
| 1041 | { | ||
| 1042 | /* A node clusters into at most fan_out groups (the flat root's k = | ||
| 1043 | * nlist <= fan_out). The assignment scratch covers the root's full | ||
| 1044 | * sample; deeper slices are strictly smaller. */ | ||
| 1045 | 228 | c.replay_cents = vs_alloc((size_t)c.fan_out * dim * sizeof(float)); | |
| 1046 | 228 | c.assign_scratch = vs_alloc((size_t)nvecs * sizeof(uint16_t)); | |
| 1047 | 228 | c.leaf_blk_scratch = vs_alloc((size_t)c.fan_out * sizeof(BlockNumber)); | |
| 1048 | } | ||
| 1049 | 228 | c.rq_params = rq_params; | |
| 1050 | 228 | c.global_mean = global_mean; | |
| 1051 | 228 | c.first_posting = first_posting; | |
| 1052 | 228 | c.next_blk = first_centroid; | |
| 1053 | 228 | c.on_leaf = on_leaf; | |
| 1054 | 228 | c.on_leaf_arg = on_leaf_arg; | |
| 1055 | 228 | c.collector = collector; | |
| 1056 | |||
| 1057 | /* Same pass-scoped scratch as the PLAN pass -- the leak-containment | ||
| 1058 | * boundary (see the note there). on_leaf runs under it too; its | ||
| 1059 | * allocations must not outlive the call. */ | ||
| 1060 | 228 | VsMemCtx scratch = vs_memctx_create(NULL, "vs stream write"); | |
| 1061 | 228 | VsMemCtx old_ctx = vs_memctx_switch(scratch); | |
| 1062 | 228 | BlockNumber root = replay_node_recurse(&c, nvecs, 0); | |
| 1063 | 228 | vs_memctx_switch(old_ctx); | |
| 1064 | 228 | vs_memctx_delete(scratch); | |
| 1065 |
1/2✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
|
228 | if (c.replay_cents != NULL) |
| 1066 | 228 | vs_free(c.replay_cents); | |
| 1067 |
1/2✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
|
228 | if (c.assign_scratch != NULL) |
| 1068 | 228 | vs_free(c.assign_scratch); | |
| 1069 |
1/2✓ Branch 0 taken 228 times.
✗ Branch 1 not taken.
|
228 | if (c.leaf_blk_scratch != NULL) |
| 1070 | 228 | vs_free(c.leaf_blk_scratch); | |
| 1071 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 204 times.
|
228 | return c.ok ? root : InvalidBlockNumber; |
| 1072 | } | ||
| 1073 | |||
| 1074 | /* Parallel build: write one worker-built (materialized) subtree's pages at | ||
| 1075 | * its reserved block range, mapping its leaves into the global leaf index | ||
| 1076 | * space -- see the header comment. */ | ||
| 1077 | BlockNumber | ||
| 1078 | 405 | prism_routing_subtree_write( | |
| 1079 | VsStorage *storage, | ||
| 1080 | const HKMeansResult *subtree, | ||
| 1081 | Dimension dim, | ||
| 1082 | DistanceMetric metric, | ||
| 1083 | uint32_t fan_out, | ||
| 1084 | uint8_t level_offset, | ||
| 1085 | PrismCentroidFormat format, | ||
| 1086 | const RaBitQParams *rq_params, | ||
| 1087 | const float *global_mean, | ||
| 1088 | BlockNumber first_posting, | ||
| 1089 | uint32_t leaf_offset, | ||
| 1090 | BlockNumber first_block, | ||
| 1091 | PrismStreamLeafCb on_leaf, | ||
| 1092 | void *on_leaf_arg, | ||
| 1093 | PrismExactCentroidCollector *collector) | ||
| 1094 | { | ||
| 1095 | 405 | uint32_t max_ent = prism_centroid_max_entries_fmt(dim, format); | |
| 1096 | |||
| 1097 | /* Lay the subtree's nodes out at reserved blocks starting at first_block | ||
| 1098 | * (BFS: node 0 = subtree root at first_block). */ | ||
| 1099 | 405 | BlockNumber *nfb = vs_alloc((size_t)subtree->nnodes * sizeof(BlockNumber)); | |
| 1100 | 405 | (void)prism_compute_centroid_layout(subtree, max_ent, first_block, nfb); | |
| 1101 | |||
| 1102 | /* Leaf entries link to formula-derived posting heads (first_posting + | ||
| 1103 | * global leaf index); leaf_offset maps the subtree's local leaf indices to | ||
| 1104 | * the global index space. */ | ||
| 1105 | /* Subtree node levels are subtree-relative; level_offset places them at | ||
| 1106 | * their absolute depth (the tree root above them is level 0). */ | ||
| 1107 | /* Cosine: normalize the subtree's leaf centroids in place before the | ||
| 1108 | * leaf codes and head references are written from them (matches the | ||
| 1109 | * flat-tree path; k-means means drift below unit norm). */ | ||
| 1110 |
2/2✓ Branch 0 taken 14 times.
✓ Branch 1 taken 391 times.
|
405 | if (metric == DISTANCE_COSINE) |
| 1111 | { | ||
| 1112 | 14 | float *lv = hk_leaf_centroids(subtree); | |
| 1113 |
2/2✓ Branch 0 taken 123 times.
✓ Branch 1 taken 14 times.
|
137 | for (uint32_t li = 0; li < subtree->nleaves; li++) |
| 1114 | 123 | vs_l2_normalize(lv + (size_t)li * dim, dim); | |
| 1115 | } | ||
| 1116 | |||
| 1117 | 405 | prism_write_centroid_tree( | |
| 1118 | storage, | ||
| 1119 | subtree, | ||
| 1120 | dim, | ||
| 1121 | fan_out, | ||
| 1122 | level_offset, | ||
| 1123 | format, | ||
| 1124 | rq_params, | ||
| 1125 | global_mean, | ||
| 1126 | prism_leaf_head_blkno( | ||
| 1127 | first_posting, | ||
| 1128 | leaf_offset, | ||
| 1129 | prism_posting_reference_pages(dim)), | ||
| 1130 | prism_posting_reference_pages(dim), | ||
| 1131 | nfb, | ||
| 1132 | NULL, | ||
| 1133 | collector); | ||
| 1134 | 405 | vs_free(nfb); | |
| 1135 | |||
| 1136 | /* Head pages carry pt_centroid from the resident float leaf centroids. */ | ||
| 1137 |
1/2✓ Branch 0 taken 405 times.
✗ Branch 1 not taken.
|
405 | if (on_leaf != NULL) |
| 1138 | { | ||
| 1139 | 405 | const float *leaves = hk_leaf_centroids(subtree); | |
| 1140 |
2/2✓ Branch 0 taken 2744 times.
✓ Branch 1 taken 405 times.
|
3149 | for (uint32_t i = 0; i < subtree->nleaves; i++) |
| 1141 | 2744 | on_leaf(on_leaf_arg, leaf_offset + i, leaves + (size_t)i * dim); | |
| 1142 | } | ||
| 1143 | |||
| 1144 | 405 | return first_block; | |
| 1145 | } | ||
| 1146 | |||
| 1147 | /* Resolve the tree fan-out when the user left it at the default: sqrt of | ||
| 1148 | * the partition count, falling to cbrt when that exceeds a page's worth of | ||
| 1149 | * children. */ | ||
| 1150 | uint32_t | ||
| 1151 | 364 | prism_auto_fan_out(uint32_t fan_out, uint32_t nlist, uint32_t default_fan_out) | |
| 1152 | { | ||
| 1153 |
3/4✓ Branch 0 taken 339 times.
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 114 times.
|
364 | if (fan_out != default_fan_out || nlist <= fan_out) |
| 1154 | 225 | return (nlist <= fan_out) ? nlist : fan_out; | |
| 1155 | |||
| 1156 | 139 | uint32_t f = (uint32_t)ceil(sqrt((double)nlist)); | |
| 1157 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 139 times.
|
139 | if (f > 256) |
| 1158 | ✗ | f = (uint32_t)ceil(cbrt((double)nlist)); | |
| 1159 | 114 | return f; | |
| 1160 | } | ||
| 1161 | |||
| 1162 | /* Target entries per posting list at this dimension -- see the header. */ | ||
| 1163 | uint32_t | ||
| 1164 | 2241 | prism_target_entries_per_dim(Dimension dim, uint32_t target_pages) | |
| 1165 | { | ||
| 1166 |
2/2✓ Branch 0 taken 2115 times.
✓ Branch 1 taken 126 times.
|
2241 | if (target_pages == 0) |
| 1167 | 2115 | target_pages = PRISM_DEFAULT_TARGET_PAGES; | |
| 1168 | |||
| 1169 | 2241 | uint32_t per_page = prism_posting_page_usable() / | |
| 1170 | 2241 | PRISM_POSTING_ENTRY_SIZE(dim); | |
| 1171 | |||
| 1172 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2241 times.
|
2241 | if (per_page < 1) |
| 1173 | ✗ | per_page = 1; | |
| 1174 | |||
| 1175 | 2241 | uint32_t target = per_page * target_pages; | |
| 1176 | |||
| 1177 | 147 | return target > PRISM_MIN_ENTRIES_PER_LIST ? target | |
| 1178 | 2241 | : PRISM_MIN_ENTRIES_PER_LIST; | |
| 1179 | } | ||
| 1180 | |||
| 1181 | /* Automatic partition count from the (estimated) row count. */ | ||
| 1182 | uint32_t | ||
| 1183 | 118 | prism_auto_nlist(double count, Dimension dim, uint32_t target_pages) | |
| 1184 | { | ||
| 1185 | /* | ||
| 1186 | * One list per prism_target_entries_per_dim(dim) vectors -- see the header | ||
| 1187 | * for why that is the target. The hierarchical centroid tree keeps routing | ||
| 1188 | * cheap even at a high list count, so nlist scales linearly with the row | ||
| 1189 | * count. | ||
| 1190 | * | ||
| 1191 | * Floor it at sqrt(count): for small tables count/target collapses toward | ||
| 1192 | * a single list, which under-partitions and can starve the k-means build. | ||
| 1193 | * The linear target overtakes the sqrt floor at target^2 rows (65536 at a | ||
| 1194 | * 256-entry target). Back-ends clamp the result to their own nlist | ||
| 1195 | * ceiling. | ||
| 1196 | */ | ||
| 1197 |
2/2✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
|
118 | double c = count > 1.0 ? count : 1.0; |
| 1198 | 118 | uint32_t target = prism_target_entries_per_dim(dim, target_pages); | |
| 1199 | 118 | uint32_t linear = (uint32_t)(c / (double)target + 0.5); | |
| 1200 | 118 | uint32_t min_lists = (uint32_t)sqrt(c); | |
| 1201 | 118 | uint32_t nlist = linear > min_lists ? linear : min_lists; | |
| 1202 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 100 times.
|
118 | return nlist < 1 ? 1 : nlist; |
| 1203 | } | ||
| 1204 | |||
| 1205 | /* | ||
| 1206 | * Vectors per posting list at a given row count -- the resting size | ||
| 1207 | * maintenance aims each list at. Inverts prism_auto_nlist so the two cannot | ||
| 1208 | * drift apart; see the header for the sqrt-floor regime and the nlist == 0 | ||
| 1209 | * convention. | ||
| 1210 | */ | ||
| 1211 | uint32_t | ||
| 1212 | 20 | prism_target_entries_per_list( | |
| 1213 | double count, uint32_t nlist, Dimension dim, uint32_t target_pages) | ||
| 1214 | { | ||
| 1215 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
|
20 | double c = count > 1.0 ? count : 1.0; |
| 1216 | |||
| 1217 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
|
20 | if (nlist == 0) |
| 1218 | 18 | nlist = prism_auto_nlist(c, dim, target_pages); | |
| 1219 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
|
20 | if (nlist < 1) |
| 1220 | ✗ | nlist = 1; | |
| 1221 | |||
| 1222 | 20 | uint32_t per_list = (uint32_t)(c / (double)nlist + 0.5); | |
| 1223 |
1/2✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
|
20 | return per_list < 1 ? 1 : per_list; |
| 1224 | } | ||
| 1225 | |||
| 1226 | /* 2nd-nearest cluster from a distance-sorted candidate list, or | ||
| 1227 | * primary_cluster when the runner-up is not within epsilon (no replication | ||
| 1228 | * warranted) -- see the header comment. */ | ||
| 1229 | uint32_t | ||
| 1230 | ✗ | prism_find_secondary_cluster( | |
| 1231 | const uint32_t *cand_leaves, | ||
| 1232 | const Distance *cand_dists, | ||
| 1233 | uint32_t ncand, | ||
| 1234 | uint32_t primary_cluster, | ||
| 1235 | Distance primary_dist, | ||
| 1236 | double epsilon) | ||
| 1237 | { | ||
| 1238 | /* Candidates are sorted by ascending distance, so the first one | ||
| 1239 | * that is not the primary is the 2nd-nearest centroid. */ | ||
| 1240 | ✗ | for (uint32_t i = 0; i < ncand; i++) | |
| 1241 | { | ||
| 1242 | ✗ | if (cand_leaves[i] == primary_cluster) | |
| 1243 | ✗ | continue; | |
| 1244 | |||
| 1245 | ✗ | Distance best2 = cand_dists[i]; | |
| 1246 | ✗ | double gap = (double)best2 - (double)primary_dist; | |
| 1247 | ✗ | double gap_ratio = (primary_dist != 0.0) | |
| 1248 | ✗ | ? gap / fabs((double)primary_dist) | |
| 1249 | ✗ | : INFINITY; | |
| 1250 | |||
| 1251 | ✗ | if (gap_ratio <= epsilon) | |
| 1252 | ✗ | return cand_leaves[i]; | |
| 1253 | ✗ | break; | |
| 1254 | } | ||
| 1255 | |||
| 1256 | ✗ | return primary_cluster; | |
| 1257 | } | ||
| 1258 | |||
| 1259 | /* | ||
| 1260 | * SOAR secondary cluster: the leaf (other than the primary) minimizing the | ||
| 1261 | * orthogonality-amplified distance, decomposed so both terms use the SIMD | ||
| 1262 | * vecops kernels: | ||
| 1263 | * | ||
| 1264 | * oa(c) = ||v - c||^2 + lambda * (r_hat . (v - c))^2 | ||
| 1265 | * = ||v - c||^2 + lambda * (r_hat.v - r_hat.c)^2 | ||
| 1266 | * | ||
| 1267 | * r_hat.v is constant across centroids, so only ||v - c||^2 and r_hat.c are | ||
| 1268 | * per-centroid. Since lambda * (...)^2 >= 0, ||v - c||^2 is a lower bound on | ||
| 1269 | * oa: when it already exceeds the running best we skip the dot product (exact | ||
| 1270 | * pruning — no recall impact). | ||
| 1271 | * | ||
| 1272 | * The search set is `count` leaves: the ids cand_leaves[0..count) when | ||
| 1273 | * cand_leaves is non-NULL, otherwise leaves 0..count (a full scan, called with | ||
| 1274 | * count == nleaves). The candidate form is O(count) rather than O(nleaves); | ||
| 1275 | * because the minimizer always has a small ||v - c||^2 (a far leaf cannot win) | ||
| 1276 | * it lies among the nearest leaves the beam already found, so the result is | ||
| 1277 | * unchanged while scaling to large nlist — where a full scan would read the | ||
| 1278 | * entire (multi-hundred-MB) leaf-centroid array per replicated vector. | ||
| 1279 | */ | ||
| 1280 | uint32_t | ||
| 1281 | 37549 | prism_find_soar_secondary( | |
| 1282 | const float *vec, | ||
| 1283 | const float *leaf_centroids, | ||
| 1284 | const uint32_t *cand_leaves, | ||
| 1285 | uint32_t count, | ||
| 1286 | Dimension dim, | ||
| 1287 | uint32_t primary_cluster, | ||
| 1288 | const float *normalized_residual, | ||
| 1289 | double lambda) | ||
| 1290 | { | ||
| 1291 | 37549 | float qrv = vs_dot_product(normalized_residual, vec, dim); | |
| 1292 | 37549 | float lam = (float)lambda; | |
| 1293 | 37549 | float best_oa = INFINITY; | |
| 1294 | 37549 | uint32_t best_c = primary_cluster; | |
| 1295 | |||
| 1296 |
2/2✓ Branch 0 taken 1342514 times.
✓ Branch 1 taken 37549 times.
|
1380063 | for (uint32_t k = 0; k < count; k++) |
| 1297 | { | ||
| 1298 |
2/2✓ Branch 0 taken 124806 times.
✓ Branch 1 taken 1217708 times.
|
1342514 | uint32_t i = cand_leaves ? cand_leaves[k] : k; |
| 1299 |
2/2✓ Branch 0 taken 37001 times.
✓ Branch 1 taken 1305513 times.
|
1342514 | if (i == primary_cluster) |
| 1300 | 37001 | continue; | |
| 1301 | |||
| 1302 | 1305513 | const float *cent = leaf_centroids + (size_t)i * dim; | |
| 1303 | |||
| 1304 | 1305513 | float l2 = vs_l2_distance_squared(vec, cent, dim); | |
| 1305 |
2/2✓ Branch 0 taken 1175708 times.
✓ Branch 1 taken 129805 times.
|
1305513 | if (l2 >= best_oa) |
| 1306 | 1175708 | continue; /* oa >= l2 >= best_oa: cannot improve */ | |
| 1307 | |||
| 1308 | 129805 | float rc = vs_dot_product(normalized_residual, cent, dim); | |
| 1309 | 129805 | float gap = qrv - rc; | |
| 1310 | 129805 | float oa = l2 + lam * gap * gap; | |
| 1311 |
2/2✓ Branch 0 taken 82653 times.
✓ Branch 1 taken 47152 times.
|
129805 | if (oa < best_oa) |
| 1312 | { | ||
| 1313 | 1106470 | best_oa = oa; | |
| 1314 | 1106470 | best_c = i; | |
| 1315 | } | ||
| 1316 | } | ||
| 1317 | |||
| 1318 | 37549 | return best_c; | |
| 1319 | } | ||
| 1320 | |||
| 1321 | /* Log the per-phase build time summary. */ | ||
| 1322 | void | ||
| 1323 | 249 | prism_build_stats_print(const PrismBuildStats *s) | |
| 1324 | { | ||
| 1325 | /* Per-phase breakdown — the single shared build summary, filled by both | ||
| 1326 | * the PostgreSQL build (via the build-progress seam) and the standalone | ||
| 1327 | * build. */ | ||
| 1328 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
|
249 | vs_log("build: sample %.1fms, kmeans %.1fms, refine %.1fms, setup " |
| 1329 | "%.1fms, " | ||
| 1330 | "posting %.1fms, centroid %.1fms, total %.1fms\n", | ||
| 1331 | s->ms_sample, | ||
| 1332 | s->ms_kmeans, | ||
| 1333 | s->ms_refine, | ||
| 1334 | s->ms_setup, | ||
| 1335 | s->ms_posting, | ||
| 1336 | s->ms_centroid, | ||
| 1337 | s->ms_total); | ||
| 1338 | |||
| 1339 | /* Posting-merge sub-detail: only the standalone parallel path populates | ||
| 1340 | * these. Skip the line (and its zeros) when unset — e.g. the PostgreSQL | ||
| 1341 | * build, which tracks posting as one phase. */ | ||
| 1342 |
3/6✓ Branch 0 taken 249 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 249 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 249 times.
|
249 | if (s->ms_parallel > 0.0 || s->ms_merge > 0.0 || s->total_pages > 0) |
| 1343 | ✗ | vs_log("build: posting detail — parallel %.1fms + merge %.1fms, " | |
| 1344 | "%u workers + leader, %u pages, " | ||
| 1345 | "%u partial pages merged into %u\n", | ||
| 1346 | s->ms_parallel, | ||
| 1347 | s->ms_merge, | ||
| 1348 | s->nworkers, | ||
| 1349 | s->total_pages, | ||
| 1350 | s->merge_input, | ||
| 1351 | s->merge_output); | ||
| 1352 | 249 | } | |
| 1353 |