GCC Code Coverage Report

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