GCC Code Coverage Report


Directory: src/
File: src/index/posting_split.h
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 23 25 92.0%
Functions: 3 3 100.0%
Branches: 7 9 77.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.h - Incremental posting-list split (SPFresh/LIRE)
6 *
7 * Splits one oversized posting list into two or more balanced lists, keeping
8 * partition quality close to a from-scratch build without a global rebuild.
9 * The core is backend-neutral (operates on PrismIndexBase + VsStorage), so
10 * the standalone engine and the PostgreSQL extension share it.
11 *
12 * Splits into k >= 2 partitions. With PrismSplitConfig.target_entries the
13 * width is derived from the counted entries, so a list far past its trigger is
14 * right-sized in one pass rather than by repeated 2-way bisection -- one flat
15 * k-means also beats greedy hierarchical halving. Without a target,
16 * PrismSplitConfig.nparts decides, defaulting to 2.
17 *
18 * The list is streamed, not held: holding every vector at full precision costs
19 * entries * dim * 4 bytes, which would make splitting an oversized list fail
20 * in proportion to how oversized it is. Two passes over the chain, and the
21 * memory is a sample the caller's budget pays for -- see
22 * PrismSplitConfig.sample_budget_bytes and prism_split_sample_cap.
23 *
24 * Algorithm (one cluster, caller holds an exclusive lock on it):
25 * 1. Walk the chain, counting the entries whose vectors can still be
26 * fetched (via PrismSplitEnv — heap fetch in PG, in-RAM copy standalone)
27 * and reservoir-sampling them into the clustering buffer. That count,
28 * not the head's live_count, decides whether and how far to split.
29 * 2. k-means over the sample -> k centroids, then drop those too small to
30 * be worth a list of their own, widening once or twice rather than
31 * declining if that would leave fewer than two.
32 * 3. Walk the chain again, appending each entry to the builder for the
33 * surviving centroid nearest it -- so dropping a centroid is what folds
34 * its entries away, and an entry lands in the list whose stored centroid
35 * is nearest, which is what a query reproduces at scan time. The builders
36 * write in the index's page format, so a split also upgrades a list that
37 * had drifted to AoS back to fastscan.
38 * 4. Flip the centroid tree to point the leaf at the k new heads. When the
39 * old leaf and the chain tail share one page and the k-1 extra leaves fit
40 * on it (the common flat single-page tree), the whole flip is one atomic
41 * page write, so a concurrent scan never sees old and new heads together.
42 * Otherwise (tail elsewhere, or the page is full) it falls back to
43 * appending the k-1 extra leaves first, then overwriting the old leaf
44 * last: the old list stays authoritative until that overwrite, so a scan
45 * never misses entries; it may briefly reach a new head and the old head
46 * both, and the duplicate vectors are dropped by the top-k's id dedup
47 * (the same path that dedups SOAR replicas), so results stay correct.
48 * 5. Retire the old chain for later reclaim; bump nlist by k-1.
49 *
50 * Crash-safety (PG): pages are committed in that order, so any crash leaks
51 * unreachable pages but never corrupts — before the flip the old list is
52 * authoritative; after it the old chain is unreachable garbage.
53 *
54 * Phase-1 limitations: flat tree (nlevels == 1) and RaBitQ centroid format
55 * only. FLOAT/HALF/FASTSCAN centroid formats and multi-level trees are
56 * handled in later phases.
57 */
58
59 #ifndef PRISM_POSTING_SPLIT_H
60 #define PRISM_POSTING_SPLIT_H
61
62 #include <stdbool.h>
63 #include <stdint.h>
64
65 #include "core/types.h"
66 #include "index/index_base.h"
67
68 #ifdef VS_STANDALONE
69 #include "standalone/pg_compat.h"
70 #else
71 #include <postgres.h>
72
73 #include <storage/itemptr.h>
74 #endif
75
76 /*
77 * Context-specific vector access. The split re-clusters on full-precision
78 * vectors, which live outside the index (heap in PG, in-RAM store
79 * standalone). Fill out[dim] for the given entry TID.
80 *
81 * Returns true on success. False means the entry has no vector any more and
82 * is dropped from the split, so an implementation may only return it once the
83 * entry is dead to every transaction -- not merely invisible to the one
84 * running the split. The split re-clusters; dropping an entry a live snapshot
85 * still has to find would lose the row for that snapshot, since the new lists
86 * are the only place it can look once the centroid leaf is flipped.
87 */
88 typedef struct PrismSplitEnv
89 {
90 bool (*fetch_vector)(
91 void *ctx, ItemPointerData tid, float *out, Dimension dim);
92 /*
93 * Retire the split's old chain (unreachable via the tree once the flip
94 * commits). NULL means the core tombstones it immediately — correct where
95 * no concurrent snapshot-holding scanner can still reach it (standalone).
96 * A backend with MVCC snapshots supplies this to defer reclaim behind an
97 * XID gate, keeping the chain readable for in-flight scanners meanwhile.
98 */
99 void (*retire_chain)(
100 void *ctx, VsStorage *posting_storage, BlockNumber head);
101 /*
102 * Persist the leaf count before the ids counted from it are used, if the
103 * backend keeps one durably. New cluster ids are counted from nlist and
104 * the new leaves are written before anything raises it, so a backend that
105 * only persists the count afterwards has a window where a crash leaves the
106 * leaves reachable and the count stale -- and the next split then hands
107 * the same ids out again. Called once per split, before the new lists are
108 * written. May be NULL where the count is not persisted separately.
109 */
110 void (*reserve_nlist)(void *ctx, uint32_t nlist);
111 /*
112 * Start the read for a tid the walk is about to reach, so the fetch that
113 * follows can find it resident. Both passes fetch every entry of the
114 * list, in a chain whose tids are already roughly ascending, so there is
115 * a next block worth starting early. Called at most once per distinct
116 * block, one tid ahead of the callback. May be NULL where fetching does
117 * no I/O (standalone holds its vectors in memory).
118 */
119 void (*prefetch_vector)(void *ctx, ItemPointerData tid);
120
121 void *ctx;
122 } PrismSplitEnv;
123
124 /* Upper bound on the number of partitions one split may produce. A very
125 * oversized list is split toward this many at once; anything beyond is left
126 * for a later split. Bounds the on-stack result arrays and the per-split work.
127 */
128 #define PRISM_SPLIT_MAX_PARTS 32
129
130 /*
131 * How far above the target size a list must grow before it is worth splitting.
132 * The target is the resting size a split aims each new list at; the trigger is
133 * that times this factor, so a list has room to absorb inserts (and deletes)
134 * without immediately splitting again, and a fresh part sits at the geometric
135 * centre of the operating band [target/factor, target*factor].
136 *
137 * Keep it an integer: split width is round(count / target), which at the
138 * trigger is the factor itself, so each new list lands on the target. A
139 * fractional factor would round the width up and land every new part below the
140 * target, and the target would stop being where lists rest. At 2 the
141 * steady-state split is a bisection, matching the SPFresh/LIRE protocol, and a
142 * wider split only happens when a batch pass meets a neglected list.
143 */
144 #define PRISM_SPLIT_TRIGGER_FACTOR 2
145
146 /*
147 * How many times a split may widen by one partition when dropping the
148 * undersized clusters cannot leave two standing. Small on purpose: one extra
149 * partition resolves the common case (a dense region plus a straggler), and
150 * data that resists more than that is better declined than re-clustered
151 * repeatedly.
152 */
153 #define PRISM_SPLIT_WIDEN_ATTEMPTS 2
154
155 /*
156 * The size a list must exceed before it is worth splitting. One definition,
157 * because the trigger is tested in three places -- the scan that picks
158 * candidates, the re-check under the head lock, and the authoritative re-check
159 * after collection -- and they have to agree. They drifted once already, when
160 * the two re-checks disagreed on `<` versus `<=`.
161 */
162 static inline uint64_t
163 272 prism_split_trigger(uint32_t target_entries)
164 {
165
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 103 times.
✓ Branch 2 taken 104 times.
272 return (uint64_t)target_entries * PRISM_SPLIT_TRIGGER_FACTOR;
166 }
167
168 /*
169 * Memory budget for a split, in bytes, when the caller does not state one.
170 * Deliberately modest -- a caller with a maintenance memory budget of its own
171 * should say so through PrismSplitConfig.sample_budget_bytes.
172 */
173 #define PRISM_SPLIT_SAMPLE_BUDGET_BYTES (32u * 1024u * 1024u)
174
175 /*
176 * Ceiling on the sample's own allocation, whatever budget the caller states.
177 * A single allocation has an upper limit in a PostgreSQL backend
178 * (MaxAllocSize, just under 1 GB) and asking for more is an error, not a
179 * smaller sample -- so a generous maintenance_work_mem must not turn into a
180 * failed split. Well inside that limit, and far more sample than clustering
181 * into at most PRISM_SPLIT_MAX_PARTS partitions can use.
182 */
183 #define PRISM_SPLIT_MAX_SAMPLE_BYTES (256u * 1024u * 1024u)
184
185 /*
186 * Sample points a partition needs before its share of the sample says anything
187 * about its real size. Below this the tally is noise, and a cluster that is
188 * really a fair size looks small enough to drop -- so a split asks for no more
189 * partitions than its sample can speak for, and leaves the rest to the pass
190 * after it. With the default budget this never binds; it protects a caller
191 * that sets a tight one.
192 */
193 #define PRISM_SPLIT_MIN_SAMPLE_PER_PART 32u
194
195 /* Seed for the reservoir draws when the caller states no k-means seed, so a
196 * split samples the same way on a re-run. */
197 #define PRISM_SPLIT_SAMPLE_SEED UINT64_C(0x5EED5A1717C0FFEE)
198
199 /*
200 * What clustering costs per sampled point, on top of the point itself: k-means
201 * keeps an assignment, an L2 norm and an initialisation distance per point,
202 * Elkan keeps an upper bound per point and a lower bound per point *per
203 * centroid*, and the result carries its own copy of the assignments. The
204 * per-centroid part is sized for the widest split, because the width is not
205 * known until the list has been counted.
206 *
207 * At a wide dimension this is a few percent of the point; at a narrow one it
208 * is several times the point, which is why the budget cannot simply be divided
209 * by the vector size.
210 */
211 #define PRISM_SPLIT_SAMPLE_POINT_OVERHEAD \
212 (5u * (uint32_t)sizeof(float) + \
213 (uint32_t)sizeof(float) * PRISM_SPLIT_MAX_PARTS)
214
215 /*
216 * What clustering costs regardless of how many points are sampled: several
217 * sets of centroids, and k-means' blocked distance and vector scratch. Sized
218 * for the widest split and the full block, so it over-reserves for a narrow
219 * one rather than under-reserving.
220 */
221 static inline uint64_t
222 217 prism_split_fixed_bytes(Dimension dim)
223 {
224 217 const uint64_t block = 4096; /* KMEANS_BLOCK_SIZE */
225 217 const uint64_t centroids = 5u * PRISM_SPLIT_MAX_PARTS;
226 217 uint64_t per_dim = (centroids + block) * (uint64_t)dim * sizeof(float);
227 217 uint64_t dist_block = block * PRISM_SPLIT_MAX_PARTS * sizeof(float);
228
229 /* Slack for the many small allocations neither term names. */
230 217 return per_dim + dist_block + 64u * 1024u;
231 }
232
233 /*
234 * Sampled points a budget can pay for, or 0 if it cannot pay for a split at
235 * all. A caller that gets 0 should say so rather than proceed: exceeding the
236 * budget it was given is not its decision to make.
237 */
238 static inline uint32_t
239 212 prism_split_sample_cap(uint64_t budget_bytes, Dimension dim)
240 {
241 212 uint64_t fixed = prism_split_fixed_bytes(dim);
242 212 uint64_t per_point = (uint64_t)dim * sizeof(float) +
243 PRISM_SPLIT_SAMPLE_POINT_OVERHEAD;
244 212 uint64_t vec_cap = PRISM_SPLIT_MAX_SAMPLE_BYTES /
245 212 ((uint64_t)dim * sizeof(float));
246
247
2/2
✓ Branch 0 taken 157 times.
✓ Branch 1 taken 55 times.
212 if (budget_bytes <= fixed)
248 2 return 0;
249
250 209 uint64_t n = (budget_bytes - fixed) / per_point;
251
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 54 times.
209 if (n > vec_cap)
252 ✗ n = vec_cap;
253 /* Too few points to say anything about even two partitions. */
254
2/2
✓ Branch 0 taken 155 times.
✓ Branch 1 taken 54 times.
209 if (n < 2u * PRISM_SPLIT_MIN_SAMPLE_PER_PART)
255 ✗ return 0;
256 209 return (uint32_t)n;
257 }
258
259 /* The smallest budget prism_split_sample_cap will accept, for a caller that
260 * wants to say by how much its own is short. */
261 static inline uint64_t
262 1 prism_split_min_budget_bytes(Dimension dim)
263 {
264 1 uint64_t per_point = (uint64_t)dim * sizeof(float) +
265 PRISM_SPLIT_SAMPLE_POINT_OVERHEAD;
266 1 return prism_split_fixed_bytes(dim) +
267 1 2u * PRISM_SPLIT_MIN_SAMPLE_PER_PART * per_point;
268 }
269
270 /* Split tuning. Zero-initialize for defaults. */
271 typedef struct PrismSplitConfig
272 {
273 uint32_t min_split_entries; /* refuse to split below this (0 -> 2) */
274 /*
275 * Resting size to aim each new list at. When set, the split declines
276 * unless the collected entries still exceed
277 * target_entries * PRISM_SPLIT_TRIGGER_FACTOR, and otherwise splits
278 * round(count / target_entries) ways -- rounded, not ceiled, so that at
279 * the trigger the width is exactly the factor and each new list lands on
280 * the target rather than below it.
281 *
282 * The check is deliberately against the *collected* count, not the head's
283 * live_count: collection drops entries whose vector cannot be fetched,
284 * and those are not reflected in live_count, so a list can look oversized
285 * and turn out not to be. Re-verifying after collection is also what the
286 * LIRE protocol does (SPFresh SS4.2.1: garbage-collect, re-check against
287 * the split limit, complete without splitting if it now fits).
288 *
289 * 0 disables both behaviours: the split is unconditional and nparts (or
290 * its default of 2) decides the width. That is the manual escape hatch.
291 */
292 uint32_t target_entries;
293 /* Number of partitions to split into, clamped to
294 * [2, PRISM_SPLIT_MAX_PARTS] and to the live entry count (0 -> 2). Ignored
295 * when target_entries is set, which derives the width instead. Lets a
296 * caller right-size a hugely oversized list in one pass instead of
297 * repeatedly bisecting. */
298 uint32_t nparts;
299 /*
300 * Memory a split may use, in bytes. It streams the list rather than
301 * holding it, and sizes its clustering sample so that the sample and the
302 * clustering working set together fit here -- see prism_split_sample_cap.
303 * 0 takes PRISM_SPLIT_SAMPLE_BUDGET_BYTES. A backend with a maintenance
304 * memory budget should pass it through.
305 */
306 uint64_t sample_budget_bytes;
307 uint32_t km_max_iter; /* k-means iterations (0 -> default) */
308 uint64_t km_seed; /* k-means seed (0 -> default) */
309 } PrismSplitConfig;
310
311 typedef struct PrismSplitResult
312 {
313 /*
314 * false when the split declined: too few entries, a list already inside
315 * its operating band, or no two partitions clearing the floor even after
316 * widening.
317 */
318 bool did_split;
319 uint32_t nparts; /* number of new lists produced (0 if declined) */
320 BlockNumber head[PRISM_SPLIT_MAX_PARTS]; /* new posting heads; head[0]
321 * reuses the former leaf slot */
322 uint32_t count[PRISM_SPLIT_MAX_PARTS]; /* live entries per new head */
323 uint32_t new_nlist; /* leaf count after the split */
324 /*
325 * Centroid pages this split appended because a level-0 page had no room.
326 * The caller persists the new total; the split cannot, the metapage
327 * being a PostgreSQL detail the shared layer does not reach.
328 */
329 uint32_t new_centroid_pages;
330 } PrismSplitResult;
331
332 /*
333 * Split the posting list whose head page is `head`. The caller must hold an
334 * exclusive lock on the cluster (no-op in standalone). cfg and out may be
335 * NULL. Returns 0 on success (out->did_split reports whether a split happened
336 * -- declining is not an error), or a negative value on error, which includes
337 * a memory budget too small to split at this dimension.
338 */
339 int prism_posting_split(
340 PrismIndexBase *base,
341 BlockNumber head,
342 const PrismSplitConfig *cfg,
343 const PrismSplitEnv *env,
344 PrismSplitResult *out);
345
346 /*
347 * Tombstone every page of a posting chain starting at `head`, so scans skip it
348 * and a later recycle pass can reclaim the space. Retires a split's old chain
349 * once no scanner can still reach it: the immediate standalone path, and the
350 * PG XID-gated reclaim once the deletion horizon has passed.
351 */
352 void prism_posting_chain_tombstone(VsStorage *storage, BlockNumber head);
353
354 #endif /* PRISM_POSTING_SPLIT_H */
355