| 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 |