GCC Code Coverage Report


Directory: src/
File: src/standalone/index.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 336 382 88.0%
Functions: 17 18 94.4%
Branches: 105 142 73.9%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * index.c - Standalone in-memory index build
6 *
7 * Builds centroid tree and per-cluster posting lists from a flat
8 * vector array. Used by bindings and CLI benchmark.
9 *
10 * When RaBitQ encoding is enabled, posting data is written to pages
11 * via PrismPostingBuilder. The full-precision vectors are stored in a
12 * flat array for reranking.
13 */
14
15 #include <math.h>
16 #include <pthread.h>
17 #include <stdatomic.h>
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <time.h>
22 #include <unistd.h>
23
24 #include "algo/distance.h"
25 #include "algo/hkmeans.h"
26 #include "algo/kmeans.h"
27 #include "algo/kmeans_internal.h"
28 #include "algo/topk.h"
29 #include "algo/vecops.h"
30 #include "core/log.h"
31 #include "core/memory.h"
32 #include "index/centroid_build.h"
33 #include "index/centroid_page.h"
34 #include "index/index_build.h"
35 #include "index/parallel_build.h"
36 #include "index/posting_build.h"
37 #include "index/posting_convert.h"
38 #include "index/posting_page.h"
39 #include "quant/rabitq.h"
40 #include "standalone/index.h"
41
42 static uint64_t
43 710 now_ns(void)
44 {
45 struct timespec ts;
46 710 clock_gettime(CLOCK_MONOTONIC, &ts);
47 710 return (uint64_t)ts.tv_sec * 1000000000ULL + (uint64_t)ts.tv_nsec;
48 }
49
50 /* Arena-safe grow: alloc new, copy old, old freed on context delete */
51 static void *
52 94 arena_grow(void *old, size_t old_size, size_t new_size)
53 {
54 94 void *new_buf = vs_alloc(new_size);
55
2/4
✓ Branch 0 taken 94 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 94 times.
✗ Branch 3 not taken.
94 if (old != NULL && old_size > 0)
56 94 memcpy(new_buf, old, old_size);
57 94 return new_buf;
58 }
59
60 /* ----------------------------------------------------------------
61 * ArrayPageStorage — page array backed by memory context
62 * ---------------------------------------------------------------- */
63
64 static Page
65 4200732 aps_read_page(VsStorage *self, BlockNumber blkno)
66 {
67 4200732 ArrayPageStorage *s = (ArrayPageStorage *)self;
68 4200732 return s->pages + (size_t)blkno * BLCKSZ;
69 }
70
71 static void
72 4200732 aps_release_page(VsStorage *self, BlockNumber blkno)
73 {
74 (void)self;
75 (void)blkno;
76 4200732 }
77
78 static Page
79 8744 aps_write_page(VsStorage *self, BlockNumber blkno)
80 {
81 8744 ArrayPageStorage *s = (ArrayPageStorage *)self;
82 8744 return s->pages + (size_t)blkno * BLCKSZ;
83 }
84
85 static Page
86 940 aps_new_page(VsStorage *self, BlockNumber *blkno_out)
87 {
88 940 ArrayPageStorage *s = (ArrayPageStorage *)self;
89 940 pthread_mutex_lock(&s->alloc_mutex);
90
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 940 times.
940 if (s->next_blkno >= s->page_cap)
91 {
92 ✗ VsMemCtx prev = vs_memctx_switch(s->memctx);
93 ✗ uint32_t new_cap = s->page_cap * 2;
94 ✗ s->pages = arena_grow(
95 ✗ s->pages,
96 ✗ (size_t)s->page_cap * BLCKSZ,
97 ✗ (size_t)new_cap * BLCKSZ);
98 ✗ s->page_cap = new_cap;
99 ✗ vs_memctx_switch(prev);
100 }
101 940 *blkno_out = s->next_blkno++;
102 940 pthread_mutex_unlock(&s->alloc_mutex);
103 940 return s->pages + (size_t)*blkno_out * BLCKSZ;
104 }
105
106 static void
107 9684 aps_commit_page(VsStorage *self, BlockNumber blkno)
108 {
109 (void)self;
110 (void)blkno;
111 9684 }
112
113 static BlockNumber
114 106 aps_extend(VsStorage *self, uint32_t npages)
115 {
116 106 ArrayPageStorage *s = (ArrayPageStorage *)self;
117 106 pthread_mutex_lock(&s->alloc_mutex);
118
119 106 BlockNumber start = s->next_blkno;
120 106 uint32_t needed = start + npages;
121
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 106 times.
106 while (needed > s->page_cap)
123 {
124 ✗ VsMemCtx prev = vs_memctx_switch(s->memctx);
125 ✗ uint32_t new_cap = s->page_cap * 2;
126 ✗ if (new_cap < needed)
127 ✗ new_cap = needed;
128 ✗ s->pages = arena_grow(
129 ✗ s->pages,
130 ✗ (size_t)s->page_cap * BLCKSZ,
131 ✗ (size_t)new_cap * BLCKSZ);
132 ✗ s->page_cap = new_cap;
133 ✗ vs_memctx_switch(prev);
134 }
135
136 106 s->next_blkno = needed;
137 106 pthread_mutex_unlock(&s->alloc_mutex);
138 106 return start;
139 }
140
141 static uint32_t
142 4294 aps_rerank(
143 VsStorage *self,
144 const float *query,
145 Dimension dim,
146 const VsTopKEntry *candidates,
147 uint32_t count,
148 uint32_t keep,
149 uint32_t *out_indices,
150 Distance *out_distances)
151 {
152 4294 ArrayPageStorage *s = (ArrayPageStorage *)self;
153
154
2/4
✓ Branch 0 taken 4294 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 4294 times.
4294 if (s->all_vectors == NULL || count == 0)
155 ✗ return 0;
156
157 4294 vs_topk_reset_to_k(&s->rerank_topk, keep);
158
159
2/2
✓ Branch 0 taken 82975 times.
✓ Branch 1 taken 4294 times.
87269 for (uint32_t i = 0; i < count; i++)
160 {
161 Distance d;
162
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 82967 times.
82975 if (candidates[i].error == 0.0f)
163 {
164 8 d = candidates[i].distance;
165 }
166 else
167 {
168 82967 uint32_t vid = prism_posting_decode_vector_id(candidates[i].id);
169
1/2
✓ Branch 0 taken 82967 times.
✗ Branch 1 not taken.
82967 if (vid < s->nvecs)
170 {
171 82967 const float *vec = s->all_vectors + (size_t)vid * dim;
172 82967 d = vs_l2_distance_squared(query, vec, dim);
173 }
174 else
175 {
176 ✗ d = candidates[i].distance;
177 }
178 }
179
180 82975 vs_topk_insert(&s->rerank_topk, d, 0.0f, (uint64_t)i);
181 }
182
183 /* Extraction writes every threshold survivor before capping to
184 * keep, and candidates tied at the keep-th distance can push the
185 * survivors past the preallocated entries. Grow from the index's
186 * own context -- the current one belongs to the query, which dies
187 * before the index -- and double so the superseded buffers an
188 * arena retains until teardown stay linear in the largest size. */
189
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4290 times.
4294 if (s->rerank_topk.cand_count > s->rerank_cap)
190 {
191
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
8 while (s->rerank_cap < s->rerank_topk.cand_count)
192 4 s->rerank_cap *= 2;
193 4 s->rerank_entries = vs_memctx_alloc(
194 4 s->memctx, (size_t)s->rerank_cap * sizeof(VsTopKEntry));
195 }
196
197 uint32_t nresults;
198 4294 vs_topk_extract_sorted_capped(
199 &s->rerank_topk, s->rerank_entries, &nresults, keep);
200
201
2/2
✓ Branch 0 taken 8094 times.
✓ Branch 1 taken 4294 times.
12388 for (uint32_t i = 0; i < nresults; i++)
202 {
203 8094 out_indices[i] = (uint32_t)s->rerank_entries[i].id;
204 8094 out_distances[i] = s->rerank_entries[i].distance;
205 }
206
207 4294 return nresults;
208 }
209
210 static const VsStorageOps array_page_storage_ops = {
211 .read_page = aps_read_page,
212 .release_page = aps_release_page,
213 .write_page = aps_write_page,
214 .new_page = aps_new_page,
215 .commit_page = aps_commit_page,
216 .extend = aps_extend,
217 .rerank = aps_rerank,
218 };
219
220 /* ----------------------------------------------------------------
221 * Cluster list helpers (per-cluster vector ID lists)
222 * ---------------------------------------------------------------- */
223
224 static void
225 222 cluster_list_init(PrismClusterList *cl, uint32_t initial_cap)
226 {
227 222 cl->count = 0;
228 222 cl->capacity = initial_cap;
229 222 cl->ids = vs_alloc(initial_cap * sizeof(uint32_t));
230 222 }
231
232 static void
233 13600 cluster_list_append(PrismClusterList *cl, uint32_t id)
234 {
235
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 13506 times.
13600 if (cl->count == cl->capacity)
236 {
237 94 uint32_t old_cap = cl->capacity;
238 94 uint32_t new_cap = old_cap * 2;
239 188 cl->ids = arena_grow(
240 94 cl->ids,
241 94 old_cap * sizeof(uint32_t),
242 94 new_cap * sizeof(uint32_t));
243 94 cl->capacity = new_cap;
244 }
245 13600 cl->ids[cl->count++] = id;
246 13600 }
247
248 /* ----------------------------------------------------------------
249 * ArrayPageStorage initialization helper
250 * ---------------------------------------------------------------- */
251
252 static ArrayPageStorage
253 124 make_array_page_storage(uint32_t est_pages, VsMemCtx memctx)
254 {
255 /*
256 * No zero-fill: every page is fully overwritten on its first write
257 * (flush copies the whole BLCKSZ buffer), and reserved/spill pages
258 * that no worker writes are never linked into a chain, so they are
259 * never read. Zeroing the whole pre-reserved array (hundreds of MB
260 * for large builds) would be pure overhead.
261 */
262 248 ArrayPageStorage s = {
263 .base = {.ops = &array_page_storage_ops},
264 124 .pages = vs_alloc((size_t)est_pages * BLCKSZ),
265 .next_blkno = 0,
266 .page_cap = est_pages,
267 .memctx = memctx,
268 };
269 124 pthread_mutex_init(&s.alloc_mutex, NULL);
270 124 return s;
271 }
272
273 /* ----------------------------------------------------------------
274 * Normalize helpers
275 * ---------------------------------------------------------------- */
276
277 static void
278 2898 normalize_vector(float *v, Dimension dim)
279 {
280 2898 float norm = vs_l2_norm(v, dim);
281
2/2
✓ Branch 0 taken 2818 times.
✓ Branch 1 taken 80 times.
2898 if (norm > 0.0f)
282 2818 vec32_scale(v, 1.0f / norm, v, dim);
283 2898 }
284
285 static void
286 6 normalize_all(float *data, uint32_t nvecs, Dimension dim)
287 {
288
2/2
✓ Branch 0 taken 2880 times.
✓ Branch 1 taken 6 times.
2886 for (uint32_t i = 0; i < nvecs; i++)
289 2880 normalize_vector(data + (size_t)i * dim, dim);
290 6 }
291
292 static uint32_t
293 ✗ sa_detect_nthreads(void)
294 {
295 ✗ long n = sysconf(_SC_NPROCESSORS_ONLN);
296 ✗ if (n < 1)
297 ✗ n = 1;
298 ✗ if (n > 64)
299 ✗ n = 64;
300 ✗ return (uint32_t)n;
301 }
302
303 /* ----------------------------------------------------------------
304 * Assign vectors to cluster lists (serial, inline)
305 *
306 * Used only by flat mode and no-rabitq brute-force path which need
307 * per-cluster vector ID lists. The pages mode parallel path does
308 * assignment inline in each posting worker instead.
309 * ---------------------------------------------------------------- */
310
311 static void
312 18 assign_to_cluster_lists(
313 PrismIndex *idx,
314 const HKMeansResult *tree,
315 const PrismAssignParams *bp,
316 Dimension dim,
317 uint32_t nlist)
318 {
319 18 PrismBuildWorkerBufs bufs = prism_build_worker_bufs_create(dim);
320
321
2/2
✓ Branch 0 taken 13600 times.
✓ Branch 1 taken 18 times.
13618 for (uint32_t i = 0; i < idx->nvecs; i++)
322 {
323 13600 const float *vec = idx->all_vectors + (size_t)i * dim;
324 PrismBuildAssignment asgn =
325 13600 prism_build_assign_vector(tree, vec, bp, &bufs);
326
327 13600 cluster_list_append(&idx->clusters[asgn.primary], i);
328
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13600 times.
13600 if (asgn.secondary != PRISM_INVALID_CLUSTER)
329 ✗ cluster_list_append(&idx->clusters[asgn.secondary], i);
330 }
331
332 18 prism_build_worker_bufs_free(&bufs);
333
334 18 idx->max_cluster_size = 0;
335
2/2
✓ Branch 0 taken 222 times.
✓ Branch 1 taken 18 times.
240 for (uint32_t c = 0; c < nlist; c++)
336
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 178 times.
222 if (idx->clusters[c].count > idx->max_cluster_size)
337 44 idx->max_cluster_size = idx->clusters[c].count;
338 18 }
339
340 /* ----------------------------------------------------------------
341 * Build
342 * ---------------------------------------------------------------- */
343
344 PrismIndex *
345 140 prism_index_build(
346 Vec32Source *src,
347 const PrismIndexConfig *config,
348 PrismBuildStats *stats)
349 {
350 /* Each path below writes only the phases it ran, and ms_refine has no
351 * standalone producer at all, while callers read the struct whole. */
352
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 124 times.
140 if (stats != NULL)
353 16 memset(stats, 0, sizeof(*stats));
354
355
8/8
✓ Branch 0 taken 138 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 136 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 134 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 132 times.
140 if (src == NULL || src->nvecs == 0 || src->dim == 0 || config == NULL)
356 8 return NULL;
357
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 128 times.
132 if (!prism_index_dim_supported(src->dim))
358 {
359 4 vs_warn("index build: %u dimensions is not supported (ceiling %u; "
360 "above %u the dimension must be a power of two times an "
361 "odd factor of at most %u)",
362 (unsigned)src->dim,
363 (unsigned)PRISM_INDEX_MAX_DIM,
364 (unsigned)PRISM_INDEX_NARROW_MAX_DIM,
365 (unsigned)VS_FAST_ROTATE_K_MAX);
366 4 return NULL;
367 }
368 /* Same refusal the PG build makes: an uncompressed (or fastscan)
369 * centroid entry that no page can hold. */
370
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 124 times.
128 if (prism_centroid_max_entries_fmt(src->dim, config->centroid_fmt) == 0)
371 {
372 4 vs_warn("index build: centroid format %d does not fit a page at %u "
373 "dimensions; use RaBitQ centroids",
374 (int)config->centroid_fmt,
375 (unsigned)src->dim);
376 4 return NULL;
377 }
378
379 124 uint32_t nvecs = src->nvecs;
380 124 Dimension dim = src->dim;
381
382 124 vs_distance_init();
383
384 /* Resolve the worker count for the parallel driver (paged builds). */
385 uint32_t nworkers;
386
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 124 times.
124 if (config->nworkers < 0)
387 {
388 ✗ uint32_t ncpu = sa_detect_nthreads();
389 ✗ nworkers = ncpu > 1 ? ncpu - 1 : 0;
390 }
391 else
392 {
393 124 nworkers = (uint32_t)config->nworkers;
394 }
395
396 /* Long-lived context for index data. Build-phase temporaries
397 * go into a child context that gets deleted after build. */
398 124 VsMemCtx idx_ctx = vs_memctx_create(NULL, "index");
399 124 VsMemCtx build_ctx = vs_memctx_create(idx_ctx, "index_build");
400 124 VsMemCtx old_ctx = vs_memctx_switch(idx_ctx);
401
402 124 PrismIndex *idx = vs_alloc0(sizeof(PrismIndex));
403 124 idx->memctx = idx_ctx;
404 124 idx->base.dim = dim;
405 124 idx->base.metric = config->metric;
406 124 idx->base.centroid_format = config->centroid_fmt;
407
408 /* Resolve nlist */
409 124 uint32_t nlist = config->nlist;
410
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 124 times.
124 if (nlist == 0)
411 ✗ nlist = prism_auto_nlist((double)nvecs, dim, config->target_pages);
412
413 /* Resolve fan_out */
414 124 uint32_t fan_out = config->fan_out;
415
2/2
✓ Branch 0 taken 114 times.
✓ Branch 1 taken 10 times.
124 if (fan_out == 0)
416 114 fan_out = prism_auto_fan_out(0, nlist, 0);
417 124 idx->fan_out = fan_out;
418
419 /* --- Phase: load vectors --- */
420 124 uint64_t t_phase = now_ns();
421
422 124 idx->all_vectors = vs_alloc((size_t)nvecs * dim * sizeof(float));
423
424
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 124 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
124 if (src->read_all != NULL && src->read_all(src, idx->all_vectors))
425 {
426 ✗ idx->nvecs = nvecs;
427 }
428 else
429 {
430 124 idx->nvecs = 0;
431 const float *vec;
432 uint32_t id;
433
2/2
✓ Branch 1 taken 203042 times.
✓ Branch 2 taken 124 times.
203166 while (src->next(src, 1, &vec, &id))
434 {
435 203042 memcpy(idx->all_vectors + (size_t)id * dim,
436 vec,
437 203042 dim * sizeof(float));
438 203042 idx->nvecs++;
439 }
440 }
441
442
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 118 times.
124 if (idx->base.metric == DISTANCE_COSINE)
443 6 normalize_all(idx->all_vectors, idx->nvecs, dim);
444
445 124 double ms_sample = (double)(now_ns() - t_phase) / 1e6;
446
447 /*
448 * Paged RaBitQ builds with at least one worker run the shared parallel
449 * build driver (sampling + k-means + bounded streaming posting) — the same
450 * code path the PostgreSQL extension uses. Flat and serial builds keep the
451 * in-memory path below.
452 */
453
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 4 times.
244 bool use_driver = config->encode_rabitq &&
454
2/2
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 14 times.
120 config->posting_fmt == PRISM_POSTING_FMT_PAGES;
455
456 124 HKMeansResult *tree = NULL;
457 124 uint32_t drv_nlist = 0; /* driver path: streamed tree shape */
458 124 uint8_t drv_nlevels = 0;
459 124 float *km_vectors = NULL;
460 124 uint32_t km_nvecs = 0;
461 124 double ms_kmeans = 0;
462 124 float *sa_global_mean = NULL; /* driver's leaf-centroid mean */
463
464
2/2
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 18 times.
124 if (use_driver)
465 {
466 106 t_phase = now_ns();
467
468 /* The driver produces fastscan-packed pages when requested; the query
469 * path must know to read them as fastscan (not AoS). */
470 106 idx->base.fastscan = config->fastscan != 0;
471
472 /* Upper bound on leaves (fan_out^nlevels, matching the tree the driver
473 * builds). */
474 106 uint32_t max_nlist = prism_max_nlist(nlist, fan_out);
475
476 /*
477 * Long-lived posting storage for the driver's streamed pages. The
478 * driver reserves a centroid region at the front (left unwritten here
479 * — the centroid pages go to centroid_storage below) and writes
480 * posting pages after it. Head blocks are formula-derived
481 * (first_posting + leaf), so no head array is needed.
482 */
483 106 uint32_t est_pages = idx->nvecs / 4 + max_nlist + 256;
484 106 idx->posting_storage = make_array_page_storage(est_pages, idx_ctx);
485
486 106 RelationData heap_rel = {
487 106 .vectors = idx->all_vectors,
488 106 .nvecs = idx->nvecs,
489 .dim = dim,
490 };
491 106 RelationData index_rel = {
492 106 .page_count = &idx->posting_storage.next_blkno,
493 };
494 /* The driver streams worker→leader, so it needs at least one worker;
495 * a serial (nworkers==0) PAGES build runs through the driver with one.
496 */
497 106 IndexInfo index_info = {
498
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 86 times.
106 .ii_ParallelWorkers = (int)(nworkers > 0 ? nworkers : 1)};
499 106 PrismBuildConfig cfg = {
500 .dim = dim,
501 106 .metric = config->metric,
502 106 .centroid_format = idx->base.centroid_format,
503 /* The tree expands to up to fan_out^nlevels leaves; size the
504 * shared regions for that bound (matches the PG caller). */
505 .nlist = max_nlist,
506 .fan_out = fan_out,
507 106 .soar_lambda = config->soar_lambda,
508 106 .boundary_epsilon = config->boundary_epsilon,
509 106 .fastscan = config->fastscan != 0,
510 };
511
512 106 double heap_tuples = 0, indtuples = 0, soar_dupes = 0;
513
514 /* Build temporaries (samples, accumulators, the tree) live in
515 * build_ctx and are freed after the build; page growth uses the
516 * storage's own (idx_ctx) context, so the index pages outlive it. */
517 106 vs_memctx_switch(build_ctx);
518 106 bool ok = do_parallel_build(
519 &heap_rel,
520 &index_rel,
521 &index_info,
522 &cfg,
523 &idx->posting_storage.base,
524 NULL, /* no build-progress seam in standalone (no-op stub) */
525 &drv_nlist,
526 &drv_nlevels,
527 &heap_tuples,
528 &indtuples,
529 &soar_dupes,
530 /* The driver streams the centroid tree into posting_storage
531 * (no in-RAM tree). Capture the leaf-centroid mean it encoded
532 * against so the page-backed query centering matches. */
533 &sa_global_mean,
534 &idx->first_posting);
535 106 vs_memctx_switch(idx_ctx);
536
537 /* The driver always launches at least one worker, so it does not fail
538 * here; on the off chance it does, the empty guard below returns. */
539
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 106 times.
106 if (!ok)
540 ✗ drv_nlist = 0;
541
542 106 ms_kmeans = (double)(now_ns() - t_phase) / 1e6;
543 }
544
545
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 106 times.
124 if (!use_driver)
546 {
547 /* --- Phase: kmeans (serial; FLAT/no-RaBitQ do not need parallel)
548 * --- */
549 18 t_phase = now_ns();
550 18 vs_memctx_switch(build_ctx);
551
552 /* Subsample by stride into a contiguous buffer for cache-friendly
553 * k-means iteration. */
554 18 uint32_t max_samples = idx->nvecs < 256000 ? idx->nvecs : 256000;
555
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
18 uint32_t stride = max_samples > 0 ? idx->nvecs / max_samples : 1;
556
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 if (stride < 1)
557 ✗ stride = 1;
558
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
18 km_nvecs = (stride > 1) ? max_samples : idx->nvecs;
559
560
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 if (stride > 1)
561 {
562 ✗ km_vectors = vs_alloc((size_t)km_nvecs * dim * sizeof(float));
563 ✗ for (uint32_t i = 0; i < km_nvecs; i++)
564 ✗ memcpy(km_vectors + (size_t)i * dim,
565 ✗ idx->all_vectors + (size_t)i * stride * dim,
566 ✗ dim * sizeof(float));
567 }
568 else
569 {
570 18 km_vectors = idx->all_vectors;
571 }
572
573 18 KMeansOptions km_opts = VS_KMEANS_OPTIONS_DEFAULT;
574
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 if (config->km_nredo > 0)
575 ✗ km_opts.nredo = config->km_nredo;
576
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 if (config->km_max_iter > 0)
577 ✗ km_opts.max_iterations = config->km_max_iter;
578
579 18 tree = vs_hkmeans_f32(
580 km_vectors,
581 km_nvecs,
582 NULL,
583 dim,
584 nlist,
585 fan_out,
586 idx->base.metric,
587 &km_opts);
588
589 18 ms_kmeans = (double)(now_ns() - t_phase) / 1e6;
590 } /* end serial in-memory k-means */
591
592 /* --- Phase: setup --- */
593 124 t_phase = now_ns();
594
595 124 vs_memctx_switch(idx_ctx);
596
597
3/4
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 124 times.
124 if (use_driver ? drv_nlist == 0 : tree == NULL)
598 {
599 ✗ vs_memctx_switch(old_ctx);
600 ✗ vs_memctx_delete(idx_ctx); /* frees idx, build_ctx, everything */
601 ✗ return NULL;
602 }
603
604
2/2
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 18 times.
124 if (use_driver)
605 {
606 /* Paged parallel build: do_parallel_build streamed the whole centroid
607 * tree + posting heads into posting_storage (no in-RAM tree). The
608 * query routes page-backed over those pages via idx->base, so skip the
609 * tree-centroid finalize entirely (the returned tree is only a carrier
610 * of leaf/level counts). */
611 106 nlist = drv_nlist;
612 106 idx->nlist = nlist;
613 106 idx->base.nlevels = drv_nlevels;
614 106 idx->base.nlist = nlist;
615
1/2
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
106 idx->base.fan_out = (uint8_t)(fan_out <= UINT8_MAX ? fan_out
616 : UINT8_MAX);
617 /* Query knobs: mirror the PG GUC defaults so the paged beam search
618 * behaves identically in both engines (a zero beam scale would
619 * collapse the beam to width 1 and skip the coverage floors). */
620 106 idx->base.centroid_error_scale = 0.0f;
621 106 idx->base.centroid_beam_scale = 0.5f;
622 /* The streaming build reserves block 0 for the meta page (and the
623 * mean's reference pages after it, left blank here: the standalone
624 * mean lives in RAM) and writes the root centroid page in place
625 * right after, following its subtrees. */
626 106 idx->base.first_centroid = prism_first_centroid_blkno(dim);
627 106 idx->base.params = vs_rabitq_create(dim, VS_RABITQ_BUILD_SEED);
628 /* The paged query needs no per-cluster lists, but the bindings API
629 * reads idx->clusters[c].count for build stats; give it zeroed entries
630 * (count 0 -> the API falls back to size estimates). */
631 106 idx->clusters = vs_alloc0((size_t)nlist * sizeof(PrismClusterList));
632 106 idx->base.pt_global_mean = vs_alloc(dim * sizeof(float));
633
1/2
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
106 if (sa_global_mean != NULL)
634 106 vs_rabitq_rotate(
635 106 idx->base.params,
636 sa_global_mean,
637 idx->base.pt_global_mean);
638 else
639 ✗ memset(idx->base.pt_global_mean, 0, (size_t)dim * sizeof(float));
640 106 idx->has_posting_data = true;
641 106 idx->posting_fmt = config->posting_fmt;
642
643 106 vs_memctx_switch(old_ctx);
644 106 vs_memctx_delete(build_ctx);
645
646
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 92 times.
106 if (stats != NULL)
647 {
648 14 stats->ms_sample = ms_sample;
649 14 stats->ms_kmeans = ms_kmeans;
650 14 stats->ms_total = ms_sample + ms_kmeans;
651 14 stats->nworkers = nworkers;
652 }
653
654 106 idx->base.centroid_storage = &idx->posting_storage.base;
655 106 idx->base.posting_storage = &idx->posting_storage.base;
656 106 idx->base.page_base = idx->posting_storage.pages;
657
658 106 idx->posting_storage.all_vectors = idx->all_vectors;
659 106 idx->posting_storage.nvecs = idx->nvecs;
660 106 idx->posting_storage.metric = idx->base.metric;
661 106 uint32_t rerank_cap = 256;
662 106 vs_topk_init(&idx->posting_storage.rerank_topk, rerank_cap);
663 212 idx->posting_storage.rerank_entries = vs_alloc(
664 106 rerank_cap * sizeof(VsTopKEntry));
665 106 idx->posting_storage.rerank_cap = rerank_cap;
666
667 106 return idx;
668 }
669
670 18 nlist = tree->nleaves;
671 18 idx->nlist = nlist;
672 18 idx->base.nlevels = (uint8_t)tree->nlevels;
673
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
18 idx->base.fan_out = (uint8_t)(fan_out <= UINT8_MAX ? fan_out : UINT8_MAX);
674 18 idx->base.nlist = nlist;
675
676 /* Normalize leaf centroids for cosine */
677
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 16 times.
18 if (idx->base.metric == DISTANCE_COSINE)
678 {
679
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
20 for (uint32_t c = 0; c < nlist; c++)
680 18 normalize_vector(hk_leaf_centroids(tree) + (size_t)c * dim, dim);
681 }
682
683 /* Global mean */
684 18 idx->global_mean = vs_alloc(dim * sizeof(float));
685 18 vs_global_mean(
686 18 hk_leaf_centroids(tree),
687 nlist,
688 dim,
689 idx->base.metric,
690 idx->global_mean);
691
692 /* Save leaf centroids for per-cluster query preparation */
693 18 idx->leaf_centroids = vs_alloc((size_t)nlist * dim * sizeof(float));
694 18 memcpy(idx->leaf_centroids,
695 18 hk_leaf_centroids(tree),
696 18 (size_t)nlist * dim * sizeof(float));
697
698 /* RaBitQ params */
699 18 idx->base.params = vs_rabitq_create(dim, VS_RABITQ_BUILD_SEED);
700
701 /* Precompute P^T * centroids for zero-alloc query path. */
702 18 idx->pt_centroids = vs_alloc((size_t)nlist * dim * sizeof(float));
703
2/2
✓ Branch 0 taken 222 times.
✓ Branch 1 taken 18 times.
240 for (uint32_t c = 0; c < nlist; c++)
704 222 vs_rabitq_rotate(
705 222 idx->base.params,
706 222 idx->leaf_centroids + (size_t)c * dim,
707 222 idx->pt_centroids + (size_t)c * dim);
708
709 18 idx->base.pt_global_mean = vs_alloc(dim * sizeof(float));
710 18 vs_rabitq_rotate(
711 18 idx->base.params, idx->global_mean, idx->base.pt_global_mean);
712
713 /* Build centroid pages */
714 18 uint32_t est_centroid_pages = nlist + 100;
715 idx->centroid_storage =
716 18 make_array_page_storage(est_centroid_pages, idx_ctx);
717
718 uint32_t max_ent =
719 18 prism_centroid_max_entries_fmt(dim, idx->base.centroid_format);
720
721 /* Temporary arrays for centroid page layout (build context) */
722 18 vs_memctx_switch(build_ctx);
723 18 BlockNumber *node_first_blkno = vs_alloc(
724 18 tree->nnodes * sizeof(BlockNumber));
725 18 idx->base.first_centroid = 0;
726 18 prism_compute_centroid_layout(
727 tree, max_ent, idx->base.first_centroid, node_first_blkno);
728
729 /* Switch back to index context for posting data.
730 * Posting lists are built before centroid pages so that
731 * centroid leaf entries store actual posting block numbers. */
732 18 vs_memctx_switch(idx_ctx);
733
734 /* Initialize per-cluster ID lists */
735
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
18 uint32_t est_per_cluster = nlist > 0 ? nvecs / nlist + 1 : 1;
736 18 idx->clusters = vs_alloc0(nlist * sizeof(PrismClusterList));
737
2/2
✓ Branch 0 taken 222 times.
✓ Branch 1 taken 18 times.
240 for (uint32_t c = 0; c < nlist; c++)
738 222 cluster_list_init(&idx->clusters[c], est_per_cluster);
739
740 18 double ms_setup = (double)(now_ns() - t_phase) / 1e6;
741 18 const PrismAssignParams bp = {
742 .dim = dim,
743 18 .metric = config->metric,
744 18 .soar_lambda = config->soar_lambda,
745 18 .boundary_epsilon = config->boundary_epsilon,
746 };
747
748 /* --- Phase: posting --- */
749 18 t_phase = now_ns();
750
751 18 double ms_parallel = 0, ms_merge = 0;
752 18 uint32_t stat_nworkers = nworkers, stat_pages = 0;
753 18 uint32_t stat_merge_in = 0, stat_merge_out = 0;
754
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
18 if (config->encode_rabitq)
755 {
756 14 idx->posting_fmt = config->posting_fmt;
757
758 /* The driver path returned above, so this is always the flat
759 * mode, which needs per-cluster vector lists. */
760 14 assign_to_cluster_lists(idx, tree, &bp, dim, nlist);
761
762 14 idx->flat_pages = vs_alloc(nlist * sizeof(char *));
763
764
2/2
✓ Branch 0 taken 186 times.
✓ Branch 1 taken 14 times.
200 for (uint32_t c = 0; c < nlist; c++)
765 {
766 186 PrismClusterList *cl = &idx->clusters[c];
767 186 const float *cent = hk_leaf_centroids(tree) + (size_t)c * dim;
768
769 PrismFlatPostingBuilder builder;
770 186 prism_flat_posting_builder_init(
771 186 &builder, idx->base.params, dim, c, cent, cl->count);
772
773
2/2
✓ Branch 0 taken 12200 times.
✓ Branch 1 taken 186 times.
12386 for (uint32_t i = 0; i < cl->count; i++)
774 {
775 12200 uint32_t vid = cl->ids[i];
776 12200 const float *vec = idx->all_vectors + (size_t)vid * dim;
777 ItemPointerData tid;
778 12200 prism_posting_set_vector_id(&tid, vid);
779 12200 prism_flat_posting_builder_add(&builder, tid, vec);
780 }
781
782 186 idx->flat_pages[c] = prism_flat_posting_builder_finish(&builder);
783 186 prism_flat_posting_builder_cleanup(&builder);
784 }
785
786 14 idx->has_posting_data = true;
787 }
788 else
789 {
790 /* No RaBitQ — still need cluster lists for brute-force */
791 4 assign_to_cluster_lists(idx, tree, &bp, dim, nlist);
792 }
793
794
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
36 idx->has_replication = config->soar_lambda > 0.0 ||
795
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 config->boundary_epsilon > 0.0;
796
797 /* --- Phase: centroid pages --- */
798 18 double ms_posting = (double)(now_ns() - t_phase) / 1e6;
799 18 t_phase = now_ns();
800 {
801 /* This (non-driver) path stores cluster indices as leaf child blocks;
802 * the inline flat query maps them to per-cluster lists. Leaf j's child
803 * is posting_base + global_leaf_index, so posting_base = 0 yields the
804 * leaf (cluster) index directly. The paged build takes the use_driver
805 * path, which writes the centroid tree itself and returns above. */
806 18 vs_memctx_switch(build_ctx);
807 18 bool needs_rq_params =
808
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 14 times.
22 (idx->base.centroid_format == PRISM_CENTROID_FMT_RABITQ ||
809
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
4 idx->base.centroid_format == PRISM_CENTROID_FMT_FASTSCAN);
810 18 prism_write_centroid_tree(
811 &idx->centroid_storage.base,
812 tree,
813 dim,
814 fan_out,
815 0, /* in-RAM tree levels are absolute */
816 idx->base.centroid_format,
817 needs_rq_params ? idx->base.params : NULL,
818
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
18 idx->global_mean,
819 0, /* posting_base: leaf child = global leaf (cluster) index */
820 1, /* head_stride: a plain index, whatever the dimension */
821 node_first_blkno,
822 NULL, /* pt_centroids on posting pages, not here */
823 NULL); /* in-RAM assignment descends the exact float tree */
824 18 vs_memctx_switch(idx_ctx);
825 }
826
827 18 double ms_centroid = (double)(now_ns() - t_phase) / 1e6;
828
829 18 vs_free(tree);
830
831 18 vs_memctx_switch(old_ctx);
832 18 vs_memctx_delete(build_ctx);
833
834 /* Fill build stats */
835
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 16 times.
18 if (stats != NULL)
836 {
837 2 stats->ms_sample = ms_sample;
838 2 stats->ms_kmeans = ms_kmeans;
839 2 stats->ms_setup = ms_setup;
840 2 stats->ms_posting = ms_posting;
841 2 stats->ms_parallel = ms_parallel;
842 2 stats->ms_merge = ms_merge;
843 2 stats->ms_centroid = ms_centroid;
844 2 stats->ms_total = ms_sample + ms_kmeans + ms_setup + ms_posting +
845 ms_centroid;
846 2 stats->nworkers = stat_nworkers;
847 2 stats->total_pages = stat_pages;
848 2 stats->merge_input = stat_merge_in;
849 2 stats->merge_output = stat_merge_out;
850 }
851
852 /* Wire storage pointers in base (concrete storage owned above) */
853 18 idx->base.centroid_storage = &idx->centroid_storage.base;
854 18 idx->base.posting_storage = &idx->posting_storage.base;
855 18 idx->base.page_base = idx->posting_storage.pages;
856
857 /* Wire rerank data on posting storage */
858 18 idx->posting_storage.all_vectors = idx->all_vectors;
859 18 idx->posting_storage.nvecs = idx->nvecs;
860 18 idx->posting_storage.metric = idx->base.metric;
861
862 /* Pre-allocate rerank buffers */
863 18 uint32_t rerank_cap = 256;
864 18 vs_topk_init(&idx->posting_storage.rerank_topk, rerank_cap);
865 36 idx->posting_storage.rerank_entries = vs_alloc(
866 18 rerank_cap * sizeof(VsTopKEntry));
867 18 idx->posting_storage.rerank_cap = rerank_cap;
868
869 18 return idx;
870 }
871
872 void
873 124 prism_index_destroy(PrismIndex *idx)
874 {
875
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 124 times.
124 if (idx == NULL)
876 ✗ return;
877
878 124 vs_topk_cleanup(&idx->posting_storage.rerank_topk);
879
880 /* Deleting the memory context frees idx and all owned data. */
881 124 vs_memctx_delete(idx->memctx);
882 }
883