| 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_page.h - Posting list page format | ||
| 6 | * | ||
| 7 | * Stores per-cluster posting data using an AoS layout: each entry | ||
| 8 | * is a fixed-size block packing meta + factors + bits together. | ||
| 9 | * | ||
| 10 | * Paged mode (BLCKSZ pages): | ||
| 11 | * PageHeader (PG-compatible, 24B) | ||
| 12 | * (pt_centroid — on first page only) | ||
| 13 | * entry[0], entry[1], ... | ||
| 14 | * PrismPostingPageOpaque (16B at page end) | ||
| 15 | * | ||
| 16 | * Flat mode (one buffer per cluster): | ||
| 17 | * PrismFlatPostingHeader (16B) | ||
| 18 | * entry[0], entry[1], ... | ||
| 19 | * | ||
| 20 | * Per-entry block (size = PRISM_POSTING_ENTRY_SIZE(dim) bytes): | ||
| 21 | * PrismPostingEntryHeader 20B (tid + flags + f_add/rescale/error) | ||
| 22 | * uint8_t bits[packed_bytes] (dim-dependent, 96B at dim=768) | ||
| 23 | * | ||
| 24 | * Why AoS: when the SIMD kernel strides through entries at | ||
| 25 | * stride=PRISM_POSTING_ENTRY_SIZE(dim), consecutive pages' bit | ||
| 26 | * regions are separated by only ~72 bytes of page-boundary overhead | ||
| 27 | * (opaque + next PageHeader) instead of the ~1472 bytes that an | ||
| 28 | * SoA layout interleaves (metas + f_add + f_rescale + f_error of | ||
| 29 | * the next page before its bits). A small per-page perturbation is | ||
| 30 | * much easier for the HW prefetcher to absorb than a multi-KB | ||
| 31 | * discontinuity — see the BLCKSZ experiment that confirmed the gap | ||
| 32 | * lives at those region transitions. | ||
| 33 | * | ||
| 34 | * Side benefit: reading bits at stride=entry_size also pulls each | ||
| 35 | * entry's f_add/f_rescale/f_error/meta into L1 for free, so phase 3 | ||
| 36 | * (distance conversion + prune) finds them hot. | ||
| 37 | */ | ||
| 38 | |||
| 39 | #ifndef PRISM_POSTING_PAGE_H | ||
| 40 | #define PRISM_POSTING_PAGE_H | ||
| 41 | |||
| 42 | #include <assert.h> /* static_assert pre-C23 (e.g. gcc 11's -std=c2x) */ | ||
| 43 | #include <stdbool.h> | ||
| 44 | #include <stdint.h> | ||
| 45 | #include <string.h> | ||
| 46 | |||
| 47 | #include "core/types.h" | ||
| 48 | #include "index/storage.h" | ||
| 49 | #include "quant/rabitq.h" | ||
| 50 | |||
| 51 | /* ---------------------------------------------------------------- | ||
| 52 | * Constants | ||
| 53 | * ---------------------------------------------------------------- */ | ||
| 54 | |||
| 55 | #define PRISM_POSTING_PAGE_ID 0x4D50 /* "MP" */ | ||
| 56 | |||
| 57 | /* Entry flags */ | ||
| 58 | #define PRISM_POSTING_FLAG_DELETED 0x01 | ||
| 59 | #define PRISM_POSTING_FLAG_BOUNDARY 0x02 | ||
| 60 | |||
| 61 | /* Page flags */ | ||
| 62 | #define PRISM_POSTING_PAGE_FIRST 0x0001 | ||
| 63 | #define PRISM_POSTING_PAGE_OVERFLOW 0x0002 | ||
| 64 | #define PRISM_POSTING_PAGE_FASTSCAN 0x0004 /* reserved for phase 2 */ | ||
| 65 | /* | ||
| 66 | * Every entry on the page is dead. Set by the VACUUM tombstone pass when a | ||
| 67 | * page's whole contents are deleted (AoS: all entries flagged; FASTSCAN: all | ||
| 68 | * group TIDs dead — the only way a packed page's deletes are recorded, since | ||
| 69 | * its entries can't be flagged individually). The scan skips the page's | ||
| 70 | * scoring kernel entirely; the page stays linked so compaction can later | ||
| 71 | * reclaim it. Cleared if the page is ever reused for new entries. | ||
| 72 | */ | ||
| 73 | #define PRISM_POSTING_PAGE_TOMBSTONED 0x0008 | ||
| 74 | /* | ||
| 75 | * The page belongs to a chain that has been logically retired — no longer | ||
| 76 | * reachable through the centroid tree — and is awaiting physical reclaim. A | ||
| 77 | * posting-list split sets this on every page of the old chain (head included) | ||
| 78 | * once it has repointed the leaf at the new heads. | ||
| 79 | * | ||
| 80 | * Distinct from TOMBSTONED: a tombstoned page is all-dead but still a live | ||
| 81 | * part of its cluster, so scans skip it and follow the chain past it. A | ||
| 82 | * DELETED chain is off the tree but stays physically LINKED and readable until | ||
| 83 | * reclaim, so an in-flight scanner that already followed a stale leaf pointer | ||
| 84 | * into it still sees a consistent list rather than a gap. | ||
| 85 | * | ||
| 86 | * When this flag is set on a head, the head-metadata overlay in the opaque | ||
| 87 | * (see the union below) holds the deletion XID instead of | ||
| 88 | * live_count/tail_blkno. The reclaim gate compares that XID against the global | ||
| 89 | * visibility horizon before physically reclaiming the chain, so a scanner that | ||
| 90 | * still holds a stale pointer can never have it repurposed underneath it. | ||
| 91 | * Unlike TOMBSTONED, this flag therefore does apply to chain heads: a split | ||
| 92 | * retires the whole old chain, head and all. | ||
| 93 | */ | ||
| 94 | #define PRISM_POSTING_PAGE_DELETED 0x0010 | ||
| 95 | |||
| 96 | /* ---------------------------------------------------------------- | ||
| 97 | * Structs | ||
| 98 | * ---------------------------------------------------------------- */ | ||
| 99 | |||
| 100 | /* | ||
| 101 | * Per-entry metadata. | ||
| 102 | * | ||
| 103 | * In PG: tid is a heap TID for reranking via buffer cache. | ||
| 104 | * In standalone: vector_id packed into tid via ItemPointerSet. | ||
| 105 | */ | ||
| 106 | typedef struct PrismPostingEntryMeta | ||
| 107 | { | ||
| 108 | ItemPointerData tid; /* 6B */ | ||
| 109 | uint8_t flags; | ||
| 110 | uint8_t reserved; | ||
| 111 | } PrismPostingEntryMeta; /* 8B */ | ||
| 112 | |||
| 113 | /* | ||
| 114 | * Per-entry header in the AoS layout: meta + the three RaBitQ | ||
| 115 | * scalar factors, followed by a flexible array of quantized bits | ||
| 116 | * (VS_RABITQ_BYTES(dim) bytes at runtime). | ||
| 117 | * | ||
| 118 | * sizeof(PrismPostingEntryHeader) is 20B — the FAM doesn't contribute | ||
| 119 | * to the struct's static size, so PRISM_POSTING_ENTRY_HEADER_SIZE | ||
| 120 | * stays a clean compile-time constant. The bits array extends past | ||
| 121 | * the struct in memory; callers compute per-entry offsets via | ||
| 122 | * PRISM_POSTING_ENTRY_SIZE(dim) and access bits as `hdr->bits`. | ||
| 123 | */ | ||
| 124 | typedef struct PrismPostingEntryHeader | ||
| 125 | { | ||
| 126 | PrismPostingEntryMeta meta; /* 8B */ | ||
| 127 | float f_add; /* 4B */ | ||
| 128 | float f_rescale; /* 4B */ | ||
| 129 | float f_error; /* 4B */ | ||
| 130 | uint8_t bits[FLEXIBLE_ARRAY_MEMBER]; | ||
| 131 | } PrismPostingEntryHeader; /* 20B + dim-dependent bits */ | ||
| 132 | |||
| 133 | /* | ||
| 134 | * Paged-mode opaque (at end of every BLCKSZ posting page). | ||
| 135 | */ | ||
| 136 | typedef struct PrismPostingPageOpaque | ||
| 137 | { | ||
| 138 | BlockNumber next_blkno; /* next page in chain */ | ||
| 139 | uint32_t cluster_id; | ||
| 140 | uint16_t entry_count; /* entries on this page */ | ||
| 141 | uint16_t flags; /* FIRST | OVERFLOW | FASTSCAN | TOMBSTONED | | ||
| 142 | * DELETED */ | ||
| 143 | uint16_t page_id; /* PRISM_POSTING_PAGE_ID */ | ||
| 144 | uint16_t max_entries; /* capacity of this page */ | ||
| 145 | |||
| 146 | /* | ||
| 147 | * Overlay (8 bytes). On a live page these are the per-cluster head | ||
| 148 | * metadata; on a page flagged PRISM_POSTING_PAGE_DELETED they instead | ||
| 149 | * carry the deletion XID for the reclaim gate. The DELETED flag is the | ||
| 150 | * sole discriminator — always read live_count/tail_blkno only when it is | ||
| 151 | * clear and delete_xid only when it is set. A posting-list split retires | ||
| 152 | * the whole old chain, its FIRST head included, so a DELETED head does | ||
| 153 | * carry delete_xid here rather than head metadata; readers of head | ||
| 154 | * metadata (insert, split) first check the flag and treat a retired head | ||
| 155 | * as gone, so the two uses never collide. The anonymous struct/union keeps | ||
| 156 | * op->live_count, op->tail_blkno, and op->delete_xid all directly | ||
| 157 | * accessible. Storing the XID as a backend-neutral uint64_t (not PG's | ||
| 158 | * FullTransactionId) keeps this header usable by the standalone engine; | ||
| 159 | * the PG side converts via U64FromFullTransactionId / the inverse. | ||
| 160 | */ | ||
| 161 | union | ||
| 162 | { | ||
| 163 | struct | ||
| 164 | { | ||
| 165 | /* | ||
| 166 | * Lets the runtime insert path find the chain tail in O(1) and | ||
| 167 | * track per-cluster live size (for LIRE split/merge in a later | ||
| 168 | * phase). tail_blkno == InvalidBlockNumber means "not yet | ||
| 169 | * computed": the first insert walks the chain to fill both fields, | ||
| 170 | * then maintains them incrementally. Left zero / Invalid on | ||
| 171 | * overflow (non-first) pages. | ||
| 172 | */ | ||
| 173 | uint32_t live_count; | ||
| 174 | BlockNumber tail_blkno; | ||
| 175 | }; | ||
| 176 | |||
| 177 | /* Valid only when PRISM_POSTING_PAGE_DELETED is set (see flag | ||
| 178 | * comment). | ||
| 179 | */ | ||
| 180 | uint64_t delete_xid; | ||
| 181 | }; | ||
| 182 | } PrismPostingPageOpaque; /* 24B */ | ||
| 183 | |||
| 184 | /* | ||
| 185 | * True when this page's entries are gone for good, as opposed to moved. | ||
| 186 | * | ||
| 187 | * TOMBSTONED means "nothing here worth scoring" and the scan skips the page. | ||
| 188 | * The reclaim pass sets the same bit on a retired chain, whose entries are not | ||
| 189 | * dead at all -- they were rewritten into the chain's replacements -- so | ||
| 190 | * skipping there drops results that a stale-pointer scan is entitled to see. | ||
| 191 | * DELETED separates the two: it is set only by the retire pass, so a page | ||
| 192 | * carrying both moved rather than died, and its contents are still intact and | ||
| 193 | * linked until #224 makes the pages reusable. | ||
| 194 | */ | ||
| 195 | static inline bool | ||
| 196 | 38835 | prism_posting_page_all_dead(const PrismPostingPageOpaque *op) | |
| 197 | { | ||
| 198 |
4/4✓ Branch 0 taken 8 times.
✓ Branch 1 taken 37161 times.
✓ Branch 2 taken 1658 times.
✓ Branch 3 taken 8 times.
|
38843 | return (op->flags & PRISM_POSTING_PAGE_TOMBSTONED) != 0 && |
| 199 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
|
8 | (op->flags & PRISM_POSTING_PAGE_DELETED) == 0; |
| 200 | } | ||
| 201 | |||
| 202 | /* | ||
| 203 | * Flat-mode header (at start of flat page buffer). | ||
| 204 | * No PG PageHeaderData — avoids the uint16_t page size limit. | ||
| 205 | */ | ||
| 206 | typedef struct PrismFlatPostingHeader | ||
| 207 | { | ||
| 208 | uint32_t max_entries; /* == capacity (sized for count) */ | ||
| 209 | uint32_t entry_count; | ||
| 210 | uint32_t cluster_id; | ||
| 211 | uint32_t _pad; | ||
| 212 | } PrismFlatPostingHeader; /* 16B */ | ||
| 213 | |||
| 214 | /* ---------------------------------------------------------------- | ||
| 215 | * Size calculations | ||
| 216 | * ---------------------------------------------------------------- */ | ||
| 217 | |||
| 218 | /* Bytes in the per-entry header (meta + 3 floats) */ | ||
| 219 | #define PRISM_POSTING_ENTRY_HEADER_SIZE \ | ||
| 220 | sizeof(PrismPostingEntryHeader) /* 20B */ | ||
| 221 | |||
| 222 | /* Byte offset of bits[] within one entry. Equal to the header size | ||
| 223 | * because bits[] is the FAM right after the header. */ | ||
| 224 | #define PRISM_POSTING_ENTRY_BITS_OFFSET offsetof(PrismPostingEntryHeader, bits) | ||
| 225 | |||
| 226 | /* Bytes per entry in bits region */ | ||
| 227 | #define PRISM_POSTING_BITS_PER_ENTRY(dim) VS_RABITQ_BYTES(dim) | ||
| 228 | |||
| 229 | /* Entry stride must be a multiple of PrismPostingEntryHeader's alignment | ||
| 230 | * (4 bytes — the float fields) so entry i's float members land on | ||
| 231 | * properly aligned addresses regardless of `i`. For dim values where | ||
| 232 | * VS_RABITQ_BYTES(dim) isn't already a multiple of 4 (i.e., dim not | ||
| 233 | * a multiple of 32, such as dim=16 or dim=100), we pad up. */ | ||
| 234 | #define PRISM_POSTING_ENTRY_ALIGN 4u | ||
| 235 | |||
| 236 | /* Total bytes per entry: header + bits, padded up to entry alignment | ||
| 237 | * (= 116 at dim=768; 24 at dim=16). */ | ||
| 238 | #define PRISM_POSTING_ENTRY_SIZE(dim) \ | ||
| 239 | (((PRISM_POSTING_ENTRY_HEADER_SIZE + PRISM_POSTING_BITS_PER_ENTRY(dim)) + \ | ||
| 240 | PRISM_POSTING_ENTRY_ALIGN - 1u) & \ | ||
| 241 | ~(PRISM_POSTING_ENTRY_ALIGN - 1u)) | ||
| 242 | |||
| 243 | /* | ||
| 244 | * Hard dimension ceiling for the index layout. A posting list's first page | ||
| 245 | * carries the list's float encode reference (MAXALIGN(dim * sizeof(float)) | ||
| 246 | * bytes) and must still hold at least one posting entry; that binds before | ||
| 247 | * the float-format centroid page (one dim * sizeof(float) entry, ~2036) and | ||
| 248 | * the metadata page's inline mean. Past the ceiling the first-page capacity | ||
| 249 | * arithmetic underflows, so index creation must reject the dimension up | ||
| 250 | * front. | ||
| 251 | * | ||
| 252 | * The number is derived at 8-byte alignment, the largest MAXALIGN | ||
| 253 | * PostgreSQL uses, so it is one constant on every platform. Where MAXALIGN | ||
| 254 | * is smaller (32-bit x86) the first page has a few bytes of slack and the | ||
| 255 | * ceiling is merely conservative. The static asserts keep the number honest | ||
| 256 | * against layout changes, at that same fixed alignment. | ||
| 257 | */ | ||
| 258 | #define PRISM_INDEX_MAX_DIM 1968 | ||
| 259 | |||
| 260 | #define PRISM_CEILING_ALIGN(len) (((size_t)(len) + 7) & ~(size_t)7) | ||
| 261 | |||
| 262 | static_assert( | ||
| 263 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 264 | sizeof(PrismPostingPageOpaque) - | ||
| 265 | PRISM_CEILING_ALIGN( | ||
| 266 | PRISM_INDEX_MAX_DIM * sizeof(float)) >= | ||
| 267 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_MAX_DIM), | ||
| 268 | "posting first page must fit the encode reference plus one entry"); | ||
| 269 | static_assert( | ||
| 270 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 271 | sizeof(PrismPostingPageOpaque) - | ||
| 272 | PRISM_CEILING_ALIGN( | ||
| 273 | (PRISM_INDEX_MAX_DIM + 1) * sizeof(float)) < | ||
| 274 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_MAX_DIM + 1), | ||
| 275 | "the ceiling is tight: one dimension more must not fit"); | ||
| 276 | |||
| 277 | /* Usable space on a BLCKSZ page (between content start and opaque) */ | ||
| 278 | static inline uint32_t | ||
| 279 | 9112 | prism_posting_page_usable(void) | |
| 280 | { | ||
| 281 | 9112 | return BLCKSZ - (uint32_t)MAXALIGN(SizeOfPageHeaderData) - | |
| 282 | sizeof(PrismPostingPageOpaque); | ||
| 283 | } | ||
| 284 | |||
| 285 | /* Space occupied by P^T * centroid on first pages (MAXALIGN'd) */ | ||
| 286 | static inline uint32_t | ||
| 287 | 276275 | prism_posting_pt_centroid_size(Dimension dim) | |
| 288 | { | ||
| 289 | 276275 | return (uint32_t)MAXALIGN(dim * sizeof(float)); | |
| 290 | } | ||
| 291 | |||
| 292 | /* Max entries on an overflow page (no pt_centroid) */ | ||
| 293 | static inline uint32_t | ||
| 294 | 40428 | prism_posting_max_entries(Dimension dim) | |
| 295 | { | ||
| 296 | 40177 | return prism_posting_page_usable() / PRISM_POSTING_ENTRY_SIZE(dim); | |
| 297 | } | ||
| 298 | |||
| 299 | /* Max entries on a first page (with pt_centroid) */ | ||
| 300 | static inline uint32_t | ||
| 301 | 14440 | prism_posting_max_entries_first(Dimension dim) | |
| 302 | { | ||
| 303 | 14440 | uint32_t usable = prism_posting_page_usable(); | |
| 304 | 14440 | uint32_t pt = prism_posting_pt_centroid_size(dim); | |
| 305 | |||
| 306 | /* Past PRISM_INDEX_MAX_DIM the reference alone overruns the page, and an | ||
| 307 | * unsigned subtraction would report a capacity of millions -- which the | ||
| 308 | * count checks use as their bound. */ | ||
| 309 |
2/2✓ Branch 0 taken 13008 times.
✓ Branch 1 taken 1432 times.
|
14440 | if (pt >= usable) |
| 310 | 334 | return 0; | |
| 311 | |||
| 312 | 14106 | return (usable - pt) / PRISM_POSTING_ENTRY_SIZE(dim); | |
| 313 | } | ||
| 314 | |||
| 315 | /* Buffer size for a flat page with count entries */ | ||
| 316 | static inline size_t | ||
| 317 | 150 | prism_posting_flat_page_size(Dimension dim, uint32_t count) | |
| 318 | { | ||
| 319 | 300 | return sizeof(PrismFlatPostingHeader) + | |
| 320 | 150 | (size_t)count * PRISM_POSTING_ENTRY_SIZE(dim); | |
| 321 | } | ||
| 322 | |||
| 323 | /* ---------------------------------------------------------------- | ||
| 324 | * Paged-mode access — opaque via PG PageGetSpecialPointer | ||
| 325 | * ---------------------------------------------------------------- */ | ||
| 326 | |||
| 327 | static inline PrismPostingPageOpaque * | ||
| 328 | 1357684 | prism_posting_opaque(Page page) | |
| 329 | { | ||
| 330 |
13/14✓ Branch 1 taken 412 times.
✓ Branch 2 taken 8954 times.
✓ Branch 3 taken 85 times.
✓ Branch 4 taken 12498 times.
✓ Branch 5 taken 8306 times.
✓ Branch 7 taken 1829 times.
✓ Branch 8 taken 8 times.
✓ Branch 10 taken 1 times.
✓ Branch 11 taken 17462 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 28347 times.
✓ Branch 14 taken 103 times.
✓ Branch 17 taken 106 times.
✓ Branch 18 taken 25 times.
|
1156431 | return (PrismPostingPageOpaque *)PageGetSpecialPointer(page); |
| 331 | } | ||
| 332 | |||
| 333 | /* | ||
| 334 | * Is this page a posting page at all (not a wrong-kind page, and not one | ||
| 335 | * only extended but never initialized)? Guard on the special-area size | ||
| 336 | * before reading the opaque, so a page of another kind is never misread | ||
| 337 | * through the posting layout. MAXALIGN, not a bare sizeof: PageGetSpecialSize | ||
| 338 | * reports the on-disk (MAXALIGN'd) special-area size PageInit reserved, and a | ||
| 339 | * struct whose size isn't already a multiple of MAXIMUM_ALIGNOF would | ||
| 340 | * otherwise silently stop matching the moment a field is added. | ||
| 341 | */ | ||
| 342 | static inline bool | ||
| 343 | 5341 | prism_page_is_posting(Page page) | |
| 344 | { | ||
| 345 |
2/3✓ Branch 0 taken 4547 times.
✓ Branch 1 taken 794 times.
✗ Branch 2 not taken.
|
6125 | return !PageIsNew(page) && |
| 346 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4541 times.
|
5331 | PageGetSpecialSize(page) == |
| 347 |
2/2✓ Branch 0 taken 5331 times.
✓ Branch 1 taken 10 times.
|
6125 | MAXALIGN(sizeof(PrismPostingPageOpaque)) && |
| 348 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 5325 times.
✗ Branch 2 not taken.
|
5325 | prism_posting_opaque(page)->page_id == PRISM_POSTING_PAGE_ID; |
| 349 | } | ||
| 350 | |||
| 351 | static inline uint32_t | ||
| 352 | 526 | prism_posting_page_count(Page page) | |
| 353 | { | ||
| 354 | 526 | return prism_posting_opaque(page)->entry_count; | |
| 355 | } | ||
| 356 | |||
| 357 | static inline bool | ||
| 358 | 513586 | prism_posting_page_has_room(Page page) | |
| 359 | { | ||
| 360 | 513586 | PrismPostingPageOpaque *op = prism_posting_opaque(page); | |
| 361 | 513586 | return op->entry_count < op->max_entries; | |
| 362 | } | ||
| 363 | |||
| 364 | /* | ||
| 365 | * Per-cluster head metadata (read from the FIRST page). tail_blkno == | ||
| 366 | * InvalidBlockNumber means it has not been computed yet — see | ||
| 367 | * prism_posting_insert_one, which fills it lazily on the first insert. | ||
| 368 | */ | ||
| 369 | static inline uint32_t | ||
| 370 | 617 | prism_posting_head_live_count(Page head) | |
| 371 | { | ||
| 372 | 617 | return prism_posting_opaque(head)->live_count; | |
| 373 | } | ||
| 374 | |||
| 375 | static inline BlockNumber | ||
| 376 | 198 | prism_posting_head_tail(Page head) | |
| 377 | { | ||
| 378 | 198 | return prism_posting_opaque(head)->tail_blkno; | |
| 379 | } | ||
| 380 | |||
| 381 | /* ---------------------------------------------------------------- | ||
| 382 | * Content-based AoS access — header-agnostic | ||
| 383 | * | ||
| 384 | * Entries are laid out contiguously: entry i starts at | ||
| 385 | * content + i * PRISM_POSTING_ENTRY_SIZE(dim) | ||
| 386 | * and consists of an PrismPostingEntryHeader followed by | ||
| 387 | * VS_RABITQ_BYTES(dim) bytes of bits. The SIMD kernel strides | ||
| 388 | * through bits[] at stride = PRISM_POSTING_ENTRY_SIZE(dim), starting | ||
| 389 | * from prism_posting_first_bits(content). | ||
| 390 | * ---------------------------------------------------------------- */ | ||
| 391 | |||
| 392 | /* Header for entry i (access fields via the struct: hdr->meta, | ||
| 393 | * hdr->f_add, hdr->f_rescale, hdr->f_error). */ | ||
| 394 | static inline PrismPostingEntryHeader * | ||
| 395 | 6125355 | prism_posting_entry_at(char *content, uint32_t i, Dimension dim) | |
| 396 | { | ||
| 397 | 11972261 | return (PrismPostingEntryHeader *)(content + | |
| 398 | 6125355 | (size_t)i * | |
| 399 |
4/4✓ Branch 0 taken 6712 times.
✓ Branch 1 taken 67937 times.
✓ Branch 2 taken 73423 times.
✓ Branch 3 taken 8020 times.
|
6125355 | PRISM_POSTING_ENTRY_SIZE(dim)); |
| 400 | } | ||
| 401 | |||
| 402 | /* Bits pointer for entry i (immediately follows entry i's header). */ | ||
| 403 | static inline uint8_t * | ||
| 404 | 2 | prism_posting_entry_bits_at( | |
| 405 | char *content, uint32_t max_entries, Dimension dim, uint32_t i) | ||
| 406 | { | ||
| 407 | (void)max_entries; | ||
| 408 | 2 | return prism_posting_entry_at(content, i, dim)->bits; | |
| 409 | } | ||
| 410 | |||
| 411 | /* Pointer to entry 0's bits — the base the SIMD kernel uses, with | ||
| 412 | * stride = PRISM_POSTING_ENTRY_SIZE(dim). */ | ||
| 413 | static inline uint8_t * | ||
| 414 | 28460 | prism_posting_first_bits(char *content) | |
| 415 | { | ||
| 416 | 28460 | return ((PrismPostingEntryHeader *)content)->bits; | |
| 417 | } | ||
| 418 | |||
| 419 | /* ---------------------------------------------------------------- | ||
| 420 | * Paged-mode convenience wrappers | ||
| 421 | * | ||
| 422 | * These use PageGetContents for the content pointer and read | ||
| 423 | * max_entries from the opaque. Used by page init/add and tests. | ||
| 424 | * ---------------------------------------------------------------- */ | ||
| 425 | |||
| 426 | static inline char * | ||
| 427 | 92184 | prism_posting_content(Page page) | |
| 428 | { | ||
| 429 | 92184 | return PageGetContents(page); | |
| 430 | } | ||
| 431 | |||
| 432 | /* | ||
| 433 | * On first pages, P^T * centroid is stored right after PageHeader, | ||
| 434 | * before the SoA content. Content starts after pt_centroid area. | ||
| 435 | */ | ||
| 436 | static inline const float * | ||
| 437 | 13339649 | prism_posting_pt_centroid(Page page) | |
| 438 | { | ||
| 439 | 13357111 | return (const float *)PageGetContents(page); | |
| 440 | } | ||
| 441 | |||
| 442 | static inline float * | ||
| 443 | 11962 | prism_posting_pt_centroid_mut(Page page) | |
| 444 | { | ||
| 445 | 11962 | return (float *)PageGetContents(page); | |
| 446 | } | ||
| 447 | |||
| 448 | static inline char * | ||
| 449 | 232176 | prism_posting_content_first(Page page, Dimension dim) | |
| 450 | { | ||
| 451 | 232176 | return PageGetContents(page) + prism_posting_pt_centroid_size(dim); | |
| 452 | } | ||
| 453 | |||
| 454 | /* ---------------------------------------------------------------- | ||
| 455 | * Chain walks | ||
| 456 | * | ||
| 457 | * A posting list is a chain of pages linked by next_blkno. Every caller | ||
| 458 | * that traverses one has to read the link before releasing the page and | ||
| 459 | * release it before moving on; these keep that order in one place. | ||
| 460 | * | ||
| 461 | * The scan path deliberately does not use them. It holds a page across the | ||
| 462 | * SIMD kernels that consume it, interleaves the next page's prefetch, and | ||
| 463 | * handles flat mode (a single page, no chain) and page_base mode (memory it | ||
| 464 | * does not release) -- so its stepping is a different shape, not a | ||
| 465 | * duplicate of this one. | ||
| 466 | * ---------------------------------------------------------------- */ | ||
| 467 | |||
| 468 | /* | ||
| 469 | * Where a read walk currently is. The callback may release the page early | ||
| 470 | * and keep working: the next block is already read, so the walk does not | ||
| 471 | * need it afterwards. That matters for work which must not hold a page -- | ||
| 472 | * fetching heap tuples through the same storage, which holds one page at a | ||
| 473 | * time and would take over the slot. | ||
| 474 | */ | ||
| 475 | typedef struct PrismPostingChainPos | ||
| 476 | { | ||
| 477 | VsStorage *storage; | ||
| 478 | BlockNumber blkno; | ||
| 479 | Page page; /* NULL once released */ | ||
| 480 | BlockNumber next; /* read before the callback runs */ | ||
| 481 | bool first; | ||
| 482 | } PrismPostingChainPos; | ||
| 483 | |||
| 484 | static inline void | ||
| 485 | 5184 | prism_posting_chain_release(PrismPostingChainPos *pos) | |
| 486 | { | ||
| 487 |
2/2✓ Branch 0 taken 4392 times.
✓ Branch 1 taken 792 times.
|
5184 | if (pos->page != NULL) |
| 488 | { | ||
| 489 | 4392 | vs_storage_release_page(pos->storage, pos->blkno); | |
| 490 | 4392 | pos->page = NULL; | |
| 491 | } | ||
| 492 | 5184 | } | |
| 493 | |||
| 494 | /* Return false to stop the walk. */ | ||
| 495 | typedef bool (*PrismPostingChainCb)(PrismPostingChainPos *pos, void *state); | ||
| 496 | |||
| 497 | void prism_posting_chain_walk( | ||
| 498 | VsStorage *storage, | ||
| 499 | BlockNumber head, | ||
| 500 | PrismPostingChainCb cb, | ||
| 501 | void *state); | ||
| 502 | |||
| 503 | /* | ||
| 504 | * Mutating walk: the callback gets the opaque of a page held for write, and | ||
| 505 | * every page is committed. For chain-wide flag changes, where the body is a | ||
| 506 | * line or two and the walk is all of the code. | ||
| 507 | */ | ||
| 508 | typedef void (*PrismPostingChainMutateCb)( | ||
| 509 | PrismPostingPageOpaque *op, void *state); | ||
| 510 | |||
| 511 | void prism_posting_chain_mutate( | ||
| 512 | VsStorage *storage, | ||
| 513 | BlockNumber head, | ||
| 514 | PrismPostingChainMutateCb cb, | ||
| 515 | void *state); | ||
| 516 | |||
| 517 | /* | ||
| 518 | * Content of any posting page, first or not. | ||
| 519 | * | ||
| 520 | * A first page carries pt_centroid ahead of its entries, so the offset | ||
| 521 | * differs; every caller that walks a chain meets both kinds and was | ||
| 522 | * repeating this test. Inline, so the scan pays nothing for it. | ||
| 523 | */ | ||
| 524 | static inline char * | ||
| 525 | 276574 | prism_posting_page_content(Page page, Dimension dim) | |
| 526 | { | ||
| 527 | 276574 | return (prism_posting_opaque(page)->flags & PRISM_POSTING_PAGE_FIRST) | |
| 528 | 187404 | ? prism_posting_content_first(page, dim) | |
| 529 |
2/2✓ Branch 0 taken 187404 times.
✓ Branch 1 taken 89170 times.
|
405158 | : prism_posting_content(page); |
| 530 | } | ||
| 531 | |||
| 532 | /* Paged-mode convenience wrappers — these assume non-first pages | ||
| 533 | * (content starts right after PageHeader). For first pages with | ||
| 534 | * pt_centroid, go through prism_posting_content_first. */ | ||
| 535 | static inline PrismPostingEntryHeader * | ||
| 536 | 2 | prism_posting_entry(Page page, uint32_t i, Dimension dim) | |
| 537 | { | ||
| 538 | 2 | return prism_posting_entry_at(PageGetContents(page), i, dim); | |
| 539 | } | ||
| 540 | |||
| 541 | static inline uint8_t * | ||
| 542 | 2 | prism_posting_entry_bits( | |
| 543 | Page page, uint32_t max_entries, Dimension dim, uint32_t i) | ||
| 544 | { | ||
| 545 | 2 | return prism_posting_entry_bits_at( | |
| 546 | PageGetContents(page), max_entries, dim, i); | ||
| 547 | } | ||
| 548 | |||
| 549 | /* ---------------------------------------------------------------- | ||
| 550 | * Flat-mode access | ||
| 551 | * ---------------------------------------------------------------- */ | ||
| 552 | |||
| 553 | static inline PrismFlatPostingHeader * | ||
| 554 | 10370 | prism_flat_posting_header(char *buf) | |
| 555 | { | ||
| 556 | 10370 | return (PrismFlatPostingHeader *)buf; | |
| 557 | } | ||
| 558 | |||
| 559 | static inline char * | ||
| 560 | 10220 | prism_flat_posting_content(char *buf) | |
| 561 | { | ||
| 562 |
0/2✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
10220 | return buf + sizeof(PrismFlatPostingHeader); |
| 563 | } | ||
| 564 | |||
| 565 | /* ---------------------------------------------------------------- | ||
| 566 | * Standalone helper: pack/extract vector_id in ItemPointerData | ||
| 567 | * ---------------------------------------------------------------- */ | ||
| 568 | |||
| 569 | static inline void | ||
| 570 | 11264 | prism_posting_set_vector_id(ItemPointerData *tid, uint32_t vector_id) | |
| 571 | { | ||
| 572 | 11264 | ItemPointerSet(tid, (BlockNumber)vector_id, 0); | |
| 573 | 11264 | } | |
| 574 | |||
| 575 | static inline uint32_t | ||
| 576 | 150270 | prism_posting_get_vector_id(const ItemPointerData *tid) | |
| 577 | { | ||
| 578 | 150270 | return (uint32_t)ItemPointerGetBlockNumber(tid); | |
| 579 | } | ||
| 580 | |||
| 581 | /* ---------------------------------------------------------------- | ||
| 582 | * TID ↔ uint64_t encoding for VsTopK | ||
| 583 | * | ||
| 584 | * Both standalone and PG store TIDs in VsTopK's uint64_t id field. | ||
| 585 | * For standalone: vector_id is packed in BlockNumber with offset=0, | ||
| 586 | * so encode yields (vector_id << 16) and decode_vector_id shifts | ||
| 587 | * back. For PG: full ItemPointerData (block + offset) fits in 48 | ||
| 588 | * bits of the uint64_t. | ||
| 589 | * ---------------------------------------------------------------- */ | ||
| 590 | |||
| 591 | static inline uint64_t | ||
| 592 | 593806 | prism_posting_encode_tid(const ItemPointerData *tid) | |
| 593 | { | ||
| 594 | 593806 | return ((uint64_t)ItemPointerGetBlockNumber(tid) << 16) | | |
| 595 | 593806 | (uint64_t)ItemPointerGetOffsetNumber(tid); | |
| 596 | } | ||
| 597 | |||
| 598 | static inline ItemPointerData | ||
| 599 | 31665 | prism_posting_decode_tid(uint64_t id) | |
| 600 | { | ||
| 601 | 31665 | ItemPointerData tid; | |
| 602 | 31665 | ItemPointerSet(&tid, (BlockNumber)(id >> 16), (OffsetNumber)(id & 0xFFFF)); | |
| 603 | 31665 | return tid; | |
| 604 | } | ||
| 605 | |||
| 606 | /* Convenience for standalone: extract vector_id from encoded TID. | ||
| 607 | * Works because prism_posting_set_vector_id stores vid in BlockNumber | ||
| 608 | * with offset=0, so (id >> 16) == vid. */ | ||
| 609 | static inline uint32_t | ||
| 610 | 79600 | prism_posting_decode_vector_id(uint64_t id) | |
| 611 | { | ||
| 612 | 79600 | return (uint32_t)(id >> 16); | |
| 613 | } | ||
| 614 | |||
| 615 | /* ---------------------------------------------------------------- | ||
| 616 | * Paged-mode page operations | ||
| 617 | * ---------------------------------------------------------------- */ | ||
| 618 | |||
| 619 | /* | ||
| 620 | * Initialize an empty BLCKSZ posting page. | ||
| 621 | */ | ||
| 622 | void prism_posting_page_init( | ||
| 623 | Page page, uint32_t cluster_id, Dimension dim, uint16_t flags); | ||
| 624 | |||
| 625 | /* | ||
| 626 | * Add one entry to a BLCKSZ page. Returns false if page is full. | ||
| 627 | */ | ||
| 628 | bool prism_posting_page_add( | ||
| 629 | Page page, | ||
| 630 | Dimension dim, | ||
| 631 | ItemPointerData tid, | ||
| 632 | float f_add, | ||
| 633 | float f_rescale, | ||
| 634 | float f_error, | ||
| 635 | const uint8_t *bits, | ||
| 636 | uint8_t entry_flags); | ||
| 637 | |||
| 638 | /* ---------------------------------------------------------------- | ||
| 639 | * Flat-mode page operations | ||
| 640 | * ---------------------------------------------------------------- */ | ||
| 641 | |||
| 642 | /* | ||
| 643 | * Initialize a flat posting page buffer. buf must be at least | ||
| 644 | * prism_posting_flat_page_size(dim, max_entries) bytes. | ||
| 645 | */ | ||
| 646 | void | ||
| 647 | prism_posting_flat_init(char *buf, uint32_t max_entries, uint32_t cluster_id); | ||
| 648 | |||
| 649 | /* | ||
| 650 | * Add one entry to a flat page. Returns false if full. | ||
| 651 | */ | ||
| 652 | bool prism_posting_flat_add( | ||
| 653 | char *buf, | ||
| 654 | Dimension dim, | ||
| 655 | ItemPointerData tid, | ||
| 656 | float f_add, | ||
| 657 | float f_rescale, | ||
| 658 | float f_error, | ||
| 659 | const uint8_t *bits, | ||
| 660 | uint8_t entry_flags); | ||
| 661 | |||
| 662 | /* ---------------------------------------------------------------- | ||
| 663 | * Fastscan page format | ||
| 664 | * | ||
| 665 | * SoA layout organized into 32-vector group sections. | ||
| 666 | * Each group section: | ||
| 667 | * ItemPointerData tids[32] 192B | ||
| 668 | * float f_add[32] 128B | ||
| 669 | * float f_rescale[32] 128B | ||
| 670 | * float f_error[32] 128B | ||
| 671 | * uint8_t codes[nsq_pairs × 32] variable (3072B at dim=768) | ||
| 672 | * | ||
| 673 | * Pages are identified by PRISM_POSTING_PAGE_FASTSCAN in opaque flags. | ||
| 674 | * ---------------------------------------------------------------- */ | ||
| 675 | |||
| 676 | #include "quant/fastscan.h" | ||
| 677 | |||
| 678 | /* Bytes per 32-vector group section (metadata + packed codes) */ | ||
| 679 | static inline uint32_t | ||
| 680 | 113254 | prism_fastscan_group_section_bytes(Dimension dim) | |
| 681 | { | ||
| 682 | 156408 | return (uint32_t)(VS_FASTSCAN_GROUP * sizeof(ItemPointerData) + | |
| 683 | 113254 | VS_FASTSCAN_GROUP * 3 * sizeof(float) + | |
| 684 | 113254 | VS_FASTSCAN_GROUP_BYTES(dim)); | |
| 685 | } | ||
| 686 | |||
| 687 | /* Max entries on a fastscan overflow page */ | ||
| 688 | static inline uint32_t | ||
| 689 | 2158 | prism_fastscan_max_entries(Dimension dim) | |
| 690 | { | ||
| 691 | 2158 | uint32_t section = prism_fastscan_group_section_bytes(dim); | |
| 692 | 2158 | uint32_t usable = prism_posting_page_usable(); | |
| 693 | 2158 | uint32_t ngroups = usable / section; | |
| 694 | 2158 | return ngroups * VS_FASTSCAN_GROUP; | |
| 695 | } | ||
| 696 | |||
| 697 | /* Max entries on a fastscan first page (with pt_centroid) */ | ||
| 698 | static inline uint32_t | ||
| 699 | 10802 | prism_fastscan_max_entries_first(Dimension dim) | |
| 700 | { | ||
| 701 | 10802 | uint32_t section = prism_fastscan_group_section_bytes(dim); | |
| 702 | 10802 | uint32_t usable = prism_posting_page_usable(); | |
| 703 | 10802 | uint32_t pt = prism_posting_pt_centroid_size(dim); | |
| 704 | |||
| 705 |
2/2✓ Branch 0 taken 9792 times.
✓ Branch 1 taken 1010 times.
|
10802 | if (pt >= usable) |
| 706 | 334 | return 0; /* see prism_posting_max_entries_first */ | |
| 707 | |||
| 708 | 10468 | uint32_t ngroups = (usable - pt) / section; | |
| 709 | 10468 | return ngroups * VS_FASTSCAN_GROUP; | |
| 710 | } | ||
| 711 | |||
| 712 | /* | ||
| 713 | * Upper bound on the entries a single posting page can hold, whatever format | ||
| 714 | * it is in. Neither format's figure bounds the other: fastscan packs more | ||
| 715 | * than AoS at low dimension (416 vs 339 at dim 4) and fewer at high (64 vs 67 | ||
| 716 | * at dim 768, and none at all once a group stops fitting). The overflow-page | ||
| 717 | * figures bound a first page too, since that gives up room to the encode | ||
| 718 | * reference. Callers sizing a buffer for one page's worth of entries want | ||
| 719 | * this rather than either half. | ||
| 720 | */ | ||
| 721 | static inline uint32_t | ||
| 722 | 668 | prism_posting_max_entries_any_format(Dimension dim) | |
| 723 | { | ||
| 724 | 668 | uint32_t aos = prism_posting_max_entries(dim); | |
| 725 | 668 | uint32_t fs = prism_fastscan_max_entries(dim); | |
| 726 | 668 | return aos > fs ? aos : fs; | |
| 727 | } | ||
| 728 | |||
| 729 | /* | ||
| 730 | * The entry ceiling a page of this format and position really has. All four | ||
| 731 | * combinations differ: a fastscan page packs more entries than an AoS one, | ||
| 732 | * and a first page gives up room to the encode reference. Bounding an AoS | ||
| 733 | * page by the fastscan figure (or by the larger of the two) would still let | ||
| 734 | * prism_posting_entry_at walk off the page. | ||
| 735 | */ | ||
| 736 | static inline uint32_t | ||
| 737 | 3043 | prism_posting_page_cap(const PrismPostingPageOpaque *op, Dimension dim) | |
| 738 | { | ||
| 739 | 3043 | bool first = (op->flags & PRISM_POSTING_PAGE_FIRST) != 0; | |
| 740 | |||
| 741 |
2/2✓ Branch 0 taken 338 times.
✓ Branch 1 taken 2705 times.
|
3043 | if (op->flags & PRISM_POSTING_PAGE_FASTSCAN) |
| 742 | 290 | return first ? prism_fastscan_max_entries_first(dim) | |
| 743 |
2/2✓ Branch 0 taken 290 times.
✓ Branch 1 taken 48 times.
|
348 | : prism_fastscan_max_entries(dim); |
| 744 | |||
| 745 | 2134 | return first ? prism_posting_max_entries_first(dim) | |
| 746 |
2/2✓ Branch 0 taken 2134 times.
✓ Branch 1 taken 571 times.
|
2797 | : prism_posting_max_entries(dim); |
| 747 | } | ||
| 748 | |||
| 749 | /* | ||
| 750 | * Reject an on-disk entry_count past that ceiling before it drives a loop, so | ||
| 751 | * a corrupt or truncated page cannot read past the page end. The bound the | ||
| 752 | * scan path already applies (posting_scan.c), in the form the shared read | ||
| 753 | * paths need. | ||
| 754 | */ | ||
| 755 | void prism_posting_check_count( | ||
| 756 | BlockNumber blkno, const PrismPostingPageOpaque *op, Dimension dim); | ||
| 757 | |||
| 758 | /* Max groups on a page */ | ||
| 759 | static inline uint32_t | ||
| 760 | 34762 | prism_fastscan_max_groups(Dimension dim, bool is_first) | |
| 761 | { | ||
| 762 | 34762 | uint32_t section = prism_fastscan_group_section_bytes(dim); | |
| 763 | 34762 | uint32_t usable = prism_posting_page_usable(); | |
| 764 |
2/2✓ Branch 0 taken 132 times.
✓ Branch 1 taken 204 times.
|
34762 | if (is_first) |
| 765 | 18857 | usable -= prism_posting_pt_centroid_size(dim); | |
| 766 |
3/3✓ Branch 0 taken 10 times.
✓ Branch 1 taken 161 times.
✓ Branch 2 taken 24 times.
|
9488 | return usable / section; |
| 767 | } | ||
| 768 | |||
| 769 | /* ---------------------------------------------------------------- | ||
| 770 | * Fastscan group accessors | ||
| 771 | * | ||
| 772 | * All take content pointer (past PageHeader, past pt_centroid on | ||
| 773 | * first pages) and group index g. | ||
| 774 | * ---------------------------------------------------------------- */ | ||
| 775 | |||
| 776 | static inline char * | ||
| 777 | 69032 | prism_fastscan_group_base(char *content, uint32_t g, Dimension dim) | |
| 778 | { | ||
| 779 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 9049 times.
|
81014 | return content + (size_t)g * prism_fastscan_group_section_bytes(dim); |
| 780 | } | ||
| 781 | |||
| 782 | static inline ItemPointerData * | ||
| 783 | 17761 | prism_fastscan_group_tids(char *content, uint32_t g, Dimension dim) | |
| 784 | { | ||
| 785 | 17761 | return (ItemPointerData *)prism_fastscan_group_base(content, g, dim); | |
| 786 | } | ||
| 787 | |||
| 788 | static inline float * | ||
| 789 | 39432 | prism_fastscan_group_f_add(char *content, uint32_t g, Dimension dim) | |
| 790 | { | ||
| 791 | 39432 | return (float *)(prism_fastscan_group_base(content, g, dim) + | |
| 792 | VS_FASTSCAN_GROUP * sizeof(ItemPointerData)); | ||
| 793 | } | ||
| 794 | |||
| 795 | static inline float * | ||
| 796 | 38404 | prism_fastscan_group_f_rescale(char *content, uint32_t g, Dimension dim) | |
| 797 | { | ||
| 798 | 38404 | return prism_fastscan_group_f_add(content, g, dim) + VS_FASTSCAN_GROUP; | |
| 799 | } | ||
| 800 | |||
| 801 | static inline float * | ||
| 802 | 37376 | prism_fastscan_group_f_error(char *content, uint32_t g, Dimension dim) | |
| 803 | { | ||
| 804 | 37376 | return prism_fastscan_group_f_rescale(content, g, dim) + VS_FASTSCAN_GROUP; | |
| 805 | } | ||
| 806 | |||
| 807 | static inline uint8_t * | ||
| 808 | 36348 | prism_fastscan_group_codes(char *content, uint32_t g, Dimension dim) | |
| 809 | { | ||
| 810 | 36348 | return (uint8_t *)(prism_fastscan_group_f_error(content, g, dim) + | |
| 811 | VS_FASTSCAN_GROUP); | ||
| 812 | } | ||
| 813 | |||
| 814 | #endif /* PRISM_POSTING_PAGE_H */ | ||
| 815 |