GCC Code Coverage Report


Directory: src/
File: src/index/posting_split.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 404 425 95.1%
Functions: 18 18 100.0%
Branches: 217 256 84.8%

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