| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * index_base.h - Common index descriptor for search | ||
| 6 | * | ||
| 7 | * PrismIndexBase contains the fields needed by the shared search | ||
| 8 | * path. Standalone embeds it in PrismIndex; PG populates it from | ||
| 9 | * the meta page and amcache. | ||
| 10 | */ | ||
| 11 | |||
| 12 | #ifndef PRISM_INDEX_BASE_H | ||
| 13 | #define PRISM_INDEX_BASE_H | ||
| 14 | |||
| 15 | #include "core/types.h" | ||
| 16 | #include "index/centroid_page.h" | ||
| 17 | #include "index/posting_page.h" | ||
| 18 | #include "index/storage.h" | ||
| 19 | #include "quant/rabitq.h" | ||
| 20 | |||
| 21 | /* | ||
| 22 | * Block 0 holds the metapage. Up to PRISM_GLOBAL_MEAN_MAX_INLINE_DIM | ||
| 23 | * dimensions the full-precision global mean vector fits in the metapage's | ||
| 24 | * special area. For higher dimensions, the global mean spills into the | ||
| 25 | * pages immediately following the metapage. Similarly, the reference vector | ||
| 26 | * of each posting list spills from its head into the pages chained after it | ||
| 27 | * (all flagged REFERENCE). The centroid region starts after the spilled | ||
| 28 | * mean. Shared here so the standalone build reserves the same blocks. | ||
| 29 | */ | ||
| 30 | #define PRISM_META_PAGE_BLKNO 0 | ||
| 31 | #define PRISM_META_PAGE_PAGES 1 | ||
| 32 | #define PRISM_GLOBAL_MEAN_MAX_INLINE_DIM 2032 | ||
| 33 | /* cluster_id stamped on the spilled mean's head pages */ | ||
| 34 | #define PRISM_GLOBAL_MEAN_CLUSTER UINT32_MAX | ||
| 35 | |||
| 36 | /* First block of a spilled global mean. */ | ||
| 37 | #define PRISM_GLOBAL_MEAN_BLKNO (PRISM_META_PAGE_BLKNO + PRISM_META_PAGE_PAGES) | ||
| 38 | |||
| 39 | static inline uint32_t | ||
| 40 | 2472 | prism_global_mean_pages(Dimension dim) | |
| 41 | { | ||
| 42 |
6/6✓ Branch 0 taken 688 times.
✓ Branch 1 taken 119 times.
✓ Branch 2 taken 272 times.
✓ Branch 3 taken 305 times.
✓ Branch 4 taken 30 times.
✓ Branch 5 taken 219 times.
|
2223 | if (dim <= PRISM_GLOBAL_MEAN_MAX_INLINE_DIM) |
| 43 | 194 | return 0; | |
| 44 | 225 | return ((uint32_t)dim + PRISM_POSTING_REFERENCE_PAGE_FLOATS - 1) / | |
| 45 | PRISM_POSTING_REFERENCE_PAGE_FLOATS; | ||
| 46 | } | ||
| 47 | |||
| 48 | static inline BlockNumber | ||
| 49 | 1069 | prism_first_centroid_blkno(Dimension dim) | |
| 50 | { | ||
| 51 |
6/6✓ Branch 0 taken 2 times.
✓ Branch 1 taken 89 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 71 times.
✓ Branch 5 taken 29 times.
✓ Branch 6 taken 175 times.
|
1644 | return PRISM_GLOBAL_MEAN_BLKNO + prism_global_mean_pages(dim); |
| 52 | } | ||
| 53 | |||
| 54 | /* | ||
| 55 | * Posting pages the scan cost estimate prices, and what prism_index_settings | ||
| 56 | * reports as posting_pages. | ||
| 57 | * | ||
| 58 | * Block 0 is the metapage and the centroid region a build reserves starts at | ||
| 59 | * prism_first_centroid_blkno, so on a freshly built index the posting pages | ||
| 60 | * are everything from first_posting onward. That range stops measuring them | ||
| 61 | * once a split overflows a level-0 centroid page: the split extends the | ||
| 62 | * relation and chains the new centroid page past the posting region, so the | ||
| 63 | * page is both counted by ncentroid_pages and, to a range measurement, a | ||
| 64 | * posting page. Taking the maintained count out of the relation's size | ||
| 65 | * instead is layout-independent and leaves it in one term only. | ||
| 66 | * | ||
| 67 | * num_pages is the relation's current size, not pg_class.relpages: both | ||
| 68 | * callers read it straight from the relation, the planner included, so the | ||
| 69 | * count never lags a statistics update. | ||
| 70 | * | ||
| 71 | * An upper bound rather than an exact count: free and new pages from | ||
| 72 | * extension slack are included, the same over-count the estimate already | ||
| 73 | * documents for a bloated index. | ||
| 74 | */ | ||
| 75 | static inline double | ||
| 76 | 552 | prism_index_posting_pages( | |
| 77 | double num_pages, Dimension dim, double ncentroid_pages) | ||
| 78 | { | ||
| 79 |
2/2✓ Branch 0 taken 75 times.
✓ Branch 1 taken 469 times.
|
552 | double n = num_pages - (double)prism_first_centroid_blkno(dim) - |
| 80 | ncentroid_pages; | ||
| 81 | |||
| 82 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 546 times.
|
552 | return n < 1.0 ? 1.0 : n; |
| 83 | } | ||
| 84 | |||
| 85 | typedef struct PrismIndexBase | ||
| 86 | { | ||
| 87 | /* RaBitQ (must outlive the search context) */ | ||
| 88 | RaBitQParams *params; | ||
| 89 | float *pt_global_mean; | ||
| 90 | uint64_t rabitq_seed; | ||
| 91 | |||
| 92 | /* PG: both point to the same VsPgStorage (one index relation). | ||
| 93 | * Standalone: separate ArrayPageStorage for centroids vs postings. */ | ||
| 94 | VsStorage *centroid_storage; | ||
| 95 | VsStorage *posting_storage; | ||
| 96 | |||
| 97 | /* Non-NULL for inline page access (standalone postings) */ | ||
| 98 | char *page_base; | ||
| 99 | |||
| 100 | /* Index metadata */ | ||
| 101 | Dimension dim; | ||
| 102 | uint8_t nlevels; | ||
| 103 | /* Children per tree node; floors the intermediate beam width so the | ||
| 104 | * top-nprobe leaves stay reachable (0 = unknown, no floor). */ | ||
| 105 | uint8_t fan_out; | ||
| 106 | /* Leaf (posting-list) count; when nprobe covers every leaf the | ||
| 107 | * intermediate beam keeps whole levels so no subtree is pruned | ||
| 108 | * (0 = unknown, no full-coverage floor). */ | ||
| 109 | uint32_t nlist; | ||
| 110 | /* | ||
| 111 | * Root of the centroid tree, which every descent starts from -- NOT the | ||
| 112 | * first block of the centroid region, despite the name. Where the root | ||
| 113 | * sits inside the region depends on the build: a serial build writes the | ||
| 114 | * centroid pages post-order and the root lands last, a parallel one | ||
| 115 | * places it first. The region itself is always | ||
| 116 | * [prism_first_centroid_blkno(dim), first_posting). | ||
| 117 | */ | ||
| 118 | BlockNumber first_centroid; | ||
| 119 | /* | ||
| 120 | * First block of the posting-head region; leaf c's head is | ||
| 121 | * prism_leaf_head_blkno(first_posting, c, stride). Fixed for the life of | ||
| 122 | * the index, since that formula is how every head is located, so | ||
| 123 | * nothing can be inserted below it. | ||
| 124 | */ | ||
| 125 | BlockNumber first_posting; | ||
| 126 | /* | ||
| 127 | * Centroid pages reachable from first_centroid. Maintained rather than | ||
| 128 | * derived, because a split with no room on a level-0 page extends the | ||
| 129 | * relation and chains the new page past first_posting, after which the | ||
| 130 | * reserved block range no longer measures the count. | ||
| 131 | */ | ||
| 132 | uint32_t ncentroid_pages; | ||
| 133 | DistanceMetric metric; | ||
| 134 | PrismCentroidFormat centroid_format; | ||
| 135 | int fastscan; /* 0=off, 8=uint8, 16=uint16 hacc */ | ||
| 136 | float centroid_error_scale; /* scales centroid pruning error (1=default) */ | ||
| 137 | float centroid_beam_scale; /* intermediate beam width / nprobe | ||
| 138 | (0.25=default) */ | ||
| 139 | /* Build-only: exact internal-node centroids for the build descent | ||
| 140 | * (see PrismExactInternalCentroids in centroid_search.h). NULL — the | ||
| 141 | * default everywhere the base is zero-initialized — keeps the | ||
| 142 | * estimated scoring; the query and insert paths never set it. */ | ||
| 143 | const struct PrismExactInternalCentroids *exact_internal; | ||
| 144 | } PrismIndexBase; | ||
| 145 | |||
| 146 | static inline RaBitQParams * | ||
| 147 | 20955 | prism_index_ensure_rabitq(PrismIndexBase *idx) | |
| 148 | { | ||
| 149 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 20955 times.
|
20955 | if (idx->params == NULL) |
| 150 | { | ||
| 151 | ✗ | idx->params = vs_rabitq_create(idx->dim, idx->rabitq_seed); | |
| 152 | ✗ | if (idx->pt_global_mean != NULL) | |
| 153 | ✗ | vs_rabitq_rotate( | |
| 154 | ✗ | idx->params, idx->pt_global_mean, idx->pt_global_mean); | |
| 155 | } | ||
| 156 | 20955 | return idx->params; | |
| 157 | } | ||
| 158 | |||
| 159 | #endif /* PRISM_INDEX_BASE_H */ | ||
| 160 |