GCC Code Coverage Report

Directory: src/
File: src/index/posting_insert.c
Date: 2026-10-23 09:17:32
Exec Total Coverage
Lines: 151 156 96.8%
Functions: 2 2 100.0%
Branches: 86 98 87.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_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 17542 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 17420 times.
✓ Branch 1 taken 122 times.
 17542 if (head_retired != NULL)
26 17420 *head_retired = false;
27
28
4/8
✓ Branch 0 taken 17542 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 122 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 122 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 122 times.
✗ Branch 7 not taken.
 17542 if (storage == NULL || params == NULL || pt_input == NULL ||
29
3/4
✓ Branch 0 taken 17420 times.
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 17420 times.
 17542 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 17542 Page head = vs_storage_read_page(storage, head_blkno);
38 17542 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 17541 times.
 17542 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 17541 uint32_t cluster_id = hop->cluster_id;
55 17541 BlockNumber tail_blkno = hop->tail_blkno;
56 17541 uint32_t live = hop->live_count;
57 17541 const float *pt_cent = prism_posting_pt_centroid(head);
58
59 /* pt_residual = pt_input - pt_centroid (P^T linear). Reuse scratch
60 * (encode_from_pt only touches scratch->xu_cb). */
61 17541 float *pt_residual = scratch->transformed;
62
2/2
✓ Branch 0 taken 462855 times.
✓ Branch 1 taken 17541 times.
 480396 for (Dimension i = 0; i < dim; i++)
63 462855 pt_residual[i] = pt_input[i] - pt_cent[i];
64
65 17541 vs_storage_release_page(storage, head_blkno);
66
67 /* Encode relative to the leaf centroid. */
68 17541 RaBitQData *rdata = vs_alloc(VS_RABITQ_DATA_SIZE(dim));
69 17541 vs_rabitq_encode_from_pt(params, pt_residual, rdata, scratch);
70 17419 float f_error =
71 17541 vs_rabitq_derive_f_error(rdata->f_add, rdata->f_rescale, dim);
72
73 /* No defined distance under the index metric: estimated distance
74 * +inf with zero error, so scans prune the entry before it can
75 * enter the top-k threshold heap (see mark_entry_unreachable in
76 * posting_build.c for the full rationale). */
77
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 17540 times.
 17541 if (unreachable)
78 {
79 1 rdata->f_add = INFINITY;
80 1 f_error = 0.0f;
81 }
82
83 /*
84 * tail_blkno / live are read straight from the head: the build stamps both
85 * for every cluster (see prism_posting_builder_finish and the parallel
86 * leader's finalize), and inserts maintain them, so a built head always
87 * has a valid tail — no chain walk on the insert path.
88 */
89
90 /*
91 * Phase B: append to the tail. Read it first to check for room (released
92 * before any write); the caller's per-cluster lock prevents a concurrent
93 * fill in between.
94 */
95 17541 Page tcheck = vs_storage_read_page(storage, tail_blkno);
96 /*
97 * Only append into an AoS tail that has room. A FASTSCAN page packs codes
98 * in immutable 32-vector groups, so an insert can never append to it — it
99 * starts a fresh AoS overflow page instead (the scan merges the mixed
100 * chain by per-page format).
101 */
102 17541 bool tail_is_aos = (prism_posting_opaque(tcheck)->flags &
103 PRISM_POSTING_PAGE_FASTSCAN) == 0;
104
4/4
✓ Branch 0 taken 17443 times.
✓ Branch 1 taken 98 times.
✓ Branch 3 taken 146 times.
✓ Branch 4 taken 17297 times.
 17541 bool has_room = tail_is_aos && prism_posting_page_has_room(tcheck);
105 17541 vs_storage_release_page(storage, tail_blkno);
106
107 17541 BlockNumber new_tail = tail_blkno;
108 17541 bool head_updated = false;
109
110
2/2
✓ Branch 0 taken 17413 times.
✓ Branch 1 taken 128 times.
 17541 if (has_room)
111 {
112 17413 Page wp = vs_storage_write_page(storage, tail_blkno);
113 17413 prism_posting_page_add(
114 wp,
115 dim,
116 tid,
117 rdata->f_add,
118 rdata->f_rescale,
119 f_error,
120 17413 rdata->bits,
121 0);
122
2/2
✓ Branch 0 taken 1427 times.
✓ Branch 1 taken 15986 times.
 17413 if (tail_blkno == head_blkno)
123 {
124 /* Tail is the head — fold the metadata update into this write so
125 * single-page clusters cost one head write, not two. */
126 1427 PrismPostingPageOpaque *op = prism_posting_opaque(wp);
127 1427 op->tail_blkno = new_tail;
128 1427 op->live_count = live + 1;
129 1427 head_updated = true;
130 }
131 17413 vs_storage_commit_page(storage, tail_blkno);
132 }
133 else
134 {
135 /* Tail full: build the new overflow page fully and commit it BEFORE
136 * linking, so a crash never points the chain at an uninitialized
137 * page (it leaves at worst an unreferenced page). */
138 124 BlockNumber t2;
139 128 Page np = vs_storage_new_page(storage, &t2);
140 128 prism_posting_page_init(
141 np, cluster_id, dim, PRISM_POSTING_PAGE_OVERFLOW);
142 128 prism_posting_page_add(
143 np,
144 dim,
145 tid,
146 rdata->f_add,
147 rdata->f_rescale,
148 f_error,
149 128 rdata->bits,
150 0);
151 128 vs_storage_commit_page(storage, t2);
152
153 128 Page lp = vs_storage_write_page(storage, tail_blkno);
154 128 prism_posting_opaque(lp)->next_blkno = t2;
155
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 25 times.
 128 if (tail_blkno == head_blkno)
156 {
157 103 PrismPostingPageOpaque *op = prism_posting_opaque(lp);
158 103 op->tail_blkno = t2;
159 103 op->live_count = live + 1;
160 103 head_updated = true;
161 }
162 128 vs_storage_commit_page(storage, tail_blkno);
163 128 new_tail = t2;
164 }
165
166 /* Phase C: update the head metadata when it wasn't folded above. */
167
2/2
✓ Branch 0 taken 16011 times.
✓ Branch 1 taken 1530 times.
 17541 if (!head_updated)
168 {
169 16011 Page hw = vs_storage_write_page(storage, head_blkno);
170 16011 PrismPostingPageOpaque *op = prism_posting_opaque(hw);
171 16011 op->tail_blkno = new_tail;
172 16011 op->live_count = live + 1;
173 16011 vs_storage_commit_page(storage, head_blkno);
174 }
175
176 122 return true;
177 }
178
179 /*
180 * Contract is in the header. Implementation notes not stated there: each page
181 * is read-scanned first and only write-locked / WAL-logged when it actually
182 * has a dead entry to mark, so vacuuming a chain with no dead tuples dirties
183 * nothing. Marking is idempotent — an already-deleted entry is skipped, not
184 * recounted — so a repeated VACUUM over the same dead TIDs is a no-op.
185 */
186 uint32_t
187 283 prism_posting_tombstone_chain(
188 VsStorage *storage,
189 Dimension dim,
190 BlockNumber head_blkno,
191 bool (*is_dead)(ItemPointerData tid, void *state),
192 void *state)
193 {
194
3/6
✓ Branch 0 taken 283 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 283 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 18 times.
 283 if (storage == NULL || is_dead == NULL || head_blkno == InvalidBlockNumber)
195 ✗ return 0;
196
197 18 uint32_t total_marked = 0;
198 18 BlockNumber blk = head_blkno;
199
200
2/2
✓ Branch 0 taken 321 times.
✓ Branch 1 taken 283 times.
 604 while (blk != InvalidBlockNumber)
201 {
202 /*
203 * Phase 1: under a SHARE lock, scan the page's entries to find whether
204 * it has any dead entry that still needs marking. This is only a probe
205 * — nothing is mutated — so a page with no dead tuples is never
206 * dirtied or WAL-logged. Both formats early-break at the first entry
207 * that needs marking; they only need to know "is there work?" here.
208 */
209 321 Page p = vs_storage_read_page(storage, blk);
210 321 const PrismPostingPageOpaque *op = prism_posting_opaque(p);
211 321 BlockNumber next = op->next_blkno;
212 321 uint16_t flags = op->flags;
213 321 uint32_t n = op->entry_count;
214
215 321 prism_posting_check_count(blk, op, dim);
216
217 /* Already fully tombstoned: nothing to mark, and skip so its entries
218 * aren't counted into the live_count decrement twice. */
219
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 321 times.
 321 if (flags & PRISM_POSTING_PAGE_TOMBSTONED)
220 {
221 ✗ vs_storage_release_page(storage, blk);
222 ✗ blk = next;
223 ✗ continue;
224 }
225
226 321 bool is_fastscan = (flags & PRISM_POSTING_PAGE_FASTSCAN) != 0;
227 321 char *content = prism_posting_page_content(p, dim);
228 321 bool needs_mark = false; /* has a not-yet-marked dead entry */
229
230
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 97 times.
 321 if (!is_fastscan)
231 {
232
2/2
✓ Branch 0 taken 4319 times.
✓ Branch 1 taken 51 times.
 4370 for (uint32_t i = 0; i < n; i++)
233 {
234 4295 PrismPostingEntryHeader *h =
235
2/2
✓ Branch 0 taken 4287 times.
✓ Branch 1 taken 8 times.
 4319 prism_posting_entry_at(content, i, dim);
236
4/4
✓ Branch 0 taken 4305 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 4126 times.
✓ Branch 3 taken 179 times.
 8624 if (!(h->meta.flags & PRISM_POSTING_FLAG_DELETED) &&
237 4305 is_dead(h->meta.tid, state))
238 {
239 6 needs_mark = true;
240 6 break;
241 }
242 }
243 }
244 else
245 {
246 97 uint32_t ngroups = (n + VS_FASTSCAN_GROUP - 1) / VS_FASTSCAN_GROUP;
247
4/4
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 87 times.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 10 times.
 267 for (uint32_t g = 0; g < ngroups && !needs_mark; g++)
248 {
249 170 uint32_t g_count = n - g * VS_FASTSCAN_GROUP;
250
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 6 times.
 170 if (g_count > VS_FASTSCAN_GROUP)
251 42 g_count = VS_FASTSCAN_GROUP;
252 170 uint32_t mask =
253 170 *prism_fastscan_group_tombstone_mask(content, g, dim);
254 122 ItemPointerData *tids =
255 170 prism_fastscan_group_tids(content, g, dim);
256
2/2
✓ Branch 0 taken 3289 times.
✓ Branch 1 taken 134 times.
 3423 for (uint32_t v = 0; v < g_count; v++)
257
5/5
✓ Branch 0 taken 2011 times.
✓ Branch 1 taken 1272 times.
✓ Branch 2 taken 1993 times.
✓ Branch 3 taken 36 times.
✓ Branch 4 taken 1260 times.
 6572 if (!prism_fastscan_lane_is_tombstoned(mask, v) &&
258 3283 is_dead(tids[v], state))
259 {
260 12 needs_mark = true;
261 12 break;
262 }
263 }
264 }
265 321 vs_storage_release_page(storage, blk);
266
267 /*
268 * Phase 2: only if phase 1 found work, take the EXCLUSIVE write lock
269 * (which WAL-logs the page on commit) and mark the dead entries. The
270 * share lock was dropped above and PG has no atomic lock upgrade, so
271 * the page may have changed; re-derive everything from scratch here
272 * (re-read entry_count, re-test is_dead and the dead marker) rather
273 * than trusting phase 1's findings. This makes marking idempotent.
274 */
275
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 197 times.
 321 if (needs_mark)
276 {
277 209 Page wp = vs_storage_write_page(storage, blk);
278 209 PrismPostingPageOpaque *wop = prism_posting_opaque(wp);
279 209 char *c = prism_posting_page_content(wp, dim);
280 209 uint32_t deleted_on_page = 0;
281
282 /* Read the format fresh rather than trust phase 1's is_fastscan,
283 * matching the "re-derive everything from scratch" rule above --
284 * a page's format never actually changes today, but this way the
285 * code doesn't quietly rely on that to stay correct. */
286
2/2
✓ Branch 0 taken 173 times.
✓ Branch 1 taken 36 times.
 209 if (!(wop->flags & PRISM_POSTING_PAGE_FASTSCAN))
287 {
288
2/2
✓ Branch 0 taken 8098 times.
✓ Branch 1 taken 173 times.
 8271 for (uint32_t i = 0; i < wop->entry_count; i++)
289 {
290 8050 PrismPostingEntryHeader *h =
291
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8020 times.
 8098 prism_posting_entry_at(c, i, dim);
292
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8068 times.
 8098 if (h->meta.flags & PRISM_POSTING_FLAG_DELETED)
293 {
294 30 deleted_on_page++;
295 30 continue;
296 }
297
2/2
✓ Branch 1 taken 2368 times.
✓ Branch 2 taken 5700 times.
 8068 if (is_dead(h->meta.tid, state))
298 {
299 2368 h->meta.flags |= PRISM_POSTING_FLAG_DELETED;
300 2368 total_marked++;
301 2368 deleted_on_page++;
302 }
303 }
304 }
305 else
306 {
307 36 uint32_t wn = wop->entry_count;
308 36 uint32_t ngroups = (wn + VS_FASTSCAN_GROUP - 1) /
309 VS_FASTSCAN_GROUP;
310
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 36 times.
 192 for (uint32_t g = 0; g < ngroups; g++)
311 {
312 156 uint32_t g_count = wn - g * VS_FASTSCAN_GROUP;
313
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 12 times.
 156 if (g_count > VS_FASTSCAN_GROUP)
314 52 g_count = VS_FASTSCAN_GROUP;
315 92 uint32_t *mask_p =
316 156 prism_fastscan_group_tombstone_mask(c, g, dim);
317 156 uint32_t mask = *mask_p;
318 92 ItemPointerData *tids =
319 156 prism_fastscan_group_tids(c, g, dim);
320
2/2
✓ Branch 0 taken 4425 times.
✓ Branch 1 taken 156 times.
 4581 for (uint32_t v = 0; v < g_count; v++)
321 {
322
3/3
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 2533 times.
✓ Branch 2 taken 1872 times.
 4425 if (prism_fastscan_lane_is_tombstoned(mask, v))
323 {
324 20 deleted_on_page++;
325 20 continue;
326 }
327
2/2
✓ Branch 1 taken 832 times.
✓ Branch 2 taken 3573 times.
 4405 if (is_dead(tids[v], state))
328 {
329 832 mask = prism_fastscan_lane_set_tombstone(mask, v);
330 832 total_marked++;
331 832 deleted_on_page++;
332 }
333 }
334 156 *mask_p = mask;
335 }
336 }
337 /* Whole page now dead: flag it so the scan skips its scoring. */
338
3/4
✓ Branch 0 taken 209 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 21 times.
✓ Branch 3 taken 188 times.
 209 if (wop->entry_count > 0 && deleted_on_page == wop->entry_count)
339 21 wop->flags |= PRISM_POSTING_PAGE_TOMBSTONED;
340 209 vs_storage_commit_page(storage, blk);
341 }
342
343 24 blk = next;
344 }
345
346 /* Keep the head's live_count current (one head write per cluster). It is
347 * stamped at build and maintained by inserts, so it is always meaningful
348 * here; clamp defensively. */
349
2/2
✓ Branch 0 taken 205 times.
✓ Branch 1 taken 78 times.
 283 if (total_marked > 0)
350 {
351 205 Page hw = vs_storage_write_page(storage, head_blkno);
352 205 PrismPostingPageOpaque *op = prism_posting_opaque(hw);
353 410 op->live_count = (op->live_count >= total_marked)
354 14 ? op->live_count - total_marked
355
1/2
✓ Branch 0 taken 205 times.
✗ Branch 1 not taken.
 205 : 0;
356 205 vs_storage_commit_page(storage, head_blkno);
357 }
358
359 18 return total_marked;
360 }
361