GCC Code Coverage Report


Directory: src/
File: src/index/posting_scan.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 380 410 92.7%
Functions: 19 20 95.0%
Branches: 253 317 79.8%

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