| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * scan.c - Index scan for prism | ||
| 6 | * | ||
| 7 | * Uses PrismQueryState (shared with standalone) for the search hot | ||
| 8 | * path. PG-specific concerns: scan iterator protocol, memory | ||
| 9 | * contexts, query vector extraction. | ||
| 10 | * | ||
| 11 | * Memory layout: | ||
| 12 | * scan_ctx — scan lifetime (index base, query state, storage) | ||
| 13 | */ | ||
| 14 | |||
| 15 | #include <postgres.h> | ||
| 16 | |||
| 17 | #include <access/genam.h> | ||
| 18 | #include <access/relscan.h> | ||
| 19 | #include <fmgr.h> | ||
| 20 | #include <miscadmin.h> | ||
| 21 | #include <pgstat.h> | ||
| 22 | #include <utils/builtins.h> | ||
| 23 | #include <utils/memutils.h> | ||
| 24 | #include <utils/rel.h> | ||
| 25 | |||
| 26 | #include "algo/vecops.h" | ||
| 27 | #include "amcache.h" | ||
| 28 | #include "build.h" | ||
| 29 | #include "core/platform.h" | ||
| 30 | #include "index/posting_page.h" | ||
| 31 | #include "index/query_scan.h" | ||
| 32 | #include "pg/bufstorage.h" | ||
| 33 | #include "quant/rabitq.h" | ||
| 34 | #include "scan.h" | ||
| 35 | #include "scan_bound.h" | ||
| 36 | #include "support_pg.h" | ||
| 37 | #include "typeinfo.h" | ||
| 38 | #include "types/vec32.h" | ||
| 39 | |||
| 40 | /* Default nprobe — will become a GUC later */ | ||
| 41 | #define PRISM_DEFAULT_NPROBE 10 | ||
| 42 | /* | ||
| 43 | * Smallest top-k any scan is sized for. Not a default in the sense of "what | ||
| 44 | * you get when you ask for nothing" -- a query with no LIMIT is sized from | ||
| 45 | * work_mem (see resolve_top_k) -- but a floor under every sizing, so that a | ||
| 46 | * LIMIT 1 has slack for a candidate that turns out to be a dead tuple the | ||
| 47 | * heap fetch discards, and a work_mem too small to hold more still answers. | ||
| 48 | */ | ||
| 49 | |||
| 50 | /* ---------------------------------------------------------------- | ||
| 51 | * Process-global per-phase accumulators (diagnostic). | ||
| 52 | * | ||
| 53 | * Summed across every prism index scan in this backend so phase timing | ||
| 54 | * can be measured over a large query set (e.g. a full 10k-query | ||
| 55 | * benchmark run in one session) instead of eyeballing EXPLAIN on a | ||
| 56 | * single query. Exposed via vs_phase_stats() / vs_phase_stats_reset(): | ||
| 57 | * | ||
| 58 | * CREATE FUNCTION vs_phase_stats_reset() RETURNS void | ||
| 59 | * AS '$libdir/pg_vectorsearch','vs_phase_stats_reset' LANGUAGE C; | ||
| 60 | * CREATE FUNCTION vs_phase_stats() RETURNS text | ||
| 61 | * AS '$libdir/pg_vectorsearch','vs_phase_stats' LANGUAGE C; | ||
| 62 | * ---------------------------------------------------------------- */ | ||
| 63 | static uint64_t g_phase_nqueries = 0; | ||
| 64 | static uint64_t g_phase_centroid_ns = 0; | ||
| 65 | static uint64_t g_phase_posting_ns = 0; | ||
| 66 | static uint64_t g_phase_rerank_ns = 0; | ||
| 67 | static uint64_t g_phase_entries = 0; | ||
| 68 | static uint64_t g_phase_rotation_ns = 0; | ||
| 69 | /* Routing-depth histogram: deepest probe rank the final top-k came from. */ | ||
| 70 | static uint64_t g_route_sum = 0; | ||
| 71 | static uint64_t g_route_le[7] = {0}; /* <=8,16,32,64,128,256,>256 */ | ||
| 72 | |||
| 73 | 2 | PG_FUNCTION_INFO_V1(vs_phase_stats_reset); | |
| 74 | |||
| 75 | Datum | ||
| 76 | 1 | vs_phase_stats_reset(PG_FUNCTION_ARGS) | |
| 77 | { | ||
| 78 | 1 | g_phase_nqueries = 0; | |
| 79 | 1 | g_phase_centroid_ns = 0; | |
| 80 | 1 | g_phase_posting_ns = 0; | |
| 81 | 1 | g_phase_rerank_ns = 0; | |
| 82 | 1 | g_phase_entries = 0; | |
| 83 | 1 | g_phase_rotation_ns = 0; | |
| 84 | 1 | g_route_sum = 0; | |
| 85 | 1 | vs_bufcache_hits = 0; | |
| 86 | 1 | vs_bufcache_cold = 0; | |
| 87 | 1 | vs_bufcache_stale = 0; | |
| 88 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1 times.
|
8 | for (int i = 0; i < 7; i++) |
| 89 | 7 | g_route_le[i] = 0; | |
| 90 | 1 | PG_RETURN_VOID(); | |
| 91 | } | ||
| 92 | |||
| 93 | 2 | PG_FUNCTION_INFO_V1(vs_routing_stats); | |
| 94 | |||
| 95 | Datum | ||
| 96 | 1 | vs_routing_stats(PG_FUNCTION_ARGS) | |
| 97 | { | ||
| 98 | 1 | char buf[448]; | |
| 99 | 1 | uint64_t n = g_phase_nqueries ? g_phase_nqueries : 1; | |
| 100 | 1 | snprintf( | |
| 101 | buf, | ||
| 102 | sizeof(buf), | ||
| 103 | "bufcache hits=" UINT64_FORMAT " cold=" UINT64_FORMAT | ||
| 104 | " stale=" UINT64_FORMAT " | " | ||
| 105 | "queries=" UINT64_FORMAT " avg_deepest_contrib_rank=%.1f | " | ||
| 106 | "deepest-rank histogram: <=8:%.1f%% <=16:%.1f%% <=32:%.1f%% " | ||
| 107 | "<=64:%.1f%% <=128:%.1f%% <=256:%.1f%% >256:%.1f%%", | ||
| 108 | vs_bufcache_hits, | ||
| 109 | vs_bufcache_cold, | ||
| 110 | vs_bufcache_stale, | ||
| 111 | g_phase_nqueries, | ||
| 112 | 1 | (double)g_route_sum / n, | |
| 113 | 1 | 100.0 * g_route_le[0] / n, | |
| 114 | 1 | 100.0 * g_route_le[1] / n, | |
| 115 | 1 | 100.0 * g_route_le[2] / n, | |
| 116 | 1 | 100.0 * g_route_le[3] / n, | |
| 117 | 1 | 100.0 * g_route_le[4] / n, | |
| 118 | 1 | 100.0 * g_route_le[5] / n, | |
| 119 | 1 | 100.0 * g_route_le[6] / n); | |
| 120 | 1 | PG_RETURN_TEXT_P(cstring_to_text(buf)); | |
| 121 | } | ||
| 122 | |||
| 123 | ✗ | PG_FUNCTION_INFO_V1(vs_phase_stats); | |
| 124 | |||
| 125 | Datum | ||
| 126 | ✗ | vs_phase_stats(PG_FUNCTION_ARGS) | |
| 127 | { | ||
| 128 | ✗ | char buf[256]; | |
| 129 | ✗ | uint64_t n = g_phase_nqueries ? g_phase_nqueries : 1; | |
| 130 | ✗ | snprintf( | |
| 131 | buf, | ||
| 132 | sizeof(buf), | ||
| 133 | "queries=" UINT64_FORMAT " | per-query us: centroid=%.1f " | ||
| 134 | "[rot=%.1f] " | ||
| 135 | "posting=%.1f rerank=%.1f | entries/q=" UINT64_FORMAT, | ||
| 136 | g_phase_nqueries, | ||
| 137 | ✗ | (double)g_phase_centroid_ns / n / VS_NS_PER_US, | |
| 138 | ✗ | (double)g_phase_rotation_ns / n / VS_NS_PER_US, | |
| 139 | ✗ | (double)g_phase_posting_ns / n / VS_NS_PER_US, | |
| 140 | ✗ | (double)g_phase_rerank_ns / n / VS_NS_PER_US, | |
| 141 | g_phase_entries / n); | ||
| 142 | ✗ | PG_RETURN_TEXT_P(cstring_to_text(buf)); | |
| 143 | } | ||
| 144 | |||
| 145 | /* ---------------------------------------------------------------- | ||
| 146 | * Scan result entry | ||
| 147 | * ---------------------------------------------------------------- */ | ||
| 148 | |||
| 149 | typedef struct PrismScanResult | ||
| 150 | { | ||
| 151 | ItemPointerData tid; | ||
| 152 | Distance distance; | ||
| 153 | } PrismScanResult; | ||
| 154 | |||
| 155 | /* ---------------------------------------------------------------- | ||
| 156 | * Scan state | ||
| 157 | * ---------------------------------------------------------------- */ | ||
| 158 | |||
| 159 | typedef struct PrismScanState | ||
| 160 | { | ||
| 161 | /* Common index descriptor (first for cast compatibility) */ | ||
| 162 | PrismIndexBase index_base; | ||
| 163 | |||
| 164 | /* Result iterator */ | ||
| 165 | PrismScanResult *results; | ||
| 166 | uint32_t results_cap; | ||
| 167 | uint32_t nresults; | ||
| 168 | uint32_t curr; | ||
| 169 | bool first; | ||
| 170 | |||
| 171 | /* Shared query state. Allocated on the first search rather than at | ||
| 172 | * beginscan, so it can be sized for the top-k the query actually | ||
| 173 | * asks for -- the LIMIT hint arrives between the two (see | ||
| 174 | * scan_bound.c). Rebuilt only if a later search needs a larger k. */ | ||
| 175 | PrismQueryState qstate; | ||
| 176 | bool qstate_ready; | ||
| 177 | uint32_t max_nprobe; | ||
| 178 | |||
| 179 | /* Rows the enclosing LIMIT will pull, 0 when unknown */ | ||
| 180 | uint32_t scan_bound; | ||
| 181 | |||
| 182 | /* PG storage (index page I/O) */ | ||
| 183 | VsPgStorage storage; | ||
| 184 | |||
| 185 | /* EXPLAIN ANALYZE stats (accumulated across rescans) */ | ||
| 186 | PrismScanStats stats; | ||
| 187 | |||
| 188 | /* Resource owner the params checkout was registered with (the | ||
| 189 | * CurrentResourceOwner at the prism_index_base_init call below); | ||
| 190 | * the endscan release must name the same owner. */ | ||
| 191 | ResourceOwner params_owner; | ||
| 192 | |||
| 193 | MemoryContext scan_ctx; | ||
| 194 | |||
| 195 | /* | ||
| 196 | * Reads the query vector out of the ORDER BY argument: the opclass input | ||
| 197 | * type bound to this index's dimension, plus the conversion buffer a | ||
| 198 | * float32 view needs. It is the same binding build and insert use for | ||
| 199 | * column values, because the ORDER BY argument has the opclass's input | ||
| 200 | * type -- an access, not the vector itself. | ||
| 201 | */ | ||
| 202 | Vec32Access query_vector_access; | ||
| 203 | } PrismScanState; | ||
| 204 | |||
| 205 | const PrismScanStats * | ||
| 206 | 27 | prism_scan_get_stats(IndexScanDesc scan) | |
| 207 | { | ||
| 208 | 27 | PrismScanState *ss = (PrismScanState *)scan->opaque; | |
| 209 |
1/2✓ Branch 0 taken 27 times.
✗ Branch 1 not taken.
|
27 | return ss ? &ss->stats : NULL; |
| 210 | } | ||
| 211 | |||
| 212 | /* ---------------------------------------------------------------- | ||
| 213 | * beginscan | ||
| 214 | * ---------------------------------------------------------------- */ | ||
| 215 | |||
| 216 | IndexScanDesc | ||
| 217 | 349 | prism_beginscan(Relation index, int nkeys, int norderbys) | |
| 218 | { | ||
| 219 | 349 | IndexScanDesc scan = RelationGetIndexScan(index, nkeys, norderbys); | |
| 220 | |||
| 221 | 349 | MemoryContext scan_ctx = AllocSetContextCreate( | |
| 222 | CurrentMemoryContext, "prism scan", ALLOCSET_DEFAULT_SIZES); | ||
| 223 | 349 | MemoryContext old_ctx = MemoryContextSwitchTo(scan_ctx); | |
| 224 | |||
| 225 | 349 | PrismScanState *ss = palloc0(sizeof(PrismScanState)); | |
| 226 | 349 | ss->scan_ctx = scan_ctx; | |
| 227 | 349 | ss->first = true; | |
| 228 | |||
| 229 | /* Immutable index parameters from the per-backend cache (metapage read at | ||
| 230 | * most once per backend). */ | ||
| 231 | 349 | prism_index_base_init(index, &ss->index_base); | |
| 232 | 349 | ss->params_owner = CurrentResourceOwner; | |
| 233 | |||
| 234 | /* The cached mean is freed by a relcache invalidation, which an open | ||
| 235 | * scan can process between rescans, so the scan keeps its own copy. */ | ||
| 236 |
1/2✓ Branch 0 taken 349 times.
✗ Branch 1 not taken.
|
349 | if (ss->index_base.pt_global_mean != NULL) |
| 237 | { | ||
| 238 | 349 | size_t bytes = ss->index_base.dim * sizeof(float); | |
| 239 | 349 | float *mean = palloc(bytes); | |
| 240 | 349 | memcpy(mean, ss->index_base.pt_global_mean, bytes); | |
| 241 | 349 | ss->index_base.pt_global_mean = mean; | |
| 242 | } | ||
| 243 | |||
| 244 | 349 | PrismScanInfo info = prism_cache_scan_info(index); | |
| 245 | |||
| 246 | /* From the per-backend cache; the buffer must outlive a rescan. */ | ||
| 247 | 349 | ss->query_vector_access = vec32_access( | |
| 248 | 349 | prism_cache_type_info(index), ss->index_base.dim, scan_ctx); | |
| 249 | |||
| 250 | /* Size the per-scan query buffers to the nprobe actually requested | ||
| 251 | * (the GUC is set before the query runs) rather than the worst-case | ||
| 252 | * ceiling: the centroid-search scratch alone is | ||
| 253 | * O(max_nprobe * entries_per_page) candidates, several MB per query | ||
| 254 | * at the ceiling but a few hundred KB at typical nprobe. Headroom | ||
| 255 | * covers routing more leaf candidates than are scanned (bounded | ||
| 256 | * probe expansion); requests beyond the sizing are clamped by | ||
| 257 | * prism_query_execute exactly as they were against the old ceiling. */ | ||
| 258 | 237 | uint32_t req_nprobe = prism_nprobe > 0 ? (uint32_t)prism_nprobe | |
| 259 |
2/2✓ Branch 0 taken 112 times.
✓ Branch 1 taken 237 times.
|
349 | : prism_auto_nprobe(info.nlist); |
| 260 | 349 | uint32_t max_nprobe = req_nprobe + Min(req_nprobe, 256) + 16; | |
| 261 | 349 | if (max_nprobe > 4096) | |
| 262 | max_nprobe = 4096; | ||
| 263 | 349 | if (max_nprobe > info.nlist) | |
| 264 | max_nprobe = info.nlist; | ||
| 265 | 349 | ss->max_nprobe = max_nprobe; | |
| 266 | |||
| 267 | /* Always score through the fastscan path, which falls back to AoS per | ||
| 268 | * page. Fastscan is the normal format, and the cached metapage flag can | ||
| 269 | * be stale after a conversion. */ | ||
| 270 | 349 | ss->index_base.fastscan = prism_fastscan_bits; | |
| 271 | |||
| 272 | /* Initialize PG storage */ | ||
| 273 | 349 | vs_pg_storage_init(&ss->storage, index, NULL, ss->index_base.metric); | |
| 274 | 349 | ss->index_base.centroid_storage = &ss->storage.base; | |
| 275 | 349 | ss->index_base.posting_storage = &ss->storage.base; | |
| 276 | 349 | ss->index_base.page_base = NULL; | |
| 277 | |||
| 278 | /* The query state and result buffer are sized on the first search | ||
| 279 | * (ensure_query_state), once the top-k is known. */ | ||
| 280 | |||
| 281 | /* Order-by arrays */ | ||
| 282 |
1/2✓ Branch 0 taken 349 times.
✗ Branch 1 not taken.
|
349 | if (norderbys > 0) |
| 283 | { | ||
| 284 | 349 | scan->xs_orderbyvals = palloc0(norderbys * sizeof(Datum)); | |
| 285 | 349 | scan->xs_orderbynulls = palloc(norderbys * sizeof(bool)); | |
| 286 | 349 | memset(scan->xs_orderbynulls, true, norderbys * sizeof(bool)); | |
| 287 | } | ||
| 288 | |||
| 289 | 349 | MemoryContextSwitchTo(old_ctx); | |
| 290 | 349 | scan->opaque = ss; | |
| 291 | 349 | return scan; | |
| 292 | } | ||
| 293 | |||
| 294 | /* ---------------------------------------------------------------- | ||
| 295 | * rescan | ||
| 296 | * ---------------------------------------------------------------- */ | ||
| 297 | |||
| 298 | void | ||
| 299 | 368 | prism_rescan( | |
| 300 | IndexScanDesc scan, | ||
| 301 | ScanKey keys, | ||
| 302 | int nkeys, | ||
| 303 | ScanKey orderbys, | ||
| 304 | int norderbys) | ||
| 305 | { | ||
| 306 | 368 | PrismScanState *ss = (PrismScanState *)scan->opaque; | |
| 307 | |||
| 308 |
2/4✓ Branch 0 taken 368 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 368 times.
|
368 | if (keys && scan->numberOfKeys > 0) |
| 309 | ✗ | memcpy(scan->keyData, keys, scan->numberOfKeys * sizeof(ScanKeyData)); | |
| 310 |
2/4✓ Branch 0 taken 368 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 368 times.
✗ Branch 3 not taken.
|
368 | if (orderbys && scan->numberOfOrderBys > 0) |
| 311 | 368 | memcpy(scan->orderByData, | |
| 312 | orderbys, | ||
| 313 | 368 | scan->numberOfOrderBys * sizeof(ScanKeyData)); | |
| 314 | |||
| 315 | 368 | ss->first = true; | |
| 316 | 368 | ss->curr = 0; | |
| 317 | 368 | ss->nresults = 0; | |
| 318 | |||
| 319 | /* | ||
| 320 | * Size the top-k from the query's LIMIT, if this scan runs under one. | ||
| 321 | * Here rather than pushed in from the executor: by rescan the executor | ||
| 322 | * node already points at this scan, so scan_bound.c can find the right | ||
| 323 | * node by identity, and nothing has to open the scan descriptor before | ||
| 324 | * the executor would. | ||
| 325 | * | ||
| 326 | * Re-resolved on every rescan, not cached: a correlated LIMIT takes a | ||
| 327 | * new value for each outer row, and a stale one would return too few | ||
| 328 | * rows -- the very failure this exists to prevent. nodeLimit.c | ||
| 329 | * re-derives its own bound per rescan for the same reason ("in case | ||
| 330 | * this is a rescan and the previous time we got a different result"). | ||
| 331 | */ | ||
| 332 | 368 | ss->scan_bound = prism_scan_bound(scan); | |
| 333 | 368 | } | |
| 334 | |||
| 335 | /* | ||
| 336 | * Bytes the scan commits per row its top-k can return. | ||
| 337 | * | ||
| 338 | * Every allocation that scales with k, and none scale with the vector | ||
| 339 | * dimension. Sizing this from anything less makes the work_mem ceiling | ||
| 340 | * below a fiction: the extraction buffer alone is PRISM_QUERY_CAND_PER_K | ||
| 341 | * entries per row, which dominates the rest by an order of magnitude. | ||
| 342 | * | ||
| 343 | * vs_topk_init one upper bound and one id per row, plus a | ||
| 344 | * candidate array of two entries per row | ||
| 345 | * prism_query_state_init PRISM_QUERY_CAND_PER_K candidates per row and an | ||
| 346 | * index and a distance for each of them | ||
| 347 | * execute_search one result slot per row | ||
| 348 | * | ||
| 349 | * Keep in step with those three. PRISM_QUERY_CAND_PER_K is the same constant | ||
| 350 | * the allocator uses. | ||
| 351 | * | ||
| 352 | * This prices the state as initialized. extract_candidates doubles the | ||
| 353 | * extraction arrays if a query admits more candidates than the sizing | ||
| 354 | * allowed for, so a scan can exceed this budget; work_mem bounds what the | ||
| 355 | * scan asks for, not the high-water mark of a pathological query. | ||
| 356 | */ | ||
| 357 | #define PRISM_TOP_K_BYTES_PER_ROW \ | ||
| 358 | (sizeof(Distance) + sizeof(uint64_t) + 2 * sizeof(VsTopKEntry) + \ | ||
| 359 | PRISM_QUERY_CAND_PER_K * \ | ||
| 360 | (sizeof(VsTopKEntry) + sizeof(uint32_t) + sizeof(Distance)) + \ | ||
| 361 | sizeof(PrismScanResult)) | ||
| 362 | |||
| 363 | /* | ||
| 364 | * Rows the top-k may be sized to, from work_mem. | ||
| 365 | * | ||
| 366 | * The ceiling belongs to the memory the administrator granted, not to a row | ||
| 367 | * constant: a session with work_mem raised for a large query should be able | ||
| 368 | * to ask for a large LIMIT, and one with it lowered should not be able to | ||
| 369 | * commit the backend to more. The LIMIT and the relation's row count are | ||
| 370 | * inputs to the sizing rather than limits on it; prism.query_limit lowers it | ||
| 371 | * when set, and this bounds whatever the rest of the sizing arrives at. | ||
| 372 | * | ||
| 373 | * Floored at the built-in default so a query always answers something. A | ||
| 374 | * scan, unlike a split, can always return a few rows -- so a work_mem too | ||
| 375 | * small to hold more is a reason to return fewer, not to raise an error. | ||
| 376 | */ | ||
| 377 | static uint32_t | ||
| 378 | 865 | max_top_k_for_work_mem(void) | |
| 379 | { | ||
| 380 | 865 | uint64 rows = ((uint64)work_mem * 1024) / PRISM_TOP_K_BYTES_PER_ROW; | |
| 381 | |||
| 382 | 865 | if (rows < PRISM_DEFAULT_K) | |
| 383 | return PRISM_DEFAULT_K; | ||
| 384 |
1/2✓ Branch 0 taken 865 times.
✗ Branch 1 not taken.
|
865 | if (rows > PG_UINT32_MAX) |
| 385 | return PG_UINT32_MAX; | ||
| 386 | 865 | return (uint32_t)rows; | |
| 387 | } | ||
| 388 | |||
| 389 | /* | ||
| 390 | * Resolve the top-k for a search. | ||
| 391 | * | ||
| 392 | * The rows the query's LIMIT asks for (resolved by scan_bound.c) are the | ||
| 393 | * primary source. With no usable LIMIT the query has asked for every row in | ||
| 394 | * distance order, so the scan is sized for as many as it could possibly | ||
| 395 | * return: what work_mem affords, or the relation's estimated row count if | ||
| 396 | * that is smaller -- an ordered scan cannot return more rows than exist. | ||
| 397 | * Sizing for a fixed handful instead would silently answer a complete | ||
| 398 | * ordered scan with a fraction of it. | ||
| 399 | * | ||
| 400 | * prism.query_limit then lowers the result if it is set below it, and | ||
| 401 | * work_mem bounds it in every case, so a query asking for more rows than | ||
| 402 | * the backend may hold returns as many as it can. | ||
| 403 | * | ||
| 404 | * The built-in default is the floor. It keeps a little slack under a small | ||
| 405 | * LIMIT for rows the executor's heap fetch discards (deleted but not yet | ||
| 406 | * vacuumed), which would otherwise leave a LIMIT 1 empty when its single | ||
| 407 | * candidate is dead, and it leaves a query something to answer with under a | ||
| 408 | * work_mem too small to hold more. | ||
| 409 | */ | ||
| 410 | static uint32_t | ||
| 411 | 368 | resolve_top_k(const PrismScanState *ss, Relation heap) | |
| 412 | { | ||
| 413 |
1/2✓ Branch 0 taken 368 times.
✗ Branch 1 not taken.
|
368 | double rows = heap != NULL ? prism_estimate_heap_tuples(heap) : -1.0; |
| 414 | |||
| 415 | 368 | return prism_scan_resolve_top_k(ss->scan_bound, rows); | |
| 416 | } | ||
| 417 | |||
| 418 | uint32_t | ||
| 419 | 865 | prism_scan_resolve_top_k(uint32_t scan_bound, double heap_rows) | |
| 420 | { | ||
| 421 |
1/2✓ Branch 0 taken 865 times.
✗ Branch 1 not taken.
|
865 | uint32_t cap = max_top_k_for_work_mem(); |
| 422 | 865 | uint32_t k = scan_bound; | |
| 423 | |||
| 424 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 857 times.
|
865 | if (k == 0) |
| 425 | { | ||
| 426 | /* No LIMIT to size from: the query has asked for every row in | ||
| 427 | * order, so size for as many as it could return. */ | ||
| 428 | 8 | k = cap; | |
| 429 |
3/4✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 1 times.
|
8 | if (heap_rows >= 1.0 && heap_rows < (double)cap) |
| 430 | 7 | k = (uint32_t)heap_rows; | |
| 431 | } | ||
| 432 | |||
| 433 | /* | ||
| 434 | * prism.query_limit only ever lowers the sizing. Raising it above what | ||
| 435 | * the query asked for would have the scan rank rows the LIMIT then | ||
| 436 | * throws away; the lever exists to cap a query that asks for too much | ||
| 437 | * -- one with no LIMIT, or with one set far higher than the rows the | ||
| 438 | * caller will read. | ||
| 439 | */ | ||
| 440 |
2/2✓ Branch 0 taken 35 times.
✓ Branch 1 taken 830 times.
|
865 | if (prism_query_limit > 0 && (uint32_t)prism_query_limit < k) |
| 441 | 865 | k = (uint32_t)prism_query_limit; | |
| 442 | |||
| 443 | 865 | if (k < PRISM_DEFAULT_K) | |
| 444 | k = PRISM_DEFAULT_K; | ||
| 445 | |||
| 446 | 865 | return k > cap ? cap : k; | |
| 447 | } | ||
| 448 | |||
| 449 | /* | ||
| 450 | * Allocate (or resize) the shared query state and result buffer for a | ||
| 451 | * top-k of at least k. prism_query_execute clamps k to the allocated | ||
| 452 | * max_k, so undersizing here is what silently truncates results. | ||
| 453 | * | ||
| 454 | * A resize discards the previous state rather than adding to it. Every | ||
| 455 | * buffer in it is sized to max_k, and a rescan can resize -- a correlated | ||
| 456 | * LIMIT resolves afresh for each outer row -- so keeping the old ones | ||
| 457 | * would accumulate a full set per resize for the life of the scan. | ||
| 458 | * prism_query_state_cleanup owns that: the state holds its buffers in a | ||
| 459 | * context of its own. | ||
| 460 | * | ||
| 461 | * The result array is deliberately not part of that state. It grows with | ||
| 462 | * what the rerank returns rather than with the sizing, so it lives in the | ||
| 463 | * scan context where repalloc preserves it across a resize. | ||
| 464 | */ | ||
| 465 | static void | ||
| 466 | 368 | ensure_query_state(PrismScanState *ss, uint32_t k) | |
| 467 | { | ||
| 468 | 368 | uint32_t max_k = Max(k, (uint32_t)PRISM_DEFAULT_K); | |
| 469 | |||
| 470 |
4/4✓ Branch 0 taken 19 times.
✓ Branch 1 taken 349 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 15 times.
|
368 | if (ss->qstate_ready && max_k <= ss->qstate.max_k) |
| 471 | return; | ||
| 472 | |||
| 473 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 349 times.
|
353 | MemoryContext old_ctx = MemoryContextSwitchTo(ss->scan_ctx); |
| 474 | |||
| 475 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 349 times.
|
353 | if (ss->qstate_ready) |
| 476 | { | ||
| 477 | 4 | prism_query_state_cleanup(&ss->qstate); | |
| 478 | 4 | ss->qstate_ready = false; | |
| 479 | } | ||
| 480 | |||
| 481 | 353 | prism_query_state_init( | |
| 482 | &ss->qstate, &ss->index_base, max_k, ss->max_nprobe); | ||
| 483 | 353 | prism_posting_scan_enable_fastscan(&ss->qstate.pscan, prism_fastscan_bits); | |
| 484 | 353 | ss->qstate_ready = true; | |
| 485 | |||
| 486 | /* The error-bound rerank can return more than max_k results, so this | ||
| 487 | * is a starting size; execute_search grows it as needed. */ | ||
| 488 |
1/2✓ Branch 0 taken 353 times.
✗ Branch 1 not taken.
|
353 | if (ss->results_cap < max_k) |
| 489 | { | ||
| 490 | 353 | size_t bytes = max_k * sizeof(PrismScanResult); | |
| 491 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 349 times.
|
353 | ss->results = ss->results ? repalloc(ss->results, bytes) |
| 492 | 349 | : palloc(bytes); | |
| 493 | 353 | ss->results_cap = max_k; | |
| 494 | } | ||
| 495 | |||
| 496 | 353 | MemoryContextSwitchTo(old_ctx); | |
| 497 | } | ||
| 498 | |||
| 499 | /* ---------------------------------------------------------------- | ||
| 500 | * Search execution (called on first gettuple) | ||
| 501 | * ---------------------------------------------------------------- */ | ||
| 502 | |||
| 503 | static void | ||
| 504 | 368 | execute_search(IndexScanDesc scan) | |
| 505 | { | ||
| 506 | 368 | PrismScanState *ss = (PrismScanState *)scan->opaque; | |
| 507 | |||
| 508 | /* | ||
| 509 | * Count the search where it runs, as every core AM does at the start of | ||
| 510 | * its own search: pg_stat_*_indexes.idx_scan, and the per-scan counter | ||
| 511 | * PostgreSQL 18 prints as EXPLAIN's "Index Searches" (also the one a | ||
| 512 | * parallel scan aggregates across workers). Core's indexam.c maintains | ||
| 513 | * neither; it counts only the tuples the scan returns. | ||
| 514 | */ | ||
| 515 |
3/4✓ Branch 0 taken 5 times.
✓ Branch 1 taken 363 times.
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
|
368 | pgstat_count_index_scan(scan->indexRelation); |
| 516 |
1/2✓ Branch 0 taken 368 times.
✗ Branch 1 not taken.
|
368 | if (scan->instrument != NULL) |
| 517 | 368 | scan->instrument->nsearches++; | |
| 518 | |||
| 519 | 368 | uint32_t k = resolve_top_k(ss, scan->heapRelation); | |
| 520 | 368 | ensure_query_state(ss, k); | |
| 521 | |||
| 522 | /* Lazily set heap relation for reranking (rel is NULL at | ||
| 523 | * beginscan time; heapRelation becomes available later) */ | ||
| 524 |
3/4✓ Branch 0 taken 368 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 349 times.
✓ Branch 3 taken 19 times.
|
368 | if (scan->heapRelation != NULL && ss->storage.rel == NULL) |
| 525 | 349 | vs_pg_storage_set_rel( | |
| 526 | 349 | &ss->storage, scan->heapRelation, scan->xs_snapshot); | |
| 527 | |||
| 528 | /* | ||
| 529 | * Extract query vector. The ORDER BY operator belongs to the opclass, so | ||
| 530 | * its argument has the opclass's input type and the same descriptor | ||
| 531 | * converts it -- into the scan-lifetime buffer, so a rescan does not leak | ||
| 532 | * one per execution. vec32_read rejects a dimension mismatch. | ||
| 533 | */ | ||
| 534 | 368 | Datum query_datum = scan->orderByData[0].sk_argument; | |
| 535 | 368 | Vec32Ref qref = vec32_read(&ss->query_vector_access, query_datum); | |
| 536 | |||
| 537 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 368 times.
|
368 | if (qref.dim != ss->index_base.dim) |
| 538 | ✗ | ereport(ERROR, | |
| 539 | (errcode(ERRCODE_DATA_EXCEPTION), | ||
| 540 | errmsg("query dimension %u does not match " | ||
| 541 | "index dimension %u", | ||
| 542 | qref.dim, | ||
| 543 | ss->index_base.dim))); | ||
| 544 | |||
| 545 | /* Execute shared search */ | ||
| 546 | 250 | uint32_t nprobe = prism_nprobe > 0 | |
| 547 | ? (uint32_t)prism_nprobe | ||
| 548 |
2/2✓ Branch 0 taken 118 times.
✓ Branch 1 taken 250 times.
|
368 | : prism_auto_nprobe(ss->index_base.nlist); |
| 549 | |||
| 550 | 368 | PrismQueryStats qstats = {0}; | |
| 551 | 368 | ss->storage.read_count = 0; | |
| 552 | |||
| 553 | 368 | prism_query_execute( | |
| 554 | &ss->qstate, | ||
| 555 | qref.data, | ||
| 556 | k, | ||
| 557 | nprobe, | ||
| 558 | (VsDistanceMode)prism_distance_mode, | ||
| 559 | prism_rerank, | ||
| 560 | &qstats); | ||
| 561 | |||
| 562 | 368 | ss->stats.clusters_scanned = qstats.clusters_scanned; | |
| 563 | 368 | ss->stats.centroid_pages_read = qstats.centroid_pages_read; | |
| 564 | 368 | ss->stats.posting_pages_read = qstats.posting_pages_read; | |
| 565 | 368 | ss->stats.posting_pages_skipped = qstats.posting_pages_skipped; | |
| 566 | 368 | ss->stats.posting_entries_scanned = qstats.posting_entries_scanned; | |
| 567 | 368 | ss->stats.rerank_candidates = ss->qstate.ncandidates; | |
| 568 | 368 | ss->stats.rerank_results = ss->qstate.nresults; | |
| 569 | 368 | ss->stats.storage_reads = ss->storage.read_count; | |
| 570 | 368 | ss->stats.top_k = k; | |
| 571 | 368 | ss->stats.centroid_ns = qstats.centroid_ns; | |
| 572 | 368 | ss->stats.posting_ns = qstats.posting_ns; | |
| 573 | 368 | ss->stats.rerank_ns = qstats.rerank_ns; | |
| 574 | |||
| 575 | /* Accumulate into the process-global diagnostic counters. */ | ||
| 576 | 368 | g_phase_nqueries++; | |
| 577 | 368 | g_phase_centroid_ns += qstats.centroid_ns; | |
| 578 | 368 | g_phase_posting_ns += qstats.posting_ns; | |
| 579 | 368 | g_phase_rerank_ns += qstats.rerank_ns; | |
| 580 | 368 | g_phase_entries += qstats.posting_entries_scanned; | |
| 581 | 368 | g_phase_rotation_ns += qstats.rotation_ns; | |
| 582 | |||
| 583 | { | ||
| 584 | 368 | uint32_t r = qstats.max_contrib_rank; | |
| 585 | 368 | g_route_sum += r; | |
| 586 |
2/2✓ Branch 0 taken 355 times.
✓ Branch 1 taken 13 times.
|
368 | if (r <= 8) |
| 587 | 355 | g_route_le[0]++; | |
| 588 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 5 times.
|
13 | else if (r <= 16) |
| 589 | 8 | g_route_le[1]++; | |
| 590 |
1/2✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
|
5 | else if (r <= 32) |
| 591 | 5 | g_route_le[2]++; | |
| 592 | ✗ | else if (r <= 64) | |
| 593 | ✗ | g_route_le[3]++; | |
| 594 | ✗ | else if (r <= 128) | |
| 595 | ✗ | g_route_le[4]++; | |
| 596 | ✗ | else if (r <= 256) | |
| 597 | ✗ | g_route_le[5]++; | |
| 598 | else | ||
| 599 | ✗ | g_route_le[6]++; | |
| 600 | } | ||
| 601 | |||
| 602 | /* Copy results from result ordering. The error-bound rerank can return | ||
| 603 | * more than the beginscan max_k (the rerank set is inflated beyond k to | ||
| 604 | * guarantee correctness), so grow the result buffer to fit. */ | ||
| 605 | 368 | uint32_t nresults = ss->qstate.nresults; | |
| 606 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 368 times.
|
368 | if (nresults > ss->results_cap) |
| 607 | { | ||
| 608 | ✗ | ss->results = | |
| 609 | ✗ | repalloc(ss->results, nresults * sizeof(PrismScanResult)); | |
| 610 | ✗ | ss->results_cap = nresults; | |
| 611 | } | ||
| 612 |
2/2✓ Branch 0 taken 11503 times.
✓ Branch 1 taken 368 times.
|
11871 | for (uint32_t i = 0; i < nresults; i++) |
| 613 | { | ||
| 614 | 11503 | uint32_t ci = ss->qstate.result_order[i]; | |
| 615 | 11503 | ss->results[i].tid = prism_posting_decode_tid( | |
| 616 | 11503 | ss->qstate.candidates[ci].id); | |
| 617 | 11503 | ss->results[i].distance = ss->qstate.result_dists[i]; | |
| 618 | } | ||
| 619 | 368 | ss->nresults = nresults; | |
| 620 | 368 | ss->curr = 0; | |
| 621 | 368 | } | |
| 622 | |||
| 623 | /* ---------------------------------------------------------------- | ||
| 624 | * gettuple | ||
| 625 | * ---------------------------------------------------------------- */ | ||
| 626 | |||
| 627 | bool | ||
| 628 | 9484 | prism_gettuple(IndexScanDesc scan, ScanDirection direction) | |
| 629 | { | ||
| 630 | 9484 | PrismScanState *ss = (PrismScanState *)scan->opaque; | |
| 631 | |||
| 632 | 9484 | (void)direction; | |
| 633 | |||
| 634 |
2/2✓ Branch 0 taken 368 times.
✓ Branch 1 taken 9116 times.
|
9484 | if (ss->first) |
| 635 | { | ||
| 636 | 368 | ss->first = false; | |
| 637 | |||
| 638 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 368 times.
|
368 | if (scan->numberOfOrderBys == 0) |
| 639 | return false; | ||
| 640 | |||
| 641 | 368 | execute_search(scan); | |
| 642 | } | ||
| 643 | |||
| 644 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 9460 times.
|
9484 | if (ss->curr >= ss->nresults) |
| 645 | return false; | ||
| 646 | |||
| 647 | 9460 | PrismScanResult *entry = &ss->results[ss->curr]; | |
| 648 | |||
| 649 | 9460 | scan->xs_heaptid = entry->tid; | |
| 650 | |||
| 651 | /* prism never returns a lossy match: the heap tuple always satisfies | ||
| 652 | * the original qual, so no recheck is ever needed. */ | ||
| 653 | 9460 | scan->xs_recheck = false; | |
| 654 | 9460 | scan->xs_recheckorderby = false; | |
| 655 | 9460 | scan->xs_orderbyvals[0] = Float8GetDatum((double)entry->distance); | |
| 656 | 9460 | scan->xs_orderbynulls[0] = false; | |
| 657 | |||
| 658 | 9460 | ss->curr++; | |
| 659 | 9460 | return true; | |
| 660 | } | ||
| 661 | |||
| 662 | /* ---------------------------------------------------------------- | ||
| 663 | * endscan | ||
| 664 | * ---------------------------------------------------------------- */ | ||
| 665 | |||
| 666 | void | ||
| 667 | 347 | prism_endscan(IndexScanDesc scan) | |
| 668 | { | ||
| 669 | 347 | PrismScanState *ss = (PrismScanState *)scan->opaque; | |
| 670 | |||
| 671 |
1/2✓ Branch 0 taken 347 times.
✗ Branch 1 not taken.
|
347 | if (ss != NULL) |
| 672 | { | ||
| 673 |
1/2✓ Branch 0 taken 347 times.
✗ Branch 1 not taken.
|
347 | if (ss->qstate_ready) |
| 674 | 347 | prism_query_state_cleanup(&ss->qstate); | |
| 675 | /* Check the RaBitQParams checkout back in before the scan's own | ||
| 676 | * memory goes away — see prism_index_base_init / the beginscan | ||
| 677 | * call above. */ | ||
| 678 | 347 | prism_release_params( | |
| 679 | 347 | ss->index_base.dim, | |
| 680 | ss->index_base.rabitq_seed, | ||
| 681 | ss->params_owner); | ||
| 682 | 347 | MemoryContextDelete(ss->scan_ctx); | |
| 683 | 347 | scan->opaque = NULL; | |
| 684 | } | ||
| 685 | 347 | } | |
| 686 |