GCC Code Coverage Report


Directory: src/
File: src/index/centroid_build.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 103 115 89.6%
Functions: 2 2 100.0%
Branches: 40 58 69.0%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * centroid_build.c - Generic centroid page writer
6 *
7 * Writes centroid entries to linked pages via VsStorage. Format-
8 * agnostic: page format determines metadata and data sizes.
9 */
10
11 #include "vs_config.h"
12
13 #include <math.h>
14 #include <string.h>
15
16 #include "core/log.h"
17 #include "core/memory.h"
18 #include "index/centroid_build.h"
19 #include "quant/fastscan.h"
20 #include "quant/rabitq.h"
21
22 BlockNumber
23 886 prism_centroid_write_pages(
24 VsStorage *storage,
25 Dimension dim,
26 uint32_t nlist,
27 PrismCentroidFormat fmt,
28 uint8_t level,
29 uint16_t flags,
30 uint16_t child_count,
31 CentroidEncoder *encoder,
32 const BlockNumber *child_blknos,
33 const float *pt_centroids,
34 BlockNumber start_blkno)
35 {
36 886 bool reserved = (start_blkno != InvalidBlockNumber);
37
1/2
✓ Branch 0 taken 684 times.
✗ Branch 1 not taken.
886 BlockNumber first_blkno = reserved ? start_blkno : InvalidBlockNumber;
38 886 BlockNumber prev_blkno = InvalidBlockNumber;
39 886 BlockNumber next_blkno = start_blkno;
40 886 Page cur_page = NULL;
41 886 BlockNumber cur_blkno = InvalidBlockNumber;
42
43 202 (void)pt_centroids; /* pt_centroids stored on posting pages, not here */
44
45
2/2
✓ Branch 0 taken 5118 times.
✓ Branch 1 taken 886 times.
6004 for (uint32_t i = 0; i < nlist; i++)
46 {
47 /* Allocate a new page if needed */
48
4/4
✓ Branch 0 taken 4232 times.
✓ Branch 1 taken 886 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 1202 times.
6324 if (cur_page == NULL ||
49
2/2
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 3002 times.
4232 !prism_centroid_page_has_room(cur_page, dim, false))
50 {
51 /* Commit the previous page if any */
52
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 684 times.
712 if (cur_page != NULL)
53 28 vs_storage_commit_page(storage, cur_blkno);
54
55
1/2
✓ Branch 0 taken 914 times.
✗ Branch 1 not taken.
914 if (reserved)
56 {
57 914 cur_blkno = next_blkno++;
58 914 cur_page = vs_storage_write_page(storage, cur_blkno);
59 }
60 else
61 {
62 ✗ cur_page = vs_storage_new_page(storage, &cur_blkno);
63 }
64 914 prism_centroid_page_init_fmt(cur_page, level, fmt);
65
66
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 914 times.
914 if (first_blkno == InvalidBlockNumber)
67 ✗ first_blkno = cur_blkno;
68
69 /* Link previous page to this one. The storage layer
70 * holds at most one buffer, so we commit the new page
71 * first, reopen the previous page to set next_blkno,
72 * then reopen the new page. */
73
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 886 times.
914 if (prev_blkno != InvalidBlockNumber)
74 {
75 28 vs_storage_commit_page(storage, cur_blkno);
76
77 28 Page prev_page = vs_storage_write_page(storage, prev_blkno);
78 28 PRISM_CENTROID_OPAQUE(prev_page)->next_blkno = cur_blkno;
79 28 vs_storage_commit_page(storage, prev_blkno);
80
81 28 cur_page = vs_storage_write_page(storage, cur_blkno);
82 }
83
84 914 prev_blkno = cur_blkno;
85 }
86
87 5118 BlockNumber entry_child = child_blknos != NULL ? child_blknos[i]
88
1/2
✓ Branch 0 taken 5118 times.
✗ Branch 1 not taken.
5118 : InvalidBlockNumber;
89
90 5118 void *dest = prism_centroid_page_add_entry_begin(
91 cur_page, dim, entry_child, child_count, flags);
92
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5118 times.
5118 if (dest == NULL)
93 ✗ vs_error(
94 VS_EXTENSION_NAME
95 ": a centroid entry (format %d) does not fit a page at "
96 "%u dimensions",
97 (int)fmt,
98 (unsigned)dim);
99 5118 encoder->ops->encode_into(encoder, i, dest);
100 }
101
102 /* Commit last page */
103
1/2
✓ Branch 0 taken 886 times.
✗ Branch 1 not taken.
886 if (cur_page != NULL)
104 886 vs_storage_commit_page(storage, cur_blkno);
105
106 886 return first_blkno;
107 }
108
109 /* ----------------------------------------------------------------
110 * FASTSCAN centroid writer
111 *
112 * Walks the input centroid list in 32-vector groups. For each group:
113 * 1. Encode each centroid with vs_rabitq_encode_into to get
114 * f_add, f_rescale, and 1-bit packed code bytes.
115 * 2. Derive f_error from (f_add, f_rescale).
116 * 3. Repack the bits into the kPerm0 layout that
117 * vs_fastscan_accumulate_hacc expects, and place the per-
118 * group f_add / f_rescale / f_error / child_blkno arrays in
119 * the group section.
120 *
121 * One page holds `groups_per_page` groups; once a page is full we
122 * commit it and chain via next_blkno, the same way the RABITQ
123 * writer above does. Partial trailing group is padded with
124 * InvalidBlockNumber and zero codes.
125 * ---------------------------------------------------------------- */
126
127 BlockNumber
128 1412 prism_centroid_write_fastscan_pages(
129 VsStorage *storage,
130 Dimension dim,
131 uint32_t nlist,
132 uint8_t level,
133 uint16_t flags,
134 const RaBitQParams *params,
135 const float *vectors,
136 const float *global_mean,
137 const BlockNumber *child_blknos,
138 BlockNumber start_blkno)
139 {
140 1304 (void)flags; /* per-entry flags not stored in FASTSCAN format */
141
142 1412 uint32_t packed_bytes = (dim + 7) / 8;
143
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1304 times.
1412 uint32_t groups_per_page = prism_centroid_fastscan_max_groups(dim);
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1412 times.
1412 if (groups_per_page == 0)
145 ✗ groups_per_page = 1; /* defensive — bigger dims may need split */
146
147 1412 uint32_t ngroups = (nlist + VS_FASTSCAN_GROUP - 1) / VS_FASTSCAN_GROUP;
148
149 /* Scratch for one group's RaBitQ data (32 entries). */
150 1412 size_t rdata_size = VS_RABITQ_DATA_SIZE(dim);
151 1412 uint8_t *rdata_buf = vs_alloc((size_t)VS_FASTSCAN_GROUP * rdata_size);
152 1412 uint8_t *bits_buf = vs_alloc((size_t)VS_FASTSCAN_GROUP * packed_bytes);
153
154 1412 Vec32Ref mref = {.data = global_mean, .dim = dim};
155
156 1412 bool reserved = (start_blkno != InvalidBlockNumber);
157
1/2
✓ Branch 0 taken 108 times.
✗ Branch 1 not taken.
1412 BlockNumber first_blkno = reserved ? start_blkno : InvalidBlockNumber;
158 1412 BlockNumber prev_blkno = InvalidBlockNumber;
159 1412 BlockNumber next_blkno = start_blkno;
160 1412 Page cur_page = NULL;
161 1412 BlockNumber cur_blkno = InvalidBlockNumber;
162 1412 uint32_t cur_ngroups = 0;
163
164
2/2
✓ Branch 0 taken 1436 times.
✓ Branch 1 taken 1412 times.
2848 for (uint32_t g = 0; g < ngroups; g++)
165 {
166 /* Open a fresh page when needed */
167
3/4
✓ Branch 0 taken 1328 times.
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
1436 if (cur_page == NULL || cur_ngroups == groups_per_page)
168 {
169
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1412 times.
1412 if (cur_page != NULL)
170 ✗ vs_storage_commit_page(storage, cur_blkno);
171
172
1/2
✓ Branch 0 taken 1412 times.
✗ Branch 1 not taken.
1412 if (reserved)
173 {
174 1412 cur_blkno = next_blkno++;
175 1412 cur_page = vs_storage_write_page(storage, cur_blkno);
176 }
177 else
178 ✗ cur_page = vs_storage_new_page(storage, &cur_blkno);
179
180 1412 prism_centroid_page_init_fmt(
181 cur_page, level, PRISM_CENTROID_FMT_FASTSCAN);
182
183
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1412 times.
1412 if (first_blkno == InvalidBlockNumber)
184 ✗ first_blkno = cur_blkno;
185
186
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1412 times.
1412 if (prev_blkno != InvalidBlockNumber)
187 {
188 ✗ vs_storage_commit_page(storage, cur_blkno);
189 ✗ Page prev = vs_storage_write_page(storage, prev_blkno);
190 ✗ PRISM_CENTROID_OPAQUE(prev)->next_blkno = cur_blkno;
191 ✗ vs_storage_commit_page(storage, prev_blkno);
192 ✗ cur_page = vs_storage_write_page(storage, cur_blkno);
193 }
194
195 1412 prev_blkno = cur_blkno;
196 1412 cur_ngroups = 0;
197 }
198
199 /* Encode this group's 32 entries (or fewer for the last). */
200 1436 uint32_t g_start = g * VS_FASTSCAN_GROUP;
201 1436 uint32_t g_count = nlist - g_start;
202
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 108 times.
1436 if (g_count > VS_FASTSCAN_GROUP)
203 24 g_count = VS_FASTSCAN_GROUP;
204
205 /* Get per-entry RaBitQ encoding into rdata_buf, copy bits
206 * out into a flat packed_bytes-stride array for the packer. */
207
2/2
✓ Branch 0 taken 10945 times.
✓ Branch 1 taken 1436 times.
12381 for (uint32_t v = 0; v < g_count; v++)
208 {
209 10945 Vec32Ref vref = {
210 10945 .data = vectors + (size_t)(g_start + v) * dim,
211 .dim = dim,
212 };
213 10945 RaBitQData *d = (RaBitQData *)(rdata_buf + (size_t)v * rdata_size);
214 10945 vs_rabitq_encode_into(params, vref, mref, d);
215 10945 memcpy(bits_buf + (size_t)v * packed_bytes, d->bits, packed_bytes);
216 }
217
218 /* Write per-entry scalars + child_blkno arrays into the
219 * group section, then pack codes. */
220 1436 uint32_t cur_group_idx = cur_ngroups;
221 1436 char *content = (char *)PageGetContents(cur_page);
222
223 1436 BlockNumber *child = prism_centroid_fastscan_group_child(
224 content, cur_group_idx, dim);
225 1436 float *f_add_arr = prism_centroid_fastscan_group_f_add(
226 content, cur_group_idx, dim);
227 1436 float *f_rescale_arr = prism_centroid_fastscan_group_f_rescale(
228 content, cur_group_idx, dim);
229 1436 float *f_error_arr = prism_centroid_fastscan_group_f_error(
230 content, cur_group_idx, dim);
231 1436 uint8_t *codes = prism_centroid_fastscan_group_codes(
232 content, cur_group_idx, dim);
233
234
2/2
✓ Branch 0 taken 45952 times.
✓ Branch 1 taken 1436 times.
47388 for (uint32_t v = 0; v < VS_FASTSCAN_GROUP; v++)
235 {
236
2/2
✓ Branch 0 taken 10945 times.
✓ Branch 1 taken 35007 times.
45952 if (v < g_count)
237 {
238 10945 const RaBitQData *d = (const RaBitQData *)(rdata_buf +
239 10945 (size_t)v *
240 rdata_size);
241 31501 child[v] = child_blknos != NULL ? child_blknos[g_start + v]
242
1/2
✓ Branch 0 taken 10945 times.
✗ Branch 1 not taken.
10945 : InvalidBlockNumber;
243 10945 f_add_arr[v] = d->f_add;
244 10945 f_rescale_arr[v] = d->f_rescale;
245 10945 f_error_arr[v] =
246 10945 vs_rabitq_derive_f_error(d->f_add, d->f_rescale, dim);
247 }
248 else
249 {
250 35007 child[v] = InvalidBlockNumber;
251 35007 f_add_arr[v] = 0.0f;
252 35007 f_rescale_arr[v] = 0.0f;
253 35007 f_error_arr[v] = 0.0f;
254 }
255 }
256
257 1436 vs_fastscan_pack_codes(bits_buf, g_count, dim, codes);
258
259 1436 PrismCentroidPageOpaque *op = PRISM_CENTROID_OPAQUE(cur_page);
260 1436 op->entry_count += (uint16_t)g_count;
261 1436 cur_ngroups++;
262
263 /* Bump pd_lower so PostgreSQL's hole-compression preserves
264 * our writes. FASTSCAN doesn't use the backward data region
265 * — everything lives in the forward content area. */
266 1436 PageHeader header = (PageHeader)cur_page;
267 1436 header->pd_lower += prism_centroid_fastscan_group_bytes(dim);
268 }
269
270
1/2
✓ Branch 0 taken 1412 times.
✗ Branch 1 not taken.
1412 if (cur_page != NULL)
271 1412 vs_storage_commit_page(storage, cur_blkno);
272
273 1412 vs_free(rdata_buf);
274 1412 vs_free(bits_buf);
275
276 1412 return first_blkno;
277 }
278