GCC Code Coverage Report


Directory: src/
File: src/standalone/query.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 147 166 88.6%
Functions: 6 6 100.0%
Branches: 58 84 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 * query.c - Zero-allocation query execution
6 *
7 * All buffers are pre-allocated in PrismQueryCtx. The query hot path
8 * uses only pre-allocated memory and arena reset (no malloc/free).
9 *
10 * For paged posting lists, delegates to PrismQueryState (shared with
11 * PG). Flat posting lists and brute-force remain standalone-only.
12 *
13 * Memory layout:
14 * memctx (long-lived) — owns all query context buffers
15 * └── arena (child) — transient per-query allocations, reset each query
16 */
17
18 #include <math.h>
19 #include <stdio.h>
20 #include <string.h>
21
22 #include "algo/topk.h"
23 #include "algo/vecops.h"
24 #include "core/memory.h"
25 #include "index/posting_page.h"
26 #include "index/posting_scan.h"
27 #include "index/query_scan.h"
28 #include "quant/rabitq.h"
29 #include "standalone/query.h"
30
31 /* ----------------------------------------------------------------
32 * Query context internals
33 * ---------------------------------------------------------------- */
34
35 struct PrismQueryCtx
36 {
37 PrismIndex *idx;
38
39 /* Shared search context (paged mode) */
40 PrismQueryState search;
41 bool has_query_state;
42
43 /* Reranking (standalone-specific) */
44 VsTopK rerank_topk;
45 VsTopKEntry *rerank_buf;
46 uint32_t rerank_cap;
47
48 /* Flat/brute-force fallback buffers */
49 float *query_buf;
50 PrismCentroidResult *beam_results;
51 PrismCentroidScratch *centroid_scratch;
52 VsTopK topk;
53 PrismPostingScan posting_scan;
54 float *pt_query;
55 float *pt_cents_buf;
56 RaBitQQueryState beam_qs;
57 RaBitQQueryState cluster_qs;
58 float *beam_transformed;
59 float *cluster_transformed;
60 uint8_t *beam_query_bits;
61 uint8_t *cluster_query_bits;
62
63 /* Long-lived memory context for all query context buffers.
64 * Deleting this frees everything at once (no individual frees). */
65 VsMemCtx memctx;
66
67 /* Child arena for transient per-query allocations (beam search
68 * internals). Reset per query — no create/delete overhead. */
69 VsMemCtx arena;
70
71 /* Limits */
72 uint32_t max_k;
73 uint32_t max_nprobe;
74 };
75
76 /* ----------------------------------------------------------------
77 * Create / destroy
78 * ---------------------------------------------------------------- */
79
80 PrismQueryCtx *
81 56 prism_query_ctx_create(PrismIndex *idx, uint32_t max_k, uint32_t max_nprobe)
82 {
83
4/6
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 54 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 54 times.
56 if (idx == NULL || max_k == 0 || max_nprobe == 0)
84 2 return NULL;
85
86 54 VsMemCtx memctx = vs_memctx_create(NULL, "query_ctx");
87 54 VsMemCtx old_ctx = vs_memctx_switch(memctx);
88
89 54 PrismQueryCtx *ctx = vs_alloc0(sizeof(PrismQueryCtx));
90 54 ctx->idx = idx;
91 54 ctx->max_k = max_k;
92 54 ctx->max_nprobe = max_nprobe;
93 54 ctx->memctx = memctx;
94
95 54 Dimension dim = idx->base.dim;
96
97 /* Paged mode: use shared PrismQueryState */
98
3/4
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
54 if (idx->has_posting_data && idx->base.params != NULL &&
99
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 8 times.
52 idx->posting_fmt == PRISM_POSTING_FMT_PAGES)
100 {
101 44 prism_query_state_init(&ctx->search, &idx->base, max_k, max_nprobe);
102 44 ctx->has_query_state = true;
103
104
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 36 times.
44 if (idx->base.fastscan)
105 8 prism_posting_scan_enable_fastscan(
106 &ctx->search.pscan, idx->base.fastscan);
107 }
108 else
109 {
110 /* Flat/brute-force: allocate standalone buffers */
111 10 uint32_t packed_bytes = VS_RABITQ_BYTES(dim);
112
113 10 ctx->query_buf = vs_alloc(dim * sizeof(float));
114 10 ctx->beam_results = vs_alloc(max_nprobe * sizeof(PrismCentroidResult));
115 10 ctx->centroid_scratch = prism_centroid_scratch_create(dim, max_nprobe);
116 10 vs_topk_init(&ctx->topk, max_k);
117
118
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
10 if (idx->has_posting_data)
119 {
120 8 VsStorage *storage = (idx->posting_fmt == PRISM_POSTING_FMT_PAGES)
121 ? &idx->posting_storage.base
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
8 : NULL;
123 8 char *page_base = (idx->posting_fmt == PRISM_POSTING_FMT_PAGES)
124 ? idx->posting_storage.pages
125
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
8 : NULL;
126 8 uint32_t max_per_page = (idx->posting_fmt ==
127 PRISM_POSTING_FMT_PAGES)
128 ✗ ? prism_posting_max_entries(dim)
129
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
8 : idx->max_cluster_size;
130
131 8 prism_posting_scan_init(
132 &ctx->posting_scan,
133 storage,
134 page_base,
135 8 idx->base.params,
136 dim,
137 max_per_page);
138
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
8 if (idx->base.fastscan)
140 ✗ prism_posting_scan_enable_fastscan(
141 &ctx->posting_scan, idx->base.fastscan);
142 }
143
144 10 ctx->pt_cents_buf = vs_alloc((size_t)max_nprobe * dim * sizeof(float));
145 10 ctx->pt_query = vs_alloc_aligned(dim * sizeof(float), 64);
146 10 ctx->beam_transformed = vs_alloc_aligned(dim * sizeof(float), 64);
147 10 ctx->cluster_transformed = vs_alloc_aligned(dim * sizeof(float), 64);
148 10 ctx->beam_query_bits = vs_alloc_aligned(packed_bytes, 64);
149 10 ctx->cluster_query_bits = vs_alloc_aligned(packed_bytes, 64);
150
151 10 ctx->beam_qs.transformed = ctx->beam_transformed;
152 10 ctx->beam_qs.query_bits = ctx->beam_query_bits;
153 10 ctx->cluster_qs.transformed = ctx->cluster_transformed;
154 10 ctx->cluster_qs.query_bits = ctx->cluster_query_bits;
155
156 10 vs_rabitq_init_query_constants(&ctx->beam_qs, dim);
157 10 vs_rabitq_init_query_constants(&ctx->cluster_qs, dim);
158 }
159
160 /* Reranking buffers (used for both paged and flat) */
161 54 vs_topk_init(&ctx->rerank_topk, max_k);
162 54 ctx->rerank_cap = max_k * 16;
163 54 ctx->rerank_buf = vs_alloc(ctx->rerank_cap * sizeof(VsTopKEntry));
164
165 /* Child arena for transient per-query allocations */
166 54 ctx->arena = vs_memctx_create(memctx, "query_arena");
167
168 54 vs_memctx_switch(old_ctx);
169 54 return ctx;
170 }
171
172 void
173 54 prism_query_ctx_destroy(PrismQueryCtx *ctx)
174 {
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 54 times.
54 if (ctx == NULL)
176 ✗ return;
177
178
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 10 times.
54 if (ctx->has_query_state)
179 44 prism_query_state_cleanup(&ctx->search);
180 else
181 {
182
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
10 if (ctx->idx->has_posting_data)
183 8 prism_posting_scan_cleanup(&ctx->posting_scan);
184 10 vs_topk_cleanup(&ctx->topk);
185 10 prism_centroid_scratch_free(ctx->centroid_scratch);
186 10 ctx->centroid_scratch = NULL;
187 }
188
189 54 vs_topk_cleanup(&ctx->rerank_topk);
190
191 /* Deleting memctx frees ctx itself, all buffers, and the arena */
192 54 vs_memctx_delete(ctx->memctx);
193 }
194
195 /* ----------------------------------------------------------------
196 * Paged query (via shared PrismQueryState)
197 * ---------------------------------------------------------------- */
198
199 static uint32_t
200 4148 exec_paged(
201 PrismQueryCtx *ctx,
202 const float *query,
203 uint32_t k,
204 uint32_t nprobe,
205 VsDistanceMode mode,
206 bool rerank,
207 uint32_t *result_ids)
208 {
209 4148 VsMemCtx old = vs_memctx_switch(ctx->memctx);
210 4148 prism_query_execute(&ctx->search, query, k, nprobe, mode, rerank, NULL);
211 4148 vs_memctx_switch(old);
212
213 4148 uint32_t nresults = ctx->search.nresults;
214
2/2
✓ Branch 0 taken 6866 times.
✓ Branch 1 taken 4148 times.
11014 for (uint32_t i = 0; i < nresults; i++)
215 {
216 6866 uint32_t ci = ctx->search.result_order[i];
217 6866 result_ids[i] = prism_posting_decode_vector_id(
218 6866 ctx->search.candidates[ci].id);
219 }
220
221 4148 return nresults;
222 }
223
224 /* ----------------------------------------------------------------
225 * Flat/brute-force query (standalone-only fallback)
226 * ---------------------------------------------------------------- */
227
228 static uint32_t
229 104 exec_fallback(
230 PrismQueryCtx *ctx,
231 const float *query,
232 uint32_t k,
233 uint32_t nprobe,
234 VsDistanceMode mode,
235 bool rerank,
236 uint32_t *result_ids)
237 {
238 104 PrismIndex *idx = ctx->idx;
239 104 Dimension dim = idx->base.dim;
240
241
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
104 if (k > ctx->max_k)
242 ✗ k = ctx->max_k;
243
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
104 if (nprobe > ctx->max_nprobe)
244 ✗ nprobe = ctx->max_nprobe;
245
246 104 VsMemCtx old_ctx = vs_memctx_switch(ctx->arena);
247 104 vs_memctx_reset(ctx->arena);
248
249 /* Normalize query */
250 104 const float *qvec = query;
251
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
104 if (idx->base.metric == DISTANCE_COSINE)
252 {
253 ✗ memcpy(ctx->query_buf, query, dim * sizeof(float));
254 ✗ float norm = vs_l2_norm(ctx->query_buf, dim);
255 ✗ if (norm > 0.0f)
256 ✗ vec32_scale(ctx->query_buf, 1.0f / norm, ctx->query_buf, dim);
257 ✗ qvec = ctx->query_buf;
258 }
259
260 /* Rotate query */
261 104 RaBitQQueryState *qs = NULL;
262
1/2
✓ Branch 0 taken 104 times.
✗ Branch 1 not taken.
104 if (idx->base.params != NULL)
263 {
264 104 vs_rabitq_rotate(idx->base.params, qvec, ctx->pt_query);
265
266
2/2
✓ Branch 0 taken 102 times.
✓ Branch 1 taken 2 times.
104 if (idx->base.centroid_format == PRISM_CENTROID_FMT_RABITQ)
267 {
268 102 vs_rabitq_init_query_state(
269 &ctx->beam_qs,
270 102 ctx->pt_query,
271 102 idx->base.pt_global_mean,
272 dim,
273 mode);
274 102 qs = &ctx->beam_qs;
275 }
276 }
277
278 /* Beam search */
279 104 PrismCentroidSearchState state = {
280 .qstate = qs,
281 .query = qvec,
282 104 .storage = &idx->centroid_storage.base,
283 .beam_width = nprobe,
284 .nprobe = nprobe,
285 .dim = dim,
286 104 .metric = idx->base.metric,
287 .error_scale = 0.0f,
288 104 .scratch = ctx->centroid_scratch,
289 };
290
291 104 PrismCentroidSearchStats beam_stats = {0};
292 104 uint32_t n_results = prism_centroid_beam_search(
293 &state,
294 idx->base.first_centroid,
295 104 idx->base.nlevels,
296 ctx->beam_results,
297 NULL,
298 &beam_stats);
299
300 104 vs_memctx_switch(old_ctx);
301
302 /* Reset top-K */
303 104 vs_topk_reset_to_k(&ctx->topk, k);
304
305 /* Flat mode or brute-force */
306
3/4
✓ Branch 0 taken 102 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 102 times.
✗ Branch 3 not taken.
104 if (idx->has_posting_data && idx->base.params != NULL)
307 {
308
2/2
✓ Branch 0 taken 700 times.
✓ Branch 1 taken 102 times.
802 for (uint32_t j = 0; j < n_results; j++)
309 {
310 700 uint32_t li = (uint32_t)ctx->beam_results[j].posting_head;
311
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 700 times.
700 if (li >= idx->nlist)
312 ✗ continue;
313
314 700 const float *pt_cent = idx->pt_centroids + (size_t)li * dim;
315 700 vs_rabitq_init_query_state(
316 700 &ctx->cluster_qs, ctx->pt_query, pt_cent, dim, mode);
317
318 700 prism_posting_scan_begin_flat(
319 700 &ctx->posting_scan, &ctx->cluster_qs, idx->flat_pages[li]);
320 700 prism_posting_scan_cluster_standalone(
321 &ctx->posting_scan, &ctx->topk);
322 700 prism_posting_scan_end_cluster(&ctx->posting_scan);
323 }
324 }
325 else
326 {
327
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
12 for (uint32_t j = 0; j < n_results; j++)
328 {
329 10 uint32_t li = (uint32_t)ctx->beam_results[j].posting_head;
330
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
10 if (li >= idx->nlist)
331 ✗ continue;
332
333 10 PrismClusterList *cl = &idx->clusters[li];
334
2/2
✓ Branch 0 taken 244 times.
✓ Branch 1 taken 10 times.
254 for (uint32_t vi = 0; vi < cl->count; vi++)
335 {
336 244 uint32_t vid = cl->ids[vi];
337 244 const float *vec = idx->all_vectors + (size_t)vid * dim;
338 244 Distance d = vs_l2_distance_squared(qvec, vec, dim);
339 244 vs_topk_insert(&ctx->topk, d, 0.0f, vid);
340 }
341 }
342 }
343
344 /* Extract results */
345 uint32_t count;
346
1/2
✓ Branch 0 taken 104 times.
✗ Branch 1 not taken.
104 if (rerank)
347 {
348
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 96 times.
104 if (ctx->topk.cand_count > ctx->rerank_cap)
349 {
350 8 ctx->rerank_cap = ctx->topk.cand_count;
351 8 ctx->rerank_buf = vs_realloc(
352 8 ctx->rerank_buf, ctx->rerank_cap * sizeof(VsTopKEntry));
353 }
354
355 uint32_t n_cands;
356 104 vs_topk_extract_sorted(&ctx->topk, ctx->rerank_buf, &n_cands);
357
358 104 vs_topk_reset_to_k(&ctx->rerank_topk, k);
359
360
2/2
✓ Branch 0 taken 24874 times.
✓ Branch 1 taken 104 times.
24978 for (uint32_t i = 0; i < n_cands; i++)
361 {
362 24874 uint32_t vid = prism_posting_decode_vector_id(
363 24874 ctx->rerank_buf[i].id);
364 24874 const float *vec = idx->all_vectors + (size_t)vid * dim;
365 24874 Distance d = vs_l2_distance_squared(qvec, vec, dim);
366 24874 vs_topk_insert(&ctx->rerank_topk, d, 0.0f, ctx->rerank_buf[i].id);
367 }
368
369 104 vs_topk_extract_sorted(&ctx->rerank_topk, ctx->rerank_buf, &count);
370 }
371 else
372 {
373 ✗ if (ctx->topk.cand_count > ctx->rerank_cap)
374 {
375 ✗ ctx->rerank_cap = ctx->topk.cand_count;
376 ✗ ctx->rerank_buf = vs_realloc(
377 ✗ ctx->rerank_buf, ctx->rerank_cap * sizeof(VsTopKEntry));
378 }
379
380 ✗ vs_topk_extract_sorted(&ctx->topk, ctx->rerank_buf, &count);
381 }
382
383 104 uint32_t out = count < k ? count : k;
384
2/2
✓ Branch 0 taken 620 times.
✓ Branch 1 taken 104 times.
724 for (uint32_t i = 0; i < out; i++)
385 620 result_ids[i] = prism_posting_decode_vector_id(ctx->rerank_buf[i].id);
386
387 104 return out;
388 }
389
390 /* ----------------------------------------------------------------
391 * Query execution — dispatch to paged or fallback
392 * ---------------------------------------------------------------- */
393
394 uint32_t
395 4254 prism_query_exec(
396 PrismQueryCtx *ctx,
397 const float *query,
398 uint32_t k,
399 uint32_t nprobe,
400 VsDistanceMode mode,
401 bool rerank,
402 uint32_t *result_ids)
403 {
404
5/8
✓ Branch 0 taken 4252 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 4252 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4252 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 4252 times.
4254 if (ctx == NULL || query == NULL || result_ids == NULL || k == 0)
405 2 return 0;
406
407
2/2
✓ Branch 0 taken 4148 times.
✓ Branch 1 taken 104 times.
4252 if (ctx->has_query_state)
408 4148 return exec_paged(ctx, query, k, nprobe, mode, rerank, result_ids);
409 else
410 104 return exec_fallback(ctx, query, k, nprobe, mode, rerank, result_ids);
411 }
412
413 void
414 702 prism_posting_scan_cluster_standalone(PrismPostingScan *scan, VsTopK *topk)
415 {
416
2/4
✓ Branch 0 taken 702 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 702 times.
702 if (scan->storage != NULL || scan->page_base != NULL)
417 {
418 ✗ prism_posting_scan_cluster(scan, topk);
419 ✗ return;
420 }
421
422
1/2
✓ Branch 0 taken 702 times.
✗ Branch 1 not taken.
702 if (scan->cur_page != NULL)
423 702 prism_posting_scan_aos_page(scan, topk);
424 702 scan->cur_page = NULL;
425 702 scan->cur_content = NULL;
426 }
427