| 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 if the vector is unavailable (e.g. a dead | ||
| 82 | * heap tuple), in which case the entry is dropped from the split and left for | ||
| 83 | * VACUUM to reclaim. | ||
| 84 | */ | ||
| 85 | typedef struct PrismSplitEnv | ||
| 86 | { | ||
| 87 | bool (*fetch_vector)( | ||
| 88 | void *ctx, ItemPointerData tid, float *out, Dimension dim); | ||
| 89 | /* | ||
| 90 | * Retire the split's old chain (unreachable via the tree once the flip | ||
| 91 | * commits). NULL means the core tombstones it immediately — correct where | ||
| 92 | * no concurrent snapshot-holding scanner can still reach it (standalone). | ||
| 93 | * A backend with MVCC snapshots supplies this to defer reclaim behind an | ||
| 94 | * XID gate, keeping the chain readable for in-flight scanners meanwhile. | ||
| 95 | */ | ||
| 96 | void (*retire_chain)( | ||
| 97 | void *ctx, VsStorage *posting_storage, BlockNumber head); | ||
| 98 | /* | ||
| 99 | * Persist the leaf count before the ids counted from it are used, if the | ||
| 100 | * backend keeps one durably. New cluster ids are counted from nlist and | ||
| 101 | * the new leaves are written before anything raises it, so a backend that | ||
| 102 | * only persists the count afterwards has a window where a crash leaves the | ||
| 103 | * leaves reachable and the count stale -- and the next split then hands | ||
| 104 | * the same ids out again. Called once per split, before the new lists are | ||
| 105 | * written. May be NULL where the count is not persisted separately. | ||
| 106 | */ | ||
| 107 | void (*reserve_nlist)(void *ctx, uint32_t nlist); | ||
| 108 | /* | ||
| 109 | * Start the read for a tid the walk is about to reach, so the fetch that | ||
| 110 | * follows can find it resident. Both passes fetch every entry of the | ||
| 111 | * list, in a chain whose tids are already roughly ascending, so there is | ||
| 112 | * a next block worth starting early. Called at most once per distinct | ||
| 113 | * block, one tid ahead of the callback. May be NULL where fetching does | ||
| 114 | * no I/O (standalone holds its vectors in memory). | ||
| 115 | */ | ||
| 116 | void (*prefetch_vector)(void *ctx, ItemPointerData tid); | ||
| 117 | |||
| 118 | void *ctx; | ||
| 119 | } PrismSplitEnv; | ||
| 120 | |||
| 121 | /* Upper bound on the number of partitions one split may produce. A very | ||
| 122 | * oversized list is split toward this many at once; anything beyond is left | ||
| 123 | * for a later split. Bounds the on-stack result arrays and the per-split work. | ||
| 124 | */ | ||
| 125 | #define PRISM_SPLIT_MAX_PARTS 32 | ||
| 126 | |||
| 127 | /* | ||
| 128 | * How far above the target size a list must grow before it is worth splitting. | ||
| 129 | * The target is the resting size a split aims each new list at; the trigger is | ||
| 130 | * that times this factor, so a list has room to absorb inserts (and deletes) | ||
| 131 | * without immediately splitting again, and a fresh part sits at the geometric | ||
| 132 | * centre of the operating band [target/factor, target*factor]. | ||
| 133 | * | ||
| 134 | * Keep it an integer: split width is round(count / target), which at the | ||
| 135 | * trigger is the factor itself, so each new list lands on the target. A | ||
| 136 | * fractional factor would round the width up and land every new part below the | ||
| 137 | * target, and the target would stop being where lists rest. At 2 the | ||
| 138 | * steady-state split is a bisection, matching the SPFresh/LIRE protocol, and a | ||
| 139 | * wider split only happens when a batch pass meets a neglected list. | ||
| 140 | */ | ||
| 141 | #define PRISM_SPLIT_TRIGGER_FACTOR 2 | ||
| 142 | |||
| 143 | /* | ||
| 144 | * How many times a split may widen by one partition when dropping the | ||
| 145 | * undersized clusters cannot leave two standing. Small on purpose: one extra | ||
| 146 | * partition resolves the common case (a dense region plus a straggler), and | ||
| 147 | * data that resists more than that is better declined than re-clustered | ||
| 148 | * repeatedly. | ||
| 149 | */ | ||
| 150 | #define PRISM_SPLIT_WIDEN_ATTEMPTS 2 | ||
| 151 | |||
| 152 | /* | ||
| 153 | * The size a list must exceed before it is worth splitting. One definition, | ||
| 154 | * because the trigger is tested in three places -- the scan that picks | ||
| 155 | * candidates, the re-check under the head lock, and the authoritative re-check | ||
| 156 | * after collection -- and they have to agree. They drifted once already, when | ||
| 157 | * the two re-checks disagreed on `<` versus `<=`. | ||
| 158 | */ | ||
| 159 | static inline uint64_t | ||
| 160 | 246 | prism_split_trigger(uint32_t target_entries) | |
| 161 | { | ||
| 162 |
2/3✗ Branch 0 not taken.
✓ Branch 1 taken 95 times.
✓ Branch 2 taken 95 times.
|
246 | return (uint64_t)target_entries * PRISM_SPLIT_TRIGGER_FACTOR; |
| 163 | } | ||
| 164 | |||
| 165 | /* | ||
| 166 | * Memory budget for a split, in bytes, when the caller does not state one. | ||
| 167 | * Deliberately modest -- a caller with a maintenance memory budget of its own | ||
| 168 | * should say so through PrismSplitConfig.sample_budget_bytes. | ||
| 169 | */ | ||
| 170 | #define PRISM_SPLIT_SAMPLE_BUDGET_BYTES (32u * 1024u * 1024u) | ||
| 171 | |||
| 172 | /* | ||
| 173 | * Ceiling on the sample's own allocation, whatever budget the caller states. | ||
| 174 | * A single allocation has an upper limit in a PostgreSQL backend | ||
| 175 | * (MaxAllocSize, just under 1 GB) and asking for more is an error, not a | ||
| 176 | * smaller sample -- so a generous maintenance_work_mem must not turn into a | ||
| 177 | * failed split. Well inside that limit, and far more sample than clustering | ||
| 178 | * into at most PRISM_SPLIT_MAX_PARTS partitions can use. | ||
| 179 | */ | ||
| 180 | #define PRISM_SPLIT_MAX_SAMPLE_BYTES (256u * 1024u * 1024u) | ||
| 181 | |||
| 182 | /* | ||
| 183 | * Sample points a partition needs before its share of the sample says anything | ||
| 184 | * about its real size. Below this the tally is noise, and a cluster that is | ||
| 185 | * really a fair size looks small enough to drop -- so a split asks for no more | ||
| 186 | * partitions than its sample can speak for, and leaves the rest to the pass | ||
| 187 | * after it. With the default budget this never binds; it protects a caller | ||
| 188 | * that sets a tight one. | ||
| 189 | */ | ||
| 190 | #define PRISM_SPLIT_MIN_SAMPLE_PER_PART 32u | ||
| 191 | |||
| 192 | /* Seed for the reservoir draws when the caller states no k-means seed, so a | ||
| 193 | * split samples the same way on a re-run. */ | ||
| 194 | #define PRISM_SPLIT_SAMPLE_SEED UINT64_C(0x5EED5A1717C0FFEE) | ||
| 195 | |||
| 196 | /* | ||
| 197 | * What clustering costs per sampled point, on top of the point itself: k-means | ||
| 198 | * keeps an assignment, an L2 norm and an initialisation distance per point, | ||
| 199 | * Elkan keeps an upper bound per point and a lower bound per point *per | ||
| 200 | * centroid*, and the result carries its own copy of the assignments. The | ||
| 201 | * per-centroid part is sized for the widest split, because the width is not | ||
| 202 | * known until the list has been counted. | ||
| 203 | * | ||
| 204 | * At a wide dimension this is a few percent of the point; at a narrow one it | ||
| 205 | * is several times the point, which is why the budget cannot simply be divided | ||
| 206 | * by the vector size. | ||
| 207 | */ | ||
| 208 | #define PRISM_SPLIT_SAMPLE_POINT_OVERHEAD \ | ||
| 209 | (5u * (uint32_t)sizeof(float) + \ | ||
| 210 | (uint32_t)sizeof(float) * PRISM_SPLIT_MAX_PARTS) | ||
| 211 | |||
| 212 | /* | ||
| 213 | * What clustering costs regardless of how many points are sampled: several | ||
| 214 | * sets of centroids, and k-means' blocked distance and vector scratch. Sized | ||
| 215 | * for the widest split and the full block, so it over-reserves for a narrow | ||
| 216 | * one rather than under-reserving. | ||
| 217 | */ | ||
| 218 | static inline uint64_t | ||
| 219 | 193 | prism_split_fixed_bytes(Dimension dim) | |
| 220 | { | ||
| 221 | 193 | const uint64_t block = 4096; /* KMEANS_BLOCK_SIZE */ | |
| 222 | 193 | const uint64_t centroids = 5u * PRISM_SPLIT_MAX_PARTS; | |
| 223 | 193 | uint64_t per_dim = (centroids + block) * (uint64_t)dim * sizeof(float); | |
| 224 | 193 | uint64_t dist_block = block * PRISM_SPLIT_MAX_PARTS * sizeof(float); | |
| 225 | |||
| 226 | /* Slack for the many small allocations neither term names. */ | ||
| 227 | 193 | return per_dim + dist_block + 64u * 1024u; | |
| 228 | } | ||
| 229 | |||
| 230 | /* | ||
| 231 | * Sampled points a budget can pay for, or 0 if it cannot pay for a split at | ||
| 232 | * all. A caller that gets 0 should say so rather than proceed: exceeding the | ||
| 233 | * budget it was given is not its decision to make. | ||
| 234 | */ | ||
| 235 | static inline uint32_t | ||
| 236 | 188 | prism_split_sample_cap(uint64_t budget_bytes, Dimension dim) | |
| 237 | { | ||
| 238 | 188 | uint64_t fixed = prism_split_fixed_bytes(dim); | |
| 239 | 188 | uint64_t per_point = (uint64_t)dim * sizeof(float) + | |
| 240 | PRISM_SPLIT_SAMPLE_POINT_OVERHEAD; | ||
| 241 | 188 | uint64_t vec_cap = PRISM_SPLIT_MAX_SAMPLE_BYTES / | |
| 242 | 188 | ((uint64_t)dim * sizeof(float)); | |
| 243 | |||
| 244 |
2/2✓ Branch 0 taken 137 times.
✓ Branch 1 taken 51 times.
|
188 | if (budget_bytes <= fixed) |
| 245 | ✗ | return 0; | |
| 246 | |||
| 247 | 187 | uint64_t n = (budget_bytes - fixed) / per_point; | |
| 248 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 50 times.
|
187 | if (n > vec_cap) |
| 249 | ✗ | n = vec_cap; | |
| 250 | /* Too few points to say anything about even two partitions. */ | ||
| 251 |
2/2✓ Branch 0 taken 137 times.
✓ Branch 1 taken 50 times.
|
187 | if (n < 2u * PRISM_SPLIT_MIN_SAMPLE_PER_PART) |
| 252 | ✗ | return 0; | |
| 253 | 187 | return (uint32_t)n; | |
| 254 | } | ||
| 255 | |||
| 256 | /* The smallest budget prism_split_sample_cap will accept, for a caller that | ||
| 257 | * wants to say by how much its own is short. */ | ||
| 258 | static inline uint64_t | ||
| 259 | 1 | prism_split_min_budget_bytes(Dimension dim) | |
| 260 | { | ||
| 261 | 1 | uint64_t per_point = (uint64_t)dim * sizeof(float) + | |
| 262 | PRISM_SPLIT_SAMPLE_POINT_OVERHEAD; | ||
| 263 | 1 | return prism_split_fixed_bytes(dim) + | |
| 264 | 1 | 2u * PRISM_SPLIT_MIN_SAMPLE_PER_PART * per_point; | |
| 265 | } | ||
| 266 | |||
| 267 | /* Split tuning. Zero-initialize for defaults. */ | ||
| 268 | typedef struct PrismSplitConfig | ||
| 269 | { | ||
| 270 | uint32_t min_split_entries; /* refuse to split below this (0 -> 2) */ | ||
| 271 | /* | ||
| 272 | * Resting size to aim each new list at. When set, the split declines | ||
| 273 | * unless the collected entries still exceed | ||
| 274 | * target_entries * PRISM_SPLIT_TRIGGER_FACTOR, and otherwise splits | ||
| 275 | * round(count / target_entries) ways -- rounded, not ceiled, so that at | ||
| 276 | * the trigger the width is exactly the factor and each new list lands on | ||
| 277 | * the target rather than below it. | ||
| 278 | * | ||
| 279 | * The check is deliberately against the *collected* count, not the head's | ||
| 280 | * live_count: collection drops entries whose vector cannot be fetched, | ||
| 281 | * and those are not reflected in live_count, so a list can look oversized | ||
| 282 | * and turn out not to be. Re-verifying after collection is also what the | ||
| 283 | * LIRE protocol does (SPFresh SS4.2.1: garbage-collect, re-check against | ||
| 284 | * the split limit, complete without splitting if it now fits). | ||
| 285 | * | ||
| 286 | * 0 disables both behaviours: the split is unconditional and nparts (or | ||
| 287 | * its default of 2) decides the width. That is the manual escape hatch. | ||
| 288 | */ | ||
| 289 | uint32_t target_entries; | ||
| 290 | /* Number of partitions to split into, clamped to | ||
| 291 | * [2, PRISM_SPLIT_MAX_PARTS] and to the live entry count (0 -> 2). Ignored | ||
| 292 | * when target_entries is set, which derives the width instead. Lets a | ||
| 293 | * caller right-size a hugely oversized list in one pass instead of | ||
| 294 | * repeatedly bisecting. */ | ||
| 295 | uint32_t nparts; | ||
| 296 | /* | ||
| 297 | * Memory a split may use, in bytes. It streams the list rather than | ||
| 298 | * holding it, and sizes its clustering sample so that the sample and the | ||
| 299 | * clustering working set together fit here -- see prism_split_sample_cap. | ||
| 300 | * 0 takes PRISM_SPLIT_SAMPLE_BUDGET_BYTES. A backend with a maintenance | ||
| 301 | * memory budget should pass it through. | ||
| 302 | */ | ||
| 303 | uint64_t sample_budget_bytes; | ||
| 304 | uint32_t km_max_iter; /* k-means iterations (0 -> default) */ | ||
| 305 | uint64_t km_seed; /* k-means seed (0 -> default) */ | ||
| 306 | } PrismSplitConfig; | ||
| 307 | |||
| 308 | typedef struct PrismSplitResult | ||
| 309 | { | ||
| 310 | /* | ||
| 311 | * false when the split declined: too few entries, a list already inside | ||
| 312 | * its operating band, or no two partitions clearing the floor even after | ||
| 313 | * widening. | ||
| 314 | */ | ||
| 315 | bool did_split; | ||
| 316 | uint32_t nparts; /* number of new lists produced (0 if declined) */ | ||
| 317 | BlockNumber head[PRISM_SPLIT_MAX_PARTS]; /* new posting heads; head[0] | ||
| 318 | * reuses the former leaf slot */ | ||
| 319 | uint32_t count[PRISM_SPLIT_MAX_PARTS]; /* live entries per new head */ | ||
| 320 | uint32_t new_nlist; /* leaf count after the split */ | ||
| 321 | /* | ||
| 322 | * Centroid pages this split appended because a level-0 page had no room. | ||
| 323 | * The caller persists the new total; the split cannot, the metapage | ||
| 324 | * being a PostgreSQL detail the shared layer does not reach. | ||
| 325 | */ | ||
| 326 | uint32_t new_centroid_pages; | ||
| 327 | } PrismSplitResult; | ||
| 328 | |||
| 329 | /* | ||
| 330 | * Split the posting list whose head page is `head`. The caller must hold an | ||
| 331 | * exclusive lock on the cluster (no-op in standalone). cfg and out may be | ||
| 332 | * NULL. Returns 0 on success (out->did_split reports whether a split happened | ||
| 333 | * -- declining is not an error), or a negative value on error, which includes | ||
| 334 | * a memory budget too small to split at this dimension. | ||
| 335 | */ | ||
| 336 | int prism_posting_split( | ||
| 337 | PrismIndexBase *base, | ||
| 338 | BlockNumber head, | ||
| 339 | const PrismSplitConfig *cfg, | ||
| 340 | const PrismSplitEnv *env, | ||
| 341 | PrismSplitResult *out); | ||
| 342 | |||
| 343 | /* | ||
| 344 | * Tombstone every page of a posting chain starting at `head`, so scans skip it | ||
| 345 | * and a later recycle pass can reclaim the space. Retires a split's old chain | ||
| 346 | * once no scanner can still reach it: the immediate standalone path, and the | ||
| 347 | * PG XID-gated reclaim once the deletion horizon has passed. | ||
| 348 | */ | ||
| 349 | void prism_posting_chain_tombstone(VsStorage *storage, BlockNumber head); | ||
| 350 | |||
| 351 | #endif /* PRISM_POSTING_SPLIT_H */ | ||
| 352 |