| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * centroid_page.h - Centroid tree page layout | ||
| 6 | * | ||
| 7 | * Centroid pages use bidirectional growth, inspired by PostgreSQL's | ||
| 8 | * standard page layout: | ||
| 9 | * | ||
| 10 | * [PageHeaderData (24B)] | ||
| 11 | * [PrismCentroidEntryMeta[0] ] ← metadata grows forward | ||
| 12 | * [PrismCentroidEntryMeta[1] ] | ||
| 13 | * [ ... ] | ||
| 14 | * [ free space ] | ||
| 15 | * [ ... ] | ||
| 16 | * [ data[1] ] ← vector data grows backward | ||
| 17 | * [ data[0] ] | ||
| 18 | * [PrismCentroidPageOpaque(12B)] | ||
| 19 | * | ||
| 20 | * Metadata grows from the top; vector data grows from the bottom. | ||
| 21 | * The page is full when the two regions would overlap. Metadata | ||
| 22 | * is 8 bytes per entry (uniform across all formats). | ||
| 23 | * | ||
| 24 | * The data format is selected at page initialization and stored in the | ||
| 25 | * low 2 bits of opaque->flags: | ||
| 26 | * | ||
| 27 | * RABITQ (default) — RaBitQData (8 + ceil(dim/8) bytes per entry) | ||
| 28 | * FLOAT — float32 vectors (dim * 4 bytes per entry) | ||
| 29 | * HALF — float16 vectors (dim * 2 bytes per entry) | ||
| 30 | * | ||
| 31 | * RABITQ pages encode centroids relative to a global mean, enabling | ||
| 32 | * fast approximate distance with error bounds. FLOAT/HALF pages store | ||
| 33 | * full-precision vectors for exact routing at the cost of fewer | ||
| 34 | * entries per page. | ||
| 35 | */ | ||
| 36 | |||
| 37 | #ifndef PRISM_CENTROID_PAGE_H | ||
| 38 | #define PRISM_CENTROID_PAGE_H | ||
| 39 | |||
| 40 | #include <stdint.h> | ||
| 41 | #include <string.h> | ||
| 42 | |||
| 43 | #include "core/memory.h" | ||
| 44 | #include "core/types.h" | ||
| 45 | #include "quant/fastscan.h" | ||
| 46 | #include "quant/rabitq.h" | ||
| 47 | #include "types/vec16.h" | ||
| 48 | |||
| 49 | /* Include PG compat for standalone, real PG headers for extension */ | ||
| 50 | #ifdef VS_STANDALONE | ||
| 51 | #include "standalone/pg_compat.h" | ||
| 52 | #else | ||
| 53 | #include <postgres.h> | ||
| 54 | |||
| 55 | #pragma GCC diagnostic push | ||
| 56 | #pragma GCC diagnostic ignored "-Wunused-parameter" | ||
| 57 | #include <storage/bufpage.h> | ||
| 58 | #pragma GCC diagnostic pop | ||
| 59 | #include <storage/itemptr.h> | ||
| 60 | #endif | ||
| 61 | |||
| 62 | /* ---------------------------------------------------------------- | ||
| 63 | * Page type identifier | ||
| 64 | * ---------------------------------------------------------------- */ | ||
| 65 | #define PRISM_CENTROID_PAGE_ID ((uint16_t)0x4D43) /* "MC" */ | ||
| 66 | |||
| 67 | /* ---------------------------------------------------------------- | ||
| 68 | * Centroid entry flags | ||
| 69 | * ---------------------------------------------------------------- */ | ||
| 70 | #define PRISM_CENTROID_FLAG_LEAF ((uint16_t)0x0001) | ||
| 71 | |||
| 72 | /* ---------------------------------------------------------------- | ||
| 73 | * Centroid data format (stored in low 2 bits of opaque->flags) | ||
| 74 | * ---------------------------------------------------------------- */ | ||
| 75 | #define PRISM_CENTROID_FMT_MASK ((uint8_t)0x03) | ||
| 76 | |||
| 77 | typedef enum PrismCentroidFormat | ||
| 78 | { | ||
| 79 | PRISM_CENTROID_FMT_RABITQ = 0, | ||
| 80 | PRISM_CENTROID_FMT_FLOAT = 1, | ||
| 81 | PRISM_CENTROID_FMT_HALF = 2, | ||
| 82 | /* | ||
| 83 | * FASTSCAN: same RaBitQ codes as the RABITQ format, but rearranged | ||
| 84 | * into 32-vector groups with kPerm0 interleaving so the centroid | ||
| 85 | * scoring path can use vs_fastscan_accumulate instead of the | ||
| 86 | * per-vector vs_rabitq_inner_product_multi kernel. | ||
| 87 | * | ||
| 88 | * Group section layout (per 32 entries): | ||
| 89 | * BlockNumber child_blkno[32] 128 B | ||
| 90 | * float f_add[32] 128 B | ||
| 91 | * float f_rescale[32] 128 B | ||
| 92 | * float f_error[32] 128 B | ||
| 93 | * uint8_t codes[nsq_pairs*32] variable | ||
| 94 | * | ||
| 95 | * Per-entry PrismCentroidEntryMeta (4 B child_blkno + 4 B | ||
| 96 | * child_count/flags) is replaced by the array-of-fields layout | ||
| 97 | * above; child_count and per-entry flags are dropped because the | ||
| 98 | * scan already knows from its descent level whether children are | ||
| 99 | * posting heads vs. nested centroid pages, and child_count is only | ||
| 100 | * used at build time. Final group may be partial; unused slots | ||
| 101 | * have child_blkno = InvalidBlockNumber and zero-padded codes. | ||
| 102 | */ | ||
| 103 | PRISM_CENTROID_FMT_FASTSCAN = 3, | ||
| 104 | } PrismCentroidFormat; | ||
| 105 | |||
| 106 | /* ---------------------------------------------------------------- | ||
| 107 | * Per-centroid metadata (grows forward from page header) | ||
| 108 | * | ||
| 109 | * Uniform 8-byte struct used by all formats. For internal nodes, | ||
| 110 | * child_blkno points to the child centroid page. For leaf nodes, | ||
| 111 | * child_blkno points to the posting list head page. | ||
| 112 | * ---------------------------------------------------------------- */ | ||
| 113 | typedef struct PrismCentroidEntryMeta | ||
| 114 | { | ||
| 115 | BlockNumber child_blkno; /* 4B - child page */ | ||
| 116 | uint16_t child_count; /* 2B - children at next level */ | ||
| 117 | uint16_t flags; /* 2B - PRISM_CENTROID_FLAG_LEAF etc */ | ||
| 118 | } PrismCentroidEntryMeta; | ||
| 119 | |||
| 120 | /* ---------------------------------------------------------------- | ||
| 121 | * Page special area (12 bytes, at page end per PG convention) | ||
| 122 | * ---------------------------------------------------------------- */ | ||
| 123 | typedef struct PrismCentroidPageOpaque | ||
| 124 | { | ||
| 125 | BlockNumber next_blkno; /* 4B - next page at same level */ | ||
| 126 | uint16_t entry_count; /* 2B - centroids on this page */ | ||
| 127 | uint8_t level; /* 1B - tree level (0 = root) */ | ||
| 128 | uint8_t flags; /* 1B - page flags */ | ||
| 129 | uint16_t page_id; /* 2B - PRISM_CENTROID_PAGE_ID */ | ||
| 130 | uint16_t padding; /* 2B - alignment */ | ||
| 131 | } PrismCentroidPageOpaque; | ||
| 132 | |||
| 133 | /* ---------------------------------------------------------------- | ||
| 134 | * Capacity calculation | ||
| 135 | * ---------------------------------------------------------------- */ | ||
| 136 | |||
| 137 | /* Usable bytes on a centroid page (between header and MAXALIGN'd opaque) */ | ||
| 138 | #define PRISM_CENTROID_PAGE_USABLE \ | ||
| 139 | (BLCKSZ - SizeOfPageHeaderData - \ | ||
| 140 | (size_t)MAXALIGN(sizeof(PrismCentroidPageOpaque))) | ||
| 141 | |||
| 142 | /* Metadata size per entry (uniform across all formats) */ | ||
| 143 | static inline uint32_t | ||
| 144 | 13989612 | prism_centroid_meta_size(PrismCentroidFormat fmt) | |
| 145 | { | ||
| 146 | (void)fmt; | ||
| 147 | 13989612 | return sizeof(PrismCentroidEntryMeta); | |
| 148 | } | ||
| 149 | |||
| 150 | /* Per-entry data size for routing (centroid vector or RaBitQ) */ | ||
| 151 | static inline uint32_t | ||
| 152 | 21585161 | prism_centroid_data_size(Dimension dim, PrismCentroidFormat fmt) | |
| 153 | { | ||
| 154 |
3/4✓ Branch 0 taken 4030743 times.
✓ Branch 1 taken 158185 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 17396233 times.
|
21585161 | switch (fmt) |
| 155 | { | ||
| 156 | 4030743 | case PRISM_CENTROID_FMT_FLOAT: | |
| 157 | 4030743 | return dim * sizeof(float); | |
| 158 | 158185 | case PRISM_CENTROID_FMT_HALF: | |
| 159 | 158185 | return dim * sizeof(half); | |
| 160 | ✗ | case PRISM_CENTROID_FMT_FASTSCAN: | |
| 161 | /* Average per-entry overhead inside a fastscan group. Used | ||
| 162 | * only by the legacy "data_size × N" capacity check; the | ||
| 163 | * real layout is group-based — see prism_centroid_fastscan_*. */ | ||
| 164 | ✗ | return (uint32_t)(VS_FASTSCAN_GROUP * 3 * sizeof(float) + | |
| 165 | ✗ | VS_FASTSCAN_GROUP_BYTES(dim)) / | |
| 166 | VS_FASTSCAN_GROUP; | ||
| 167 | 17396233 | default: | |
| 168 | 17396233 | return VS_RABITQ_DATA_SIZE(dim); | |
| 169 | } | ||
| 170 | } | ||
| 171 | |||
| 172 | /* Per-entry data size for leaf pages (routing + P^T * centroid) */ | ||
| 173 | static inline uint32_t | ||
| 174 | ✗ | prism_centroid_leaf_data_size(Dimension dim, PrismCentroidFormat fmt) | |
| 175 | { | ||
| 176 | ✗ | return prism_centroid_data_size(dim, fmt) + dim * sizeof(float); | |
| 177 | } | ||
| 178 | |||
| 179 | /* Bytes consumed per entry (metadata + data) for a given format */ | ||
| 180 | static inline uint32_t | ||
| 181 | 1741310 | prism_centroid_entry_bytes_fmt(Dimension dim, PrismCentroidFormat fmt) | |
| 182 | { | ||
| 183 | 1741310 | return prism_centroid_meta_size(fmt) + prism_centroid_data_size(dim, fmt); | |
| 184 | } | ||
| 185 | |||
| 186 | /* Bytes consumed per leaf entry (metadata + routing + pt_centroid) */ | ||
| 187 | static inline uint32_t | ||
| 188 | prism_centroid_leaf_entry_bytes_fmt(Dimension dim, PrismCentroidFormat fmt) | ||
| 189 | { | ||
| 190 | return prism_centroid_meta_size(fmt) + | ||
| 191 | prism_centroid_leaf_data_size(dim, fmt); | ||
| 192 | } | ||
| 193 | |||
| 194 | /* Maximum entries per page for a given format */ | ||
| 195 | static inline uint32_t | ||
| 196 | 5686175 | prism_centroid_max_entries_fmt(Dimension dim, PrismCentroidFormat fmt) | |
| 197 | { | ||
| 198 |
2/2✓ Branch 0 taken 3944865 times.
✓ Branch 1 taken 1723341 times.
|
5668206 | if (fmt == PRISM_CENTROID_FMT_FASTSCAN) |
| 199 | { | ||
| 200 | /* fastscan stores entries in 32-vector groups; max_entries is | ||
| 201 | * ngroups * 32. See prism_centroid_fastscan_group_bytes. */ | ||
| 202 | 3944865 | uint32_t group_bytes = | |
| 203 | (uint32_t)(VS_FASTSCAN_GROUP * sizeof(BlockNumber) + | ||
| 204 | 3944865 | VS_FASTSCAN_GROUP * 3 * sizeof(float) + | |
| 205 | 3944865 | VS_FASTSCAN_GROUP_BYTES(dim)); | |
| 206 | 3944865 | uint32_t ngroups = (uint32_t)PRISM_CENTROID_PAGE_USABLE / group_bytes; | |
| 207 | 3944865 | return ngroups * VS_FASTSCAN_GROUP; | |
| 208 | } | ||
| 209 | 1741310 | return (uint32_t)(PRISM_CENTROID_PAGE_USABLE / | |
| 210 | 1723341 | prism_centroid_entry_bytes_fmt(dim, fmt)); | |
| 211 | } | ||
| 212 | |||
| 213 | /* ---------------------------------------------------------------- | ||
| 214 | * Fastscan centroid page layout | ||
| 215 | * | ||
| 216 | * No PostgreSQL-style meta-grows-forward / data-grows-backward — the | ||
| 217 | * whole page contents area is a sequence of fixed-size group sections | ||
| 218 | * laid out forward from PageGetContents(). The number of valid | ||
| 219 | * entries (which may be < ngroups * 32 for the last group) lives in | ||
| 220 | * opaque->entry_count as for the other formats; ngroups is | ||
| 221 | * ceil(entry_count / 32). | ||
| 222 | * | ||
| 223 | * Per-group section, in this order so that group index g maps to a | ||
| 224 | * single contiguous span computable via g * group_bytes: | ||
| 225 | * | ||
| 226 | * BlockNumber child_blkno[32] | ||
| 227 | * float f_add[32] | ||
| 228 | * float f_rescale[32] | ||
| 229 | * float f_error[32] | ||
| 230 | * uint8_t codes[nsq_pairs * 32] | ||
| 231 | * | ||
| 232 | * Centroid pages do NOT need leaf-mode pt_centroid (that lives on | ||
| 233 | * the first posting page; see prism_posting_pt_centroid). The leaf bit | ||
| 234 | * in opaque flags determines whether child_blkno[*] points to | ||
| 235 | * posting heads or nested centroid pages. | ||
| 236 | * ---------------------------------------------------------------- */ | ||
| 237 | |||
| 238 | static inline uint32_t | ||
| 239 | 5216225 | prism_centroid_fastscan_group_bytes(Dimension dim) | |
| 240 | { | ||
| 241 | 5547701 | return (uint32_t)(VS_FASTSCAN_GROUP * sizeof(BlockNumber) + | |
| 242 | 5216225 | VS_FASTSCAN_GROUP * 3 * sizeof(float) + | |
| 243 | 5216225 | VS_FASTSCAN_GROUP_BYTES(dim)); | |
| 244 | } | ||
| 245 | |||
| 246 | static inline uint32_t | ||
| 247 | 1947 | prism_centroid_fastscan_max_groups(Dimension dim) | |
| 248 | { | ||
| 249 | 1947 | return (uint32_t)PRISM_CENTROID_PAGE_USABLE / | |
| 250 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1482 times.
|
1947 | prism_centroid_fastscan_group_bytes(dim); |
| 251 | } | ||
| 252 | |||
| 253 | /* Group accessors: each takes the page contents pointer + group index. */ | ||
| 254 | static inline char * | ||
| 255 | 5215440 | prism_centroid_fastscan_group_base(char *content, uint32_t g, Dimension dim) | |
| 256 | { | ||
| 257 | 5215440 | return content + (size_t)g * prism_centroid_fastscan_group_bytes(dim); | |
| 258 | } | ||
| 259 | |||
| 260 | static inline BlockNumber * | ||
| 261 | 4998912 | prism_centroid_fastscan_group_child(char *content, uint32_t g, Dimension dim) | |
| 262 | { | ||
| 263 | 4998912 | return (BlockNumber *)prism_centroid_fastscan_group_base(content, g, dim); | |
| 264 | } | ||
| 265 | |||
| 266 | static inline float * | ||
| 267 | 217822 | prism_centroid_fastscan_group_f_add(char *content, uint32_t g, Dimension dim) | |
| 268 | { | ||
| 269 | 3834023 | return (float *)(prism_centroid_fastscan_group_base(content, g, dim) + | |
| 270 | VS_FASTSCAN_GROUP * sizeof(BlockNumber)); | ||
| 271 | } | ||
| 272 | |||
| 273 | static inline float * | ||
| 274 | 163690 | prism_centroid_fastscan_group_f_rescale( | |
| 275 | char *content, uint32_t g, Dimension dim) | ||
| 276 | { | ||
| 277 | 3779891 | return prism_centroid_fastscan_group_f_add(content, g, dim) + | |
| 278 | VS_FASTSCAN_GROUP; | ||
| 279 | } | ||
| 280 | |||
| 281 | static inline float * | ||
| 282 | 109558 | prism_centroid_fastscan_group_f_error(char *content, uint32_t g, Dimension dim) | |
| 283 | { | ||
| 284 | 3725759 | return prism_centroid_fastscan_group_f_rescale(content, g, dim) + | |
| 285 | VS_FASTSCAN_GROUP; | ||
| 286 | } | ||
| 287 | |||
| 288 | static inline uint8_t * | ||
| 289 | 3671627 | prism_centroid_fastscan_group_codes(char *content, uint32_t g, Dimension dim) | |
| 290 | { | ||
| 291 | 3671627 | return (uint8_t *)(prism_centroid_fastscan_group_f_error(content, g, dim) + | |
| 292 | VS_FASTSCAN_GROUP); | ||
| 293 | } | ||
| 294 | |||
| 295 | /* Maximum entries per leaf page (includes pt_centroid per entry) */ | ||
| 296 | static inline uint32_t | ||
| 297 | prism_centroid_max_leaf_entries_fmt(Dimension dim, PrismCentroidFormat fmt) | ||
| 298 | { | ||
| 299 | return (uint32_t)(PRISM_CENTROID_PAGE_USABLE / | ||
| 300 | prism_centroid_leaf_entry_bytes_fmt(dim, fmt)); | ||
| 301 | } | ||
| 302 | |||
| 303 | /* Backward-compatible wrappers (default to RaBitQ format) */ | ||
| 304 | static inline uint32_t | ||
| 305 | prism_centroid_entry_bytes(Dimension dim) | ||
| 306 | { | ||
| 307 | return prism_centroid_entry_bytes_fmt(dim, PRISM_CENTROID_FMT_RABITQ); | ||
| 308 | } | ||
| 309 | |||
| 310 | static inline uint32_t | ||
| 311 | 18131 | prism_centroid_max_entries(Dimension dim) | |
| 312 | { | ||
| 313 | 18131 | return prism_centroid_max_entries_fmt(dim, PRISM_CENTROID_FMT_RABITQ); | |
| 314 | } | ||
| 315 | |||
| 316 | /* ---------------------------------------------------------------- | ||
| 317 | * Page access helpers | ||
| 318 | * | ||
| 319 | * Metadata grows forward from page header. | ||
| 320 | * Vector data grows backward from the opaque area. | ||
| 321 | * ---------------------------------------------------------------- */ | ||
| 322 | |||
| 323 | /* Opaque area via PG-standard PageGetSpecialPointer */ | ||
| 324 | #define PRISM_CENTROID_OPAQUE(page) \ | ||
| 325 | ((PrismCentroidPageOpaque *)PageGetSpecialPointer(page)) | ||
| 326 | |||
| 327 | /* | ||
| 328 | * Is this page a centroid page at all? Same guard shape as | ||
| 329 | * prism_page_is_posting (see posting_page.h) -- MAXALIGN, not a bare sizeof, | ||
| 330 | * since PrismCentroidPageOpaque's 12 bytes are not themselves a multiple of | ||
| 331 | * MAXIMUM_ALIGNOF. The two opaque structs are a different size, so a page of | ||
| 332 | * one kind is never mistaken for the other. | ||
| 333 | */ | ||
| 334 | static inline bool | ||
| 335 | 1 | prism_page_is_centroid(Page page) | |
| 336 | { | ||
| 337 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | return !PageIsNew(page) && |
| 338 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | PageGetSpecialSize(page) == |
| 339 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | MAXALIGN(sizeof(PrismCentroidPageOpaque)) && |
| 340 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
|
1 | PRISM_CENTROID_OPAQUE(page)->page_id == PRISM_CENTROID_PAGE_ID; |
| 341 | } | ||
| 342 | |||
| 343 | /* Data format stored in the page */ | ||
| 344 | static inline PrismCentroidFormat | ||
| 345 | 45974849 | prism_centroid_page_format(Page page) | |
| 346 | { | ||
| 347 | /* Called only on a | ||
| 348 | * pinned centroid page. */ | ||
| 349 | /* NOLINTNEXTLINE(clang-analyzer-core.NullDereference) */ | ||
| 350 |
5/7✓ Branch 1 taken 574 times.
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 221206 times.
✓ Branch 6 taken 49748 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 4447540 times.
|
31748419 | return (PrismCentroidFormat)(PRISM_CENTROID_OPAQUE(page)->flags & |
| 351 | PRISM_CENTROID_FMT_MASK); | ||
| 352 | } | ||
| 353 | |||
| 354 | /* | ||
| 355 | * Get mutable pointer to the i-th metadata entry (write path). | ||
| 356 | * Uses byte-offset arithmetic since meta size is format-dependent. | ||
| 357 | */ | ||
| 358 | static inline PrismCentroidEntryMeta * | ||
| 359 | 20096793 | prism_centroid_meta_mut(Page page, uint32_t index) | |
| 360 | { | ||
| 361 | 27347521 | uint32_t meta_size = prism_centroid_meta_size( | |
| 362 | prism_centroid_page_format(page)); | ||
| 363 | 20096793 | return (PrismCentroidEntryMeta *)((char *)PageGetContents(page) + | |
| 364 | 20096793 | index * meta_size); | |
| 365 | } | ||
| 366 | |||
| 367 | /* Get pointer to the i-th metadata entry (read-only) */ | ||
| 368 | static inline const PrismCentroidEntryMeta * | ||
| 369 | 20089980 | prism_centroid_meta(const Page page, uint32_t index) | |
| 370 | { | ||
| 371 |
2/2✓ Branch 1 taken 98 times.
✓ Branch 2 taken 4244 times.
|
20089980 | return prism_centroid_meta_mut(page, index); |
| 372 | } | ||
| 373 | |||
| 374 | /* | ||
| 375 | * Get pointer to the i-th data entry (backward region). | ||
| 376 | * | ||
| 377 | * Entry 0 is at the highest address (just before opaque), entry 1 | ||
| 378 | * is below it, etc. Data size is determined by the page format. | ||
| 379 | * | ||
| 380 | * Layout (growing backward from opaque): | ||
| 381 | * opaque_start - 1*data_size = data[0] | ||
| 382 | * opaque_start - 2*data_size = data[1] | ||
| 383 | * ... | ||
| 384 | */ | ||
| 385 | /* | ||
| 386 | * Data accessor for the backward-growing data region. | ||
| 387 | * | ||
| 388 | * For leaf pages, each entry stores [routing_data | pt_centroid] | ||
| 389 | * so the total data_size per entry is larger. For internal pages, | ||
| 390 | * only routing_data is stored. | ||
| 391 | */ | ||
| 392 | static inline const void * | ||
| 393 | 19824454 | prism_centroid_entry_data(const Page page, uint32_t index, Dimension dim) | |
| 394 | { | ||
| 395 | 19824454 | PrismCentroidFormat fmt = prism_centroid_page_format(page); | |
| 396 | 19824454 | uint32_t data_size = prism_centroid_data_size(dim, fmt); | |
| 397 | 32671428 | return (const void *)(PageGetSpecialPointer(page) - | |
| 398 | 19824454 | (size_t)(index + 1) * data_size); | |
| 399 | } | ||
| 400 | |||
| 401 | /* Typed accessors for routing data (at start of data region) */ | ||
| 402 | static inline const RaBitQData * | ||
| 403 | 16067806 | prism_centroid_data(const Page page, uint32_t index, Dimension dim) | |
| 404 | { | ||
| 405 | 16067806 | return (const RaBitQData *)prism_centroid_entry_data(page, index, dim); | |
| 406 | } | ||
| 407 | |||
| 408 | static inline const float * | ||
| 409 | 3616485 | prism_centroid_float_data(const Page page, uint32_t index, Dimension dim) | |
| 410 | { | ||
| 411 | 3616485 | return (const float *)prism_centroid_entry_data(page, index, dim); | |
| 412 | } | ||
| 413 | |||
| 414 | static inline const half * | ||
| 415 | 140159 | prism_centroid_half_data(const Page page, uint32_t index, Dimension dim) | |
| 416 | { | ||
| 417 | 140159 | return (const half *)prism_centroid_entry_data(page, index, dim); | |
| 418 | } | ||
| 419 | |||
| 420 | /* ---------------------------------------------------------------- | ||
| 421 | * Page operations | ||
| 422 | * ---------------------------------------------------------------- */ | ||
| 423 | |||
| 424 | /* | ||
| 425 | * Initialize a centroid page with explicit data format. | ||
| 426 | * Zeroes the page, sets up the opaque area with format flag. | ||
| 427 | */ | ||
| 428 | void prism_centroid_page_init_fmt( | ||
| 429 | Page page, uint8_t level, PrismCentroidFormat fmt); | ||
| 430 | |||
| 431 | /* Backward-compatible init (defaults to RaBitQ format) */ | ||
| 432 | static inline void | ||
| 433 | 26 | prism_centroid_page_init(Page page, uint8_t level) | |
| 434 | { | ||
| 435 | 26 | prism_centroid_page_init_fmt(page, level, PRISM_CENTROID_FMT_RABITQ); | |
| 436 | 26 | } | |
| 437 | |||
| 438 | /* | ||
| 439 | * Reserve space for a centroid entry. Writes metadata forward, | ||
| 440 | * reserves data space backward, returns a writable pointer to | ||
| 441 | * the data region. The caller writes entry data directly into | ||
| 442 | * the returned pointer (data_size bytes). | ||
| 443 | * | ||
| 444 | * Returns NULL if the page has no room. | ||
| 445 | */ | ||
| 446 | void *prism_centroid_page_add_entry_begin( | ||
| 447 | Page page, | ||
| 448 | Dimension dim, | ||
| 449 | BlockNumber child_blkno, | ||
| 450 | uint16_t child_count, | ||
| 451 | uint16_t flags); | ||
| 452 | |||
| 453 | /* | ||
| 454 | * Add a centroid entry to a page. Writes metadata forward and | ||
| 455 | * vector data backward. The data format is read from the page's | ||
| 456 | * opaque flags to determine data size. | ||
| 457 | * | ||
| 458 | * data points to the entry payload: | ||
| 459 | * RABITQ → const RaBitQData * | ||
| 460 | * FLOAT → const float * (dim elements) | ||
| 461 | * HALF → const half * (dim elements) | ||
| 462 | */ | ||
| 463 | bool prism_centroid_page_add_entry( | ||
| 464 | Page page, | ||
| 465 | Dimension dim, | ||
| 466 | BlockNumber child_blkno, | ||
| 467 | uint16_t child_count, | ||
| 468 | uint16_t flags, | ||
| 469 | const void *data); | ||
| 470 | |||
| 471 | /* | ||
| 472 | * Overwrite an existing entry in place: replace its child_blkno and its | ||
| 473 | * routing data (data must be data_size bytes in the page's format), leaving | ||
| 474 | * child_count/flags, entry_count, and the page layout untouched. Used by the | ||
| 475 | * incremental posting-list split to repoint a leaf entry at its first child | ||
| 476 | * list and update its routing centroid. | ||
| 477 | */ | ||
| 478 | void prism_centroid_page_overwrite_entry( | ||
| 479 | Page page, | ||
| 480 | Dimension dim, | ||
| 481 | uint32_t index, | ||
| 482 | BlockNumber child_blkno, | ||
| 483 | const void *data); | ||
| 484 | |||
| 485 | /* Backward-compatible add (RaBitQ-typed parameter) */ | ||
| 486 | static inline bool | ||
| 487 | 756 | prism_centroid_page_add( | |
| 488 | Page page, | ||
| 489 | Dimension dim, | ||
| 490 | BlockNumber child_blkno, | ||
| 491 | uint16_t child_count, | ||
| 492 | uint16_t flags, | ||
| 493 | const RaBitQData *data) | ||
| 494 | { | ||
| 495 | 756 | return prism_centroid_page_add_entry( | |
| 496 | page, dim, child_blkno, child_count, flags, data); | ||
| 497 | } | ||
| 498 | |||
| 499 | /* | ||
| 500 | * Where the metadata region ends on a page holding `nentries`. | ||
| 501 | * | ||
| 502 | * Derived from entry_count rather than read from pd_lower, because pd_lower | ||
| 503 | * does not survive a page write outside index build: prism keeps its data | ||
| 504 | * in the region PostgreSQL treats as the free hole, and the storage layer | ||
| 505 | * covers that hole (pd_lower = pd_upper) so a full-page image preserves it. | ||
| 506 | * Every other page kind is indifferent -- centroid pages are the only ones | ||
| 507 | * that grow a forward region -- so entry_count, which lives in the opaque | ||
| 508 | * area and does survive, is the authoritative cursor. It is also what the | ||
| 509 | * data-region reader already uses (prism_centroid_entry_data indexes off | ||
| 510 | * pd_special), so the two regions stay consistent. | ||
| 511 | */ | ||
| 512 | static inline size_t | ||
| 513 | 16993 | prism_centroid_meta_end(Page page, uint32_t nentries) | |
| 514 | { | ||
| 515 | 16467 | PrismCentroidFormat fmt = prism_centroid_page_format(page); | |
| 516 | 29665 | return (size_t)SizeOfPageHeaderData + | |
| 517 | 15398 | (size_t)nentries * prism_centroid_meta_size(fmt); | |
| 518 | } | ||
| 519 | |||
| 520 | /* | ||
| 521 | * Check if a page has room for one more entry. | ||
| 522 | * Reads data format from the page to determine entry size. | ||
| 523 | */ | ||
| 524 | static inline bool | ||
| 525 | 10276 | prism_centroid_page_has_room(Page page, Dimension dim, bool is_leaf) | |
| 526 | { | ||
| 527 | 10276 | PageHeader header = (PageHeader)page; | |
| 528 | 10276 | PrismCentroidFormat fmt = prism_centroid_page_format(page); | |
| 529 | 10276 | size_t need_fwd = prism_centroid_meta_size(fmt); | |
| 530 | 5328 | size_t need_bwd = is_leaf ? prism_centroid_leaf_data_size(dim, fmt) | |
| 531 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10276 times.
|
10276 | : prism_centroid_data_size(dim, fmt); |
| 532 | 15604 | size_t lower = prism_centroid_meta_end( | |
| 533 | 10276 | page, PRISM_CENTROID_OPAQUE(page)->entry_count); | |
| 534 | |||
| 535 | 10276 | return lower + need_fwd + need_bwd <= header->pd_upper; | |
| 536 | } | ||
| 537 | |||
| 538 | #endif /* PRISM_CENTROID_PAGE_H */ | ||
| 539 |