| 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_scan.c - Posting list scan with fused cluster function | ||
| 6 | * | ||
| 7 | * Scans posting data (paged or flat), computes batch RaBitQ | ||
| 8 | * distances, prunes via error bounds, and reranks survivors | ||
| 9 | * in a single function call per cluster. | ||
| 10 | * | ||
| 11 | * Optimizations: | ||
| 12 | * - Inline page access via stored base pointer (no vtable dispatch) | ||
| 13 | * - Score + prune + rerank fused into one function (no iterator | ||
| 14 | * overhead, compiler can optimize across all phases) | ||
| 15 | */ | ||
| 16 | |||
| 17 | #include "vs_config.h" | ||
| 18 | |||
| 19 | #include <string.h> | ||
| 20 | |||
| 21 | #include "core/log.h" | ||
| 22 | #include "core/memory.h" | ||
| 23 | #include "index/posting_scan.h" | ||
| 24 | #include "quant/fastscan.h" | ||
| 25 | |||
| 26 | #ifdef VS_SIMD_FULL | ||
| 27 | #if defined(__x86_64__) || defined(_M_X64) | ||
| 28 | #include <immintrin.h> | ||
| 29 | |||
| 30 | #include "algo/simd_utils.h" | ||
| 31 | #endif | ||
| 32 | #endif | ||
| 33 | |||
| 34 | /* ---------------------------------------------------------------- | ||
| 35 | * Init / cleanup | ||
| 36 | * ---------------------------------------------------------------- */ | ||
| 37 | |||
| 38 | void | ||
| 39 | 21044 | prism_posting_scan_init( | |
| 40 | PrismPostingScan *scan, | ||
| 41 | VsStorage *storage, | ||
| 42 | char *page_base, | ||
| 43 | const RaBitQParams *params, | ||
| 44 | Dimension dim, | ||
| 45 | uint32_t max_entries_per_page) | ||
| 46 | { | ||
| 47 | 21044 | memset(scan, 0, sizeof(*scan)); | |
| 48 | 21044 | scan->storage = storage; | |
| 49 | 21044 | scan->page_base = page_base; | |
| 50 | 21044 | scan->params = params; | |
| 51 | 21044 | scan->dim = dim; | |
| 52 | 21044 | scan->packed_bytes = VS_RABITQ_BYTES(dim); | |
| 53 | 21044 | scan->cur_blkno = InvalidBlockNumber; | |
| 54 | |||
| 55 | /* Pre-allocate batch buffers. max_entries_cap is the trusted per-page | ||
| 56 | * capacity these buffers are sized for; a page whose on-disk | ||
| 57 | * entry_count exceeds it (corruption) would overrun | ||
| 58 | * page_distances/page_scratch and is rejected on load. */ | ||
| 59 | 21044 | scan->max_entries_cap = max_entries_per_page; | |
| 60 | 21044 | scan->page_distances = vs_alloc(max_entries_per_page * sizeof(Distance)); | |
| 61 | 21044 | scan->page_scratch = vs_alloc(max_entries_per_page * sizeof(float)); | |
| 62 | |||
| 63 |
3/3✓ Branch 0 taken 2573 times.
✓ Branch 1 taken 18133 times.
✓ Branch 2 taken 338 times.
|
21044 | if (prism_posting_spilled(dim)) |
| 64 | 2677 | scan->pt_ref = vs_alloc((size_t)dim * sizeof(float)); | |
| 65 | 21044 | } | |
| 66 | |||
| 67 | void | ||
| 68 | 21042 | prism_posting_scan_cleanup(PrismPostingScan *scan) | |
| 69 | { | ||
| 70 | /* Release pinned page if still held */ | ||
| 71 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 21042 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
21042 | if (scan->cur_page != NULL && scan->storage != NULL && |
| 72 | ✗ | scan->page_base == NULL) | |
| 73 | { | ||
| 74 | ✗ | vs_storage_release_page(scan->storage, scan->cur_blkno); | |
| 75 | ✗ | scan->cur_page = NULL; | |
| 76 | } | ||
| 77 | |||
| 78 | 21042 | vs_free(scan->page_distances); | |
| 79 | 21042 | vs_free(scan->page_scratch); | |
| 80 | 21042 | scan->page_distances = NULL; | |
| 81 | 21042 | scan->page_scratch = NULL; | |
| 82 |
2/2✓ Branch 0 taken 2677 times.
✓ Branch 1 taken 18365 times.
|
21042 | if (scan->pt_ref != NULL) |
| 83 | { | ||
| 84 | 2677 | vs_free(scan->pt_ref); | |
| 85 | 2677 | scan->pt_ref = NULL; | |
| 86 | } | ||
| 87 | |||
| 88 |
2/2✓ Branch 0 taken 509 times.
✓ Branch 1 taken 20533 times.
|
21042 | if (scan->fs_lut != NULL) |
| 89 | { | ||
| 90 | 509 | vs_free(scan->fs_lut); | |
| 91 | 509 | scan->fs_lut = NULL; | |
| 92 | } | ||
| 93 |
2/2✓ Branch 0 taken 509 times.
✓ Branch 1 taken 20533 times.
|
21042 | if (scan->fs_accum != NULL) |
| 94 | { | ||
| 95 | 509 | vs_free(scan->fs_accum); | |
| 96 | 509 | scan->fs_accum = NULL; | |
| 97 | } | ||
| 98 | 21042 | } | |
| 99 | |||
| 100 | void | ||
| 101 | 511 | prism_posting_scan_enable_fastscan(PrismPostingScan *scan, int lut_bits) | |
| 102 | { | ||
| 103 | 511 | scan->fs_lut_bits = lut_bits; | |
| 104 |
2/2✓ Branch 0 taken 60 times.
✓ Branch 1 taken 451 times.
|
511 | if (lut_bits == 8) |
| 105 | 60 | scan->fs_lut = vs_alloc0(VS_FASTSCAN_LUT_BYTES(scan->dim)); | |
| 106 | else | ||
| 107 | 451 | scan->fs_lut = vs_alloc0(VS_FASTSCAN_LUT_HACC_BYTES(scan->dim)); | |
| 108 | /* A group's codes can span pages, and its metadata can be deferred past | ||
| 109 | * the start of the next group's codes, so the scan sums several groups at | ||
| 110 | * once. Each group in flight gets its own 32 running sums. */ | ||
| 111 | 511 | scan->fs_accum = vs_alloc( | |
| 112 | PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS * VS_FASTSCAN_GROUP * | ||
| 113 | sizeof(int32_t)); | ||
| 114 | |||
| 115 | /* Resolve dispatch once per scan (see posting_scan.h). */ | ||
| 116 | 511 | scan->fs_accum_hacc = vs_fastscan_get_accumulate_hacc(); | |
| 117 | #if defined(VS_SIMD_FULL) && (defined(__x86_64__) || defined(_M_X64)) | ||
| 118 | 511 | scan->fs_has_avx512 = vs_has_all_simd(VS_SIMD_AVX512_BW); | |
| 119 | #else | ||
| 120 | scan->fs_has_avx512 = false; | ||
| 121 | #endif | ||
| 122 | 511 | scan->fs_cap_first = prism_fastscan_max_entries_first(scan->dim); | |
| 123 | 511 | scan->fs_cap_over = prism_fastscan_max_entries(scan->dim); | |
| 124 | 511 | scan->fs_space_first = prism_fastscan_page_space(scan->dim, true); | |
| 125 | 511 | scan->fs_space_over = prism_fastscan_page_space(scan->dim, false); | |
| 126 | 511 | } | |
| 127 | |||
| 128 | static bool advance_page(PrismPostingScan *scan); | ||
| 129 | |||
| 130 | /* | ||
| 131 | * Check a fastscan page against the bounds cached at enable_fastscan. The | ||
| 132 | * page's place in the stream is checked as it is scanned. | ||
| 133 | */ | ||
| 134 | static void | ||
| 135 | 20256 | fastscan_check_page( | |
| 136 | const PrismPostingScan *scan, const PrismPostingPageOpaque *opaque) | ||
| 137 | { | ||
| 138 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 20256 times.
|
20256 | if (scan->fs_lut == NULL) |
| 139 | { | ||
| 140 | ✗ | prism_posting_check_count(scan->cur_blkno, scan->cur_page, scan->dim); | |
| 141 | ✗ | return; | |
| 142 | } | ||
| 143 | |||
| 144 | 20256 | bool first = prism_posting_has_ref_prefix(opaque->flags, scan->dim); | |
| 145 | |||
| 146 |
4/4✓ Branch 0 taken 11576 times.
✓ Branch 1 taken 8680 times.
✓ Branch 2 taken 2078 times.
✓ Branch 3 taken 7954 times.
|
20256 | prism_fastscan_check_page( |
| 147 | 20256 | scan->cur_blkno, | |
| 148 | opaque, | ||
| 149 | first ? scan->fs_cap_first : scan->fs_cap_over, | ||
| 150 | first ? scan->fs_space_first : scan->fs_space_over); | ||
| 151 | } | ||
| 152 | |||
| 153 | /* ---------------------------------------------------------------- | ||
| 154 | * Per-cluster begin / end | ||
| 155 | * ---------------------------------------------------------------- */ | ||
| 156 | |||
| 157 | /* | ||
| 158 | * Reset the per-cluster state and open the first entry page at `entries`. | ||
| 159 | * `ref_pages` reference pages were already read to gather `ref` (NULL when | ||
| 160 | * the reference is read from the inline head instead). | ||
| 161 | */ | ||
| 162 | static void | ||
| 163 | 50102 | begin_cluster( | |
| 164 | PrismPostingScan *scan, | ||
| 165 | RaBitQQueryState *qstate, | ||
| 166 | BlockNumber entries, | ||
| 167 | const float *ref, | ||
| 168 | uint32_t ref_pages) | ||
| 169 | { | ||
| 170 | 50102 | scan->qstate = qstate; | |
| 171 | 50102 | scan->cur_blkno = entries; | |
| 172 | 50102 | scan->cur_page = NULL; | |
| 173 | 50102 | scan->cur_content = NULL; | |
| 174 | 50102 | scan->cur_max_entries = 0; | |
| 175 | 50102 | scan->cur_count = 0; | |
| 176 | 50102 | scan->fs_lut_valid = false; | |
| 177 | 50102 | scan->fs_stream_pos = 0; | |
| 178 | 50102 | scan->fs_next_group = 0; | |
| 179 | 50102 | scan->pages_read = ref_pages; | |
| 180 | 50102 | scan->pages_skipped = 0; | |
| 181 | 50102 | scan->entries_scanned = 0; | |
| 182 | 50102 | scan->entries_pruned = 0; | |
| 183 | 50102 | scan->cur_ref = ref; | |
| 184 | |||
| 185 | /* Eagerly read the first page so an inline pt_centroid is accessible | ||
| 186 | * via prism_posting_pt_centroid(scan->cur_page) before _cluster is | ||
| 187 | * called. */ | ||
| 188 |
1/2✓ Branch 0 taken 50102 times.
✗ Branch 1 not taken.
|
50102 | if (entries != InvalidBlockNumber) |
| 189 | 50102 | advance_page(scan); | |
| 190 | 50102 | } | |
| 191 | |||
| 192 | void | ||
| 193 | 48110 | prism_posting_scan_begin_cluster( | |
| 194 | PrismPostingScan *scan, | ||
| 195 | RaBitQQueryState *qstate, | ||
| 196 | BlockNumber posting_head) | ||
| 197 | { | ||
| 198 | 48110 | BlockNumber entries = posting_head; | |
| 199 | 48110 | const float *ref = NULL; | |
| 200 | 48110 | uint32_t ref_pages = 0; | |
| 201 | 11006 | uint32_t cluster_id; | |
| 202 | |||
| 203 |
3/4✓ Branch 0 taken 3175 times.
✓ Branch 1 taken 44935 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3175 times.
|
48110 | if (scan->pt_ref == NULL || posting_head == InvalidBlockNumber) |
| 204 | { | ||
| 205 | 44935 | begin_cluster(scan, qstate, entries, ref, ref_pages); | |
| 206 | 44935 | return; | |
| 207 | } | ||
| 208 | |||
| 209 | /* Gather a spilled reference chain first, one page at a time. The rest | ||
| 210 | * of it is on the END page, where the entries start, which begin_cluster | ||
| 211 | * reads and keeps, so it is taken from there rather than read twice. */ | ||
| 212 | 3448 | entries = prism_posting_reference_read_to_end( | |
| 213 | 3175 | scan->storage, posting_head, scan->dim, scan->pt_ref, &cluster_id); | |
| 214 | 3175 | ref = scan->pt_ref; | |
| 215 | 3175 | ref_pages = prism_posting_reference_pages(scan->dim) - 1; | |
| 216 | 3175 | begin_cluster(scan, qstate, entries, ref, ref_pages); | |
| 217 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3175 times.
|
3175 | if (scan->cur_page == NULL) |
| 218 | ✗ | vs_error( | |
| 219 | VS_EXTENSION_NAME | ||
| 220 | ": posting list %u ends before its last reference page; " | ||
| 221 | "the index may be corrupted -- REINDEX it", | ||
| 222 | posting_head); | ||
| 223 | 3175 | prism_posting_reference_read_end( | |
| 224 | posting_head, | ||
| 225 | scan->cur_blkno, | ||
| 226 | scan->cur_page, | ||
| 227 | cluster_id, | ||
| 228 | 3175 | scan->dim, | |
| 229 | scan->pt_ref); | ||
| 230 | } | ||
| 231 | |||
| 232 | void | ||
| 233 | 1992 | prism_posting_scan_begin_cluster_at( | |
| 234 | PrismPostingScan *scan, | ||
| 235 | RaBitQQueryState *qstate, | ||
| 236 | BlockNumber entries, | ||
| 237 | const float *ref) | ||
| 238 | { | ||
| 239 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1992 times.
|
1992 | Assert(scan->pt_ref != NULL); |
| 240 | |||
| 241 | /* The caller read the reference pages; the head's END page, where the | ||
| 242 | * entries start, is read again here. */ | ||
| 243 | 1992 | begin_cluster( | |
| 244 | scan, | ||
| 245 | qstate, | ||
| 246 | entries, | ||
| 247 | ref, | ||
| 248 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
|
1992 | prism_posting_reference_pages(scan->dim) - |
| 249 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 1992 times.
✗ Branch 2 not taken.
|
1992 | (prism_posting_spilled(scan->dim) ? 1 : 0)); |
| 250 | 1992 | } | |
| 251 | |||
| 252 | const float * | ||
| 253 | 49860 | prism_posting_scan_pt_centroid(const PrismPostingScan *scan) | |
| 254 | { | ||
| 255 |
2/2✓ Branch 0 taken 5109 times.
✓ Branch 1 taken 44751 times.
|
49860 | if (scan->pt_ref != NULL) |
| 256 | 5109 | return scan->cur_ref; | |
| 257 |
2/2✓ Branch 0 taken 10733 times.
✓ Branch 1 taken 34018 times.
|
44751 | if (scan->cur_page == NULL) |
| 258 | ✗ | return NULL; | |
| 259 | 44751 | return prism_posting_pt_centroid(scan->cur_page); | |
| 260 | } | ||
| 261 | |||
| 262 | void | ||
| 263 | 702 | prism_posting_scan_begin_flat( | |
| 264 | PrismPostingScan *scan, RaBitQQueryState *qstate, char *flat_buf) | ||
| 265 | { | ||
| 266 | 702 | PrismFlatPostingHeader *hdr = prism_flat_posting_header(flat_buf); | |
| 267 | |||
| 268 | 702 | scan->qstate = qstate; | |
| 269 | 702 | scan->cur_blkno = InvalidBlockNumber; | |
| 270 | 702 | scan->cur_page = flat_buf; | |
| 271 |
0/2✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
702 | scan->cur_content = prism_flat_posting_content(flat_buf); |
| 272 | 702 | scan->cur_max_entries = hdr->max_entries; | |
| 273 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 702 times.
|
702 | if (hdr->entry_count > scan->max_entries_cap) |
| 274 | ✗ | vs_error( | |
| 275 | VS_EXTENSION_NAME | ||
| 276 | ": flat posting page has an invalid entry count (%u > %u); " | ||
| 277 | "the index may be corrupted -- REINDEX it", | ||
| 278 | (unsigned)hdr->entry_count, | ||
| 279 | scan->max_entries_cap); | ||
| 280 | 702 | scan->cur_count = hdr->entry_count; | |
| 281 | 702 | scan->pages_read = 1; | |
| 282 | 702 | scan->pages_skipped = 0; | |
| 283 | 702 | scan->entries_scanned = 0; | |
| 284 | 702 | scan->entries_pruned = 0; | |
| 285 | 702 | } | |
| 286 | |||
| 287 | void | ||
| 288 | 50804 | prism_posting_scan_end_cluster(PrismPostingScan *scan) | |
| 289 | { | ||
| 290 | /* Release current page if held via storage vtable */ | ||
| 291 |
3/4✓ Branch 0 taken 9120 times.
✓ Branch 1 taken 41684 times.
✓ Branch 2 taken 9120 times.
✗ Branch 3 not taken.
|
50804 | if (scan->cur_page != NULL && scan->storage != NULL && |
| 292 |
2/2✓ Branch 0 taken 1120 times.
✓ Branch 1 taken 8000 times.
|
9120 | scan->page_base == NULL) |
| 293 | { | ||
| 294 | 1120 | vs_storage_release_page(scan->storage, scan->cur_blkno); | |
| 295 | } | ||
| 296 | |||
| 297 | 50804 | scan->cur_page = NULL; | |
| 298 | 50804 | scan->cur_content = NULL; | |
| 299 | 50804 | scan->cur_ref = NULL; | |
| 300 | 50804 | scan->qstate = NULL; | |
| 301 | 50804 | } | |
| 302 | |||
| 303 | /* ---------------------------------------------------------------- | ||
| 304 | * Advance to next page in chain | ||
| 305 | * ---------------------------------------------------------------- */ | ||
| 306 | |||
| 307 | static bool | ||
| 308 | 110071 | advance_page(PrismPostingScan *scan) | |
| 309 | { | ||
| 310 | /* Follow chain from current page */ | ||
| 311 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 110071 times.
|
110071 | if (scan->cur_page != NULL) |
| 312 | { | ||
| 313 | ✗ | if (scan->storage != NULL) | |
| 314 | { | ||
| 315 | ✗ | scan->cur_blkno = prism_posting_opaque(scan->cur_page)->next_blkno; | |
| 316 | } | ||
| 317 | else | ||
| 318 | { | ||
| 319 | /* Flat mode: single page, no chain */ | ||
| 320 | ✗ | scan->cur_blkno = InvalidBlockNumber; | |
| 321 | } | ||
| 322 | ✗ | scan->cur_page = NULL; | |
| 323 | ✗ | scan->cur_content = NULL; | |
| 324 | } | ||
| 325 | |||
| 326 |
2/2✓ Branch 0 taken 40982 times.
✓ Branch 1 taken 69089 times.
|
110071 | if (scan->cur_blkno == InvalidBlockNumber) |
| 327 | 31082 | return false; | |
| 328 | |||
| 329 | /* Read next page — inline for ArrayPageStorage. A scan over a | ||
| 330 | * non-paged posting format carries neither a page base nor a storage | ||
| 331 | * (see the flat branch of the standalone query context); it reaches | ||
| 332 | * its single page through begin_flat and has no chain to follow. */ | ||
| 333 |
2/2✓ Branch 0 taken 54879 times.
✓ Branch 1 taken 14210 times.
|
69089 | if (scan->page_base != NULL) |
| 334 | 54879 | scan->cur_page = scan->page_base + (size_t)scan->cur_blkno * BLCKSZ; | |
| 335 |
2/2✓ Branch 0 taken 1434 times.
✓ Branch 1 taken 12776 times.
|
14210 | else if (scan->storage != NULL) |
| 336 | 14210 | scan->cur_page = vs_storage_read_page(scan->storage, scan->cur_blkno); | |
| 337 | else | ||
| 338 | ✗ | return false; | |
| 339 | |||
| 340 | 69089 | PrismPostingPageOpaque *opaque = prism_posting_opaque(scan->cur_page); | |
| 341 | |||
| 342 | /* Validate page identity — catch corrupted chain pointers early */ | ||
| 343 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 69089 times.
|
69089 | if (opaque->page_id != PRISM_POSTING_PAGE_ID) |
| 344 | { | ||
| 345 | ✗ | vs_warn(VS_EXTENSION_NAME ": posting scan hit non-posting page " | |
| 346 | "(blkno=%u, page_id=0x%04X)", | ||
| 347 | scan->cur_blkno, | ||
| 348 | opaque->page_id); | ||
| 349 | /* Release the pin taken above before bailing (storage-backed only; | ||
| 350 | * in page_base mode the page is a borrowed pointer, not a pin). */ | ||
| 351 | ✗ | if (scan->storage != NULL && scan->page_base == NULL) | |
| 352 | ✗ | vs_storage_release_page(scan->storage, scan->cur_blkno); | |
| 353 | ✗ | scan->cur_page = NULL; | |
| 354 | ✗ | scan->cur_content = NULL; | |
| 355 | ✗ | return false; | |
| 356 | } | ||
| 357 | |||
| 358 | 69089 | scan->cur_content = prism_posting_page_content(scan->cur_page, scan->dim); | |
| 359 | 69089 | scan->cur_max_entries = opaque->max_entries; | |
| 360 | /* Reject an entry_count past what a valid page of this format can | ||
| 361 | * hold. An AoS page's entries must fit the page, and a list's first | ||
| 362 | * entry page holds fewer than a later one; they also drive the | ||
| 363 | * page_distances/page_scratch batch, sized to max_entries_cap. Fastscan | ||
| 364 | * pages are scored per 32-vector group, and their group metadata and | ||
| 365 | * code run must fit the page. */ | ||
| 366 |
2/2✓ Branch 0 taken 20256 times.
✓ Branch 1 taken 48833 times.
|
69089 | if (opaque->flags & PRISM_POSTING_PAGE_FASTSCAN) |
| 367 | 20256 | fastscan_check_page(scan, opaque); | |
| 368 | else | ||
| 369 | { | ||
| 370 | 48833 | uint32_t cap = prism_posting_page_cap(opaque, scan->dim); | |
| 371 | |||
| 372 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 46281 times.
|
48833 | if (cap > scan->max_entries_cap) |
| 373 | ✗ | cap = scan->max_entries_cap; | |
| 374 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48833 times.
|
48833 | if (opaque->entry_count > cap) |
| 375 | ✗ | vs_error( | |
| 376 | VS_EXTENSION_NAME | ||
| 377 | ": posting page %u has an invalid entry count (%u > %u); " | ||
| 378 | "the index may be corrupted -- REINDEX it", | ||
| 379 | scan->cur_blkno, | ||
| 380 | (unsigned)opaque->entry_count, | ||
| 381 | cap); | ||
| 382 | } | ||
| 383 | 69089 | scan->cur_count = opaque->entry_count; | |
| 384 | 69089 | scan->pages_read++; | |
| 385 | 69089 | return true; | |
| 386 | } | ||
| 387 | |||
| 388 | /* ---------------------------------------------------------------- | ||
| 389 | * Score + prune a full cluster into topk | ||
| 390 | * | ||
| 391 | * Inserts survivors with approximate (estimated) distances and | ||
| 392 | * error bounds. No exact reranking — the caller does that after | ||
| 393 | * extracting candidates from topk. | ||
| 394 | * ---------------------------------------------------------------- */ | ||
| 395 | |||
| 396 | static void scan_fastscan_page(PrismPostingScan *scan, VsTopK *topk); | ||
| 397 | static void fastscan_check_stream_end(const PrismPostingScan *scan); | ||
| 398 | |||
| 399 | void | ||
| 400 | 41433 | prism_posting_scan_aos_page(PrismPostingScan *scan, VsTopK *topk) | |
| 401 | { | ||
| 402 | 41433 | Dimension dim = scan->dim; | |
| 403 | 41433 | uint32_t entry_size = PRISM_POSTING_ENTRY_SIZE(dim); | |
| 404 | |||
| 405 | 41433 | float g_add = scan->qstate->g_add; | |
| 406 | 41433 | float sum_t = scan->qstate->sum_transformed; | |
| 407 | 41433 | float inv_sqrt_d = scan->qstate->inv_sqrt_d; | |
| 408 | 41433 | float g_error = scan->qstate->g_error; | |
| 409 | |||
| 410 | 41433 | Distance *distances = scan->page_distances; | |
| 411 | 41433 | float *scratch = scan->page_scratch; | |
| 412 | |||
| 413 | 41433 | char *content = scan->cur_content; | |
| 414 | 41433 | uint32_t count = scan->cur_count; | |
| 415 | |||
| 416 | /* --- Score: batch IP over all entries on this page --- | ||
| 417 | * | ||
| 418 | * AoS layout: entry i's bits live at content + i * entry_size | ||
| 419 | * + PRISM_POSTING_ENTRY_BITS_OFFSET. The SIMD kernel just needs | ||
| 420 | * the first entry's bits pointer and a stride of entry_size. */ | ||
| 421 | 41433 | const uint8_t *bits_base = prism_posting_first_bits(content); | |
| 422 | |||
| 423 | /* The exact count: every kernel scores the count % 4 tail itself, and | ||
| 424 | * padding it would read entries past the last one, which at a wide | ||
| 425 | * dimension is past the page. */ | ||
| 426 | 41433 | vs_rabitq_inner_product_multi( | |
| 427 | 41433 | scan->qstate->transformed, | |
| 428 | bits_base, | ||
| 429 | entry_size, | ||
| 430 | dim, | ||
| 431 | count, | ||
| 432 | scratch); | ||
| 433 | |||
| 434 | /* Convert raw IPs to distances, reading f_add/f_rescale per | ||
| 435 | * entry via the strided AoS accessor. */ | ||
| 436 |
3/3✓ Branch 0 taken 2951648 times.
✓ Branch 1 taken 110194 times.
✓ Branch 2 taken 2456 times.
|
3064298 | for (uint32_t i = 0; i < count; i++) |
| 437 | { | ||
| 438 | 3022865 | PrismPostingEntryHeader *e = prism_posting_entry_at(content, i, dim); | |
| 439 | 3022865 | float final_dot = (2.0f * scratch[i] - sum_t) * inv_sqrt_d; | |
| 440 | 3022865 | distances[i] = e->f_add + g_add - 2.0f * e->f_rescale * final_dot; | |
| 441 | } | ||
| 442 | |||
| 443 | /* --- Prune + insert approximate distances --- */ | ||
| 444 |
2/2✓ Branch 0 taken 2262 times.
✓ Branch 1 taken 194 times.
|
41433 | Distance threshold = vs_topk_threshold(topk); |
| 445 | |||
| 446 |
2/2✓ Branch 0 taken 3022865 times.
✓ Branch 1 taken 41433 times.
|
3064298 | for (uint32_t i = 0; i < count; i++) |
| 447 | { | ||
| 448 |
2/2✓ Branch 0 taken 2621 times.
✓ Branch 1 taken 68596 times.
|
3022865 | PrismPostingEntryHeader *e = prism_posting_entry_at(content, i, dim); |
| 449 | 3022865 | scan->entries_scanned++; | |
| 450 | |||
| 451 |
2/2✓ Branch 0 taken 2643 times.
✓ Branch 1 taken 3020222 times.
|
3022865 | if (e->meta.flags & PRISM_POSTING_FLAG_DELETED) |
| 452 | { | ||
| 453 | 2643 | scan->entries_pruned++; | |
| 454 | 2643 | continue; | |
| 455 | } | ||
| 456 | |||
| 457 | 3020222 | Distance est = distances[i]; | |
| 458 | 3020222 | Distance err = e->f_error * g_error; | |
| 459 | 3020222 | Distance lb = est - err; | |
| 460 | |||
| 461 |
2/2✓ Branch 0 taken 2444732 times.
✓ Branch 1 taken 575490 times.
|
3020222 | if (lb >= threshold) |
| 462 | { | ||
| 463 | 2444732 | scan->entries_pruned++; | |
| 464 | 2444732 | continue; | |
| 465 | } | ||
| 466 | |||
| 467 | 575490 | uint64_t id = prism_posting_encode_tid(&e->meta.tid); | |
| 468 | 575490 | vs_topk_insert(topk, est, err, id); | |
| 469 |
2/2✓ Branch 0 taken 4143 times.
✓ Branch 1 taken 4201 times.
|
642506 | threshold = vs_topk_threshold(topk); |
| 470 | } | ||
| 471 | 41433 | } | |
| 472 | |||
| 473 | void | ||
| 474 | 40982 | prism_posting_scan_cluster(PrismPostingScan *scan, VsTopK *topk) | |
| 475 | { | ||
| 476 | /* A flat buffer has no page header to read a format from; standalone | ||
| 477 | * scans it through prism_posting_scan_cluster_standalone. */ | ||
| 478 |
2/4✓ Branch 0 taken 31082 times.
✓ Branch 1 taken 9900 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
40982 | Assert(scan->storage != NULL || scan->page_base != NULL); |
| 479 | |||
| 480 | 33212 | for (;;) | |
| 481 | 59969 | { | |
| 482 |
4/4✓ Branch 0 taken 59969 times.
✓ Branch 1 taken 40982 times.
✓ Branch 3 taken 32838 times.
✓ Branch 4 taken 27131 times.
|
100951 | if (scan->cur_page == NULL && !advance_page(scan)) |
| 483 | 31082 | break; | |
| 484 | |||
| 485 | 59969 | const PrismPostingPageOpaque *opaque = prism_posting_opaque( | |
| 486 | scan->cur_page); | ||
| 487 | |||
| 488 | /* A fastscan page decides itself whether it can be skipped, since a | ||
| 489 | * live group's codes may pass through a page of dead entries. */ | ||
| 490 |
2/2✓ Branch 0 taken 19140 times.
✓ Branch 1 taken 40829 times.
|
59969 | if (opaque->flags & PRISM_POSTING_PAGE_FASTSCAN) |
| 491 | { | ||
| 492 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 19140 times.
|
19140 | if (scan->fs_lut == NULL) |
| 493 | ✗ | vs_error( | |
| 494 | VS_EXTENSION_NAME | ||
| 495 | ": posting page %u is in fastscan format but the scan " | ||
| 496 | "was not set up for fastscan", | ||
| 497 | scan->cur_blkno); | ||
| 498 | 19140 | scan_fastscan_page(scan, topk); | |
| 499 | } | ||
| 500 | else | ||
| 501 | { | ||
| 502 | /* Inserted AoS pages follow the fastscan ones. */ | ||
| 503 | 40829 | fastscan_check_stream_end(scan); | |
| 504 | |||
| 505 | /* A page tombstoned by VACUUM (all entries dead) is skipped. A | ||
| 506 | * retired chain also carries TOMBSTONED once reclaimed, but its | ||
| 507 | * entries moved rather than died, so it is still scored. (A | ||
| 508 | * page that holds only reference, should one be met, holds zero | ||
| 509 | * entries and scores nothing.) */ | ||
| 510 |
3/3✓ Branch 0 taken 92 times.
✓ Branch 1 taken 2462 times.
✓ Branch 2 taken 38275 times.
|
40829 | if (prism_posting_page_all_dead(opaque)) |
| 511 | 98 | scan->pages_skipped++; | |
| 512 | else | ||
| 513 | 40731 | prism_posting_scan_aos_page(scan, topk); | |
| 514 | } | ||
| 515 | |||
| 516 | 59969 | BlockNumber prev_blkno = scan->cur_blkno; | |
| 517 | 59969 | scan->cur_blkno = opaque->next_blkno; | |
| 518 |
2/2✓ Branch 0 taken 13090 times.
✓ Branch 1 taken 46879 times.
|
59969 | if (scan->page_base == NULL) |
| 519 | 13090 | vs_storage_release_page(scan->storage, prev_blkno); | |
| 520 | |||
| 521 | 59969 | scan->cur_page = NULL; | |
| 522 | 59969 | scan->cur_content = NULL; | |
| 523 | } | ||
| 524 | 40982 | fastscan_check_stream_end(scan); | |
| 525 | 40982 | } | |
| 526 | |||
| 527 | /* ---------------------------------------------------------------- | ||
| 528 | * Fastscan: vectorized distance + prune for 16 entries | ||
| 529 | * ---------------------------------------------------------------- */ | ||
| 530 | |||
| 531 | #ifdef VS_SIMD_FULL | ||
| 532 | #if defined(__x86_64__) || defined(_M_X64) | ||
| 533 | |||
| 534 | /* | ||
| 535 | * Compute distances and lower bounds for 16 entries using AVX-512. | ||
| 536 | * Returns a bitmask of survivors (lb < threshold). | ||
| 537 | */ | ||
| 538 | VS_TARGET_AVX512 static inline __mmask16 | ||
| 539 | 48728 | fastscan_prune_16( | |
| 540 | const int32_t *accum, | ||
| 541 | const float *f_add, | ||
| 542 | const float *f_rescale, | ||
| 543 | const float *f_error, | ||
| 544 | float *est_out, | ||
| 545 | float *err_out, | ||
| 546 | float lut_scale, | ||
| 547 | float lut_bias, | ||
| 548 | float sum_t, | ||
| 549 | float inv_sqrt_d, | ||
| 550 | float g_add, | ||
| 551 | float g_error, | ||
| 552 | float threshold, | ||
| 553 | __mmask16 live) | ||
| 554 | { | ||
| 555 | /* Convert 16 int32 accumulators to float */ | ||
| 556 | 48728 | __m512i acc32 = _mm512_loadu_si512((const __m512i *)accum); | |
| 557 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __m512 acc_f = _mm512_cvtepi32_ps(acc32); |
| 558 | |||
| 559 | /* binary_ip = acc * scale + bias */ | ||
| 560 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __m512 scale_v = _mm512_set1_ps(lut_scale); |
| 561 | 48728 | __m512 bias_v = _mm512_set1_ps(lut_bias); | |
| 562 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __m512 ip = _mm512_fmadd_ps(acc_f, scale_v, bias_v); |
| 563 | |||
| 564 | /* final_dot = (2*ip - sum_t) * inv_sqrt_d */ | ||
| 565 | 48728 | __m512 two_v = _mm512_set1_ps(2.0f); | |
| 566 | 48728 | __m512 sum_t_v = _mm512_set1_ps(sum_t); | |
| 567 | 48728 | __m512 inv_sqrt_v = _mm512_set1_ps(inv_sqrt_d); | |
| 568 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
8332 | __m512 final_dot = |
| 569 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
89124 | _mm512_mul_ps(_mm512_fmsub_ps(two_v, ip, sum_t_v), inv_sqrt_v); |
| 570 | |||
| 571 | /* est = f_add + g_add - 2 * f_rescale * final_dot */ | ||
| 572 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __m512 fa = _mm512_loadu_ps(f_add); |
| 573 | 48728 | __m512 fr = _mm512_loadu_ps(f_rescale); | |
| 574 | 48728 | __m512 gadd = _mm512_set1_ps(g_add); | |
| 575 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __m512 est_v = _mm512_add_ps(fa, gadd); |
| 576 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
89124 | est_v = _mm512_fnmadd_ps(_mm512_mul_ps(two_v, fr), final_dot, est_v); |
| 577 | |||
| 578 | /* err = f_error * g_error */ | ||
| 579 | 48728 | __m512 fe = _mm512_loadu_ps(f_error); | |
| 580 | 48728 | __m512 gerr_v = _mm512_set1_ps(g_error); | |
| 581 | 48728 | __m512 err_v = _mm512_mul_ps(fe, gerr_v); | |
| 582 | |||
| 583 | /* lb = est - err; survivors = lb < threshold, restricted to live lanes -- | ||
| 584 | * the masked compare clears a dead lane's result bit regardless of score. | ||
| 585 | */ | ||
| 586 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __m512 lb_v = _mm512_sub_ps(est_v, err_v); |
| 587 | 48728 | __m512 thr_v = _mm512_set1_ps(threshold); | |
| 588 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | __mmask16 surv = _mm512_mask_cmp_ps_mask(live, lb_v, thr_v, _CMP_LT_OS); |
| 589 | |||
| 590 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
8332 | _mm512_storeu_ps(est_out, est_v); |
| 591 | 8332 | _mm512_storeu_ps(err_out, err_v); | |
| 592 | |||
| 593 | 48728 | return surv; | |
| 594 | } | ||
| 595 | |||
| 596 | /* | ||
| 597 | * AVX-512 vectorized distance + prune for one 32-vector group. | ||
| 598 | * Must be in a target-attributed function so the compiler only | ||
| 599 | * emits AVX-512 instructions here, not in the caller. | ||
| 600 | */ | ||
| 601 | VS_TARGET_AVX512 static void | ||
| 602 | 24364 | fastscan_prune_group_avx512( | |
| 603 | PrismPostingScan *scan, | ||
| 604 | VsTopK *topk, | ||
| 605 | const int32_t *accum, | ||
| 606 | ItemPointerData *tids, | ||
| 607 | const float *f_add, | ||
| 608 | const float *f_rescale, | ||
| 609 | const float *f_error, | ||
| 610 | float lut_scale, | ||
| 611 | float lut_bias, | ||
| 612 | float sum_t, | ||
| 613 | float inv_sqrt_d, | ||
| 614 | float g_add, | ||
| 615 | float g_error, | ||
| 616 | uint32_t tombstone_mask, | ||
| 617 | Distance *threshold_p) | ||
| 618 | { | ||
| 619 | 24364 | Distance threshold = *threshold_p; | |
| 620 | 4166 | float est_buf[VS_FASTSCAN_GROUP]; | |
| 621 | 4166 | float err_buf[VS_FASTSCAN_GROUP]; | |
| 622 | 24364 | uint32_t live_mask = ~tombstone_mask; | |
| 623 | |||
| 624 |
2/2✓ Branch 0 taken 48728 times.
✓ Branch 1 taken 24364 times.
|
73092 | for (uint32_t h = 0; h < 2; h++) |
| 625 | { | ||
| 626 | 48728 | uint32_t off = h * 16; | |
| 627 | 48728 | __mmask16 live = (__mmask16)((live_mask >> off) & 0xFFFFu); | |
| 628 | 48728 | __mmask16 surv = fastscan_prune_16( | |
| 629 | 40396 | accum + off, | |
| 630 | 40396 | f_add + off, | |
| 631 | 40396 | f_rescale + off, | |
| 632 | 40396 | f_error + off, | |
| 633 | 40396 | est_buf + off, | |
| 634 |
2/2✓ Branch 0 taken 6897 times.
✓ Branch 1 taken 1435 times.
|
48728 | err_buf + off, |
| 635 | lut_scale, | ||
| 636 | lut_bias, | ||
| 637 | sum_t, | ||
| 638 | inv_sqrt_d, | ||
| 639 | g_add, | ||
| 640 | g_error, | ||
| 641 | threshold, | ||
| 642 | live); | ||
| 643 | |||
| 644 |
2/2✓ Branch 0 taken 24706 times.
✓ Branch 1 taken 24022 times.
|
48728 | if (surv == 0) |
| 645 | { | ||
| 646 | 24706 | scan->entries_pruned += 16; | |
| 647 | 24706 | continue; | |
| 648 | } | ||
| 649 | |||
| 650 | 24022 | scan->entries_pruned += 16 - _mm_popcnt_u32(surv); | |
| 651 | |||
| 652 |
2/2✓ Branch 0 taken 154196 times.
✓ Branch 1 taken 22587 times.
|
178218 | while (surv != 0) |
| 653 | { | ||
| 654 | 167641 | uint32_t v = off + __builtin_ctz(surv); | |
| 655 | 167641 | surv &= surv - 1; | |
| 656 | |||
| 657 | 167641 | uint64_t id = prism_posting_encode_tid(&tids[v]); | |
| 658 | 167641 | vs_topk_insert(topk, est_buf[v], err_buf[v], id); | |
| 659 |
4/4✓ Branch 0 taken 11783 times.
✓ Branch 1 taken 1662 times.
✓ Branch 2 taken 13445 times.
✓ Branch 3 taken 1435 times.
|
182521 | threshold = vs_topk_threshold(topk); |
| 660 | } | ||
| 661 | } | ||
| 662 | |||
| 663 | 24364 | *threshold_p = threshold; | |
| 664 | 24364 | } | |
| 665 | |||
| 666 | #endif | ||
| 667 | #endif | ||
| 668 | |||
| 669 | /* ---------------------------------------------------------------- | ||
| 670 | * Score one fastscan page: VPSHUFB kernel over 32-vector groups via | ||
| 671 | * table-lookup accumulation. | ||
| 672 | * | ||
| 673 | * Walks the list's code stream page by page (see the fastscan page format | ||
| 674 | * in posting_page.h). A group's running sums carry across pages until its | ||
| 675 | * last code byte and its metadata have both been read, then the | ||
| 676 | * group is scored. | ||
| 677 | * ---------------------------------------------------------------- */ | ||
| 678 | |||
| 679 | static void | ||
| 680 | ✗ | fastscan_corrupt(const PrismPostingScan *scan, const char *what) | |
| 681 | { | ||
| 682 | ✗ | vs_error( | |
| 683 | VS_EXTENSION_NAME | ||
| 684 | ": fastscan posting page %u breaks its list's code stream (%s); " | ||
| 685 | "the index may be corrupted -- REINDEX it", | ||
| 686 | scan->cur_blkno, | ||
| 687 | what); | ||
| 688 | } | ||
| 689 | |||
| 690 | static inline int32_t * | ||
| 691 | 71253 | fastscan_group_accum(const PrismPostingScan *scan, uint32_t group) | |
| 692 | { | ||
| 693 | 122607 | return scan->fs_accum + | |
| 694 | 71253 | (size_t)(group % PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS) * | |
| 695 | VS_FASTSCAN_GROUP; | ||
| 696 | } | ||
| 697 | |||
| 698 | /* Build the query LUT once per cluster, on its first fastscan page. */ | ||
| 699 | static void | ||
| 700 | 19137 | fastscan_ensure_lut(PrismPostingScan *scan) | |
| 701 | { | ||
| 702 |
2/2✓ Branch 0 taken 16336 times.
✓ Branch 1 taken 2801 times.
|
19137 | if (scan->fs_lut_valid) |
| 703 | 7954 | return; | |
| 704 |
2/2✓ Branch 0 taken 60 times.
✓ Branch 1 taken 10398 times.
|
10458 | if (scan->fs_lut_bits == 8) |
| 705 | 60 | vs_fastscan_build_lut( | |
| 706 | 60 | scan->qstate->transformed, | |
| 707 | 60 | scan->dim, | |
| 708 | scan->fs_lut, | ||
| 709 | &scan->fs_lut_scale, | ||
| 710 | &scan->fs_lut_bias); | ||
| 711 | else | ||
| 712 | 10398 | vs_fastscan_build_lut_hacc( | |
| 713 | 10398 | scan->qstate->transformed, | |
| 714 | 10398 | scan->dim, | |
| 715 | scan->fs_lut, | ||
| 716 | &scan->fs_lut_scale, | ||
| 717 | &scan->fs_lut_bias); | ||
| 718 | 10458 | scan->fs_lut_valid = true; | |
| 719 | } | ||
| 720 | |||
| 721 | /* | ||
| 722 | * Add one run of a group's codes into its running sums. A group's first | ||
| 723 | * run starts them: when it fits one kernel call, the kernel writes the sums | ||
| 724 | * directly, which is the whole job for a group that sits on one page. | ||
| 725 | */ | ||
| 726 | __attribute__((always_inline)) static inline void | ||
| 727 | 10297 | fastscan_accumulate_run( | |
| 728 | PrismPostingScan *scan, | ||
| 729 | const uint8_t *codes, | ||
| 730 | uint32_t offset, | ||
| 731 | uint32_t len, | ||
| 732 | int32_t *accum) | ||
| 733 | { | ||
| 734 | 39457 | uint32_t col_bytes = VS_FASTSCAN_GROUP_BYTES(8); | |
| 735 | 39457 | uint32_t col = offset / col_bytes; | |
| 736 | 39457 | uint32_t ncols = len / col_bytes; | |
| 737 | |||
| 738 | /* Runs start on chunks, so col is even, as the 16-bit table needs. */ | ||
| 739 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 16692 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 12468 times.
|
29160 | Assert(offset % PRISM_FASTSCAN_CHUNK_BYTES == 0); |
| 740 | |||
| 741 |
8/8✓ Branch 0 taken 16931 times.
✓ Branch 1 taken 927 times.
✓ Branch 2 taken 16688 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 5502 times.
✓ Branch 5 taken 6966 times.
✓ Branch 6 taken 2198 times.
✓ Branch 7 taken 3304 times.
|
30326 | if (offset == 0 && ncols <= VS_FASTSCAN_MAX_KERNEL_COLS) |
| 742 | { | ||
| 743 | 28256 | Dimension run_dim = (Dimension)(ncols * 8); | |
| 744 | |||
| 745 |
4/4✓ Branch 0 taken 142 times.
✓ Branch 1 taken 25677 times.
✓ Branch 2 taken 132 times.
✓ Branch 3 taken 2305 times.
|
28256 | if (scan->fs_lut_bits == 8) |
| 746 | { | ||
| 747 | ✗ | uint16_t acc16[VS_FASTSCAN_GROUP]; | |
| 748 | 274 | vs_fastscan_accumulate(codes, scan->fs_lut, acc16, run_dim); | |
| 749 |
4/6✓ Branch 0 taken 4544 times.
✓ Branch 1 taken 142 times.
✓ Branch 2 taken 4224 times.
✓ Branch 3 taken 132 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
9042 | for (uint32_t v = 0; v < VS_FASTSCAN_GROUP; v++) |
| 750 | 8768 | accum[v] = acc16[v]; | |
| 751 | } | ||
| 752 | else | ||
| 753 | 27982 | scan->fs_accum_hacc(codes, scan->fs_lut, accum, run_dim); | |
| 754 | 18886 | return; | |
| 755 | } | ||
| 756 | |||
| 757 |
4/4✓ Branch 0 taken 237 times.
✓ Branch 1 taken 694 times.
✓ Branch 2 taken 3304 times.
✓ Branch 3 taken 6966 times.
|
11201 | if (offset == 0) |
| 758 |
0/2✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
3541 | memset(accum, 0, VS_FASTSCAN_GROUP * sizeof(int32_t)); |
| 759 |
4/4✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 486 times.
✓ Branch 3 taken 10711 times.
|
11201 | if (scan->fs_lut_bits == 8) |
| 760 | 488 | vs_fastscan_accumulate_range(codes, scan->fs_lut, col, ncols, accum); | |
| 761 | else | ||
| 762 | 10713 | vs_fastscan_accumulate_hacc_range( | |
| 763 | 10713 | scan->fs_accum_hacc, codes, scan->fs_lut, col, ncols, accum); | |
| 764 | } | ||
| 765 | |||
| 766 | /* What scoring the groups of one fastscan page needs, gathered once. */ | ||
| 767 | typedef struct FastscanPageCtx | ||
| 768 | { | ||
| 769 | VsTopK *topk; | ||
| 770 | char *content; | ||
| 771 | uint32_t first_group; /* list-wide index of the page's first group */ | ||
| 772 | uint32_t meta_end; /* one past its last */ | ||
| 773 | uint32_t count; /* vectors in the page's blocks */ | ||
| 774 | uint32_t next_group; /* next group to score */ | ||
| 775 | float lut_scale; | ||
| 776 | float lut_bias; | ||
| 777 | float g_add; | ||
| 778 | float sum_t; | ||
| 779 | float inv_sqrt_d; | ||
| 780 | float g_error; | ||
| 781 | Distance threshold; | ||
| 782 | } FastscanPageCtx; | ||
| 783 | |||
| 784 | /* Prune the next group, whose running sums are complete, and insert | ||
| 785 | * survivors. */ | ||
| 786 | __attribute__((always_inline)) static inline void | ||
| 787 | 9602 | fastscan_score_group(PrismPostingScan *scan, FastscanPageCtx *ctx) | |
| 788 | { | ||
| 789 | 31796 | uint32_t g = ctx->next_group - ctx->first_group; | |
| 790 | 31796 | uint32_t g_count = ctx->count - g * VS_FASTSCAN_GROUP; | |
| 791 |
6/6✓ Branch 0 taken 1948 times.
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 14600 times.
✓ Branch 3 taken 2092 times.
✓ Branch 4 taken 72 times.
✓ Branch 5 taken 3446 times.
|
31796 | if (g_count > VS_FASTSCAN_GROUP) |
| 792 | 16620 | g_count = VS_FASTSCAN_GROUP; | |
| 793 | |||
| 794 | 31796 | const int32_t *accum = fastscan_group_accum(scan, ctx->next_group); | |
| 795 | 31796 | ItemPointerData *tids = prism_fastscan_group_tids(ctx->content, g); | |
| 796 |
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.
|
31796 | float *f_add = prism_fastscan_group_f_add(ctx->content, g); |
| 797 |
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.
|
31796 | float *f_rescale = prism_fastscan_group_f_rescale(ctx->content, g); |
| 798 |
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.
|
31796 | float *f_error = prism_fastscan_group_f_error(ctx->content, g); |
| 799 | 31796 | uint32_t tombstone_mask = | |
| 800 |
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.
|
31796 | *prism_fastscan_group_tombstone_mask(ctx->content, g); |
| 801 | |||
| 802 | /* Vectorized distance + prune: compute 16 distances at a | ||
| 803 | * time, mask survivors, iterate only the few that pass. */ | ||
| 804 | 31796 | scan->entries_scanned += g_count; | |
| 805 | |||
| 806 | #ifdef VS_SIMD_FULL | ||
| 807 | #if defined(__x86_64__) || defined(_M_X64) | ||
| 808 |
9/12✓ Branch 0 taken 1980 times.
✓ Branch 1 taken 38 times.
✓ Branch 2 taken 1980 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 19494 times.
✓ Branch 5 taken 6329 times.
✓ Branch 6 taken 19494 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2890 times.
✓ Branch 9 taken 1065 times.
✓ Branch 10 taken 2890 times.
✗ Branch 11 not taken.
|
31796 | if (vs_likely(g_count == VS_FASTSCAN_GROUP) && scan->fs_has_avx512) |
| 809 | { | ||
| 810 | 24364 | fastscan_prune_group_avx512( | |
| 811 | scan, | ||
| 812 | ctx->topk, | ||
| 813 | accum, | ||
| 814 | tids, | ||
| 815 | f_add, | ||
| 816 | f_rescale, | ||
| 817 | f_error, | ||
| 818 | ctx->lut_scale, | ||
| 819 | ctx->lut_bias, | ||
| 820 | ctx->sum_t, | ||
| 821 | ctx->inv_sqrt_d, | ||
| 822 | ctx->g_add, | ||
| 823 | ctx->g_error, | ||
| 824 | tombstone_mask, | ||
| 825 | &ctx->threshold); | ||
| 826 | 24364 | return; | |
| 827 | } | ||
| 828 | #endif | ||
| 829 | #endif | ||
| 830 | |||
| 831 | /* Scalar fallback for partial groups (and non-AVX512 CPUs, | ||
| 832 | * NEON included): no masked-compare primitive to fold the | ||
| 833 | * exclusion into, so a dead lane is skipped explicitly, the | ||
| 834 | * same as a DELETED AoS entry. */ | ||
| 835 | 7432 | Distance threshold = ctx->threshold; | |
| 836 |
6/6✓ Branch 0 taken 312 times.
✓ Branch 1 taken 38 times.
✓ Branch 2 taken 93503 times.
✓ Branch 3 taken 6329 times.
✓ Branch 4 taken 15465 times.
✓ Branch 5 taken 1065 times.
|
116712 | for (uint32_t v = 0; v < g_count; v++) |
| 837 | { | ||
| 838 |
7/8✓ Branch 0 taken 5 times.
✓ Branch 1 taken 219 times.
✓ Branch 2 taken 119 times.
✓ Branch 3 taken 69640 times.
✓ Branch 4 taken 34 times.
✓ Branch 5 taken 25227 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 14036 times.
|
109280 | if (prism_fastscan_lane_is_tombstoned(tombstone_mask, v)) |
| 839 | { | ||
| 840 | 70 | scan->entries_pruned++; | |
| 841 | 70 | continue; | |
| 842 | } | ||
| 843 | |||
| 844 | 109210 | float binary_ip = (float)accum[v] * ctx->lut_scale + ctx->lut_bias; | |
| 845 | 109210 | float final_dot = (2.0f * binary_ip - ctx->sum_t) * ctx->inv_sqrt_d; | |
| 846 | 109210 | Distance est = f_add[v] + ctx->g_add - 2.0f * f_rescale[v] * final_dot; | |
| 847 | 109210 | Distance err = f_error[v] * ctx->g_error; | |
| 848 | 109210 | Distance lb = est - err; | |
| 849 | |||
| 850 |
6/6✓ Branch 0 taken 193 times.
✓ Branch 1 taken 114 times.
✓ Branch 2 taken 78533 times.
✓ Branch 3 taken 14935 times.
✓ Branch 4 taken 7889 times.
✓ Branch 5 taken 7546 times.
|
109210 | if (lb >= threshold) |
| 851 | { | ||
| 852 | 86615 | scan->entries_pruned++; | |
| 853 | 86615 | continue; | |
| 854 | } | ||
| 855 | |||
| 856 | 22595 | uint64_t id = prism_posting_encode_tid(&tids[v]); | |
| 857 | 22595 | vs_topk_insert(ctx->topk, est, err, id); | |
| 858 |
6/6✓ Branch 0 taken 9 times.
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 6744 times.
✓ Branch 3 taken 5339 times.
✓ Branch 4 taken 72 times.
✓ Branch 5 taken 187 times.
|
88376 | threshold = vs_topk_threshold(ctx->topk); |
| 859 | } | ||
| 860 | 7432 | ctx->threshold = threshold; | |
| 861 | } | ||
| 862 | |||
| 863 | /* | ||
| 864 | * Score the groups whose metadata is on this page and whose codes are | ||
| 865 | * complete, up to (not including) list-wide group `done`. | ||
| 866 | */ | ||
| 867 | __attribute__((always_inline)) static inline void | ||
| 868 | 9578 | fastscan_score_ready( | |
| 869 | PrismPostingScan *scan, FastscanPageCtx *ctx, uint32_t done) | ||
| 870 | { | ||
| 871 |
7/8✓ Branch 0 taken 11091 times.
✓ Branch 1 taken 10064 times.
✓ Branch 2 taken 2018 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 5973 times.
✓ Branch 5 taken 3955 times.
✓ Branch 6 taken 3955 times.
✓ Branch 7 taken 2018 times.
|
31083 | while (ctx->next_group < done && ctx->next_group < ctx->meta_end) |
| 872 | { | ||
| 873 |
4/4✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 310 times.
✓ Branch 3 taken 127 times.
|
471 | fastscan_score_group(scan, ctx); |
| 874 | 5973 | ctx->next_group++; | |
| 875 | } | ||
| 876 | 15532 | } | |
| 877 | |||
| 878 | static void | ||
| 879 | 19140 | scan_fastscan_page(PrismPostingScan *scan, VsTopK *topk) | |
| 880 | { | ||
| 881 | 19140 | char *content = scan->cur_content; | |
| 882 | 19140 | PrismPostingPageOpaque *opaque = prism_posting_opaque(scan->cur_page); | |
| 883 | 19140 | uint32_t code_len = VS_FASTSCAN_GROUP_BYTES(scan->dim); | |
| 884 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 9108 times.
|
19140 | uint32_t ngroups = prism_fastscan_page_groups(opaque); |
| 885 | |||
| 886 | /* The page continues the stream where the previous one stopped. */ | ||
| 887 | 19140 | uint64_t start = scan->fs_stream_pos; | |
| 888 | 19140 | uint64_t end = start + opaque->code_bytes; | |
| 889 | 19140 | uint32_t first_group = scan->fs_next_group; | |
| 890 | 19140 | uint32_t meta_end = first_group + ngroups; | |
| 891 | 19140 | uint64_t pos = start; | |
| 892 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 9108 times.
|
19140 | const uint8_t *codes = prism_fastscan_page_codes(content, ngroups); |
| 893 | |||
| 894 | /* The builder ends a run inside a group only at a chunk boundary. A run | ||
| 895 | * that ends elsewhere would start the next page's kernel call at a | ||
| 896 | * column its lookup table does not line up with, so it is refused before | ||
| 897 | * any kernel runs. The previous page's end, checked the same way, is | ||
| 898 | * where this run starts. */ | ||
| 899 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 19140 times.
|
19140 | if (end % code_len % PRISM_FASTSCAN_CHUNK_BYTES != 0) |
| 900 | ✗ | fastscan_corrupt(scan, "a code run ends inside a chunk"); | |
| 901 | |||
| 902 | /* | ||
| 903 | * A page with only dead entries is skipped when everything on it belongs | ||
| 904 | * to its own groups: its codes end on a group boundary and every group | ||
| 905 | * they touch has its metadata here. Otherwise a live group's codes or | ||
| 906 | * running sums pass through the page and it must be read. | ||
| 907 | */ | ||
| 908 |
5/5✓ Branch 0 taken 7 times.
✓ Branch 1 taken 9105 times.
✓ Branch 2 taken 10029 times.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 2 times.
|
19147 | if (prism_posting_page_all_dead(opaque) && end % code_len == 0 && |
| 909 |
1/2✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
|
3 | meta_end == end / code_len) |
| 910 | { | ||
| 911 | 3 | scan->fs_stream_pos = end; | |
| 912 | 3 | scan->fs_next_group = meta_end; | |
| 913 | 3 | scan->pages_skipped++; | |
| 914 | 3 | return; | |
| 915 | } | ||
| 916 | |||
| 917 | 19137 | fastscan_ensure_lut(scan); | |
| 918 | |||
| 919 | 38274 | FastscanPageCtx ctx = { | |
| 920 | .topk = topk, | ||
| 921 | .content = content, | ||
| 922 | .first_group = first_group, | ||
| 923 | .meta_end = meta_end, | ||
| 924 | 19137 | .count = scan->cur_count, | |
| 925 | 19137 | .next_group = scan->fs_next_group, | |
| 926 | 19137 | .lut_scale = scan->fs_lut_scale, | |
| 927 | 19137 | .lut_bias = scan->fs_lut_bias, | |
| 928 | 19137 | .g_add = scan->qstate->g_add, | |
| 929 | 19137 | .sum_t = scan->qstate->sum_transformed, | |
| 930 | 19137 | .inv_sqrt_d = scan->qstate->inv_sqrt_d, | |
| 931 |
2/2✓ Branch 0 taken 8452 times.
✓ Branch 1 taken 655 times.
|
19137 | .g_error = scan->qstate->g_error, |
| 932 | 19137 | .threshold = vs_topk_threshold(topk), | |
| 933 | }; | ||
| 934 | |||
| 935 | /* The group the page's codes start in, and how far into it. */ | ||
| 936 | 19137 | uint32_t g = (uint32_t)(pos / code_len); | |
| 937 | 19137 | uint32_t off = (uint32_t)(pos % code_len); | |
| 938 | |||
| 939 | /* Groups whose codes ended on an earlier page. */ | ||
| 940 | 9107 | fastscan_score_ready(scan, &ctx, g); | |
| 941 | |||
| 942 |
2/2✓ Branch 0 taken 29160 times.
✓ Branch 1 taken 10030 times.
|
58594 | while (pos < end) |
| 943 | { | ||
| 944 | 39457 | const uint8_t *run_codes = codes + (pos - start); | |
| 945 | |||
| 946 | /* | ||
| 947 | * The common case: a whole group on this page with its metadata | ||
| 948 | * here and nothing waiting before it, scored straight away. | ||
| 949 | */ | ||
| 950 |
8/8✓ Branch 0 taken 31797 times.
✓ Branch 1 taken 7660 times.
✓ Branch 2 taken 27801 times.
✓ Branch 3 taken 3996 times.
✓ Branch 4 taken 26834 times.
✓ Branch 5 taken 967 times.
✓ Branch 6 taken 25823 times.
✓ Branch 7 taken 1011 times.
|
39457 | if (off == 0 && end - pos >= code_len && ctx.next_group == g && |
| 951 | g < meta_end) | ||
| 952 | 25823 | { | |
| 953 |
1/2✓ Branch 0 taken 9131 times.
✗ Branch 1 not taken.
|
25823 | fastscan_accumulate_run( |
| 954 | scan, | ||
| 955 | run_codes, | ||
| 956 | 0, | ||
| 957 | code_len, | ||
| 958 | fastscan_group_accum(scan, g)); | ||
| 959 | 25823 | pos += code_len; | |
| 960 | |||
| 961 | /* Fetch the next group's codes while this one is pruned. */ | ||
| 962 | 22397 | uint32_t ahead = end - pos < code_len ? (uint32_t)(end - pos) | |
| 963 |
2/2✓ Branch 0 taken 6817 times.
✓ Branch 1 taken 19006 times.
|
25823 | : code_len; |
| 964 |
2/2✓ Branch 0 taken 33439 times.
✓ Branch 1 taken 25823 times.
|
59262 | for (uint32_t p = 0; p < ahead; p += PRISM_FASTSCAN_CHUNK_BYTES) |
| 965 | 33439 | __builtin_prefetch(run_codes + code_len + p, 0, 1); | |
| 966 |
2/2✓ Branch 0 taken 3848 times.
✓ Branch 1 taken 5283 times.
|
9131 | fastscan_score_group(scan, &ctx); |
| 967 | 25823 | ctx.next_group++; | |
| 968 | 25823 | g++; | |
| 969 | 25823 | continue; | |
| 970 | } | ||
| 971 | |||
| 972 | 13634 | uint32_t run = code_len - off; | |
| 973 |
2/2✓ Branch 0 taken 7661 times.
✓ Branch 1 taken 5973 times.
|
13634 | if (run > end - pos) |
| 974 | 7661 | run = (uint32_t)(end - pos); | |
| 975 | |||
| 976 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 13634 times.
|
13634 | if (g - ctx.next_group >= PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS) |
| 977 | ✗ | fastscan_corrupt(scan, "too many groups in flight"); | |
| 978 | |||
| 979 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1166 times.
|
13634 | fastscan_accumulate_run( |
| 980 | scan, run_codes, off, run, fastscan_group_accum(scan, g)); | ||
| 981 | 13634 | pos += run; | |
| 982 | |||
| 983 |
2/2✓ Branch 0 taken 7437 times.
✓ Branch 1 taken 6197 times.
|
13634 | if (off + run < code_len) |
| 984 | 6966 | off += run; | |
| 985 | else | ||
| 986 | { | ||
| 987 |
2/2✓ Branch 0 taken 10297 times.
✓ Branch 1 taken 9107 times.
|
25377 | fastscan_score_ready(scan, &ctx, g + 1); |
| 988 | 5502 | g++; | |
| 989 | 5502 | off = 0; | |
| 990 | } | ||
| 991 | } | ||
| 992 | |||
| 993 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 19137 times.
|
19137 | if (ctx.next_group != meta_end) |
| 994 | ✗ | fastscan_corrupt(scan, "metadata ahead of its codes"); | |
| 995 | 19137 | scan->fs_next_group = ctx.next_group; | |
| 996 | 19137 | scan->fs_stream_pos = end; | |
| 997 | } | ||
| 998 | |||
| 999 | /* The fastscan pages of a list must leave no group half-read. */ | ||
| 1000 | static void | ||
| 1001 | 81811 | fastscan_check_stream_end(const PrismPostingScan *scan) | |
| 1002 | { | ||
| 1003 | 81811 | uint32_t code_len = VS_FASTSCAN_GROUP_BYTES(scan->dim); | |
| 1004 | |||
| 1005 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 81811 times.
|
81811 | if (scan->fs_stream_pos != (uint64_t)scan->fs_next_group * code_len) |
| 1006 | ✗ | vs_error( | |
| 1007 | VS_EXTENSION_NAME | ||
| 1008 | ": a fastscan posting list ends inside a group (%llu code " | ||
| 1009 | "bytes for %u groups); the index may be corrupted -- " | ||
| 1010 | "REINDEX it", | ||
| 1011 | (unsigned long long)scan->fs_stream_pos, | ||
| 1012 | scan->fs_next_group); | ||
| 1013 | 81811 | } | |
| 1014 |