GCC Code Coverage Report

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