GCC Code Coverage Report

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