GCC Code Coverage Report

Directory: src/
File: src/index/posting_split.c
Date: 2026-10-23 09:17:32
Exec Total Coverage
Lines: 404 425 95.1%
Functions: 18 18 100.0%
Branches: 215 256 84.0%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * posting_split.c - Incremental posting-list split (see header)
6 */
7
8 #include <string.h>
9
10 #include "algo/distance.h"
11 #include "algo/kmeans.h"
12 #include "algo/vecops.h"
13 #include "core/injection.h"
14 #include "core/memory.h"
15 #include "index/centroid_page.h"
16 #include "index/posting_build.h"
17 #include "index/posting_page.h"
18 #include "index/posting_split.h"
19 #include "quant/rabitq.h"
20
21 /* ----------------------------------------------------------------
22 * Entry collection
23 * ---------------------------------------------------------------- */
24
25 /*
26 * A split streams its list; it does not hold it.
27 *
28 * Holding every vector at full precision costs n * dim * 4 bytes, which makes
29 * the tool for splitting an oversized list fail in proportion to how oversized
30 * the list is -- the one case where it has to work. So the list is streamed
31 * twice instead: once to count it and draw a bounded sample to cluster on, and
32 * once to write each entry into the list whose centroid is nearest. Peak
33 * memory is the sample plus the page builders, whatever the list holds.
34 *
35 * Clustering a sample rather than the whole list is the trade the bulk build
36 * already makes for the same reason. A list that fits the budget is sampled
37 * whole, so nothing changes for the sizes a split normally meets.
38 */
39 typedef struct SplitSample
40 {
41 float *vecs; /* [alloc * dim], the clustering input */
42 uint32_t cap; /* ceiling the budget pays for */
43 uint32_t alloc; /* entries the buffer holds; grows toward cap */
44 uint32_t count; /* sampled so far */
45
46 uint32_t n_live; /* fetchable entries in the list */
47 uint32_t n_degenerate; /* of those, with no defined distance */
48 uint32_t eligible; /* entries the sample could have taken */
49 uint64_t rng; /* reservoir draws; seeded, so runs repeat */
50
51 Dimension dim;
52 DistanceMetric metric;
53 const PrismSplitEnv *env;
54 float *one; /* scratch for the entry being fetched */
55 } SplitSample;
56
57 /* The j'th centroid of a packed [n * dim] array. */
58 static inline const float *
59 556304 centroid_at(const float *centroids, uint32_t j, Dimension dim)
60 {
61 556304 return centroids + (size_t)j * dim;
62 }
63
64 /*
65 * Deterministic draws for the reservoir. splitmix64: a few operations, and
66 * seeded from the split's own seed so a given list samples the same way twice.
67 * Choosing which sampled point to displace does not need more than this.
68 */
69 static inline uint64_t
70 21600 splitmix64_next(uint64_t *state)
71 {
72 21600 uint64_t z = (*state += UINT64_C(0x9E3779B97F4A7C15));
73 21600 z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
74 21600 z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
75 21600 return z ^ (z >> 31);
76 }
77
78 /* The head's own idea of how many entries the list holds. Only an estimate for
79 * sizing the sample: it does not know about entries whose vector can no longer
80 * be fetched. */
81 static uint32_t
82 150 head_live_count(VsStorage *storage, BlockNumber head)
83 {
84 150 Page p = vs_storage_read_page(storage, head);
85 150 uint32_t n = prism_posting_head_live_count(p);
86 150 vs_storage_release_page(storage, head);
87 150 return n;
88 }
89
90 /* True when `vec` has no defined distance under `metric` -- a zero-norm vector
91 * under cosine. Such an entry can never be a result, and must stay out of the
92 * clustering: its distance to every centroid is undefined, and a cluster of
93 * nothing else gets a zero-norm mean that k-means leaves unnormalized. */
94 static bool
95 153112 vector_is_degenerate(const float *vec, Dimension dim, DistanceMetric metric)
96 {
97 /* Squared norm -- zero iff the norm is zero, without the sqrt. */
98
4/6
✓ Branch 0 taken 1760 times.
✓ Branch 1 taken 121952 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 160 times.
✓ Branch 4 taken 1600 times.
✗ Branch 5 not taken.
 123712 return metric == DISTANCE_COSINE && vs_l2_norm_squared(vec, dim) == 0.0f;
99 }
100
101 /* ----------------------------------------------------------------
102 * Chain traversal
103 * ---------------------------------------------------------------- */
104
105 /*
106 * Call `cb` once per live entry of the chain at `head`, in chain order --
107 * once per indexed vector, that is, not once per page or per fastscan group.
108 * Callers see a flat sequence of tids and nothing about how the pages are
109 * laid out: this is the single place that knows either page format, so every
110 * pass over a list shares it.
111 *
112 * It yields tids rather than vectors deliberately. Fetching is the caller's
113 * job (see sample_one_vector and write_one_vector), which is what keeps this
114 * cheap and independent of where the vectors live.
115 *
116 * `cluster_id_out` receives the list's cluster id from the head page.
117 */
118 /*
119 * Called once per live entry. Runs in a context the walk resets after every
120 * entry, so anything the callback allocates -- including whatever the
121 * backend's fetch allocates underneath it, which for a toasted vector is a
122 * whole TOAST reassembly -- goes away with that entry. The contract that
123 * buys: a callback must not allocate anything it needs after returning.
124 * Buffers that outlive an entry belong to the caller and are allocated
125 * before the walk.
126 */
127 typedef void (*ChainTidCb)(void *state, ItemPointerData tid);
128
129 /* State a tid walk carries across its pages. */
130 typedef struct ChainTidsCtx
131 {
132 Dimension dim;
133 ChainTidCb cb;
134 void *state;
135 ItemPointerData *tids; /* one page's worth, caller-owned */
136 uint32_t cap;
137 VsMemCtx entry_ctx;
138 void (*prefetch)(void *, ItemPointerData);
139 void *prefetch_ctx;
140 uint32_t *cluster_id_out;
141 } ChainTidsCtx;
142
143 static bool
144 808 walk_one_page_tids(PrismPostingChainPos *pos, void *state)
145 {
146 808 ChainTidsCtx *ctx = state;
147 808 const PrismPostingPageOpaque *op = prism_posting_opaque(pos->page);
148 808 Dimension dim = ctx->dim;
149 808 uint32_t cnt = op->entry_count;
150 808 uint32_t ntids = 0;
151
152
4/4
✓ Branch 0 taken 290 times.
✓ Branch 1 taken 518 times.
✓ Branch 2 taken 150 times.
✓ Branch 3 taken 140 times.
 808 if (pos->first && ctx->cluster_id_out != NULL)
153 150 *ctx->cluster_id_out = op->cluster_id;
154
155 /*
156 * ctx->cap sizes the tids buffer for the larger of the two formats, so
157 * clamping to it would still let an AoS page's entry loop run past the
158 * page. Reject against this page's own ceiling instead.
159 */
160 808 prism_posting_check_count(pos->blkno, op, dim);
161
162
1/2
✓ Branch 0 taken 808 times.
✗ Branch 1 not taken.
 808 if (!(op->flags & PRISM_POSTING_PAGE_TOMBSTONED))
163 {
164 808 char *content = prism_posting_page_content(pos->page, dim);
165
166
2/2
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 626 times.
 808 if (op->flags & PRISM_POSTING_PAGE_FASTSCAN)
167 {
168 /* SoA: tids live in fixed 32-entry group sections. The last
169 * group may be partial; entry_count bounds the valid slots.
170 * A lane VACUUM has tombstoned is dropped here the same way an
171 * AoS DELETED entry is below -- carrying it into the new list
172 * would resurrect it (see posting_convert.c for the same
173 * hazard on the conversion path). */
174 182 uint32_t ngroups = (cnt + VS_FASTSCAN_GROUP - 1) /
175 VS_FASTSCAN_GROUP;
176
2/2
✓ Branch 0 taken 1168 times.
✓ Branch 1 taken 182 times.
 1350 for (uint32_t g = 0; g < ngroups; g++)
177 {
178 712 ItemPointerData *gt =
179 1168 prism_fastscan_group_tids(content, g, dim);
180 1168 uint32_t mask =
181 1168 *prism_fastscan_group_tombstone_mask(content, g, dim);
182 1168 uint32_t base_i = g * VS_FASTSCAN_GROUP;
183 1168 uint32_t valid = (cnt - base_i) < VS_FASTSCAN_GROUP
184 ? (cnt - base_i)
185 : VS_FASTSCAN_GROUP;
186
2/2
✓ Branch 0 taken 35888 times.
✓ Branch 1 taken 1168 times.
 37056 for (uint32_t v = 0; v < valid; v++)
187 {
188
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 21500 times.
✓ Branch 2 taken 14388 times.
 35888 if (prism_fastscan_lane_is_tombstoned(mask, v))
189 12 continue;
190 35876 ctx->tids[ntids++] = gt[v];
191 }
192 }
193 }
194 else
195 {
196
2/2
✓ Branch 0 taken 123248 times.
✓ Branch 1 taken 626 times.
 123874 for (uint32_t i = 0; i < cnt; i++)
197 {
198 7924 PrismPostingEntryHeader *hdr =
199
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7924 times.
 123248 prism_posting_entry_at(content, i, dim);
200
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 123248 times.
 123248 if (hdr->meta.flags & PRISM_POSTING_FLAG_DELETED)
201 ✗ continue;
202 123248 ctx->tids[ntids++] = hdr->meta.tid;
203 }
204 }
205 }
206
207 /*
208 * The callback may write through this same storage -- the writing pass
209 * appends to page builders, which flush a full page as they go -- and
210 * the backend holds one page at a time, so a write during the callback
211 * would take over the slot this page occupies. Hence the tids were
212 * copied out above, and the page goes before any callback runs.
213 */
214 808 prism_posting_chain_release(pos);
215
216 /*
217 * Dispatch, starting the read for the next tid's block while the
218 * current one is being fetched. Only when the block changes: runs of
219 * tids share a heap block (a low-dimension table packs many rows per
220 * page), and re-requesting a block already in flight buys nothing.
221 */
222 808 BlockNumber prefetched = InvalidBlockNumber;
223 808 VsMemCtx outer = vs_memctx_switch(ctx->entry_ctx);
224
225
2/2
✓ Branch 0 taken 159124 times.
✓ Branch 1 taken 808 times.
 159932 for (uint32_t i = 0; i < ntids; i++)
226 {
227
4/4
✓ Branch 0 taken 29412 times.
✓ Branch 1 taken 129712 times.
✓ Branch 2 taken 29054 times.
✓ Branch 3 taken 358 times.
 159124 if (ctx->prefetch != NULL && i + 1 < ntids)
228 {
229 29054 BlockNumber nb = ItemPointerGetBlockNumber(&ctx->tids[i + 1]);
230
2/2
✓ Branch 0 taken 4114 times.
✓ Branch 1 taken 24940 times.
 29054 if (nb != prefetched)
231 {
232 4114 ctx->prefetch(ctx->prefetch_ctx, ctx->tids[i + 1]);
233 4114 prefetched = nb;
234 }
235 }
236 159124 ctx->cb(ctx->state, ctx->tids[i]);
237 159124 vs_memctx_reset(ctx->entry_ctx);
238 }
239
240 808 vs_memctx_switch(outer);
241 808 return true;
242 }
243
244 static void
245 290 walk_chain_tids(
246 VsStorage *storage,
247 Dimension dim,
248 BlockNumber head,
249 ChainTidCb cb,
250 void *state,
251 const PrismSplitEnv *env,
252 uint32_t *cluster_id_out)
253 {
254 /*
255 * One page's worth of tids, sized to whichever page format packs the
256 * most, from the same helpers page init uses to set max_entries -- so
257 * the cap cannot disagree with what a page reports.
258 */
259 290 uint32_t cap = prism_posting_max_entries_any_format(dim);
260 290 ItemPointerData *tids = vs_alloc((size_t)cap * sizeof(ItemPointerData));
261
262 /*
263 * Reset between entries, so per-entry allocations cannot accumulate over
264 * a list. This belongs here rather than in each backend's fetch: the walk
265 * is what knows there is an iteration, and leaving it to the fetch gives
266 * the guarantee on whichever backend remembered to implement it. Created
267 * after the tids buffer above, which has to outlive the resets.
268 */
269 1160 ChainTidsCtx ctx = {
270 .dim = dim,
271 .cb = cb,
272 .state = state,
273 .tids = tids,
274 .cap = cap,
275 .entry_ctx =
276 290 vs_memctx_create(vs_memctx_current(), "prism split entry"),
277
1/2
✓ Branch 0 taken 290 times.
✗ Branch 1 not taken.
 290 .prefetch = (env != NULL) ? env->prefetch_vector : NULL,
278
1/2
✓ Branch 0 taken 290 times.
✗ Branch 1 not taken.
 290 .prefetch_ctx = (env != NULL) ? env->ctx : NULL,
279 .cluster_id_out = cluster_id_out,
280 };
281
282 290 prism_posting_chain_walk(storage, head, walk_one_page_tids, &ctx);
283
284 290 vs_memctx_delete(ctx.entry_ctx);
285 290 vs_free(tids);
286 290 }
287
288 /* ----------------------------------------------------------------
289 * Pass 1: count and sample
290 * ---------------------------------------------------------------- */
291
292 /*
293 * One entry of the counting pass. Every fetchable entry is counted; one in
294 * every `stride` is copied into the sample, until the sample is full. An entry
295 * whose vector can no longer be fetched drops out of the split entirely, which
296 * is why the count here -- not the head's live_count -- is what the size
297 * decisions use.
298 */
299 static void
300 84662 sample_one_vector(void *state, ItemPointerData tid)
301 {
302 84662 SplitSample *s = (SplitSample *)state;
303 84662 Dimension dim = s->dim;
304
305
2/2
✓ Branch 1 taken 19500 times.
✓ Branch 2 taken 65162 times.
 84662 if (!s->env->fetch_vector(s->env->ctx, tid, s->one, dim))
306 4800 return;
307
308 79856 s->n_live++;
309
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 14780 times.
✓ Branch 2 taken 65076 times.
 79856 if (vector_is_degenerate(s->one, dim, s->metric))
310 {
311 80 s->n_degenerate++;
312 80 return;
313 }
314 /*
315 * Under cosine the clustering kernels take 1 - dot(x, c) and require unit
316 * vectors, and the bulk build normalizes before it encodes -- so the split
317 * has to as well, or it would cluster by magnitude and write codes the
318 * scan does not expect. A backend that already stores unit vectors is
319 * unaffected: normalizing again changes nothing.
320 */
321
2/2
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 78976 times.
 79776 if (s->metric == DISTANCE_COSINE)
322 800 vs_l2_normalize(s->one, dim);
323
324
2/2
✓ Branch 0 taken 58176 times.
✓ Branch 1 taken 21600 times.
 79776 if (s->count < s->cap)
325 {
326 /* Filling the reservoir. The buffer starts at what the head's count
327 * suggested and grows if that came out low. */
328
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58176 times.
 58176 if (s->count == s->alloc)
329 {
330 ✗ uint32_t want = (s->alloc < s->cap / 2) ? s->alloc * 2 : s->cap;
331 ✗ s->vecs = vs_realloc(s->vecs, (size_t)want * dim * sizeof(float));
332 ✗ s->alloc = want;
333 }
334 58176 memcpy(s->vecs + (size_t)s->count * dim,
335 58176 s->one,
336 58176 (size_t)dim * sizeof(float));
337 58176 s->count++;
338 }
339 else
340 {
341 /* Full: this entry takes a slot with probability cap/eligible, which
342 * leaves every eligible entry equally likely to be in the sample. */
343 21600 uint64_t j = splitmix64_next(&s->rng) % ((uint64_t)s->eligible + 1);
344
2/2
✓ Branch 0 taken 4580 times.
✓ Branch 1 taken 17020 times.
 21600 if (j < s->cap)
345 4580 memcpy(s->vecs + j * dim, s->one, (size_t)dim * sizeof(float));
346 }
347 79776 s->eligible++;
348 }
349
350 /*
351 * Draw the clustering sample. `est_entries` (the head's live_count) only sets
352 * the stride, so an inaccurate estimate costs sample size, never correctness:
353 * too high a stride simply samples fewer than the budget allows, and too low
354 * a one stops at the budget.
355 */
356 static void
357 150 sample_chain_vectors(
358 PrismIndexBase *base,
359 Dimension dim,
360 BlockNumber head,
361 const PrismSplitEnv *env,
362 uint32_t cap,
363 uint32_t est_entries,
364 uint64_t seed,
365 SplitSample *out,
366 uint32_t *cluster_id_out)
367 {
368 150 memset(out, 0, sizeof(*out));
369 150 out->dim = dim;
370 150 out->metric = base->metric;
371 150 out->env = env;
372 150 out->cap = cap;
373 150 out->rng = seed;
374
375 /*
376 * Size the buffer to what this list is expected to need, not to what the
377 * budget would allow: a generous budget must not cost a generous
378 * allocation on a list that does not fill it. The buffer grows if the
379 * estimate was low.
380 */
381 150 uint32_t want = (est_entries < cap) ? est_entries : cap;
382
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 150 if (want < 64)
383 ✗ want = 64;
384 150 out->alloc = want;
385 150 out->vecs = vs_alloc((size_t)want * dim * sizeof(float));
386 150 out->one = vs_alloc((size_t)dim * sizeof(float));
387
388 150 walk_chain_tids(
389 base->posting_storage,
390 dim,
391 head,
392 sample_one_vector,
393 out,
394 env,
395 cluster_id_out);
396 150 }
397
398 /* ----------------------------------------------------------------
399 * Undersized-cluster drop
400 * ---------------------------------------------------------------- */
401
402 /* What a sample tally of `tally` implies about the real cluster size. */
403 static uint32_t
404 860 estimate_cluster_size(uint32_t tally, uint32_t sampled, uint32_t n_live)
405 {
406
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 358 times.
 860 if (sampled == 0)
407 ✗ return 0;
408
2/2
✓ Branch 0 taken 222 times.
✓ Branch 1 taken 638 times.
 860 if (sampled == n_live)
409 222 return tally; /* the list was sampled whole -- exact */
410 136 return (uint32_t)((double)tally * (double)n_live / (double)sampled + 0.5);
411 }
412
413 /*
414 * Drop the clusters holding too few entries to be worth a posting list of
415 * their own, and compact the surviving centroids into `out` (k' * dim floats,
416 * in their original order). Returns k', or 0 if fewer than two survive.
417 *
418 * "Dropping a cluster" means dropping its centroid, before anything has been
419 * assigned to it. Nothing moves as a result: the writing pass sends each entry
420 * to the nearest centroid that survived, which is where a fold would have put
421 * the entries this cluster would have held.
422 *
423 * k-means minimizes distortion, not partition size, so a cluster can come out
424 * arbitrarily small -- an outlier becomes a partition of one. Writing that out
425 * as a posting list costs a whole page to hold one entry, spends a leaf
426 * centroid on a single vector it alone can route, and inflates nlist with
427 * partitions holding almost no data -- which skews the automatic probe count
428 * and the cost model, since both are derived from nlist.
429 *
430 * Survivors keep the position k-means elected for them; recomputing one to
431 * account for a handful of absorbed outliers would encode the many worse to
432 * encode the few better, and the resulting drift in nearest-partition
433 * assignment is what a reassign pass exists to clean up.
434 *
435 * Sizes come from the sample, scaled. A cluster with too few of the sample's
436 * points to clear the floor is either genuinely small or too small to measure,
437 * and both are reasons not to give it a list of its own.
438 */
439 static uint32_t
440 148 drop_undersized_clusters(
441 const KMeansResult *km,
442 const float *sample_vecs,
443 uint32_t k,
444 Dimension dim,
445 DistanceMetric metric,
446 uint32_t sampled,
447 uint32_t n_live,
448 uint32_t floor_entries,
449 float *out)
450 {
451 148 uint32_t tally[PRISM_SPLIT_MAX_PARTS] = {0};
452 98 bool live[PRISM_SPLIT_MAX_PARTS];
453 /* The sample's assignments, rewritten as centroids are dropped so the
454 * tallies keep describing what the writing pass will do. */
455 148 ClusterId *owner = vs_alloc((size_t)sampled * sizeof(ClusterId));
456
457
3/3
✓ Branch 0 taken 39876 times.
✓ Branch 1 taken 14750 times.
✓ Branch 2 taken 98 times.
 54724 for (uint32_t i = 0; i < sampled; i++)
458 {
459 54576 owner[i] = km->assignments[i];
460 54576 tally[owner[i]]++;
461 }
462
2/2
✓ Branch 0 taken 693 times.
✓ Branch 1 taken 148 times.
 841 for (uint32_t j = 0; j < k; j++)
463 693 live[j] = true;
464
465 50 uint32_t nlive = k;
466
467 112 for (;;)
468 27 {
469 /* Smallest surviving centroid that still misses the floor. */
470 175 uint32_t victim = UINT32_MAX;
471 175 uint32_t victim_sz = 0;
472
2/2
✓ Branch 0 taken 898 times.
✓ Branch 1 taken 175 times.
 1073 for (uint32_t j = 0; j < k; j++)
473 {
474
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 860 times.
 898 if (!live[j])
475 38 continue;
476
1/2
✓ Branch 0 taken 502 times.
✗ Branch 1 not taken.
 860 uint32_t sz = estimate_cluster_size(tally[j], sampled, n_live);
477
2/2
✓ Branch 0 taken 808 times.
✓ Branch 1 taken 52 times.
 860 if (sz >= floor_entries)
478 808 continue;
479
3/4
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
 52 if (victim == UINT32_MAX || sz < victim_sz)
480 {
481 538 victim = j;
482 538 victim_sz = sz;
483 }
484 }
485
2/2
✓ Branch 0 taken 49 times.
✓ Branch 1 taken 126 times.
 175 if (victim == UINT32_MAX)
486 42 break; /* every survivor clears the floor */
487
488
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 27 times.
 35 if (nlive <= 2)
489 {
490 /*
491 * Dropping another would leave one partition, which is not a
492 * split. Let the caller widen or decline: the data is one dense
493 * region plus stragglers, and emitting a partition of a handful of
494 * entries to be able to claim a split serves nobody.
495 */
496 8 return 0;
497 }
498
499 /* Re-home the victim's share of the sample so the tallies keep
500 * describing what the writing pass will do -- each of its points to
501 * the nearest centroid that survives, which is where that pass will
502 * send the entries it stood for. Only its own points can move. */
503
2/2
✓ Branch 0 taken 14373 times.
✓ Branch 1 taken 27 times.
 14400 for (uint32_t i = 0; i < sampled; i++)
504 {
505
2/2
✓ Branch 0 taken 14203 times.
✓ Branch 1 taken 170 times.
 14373 if (owner[i] != (ClusterId)victim)
506 14203 continue;
507
508 170 Vec32Ref v = {sample_vecs + (size_t)i * dim, dim};
509 170 uint32_t best = UINT32_MAX;
510 170 Distance best_d = 0;
511
2/2
✓ Branch 0 taken 1370 times.
✓ Branch 1 taken 170 times.
 1540 for (uint32_t j = 0; j < k; j++)
512 {
513
4/4
✓ Branch 0 taken 1318 times.
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 170 times.
✓ Branch 3 taken 1148 times.
 1370 if (!live[j] || j == victim)
514 222 continue;
515 1148 Vec32Ref c = {centroid_at(km->centroids, j, dim), dim};
516 1148 Distance d = vs_distance(v, c, metric);
517
4/4
✓ Branch 0 taken 909 times.
✓ Branch 1 taken 239 times.
✓ Branch 2 taken 226 times.
✓ Branch 3 taken 476 times.
 1148 if (best == UINT32_MAX || d < best_d)
518 {
519 525 best = j;
520 525 best_d = d;
521 }
522 }
523 170 owner[i] = (ClusterId)best;
524 170 tally[best]++;
525 }
526
527 27 tally[victim] = 0;
528 27 live[victim] = false;
529 27 nlive--;
530 }
531
532
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 140 times.
 140 if (nlive < 2)
533 ✗ return 0;
534
535 /* Compact survivors, preserving order: the caller gives the first one the
536 * retiring list's cluster id, and reordering would hand it elsewhere. */
537 42 uint32_t next = 0;
538
2/2
✓ Branch 0 taken 671 times.
✓ Branch 1 taken 140 times.
 811 for (uint32_t j = 0; j < k; j++)
539 {
540
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 650 times.
 671 if (!live[j])
541 21 continue;
542 832 memcpy(out + (size_t)next * dim,
543 650 centroid_at(km->centroids, j, dim),
544 650 (size_t)dim * sizeof(float));
545 650 next++;
546 }
547 42 return nlive;
548 }
549
550 /* ----------------------------------------------------------------
551 * Pass 2: assign and write
552 * ---------------------------------------------------------------- */
553
554 /*
555 * Streaming writer: k page builders, and each entry appended to the one whose
556 * centroid is nearest. The builders assemble pages in their own memory and
557 * only touch storage to flush a full page, so holding k of them open costs k
558 * page images rather than k pinned buffers.
559 */
560 typedef struct SplitWriter
561 {
562 PrismPostingBuilder *builders;
563 uint32_t k;
564 const float *centroids; /* k * dim */
565 uint32_t *counts; /* entries written per builder */
566 Dimension dim;
567 DistanceMetric metric;
568 const PrismSplitEnv *env;
569 float *one;
570 } SplitWriter;
571
572 static void
573 74462 write_one_vector(void *state, ItemPointerData tid)
574 {
575 74462 SplitWriter *w = (SplitWriter *)state;
576 74462 Dimension dim = w->dim;
577
578
2/2
✓ Branch 1 taken 15900 times.
✓ Branch 2 taken 58562 times.
 74462 if (!w->env->fetch_vector(w->env->ctx, tid, w->one, dim))
579 1200 return; /* gone from the heap since the counting pass */
580
581 14700 uint32_t target;
582
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14700 times.
 73256 bool degenerate = vector_is_degenerate(w->one, dim, w->metric);
583
584 /* Same unit-vector contract as the sampling pass, and for the same two
585 * reasons: the centroids were elected in that space, and the builder
586 * encodes against them. */
587
4/4
✓ Branch 0 taken 73176 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 800 times.
✓ Branch 3 taken 72376 times.
 73256 if (!degenerate && w->metric == DISTANCE_COSINE)
588 800 vs_l2_normalize(w->one, dim);
589
590
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 73176 times.
 73256 if (degenerate)
591 {
592 /*
593 * No centroid can claim it and it can never be a result, so the only
594 * thing the choice affects is how evenly the lists come out: give it
595 * to whichever is smallest so far.
596 */
597 80 target = 0;
598
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 80 times.
 320 for (uint32_t j = 1; j < w->k; j++)
599
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 164 times.
 240 if (w->counts[j] < w->counts[target])
600 76 target = j;
601 }
602 else
603 {
604 73176 Vec32Ref v = {w->one, dim};
605 73176 Distance best = 0;
606 73176 target = 0;
607
2/2
✓ Branch 0 taken 553856 times.
✓ Branch 1 taken 73176 times.
 627032 for (uint32_t j = 0; j < w->k; j++)
608 {
609 553856 Vec32Ref c = {centroid_at(w->centroids, j, dim), dim};
610 553856 Distance d = vs_distance(v, c, w->metric);
611
4/4
✓ Branch 0 taken 417781 times.
✓ Branch 1 taken 136075 times.
✓ Branch 2 taken 70890 times.
✓ Branch 3 taken 311986 times.
 553856 if (j == 0 || d < best)
612 {
613 164271 best = d;
614 164271 target = j;
615 }
616 }
617 }
618
619 73256 prism_posting_builder_add_ex(
620 73256 &w->builders[target], tid, w->one, degenerate);
621 73256 w->counts[target]++;
622 }
623
624 static void
625 244 tombstone_page(PrismPostingPageOpaque *op, void *state)
626 {
627 32 (void)state;
628 244 op->flags |= PRISM_POSTING_PAGE_TOMBSTONED;
629 244 }
630
631 void
632 66 prism_posting_chain_tombstone(VsStorage *storage, BlockNumber head)
633 {
634 66 prism_posting_chain_mutate(storage, head, tombstone_page, NULL);
635 66 }
636
637 /* ----------------------------------------------------------------
638 * Centroid-tree flip
639 * ---------------------------------------------------------------- */
640
641 /*
642 * In the flat (nlevels == 1) tree, find the leaf entry whose child_blkno ==
643 * head, and the last page of the level-0 chain (append target). Returns 0 on
644 * success, -1 if the leaf entry was not found.
645 */
646 static int
647 140 find_leaf_and_tail(
648 VsStorage *storage,
649 BlockNumber first_centroid,
650 BlockNumber head,
651 BlockNumber *found_page,
652 uint32_t *found_idx,
653 BlockNumber *tail_page,
654 uint8_t *level)
655 {
656 /*
657 * Define every output up front. Only found_page and tail_page are
658 * meaningful when this fails, and the other two are written solely on
659 * the path that finds the leaf -- so a caller that skipped the return
660 * value, or a compiler that cannot correlate found_idx's write with
661 * found_page's, sees an indeterminate value (GCC warns about exactly
662 * that at -O2).
663 */
664 140 *found_page = InvalidBlockNumber;
665 140 *tail_page = InvalidBlockNumber;
666 140 *found_idx = 0;
667 140 *level = 0;
668
669 140 BlockNumber blk = first_centroid;
670
2/2
✓ Branch 0 taken 202 times.
✓ Branch 1 taken 140 times.
 342 while (blk != InvalidBlockNumber)
671 {
672 202 Page page = vs_storage_read_page(storage, blk);
673 202 const PrismCentroidPageOpaque *op = PRISM_CENTROID_OPAQUE(page);
674 202 uint16_t cnt = op->entry_count;
675 202 BlockNumber next = op->next_blkno;
676 202 *level = op->level;
677
678
2/2
✓ Branch 0 taken 5196 times.
✓ Branch 1 taken 202 times.
 5398 for (uint16_t i = 0; i < cnt; i++)
679 {
680
2/2
✓ Branch 1 taken 140 times.
✓ Branch 2 taken 5056 times.
 5196 if (prism_centroid_meta(page, i)->child_blkno == head)
681 {
682 140 *found_page = blk;
683 140 *found_idx = i;
684 }
685 }
686
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 62 times.
 202 if (next == InvalidBlockNumber)
687 140 *tail_page = blk;
688
689 202 vs_storage_release_page(storage, blk);
690 202 blk = next;
691 }
692
693
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 42 times.
 140 return (*found_page == InvalidBlockNumber) ? -1 : 0;
694 }
695
696 /*
697 * True if `page` has room for `n` more centroid entries in the split's format.
698 * Generalizes prism_centroid_page_has_room (which checks one) to n, so the
699 * flip can decide up front whether all k-1 new leaves fit on the old leaf's
700 * page. Uses data_size (not leaf_data_size) to match
701 * prism_centroid_page_add_entry.
702 */
703 static bool
704 108 centroid_page_has_room_for(Page page, Dimension dim, uint32_t n)
705 {
706 108 PageHeader h = (PageHeader)page;
707 108 PrismCentroidFormat fmt = prism_centroid_page_format(page);
708 108 size_t per = prism_centroid_meta_size(fmt) +
709 108 prism_centroid_data_size(dim, fmt);
710 240 size_t lower = prism_centroid_meta_end(
711 108 page, PRISM_CENTROID_OPAQUE(page)->entry_count);
712 108 return lower + (size_t)n * per <= (size_t)h->pd_upper;
713 }
714
715 /* ----------------------------------------------------------------
716 * Split
717 * ---------------------------------------------------------------- */
718
719 /*
720 * Draw the clustering sample and cluster it. Writes up to
721 * PRISM_SPLIT_MAX_PARTS centroids into `centroids`, which the caller owns and
722 * which outlives this phase, and returns how many stand (>= 2), 0 when the
723 * split is declined, -1 on error.
724 *
725 * Called inside a context of its own, which the caller deletes: the sample
726 * buffer is the split's largest allocation -- the whole budget -- and the
727 * k-means workspace sits beside it, so both have to be gone before the
728 * writing pass allocates. Nothing here frees anything by hand, deliberately.
729 * vs_free does nothing on the standalone allocator, where memory returns
730 * only when a context is reset, so hand-freeing would bound the peak on
731 * PostgreSQL and silently not bound it standalone. A context boundary means
732 * the same thing on both.
733 *
734 * The centroids are the only result that outlives the phase, so they are
735 * written into the caller's buffer rather than allocated here -- otherwise
736 * they would die with the context. Its size does not depend on the sample:
737 * the width can grow while widening, so it is always PRISM_SPLIT_MAX_PARTS
738 * wide.
739 */
740 static int
741 150 sample_and_cluster(
742 PrismIndexBase *base,
743 Dimension dim,
744 BlockNumber head,
745 const PrismSplitConfig *cfg,
746 const PrismSplitEnv *env,
747 uint32_t min_split_entries,
748 float *centroids,
749 uint32_t *cluster_id_out)
750 {
751 /*
752 * 1. Count the list and draw the clustering sample, in one pass.
753 *
754 * The head's live_count only estimates the size -- it does not account for
755 * entries whose vector can no longer be fetched -- so it sets the sample
756 * stride and nothing else. The count this pass returns is what the size
757 * decisions use.
758 */
759
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 122 times.
 128 uint64_t budget = (cfg != NULL && cfg->sample_budget_bytes)
760 ? cfg->sample_budget_bytes
761
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 22 times.
 180 : PRISM_SPLIT_SAMPLE_BUDGET_BYTES;
762 150 uint32_t cap = prism_split_sample_cap(budget, dim);
763
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 150 times.
 150 if (cap == 0)
764 ✗ return -1; /* the budget cannot pay for a split at this dimension */
765 150 uint32_t est = head_live_count(base->posting_storage, head);
766
767 98 SplitSample smp;
768 150 uint32_t cluster_id = 0;
769
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 30 times.
 128 uint64_t seed = (cfg != NULL && cfg->km_seed) ? cfg->km_seed
770
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 22 times.
 180 : PRISM_SPLIT_SAMPLE_SEED;
771 150 sample_chain_vectors(
772 base, dim, head, env, cap, est, seed, &smp, &cluster_id);
773
774
3/4
✓ Branch 0 taken 146 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 146 times.
 150 if (smp.n_live < min_split_entries || smp.n_live < 2)
775 4 return 0; /* declined: too few entries */
776
777 /*
778 * 2. Re-check the size now that the list has been counted, then pick k.
779 *
780 * With a target size the caller gets both from one number: the split is
781 * declined unless the counted entries still exceed the trigger, and the
782 * width is round(count / target) so each new list rests at the target.
783 * Without a target, k defaults to 2 and cfg->nparts may override.
784 *
785 * Clamp to [2, PRISM_SPLIT_MAX_PARTS] and to the sample size (k-means
786 * needs k <= n). A list needing more than PRISM_SPLIT_MAX_PARTS is
787 * narrowed to the cap and stays above the trigger; a further pass splits
788 * it again.
789 */
790
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 22 times.
 146 uint32_t target = (cfg != NULL) ? cfg->target_entries : 0;
791 98 uint32_t k;
792
793
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 29 times.
 146 if (target > 0)
794 {
795
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 99 times.
✓ Branch 2 taken 18 times.
 117 if ((uint64_t)smp.n_live <= prism_split_trigger(target))
796 4 return 0; /* declined: inside the operating band */
797
798 /*
799 * Round, do not ceil. The width has to put each new list *at* the
800 * target, and at the trigger the count is just over target*factor:
801 * ceil would give factor+1 parts and land them all below the target
802 * (0.67*target at factor 2), so a fresh list would start below where
803 * it is supposed to rest. Rounding gives exactly `factor` parts there
804 * -- a bisection at factor 2, as in LIRE -- and keeps parts within
805 * [0.75, 1.25] of the target everywhere else.
806 */
807 113 uint64_t want = ((uint64_t)smp.n_live + target / 2) / target;
808
2/2
✓ Branch 0 taken 95 times.
✓ Branch 1 taken 18 times.
 113 if (want < 2)
809 ✗ want = 2;
810 113 k = (want > PRISM_SPLIT_MAX_PARTS) ? PRISM_SPLIT_MAX_PARTS
811
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 5 times.
 113 : (uint32_t)want;
812 }
813 else
814 {
815
3/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 29 k = (cfg != NULL && cfg->nparts > 2) ? cfg->nparts : 2;
816 }
817
818 /* Only entries a centroid can represent were sampled. */
819
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 142 times.
 142 if (smp.count < 2)
820 {
821 /* Nothing to cluster: every entry is unreachable under this metric,
822 * and no arrangement of them improves a query. */
823 ✗ return 0;
824 }
825
826 142 KMeansOptions opts = VS_KMEANS_OPTIONS_DEFAULT;
827
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 22 times.
 142 if (cfg != NULL)
828 {
829
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 120 times.
 120 if (cfg->km_max_iter)
830 ✗ opts.max_iterations = cfg->km_max_iter;
831
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 120 times.
 120 if (cfg->km_seed)
832 ✗ opts.seed = cfg->km_seed;
833 }
834
835
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44 times.
 142 if (k > PRISM_SPLIT_MAX_PARTS)
836 ✗ k = PRISM_SPLIT_MAX_PARTS;
837
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44 times.
 142 if (k > smp.count)
838 ✗ k = smp.count;
839
840 /*
841 * When the list did not fit the budget, ask for no more partitions than
842 * the sample can speak for -- see PRISM_SPLIT_MIN_SAMPLE_PER_PART. A list
843 * too big for its budget is split less far per pass, not split badly.
844 * A list sampled whole needs no such limit: its tallies are the real
845 * sizes, not estimates of them.
846 */
847 142 uint32_t clusterable = smp.n_live - smp.n_degenerate;
848
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 136 times.
 142 if (smp.count < clusterable)
849 {
850 6 uint32_t k_sample_max = smp.count / PRISM_SPLIT_MIN_SAMPLE_PER_PART;
851
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (k_sample_max < 2)
852 ✗ k_sample_max = 2;
853
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 6 if (k > k_sample_max)
854 100 k = k_sample_max;
855 }
856
857 /*
858 * The floor a partition must clear to be worth its own centroid. With a
859 * target that is the bottom of the operating band, so a split never emits
860 * a list maintenance would immediately want to merge away. Without one
861 * there is no size to reason from and the caller is asking for an
862 * unconditional split, so only empty clusters are dropped.
863 */
864 237 uint32_t floor_entries = (target > 0) ? target / PRISM_SPLIT_TRIGGER_FACTOR
865
2/2
✓ Branch 0 taken 113 times.
✓ Branch 1 taken 29 times.
 142 : 1;
866
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44 times.
 139 if (floor_entries < 1)
867 98 floor_entries = 1;
868
869 /*
870 * Cluster the sample, then drop the clusters holding too few entries to be
871 * worth a list of their own (see drop_undersized_clusters -- an empty
872 * cluster is just the extreme case, so no separate empty check is
873 * needed).
874 *
875 * If dropping cannot leave two centroids standing, widen and retry before
876 * giving up. At the trigger the width is a bisection, so a list that is
877 * one dense region plus a straggler has no second partition clearing the
878 * floor and would decline -- and, the k-means seed being fixed, decline
879 * again on every later pass, leaving a list above the trigger forever. One
880 * more partition usually resolves it: the bulk splits in two and the
881 * straggler goes to whichever half is nearer. Bounded, because the answer
882 * for genuinely unsplittable data (identical vectors, say) is to decline
883 * rather than to keep re-clustering.
884 */
885 142 uint32_t nparts = 0;
886
887
2/2
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 2 times.
 150 for (uint32_t attempt = 0; attempt <= PRISM_SPLIT_WIDEN_ATTEMPTS;
888 8 attempt++)
889 {
890 246 KMeansResult *km = vs_kmeans_f32(
891 148 smp.vecs, smp.count, dim, k, base->metric, &opts);
892
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 148 times.
 148 if (km == NULL)
893 ✗ return -1;
894
895 246 nparts = drop_undersized_clusters(
896 km,
897 148 smp.vecs,
898 k,
899 dim,
900 base->metric,
901 smp.count,
902 148 smp.n_live - smp.n_degenerate,
903 floor_entries,
904 centroids);
905 148 vs_kmeans_result_destroy(km);
906
907
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 106 times.
 148 if (nparts >= 2)
908 42 break;
909
2/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 if (k + 1 > PRISM_SPLIT_MAX_PARTS || k + 1 > smp.count)
910 break;
911 8 k++;
912 }
913
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 140 times.
 142 if (nparts < 2)
914 2 return 0; /* degenerate: no two partitions clear the floor */
915
916 140 *cluster_id_out = cluster_id;
917 140 return (int)nparts;
918 }
919
920 /*
921 * Release what the writing pass allocated. Both the error path out of the
922 * flip and the normal end need exactly this, and a seventh allocation added
923 * to one copy and not the other is how that kind of pair goes wrong.
924 *
925 * A context would also collapse the two, but the writing pass has nothing to
926 * release early -- everything here lives until the split ends -- so the
927 * problem is duplication, not peak, and this is the smaller tool for it.
928 */
929 static void
930 140 write_phase_cleanup(
931 RaBitQScratch *scratch,
932 RaBitQData **rd,
933 uint32_t k,
934 float *pt_res,
935 float *pt_c,
936 float *centroids)
937 {
938 140 vs_rabitq_scratch_cleanup(scratch);
939
3/3
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 510 times.
✓ Branch 2 taken 98 times.
 790 for (uint32_t j = 0; j < k; j++)
940 650 vs_free(rd[j]);
941 140 vs_free_aligned(pt_res);
942 140 vs_free_aligned(pt_c);
943 140 vs_free(centroids);
944 140 }
945
946 /*
947 * Split the oversized posting list at `head` into two balanced lists.
948 *
949 * Locking. The caller holds an exclusive lock on this cluster (in PG a
950 * heavyweight page lock on the head; a no-op standalone). That lock, not the
951 * index-relation lock, is the concurrency gate: convert/split/insert take only
952 * the index's RowExclusiveLock, which does not conflict with itself, so the
953 * per-cluster lock is what serializes this split against inserts and other
954 * splits of the same list and makes the snapshot of the old entries and the
955 * centroid flip atomic with respect to writers. The caller releases it once
956 * this returns.
957 *
958 * Why new blocks instead of an in-place rewrite. The split builds two fresh
959 * chains, then repoints the centroid leaf at them in a single page write (the
960 * flip in step 7). That flip is the atomic commit point: before it the old
961 * list is authoritative, after it the two new lists are. Consequences:
962 * - Crash-safety: a crash can only leak the freshly written, still
963 * unreferenced pages; it can never corrupt or lose entries, because the
964 * old chain is untouched until the flip and the new chains are fully
965 * committed before it.
966 * - Concurrency: a scanner that read the leaf pointer *before* the flip
967 * still holds the old head and must see the complete pre-split list. New
968 * blocks leave that old chain byte-for-byte intact, so such a scanner
969 * reads it correctly. An in-place reorder would move entries out from
970 * under that scanner (it would miss whatever was routed to the other new
971 * list). This is why the old chain is retired, not overwritten: a backend
972 * with MVCC snapshots defers reclaiming it behind a visibility gate
973 * (env->retire_chain) so an in-flight scan is never cut off; standalone,
974 * where no snapshot-holding scanner exists, it is tombstoned immediately.
975 * A retired chain's pages are not reused: they stay allocated to the
976 * relation once the chain is tombstoned.
977 */
978 int
979 150 prism_posting_split(
980 PrismIndexBase *base,
981 BlockNumber head,
982 const PrismSplitConfig *cfg,
983 const PrismSplitEnv *env,
984 PrismSplitResult *out)
985 {
986 150 PrismSplitResult res = {0};
987
988
5/8
✓ Branch 0 taken 150 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 150 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 52 times.
✓ Branch 5 taken 98 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 52 times.
 150 if (base == NULL || env == NULL || env->fetch_vector == NULL ||
989 head == InvalidBlockNumber)
990 ✗ return -1;
991
992 /* Phase-1 scope: flat tree + RaBitQ centroid format only. */
993
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 98 times.
 150 if (base->nlevels != 1 ||
994
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 150 times.
 150 base->centroid_format != PRISM_CENTROID_FMT_RABITQ)
995 ✗ return -1;
996
997 150 RaBitQParams *params = prism_index_ensure_rabitq(base);
998
3/4
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 150 times.
 150 if (params == NULL || base->pt_global_mean == NULL)
999 ✗ return -1;
1000
1001 150 Dimension dim = base->dim;
1002
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 28 times.
 128 uint32_t min_split_entries = (cfg && cfg->min_split_entries)
1003 ? cfg->min_split_entries
1004
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 22 times.
 180 : 2;
1005 /*
1006 * 1-2. Sample, count and cluster, in a context that goes away with the
1007 * sample buffer inside it. See sample_and_cluster: the phase boundary is
1008 * a context boundary so that it bounds the peak on both allocators, not
1009 * just on the one where vs_free frees.
1010 */
1011 150 float *centroids = vs_alloc(
1012 (size_t)PRISM_SPLIT_MAX_PARTS * dim * sizeof(float));
1013
1014 98 VsMemCtx work =
1015 150 vs_memctx_create(vs_memctx_current(), "prism split sample");
1016 150 VsMemCtx old = vs_memctx_switch(work);
1017
1018 150 uint32_t cluster_id = 0;
1019 150 int nparts = sample_and_cluster(
1020 base,
1021 dim,
1022 head,
1023 cfg,
1024 env,
1025 min_split_entries,
1026 centroids,
1027 &cluster_id);
1028
1029 150 vs_memctx_switch(old);
1030 150 vs_memctx_delete(work);
1031
1032
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 140 times.
 150 if (nparts < 2)
1033 {
1034
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (out != NULL)
1035 10 *out = res;
1036
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 return nparts < 0 ? -1 : 0;
1037 }
1038 140 uint32_t k = (uint32_t)nparts;
1039
1040 /*
1041 * 3. Write the k new lists in one streaming pass, encoding each entry
1042 * against the centroid of the list it lands in. New lists take the index's
1043 * posting format, so a split also upgrades a list that had drifted to AoS
1044 * back to fastscan (a re-optimization point). new_head[0] reuses the old
1045 * cluster id; new_head[1..] get fresh ids.
1046 */
1047 /*
1048 * Reserve the ids durably before using them -- see
1049 * PrismSplitEnv.reserve_nlist. Raised first, so a crash before the new
1050 * leaves are reachable leaves the count too high, which costs nothing but
1051 * a gap in the ids; the other order hands the same ids out twice.
1052 */
1053 140 uint32_t first_new_id = base->nlist;
1054 140 base->nlist += (k - 1);
1055
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 42 times.
 140 if (env->reserve_nlist != NULL)
1056 98 env->reserve_nlist(env->ctx, base->nlist);
1057
1058 140 bool fastscan = (base->fastscan != 0);
1059 98 BlockNumber new_head[PRISM_SPLIT_MAX_PARTS];
1060 98 RaBitQData *rd[PRISM_SPLIT_MAX_PARTS];
1061 140 uint32_t counts[PRISM_SPLIT_MAX_PARTS] = {0};
1062 140 float *pt_c = vs_alloc_aligned((size_t)dim * sizeof(float), 64);
1063 140 float *pt_res = vs_alloc_aligned((size_t)dim * sizeof(float), 64);
1064 98 RaBitQScratch scratch;
1065 140 vs_rabitq_scratch_init(&scratch, dim);
1066
1067 140 PrismPostingBuilder *builders = vs_alloc(
1068 42 (size_t)k * sizeof(PrismPostingBuilder));
1069
3/3
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 510 times.
✓ Branch 2 taken 98 times.
 790 for (uint32_t j = 0; j < k; j++)
1070 {
1071 650 const float *centroid = centroid_at(centroids, j, dim);
1072 650 vs_rabitq_rotate(params, centroid, pt_c);
1073
1074 /* Not `cid`: that is a command id in PostgreSQL. */
1075
2/2
✓ Branch 0 taken 510 times.
✓ Branch 1 taken 140 times.
 650 uint32_t new_cluster = (j == 0) ? cluster_id : first_new_id + (j - 1);
1076 650 prism_posting_builder_init_fmt(
1077 650 &builders[j],
1078 base->posting_storage,
1079 params,
1080 dim,
1081 new_cluster,
1082 centroid,
1083 pt_c,
1084 fastscan);
1085
1086 /* Routing centroid for the leaf entry: encode (pt_c - pt_mean), which
1087 * matches encode_into(c, mean) used at build. */
1088 650 rd[j] = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
1089
2/2
✓ Branch 0 taken 351829 times.
✓ Branch 1 taken 650 times.
 352479 for (Dimension d = 0; d < dim; d++)
1090 351829 pt_res[d] = pt_c[d] - base->pt_global_mean[d];
1091 650 vs_rabitq_encode_from_pt(params, pt_res, rd[j], &scratch);
1092 }
1093
1094 280 SplitWriter w = {
1095 .builders = builders,
1096 .k = k,
1097 .centroids = centroids,
1098 .counts = counts,
1099 .dim = dim,
1100 140 .metric = base->metric,
1101 .env = env,
1102 140 .one = vs_alloc((size_t)dim * sizeof(float)),
1103 };
1104 140 walk_chain_tids(
1105 base->posting_storage, dim, head, write_one_vector, &w, env, NULL);
1106 140 vs_free(w.one);
1107
1108
3/3
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 510 times.
✓ Branch 2 taken 98 times.
 790 for (uint32_t j = 0; j < k; j++)
1109 650 new_head[j] = prism_posting_builder_finish(&builders[j]);
1110
2/2
✓ Branch 0 taken 650 times.
✓ Branch 1 taken 140 times.
 790 for (uint32_t j = 0; j < k; j++)
1111 650 prism_posting_builder_cleanup(&builders[j]);
1112 140 vs_free(builders);
1113 /* 4. Flip the centroid tree: locate the old leaf entry + chain tail. */
1114 98 BlockNumber found_page, tail_page;
1115 98 uint32_t found_idx;
1116 140 uint8_t level = 0;
1117 140 int rc = find_leaf_and_tail(
1118 base->centroid_storage,
1119 base->first_centroid,
1120 head,
1121 &found_page,
1122 &found_idx,
1123 &tail_page,
1124 &level);
1125
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 140 times.
 140 if (rc != 0)
1126 {
1127 /* Should not happen: the head must be reachable from the tree. */
1128 ✗ write_phase_cleanup(&scratch, rd, k, pt_res, pt_c, centroids);
1129 ✗ return -1;
1130 }
1131
1132 /*
1133 * Test hook: fires with the new chains fully written and committed but
1134 * the tree still pointing at the old head, which is the window the
1135 * crash-safety argument rests on. A crash here must leave the old list
1136 * authoritative and leak only the new, unreferenced pages.
1137 */
1138 98 VS_INJECTION_POINT("prism-split-before-flip");
1139
1140 /*
1141 * Flip: repoint the old leaf at new_head[0] and add leaves for the k-1
1142 * extra heads.
1143 *
1144 * Fast path (the common flat single-page tree): when the old leaf and the
1145 * chain tail are the same centroid page and all k-1 extra leaves fit on
1146 * it, do the whole flip in one page write. A concurrent scan reading that
1147 * page then observes only the pre- or post-flip state -- never both the
1148 * old head and a new head -- so it never scans (then dedups) the same
1149 * vectors twice. This is one buffer-lock hold and one WAL record, cheaper
1150 * than the per-entry commits below, not a heavyweight lock.
1151 */
1152 140 uint32_t appended_centroid_pages = 0;
1153 140 bool single_page = false;
1154
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 32 times.
 140 if (found_page == tail_page)
1155 {
1156 108 Page cp = vs_storage_read_page(base->centroid_storage, found_page);
1157 108 single_page = centroid_page_has_room_for(cp, dim, k - 1);
1158 108 vs_storage_release_page(base->centroid_storage, found_page);
1159 }
1160
1161
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 36 times.
 140 if (single_page)
1162 {
1163 104 Page fp = vs_storage_write_page(base->centroid_storage, found_page);
1164 104 prism_centroid_page_overwrite_entry(
1165 104 fp, dim, found_idx, new_head[0], rd[0]);
1166
3/3
✓ Branch 0 taken 138 times.
✓ Branch 1 taken 270 times.
✓ Branch 2 taken 64 times.
 472 for (uint32_t j = 1; j < k; j++)
1167 368 prism_centroid_page_add_entry(
1168 368 fp, dim, new_head[j], 0, PRISM_CENTROID_FLAG_LEAF, rd[j]);
1169 104 vs_storage_commit_page(base->centroid_storage, found_page);
1170 }
1171 else
1172 {
1173 /*
1174 * Fallback (tail on another page, or the page can't hold all k-1): a
1175 * multi-page flip can't be one atomic write. Append the k-1 new leaves
1176 * first -- chaining a new level-0 page as the tail fills -- then
1177 * overwrite the old leaf last. Appending first keeps the old leaf on
1178 * the full old list until that final overwrite, so a mid-flip scan
1179 * never misses entries; it may briefly reach both a new head and the
1180 * old head, but those duplicate vectors are dropped by the top-k's id
1181 * dedup (the same path that dedups SOAR replicas), so results stay
1182 * correct.
1183 */
1184
2/2
✓ Branch 0 taken 142 times.
✓ Branch 1 taken 36 times.
 178 for (uint32_t j = 1; j < k; j++)
1185 {
1186 142 Page tp = vs_storage_write_page(base->centroid_storage, tail_page);
1187 282 bool appended = prism_centroid_page_add_entry(
1188 142 tp, dim, new_head[j], 0, PRISM_CENTROID_FLAG_LEAF, rd[j]);
1189 142 vs_storage_commit_page(base->centroid_storage, tail_page);
1190
1191
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 136 times.
 142 if (!appended)
1192 {
1193 4 BlockNumber np;
1194 6 Page npg = vs_storage_new_page(base->centroid_storage, &np);
1195 6 prism_centroid_page_init_fmt(
1196 npg, level, base->centroid_format);
1197 6 prism_centroid_page_add_entry(
1198 npg,
1199 dim,
1200 new_head[j],
1201 0,
1202 PRISM_CENTROID_FLAG_LEAF,
1203 2 rd[j]);
1204 6 vs_storage_commit_page(base->centroid_storage, np);
1205
1206 6 Page link = vs_storage_write_page(
1207 base->centroid_storage, tail_page);
1208 6 PRISM_CENTROID_OPAQUE(link)->next_blkno = np;
1209 6 vs_storage_commit_page(base->centroid_storage, tail_page);
1210
1211 6 tail_page = np;
1212 6 appended_centroid_pages++;
1213 }
1214 }
1215
1216 36 Page fp = vs_storage_write_page(base->centroid_storage, found_page);
1217 36 prism_centroid_page_overwrite_entry(
1218 36 fp, dim, found_idx, new_head[0], rd[0]);
1219 36 vs_storage_commit_page(base->centroid_storage, found_page);
1220 }
1221
1222 /*
1223 * 5. Retire the old chain, now unreachable via the tree. A concurrent
1224 * scanner may still hold a stale head pointer read before the flip, so the
1225 * backend that can see snapshots (PG) defers reclaim behind an XID gate,
1226 * keeping the chain readable meanwhile. Where there are no such scanners
1227 * (env->retire_chain == NULL, e.g. standalone), tombstone it immediately.
1228 */
1229
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 40 times.
 140 if (env->retire_chain != NULL)
1230 100 env->retire_chain(env->ctx, base->posting_storage, head);
1231 else
1232 40 prism_posting_chain_tombstone(base->posting_storage, head);
1233
1234 608 res.did_split = true;
1235 608 res.nparts = k;
1236
2/2
✓ Branch 0 taken 650 times.
✓ Branch 1 taken 140 times.
 790 for (uint32_t j = 0; j < k; j++)
1237 {
1238 650 res.head[j] = new_head[j];
1239 650 res.count[j] = counts[j];
1240 }
1241 140 res.new_nlist = base->nlist;
1242 140 res.new_centroid_pages = appended_centroid_pages;
1243 140 base->ncentroid_pages += appended_centroid_pages;
1244
1245 140 write_phase_cleanup(&scratch, rd, k, pt_res, pt_c, centroids);
1246
1247
1/2
✓ Branch 0 taken 140 times.
✗ Branch 1 not taken.
 140 if (out != NULL)
1248 140 *out = res;
1249 42 return 0;
1250 }
1251