GCC Code Coverage Report


Directory: src/
File: src/index/posting_page.h
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 177 177 100.0%
Functions: 56 56 100.0%
Branches: 142 157 90.4%

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 * (reference prefix — on a list's first entry 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 /*
62 * Page flags.
63 *
64 * The low two bits are a field, not two flags: the page's part of its
65 * list's head. A list's head is the pages that carry its encode reference
66 * (P^T * centroid, 4 * dim bytes). An inline list's head is its first page,
67 * which holds the whole reference followed by entries. A spilled list
68 * (prism_posting_spilled, past 1968 dimensions) spreads the reference over
69 * prism_posting_reference_pages(dim) pages, which the bulk build lays out
70 * contiguously after the first:
71 *
72 * head part inline list spilled list
73 * START whole reference, then entries a page of reference only
74 * MIDDLE (none) a page of reference only
75 * END (none) rest of reference, entries
76 * NONE entries entries
77 *
78 * START means the same on every list: the list's first page, which carries
79 * the head metadata in the opaque and is what a leaf centroid points at.
80 * Whether it also holds entries follows from the dimension. The values share
81 * bits (END includes START's), so read the field with
82 * prism_posting_head_part and compare it; never test one of its bits alone.
83 */
84 #define PRISM_POSTING_PAGE_HEAD_MASK 0x0003
85 #define PRISM_POSTING_HEAD_NONE 0x0000
86 #define PRISM_POSTING_HEAD_START 0x0001
87 #define PRISM_POSTING_HEAD_MIDDLE 0x0002
88 #define PRISM_POSTING_HEAD_END 0x0003
89
90 /* The page's entries are in the fastscan format, not AoS. */
91 #define PRISM_POSTING_PAGE_FASTSCAN 0x0004
92 /*
93 * Every entry on the page is dead (AoS: all entries flagged; FASTSCAN: every
94 * lane of every group's tombstone_mask set). Both formats mark entries
95 * individually; this flag is the scan-side shortcut that lets a fully dead
96 * page skip its scoring kernel outright. The page stays linked so compaction
97 * can later reclaim it. Cleared if the page is ever reused for new entries.
98 */
99 #define PRISM_POSTING_PAGE_TOMBSTONED 0x0008
100 /*
101 * The page belongs to a chain that has been logically retired — no longer
102 * reachable through the centroid tree — and is awaiting physical reclaim. A
103 * posting-list split sets this on every page of the old chain (head included)
104 * once it has repointed the leaf at the new heads.
105 *
106 * Distinct from TOMBSTONED: a tombstoned page is all-dead but still a live
107 * part of its cluster, so scans skip it and follow the chain past it. A
108 * DELETED chain is off the tree but stays physically LINKED and readable until
109 * reclaim, so an in-flight scanner that already followed a stale leaf pointer
110 * into it still sees a consistent list rather than a gap.
111 *
112 * When this flag is set on a head, the head-metadata overlay in the opaque
113 * (see the union below) holds the deletion XID instead of
114 * live_count/tail_blkno. The reclaim gate compares that XID against the global
115 * visibility horizon before physically reclaiming the chain, so a scanner that
116 * still holds a stale pointer can never have it repurposed underneath it.
117 * Unlike TOMBSTONED, this flag therefore does apply to chain heads: a split
118 * retires the whole old chain, head and all.
119 */
120 #define PRISM_POSTING_PAGE_DELETED 0x0010
121
122 /* ----------------------------------------------------------------
123 * Structs
124 * ---------------------------------------------------------------- */
125
126 /*
127 * Per-entry metadata.
128 *
129 * In PG: tid is a heap TID for reranking via buffer cache.
130 * In standalone: vector_id packed into tid via ItemPointerSet.
131 */
132 typedef struct PrismPostingEntryMeta
133 {
134 ItemPointerData tid; /* 6B */
135 uint8_t flags;
136 uint8_t reserved;
137 } PrismPostingEntryMeta; /* 8B */
138
139 /*
140 * Per-entry header in the AoS layout: meta + the three RaBitQ
141 * scalar factors, followed by a flexible array of quantized bits
142 * (VS_RABITQ_BYTES(dim) bytes at runtime).
143 *
144 * sizeof(PrismPostingEntryHeader) is 20B — the FAM doesn't contribute
145 * to the struct's static size, so PRISM_POSTING_ENTRY_HEADER_SIZE
146 * stays a clean compile-time constant. The bits array extends past
147 * the struct in memory; callers compute per-entry offsets via
148 * PRISM_POSTING_ENTRY_SIZE(dim) and access bits as `hdr->bits`.
149 */
150 typedef struct PrismPostingEntryHeader
151 {
152 PrismPostingEntryMeta meta; /* 8B */
153 float f_add; /* 4B */
154 float f_rescale; /* 4B */
155 float f_error; /* 4B */
156 uint8_t bits[FLEXIBLE_ARRAY_MEMBER];
157 } PrismPostingEntryHeader; /* 20B + dim-dependent bits */
158
159 /*
160 * Paged-mode opaque (at end of every BLCKSZ posting page).
161 */
162 typedef struct PrismPostingPageOpaque
163 {
164 BlockNumber next_blkno; /* next page in chain */
165 uint32_t cluster_id;
166 uint16_t entry_count; /* entries on this page */
167 uint16_t flags; /* PRISM_POSTING_PAGE_* */
168 uint16_t page_id; /* PRISM_POSTING_PAGE_ID */
169
170 /*
171 * An AoS page's capacity. A fastscan page takes no inserts, so it holds
172 * the length of its run of the list's code stream instead (see the
173 * fastscan page format below).
174 */
175 union
176 {
177 uint16_t max_entries;
178 uint16_t code_bytes;
179 };
180
181 /*
182 * Overlay (8 bytes). On a live page these are the per-cluster head
183 * metadata; on a page flagged PRISM_POSTING_PAGE_DELETED they instead
184 * carry the deletion XID for the reclaim gate. The DELETED flag is the
185 * sole discriminator — always read live_count/tail_blkno only when it is
186 * clear and delete_xid only when it is set. A posting-list split retires
187 * the whole old chain, its START page included, so a DELETED head does
188 * carry delete_xid here rather than head metadata; readers of head
189 * metadata (insert, split) first check the flag and treat a retired head
190 * as gone, so the two uses never collide. The anonymous struct/union keeps
191 * op->live_count, op->tail_blkno, and op->delete_xid all directly
192 * accessible. Storing the XID as a backend-neutral uint64_t (not PG's
193 * FullTransactionId) keeps this header usable by the standalone engine;
194 * the PG side converts via U64FromFullTransactionId / the inverse.
195 */
196 union
197 {
198 struct
199 {
200 /*
201 * Lets the runtime insert path find the chain tail in O(1) and
202 * track per-cluster live size (for LIRE split/merge in a later
203 * phase). tail_blkno == InvalidBlockNumber means "not yet
204 * computed": the first insert walks the chain to fill both fields,
205 * then maintains them incrementally. Left zero / Invalid on
206 * overflow (non-first) pages.
207 */
208 uint32_t live_count;
209 BlockNumber tail_blkno;
210 };
211
212 /* Valid only when PRISM_POSTING_PAGE_DELETED is set (see flag
213 * comment).
214 */
215 uint64_t delete_xid;
216 };
217 } PrismPostingPageOpaque; /* 24B */
218
219 /*
220 * True when this page's entries are gone for good, as opposed to moved.
221 *
222 * TOMBSTONED means "nothing here worth scoring" and the scan skips the page.
223 * The reclaim pass sets the same bit on a retired chain, whose entries are not
224 * dead at all -- they were rewritten into the chain's replacements -- so
225 * skipping there drops results that a stale-pointer scan is entitled to see.
226 * DELETED separates the two: it is set only by the retire pass, so a page
227 * carrying both moved rather than died, and its contents are still intact and
228 * linked until #224 makes the pages reusable.
229 */
230 static inline bool
231 59971 prism_posting_page_all_dead(const PrismPostingPageOpaque *op)
232 {
233
6/8
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 57402 times.
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 92 times.
✓ Branch 5 taken 2456 times.
✓ Branch 6 taken 92 times.
✗ Branch 7 not taken.
59985 return (op->flags & PRISM_POSTING_PAGE_TOMBSTONED) != 0 &&
234
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 2 times.
14 (op->flags & PRISM_POSTING_PAGE_DELETED) == 0;
235 }
236
237 /*
238 * Flat-mode header (at start of flat page buffer).
239 * No PG PageHeaderData — avoids the uint16_t page size limit.
240 */
241 typedef struct PrismFlatPostingHeader
242 {
243 uint32_t max_entries; /* == capacity (sized for count) */
244 uint32_t entry_count;
245 uint32_t cluster_id;
246 uint32_t _pad;
247 } PrismFlatPostingHeader; /* 16B */
248
249 /* ----------------------------------------------------------------
250 * Size calculations
251 * ---------------------------------------------------------------- */
252
253 /* Bytes in the per-entry header (meta + 3 floats) */
254 #define PRISM_POSTING_ENTRY_HEADER_SIZE \
255 sizeof(PrismPostingEntryHeader) /* 20B */
256
257 /* Byte offset of bits[] within one entry. Equal to the header size
258 * because bits[] is the FAM right after the header. */
259 #define PRISM_POSTING_ENTRY_BITS_OFFSET offsetof(PrismPostingEntryHeader, bits)
260
261 /* Bytes per entry in bits region */
262 #define PRISM_POSTING_BITS_PER_ENTRY(dim) VS_RABITQ_BYTES(dim)
263
264 /* Entry stride must be a multiple of PrismPostingEntryHeader's alignment
265 * (4 bytes — the float fields) so entry i's float members land on
266 * properly aligned addresses regardless of `i`. For dim values where
267 * VS_RABITQ_BYTES(dim) isn't already a multiple of 4 (i.e., dim not
268 * a multiple of 32, such as dim=16 or dim=100), we pad up. */
269 #define PRISM_POSTING_ENTRY_ALIGN 4u
270
271 /* Total bytes per entry: header + bits, padded up to entry alignment
272 * (= 116 at dim=768; 24 at dim=16). */
273 #define PRISM_POSTING_ENTRY_SIZE(dim) \
274 (((PRISM_POSTING_ENTRY_HEADER_SIZE + PRISM_POSTING_BITS_PER_ENTRY(dim)) + \
275 PRISM_POSTING_ENTRY_ALIGN - 1u) & \
276 ~(PRISM_POSTING_ENTRY_ALIGN - 1u))
277
278 /*
279 * A posting list's first page holds a full-precision encode reference (a
280 * vector of 32-bit floats). The reference fits into the first page, together
281 * with at least one entry, up to dimension PRISM_INDEX_NARROW_MAX_DIM.
282 * Vectors of higher dimensions spill over to the following page(s) in a
283 * chain of reference pages (prism_posting_spilled).
284 *
285 * Derived at 8-byte alignment, the largest MAXALIGN PostgreSQL uses, so it
286 * is one constant on every platform; where MAXALIGN is smaller the head has
287 * a few bytes of slack and the threshold is merely conservative. The static
288 * asserts keep the number honest against layout changes.
289 */
290 #define PRISM_INDEX_NARROW_MAX_DIM 1968
291
292 #define PRISM_CEILING_ALIGN(len) (((size_t)(len) + 7) & ~(size_t)7)
293
294 static_assert(
295 BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) -
296 sizeof(PrismPostingPageOpaque) -
297 PRISM_CEILING_ALIGN(
298 PRISM_INDEX_NARROW_MAX_DIM * sizeof(float)) >=
299 PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_NARROW_MAX_DIM),
300 "an inline head must fit the encode reference plus one entry");
301 static_assert(
302 BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) -
303 sizeof(PrismPostingPageOpaque) -
304 PRISM_CEILING_ALIGN(
305 (PRISM_INDEX_NARROW_MAX_DIM + 1) *
306 sizeof(float)) <
307 PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_NARROW_MAX_DIM + 1),
308 "the inline threshold is tight: one dimension more must not fit");
309
310 /*
311 * Hard dimension ceiling for the index layout, which is imposed by the
312 * Hadamard fast-rotation bound.
313 *
314 * A dimension above PRISM_INDEX_NARROW_MAX_DIM is admitted only when
315 * vs_fast_rotate_supported() holds (see prism_index_dim_supported), and
316 * the Hadamard transform's inline sign storage stops at
317 * VS_FAST_ROTATE_MAX_DIM.
318 */
319 #define PRISM_INDEX_MAX_DIM 8192
320
321 static_assert(
322 PRISM_INDEX_MAX_DIM <= VS_FAST_ROTATE_MAX_DIM,
323 "every admitted dimension must rotate through the fast path");
324
325 /*
326 * The one gate every build applies: an inline layout up to the narrow
327 * threshold, and past it a spilled layout only where the fast rotation
328 * applies (dim = 2^m * k with 2^m >= 4 and odd k <= 8: 2048, 3072, 4096,
329 * 6144, 8192 pass; 3000 does not). Takes a uint32_t so a wider dimension
330 * is range-checked before it narrows to a Dimension.
331 */
332 static inline bool
333 16801 prism_index_dim_supported(uint32_t dim)
334 {
335
4/4
✓ Branch 0 taken 16798 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 16536 times.
16801 if (dim == 0 || dim > PRISM_INDEX_MAX_DIM)
336 8 return false;
337
2/2
✓ Branch 0 taken 4085 times.
✓ Branch 1 taken 12707 times.
16792 if (dim <= PRISM_INDEX_NARROW_MAX_DIM)
338 4050 return true;
339 12521 return vs_fast_rotate_supported((Dimension)dim);
340 }
341
342 static_assert(
343 BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) -
344 sizeof(PrismPostingPageOpaque) >=
345 PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_MAX_DIM),
346 "an overflow page must hold one entry at the ceiling");
347
348 /* Usable space on a BLCKSZ page (between content start and opaque) */
349 static inline uint32_t
350 14406274 prism_posting_page_usable(void)
351 {
352 14406274 return BLCKSZ - (uint32_t)MAXALIGN(SizeOfPageHeaderData) -
353 sizeof(PrismPostingPageOpaque);
354 }
355
356 /* Space occupied by P^T * centroid on an inline first page (MAXALIGN'd) */
357 static inline uint32_t
358 69815945 prism_posting_pt_centroid_size(Dimension dim)
359 {
360 69815945 return (uint32_t)MAXALIGN(dim * sizeof(float));
361 }
362
363 /*
364 * True when the encode reference no longer fits beside one entry on the
365 * first page, so the list spreads it over several head pages. Equivalent to
366 * dim > PRISM_INDEX_NARROW_MAX_DIM at 8-byte MAXALIGN; computed from the
367 * layout so a different alignment cannot disagree with the pages.
368 */
369 static inline bool
370 69604647 prism_posting_spilled(Dimension dim)
371 {
372 69604647 return prism_posting_pt_centroid_size(dim) +
373
7/8
✓ Branch 0 taken 14607 times.
✓ Branch 1 taken 17618 times.
✓ Branch 2 taken 2722 times.
✓ Branch 3 taken 29053 times.
✓ Branch 4 taken 273 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 124554 times.
✓ Branch 7 taken 10862570 times.
54058171 PRISM_POSTING_ENTRY_SIZE(dim) >
374 14324954 prism_posting_page_usable();
375 }
376
377 /* Floats of the reference on a full head page: its whole usable area. */
378 #define PRISM_POSTING_REFERENCE_PAGE_FLOATS \
379 ((BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - \
380 sizeof(PrismPostingPageOpaque)) / \
381 sizeof(float))
382
383 /*
384 * Pages that carry the encode reference, the list's head pages: one for an
385 * inline layout, else START, MIDDLE and END. This is also the head stride of
386 * the bulk-built head region (prism_leaf_head_blkno), so a leaf's head pages
387 * are contiguous.
388 *
389 * A spilled list always has a START and an END page: the smallest spilled
390 * dimension the index accepts (2048) takes more than a page of floats.
391 */
392 static inline uint32_t
393 41326100 prism_posting_reference_pages(Dimension dim)
394 {
395
3/3
✓ Branch 0 taken 297275 times.
✓ Branch 1 taken 40459146 times.
✓ Branch 2 taken 569679 times.
41326100 if (!prism_posting_spilled(dim))
396 7767488 return 1;
397 866954 return ((uint32_t)dim + PRISM_POSTING_REFERENCE_PAGE_FLOATS - 1) /
398 PRISM_POSTING_REFERENCE_PAGE_FLOATS;
399 }
400
401 /* Floats of the reference on head page i of a spilled list (0 = START). */
402 static inline uint32_t
403 377662 prism_posting_reference_page_floats(Dimension dim, uint32_t i)
404 {
405 377662 uint32_t start = i * (uint32_t)PRISM_POSTING_REFERENCE_PAGE_FLOATS;
406
407
3/4
✓ Branch 0 taken 124888 times.
✓ Branch 1 taken 247315 times.
✓ Branch 2 taken 545 times.
✗ Branch 3 not taken.
376484 if (start >= dim)
408 334 return 0;
409 374835 return (dim - start) < PRISM_POSTING_REFERENCE_PAGE_FLOATS
410 ? (dim - start)
411 377328 : (uint32_t)PRISM_POSTING_REFERENCE_PAGE_FLOATS;
412 }
413
414 /* The page's part of its list's head (see the page flags above). */
415 static inline uint16_t
416 28298718 prism_posting_head_part(uint16_t flags)
417 {
418
3/4
✓ Branch 0 taken 10987414 times.
✓ Branch 1 taken 141 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 148 times.
17091567 return flags & PRISM_POSTING_PAGE_HEAD_MASK;
419 }
420
421 /* Whether the page is its list's first page, the one with head metadata. */
422 static inline bool
423 18871 prism_posting_is_head_start(uint16_t flags)
424 {
425
3/4
✓ Branch 0 taken 2008 times.
✓ Branch 1 taken 14454 times.
✓ Branch 2 taken 455 times.
✗ Branch 3 not taken.
18871 return prism_posting_head_part(flags) == PRISM_POSTING_HEAD_START;
426 }
427
428 /*
429 * Whether the page holds part of the reference and no entries: a spilled
430 * list's START page, or a MIDDLE page. Code that looks at a page on its
431 * own uses this to tell it from a page with entries: its capacity is 0, the
432 * builder writes no entries to it, and conversion and inspection count it
433 * as reference. An END page also holds reference, but entries follow it.
434 */
435 static inline bool
436 13938430 prism_posting_is_reference_only_page(uint16_t flags, Dimension dim)
437 {
438 13938430 uint16_t part = prism_posting_head_part(flags);
439
440
2/2
✓ Branch 0 taken 11065144 times.
✓ Branch 1 taken 2873286 times.
13938430 if (part == PRISM_POSTING_HEAD_MIDDLE)
441 46390 return true;
442
5/5
✓ Branch 0 taken 13680664 times.
✓ Branch 1 taken 168170 times.
✓ Branch 2 taken 10923421 times.
✓ Branch 3 taken 134505 times.
✓ Branch 4 taken 2622738 times.
24827019 return part == PRISM_POSTING_HEAD_START && prism_posting_spilled(dim);
443 }
444
445 /*
446 * The reference prefix: the part of the reference a list's first entry page
447 * holds ahead of its entries. That is the whole reference on an inline
448 * START page and the rest of it on an END page. Entries, AoS or fastscan,
449 * start this many bytes into the page content, so the prefix sets where a
450 * reader finds them and how many fit. MAXALIGN'd so the entries start
451 * aligned.
452 */
453 static inline uint32_t
454 358242 prism_posting_ref_prefix_size(Dimension dim)
455 {
456
3/3
✓ Branch 0 taken 2421 times.
✓ Branch 1 taken 343086 times.
✓ Branch 2 taken 12735 times.
358242 if (!prism_posting_spilled(dim))
457 211298 return prism_posting_pt_centroid_size(dim);
458
459 15156 uint32_t last = prism_posting_reference_pages(dim) - 1;
460
461
1/2
✓ Branch 0 taken 2421 times.
✗ Branch 1 not taken.
17577 return (uint32_t)MAXALIGN(
462 prism_posting_reference_page_floats(dim, last) * sizeof(float));
463 }
464
465 /*
466 * Whether the page has a reference prefix, so its entries start after it:
467 * an inline START page or an END page. Every other page that holds entries
468 * has them from the start of its content.
469 */
470 static inline bool
471 533930 prism_posting_has_ref_prefix(uint16_t flags, Dimension dim)
472 {
473 533930 uint16_t part = prism_posting_head_part(flags);
474
475
2/2
✓ Branch 0 taken 192780 times.
✓ Branch 1 taken 341150 times.
533930 if (part == PRISM_POSTING_HEAD_END)
476 12965 return true;
477
5/5
✓ Branch 0 taken 353650 times.
✓ Branch 1 taken 164903 times.
✓ Branch 2 taken 575 times.
✓ Branch 3 taken 352727 times.
✓ Branch 4 taken 348 times.
557779 return part == PRISM_POSTING_HEAD_START && !prism_posting_spilled(dim);
478 }
479
480 /*
481 * Head block of a leaf, and back. Heads sit in a region at first_posting
482 * with a fixed stride: 1 for an inline layout,
483 * prism_posting_reference_pages(dim) for a spilled one, so the reference
484 * pages follow their head. The stride is passed rather than derived from
485 * dim because the standalone in-RAM build addresses leaves by index
486 * (first_posting 0, stride 1).
487 */
488 static inline BlockNumber
489 38260 prism_leaf_head_blkno(
490 BlockNumber first_posting, uint32_t leaf, uint32_t stride)
491 {
492 38260 return first_posting + (BlockNumber)leaf * stride;
493 }
494
495 static inline uint32_t
496 13645470 prism_route_head_to_leaf(
497 BlockNumber first_posting, BlockNumber head, uint32_t stride)
498 {
499
2/2
✓ Branch 0 taken 48600 times.
✓ Branch 1 taken 24000 times.
13645470 return (uint32_t)(head - first_posting) / stride;
500 }
501
502 /* Max entries on a page with no reference ahead of its entries */
503 static inline uint32_t
504 49386 prism_posting_max_entries(Dimension dim)
505 {
506 48329 return prism_posting_page_usable() / PRISM_POSTING_ENTRY_SIZE(dim);
507 }
508
509 /*
510 * Max entries on a list's first entry page, after its reference prefix
511 * (prism_posting_ref_prefix_size): an inline START page or an END page.
512 */
513 static inline uint32_t
514 45463 prism_posting_max_entries_first(Dimension dim)
515 {
516 45463 return (prism_posting_page_usable() - prism_posting_ref_prefix_size(dim)) /
517 45463 PRISM_POSTING_ENTRY_SIZE(dim);
518 }
519
520 /* Buffer size for a flat page with count entries */
521 static inline size_t
522 188 prism_posting_flat_page_size(Dimension dim, uint32_t count)
523 {
524 376 return sizeof(PrismFlatPostingHeader) +
525 188 (size_t)count * PRISM_POSTING_ENTRY_SIZE(dim);
526 }
527
528 /* ----------------------------------------------------------------
529 * Paged-mode access — opaque via PG PageGetSpecialPointer
530 * ---------------------------------------------------------------- */
531
532 static inline PrismPostingPageOpaque *
533 29325052 prism_posting_opaque(Page page)
534 {
535
17/18
✓ Branch 1 taken 789 times.
✓ Branch 2 taken 10056 times.
✓ Branch 3 taken 1283 times.
✓ Branch 4 taken 22202 times.
✓ Branch 5 taken 2805 times.
✓ Branch 6 taken 290 times.
✓ Branch 7 taken 141 times.
✓ Branch 8 taken 1 times.
✓ Branch 9 taken 32818 times.
✓ Branch 10 taken 19594 times.
✓ Branch 11 taken 19842 times.
✓ Branch 12 taken 2599 times.
✓ Branch 13 taken 3720 times.
✓ Branch 14 taken 33849 times.
✓ Branch 15 taken 107 times.
✓ Branch 16 taken 206 times.
✗ Branch 19 not taken.
✓ Branch 20 taken 148 times.
29077109 return (PrismPostingPageOpaque *)PageGetSpecialPointer(page);
536 }
537
538 /*
539 * Is this page a posting page at all (not a wrong-kind page, and not one
540 * only extended but never initialized)? Guard on the special-area size
541 * before reading the opaque, so a page of another kind is never misread
542 * through the posting layout. MAXALIGN, not a bare sizeof: PageGetSpecialSize
543 * reports the on-disk (MAXALIGN'd) special-area size PageInit reserved, and a
544 * struct whose size isn't already a multiple of MAXIMUM_ALIGNOF would
545 * otherwise silently stop matching the moment a field is added.
546 */
547 static inline bool
548 13814412 prism_page_is_posting(Page page)
549 {
550
2/3
✓ Branch 0 taken 10993828 times.
✓ Branch 1 taken 2820584 times.
✗ Branch 2 not taken.
16634986 return !PageIsNew(page) &&
551
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 10993821 times.
13814402 PageGetSpecialSize(page) ==
552
2/2
✓ Branch 0 taken 13814402 times.
✓ Branch 1 taken 10 times.
16634986 MAXALIGN(sizeof(PrismPostingPageOpaque)) &&
553
1/3
✗ Branch 0 not taken.
✓ Branch 1 taken 13814395 times.
✗ Branch 2 not taken.
13814395 prism_posting_opaque(page)->page_id == PRISM_POSTING_PAGE_ID;
554 }
555
556 static inline uint32_t
557 1069 prism_posting_page_count(Page page)
558 {
559 1069 return prism_posting_opaque(page)->entry_count;
560 }
561
562 /* Room for one more AoS entry. A fastscan page never takes one. */
563 static inline bool
564 573222 prism_posting_page_has_room(Page page)
565 {
566 573222 PrismPostingPageOpaque *op = prism_posting_opaque(page);
567
1/2
✓ Branch 0 taken 573222 times.
✗ Branch 1 not taken.
1018255 return !(op->flags & PRISM_POSTING_PAGE_FASTSCAN) &&
568
2/2
✓ Branch 0 taken 444563 times.
✓ Branch 1 taken 128659 times.
573222 op->entry_count < op->max_entries;
569 }
570
571 /*
572 * Per-cluster head metadata (read from the START page). tail_blkno ==
573 * InvalidBlockNumber means it has not been computed yet — see
574 * prism_posting_insert_one, which fills it lazily on the first insert.
575 */
576 static inline uint32_t
577 804 prism_posting_head_live_count(Page head)
578 {
579 804 return prism_posting_opaque(head)->live_count;
580 }
581
582 static inline BlockNumber
583 288 prism_posting_head_tail(Page head)
584 {
585 288 return prism_posting_opaque(head)->tail_blkno;
586 }
587
588 /* ----------------------------------------------------------------
589 * Content-based AoS access — header-agnostic
590 *
591 * Entries are laid out contiguously: entry i starts at
592 * content + i * PRISM_POSTING_ENTRY_SIZE(dim)
593 * and consists of an PrismPostingEntryHeader followed by
594 * VS_RABITQ_BYTES(dim) bytes of bits. The SIMD kernel strides
595 * through bits[] at stride = PRISM_POSTING_ENTRY_SIZE(dim), starting
596 * from prism_posting_first_bits(content).
597 * ---------------------------------------------------------------- */
598
599 /* Header for entry i (access fields via the struct: hdr->meta,
600 * hdr->f_add, hdr->f_rescale, hdr->f_error). */
601 static inline PrismPostingEntryHeader *
602 6602465 prism_posting_entry_at(char *content, uint32_t i, Dimension dim)
603 {
604 12882821 return (PrismPostingEntryHeader *)(content +
605 6602465 (size_t)i *
606
4/4
✓ Branch 0 taken 73870 times.
✓ Branch 1 taken 80444 times.
✓ Branch 2 taken 82561 times.
✓ Branch 3 taken 10017 times.
6602465 PRISM_POSTING_ENTRY_SIZE(dim));
607 }
608
609 /* Bits pointer for entry i (immediately follows entry i's header). */
610 static inline uint8_t *
611 2 prism_posting_entry_bits_at(
612 char *content, uint32_t max_entries, Dimension dim, uint32_t i)
613 {
614 (void)max_entries;
615 2 return prism_posting_entry_at(content, i, dim)->bits;
616 }
617
618 /* Pointer to entry 0's bits — the base the SIMD kernel uses, with
619 * stride = PRISM_POSTING_ENTRY_SIZE(dim). */
620 static inline uint8_t *
621 41433 prism_posting_first_bits(char *content)
622 {
623 41433 return ((PrismPostingEntryHeader *)content)->bits;
624 }
625
626 /* ----------------------------------------------------------------
627 * Paged-mode convenience wrappers
628 *
629 * These use PageGetContents for the content pointer and read
630 * max_entries from the opaque. Used by page init/add and tests.
631 * ---------------------------------------------------------------- */
632
633 static inline char *
634 401184 prism_posting_content(Page page)
635 {
636 401184 return PageGetContents(page);
637 }
638
639 /*
640 * On an inline first page, P^T * centroid is stored right after PageHeader,
641 * before the entries. On a spilled list's head pages it is that page's
642 * floats of the reference; prism_posting_reference_read gathers the whole
643 * vector.
644 */
645 static inline const float *
646 13853330 prism_posting_pt_centroid(Page page)
647 {
648 13853330 return (const float *)PageGetContents(page);
649 }
650
651 static inline float *
652 13832 prism_posting_pt_centroid_mut(Page page)
653 {
654 13832 return (float *)PageGetContents(page);
655 }
656
657 /*
658 * Gather a posting list's encode reference, inline or spilled, into `out`
659 * (dim floats). Reads the head pages one at a time, releasing each before
660 * the next (the PG storage pins a single buffer). Returns the first page
661 * that holds entries: the START page for an inline layout, the END page for
662 * a spilled one. Errors out on a chain that is not what the layout says it
663 * must be.
664 */
665 BlockNumber prism_posting_reference_read(
666 VsStorage *storage, BlockNumber head, Dimension dim, float *out);
667
668 /*
669 * prism_posting_reference_read without the floats on the head's END page:
670 * returns that page, for a caller that reads it for its entries anyway and
671 * takes the floats from it with prism_posting_reference_read_end. Sets
672 * *cluster_id to the list's. For an inline layout this is the whole gather.
673 */
674 BlockNumber prism_posting_reference_read_to_end(
675 VsStorage *storage,
676 BlockNumber head,
677 Dimension dim,
678 float *out,
679 uint32_t *cluster_id);
680
681 /*
682 * Check that `page`, at blk, is the head END page of the list at head
683 * with cluster_id, and copy its floats of the reference into out.
684 */
685 void prism_posting_reference_read_end(
686 BlockNumber head,
687 BlockNumber blk,
688 Page page,
689 uint32_t cluster_id,
690 Dimension dim,
691 float *out);
692
693 /*
694 * The same gather for a caller that already copied the START page's floats
695 * while it had the head pinned: continues at `next`, the head's next_blkno,
696 * with head page 1. Inline layouts have nothing left to read and get `next`
697 * back unchanged.
698 */
699 BlockNumber prism_posting_reference_read_rest(
700 VsStorage *storage,
701 BlockNumber head,
702 BlockNumber next,
703 uint32_t cluster_id,
704 Dimension dim,
705 float *out);
706
707 /*
708 * Lay out head page i of a spilled list in `page`: init it as the head's
709 * START page for i = 0, its END page for the last, else a MIDDLE page, plus
710 * `extra_flags`, and copy its floats of `ref`. An END page starts with no
711 * entries. next_blkno is left Invalid for the caller to link.
712 */
713 void prism_posting_reference_page_fill(
714 Page page,
715 uint32_t cluster_id,
716 Dimension dim,
717 uint32_t i,
718 const float *ref,
719 uint16_t extra_flags);
720
721 /* ----------------------------------------------------------------
722 * Chain walks
723 *
724 * A posting list is a chain of pages linked by next_blkno. Every caller
725 * that traverses one has to read the link before releasing the page and
726 * release it before moving on; these keep that order in one place.
727 *
728 * The scan path deliberately does not use them. It holds a page across the
729 * SIMD kernels that consume it, interleaves the next page's prefetch, and
730 * handles flat mode (a single page, no chain) and page_base mode (memory it
731 * does not release) -- so its stepping is a different shape, not a
732 * duplicate of this one.
733 * ---------------------------------------------------------------- */
734
735 /*
736 * Where a read walk currently is. The callback may release the page early
737 * and keep working: the next block is already read, so the walk does not
738 * need it afterwards. That matters for work which must not hold a page --
739 * fetching heap tuples through the same storage, which holds one page at a
740 * time and would take over the slot.
741 */
742 typedef struct PrismPostingChainPos
743 {
744 VsStorage *storage;
745 BlockNumber blkno;
746 Page page; /* NULL once released */
747 BlockNumber next; /* read before the callback runs */
748 bool first;
749 } PrismPostingChainPos;
750
751 static inline void
752 8105 prism_posting_chain_release(PrismPostingChainPos *pos)
753 {
754
2/2
✓ Branch 0 taken 7090 times.
✓ Branch 1 taken 1015 times.
8105 if (pos->page != NULL)
755 {
756 7090 vs_storage_release_page(pos->storage, pos->blkno);
757 7090 pos->page = NULL;
758 }
759 8105 }
760
761 /* Return false to stop the walk. */
762 typedef bool (*PrismPostingChainCb)(PrismPostingChainPos *pos, void *state);
763
764 void prism_posting_chain_walk(
765 VsStorage *storage,
766 BlockNumber head,
767 PrismPostingChainCb cb,
768 void *state);
769
770 /*
771 * Mutating walk: the callback gets the opaque of a page held for write, and
772 * every page is committed. For chain-wide flag changes, where the body is a
773 * line or two and the walk is all of the code.
774 */
775 typedef void (*PrismPostingChainMutateCb)(
776 PrismPostingPageOpaque *op, void *state);
777
778 void prism_posting_chain_mutate(
779 VsStorage *storage,
780 BlockNumber head,
781 PrismPostingChainMutateCb cb,
782 void *state);
783
784 /*
785 * Entry content of any posting page: past the reference prefix on an inline
786 * START page or an END page, else the start of the page. A page that holds
787 * only reference has no entries, so its content is the (empty) start of the
788 * page.
789 */
790 static inline char *
791 401184 prism_posting_page_content(Page page, Dimension dim)
792 {
793 401184 uint16_t flags = prism_posting_opaque(page)->flags;
794
2/2
✓ Branch 0 taken 91713 times.
✓ Branch 1 taken 27382 times.
401184 char *start = prism_posting_content(page);
795
796 401184 return prism_posting_has_ref_prefix(flags, dim)
797 273714 ? start + prism_posting_ref_prefix_size(dim)
798
2/2
✓ Branch 0 taken 273714 times.
✓ Branch 1 taken 127470 times.
583185 : start;
799 }
800
801 /* Paged-mode convenience wrappers — these assume pages with no reference
802 * prefix (content starts right after PageHeader). For the others, go
803 * through prism_posting_page_content. */
804 static inline PrismPostingEntryHeader *
805 2 prism_posting_entry(Page page, uint32_t i, Dimension dim)
806 {
807 2 return prism_posting_entry_at(PageGetContents(page), i, dim);
808 }
809
810 static inline uint8_t *
811 2 prism_posting_entry_bits(
812 Page page, uint32_t max_entries, Dimension dim, uint32_t i)
813 {
814 2 return prism_posting_entry_bits_at(
815 PageGetContents(page), max_entries, dim, i);
816 }
817
818 /* ----------------------------------------------------------------
819 * Flat-mode access
820 * ---------------------------------------------------------------- */
821
822 static inline PrismFlatPostingHeader *
823 13130 prism_flat_posting_header(char *buf)
824 {
825 13130 return (PrismFlatPostingHeader *)buf;
826 }
827
828 static inline char *
829 12942 prism_flat_posting_content(char *buf)
830 {
831
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
12942 return buf + sizeof(PrismFlatPostingHeader);
832 }
833
834 /* ----------------------------------------------------------------
835 * Standalone helper: pack/extract vector_id in ItemPointerData
836 * ---------------------------------------------------------------- */
837
838 static inline void
839 37664 prism_posting_set_vector_id(ItemPointerData *tid, uint32_t vector_id)
840 {
841 37664 ItemPointerSet(tid, (BlockNumber)vector_id, 0);
842 37664 }
843
844 static inline uint32_t
845 159470 prism_posting_get_vector_id(const ItemPointerData *tid)
846 {
847 159470 return (uint32_t)ItemPointerGetBlockNumber(tid);
848 }
849
850 /* ----------------------------------------------------------------
851 * TID ↔ uint64_t encoding for VsTopK
852 *
853 * Both standalone and PG store TIDs in VsTopK's uint64_t id field.
854 * For standalone: vector_id is packed in BlockNumber with offset=0,
855 * so encode yields (vector_id << 16) and decode_vector_id shifts
856 * back. For PG: full ItemPointerData (block + offset) fits in 48
857 * bits of the uint64_t.
858 * ---------------------------------------------------------------- */
859
860 static inline uint64_t
861 777094 prism_posting_encode_tid(const ItemPointerData *tid)
862 {
863 777094 return ((uint64_t)ItemPointerGetBlockNumber(tid) << 16) |
864 777094 (uint64_t)ItemPointerGetOffsetNumber(tid);
865 }
866
867 static inline ItemPointerData
868 41921 prism_posting_decode_tid(uint64_t id)
869 {
870 41921 ItemPointerData tid;
871 41921 ItemPointerSet(&tid, (BlockNumber)(id >> 16), (OffsetNumber)(id & 0xFFFF));
872 41921 return tid;
873 }
874
875 /* Convenience for standalone: extract vector_id from encoded TID.
876 * Works because prism_posting_set_vector_id stores vid in BlockNumber
877 * with offset=0, so (id >> 16) == vid. */
878 static inline uint32_t
879 148417 prism_posting_decode_vector_id(uint64_t id)
880 {
881 148417 return (uint32_t)(id >> 16);
882 }
883
884 /* ----------------------------------------------------------------
885 * Paged-mode page operations
886 * ---------------------------------------------------------------- */
887
888 /*
889 * Initialize an empty BLCKSZ posting page.
890 */
891 void prism_posting_page_init(
892 Page page, uint32_t cluster_id, Dimension dim, uint16_t flags);
893
894 /*
895 * Add one entry to a BLCKSZ page. Returns false if page is full.
896 */
897 bool prism_posting_page_add(
898 Page page,
899 Dimension dim,
900 ItemPointerData tid,
901 float f_add,
902 float f_rescale,
903 float f_error,
904 const uint8_t *bits,
905 uint8_t entry_flags);
906
907 /* ----------------------------------------------------------------
908 * Flat-mode page operations
909 * ---------------------------------------------------------------- */
910
911 /*
912 * Initialize a flat posting page buffer. buf must be at least
913 * prism_posting_flat_page_size(dim, max_entries) bytes.
914 */
915 void
916 prism_posting_flat_init(char *buf, uint32_t max_entries, uint32_t cluster_id);
917
918 /*
919 * Add one entry to a flat page. Returns false if full.
920 */
921 bool prism_posting_flat_add(
922 char *buf,
923 Dimension dim,
924 ItemPointerData tid,
925 float f_add,
926 float f_rescale,
927 float f_error,
928 const uint8_t *bits,
929 uint8_t entry_flags);
930
931 /* ----------------------------------------------------------------
932 * Fastscan page format
933 *
934 * Fastscan scores 32 vectors at once with in-register table lookups on
935 * their 1-bit codes, which is much faster than scoring AoS entries one at a
936 * time. A fastscan list stores its vectors in 32-vector groups. Each group
937 * has codes, VS_FASTSCAN_GROUP_BYTES(dim) bytes interleaved for the kernel,
938 * and 580 bytes of group metadata:
939 * ItemPointerData tids[32] 192B
940 * float f_add[32] 128B
941 * float f_rescale[32] 128B
942 * float f_error[32] 128B
943 * uint32_t tombstone_mask 4B (bit v set => lane v is dead)
944 *
945 * Page content (after the reference prefix on a list's first entry page):
946 * group metadata[ngroups] ngroups × 580B
947 * codes[code_bytes] the page's run of the code stream
948 *
949 * A spilled list's stream starts on its head's END page, after the rest of
950 * the reference.
951 *
952 * The codes of all groups form one stream that continues from page to page.
953 * A group's codes can break at any PRISM_FASTSCAN_CHUNK_BYTES (64-byte)
954 * boundary, so a page wastes less than 64 bytes instead of the gap a whole
955 * group does not fit. Every kernel steps in sizes that divide 64 bytes, so
956 * the scan scores a split group in place, one page at a time.
957 *
958 * Group metadata never splits. It goes on the page where its group's codes
959 * end, because that is where the scan has the complete sums to prune with,
960 * and the scan holds one page at a time. When it does not fit there, it is
961 * deferred to the start of the next page and the next group's codes use the
962 * space.
963 *
964 * Metadata comes first on the page so readers that need only metadata
965 * (deleted-vector marking, split, inspect) find group g's at a fixed offset,
966 * without knowing where groups start in the code stream.
967 *
968 * In the opaque, entry_count counts the vectors whose metadata is on the
969 * page and code_bytes is the length of its code run. Only the list's last
970 * group can be partial, so a page holds ceil(entry_count / 32) groups'
971 * metadata. A page's position in the stream is not stored: the scan reads a
972 * list from its head and carries the position from page to page.
973 *
974 * tombstone_mask is the per-lane analog of an AoS entry's
975 * PRISM_POSTING_FLAG_DELETED (see fastscan-design.md for why the codes
976 * can't be marked in place). The builder writes it as zero.
977 *
978 * Pages are identified by PRISM_POSTING_PAGE_FASTSCAN in opaque flags.
979 * ---------------------------------------------------------------- */
980
981 #include "quant/fastscan.h"
982
983 static_assert(
984 VS_FASTSCAN_GROUP == 32,
985 "tombstone_mask packs one bit per lane into a uint32_t");
986
987 /*
988 * Code bytes per split unit: 16 dimensions of 32 vectors. The widest kernel
989 * step (AVX-512, 64 bytes) and the 16-bit lookup table's 128-byte block of
990 * two columns both line up with it, so a kernel call can start at any chunk.
991 */
992 #define PRISM_FASTSCAN_CHUNK_BYTES 64u
993
994 /*
995 * Most groups a scan can have in flight, meaning it has started summing
996 * their codes but not yet reached their metadata. That is the group whose
997 * codes it is reading plus up to two whose metadata was deferred to the next
998 * page. The scan keeps running sums for each, so the bound keeps its state
999 * fixed. Two deferred groups are enough to fill the space deferred metadata
1000 * leaves with codes at every dimension above about 72.
1001 */
1002 #define PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS 3u
1003
1004 /* Bytes of one group's metadata. */
1005 #define PRISM_FASTSCAN_META_BYTES \
1006 ((uint32_t)(VS_FASTSCAN_GROUP * sizeof(ItemPointerData) + \
1007 VS_FASTSCAN_GROUP * 3 * sizeof(float) + sizeof(uint32_t)))
1008
1009 static_assert(
1010 PRISM_FASTSCAN_META_BYTES % sizeof(float) == 0,
1011 "group metadata keeps the floats of the next group's aligned");
1012
1013 /* Bytes per 32-vector group, metadata and codes together */
1014 static inline uint32_t
1015 497 prism_fastscan_group_section_bytes(Dimension dim)
1016 {
1017 497 return PRISM_FASTSCAN_META_BYTES + VS_FASTSCAN_GROUP_BYTES(dim);
1018 }
1019
1020 /*
1021 * Bytes for metadata and codes on a fastscan page, after the reference
1022 * prefix when the page is a list's first entry page (ref_prefix).
1023 */
1024 static inline uint32_t
1025 58153 prism_fastscan_page_space(Dimension dim, bool ref_prefix)
1026 {
1027 58650 uint32_t usable = prism_posting_page_usable();
1028
1029
2/2
✓ Branch 0 taken 34536 times.
✓ Branch 1 taken 17978 times.
56354 return ref_prefix ? usable - prism_posting_ref_prefix_size(dim) : usable;
1030 }
1031
1032 /* Groups with metadata on a fastscan page, from its vector count. */
1033 static inline uint32_t
1034 42865 prism_fastscan_page_groups(const PrismPostingPageOpaque *op)
1035 {
1036
2/2
✓ Branch 0 taken 12709 times.
✓ Branch 1 taken 9108 times.
42865 return ((uint32_t)op->entry_count + VS_FASTSCAN_GROUP - 1) /
1037 VS_FASTSCAN_GROUP;
1038 }
1039
1040 /*
1041 * The max number of groups' metadata a page can hold. Besides the metadata
1042 * deferred from the previous page, a page holds metadata only for groups
1043 * whose codes end on it, and its code bytes reach the end of at most
1044 * space / group-code-size + 1 groups.
1045 */
1046 static inline uint32_t
1047 15088 prism_fastscan_max_groups(Dimension dim, bool ref_prefix)
1048 {
1049
2/2
✓ Branch 0 taken 3840 times.
✓ Branch 1 taken 1446 times.
15088 uint32_t space = prism_fastscan_page_space(dim, ref_prefix);
1050 15088 uint32_t deferred = PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS - 1;
1051 15088 uint32_t by_meta = space / PRISM_FASTSCAN_META_BYTES;
1052 15088 uint32_t by_code = deferred + 1 + space / VS_FASTSCAN_GROUP_BYTES(dim);
1053
1054 15088 return by_meta < by_code ? by_meta : by_code;
1055 }
1056
1057 /* Max entries on a fastscan page with no reference prefix */
1058 static inline uint32_t
1059 10666 prism_fastscan_max_entries(Dimension dim)
1060 {
1061 10666 return prism_fastscan_max_groups(dim, false) * VS_FASTSCAN_GROUP;
1062 }
1063
1064 /* Max entries on a list's first fastscan entry page, after the prefix */
1065 static inline uint32_t
1066 4088 prism_fastscan_max_entries_first(Dimension dim)
1067 {
1068 4088 return prism_fastscan_max_groups(dim, true) * VS_FASTSCAN_GROUP;
1069 }
1070
1071 /*
1072 * Entries a full page holds on average, for cost estimates. Fastscan pages
1073 * waste under a chunk each, so the code and metadata bytes per vector set
1074 * the density.
1075 */
1076 static inline double
1077 497 prism_fastscan_entries_per_page(Dimension dim)
1078 {
1079 497 return (double)prism_fastscan_page_space(dim, false) * VS_FASTSCAN_GROUP /
1080 497 prism_fastscan_group_section_bytes(dim);
1081 }
1082
1083 /*
1084 * Upper bound on the entries a single posting page can hold, whatever format
1085 * it is in. Neither format's figure bounds the other: fastscan packs more
1086 * than AoS at low dimension and allows for deferred group metadata, while
1087 * AoS packs more where a page holds under one group's codes. The figures
1088 * for a page without a reference prefix bound the others too. Callers sizing a
1089 * buffer for one page's worth of entries want this rather than either half.
1090 */
1091 static inline uint32_t
1092 4407 prism_posting_max_entries_any_format(Dimension dim)
1093 {
1094 4407 uint32_t aos = prism_posting_max_entries(dim);
1095 4407 uint32_t fs = prism_fastscan_max_entries(dim);
1096 4407 return aos > fs ? aos : fs;
1097 }
1098
1099 /* Entries a full page holds in the denser of the two formats. */
1100 static inline double
1101 497 prism_posting_entries_per_page(Dimension dim)
1102 {
1103 497 double aos = (double)prism_posting_max_entries(dim);
1104 497 double fs = prism_fastscan_entries_per_page(dim);
1105 497 return aos > fs ? aos : fs;
1106 }
1107
1108 /*
1109 * The entry ceiling a page of this format and position really has. All four
1110 * combinations differ: a fastscan page packs more entries than an AoS one,
1111 * and a list's first entry page gives up room to the reference prefix.
1112 * Bounding an AoS page by the fastscan figure (or by the larger of the two)
1113 * would still let prism_posting_entry_at walk off the page.
1114 */
1115 static inline uint32_t
1116 61049 prism_posting_page_cap(const PrismPostingPageOpaque *op, Dimension dim)
1117 {
1118 61049 bool first = prism_posting_has_ref_prefix(op->flags, dim);
1119
1120
3/3
✓ Branch 0 taken 12312 times.
✓ Branch 1 taken 1098 times.
✓ Branch 2 taken 47639 times.
61049 if (prism_posting_is_reference_only_page(op->flags, dim))
1121 350 return 0;
1122
2/2
✓ Branch 0 taken 4895 times.
✓ Branch 1 taken 55056 times.
59951 if (op->flags & PRISM_POSTING_PAGE_FASTSCAN)
1123 3577 return first ? prism_fastscan_max_entries_first(dim)
1124
2/2
✓ Branch 0 taken 3577 times.
✓ Branch 1 taken 1318 times.
4985 : prism_fastscan_max_entries(dim);
1125
1126 42614 return first ? prism_posting_max_entries_first(dim)
1127
2/2
✓ Branch 0 taken 42614 times.
✓ Branch 1 taken 12442 times.
55056 : prism_posting_max_entries(dim);
1128 }
1129
1130 /*
1131 * Reject an on-disk entry_count past that ceiling before it drives a loop, so
1132 * a corrupt or truncated page cannot read past the page end. A fastscan page
1133 * also has its group metadata and code run checked to fit.
1134 */
1135 void prism_posting_check_count(BlockNumber blkno, Page page, Dimension dim);
1136
1137 /*
1138 * The fastscan half of prism_posting_check_count, against the entry ceiling
1139 * and content space of a page in this one's position. The scan passes bounds
1140 * it computed once, since it checks every page it reads.
1141 */
1142 void prism_fastscan_check_page(
1143 BlockNumber blkno,
1144 const PrismPostingPageOpaque *op,
1145 uint32_t cap,
1146 uint32_t space);
1147
1148 /* ----------------------------------------------------------------
1149 * Fastscan page accessors
1150 *
1151 * All take the content pointer (past PageHeader, past pt_centroid on first
1152 * pages). The group index g counts the groups with metadata on that page.
1153 * ---------------------------------------------------------------- */
1154
1155 static inline char *
1156 143672 prism_fastscan_group_base(char *content, uint32_t g)
1157 {
1158 143672 return content + (size_t)g * PRISM_FASTSCAN_META_BYTES;
1159 }
1160
1161 /* The page's run of the code stream, after the metadata of ngroups groups. */
1162 static inline uint8_t *
1163 39673 prism_fastscan_page_codes(char *content, uint32_t ngroups)
1164 {
1165
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9108 times.
39673 return (uint8_t *)content + (size_t)ngroups * PRISM_FASTSCAN_META_BYTES;
1166 }
1167
1168 static inline ItemPointerData *
1169 33420 prism_fastscan_group_tids(char *content, uint32_t g)
1170 {
1171
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
33744 return (ItemPointerData *)prism_fastscan_group_base(content, g);
1172 }
1173
1174 static inline float *
1175 102030 prism_fastscan_group_f_add(char *content, uint32_t g)
1176 {
1177
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
102929 return (float *)(prism_fastscan_group_base(content, g) +
1178 VS_FASTSCAN_GROUP * sizeof(ItemPointerData));
1179 }
1180
1181 static inline float *
1182 79836 prism_fastscan_group_f_rescale(char *content, uint32_t g)
1183 {
1184
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
80735 return prism_fastscan_group_f_add(content, g) + VS_FASTSCAN_GROUP;
1185 }
1186
1187 static inline float *
1188 57642 prism_fastscan_group_f_error(char *content, uint32_t g)
1189 {
1190
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
58541 return prism_fastscan_group_f_rescale(content, g) + VS_FASTSCAN_GROUP;
1191 }
1192
1193 /*
1194 * Per-group dead-lane bitmap: bit v set means lane v's TID is dead. Read and
1195 * write through this pointer directly (it aliases the live page); there is no
1196 * copy to write back. Only valid lanes (v < the group's entry count) are ever
1197 * set -- the builder writes the word as zero and nothing else touches it, so
1198 * an unmarked lane, including every lane past entry_count on a partial final
1199 * group, reads as live.
1200 */
1201 static inline uint32_t *
1202 36347 prism_fastscan_group_tombstone_mask(char *content, uint32_t g)
1203 {
1204
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
36347 return (uint32_t *)(prism_fastscan_group_f_error(content, g) +
1205 VS_FASTSCAN_GROUP);
1206 }
1207
1208 /*
1209 * Bit test and set for one lane of a tombstone_mask word already read out
1210 * of (or about to be written back into) a page via the accessor above.
1211 * Every reader and writer of the mask goes through these two rather than
1212 * writing out the bit math itself, so there is exactly one place that
1213 * says "lane v is bit 1u << v".
1214 */
1215 static inline bool
1216 160542 prism_fastscan_lane_is_tombstoned(uint32_t mask, uint32_t lane)
1217 {
1218
6/6
✓ Branch 0 taken 2160 times.
✓ Branch 1 taken 27447 times.
✓ Branch 2 taken 71 times.
✓ Branch 3 taken 73799 times.
✓ Branch 4 taken 30 times.
✓ Branch 5 taken 1399 times.
160542 return (mask & (1u << lane)) != 0;
1219 }
1220
1221 static inline uint32_t
1222 2147 prism_fastscan_lane_set_tombstone(uint32_t mask, uint32_t lane)
1223 {
1224 2147 return mask | (1u << lane);
1225 }
1226
1227 #endif /* PRISM_POSTING_PAGE_H */
1228