GCC Code Coverage Report


Directory: src/
File: src/index/posting_insert.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 158 163 96.9%
Functions: 2 2 100.0%
Branches: 92 104 88.5%

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_insert.c - Runtime insert primitives (see header)
6 */
7
8 #include <math.h>
9
10 #include "core/memory.h"
11 #include "index/posting_insert.h"
12
13 bool
14 20125 prism_posting_insert_one(
15 VsStorage *storage,
16 const RaBitQParams *params,
17 Dimension dim,
18 BlockNumber head_blkno,
19 ItemPointerData tid,
20 const float *pt_input,
21 RaBitQScratch *scratch,
22 bool unreachable,
23 bool *head_retired)
24 {
25
2/2
✓ Branch 0 taken 19957 times.
✓ Branch 1 taken 168 times.
20125 if (head_retired != NULL)
26 19957 *head_retired = false;
27
28
4/8
✓ Branch 0 taken 20125 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 168 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 168 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 168 times.
✗ Branch 7 not taken.
20125 if (storage == NULL || params == NULL || pt_input == NULL ||
29
3/4
✓ Branch 0 taken 19957 times.
✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19957 times.
20125 scratch == NULL || head_blkno == InvalidBlockNumber)
30 ✗ return false;
31
32 /*
33 * Phase A: read the head — compute the rotated residual against its
34 * pt_centroid and snapshot the head metadata, then release it (the PG
35 * backing holds only one buffer at a time).
36 */
37 20125 Page head = vs_storage_read_page(storage, head_blkno);
38 20125 const PrismPostingPageOpaque *hop = prism_posting_opaque(head);
39
40 /*
41 * If the head was retired since it was routed to (split away by a
42 * concurrent rebalance), don't insert into a dead chain — report it so the
43 * caller re-routes. Checked here, on the read we already do, so the caller
44 * needn't re-read the head just to test these flags.
45 */
46
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 20124 times.
20125 if (hop->flags & PRISM_POSTING_PAGE_DELETED)
47 {
48 1 vs_storage_release_page(storage, head_blkno);
49
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
1 if (head_retired != NULL)
50 1 *head_retired = true;
51 1 return false;
52 }
53
54 20124 uint32_t cluster_id = hop->cluster_id;
55 20124 BlockNumber tail_blkno = hop->tail_blkno;
56 20124 uint32_t live = hop->live_count;
57
58 /* pt_residual = pt_input - pt_centroid (P^T linear). Reuse scratch
59 * (encode_from_pt only touches scratch->xu_cb). An inline head carries
60 * the whole reference; a spilled one is gathered from its chain after
61 * the head is released, since the storage pins one page at a time. */
62 20124 float *pt_residual = scratch->transformed;
63
3/3
✓ Branch 0 taken 2493 times.
✓ Branch 1 taken 17509 times.
✓ Branch 2 taken 122 times.
20124 if (prism_posting_spilled(dim))
64 {
65 /* The START page's floats off the pinned head, the rest from its
66 * chain. */
67 2539 BlockNumber next = hop->next_blkno;
68
69 2539 memcpy(scratch->residual,
70 2539 prism_posting_pt_centroid(head),
71 2539 (size_t)prism_posting_reference_page_floats(dim, 0) *
72 sizeof(float));
73 2539 vs_storage_release_page(storage, head_blkno);
74 2539 prism_posting_reference_read_rest(
75 storage, head_blkno, next, cluster_id, dim, scratch->residual);
76
3/3
✓ Branch 0 taken 188416 times.
✓ Branch 1 taken 10215470 times.
✓ Branch 2 taken 2493 times.
10406379 for (Dimension i = 0; i < dim; i++)
77 10403840 pt_residual[i] = pt_input[i] - scratch->residual[i];
78 }
79 else
80 {
81 122 const float *pt_cent = prism_posting_pt_centroid(head);
82
2/2
✓ Branch 0 taken 497068 times.
✓ Branch 1 taken 17585 times.
514653 for (Dimension i = 0; i < dim; i++)
83 497068 pt_residual[i] = pt_input[i] - pt_cent[i];
84 17585 vs_storage_release_page(storage, head_blkno);
85 }
86
87 /* Encode relative to the leaf centroid. */
88 20124 RaBitQData *rdata = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
89 20124 vs_rabitq_encode_from_pt(params, pt_residual, rdata, scratch);
90 19956 float f_error =
91 20124 vs_rabitq_derive_f_error(rdata->f_add, rdata->f_rescale, dim);
92
93 /* No defined distance under the index metric: estimated distance
94 * +inf with zero error, so scans prune the entry before it can
95 * enter the top-k threshold heap (see mark_entry_unreachable in
96 * posting_build.c for the full rationale). */
97
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 20123 times.
20124 if (unreachable)
98 {
99 1 rdata->f_add = INFINITY;
100 1 f_error = 0.0f;
101 }
102
103 /*
104 * tail_blkno / live are read straight from the head: the build stamps both
105 * for every cluster (see prism_posting_builder_finish and the parallel
106 * leader's finalize), and inserts maintain them, so a built head always
107 * has a valid tail — no chain walk on the insert path.
108 */
109
110 /*
111 * Phase B: append to the tail. Read it first to check for room (released
112 * before any write); the caller's per-cluster lock prevents a concurrent
113 * fill in between.
114 */
115 20124 Page tcheck = vs_storage_read_page(storage, tail_blkno);
116 /*
117 * Only append into an AoS tail that has room. A FASTSCAN page packs codes
118 * in immutable 32-vector groups, so an insert can never append to it — it
119 * starts a fresh AoS overflow page instead (the scan merges the mixed
120 * chain by per-page format).
121 */
122 20124 bool tail_is_aos = (prism_posting_opaque(tcheck)->flags &
123 PRISM_POSTING_PAGE_FASTSCAN) == 0;
124
4/4
✓ Branch 0 taken 20008 times.
✓ Branch 1 taken 116 times.
✓ Branch 3 taken 354 times.
✓ Branch 4 taken 19654 times.
20124 bool has_room = tail_is_aos && prism_posting_page_has_room(tcheck);
125 20124 vs_storage_release_page(storage, tail_blkno);
126
127 20124 BlockNumber new_tail = tail_blkno;
128 20124 bool head_updated = false;
129
130
2/2
✓ Branch 0 taken 19812 times.
✓ Branch 1 taken 312 times.
20124 if (has_room)
131 {
132 19812 Page wp = vs_storage_write_page(storage, tail_blkno);
133 19812 prism_posting_page_add(
134 wp,
135 dim,
136 tid,
137 rdata->f_add,
138 rdata->f_rescale,
139 f_error,
140 19812 rdata->bits,
141 0);
142
2/2
✓ Branch 0 taken 1428 times.
✓ Branch 1 taken 18384 times.
19812 if (tail_blkno == head_blkno)
143 {
144 /* Tail is the head — fold the metadata update into this write so
145 * single-page clusters cost one head write, not two. */
146 1428 PrismPostingPageOpaque *op = prism_posting_opaque(wp);
147 1428 op->tail_blkno = new_tail;
148 1428 op->live_count = live + 1;
149 1428 head_updated = true;
150 }
151 19812 vs_storage_commit_page(storage, tail_blkno);
152 }
153 else
154 {
155 /* Tail full: build the new overflow page fully and commit it BEFORE
156 * linking, so a crash never points the chain at an uninitialized
157 * page (it leaves at worst an unreferenced page). */
158 306 BlockNumber t2;
159 312 Page np = vs_storage_new_page(storage, &t2);
160 312 prism_posting_page_init(np, cluster_id, dim, 0);
161 312 prism_posting_page_add(
162 np,
163 dim,
164 tid,
165 rdata->f_add,
166 rdata->f_rescale,
167 f_error,
168 312 rdata->bits,
169 0);
170 312 vs_storage_commit_page(storage, t2);
171
172 312 Page lp = vs_storage_write_page(storage, tail_blkno);
173 312 prism_posting_opaque(lp)->next_blkno = t2;
174
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 208 times.
312 if (tail_blkno == head_blkno)
175 {
176 104 PrismPostingPageOpaque *op = prism_posting_opaque(lp);
177 104 op->tail_blkno = t2;
178 104 op->live_count = live + 1;
179 104 head_updated = true;
180 }
181 312 vs_storage_commit_page(storage, tail_blkno);
182 312 new_tail = t2;
183 }
184
185 /* Phase C: update the head metadata when it wasn't folded above. */
186
2/2
✓ Branch 0 taken 18592 times.
✓ Branch 1 taken 1532 times.
20124 if (!head_updated)
187 {
188 18592 Page hw = vs_storage_write_page(storage, head_blkno);
189 18592 PrismPostingPageOpaque *op = prism_posting_opaque(hw);
190 18592 op->tail_blkno = new_tail;
191 18592 op->live_count = live + 1;
192 18592 vs_storage_commit_page(storage, head_blkno);
193 }
194
195 168 return true;
196 }
197
198 /*
199 * Contract is in the header. Implementation notes not stated there: each page
200 * is read-scanned first and only write-locked / WAL-logged when it actually
201 * has a dead entry to mark, so vacuuming a chain with no dead tuples dirties
202 * nothing. Marking is idempotent — an already-deleted entry is skipped, not
203 * recounted — so a repeated VACUUM over the same dead TIDs is a no-op.
204 */
205 uint32_t
206 365 prism_posting_tombstone_chain(
207 VsStorage *storage,
208 Dimension dim,
209 BlockNumber head_blkno,
210 bool (*is_dead)(ItemPointerData tid, void *state),
211 void *state)
212 {
213
3/6
✓ Branch 0 taken 365 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 365 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 20 times.
365 if (storage == NULL || is_dead == NULL || head_blkno == InvalidBlockNumber)
214 ✗ return 0;
215
216 20 uint32_t total_marked = 0;
217 20 BlockNumber blk = head_blkno;
218
219
2/2
✓ Branch 0 taken 904 times.
✓ Branch 1 taken 365 times.
1269 while (blk != InvalidBlockNumber)
220 {
221 /*
222 * Phase 1: under a SHARE lock, scan the page's entries to find whether
223 * it has any dead entry that still needs marking. This is only a probe
224 * — nothing is mutated — so a page with no dead tuples is never
225 * dirtied or WAL-logged. Both formats early-break at the first entry
226 * that needs marking; they only need to know "is there work?" here.
227 */
228 904 Page p = vs_storage_read_page(storage, blk);
229 904 const PrismPostingPageOpaque *op = prism_posting_opaque(p);
230 904 BlockNumber next = op->next_blkno;
231 904 uint16_t flags = op->flags;
232 904 uint32_t n = op->entry_count;
233
234 904 prism_posting_check_count(blk, p, dim);
235
236 /* Already fully tombstoned: nothing to mark, and skip so its entries
237 * aren't counted into the live_count decrement twice. */
238
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 904 times.
904 if (flags & PRISM_POSTING_PAGE_TOMBSTONED)
239 {
240 ✗ vs_storage_release_page(storage, blk);
241 ✗ blk = next;
242 ✗ continue;
243 }
244
245 904 bool is_fastscan = (flags & PRISM_POSTING_PAGE_FASTSCAN) != 0;
246 904 char *content = prism_posting_page_content(p, dim);
247 904 bool needs_mark = false; /* has a not-yet-marked dead entry */
248
249
2/2
✓ Branch 0 taken 701 times.
✓ Branch 1 taken 203 times.
904 if (!is_fastscan)
250 {
251
2/2
✓ Branch 0 taken 7248 times.
✓ Branch 1 taken 380 times.
7628 for (uint32_t i = 0; i < n; i++)
252 {
253 7224 PrismPostingEntryHeader *h =
254
2/2
✓ Branch 0 taken 7208 times.
✓ Branch 1 taken 16 times.
7248 prism_posting_entry_at(content, i, dim);
255
4/4
✓ Branch 0 taken 7226 times.
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 6899 times.
✓ Branch 3 taken 327 times.
14474 if (!(h->meta.flags & PRISM_POSTING_FLAG_DELETED) &&
256 7226 is_dead(h->meta.tid, state))
257 {
258 6 needs_mark = true;
259 6 break;
260 }
261 }
262 }
263 else
264 {
265 203 uint32_t ngroups = (n + VS_FASTSCAN_GROUP - 1) / VS_FASTSCAN_GROUP;
266
4/4
✓ Branch 0 taken 236 times.
✓ Branch 1 taken 193 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 10 times.
429 for (uint32_t g = 0; g < ngroups && !needs_mark; g++)
267 {
268 226 uint32_t g_count = n - g * VS_FASTSCAN_GROUP;
269
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 10 times.
226 if (g_count > VS_FASTSCAN_GROUP)
270 42 g_count = VS_FASTSCAN_GROUP;
271 226 uint32_t mask =
272 226 *prism_fastscan_group_tombstone_mask(content, g);
273 226 ItemPointerData *tids = prism_fastscan_group_tids(content, g);
274
2/2
✓ Branch 0 taken 3499 times.
✓ Branch 1 taken 138 times.
3637 for (uint32_t v = 0; v < g_count; v++)
275
5/5
✓ Branch 0 taken 2155 times.
✓ Branch 1 taken 1338 times.
✓ Branch 2 taken 2087 times.
✓ Branch 3 taken 88 times.
✓ Branch 4 taken 1324 times.
6992 if (!prism_fastscan_lane_is_tombstoned(mask, v) &&
276 3493 is_dead(tids[v], state))
277 {
278 14 needs_mark = true;
279 14 break;
280 }
281 }
282 }
283 904 vs_storage_release_page(storage, blk);
284
285 /*
286 * Phase 2: only if phase 1 found work, take the EXCLUSIVE write lock
287 * (which WAL-logs the page on commit) and mark the dead entries. The
288 * share lock was dropped above and PG has no atomic lock upgrade, so
289 * the page may have changed; re-derive everything from scratch here
290 * (re-read entry_count, re-test is_dead and the dead marker) rather
291 * than trusting phase 1's findings. This makes marking idempotent.
292 */
293
2/2
✓ Branch 0 taken 507 times.
✓ Branch 1 taken 397 times.
904 if (needs_mark)
294 {
295 409 Page wp = vs_storage_write_page(storage, blk);
296 409 PrismPostingPageOpaque *wop = prism_posting_opaque(wp);
297 409 char *c = prism_posting_page_content(wp, dim);
298 409 uint32_t deleted_on_page = 0;
299
300 /* Read the format fresh rather than trust phase 1's is_fastscan,
301 * matching the "re-derive everything from scratch" rule above --
302 * a page's format never actually changes today, but this way the
303 * code doesn't quietly rely on that to stay correct. */
304
2/2
✓ Branch 0 taken 321 times.
✓ Branch 1 taken 88 times.
409 if (!(wop->flags & PRISM_POSTING_PAGE_FASTSCAN))
305 {
306
2/2
✓ Branch 0 taken 10125 times.
✓ Branch 1 taken 321 times.
10446 for (uint32_t i = 0; i < wop->entry_count; i++)
307 {
308 10077 PrismPostingEntryHeader *h =
309
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 10017 times.
10125 prism_posting_entry_at(c, i, dim);
310
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 10065 times.
10125 if (h->meta.flags & PRISM_POSTING_FLAG_DELETED)
311 {
312 60 deleted_on_page++;
313 60 continue;
314 }
315
2/2
✓ Branch 1 taken 3740 times.
✓ Branch 2 taken 6325 times.
10065 if (is_dead(h->meta.tid, state))
316 {
317 3740 h->meta.flags |= PRISM_POSTING_FLAG_DELETED;
318 3740 total_marked++;
319 3740 deleted_on_page++;
320 }
321 }
322 }
323 else
324 {
325 88 uint32_t wn = wop->entry_count;
326 88 uint32_t ngroups = (wn + VS_FASTSCAN_GROUP - 1) /
327 VS_FASTSCAN_GROUP;
328
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 88 times.
304 for (uint32_t g = 0; g < ngroups; g++)
329 {
330 216 uint32_t g_count = wn - g * VS_FASTSCAN_GROUP;
331
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 14 times.
216 if (g_count > VS_FASTSCAN_GROUP)
332 52 g_count = VS_FASTSCAN_GROUP;
333 150 uint32_t *mask_p =
334 216 prism_fastscan_group_tombstone_mask(c, g);
335 216 uint32_t mask = *mask_p;
336 216 ItemPointerData *tids = prism_fastscan_group_tids(c, g);
337
2/2
✓ Branch 0 taken 6135 times.
✓ Branch 1 taken 216 times.
6351 for (uint32_t v = 0; v < g_count; v++)
338 {
339
3/3
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 4159 times.
✓ Branch 2 taken 1936 times.
6135 if (prism_fastscan_lane_is_tombstoned(mask, v))
340 {
341 40 deleted_on_page++;
342 40 continue;
343 }
344
2/2
✓ Branch 1 taken 2147 times.
✓ Branch 2 taken 3948 times.
6095 if (is_dead(tids[v], state))
345 {
346 2147 mask = prism_fastscan_lane_set_tombstone(mask, v);
347 2147 total_marked++;
348 2147 deleted_on_page++;
349 }
350 }
351 216 *mask_p = mask;
352 }
353 }
354 /* Whole page now dead: flag it so the scan skips its scoring. */
355
3/4
✓ Branch 0 taken 409 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 125 times.
✓ Branch 3 taken 284 times.
409 if (wop->entry_count > 0 && deleted_on_page == wop->entry_count)
356 125 wop->flags |= PRISM_POSTING_PAGE_TOMBSTONED;
357 409 vs_storage_commit_page(storage, blk);
358 }
359
360 28 blk = next;
361 }
362
363 /* Keep the head's live_count current (one head write per cluster). It is
364 * stamped at build and maintained by inserts, so it is always meaningful
365 * here; clamp defensively. */
366
2/2
✓ Branch 0 taken 271 times.
✓ Branch 1 taken 94 times.
365 if (total_marked > 0)
367 {
368 271 Page hw = vs_storage_write_page(storage, head_blkno);
369 271 PrismPostingPageOpaque *op = prism_posting_opaque(hw);
370 542 op->live_count = (op->live_count >= total_marked)
371 16 ? op->live_count - total_marked
372
1/2
✓ Branch 0 taken 271 times.
✗ Branch 1 not taken.
271 : 0;
373 271 vs_storage_commit_page(storage, head_blkno);
374 }
375
376 20 return total_marked;
377 }
378