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