GCC Code Coverage Report


Directory: src/
File: src/pg/cost.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 165 168 98.2%
Functions: 10 10 100.0%
Branches: 58 71 81.7%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * cost.c - Cost model for vector index scans
6 *
7 * Prices the work a scan actually does: descending the centroid tree,
8 * scanning the posting lists it routes to, and reranking the candidates
9 * that survive. Everything comes from the scalars on the index's metapage
10 * plus the planner's own statistics, so the estimate reads no index page.
11 *
12 * Page access is priced by how each page is reached rather than uniformly:
13 * dependent reads at random_page_cost, prefetched batches at
14 * seq_page_cost.
15 *
16 * The top-k, the filter margin, the routed cluster count and the rerank
17 * pool size are resolved by the same functions in scan.c, scan_bound.c and
18 * query_scan.c that the scan itself calls. Constants are in cost.h.
19 */
20
21 #include <postgres.h>
22
23 #include <access/heaptoast.h>
24 #include <access/relation.h>
25 #include <catalog/pg_class.h>
26 #include <math.h>
27 #include <optimizer/cost.h>
28 #include <optimizer/optimizer.h>
29 #include <storage/bufmgr.h>
30 #include <storage/lmgr.h>
31 #include <utils/lsyscache.h>
32 #include <utils/rel.h>
33 #include <utils/selfuncs.h>
34 #include <utils/spccache.h>
35 #include <utils/syscache.h>
36
37 #include "amcache.h"
38 #include "cost.h"
39 #include "index/centroid_page.h"
40 #include "index/index_base.h"
41 #include "index/posting_page.h"
42 #include "index/query_scan.h"
43 #include "scan.h"
44 #include "scan_bound.h"
45 #include "support_pg.h"
46
47 /*
48 * Everything the individual terms below need, collected once so each can be
49 * read on its own.
50 */
51 typedef struct CostInputs
52 {
53 /* index shape, from the metapage */
54 Dimension dim;
55 uint32_t nlevels; /* centroid tree depth */
56 bool has_fastscan; /* posting page format the index was built in */
57 PrismCentroidFormat centroid_format;
58
59 /* what this particular query will do */
60 uint32_t nlist; /* posting lists in the index */
61 uint32_t nprobe; /* lists it will scan */
62 double n_route;
63 /*
64 * Clusters the descent routes to and scores exactly, of which the best
65 * nprobe are then scanned. Equal to nprobe with exact centroid pages,
66 * larger when compressed ones make probe expansion worthwhile.
67 */
68 uint32_t k_eff; /* rows it will elect */
69 double beam;
70 /*
71 * Candidates the beam search keeps at each level -- not the tree's
72 * fan-out, which is how many children a node has. A level scores about
73 * beam * fan_out candidates and keeps beam of them.
74 */
75
76 /* page counts derived from those */
77 double centroid_pages; /* the whole centroid region */
78 bool flat_tree; /* one level: the descent reads all of it */
79 double descent_pages;
80 double pages_per_list;
81 /* Pages a routed list's reference occupies, its head pages: 1 for an
82 * inline layout, START, MIDDLE and END once the dimension spills. */
83 double ref_pages;
84 double probed_pages; /* pages of the lists this query will scan */
85 double scanned_pl_entries;
86 /*
87 * Entries in the posting lists this query will scan -- not the entries
88 * on a page, in one list, or in the whole index. Multiplied by the
89 * per-entry scoring rate, and the pool size when reranking is uncapped.
90 */
91
92 /* the planner's page prices for this index's tablespace */
93 double spc_random;
94 double spc_seq;
95
96 /* repetitions of this scan inside a nested loop; 1 when not repeated */
97 double loop_count;
98 } CostInputs;
99
100 /*
101 * Rows the query will pull from the scan, before any filter inflation.
102 *
103 * limit_tuples is the best answer but is absent more often than it looks:
104 * an unfoldable LIMIT $1 leaves it at -1, and so does a LIMIT above the
105 * subquery or CTE holding the ORDER BY. The executor finds a bound in both
106 * cases, so treating them as unbounded would size the scan for a full
107 * ranking. tuple_fraction covers them.
108 *
109 * Zero means genuinely unbounded, and prism_scan_resolve_top_k sizes for
110 * every row the scan could return.
111 *
112 * Three cases resolve in the planner's favour, since the plan has to be
113 * chosen on the planner's information: WITH TIES, where the executor
114 * treats the scan as unbounded; a cursor with no LIMIT, where
115 * cursor_tuple_fraction sizes k at a tenth of the rows the executor will
116 * rank; and an outer LIMIT above a join or CTE, where both agree on
117 * unbounded.
118 */
119 static uint32_t
120 497 row_target(PlannerInfo *root, double heap_rows)
121 {
122 497 double rows = -1.0;
123
124
3/4
✓ Branch 0 taken 486 times.
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 486 times.
497 if (root->limit_tuples > 0.0 && isfinite(root->limit_tuples))
125 rows = root->limit_tuples;
126
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
11 else if (root->tuple_fraction >= 1.0 && isfinite(root->tuple_fraction))
127 rows = root->tuple_fraction;
128
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
10 else if (root->tuple_fraction > 0.0)
129 6 rows = root->tuple_fraction * heap_rows;
130
131
1/2
✓ Branch 0 taken 493 times.
✗ Branch 1 not taken.
493 if (rows < 1.0)
132 return 0;
133
1/2
✓ Branch 0 taken 493 times.
✗ Branch 1 not taken.
493 if (rows >= (double)PG_UINT32_MAX)
134 return PG_UINT32_MAX;
135
136 493 return (uint32_t)ceil(rows);
137 }
138
139 /*
140 * Page fetches one scan is charged for, given that it touches `pages`
141 * distinct pages and will be repeated loop_count times.
142 *
143 * Repeating a scan does not re-read what is still cached, so the fetches
144 * are counted across all the repetitions and then pro-rated back to one
145 * scan -- genericcostestimate's shape, and the reason loop_count is passed
146 * to an AM at all. Without it a parameterized scan is charged full price
147 * for every repetition of pages it read on the first.
148 */
149 static double
150 2481 pages_fetched_per_scan(
151 double pages,
152 BlockNumber rel_pages,
153 double index_pages,
154 double loop_count,
155 PlannerInfo *root)
156 {
157
2/2
✓ Branch 0 taken 2158 times.
✓ Branch 1 taken 323 times.
2481 if (pages <= 0.0)
158 return 0.0;
159
160
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2158 times.
2158 if (loop_count > 1.0)
161 ✗ return index_pages_fetched(
162 ✗ pages * loop_count, rel_pages, index_pages, root) /
163 loop_count;
164
165 2158 return index_pages_fetched(pages, rel_pages, index_pages, root);
166 }
167
168 /*
169 * True when reranking a candidate has to reach the toast relation for its
170 * vector rather than reading it from the heap tuple.
171 *
172 * Needs a toast relation (heap-family tables only) and a column whose
173 * attstorage permits out-of-line storage. Where the values actually live
174 * then comes from the statistics rather than the declared width, since
175 * whether a value went out of line depends on its compressibility, the
176 * other columns in the row and the storage mode -- none of which the
177 * dimension reveals. Without statistics the declared width is the only
178 * evidence available.
179 *
180 * An expression index reports inline: it can detoast the same way, but the
181 * column to look up is not recoverable from indexkeys.
182 */
183 static bool
184 495 indexed_column_uses_toast(
185 PlannerInfo *root,
186 RelOptInfo *baserel,
187 IndexOptInfo *info,
188 Dimension dim)
189 {
190
2/4
✓ Branch 0 taken 495 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 495 times.
495 if (info->nkeycolumns < 1 || info->indexkeys[0] <= 0)
191 return false; /* expression index: nothing to look up */
192
193 495 AttrNumber attnum = info->indexkeys[0];
194 495 Oid reloid = root->simple_rte_array[baserel->relid]->relid;
195
196 495 HeapTuple reltup = SearchSysCache1(RELOID, ObjectIdGetDatum(reloid));
197
198
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 495 times.
495 if (!HeapTupleIsValid(reltup))
199 return false;
200
201 495 bool has_toast = OidIsValid(
202 ((Form_pg_class)GETSTRUCT(reltup))->reltoastrelid);
203
204 495 ReleaseSysCache(reltup);
205
206
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 495 times.
495 if (!has_toast)
207 return false;
208
209 /*
210 * Statistics first, because they say where the values *are* rather than
211 * where new ones would go: SET STORAGE does not rewrite existing rows,
212 * so a column switched to PLAIN can still be full of out-of-line values
213 * that cost a toast fetch. A stored width far below the vector's own is
214 * a pointer; the threshold is half the inline width so that a value
215 * compressed but kept in the tuple counts as inline, paying a
216 * decompress but no toast lookup.
217 */
218 495 Size inline_width = VARHDRSZ + sizeof(int32) + sizeof(float) * dim;
219 495 int32 avgwidth = get_attavgwidth(reloid, attnum);
220
221
2/2
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 372 times.
495 if (avgwidth > 0)
222 123 return (Size)avgwidth < inline_width / 2;
223
224 /*
225 * No statistics, so fall back on what the column is declared to allow
226 * and how wide a vector of this dimension would be. attstorage is PLAIN
227 * for a type that cannot be toasted and for a column explicitly set that
228 * way; EXTENDED, EXTERNAL and MAIN all permit out-of-line storage,
229 * differing only in whether compression is tried first and how hard the
230 * value is kept inline.
231 */
232 372 HeapTuple atttup = SearchSysCache2(
233 ATTNUM, ObjectIdGetDatum(reloid), Int16GetDatum(attnum));
234
235
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 372 times.
372 if (!HeapTupleIsValid(atttup))
236 return false;
237
238 372 char storage = ((Form_pg_attribute)GETSTRUCT(atttup))->attstorage;
239
240 372 ReleaseSysCache(atttup);
241
242
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 372 times.
372 if (storage == TYPSTORAGE_PLAIN)
243 return false;
244
245 372 return inline_width > TOAST_TUPLE_THRESHOLD;
246 }
247
248 /*
249 * Collect the index's shape and the sizing this query will use.
250 */
251 static void
252 497 gather_cost_inputs(
253 PlannerInfo *root,
254 IndexPath *path,
255 double loop_count,
256 CostInputs *in,
257 double *selectivity)
258 {
259 497 IndexOptInfo *info = path->indexinfo;
260 497 RelOptInfo *baserel = info->rel;
261
262 /*
263 * The index's own description of itself: vector dimension, number of
264 * posting lists, depth and fan-out of the centroid tree, the page format
265 * it was built in, and where the posting region starts. These live on the
266 * metapage and are cached per backend, so this costs one page read for
267 * the first plan in a backend and nothing afterwards. NoLock because the
268 * planner already holds one, asserted below.
269 */
270 497 Relation index = index_open(info->indexoid, NoLock);
271
272
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 497 times.
497 Assert(CheckRelationLockedByMe(index, AccessShareLock, true));
273
274 497 PrismScanInfo si = prism_cache_scan_info(index);
275
276 497 index_close(index, NoLock);
277
278 497 in->dim = si.dim;
279 497 in->nlevels = si.nlevels;
280 497 in->has_fastscan = si.has_fastscan;
281 497 in->centroid_format = si.centroid_format;
282 497 in->nlist = si.nlist > 0 ? si.nlist : 1;
283
284 /* Rows in the table, as the index and then the relation see them. */
285
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 495 times.
497 double N = info->tuples > 0.0 ? info->tuples : baserel->tuples;
286
287 497 if (N < 1.0)
288 N = 1.0;
289
290 /*
291 * Quals the executor applies above the scan do not restrict what the
292 * scan returns -- they discard rows after it has returned them -- so a
293 * selective filter means the scan has to find proportionally more rows
294 * to leave the requested number standing. Hence the top-k is inflated by
295 * the selectivity, not reduced by it.
296 *
297 * indrestrictinfo rather than baserestrictinfo, because a partial index
298 * has already excluded the rows its predicate rejects: those never reach
299 * the scan, so inflating for them would size the top-k for rows the
300 * index does not contain. It is the same list cost_index uses to charge
301 * its own qual costs. A parameterized path also has ppi_clauses applied
302 * above the scan, which appear in neither list, so a lateral scan with a
303 * join filter is under-inflated.
304 */
305 497 double sel = 1.0;
306
307
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 489 times.
497 if (info->indrestrictinfo != NIL)
308 8 sel = clauselist_selectivity(
309 8 root, info->indrestrictinfo, baserel->relid, JOIN_INNER, NULL);
310
311 /*
312 * Rows the scan will actually elect. prism_scan_resolve_top_k applies the
313 * rules the scan applies: the prism.query_limit ceiling, a floor so a tiny
314 * LIMIT still produces a usable search, and a work_mem-derived cap. With
315 * no LIMIT to size from it uses the row count instead.
316 */
317 497 uint32_t k = prism_scan_inflate_for_filter(row_target(root, N), sel);
318
319 497 in->k_eff = prism_scan_resolve_top_k(k, N);
320
321 /*
322 * Posting lists this query will scan: pinned by prism.nprobe when that is
323 * set, otherwise derived from the index's list count, and never more
324 * lists than exist.
325 */
326 295 uint32_t nprobe = prism_nprobe > 0 ? (uint32_t)prism_nprobe
327
2/2
✓ Branch 0 taken 202 times.
✓ Branch 1 taken 295 times.
497 : prism_auto_nprobe(in->nlist);
328
329 497 if (nprobe > in->nlist)
330 nprobe = in->nlist;
331
332 497 in->nprobe = nprobe;
333
334 /*
335 * Clusters the descent routes to, which is at least nprobe and can be
336 * more: with compressed centroids the beam's ordering is approximate, so
337 * the scan routes a wider set and phase A re-ranks it on exact centroid
338 * distances before scanning the best nprobe. Each routed cluster costs a
339 * head page read whether or not its list is then scanned.
340 */
341 497 in->n_route = (double)prism_query_routed_clusters(
342 nprobe, in->nlist, in->centroid_format);
343
344 /*
345 * Centroid slots the beam keeps per level, from the scan's own rule.
346 */
347 994 in->beam = (double)prism_query_beam_width(
348 497 nprobe, in->nlist, si.fan_out, prism_centroid_beam_scale);
349
350 /*
351 * Taken from the metapage, which the build sets and prism_rebalance keeps
352 * current. It cannot be derived from the block range: a split with no
353 * room on a level-0 page chains the new centroid page past the posting
354 * region, so first_posting stops bounding the count.
355 */
356 497 double centroid_pages = (double)si.ncentroid_pages;
357
358
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 497 times.
497 if (centroid_pages < 1.0)
359 ✗ centroid_pages = 1.0;
360
361 497 in->centroid_pages = centroid_pages;
362 497 in->flat_tree = in->nlevels <= 1;
363
364 /*
365 * Pages the descent reads, which is not the same as slots it examines. A
366 * single-level tree is read in full, beam width not entering into it.
367 * Below a root, one read per kept slot per level is the right shape,
368 * each level following child_blkno from the last level's survivors --
369 * approximate in both directions, since the root is read whole however
370 * wide the beam, and a parent's children can straddle pages. The region
371 * bounds it either way.
372 */
373
2/2
✓ Branch 0 taken 380 times.
✓ Branch 1 taken 117 times.
497 if (in->flat_tree)
374 380 in->descent_pages = centroid_pages;
375 else
376 117 in->descent_pages =
377
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 113 times.
117 Min(centroid_pages, (double)in->nlevels * in->beam);
378
379 /*
380 * Every page the centroid pages do not account for, with the lists taken
381 * as evenly sized. Taken from the maintained count rather than from
382 * first_posting: a split that appends a centroid page past the posting
383 * region would otherwise put that page in this term as well as the
384 * centroid one.
385 *
386 * This errs both ways. Dead entries on live pages are read and scored
387 * like any other, so counting their pages is right; free and retired
388 * pages are never visited, so a badly bloated index is over-charged.
389 * Uneven lists cut both ways too, the probe set being chosen by the
390 * query rather than uniformly.
391 */
392 994 double posting_pages = prism_index_posting_pages(
393
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 429 times.
497 (double)info->pages, in->dim, (double)si.ncentroid_pages);
394
395 497 in->pages_per_list = posting_pages / (double)in->nlist;
396 497 in->ref_pages = (double)prism_posting_reference_pages(in->dim);
397
398 497 in->probed_pages = (double)nprobe * in->pages_per_list;
399
400 /*
401 * Entries the probed lists hold: a bound, not a prediction, since how
402 * much of a page survives the error-bound gate moves with the data.
403 *
404 * Rows give the tighter of the two available bounds -- a query sees
405 * nprobe of nlist lists' worth, plus a little for replicas. Page
406 * capacity assumes full pages and badly over-counts a sparse index, so
407 * the smaller is taken.
408 */
409 497 double row_entries = (double)nprobe / (double)in->nlist * N *
410 PRISM_ENTRY_REPLICA_FACTOR;
411 /*
412 * Whichever layout packs more entries into a full page, since this is
413 * an upper bound and an index built in one format can hold pages of the
414 * other. Taking the AoS figure alone under-bounds a fastscan index at
415 * the dimensions where grouped pages hold more. One fastscan page can
416 * count more entries than the average when it holds deferred metadata,
417 * but every entry's codes and metadata take room on some page, so the
418 * average still bounds the probed pages together.
419 */
420 497 double page_entries = in->probed_pages *
421 497 prism_posting_entries_per_page(in->dim);
422
423 497 in->scanned_pl_entries = Min(row_entries, page_entries);
424
425 497 get_tablespace_page_costs(
426 497 info->reltablespace, &in->spc_random, &in->spc_seq);
427
428 497 in->loop_count = loop_count > 1.0 ? loop_count : 1.0;
429
430 /*
431 * The scan emits k_eff rows; the core applies the qual to them and
432 * arrives at roughly k output rows, charging heap fetches for k_eff.
433 */
434
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 17 times.
497 *selectivity = Min(1.0, (double)in->k_eff / N);
435 497 }
436
437 /*
438 * Descending the centroid tree to decide which posting lists to scan. Two
439 * parts, measuring different work.
440 *
441 * The beam search: `beam` is how many candidates the search keeps per
442 * level, not the tree's fan-out. Each level scores the children of the
443 * kept parents and keeps the best beam again for the level below.
444 *
445 * Phase A: with compressed centroid pages the beam's ordering is
446 * approximate, so it hands down n_route candidates -- nprobe or more --
447 * whose full-precision pt_centroids are scored exactly to decide which
448 * nprobe actually get scanned.
449 *
450 * Both are CPU only; the pages these reads touch are priced in
451 * search_page_cost.
452 */
453 /*
454 * What scoring one centroid costs, which depends on the format its page
455 * was built in. FLOAT and HALF pages hold full-precision vectors and are
456 * scored with float kernels; RABITQ and FASTSCAN hold quantized codes, the
457 * first scored one vector at a time and the second in interleaved groups.
458 */
459 static double
460 497 centroid_score_cost(const CostInputs *in)
461 {
462
3/3
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 323 times.
✓ Branch 2 taken 152 times.
497 switch (in->centroid_format)
463 {
464 22 case PRISM_CENTROID_FMT_FLOAT:
465 case PRISM_CENTROID_FMT_HALF:
466 22 return PRISM_COST_EXACT_DISTANCE(in->dim);
467 323 case PRISM_CENTROID_FMT_FASTSCAN:
468 323 return PRISM_COST_QUANT_DISTANCE(in->dim);
469 152 default:
470 152 return PRISM_COST_QUANT_DISTANCE(in->dim) *
471 PRISM_COST_UNGROUPED_PENALTY;
472 }
473 }
474
475 static double
476 497 centroid_descent_cost(const CostInputs *in)
477 {
478 /*
479 * The beam scores the children of every slot it keeps, at each level,
480 * bounded by what the pages it reads can hold.
481 */
482 497 double slots = in->descent_pages * (double)prism_centroid_max_entries_fmt(
483 497 in->dim, in->centroid_format);
484
485 /*
486 * Page capacity assumes full pages, which badly over-counts a small
487 * tree. Wherever the descent reads the whole region it cannot score
488 * more centroids than the tree holds, so nlist is the better bound --
489 * this covers a two-level tree sharing one page as well as a
490 * single-level one. Where only part of the region is read, the pages
491 * read are the bound.
492 *
493 * nlist counts the leaves; internal nodes add 1/fan_out more, which a
494 * wide fan-out makes negligible here.
495 */
496
2/2
✓ Branch 0 taken 496 times.
✓ Branch 1 taken 1 times.
497 if (in->descent_pages >= in->centroid_pages && slots > (double)in->nlist)
497 497 slots = (double)in->nlist;
498
499 497 double beam_work = slots * centroid_score_cost(in);
500
501 /*
502 * Phase A then scores one exact distance per routed cluster, against
503 * the full-precision pt_centroid on its head page.
504 */
505 497 double head_work = in->n_route * PRISM_COST_EXACT_DISTANCE(in->dim);
506
507 497 return beam_work + head_work;
508 }
509
510 /*
511 * Scanning the probed posting lists: opening each one, then scoring every
512 * entry in it against the query's quantized code.
513 */
514 static double
515 497 posting_cpu_cost(const CostInputs *in)
516 {
517 /*
518 * Opening a list builds the query state against the list's centroid --
519 * a handful of O(dim) passes over the query vector -- priced as one
520 * exact distance for the same shape. The head page it reads is counted
521 * with the pages, not here.
522 */
523 497 double list_open = PRISM_COST_EXACT_DISTANCE(in->dim);
524
525 /* One quantized distance per entry; AoS pages are not grouped. */
526 497 double per_entry = PRISM_COST_QUANT_DISTANCE(in->dim);
527
528
2/2
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 400 times.
497 if (!in->has_fastscan)
529 97 per_entry *= PRISM_COST_UNGROUPED_PENALTY;
530
531 /*
532 * Every scored entry is offered to the top-k heap, and a bigger heap
533 * costs more per offer, so the rate rises with the logarithm of k.
534 */
535 497 double topk_factor = 1.0;
536
537
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 427 times.
497 if (in->k_eff > PRISM_DEFAULT_K)
538 70 topk_factor += PRISM_COST_TOPK_LOG_COEFF *
539 70 log2((double)in->k_eff / (double)PRISM_DEFAULT_K);
540
541 497 return (double)in->nprobe * list_open +
542 497 in->scanned_pl_entries * per_entry * topk_factor;
543 }
544
545 /*
546 * Reading the index pages a search touches: the descent's centroid pages,
547 * the routed lists' head pages, and the rest of each probed chain.
548 *
549 * Priced by how each page is reached rather than uniformly. The three kinds
550 * of page a scan touches are reached in three different ways, and pricing
551 * them alike would put most of the estimate into seek latency that most of
552 * the reads never wait for.
553 */
554 static double
555 497 search_page_cost(const CostInputs *in, PlannerInfo *root, IndexOptInfo *info)
556 {
557 /*
558 * A single-level tree's centroid region is read in full and the build
559 * lays it out contiguously before the posting pages, so those reads are
560 * sequential -- less so once a split has chained a centroid page at the
561 * relation's tail. Below a root each level's reads are chosen by the
562 * level above, so they are dependent seeks.
563 */
564 994 double descent_io = pages_fetched_per_scan(
565 497 in->descent_pages,
566 info->pages,
567 497 (double)info->pages,
568 497 in->loop_count,
569 root) *
570
2/2
✓ Branch 0 taken 380 times.
✓ Branch 1 taken 117 times.
497 (in->flat_tree ? in->spc_seq : in->spc_random);
571
572 /*
573 * The scan prefetches every routed head page before reading any (a
574 * spilled layout reads its reference pages right behind the head), so
575 * these are a batch of overlapped reads rather than seeks and are
576 * priced sequentially -- except where effective_io_concurrency is zero
577 * and the storage layer's prefetch is a no-op, which is the same test
578 * the storage layer applies. No cost function consults
579 * effective_io_concurrency, so switching between the two page costs is
580 * the closest the planner's currency allows.
581 */
582 994 double head_io = pages_fetched_per_scan(
583 497 in->n_route * in->ref_pages,
584 info->pages,
585 497 (double)info->pages,
586 497 in->loop_count,
587 root) *
588 497 (effective_io_concurrency > 0 ? in->spc_seq
589
2/2
✓ Branch 0 taken 496 times.
✓ Branch 1 taken 1 times.
497 : in->spc_random);
590
591 /*
592 * The rest of each probed chain, the head having been charged above.
593 * Prefetching a head does not bring its overflow pages into shared
594 * buffers, so these are real additional reads -- priced sequentially,
595 * the build laying a chain out contiguously and the scan walking it
596 * forward.
597 */
598 497 double chain_pages = (double)in->nprobe *
599 497 (in->pages_per_list - in->ref_pages);
600
601 497 if (chain_pages < 0.0)
602 chain_pages = 0.0;
603
604 994 double chain_io = pages_fetched_per_scan(
605 chain_pages,
606 info->pages,
607 497 (double)info->pages,
608 497 in->loop_count,
609 root) *
610 497 in->spc_seq;
611
612 497 return descent_io + head_io + chain_io;
613 }
614
615 /*
616 * Reranking: settling the top-k on exact distances, and the costliest part
617 * of a scan. The posting scan only ever scores quantized codes, so the
618 * result is decided by fetching the most promising candidates' full
619 * vectors and measuring those -- a heap fetch, a detoast where the vector
620 * is out of line, and one exact distance each.
621 *
622 * The pool has three modes. Reranking off costs nothing. A capped pool
623 * uses the estimator's own number. An uncapped pool reranks every survivor
624 * of the error-bound gate, and prism_query_rerank_pool_estimate reports that
625 * as 0 -- the value the extract step reads as "keep them all", so it must
626 * not be taken at face value: here 0 is the widest pool there is. It is
627 * charged at every entry the scan scores, an over-estimate, for a setting
628 * asking for the slowest and most accurate scan.
629 *
630 * A capped pool also has a floor the planner cannot see, a fraction of the
631 * candidates actually found. Where it binds, this under-estimates.
632 *
633 * Known error: out-of-line vectors leave a heap of pointers, and
634 * baserel->pages is all the planner has -- the toast relation carries no
635 * statistics. So such a column is charged for a small heap plus the
636 * per-candidate detoast, while the same vectors inline are charged for the
637 * large heap they make. At scale the detoast term dominates and the
638 * ordering is right; on a small table it is backwards, and a sequential
639 * scan over a toasted column can win an estimate it loses badly in
640 * practice.
641 */
642 static double
643 497 rerank_cost(
644 const CostInputs *in,
645 PlannerInfo *root,
646 RelOptInfo *baserel,
647 IndexOptInfo *info)
648 {
649
2/2
✓ Branch 0 taken 495 times.
✓ Branch 1 taken 2 times.
497 if (!prism_rerank)
650 return 0.0;
651
652 495 uint32_t capped = prism_query_rerank_pool_estimate(in->k_eff, in->nprobe);
653
2/2
✓ Branch 0 taken 490 times.
✓ Branch 1 taken 5 times.
495 double pool = capped > 0 ? (double)capped : in->scanned_pl_entries;
654
655 495 bool external = indexed_column_uses_toast(root, baserel, info, in->dim);
656 /*
657 * Reaching one tuple is what cpu_tuple_cost prices; scoring it is one
658 * exact distance over the vector it holds.
659 */
660 495 double per_fetch = cpu_tuple_cost + PRISM_COST_EXACT_DISTANCE(in->dim);
661
662
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 395 times.
495 if (external)
663 100 per_fetch *= PRISM_COST_FETCH_DETOAST;
664
665 /*
666 * Every pool candidate is scored exactly, and where the vectors are out
667 * of line every one of them is also detoasted. That is all index work:
668 * nothing above the scan knows the pool exists.
669 */
670 495 double cpu = pool * per_fetch;
671
672 /*
673 * An index AM does not charge for reaching parent-table rows --
674 * cost_index does that from the selectivity reported here, covering
675 * k_eff tuples. But the pool is wider than k_eff, and those extra reads
676 * are invisible from outside, so they are what this term charges.
677 *
678 * The subtraction has to happen in pages, not candidates:
679 * Mackert-Lohman saturates at the heap's size, so on a small heap the
680 * pool already touches every page and removing candidates removes no
681 * pages, billing cost_index's survivors a second time in full. Pricing
682 * the difference between the pool's pages and the survivors' leaves
683 * only what cost_index has not already paid for.
684 *
685 * Both rerank paths sort into TID order and, on a heap-AM table, fetch
686 * through a streaming read, so these run forward with the gaps' latency
687 * hidden -- the same situation as the routed head pages and priced the
688 * same way.
689 */
690 990 double pool_pages = pages_fetched_per_scan(
691 495 pool, baserel->pages, (double)info->pages, in->loop_count, root);
692 990 double charged_pages = pages_fetched_per_scan(
693 495 (double)in->k_eff,
694 baserel->pages,
695 495 (double)info->pages,
696 495 in->loop_count,
697 root);
698 495 double extra_pages = pool_pages - charged_pages;
699
700 495 if (extra_pages < 0.0)
701 extra_pages = 0.0;
702
703 990 double io = extra_pages *
704
2/2
✓ Branch 0 taken 494 times.
✓ Branch 1 taken 1 times.
495 (effective_io_concurrency > 0 ? in->spc_seq : in->spc_random);
705
706 495 return cpu + io;
707 }
708
709 void
710 497 prism_cost_estimate(
711 PlannerInfo *root,
712 IndexPath *path,
713 double loop_count,
714 Cost *startup_cost,
715 Cost *total_cost,
716 Selectivity *selectivity,
717 double *correlation,
718 double *index_pages)
719 {
720 497 IndexOptInfo *info = path->indexinfo;
721 497 RelOptInfo *baserel = info->rel;
722 497 CostInputs in;
723 497 double sel;
724
725 497 gather_cost_inputs(root, path, loop_count, &in, &sel);
726
727 1491 double per_scan_cost = PRISM_COST_SCAN_SETUP + centroid_descent_cost(&in) +
728 497 posting_cpu_cost(&in) +
729 497 search_page_cost(&in, root, info) +
730 497 rerank_cost(&in, root, baserel, info);
731
732 /*
733 * All of it is startup work: the scan elects its whole top-k before it
734 * can return the first tuple, so a LIMIT must not discount it.
735 *
736 * The figure is for one scan. cost_nestloop applies loop_count itself,
737 * so multiplying here too would charge the square of the outer row
738 * count; loop_count is used for the cache argument instead, the way
739 * genericcostestimate uses it.
740 *
741 * In practice it is always 1 here: match_clause_to_ordering_op only
742 * accepts an ORDER BY operator whose other operand contains no Var, so
743 * a distance against another relation's column never yields a
744 * parameterized path, and the lateral form's PARAM_EXEC sits inside a
745 * subquery whose own planner sees 1. The handling is what the contract
746 * specifies.
747 */
748 497 *startup_cost = per_scan_cost;
749 497 *total_cost = *startup_cost + (double)in.k_eff * cpu_index_tuple_cost;
750
751 497 *selectivity = sel;
752
753 /* Nothing orders a vector scan's output by heap position. */
754 497 *correlation = 0.0;
755
756 /* The pages search_page_cost prices, so a parallel plan divides the
757 * same count this estimate was built from. */
758 497 *index_pages = in.descent_pages + in.n_route * in.ref_pages +
759 497 (double)in.nprobe * (in.pages_per_list - in.ref_pages);
760 497 }
761