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