PostgreSQL Source Code  git master
index_selfuncs.h File Reference
#include "access/amapi.h"
Include dependency graph for index_selfuncs.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void brincostestimate (struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
 
void btcostestimate (struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
 
void hashcostestimate (struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
 
void gistcostestimate (struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
 
void spgcostestimate (struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
 
void gincostestimate (struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
 

Function Documentation

◆ brincostestimate()

void brincostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 7334 of file selfuncs.c.

References Abs, Assert, attnum, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BRIN_DEFAULT_PAGES_PER_RANGE, brinGetStats(), CLAMP_PROBABILITY, clauselist_selectivity(), cpu_operator_cost, elog, ERROR, free_attstatsslot(), VariableStatData::freefunc, get_attstatsslot(), get_index_stats_hook, get_quals_from_indexclauses(), get_relation_stats_hook, get_tablespace_page_costs(), HeapTupleIsValid, IndexOptInfo::hypothetical, index_close(), index_open(), index_other_operands_eval_cost(), IndexPath::indexclauses, IndexClause::indexcol, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, Int16GetDatum, InvalidOid, JOIN_INNER, lfirst_node, Max, Min, AttStatsSlot::nnumbers, NoLock, AttStatsSlot::numbers, ObjectIdGetDatum, RelOptInfo::pages, IndexOptInfo::pages, BrinStatsData::pagesPerRange, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reltablespace, REVMAP_PAGE_MAXITEMS, BrinStatsData::revmapNumPages, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

7338 {
7339  IndexOptInfo *index = path->indexinfo;
7340  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7341  double numPages = index->pages;
7342  RelOptInfo *baserel = index->rel;
7343  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7344  Cost spc_seq_page_cost;
7345  Cost spc_random_page_cost;
7346  double qual_arg_cost;
7347  double qualSelectivity;
7348  BrinStatsData statsData;
7349  double indexRanges;
7350  double minimalRanges;
7351  double estimatedRanges;
7352  double selec;
7353  Relation indexRel;
7354  ListCell *l;
7355  VariableStatData vardata;
7356 
7357  Assert(rte->rtekind == RTE_RELATION);
7358 
7359  /* fetch estimated page cost for the tablespace containing the index */
7361  &spc_random_page_cost,
7362  &spc_seq_page_cost);
7363 
7364  /*
7365  * Obtain some data from the index itself, if possible. Otherwise invent
7366  * some plausible internal statistics based on the relation page count.
7367  */
7368  if (!index->hypothetical)
7369  {
7370  /*
7371  * A lock should have already been obtained on the index in plancat.c.
7372  */
7373  indexRel = index_open(index->indexoid, NoLock);
7374  brinGetStats(indexRel, &statsData);
7375  index_close(indexRel, NoLock);
7376 
7377  /* work out the actual number of ranges in the index */
7378  indexRanges = Max(ceil((double) baserel->pages /
7379  statsData.pagesPerRange), 1.0);
7380  }
7381  else
7382  {
7383  /*
7384  * Assume default number of pages per range, and estimate the number
7385  * of ranges based on that.
7386  */
7387  indexRanges = Max(ceil((double) baserel->pages /
7389 
7391  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
7392  }
7393 
7394  /*
7395  * Compute index correlation
7396  *
7397  * Because we can use all index quals equally when scanning, we can use
7398  * the largest correlation (in absolute value) among columns used by the
7399  * query. Start at zero, the worst possible case. If we cannot find any
7400  * correlation statistics, we will keep it as 0.
7401  */
7402  *indexCorrelation = 0;
7403 
7404  foreach(l, path->indexclauses)
7405  {
7406  IndexClause *iclause = lfirst_node(IndexClause, l);
7407  AttrNumber attnum = index->indexkeys[iclause->indexcol];
7408 
7409  /* attempt to lookup stats in relation for this index column */
7410  if (attnum != 0)
7411  {
7412  /* Simple variable -- look to stats for the underlying table */
7414  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7415  {
7416  /*
7417  * The hook took control of acquiring a stats tuple. If it
7418  * did supply a tuple, it'd better have supplied a freefunc.
7419  */
7420  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7421  elog(ERROR,
7422  "no function provided to release variable stats with");
7423  }
7424  else
7425  {
7426  vardata.statsTuple =
7428  ObjectIdGetDatum(rte->relid),
7429  Int16GetDatum(attnum),
7430  BoolGetDatum(false));
7431  vardata.freefunc = ReleaseSysCache;
7432  }
7433  }
7434  else
7435  {
7436  /*
7437  * Looks like we've found an expression column in the index. Let's
7438  * see if there's any stats for it.
7439  */
7440 
7441  /* get the attnum from the 0-based index. */
7442  attnum = iclause->indexcol + 1;
7443 
7444  if (get_index_stats_hook &&
7445  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7446  {
7447  /*
7448  * The hook took control of acquiring a stats tuple. If it
7449  * did supply a tuple, it'd better have supplied a freefunc.
7450  */
7451  if (HeapTupleIsValid(vardata.statsTuple) &&
7452  !vardata.freefunc)
7453  elog(ERROR, "no function provided to release variable stats with");
7454  }
7455  else
7456  {
7458  ObjectIdGetDatum(index->indexoid),
7459  Int16GetDatum(attnum),
7460  BoolGetDatum(false));
7461  vardata.freefunc = ReleaseSysCache;
7462  }
7463  }
7464 
7465  if (HeapTupleIsValid(vardata.statsTuple))
7466  {
7467  AttStatsSlot sslot;
7468 
7469  if (get_attstatsslot(&sslot, vardata.statsTuple,
7470  STATISTIC_KIND_CORRELATION, InvalidOid,
7472  {
7473  double varCorrelation = 0.0;
7474 
7475  if (sslot.nnumbers > 0)
7476  varCorrelation = Abs(sslot.numbers[0]);
7477 
7478  if (varCorrelation > *indexCorrelation)
7479  *indexCorrelation = varCorrelation;
7480 
7481  free_attstatsslot(&sslot);
7482  }
7483  }
7484 
7485  ReleaseVariableStats(vardata);
7486  }
7487 
7488  qualSelectivity = clauselist_selectivity(root, indexQuals,
7489  baserel->relid,
7490  JOIN_INNER, NULL);
7491 
7492  /*
7493  * Now calculate the minimum possible ranges we could match with if all of
7494  * the rows were in the perfect order in the table's heap.
7495  */
7496  minimalRanges = ceil(indexRanges * qualSelectivity);
7497 
7498  /*
7499  * Now estimate the number of ranges that we'll touch by using the
7500  * indexCorrelation from the stats. Careful not to divide by zero (note
7501  * we're using the absolute value of the correlation).
7502  */
7503  if (*indexCorrelation < 1.0e-10)
7504  estimatedRanges = indexRanges;
7505  else
7506  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7507 
7508  /* we expect to visit this portion of the table */
7509  selec = estimatedRanges / indexRanges;
7510 
7511  CLAMP_PROBABILITY(selec);
7512 
7513  *indexSelectivity = selec;
7514 
7515  /*
7516  * Compute the index qual costs, much as in genericcostestimate, to add to
7517  * the index costs. We can disregard indexorderbys, since BRIN doesn't
7518  * support those.
7519  */
7520  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7521 
7522  /*
7523  * Compute the startup cost as the cost to read the whole revmap
7524  * sequentially, including the cost to execute the index quals.
7525  */
7526  *indexStartupCost =
7527  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7528  *indexStartupCost += qual_arg_cost;
7529 
7530  /*
7531  * To read a BRIN index there might be a bit of back and forth over
7532  * regular pages, as revmap might point to them out of sequential order;
7533  * calculate the total cost as reading the whole index in random order.
7534  */
7535  *indexTotalCost = *indexStartupCost +
7536  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7537 
7538  /*
7539  * Charge a small amount per range tuple which we expect to match to. This
7540  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7541  * will set a bit for each page in the range when we find a matching
7542  * range, so we must multiply the charge by the number of pages in the
7543  * range.
7544  */
7545  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7546  statsData.pagesPerRange;
7547 
7548  *indexPages = index->pages;
7549 }
IndexOptInfo * indexinfo
Definition: pathnodes.h:1209
HeapTuple statsTuple
Definition: selfuncs.h:74
int nnumbers
Definition: lsyscache.h:54
#define Min(x, y)
Definition: c.h:928
#define Int16GetDatum(X)
Definition: postgres.h:451
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:76
Oid reltablespace
Definition: pathnodes.h:818
bool hypothetical
Definition: pathnodes.h:856
List * indexclauses
Definition: pathnodes.h:1210
#define Abs(x)
Definition: c.h:934
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:822
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:60
RelOptInfo * rel
Definition: pathnodes.h:819
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1138
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:372
AttrNumber indexcol
Definition: pathnodes.h:1258
#define lfirst_node(type, lc)
Definition: pg_list.h:172
#define NoLock
Definition: lockdefs.h:34
float4 * numbers
Definition: lsyscache.h:53
double cpu_operator_cost
Definition: costsize.c:122
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:5916
#define BRIN_DEFAULT_PAGES_PER_RANGE
Definition: brin.h:38
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:144
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:692
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1164
#define REVMAP_PAGE_MAXITEMS
Definition: brin_page.h:93
#define BoolGetDatum(X)
Definition: postgres.h:402
#define InvalidOid
Definition: postgres_ext.h:36
BlockNumber pagesPerRange
Definition: brin.h:33
int16 attnum
Definition: pg_attribute.h:79
#define Max(x, y)
Definition: c.h:922
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:5946
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
BlockNumber pages
Definition: pathnodes.h:703
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3052
#define Assert(condition)
Definition: c.h:746
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:145
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:158
RTEKind rtekind
Definition: parsenodes.h:981
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:84
e
Definition: preproc-init.c:82
#define elog(elevel,...)
Definition: elog.h:214
int * indexkeys
Definition: pathnodes.h:829
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
Definition: pg_list.h:50
int16 AttrNumber
Definition: attnum.h:21
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:132
double Cost
Definition: nodes.h:662
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1086
BlockNumber revmapNumPages
Definition: brin.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3169

◆ btcostestimate()

void btcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6239 of file selfuncs.c.

References add_predicate_to_index_quals(), ScalarArrayOpExpr::args, Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, clauselist_selectivity(), cpu_operator_cost, elog, ERROR, estimate_array_length(), free_attstatsslot(), VariableStatData::freefunc, genericcostestimate(), get_attstatsslot(), get_index_stats_hook, get_op_opfamily_strategy(), get_opfamily_member(), get_relation_stats_hook, HeapTupleIsValid, IndexPath::indexclauses, IndexClause::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, IndexClause::indexquals, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst_node, linitial_oid, lsecond, MemSet, NIL, IndexOptInfo::nkeycolumns, AttStatsSlot::nnumbers, nodeTag, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum, OidIsValid, IndexOptInfo::opcintype, IndexOptInfo::opfamily, OpExpr::opno, ScalarArrayOpExpr::opno, RowCompareExpr::opnos, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reverse_sort, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

6243 {
6244  IndexOptInfo *index = path->indexinfo;
6245  GenericCosts costs;
6246  Oid relid;
6247  AttrNumber colnum;
6248  VariableStatData vardata;
6249  double numIndexTuples;
6250  Cost descentCost;
6251  List *indexBoundQuals;
6252  int indexcol;
6253  bool eqQualHere;
6254  bool found_saop;
6255  bool found_is_null_op;
6256  double num_sa_scans;
6257  ListCell *lc;
6258 
6259  /*
6260  * For a btree scan, only leading '=' quals plus inequality quals for the
6261  * immediately next attribute contribute to index selectivity (these are
6262  * the "boundary quals" that determine the starting and stopping points of
6263  * the index scan). Additional quals can suppress visits to the heap, so
6264  * it's OK to count them in indexSelectivity, but they should not count
6265  * for estimating numIndexTuples. So we must examine the given indexquals
6266  * to find out which ones count as boundary quals. We rely on the
6267  * knowledge that they are given in index column order.
6268  *
6269  * For a RowCompareExpr, we consider only the first column, just as
6270  * rowcomparesel() does.
6271  *
6272  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6273  * index scans not one, but the ScalarArrayOpExpr's operator can be
6274  * considered to act the same as it normally does.
6275  */
6276  indexBoundQuals = NIL;
6277  indexcol = 0;
6278  eqQualHere = false;
6279  found_saop = false;
6280  found_is_null_op = false;
6281  num_sa_scans = 1;
6282  foreach(lc, path->indexclauses)
6283  {
6284  IndexClause *iclause = lfirst_node(IndexClause, lc);
6285  ListCell *lc2;
6286 
6287  if (indexcol != iclause->indexcol)
6288  {
6289  /* Beginning of a new column's quals */
6290  if (!eqQualHere)
6291  break; /* done if no '=' qual for indexcol */
6292  eqQualHere = false;
6293  indexcol++;
6294  if (indexcol != iclause->indexcol)
6295  break; /* no quals at all for indexcol */
6296  }
6297 
6298  /* Examine each indexqual associated with this index clause */
6299  foreach(lc2, iclause->indexquals)
6300  {
6301  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6302  Expr *clause = rinfo->clause;
6303  Oid clause_op = InvalidOid;
6304  int op_strategy;
6305 
6306  if (IsA(clause, OpExpr))
6307  {
6308  OpExpr *op = (OpExpr *) clause;
6309 
6310  clause_op = op->opno;
6311  }
6312  else if (IsA(clause, RowCompareExpr))
6313  {
6314  RowCompareExpr *rc = (RowCompareExpr *) clause;
6315 
6316  clause_op = linitial_oid(rc->opnos);
6317  }
6318  else if (IsA(clause, ScalarArrayOpExpr))
6319  {
6320  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6321  Node *other_operand = (Node *) lsecond(saop->args);
6322  int alength = estimate_array_length(other_operand);
6323 
6324  clause_op = saop->opno;
6325  found_saop = true;
6326  /* count number of SA scans induced by indexBoundQuals only */
6327  if (alength > 1)
6328  num_sa_scans *= alength;
6329  }
6330  else if (IsA(clause, NullTest))
6331  {
6332  NullTest *nt = (NullTest *) clause;
6333 
6334  if (nt->nulltesttype == IS_NULL)
6335  {
6336  found_is_null_op = true;
6337  /* IS NULL is like = for selectivity purposes */
6338  eqQualHere = true;
6339  }
6340  }
6341  else
6342  elog(ERROR, "unsupported indexqual type: %d",
6343  (int) nodeTag(clause));
6344 
6345  /* check for equality operator */
6346  if (OidIsValid(clause_op))
6347  {
6348  op_strategy = get_op_opfamily_strategy(clause_op,
6349  index->opfamily[indexcol]);
6350  Assert(op_strategy != 0); /* not a member of opfamily?? */
6351  if (op_strategy == BTEqualStrategyNumber)
6352  eqQualHere = true;
6353  }
6354 
6355  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6356  }
6357  }
6358 
6359  /*
6360  * If index is unique and we found an '=' clause for each column, we can
6361  * just assume numIndexTuples = 1 and skip the expensive
6362  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6363  * NullTest invalidates that theory, even though it sets eqQualHere.
6364  */
6365  if (index->unique &&
6366  indexcol == index->nkeycolumns - 1 &&
6367  eqQualHere &&
6368  !found_saop &&
6369  !found_is_null_op)
6370  numIndexTuples = 1.0;
6371  else
6372  {
6373  List *selectivityQuals;
6374  Selectivity btreeSelectivity;
6375 
6376  /*
6377  * If the index is partial, AND the index predicate with the
6378  * index-bound quals to produce a more accurate idea of the number of
6379  * rows covered by the bound conditions.
6380  */
6381  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
6382 
6383  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6384  index->rel->relid,
6385  JOIN_INNER,
6386  NULL);
6387  numIndexTuples = btreeSelectivity * index->rel->tuples;
6388 
6389  /*
6390  * As in genericcostestimate(), we have to adjust for any
6391  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6392  * to integer.
6393  */
6394  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6395  }
6396 
6397  /*
6398  * Now do generic index cost estimation.
6399  */
6400  MemSet(&costs, 0, sizeof(costs));
6401  costs.numIndexTuples = numIndexTuples;
6402 
6403  genericcostestimate(root, path, loop_count, &costs);
6404 
6405  /*
6406  * Add a CPU-cost component to represent the costs of initial btree
6407  * descent. We don't charge any I/O cost for touching upper btree levels,
6408  * since they tend to stay in cache, but we still have to do about log2(N)
6409  * comparisons to descend a btree of N leaf tuples. We charge one
6410  * cpu_operator_cost per comparison.
6411  *
6412  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6413  * ones after the first one are not startup cost so far as the overall
6414  * plan is concerned, so add them only to "total" cost.
6415  */
6416  if (index->tuples > 1) /* avoid computing log(0) */
6417  {
6418  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6419  costs.indexStartupCost += descentCost;
6420  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6421  }
6422 
6423  /*
6424  * Even though we're not charging I/O cost for touching upper btree pages,
6425  * it's still reasonable to charge some CPU cost per page descended
6426  * through. Moreover, if we had no such charge at all, bloated indexes
6427  * would appear to have the same search cost as unbloated ones, at least
6428  * in cases where only a single leaf page is expected to be visited. This
6429  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6430  * touched. The number of such pages is btree tree height plus one (ie,
6431  * we charge for the leaf page too). As above, charge once per SA scan.
6432  */
6433  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6434  costs.indexStartupCost += descentCost;
6435  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6436 
6437  /*
6438  * If we can get an estimate of the first column's ordering correlation C
6439  * from pg_statistic, estimate the index correlation as C for a
6440  * single-column index, or C * 0.75 for multiple columns. (The idea here
6441  * is that multiple columns dilute the importance of the first column's
6442  * ordering, but don't negate it entirely. Before 8.0 we divided the
6443  * correlation by the number of columns, but that seems too strong.)
6444  */
6445  MemSet(&vardata, 0, sizeof(vardata));
6446 
6447  if (index->indexkeys[0] != 0)
6448  {
6449  /* Simple variable --- look to stats for the underlying table */
6450  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6451 
6452  Assert(rte->rtekind == RTE_RELATION);
6453  relid = rte->relid;
6454  Assert(relid != InvalidOid);
6455  colnum = index->indexkeys[0];
6456 
6458  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6459  {
6460  /*
6461  * The hook took control of acquiring a stats tuple. If it did
6462  * supply a tuple, it'd better have supplied a freefunc.
6463  */
6464  if (HeapTupleIsValid(vardata.statsTuple) &&
6465  !vardata.freefunc)
6466  elog(ERROR, "no function provided to release variable stats with");
6467  }
6468  else
6469  {
6471  ObjectIdGetDatum(relid),
6472  Int16GetDatum(colnum),
6473  BoolGetDatum(rte->inh));
6474  vardata.freefunc = ReleaseSysCache;
6475  }
6476  }
6477  else
6478  {
6479  /* Expression --- maybe there are stats for the index itself */
6480  relid = index->indexoid;
6481  colnum = 1;
6482 
6483  if (get_index_stats_hook &&
6484  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6485  {
6486  /*
6487  * The hook took control of acquiring a stats tuple. If it did
6488  * supply a tuple, it'd better have supplied a freefunc.
6489  */
6490  if (HeapTupleIsValid(vardata.statsTuple) &&
6491  !vardata.freefunc)
6492  elog(ERROR, "no function provided to release variable stats with");
6493  }
6494  else
6495  {
6497  ObjectIdGetDatum(relid),
6498  Int16GetDatum(colnum),
6499  BoolGetDatum(false));
6500  vardata.freefunc = ReleaseSysCache;
6501  }
6502  }
6503 
6504  if (HeapTupleIsValid(vardata.statsTuple))
6505  {
6506  Oid sortop;
6507  AttStatsSlot sslot;
6508 
6509  sortop = get_opfamily_member(index->opfamily[0],
6510  index->opcintype[0],
6511  index->opcintype[0],
6513  if (OidIsValid(sortop) &&
6514  get_attstatsslot(&sslot, vardata.statsTuple,
6515  STATISTIC_KIND_CORRELATION, sortop,
6517  {
6518  double varCorrelation;
6519 
6520  Assert(sslot.nnumbers == 1);
6521  varCorrelation = sslot.numbers[0];
6522 
6523  if (index->reverse_sort[0])
6524  varCorrelation = -varCorrelation;
6525 
6526  if (index->nkeycolumns > 1)
6527  costs.indexCorrelation = varCorrelation * 0.75;
6528  else
6529  costs.indexCorrelation = varCorrelation;
6530 
6531  free_attstatsslot(&sslot);
6532  }
6533  }
6534 
6535  ReleaseVariableStats(vardata);
6536 
6537  *indexStartupCost = costs.indexStartupCost;
6538  *indexTotalCost = costs.indexTotalCost;
6539  *indexSelectivity = costs.indexSelectivity;
6540  *indexCorrelation = costs.indexCorrelation;
6541  *indexPages = costs.numIndexPages;
6542 }
Selectivity indexSelectivity
Definition: selfuncs.h:109
#define NIL
Definition: pg_list.h:65
#define IsA(nodeptr, _type_)
Definition: nodes.h:579
IndexOptInfo * indexinfo
Definition: pathnodes.h:1209
HeapTuple statsTuple
Definition: selfuncs.h:74
int nnumbers
Definition: lsyscache.h:54
double tuples
Definition: pathnodes.h:704
#define Int16GetDatum(X)
Definition: postgres.h:451
Definition: nodes.h:528
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:76
#define MemSet(start, val, len)
Definition: c.h:950
List * indexclauses
Definition: pathnodes.h:1210
double Selectivity
Definition: nodes.h:661
double tuples
Definition: pathnodes.h:823
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: pathnodes.h:824
#define OidIsValid(objectId)
Definition: c.h:652
#define lsecond(l)
Definition: pg_list.h:179
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2132
RelOptInfo * rel
Definition: pathnodes.h:819
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1138
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:372
AttrNumber indexcol
Definition: pathnodes.h:1258
double num_sa_scans
Definition: selfuncs.h:116
#define lfirst_node(type, lc)
Definition: pg_list.h:172
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6000
float4 * numbers
Definition: lsyscache.h:53
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:164
double cpu_operator_cost
Definition: costsize.c:122
Cost indexTotalCost
Definition: selfuncs.h:108
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:144
List * indexquals
Definition: pathnodes.h:1256
Index relid
Definition: pathnodes.h:692
List * lappend(List *list, void *datum)
Definition: list.c:321
Expr * clause
Definition: pathnodes.h:1987
double indexCorrelation
Definition: selfuncs.h:110
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1164
NullTestType nulltesttype
Definition: primnodes.h:1223
#define BoolGetDatum(X)
Definition: postgres.h:402
#define InvalidOid
Definition: postgres_ext.h:36
double numIndexTuples
Definition: selfuncs.h:114
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3052
#define Assert(condition)
Definition: c.h:746
#define linitial_oid(l)
Definition: pg_list.h:176
int nkeycolumns
Definition: pathnodes.h:828
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:145
Oid * opcintype
Definition: pathnodes.h:833
#define nodeTag(nodeptr)
Definition: nodes.h:533
Cost indexStartupCost
Definition: selfuncs.h:107
Oid * opfamily
Definition: pathnodes.h:832
RTEKind rtekind
Definition: parsenodes.h:981
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:81
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:84
#define elog(elevel,...)
Definition: elog.h:214
int * indexkeys
Definition: pathnodes.h:829
Oid opno
Definition: primnodes.h:516
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
bool * reverse_sort
Definition: pathnodes.h:835
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:50
int16 AttrNumber
Definition: attnum.h:21
#define BTEqualStrategyNumber
Definition: stratnum.h:31
double Cost
Definition: nodes.h:662
double numIndexPages
Definition: selfuncs.h:113
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3169
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6218

◆ gincostestimate()

void gincostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 7003 of file selfuncs.c.

References add_predicate_to_index_quals(), GinQualCounts::arrayScans, GinQualCounts::attHasFullScan, GinQualCounts::attHasNormalScan, RestrictInfo::clause, clauselist_selectivity(), cpu_index_tuple_cost, cpu_operator_cost, elog, ERROR, GinQualCounts::exactEntries, get_quals_from_indexclauses(), get_tablespace_page_costs(), gincost_opexpr(), gincost_scalararrayopexpr(), ginGetStats(), IndexOptInfo::hypothetical, i, index_close(), index_open(), index_other_operands_eval_cost(), index_pages_fetched(), IndexPath::indexclauses, IndexClause::indexcol, IndexPath::indexinfo, IndexOptInfo::indexoid, IndexClause::indexquals, IsA, JOIN_INNER, lfirst_node, list_length(), Max, Min, GinStatsData::nDataPages, GinStatsData::nEntries, GinStatsData::nEntryPages, NIL, IndexOptInfo::nkeycolumns, nodeTag, NoLock, GinStatsData::nPendingPages, GinStatsData::nTotalPages, IndexOptInfo::pages, GinQualCounts::partialEntries, IndexOptInfo::rel, RelOptInfo::relid, IndexOptInfo::reltablespace, scale, GinQualCounts::searchEntries, and IndexOptInfo::tuples.

Referenced by ginhandler().

7007 {
7008  IndexOptInfo *index = path->indexinfo;
7009  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7010  List *selectivityQuals;
7011  double numPages = index->pages,
7012  numTuples = index->tuples;
7013  double numEntryPages,
7014  numDataPages,
7015  numPendingPages,
7016  numEntries;
7017  GinQualCounts counts;
7018  bool matchPossible;
7019  bool fullIndexScan;
7020  double partialScale;
7021  double entryPagesFetched,
7022  dataPagesFetched,
7023  dataPagesFetchedBySel;
7024  double qual_op_cost,
7025  qual_arg_cost,
7026  spc_random_page_cost,
7027  outer_scans;
7028  Relation indexRel;
7029  GinStatsData ginStats;
7030  ListCell *lc;
7031  int i;
7032 
7033  /*
7034  * Obtain statistical information from the meta page, if possible. Else
7035  * set ginStats to zeroes, and we'll cope below.
7036  */
7037  if (!index->hypothetical)
7038  {
7039  /* Lock should have already been obtained in plancat.c */
7040  indexRel = index_open(index->indexoid, NoLock);
7041  ginGetStats(indexRel, &ginStats);
7042  index_close(indexRel, NoLock);
7043  }
7044  else
7045  {
7046  memset(&ginStats, 0, sizeof(ginStats));
7047  }
7048 
7049  /*
7050  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7051  * trusted, but the other fields are data as of the last VACUUM. We can
7052  * scale them up to account for growth since then, but that method only
7053  * goes so far; in the worst case, the stats might be for a completely
7054  * empty index, and scaling them will produce pretty bogus numbers.
7055  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7056  * it's grown more than that, fall back to estimating things only from the
7057  * assumed-accurate index size. But we'll trust nPendingPages in any case
7058  * so long as it's not clearly insane, ie, more than the index size.
7059  */
7060  if (ginStats.nPendingPages < numPages)
7061  numPendingPages = ginStats.nPendingPages;
7062  else
7063  numPendingPages = 0;
7064 
7065  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7066  ginStats.nTotalPages > numPages / 4 &&
7067  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7068  {
7069  /*
7070  * OK, the stats seem close enough to sane to be trusted. But we
7071  * still need to scale them by the ratio numPages / nTotalPages to
7072  * account for growth since the last VACUUM.
7073  */
7074  double scale = numPages / ginStats.nTotalPages;
7075 
7076  numEntryPages = ceil(ginStats.nEntryPages * scale);
7077  numDataPages = ceil(ginStats.nDataPages * scale);
7078  numEntries = ceil(ginStats.nEntries * scale);
7079  /* ensure we didn't round up too much */
7080  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7081  numDataPages = Min(numDataPages,
7082  numPages - numPendingPages - numEntryPages);
7083  }
7084  else
7085  {
7086  /*
7087  * We might get here because it's a hypothetical index, or an index
7088  * created pre-9.1 and never vacuumed since upgrading (in which case
7089  * its stats would read as zeroes), or just because it's grown too
7090  * much since the last VACUUM for us to put our faith in scaling.
7091  *
7092  * Invent some plausible internal statistics based on the index page
7093  * count (and clamp that to at least 10 pages, just in case). We
7094  * estimate that 90% of the index is entry pages, and the rest is data
7095  * pages. Estimate 100 entries per entry page; this is rather bogus
7096  * since it'll depend on the size of the keys, but it's more robust
7097  * than trying to predict the number of entries per heap tuple.
7098  */
7099  numPages = Max(numPages, 10);
7100  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7101  numDataPages = numPages - numPendingPages - numEntryPages;
7102  numEntries = floor(numEntryPages * 100);
7103  }
7104 
7105  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7106  if (numEntries < 1)
7107  numEntries = 1;
7108 
7109  /*
7110  * If the index is partial, AND the index predicate with the index-bound
7111  * quals to produce a more accurate idea of the number of rows covered by
7112  * the bound conditions.
7113  */
7114  selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
7115 
7116  /* Estimate the fraction of main-table tuples that will be visited */
7117  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7118  index->rel->relid,
7119  JOIN_INNER,
7120  NULL);
7121 
7122  /* fetch estimated page cost for tablespace containing index */
7124  &spc_random_page_cost,
7125  NULL);
7126 
7127  /*
7128  * Generic assumption about index correlation: there isn't any.
7129  */
7130  *indexCorrelation = 0.0;
7131 
7132  /*
7133  * Examine quals to estimate number of search entries & partial matches
7134  */
7135  memset(&counts, 0, sizeof(counts));
7136  counts.arrayScans = 1;
7137  matchPossible = true;
7138 
7139  foreach(lc, path->indexclauses)
7140  {
7141  IndexClause *iclause = lfirst_node(IndexClause, lc);
7142  ListCell *lc2;
7143 
7144  foreach(lc2, iclause->indexquals)
7145  {
7146  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
7147  Expr *clause = rinfo->clause;
7148 
7149  if (IsA(clause, OpExpr))
7150  {
7151  matchPossible = gincost_opexpr(root,
7152  index,
7153  iclause->indexcol,
7154  (OpExpr *) clause,
7155  &counts);
7156  if (!matchPossible)
7157  break;
7158  }
7159  else if (IsA(clause, ScalarArrayOpExpr))
7160  {
7161  matchPossible = gincost_scalararrayopexpr(root,
7162  index,
7163  iclause->indexcol,
7164  (ScalarArrayOpExpr *) clause,
7165  numEntries,
7166  &counts);
7167  if (!matchPossible)
7168  break;
7169  }
7170  else
7171  {
7172  /* shouldn't be anything else for a GIN index */
7173  elog(ERROR, "unsupported GIN indexqual type: %d",
7174  (int) nodeTag(clause));
7175  }
7176  }
7177  }
7178 
7179  /* Fall out if there were any provably-unsatisfiable quals */
7180  if (!matchPossible)
7181  {
7182  *indexStartupCost = 0;
7183  *indexTotalCost = 0;
7184  *indexSelectivity = 0;
7185  return;
7186  }
7187 
7188  /*
7189  * If attribute has a full scan and at the same time doesn't have normal
7190  * scan, then we'll have to scan all non-null entries of that attribute.
7191  * Currently, we don't have per-attribute statistics for GIN. Thus, we
7192  * must assume the whole GIN index has to be scanned in this case.
7193  */
7194  fullIndexScan = false;
7195  for (i = 0; i < index->nkeycolumns; i++)
7196  {
7197  if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
7198  {
7199  fullIndexScan = true;
7200  break;
7201  }
7202  }
7203 
7204  if (fullIndexScan || indexQuals == NIL)
7205  {
7206  /*
7207  * Full index scan will be required. We treat this as if every key in
7208  * the index had been listed in the query; is that reasonable?
7209  */
7210  counts.partialEntries = 0;
7211  counts.exactEntries = numEntries;
7212  counts.searchEntries = numEntries;
7213  }
7214 
7215  /* Will we have more than one iteration of a nestloop scan? */
7216  outer_scans = loop_count;
7217 
7218  /*
7219  * Compute cost to begin scan, first of all, pay attention to pending
7220  * list.
7221  */
7222  entryPagesFetched = numPendingPages;
7223 
7224  /*
7225  * Estimate number of entry pages read. We need to do
7226  * counts.searchEntries searches. Use a power function as it should be,
7227  * but tuples on leaf pages usually is much greater. Here we include all
7228  * searches in entry tree, including search of first entry in partial
7229  * match algorithm
7230  */
7231  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7232 
7233  /*
7234  * Add an estimate of entry pages read by partial match algorithm. It's a
7235  * scan over leaf pages in entry tree. We haven't any useful stats here,
7236  * so estimate it as proportion. Because counts.partialEntries is really
7237  * pretty bogus (see code above), it's possible that it is more than
7238  * numEntries; clamp the proportion to ensure sanity.
7239  */
7240  partialScale = counts.partialEntries / numEntries;
7241  partialScale = Min(partialScale, 1.0);
7242 
7243  entryPagesFetched += ceil(numEntryPages * partialScale);
7244 
7245  /*
7246  * Partial match algorithm reads all data pages before doing actual scan,
7247  * so it's a startup cost. Again, we haven't any useful stats here, so
7248  * estimate it as proportion.
7249  */
7250  dataPagesFetched = ceil(numDataPages * partialScale);
7251 
7252  /*
7253  * Calculate cache effects if more than one scan due to nestloops or array
7254  * quals. The result is pro-rated per nestloop scan, but the array qual
7255  * factor shouldn't be pro-rated (compare genericcostestimate).
7256  */
7257  if (outer_scans > 1 || counts.arrayScans > 1)
7258  {
7259  entryPagesFetched *= outer_scans * counts.arrayScans;
7260  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7261  (BlockNumber) numEntryPages,
7262  numEntryPages, root);
7263  entryPagesFetched /= outer_scans;
7264  dataPagesFetched *= outer_scans * counts.arrayScans;
7265  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7266  (BlockNumber) numDataPages,
7267  numDataPages, root);
7268  dataPagesFetched /= outer_scans;
7269  }
7270 
7271  /*
7272  * Here we use random page cost because logically-close pages could be far
7273  * apart on disk.
7274  */
7275  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7276 
7277  /*
7278  * Now compute the number of data pages fetched during the scan.
7279  *
7280  * We assume every entry to have the same number of items, and that there
7281  * is no overlap between them. (XXX: tsvector and array opclasses collect
7282  * statistics on the frequency of individual keys; it would be nice to use
7283  * those here.)
7284  */
7285  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7286 
7287  /*
7288  * If there is a lot of overlap among the entries, in particular if one of
7289  * the entries is very frequent, the above calculation can grossly
7290  * under-estimate. As a simple cross-check, calculate a lower bound based
7291  * on the overall selectivity of the quals. At a minimum, we must read
7292  * one item pointer for each matching entry.
7293  *
7294  * The width of each item pointer varies, based on the level of
7295  * compression. We don't have statistics on that, but an average of
7296  * around 3 bytes per item is fairly typical.
7297  */
7298  dataPagesFetchedBySel = ceil(*indexSelectivity *
7299  (numTuples / (BLCKSZ / 3)));
7300  if (dataPagesFetchedBySel > dataPagesFetched)
7301  dataPagesFetched = dataPagesFetchedBySel;
7302 
7303  /* Account for cache effects, the same as above */
7304  if (outer_scans > 1 || counts.arrayScans > 1)
7305  {
7306  dataPagesFetched *= outer_scans * counts.arrayScans;
7307  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7308  (BlockNumber) numDataPages,
7309  numDataPages, root);
7310  dataPagesFetched /= outer_scans;
7311  }
7312 
7313  /* And apply random_page_cost as the cost per page */
7314  *indexTotalCost = *indexStartupCost +
7315  dataPagesFetched * spc_random_page_cost;
7316 
7317  /*
7318  * Add on index qual eval costs, much as in genericcostestimate. But we
7319  * can disregard indexorderbys, since GIN doesn't support those.
7320  */
7321  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7322  qual_op_cost = cpu_operator_cost * list_length(indexQuals);
7323 
7324  *indexStartupCost += qual_arg_cost;
7325  *indexTotalCost += qual_arg_cost;
7326  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7327  *indexPages = dataPagesFetched;
7328 }
#define NIL
Definition: pg_list.h:65
BlockNumber nEntryPages
Definition: gin.h:46
bool attHasNormalScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:6710
#define IsA(nodeptr, _type_)
Definition: nodes.h:579
IndexOptInfo * indexinfo
Definition: pathnodes.h:1209
bool attHasFullScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:6709
#define Min(x, y)
Definition: c.h:928
double partialEntries
Definition: selfuncs.c:6711
double searchEntries
Definition: selfuncs.c:6713
Oid reltablespace
Definition: pathnodes.h:818
int scale
Definition: pgbench.c:154
int64 nEntries
Definition: gin.h:48
uint32 BlockNumber
Definition: block.h:31
bool hypothetical
Definition: pathnodes.h:856
List * indexclauses
Definition: pathnodes.h:1210
double tuples
Definition: pathnodes.h:823
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:6712
BlockNumber pages
Definition: pathnodes.h:822
RelOptInfo * rel
Definition: pathnodes.h:819
#define ERROR
Definition: elog.h:43
AttrNumber indexcol
Definition: pathnodes.h:1258
#define lfirst_node(type, lc)
Definition: pg_list.h:172
#define NoLock
Definition: lockdefs.h:34
double cpu_operator_cost
Definition: costsize.c:122
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:5916
List * indexquals
Definition: pathnodes.h:1256
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:692
Expr * clause
Definition: pathnodes.h:1987
BlockNumber nPendingPages
Definition: gin.h:44
double arrayScans
Definition: selfuncs.c:6714
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:630
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, OpExpr *clause, GinQualCounts *counts)
Definition: selfuncs.c:6837
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, ScalarArrayOpExpr *clause, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:6887
BlockNumber nDataPages
Definition: gin.h:47
#define Max(x, y)
Definition: c.h:922
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:5946
static int list_length(const List *l)
Definition: pg_list.h:149
BlockNumber nTotalPages
Definition: gin.h:45
int nkeycolumns
Definition: pathnodes.h:828
#define nodeTag(nodeptr)
Definition: nodes.h:533
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:158
#define elog(elevel,...)
Definition: elog.h:214
int i
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
Definition: pg_list.h:50
double cpu_index_tuple_cost
Definition: costsize.c:121
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:132
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:837
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6218

◆ gistcostestimate()

void gistcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6589 of file selfuncs.c.

References cpu_operator_cost, genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, IndexOptInfo::pages, IndexOptInfo::tree_height, and IndexOptInfo::tuples.

Referenced by gisthandler().

6593 {
6594  IndexOptInfo *index = path->indexinfo;
6595  GenericCosts costs;
6596  Cost descentCost;
6597 
6598  MemSet(&costs, 0, sizeof(costs));
6599 
6600  genericcostestimate(root, path, loop_count, &costs);
6601 
6602  /*
6603  * We model index descent costs similarly to those for btree, but to do
6604  * that we first need an idea of the tree height. We somewhat arbitrarily
6605  * assume that the fanout is 100, meaning the tree height is at most
6606  * log100(index->pages).
6607  *
6608  * Although this computation isn't really expensive enough to require
6609  * caching, we might as well use index->tree_height to cache it.
6610  */
6611  if (index->tree_height < 0) /* unknown? */
6612  {
6613  if (index->pages > 1) /* avoid computing log(0) */
6614  index->tree_height = (int) (log(index->pages) / log(100.0));
6615  else
6616  index->tree_height = 0;
6617  }
6618 
6619  /*
6620  * Add a CPU-cost component to represent the costs of initial descent. We
6621  * just use log(N) here not log2(N) since the branching factor isn't
6622  * necessarily two anyway. As for btree, charge once per SA scan.
6623  */
6624  if (index->tuples > 1) /* avoid computing log(0) */
6625  {
6626  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6627  costs.indexStartupCost += descentCost;
6628  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6629  }
6630 
6631  /*
6632  * Likewise add a per-page charge, calculated the same as for btrees.
6633  */
6634  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6635  costs.indexStartupCost += descentCost;
6636  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6637 
6638  *indexStartupCost = costs.indexStartupCost;
6639  *indexTotalCost = costs.indexTotalCost;
6640  *indexSelectivity = costs.indexSelectivity;
6641  *indexCorrelation = costs.indexCorrelation;
6642  *indexPages = costs.numIndexPages;
6643 }
Selectivity indexSelectivity
Definition: selfuncs.h:109
IndexOptInfo * indexinfo
Definition: pathnodes.h:1209
#define MemSet(start, val, len)
Definition: c.h:950
double tuples
Definition: pathnodes.h:823
int tree_height
Definition: pathnodes.h:824
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:822
double num_sa_scans
Definition: selfuncs.h:116
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6000
double cpu_operator_cost
Definition: costsize.c:122
Cost indexTotalCost
Definition: selfuncs.h:108
double indexCorrelation
Definition: selfuncs.h:110
Cost indexStartupCost
Definition: selfuncs.h:107
double Cost
Definition: nodes.h:662
double numIndexPages
Definition: selfuncs.h:113

◆ hashcostestimate()

void hashcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6545 of file selfuncs.c.

References genericcostestimate(), GenericCosts::indexCorrelation, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, and GenericCosts::numIndexPages.

Referenced by hashhandler().

6549 {
6550  GenericCosts costs;
6551 
6552  MemSet(&costs, 0, sizeof(costs));
6553 
6554  genericcostestimate(root, path, loop_count, &costs);
6555 
6556  /*
6557  * A hash index has no descent costs as such, since the index AM can go
6558  * directly to the target bucket after computing the hash value. There
6559  * are a couple of other hash-specific costs that we could conceivably add
6560  * here, though:
6561  *
6562  * Ideally we'd charge spc_random_page_cost for each page in the target
6563  * bucket, not just the numIndexPages pages that genericcostestimate
6564  * thought we'd visit. However in most cases we don't know which bucket
6565  * that will be. There's no point in considering the average bucket size
6566  * because the hash AM makes sure that's always one page.
6567  *
6568  * Likewise, we could consider charging some CPU for each index tuple in
6569  * the bucket, if we knew how many there were. But the per-tuple cost is
6570  * just a hash value comparison, not a general datatype-dependent
6571  * comparison, so any such charge ought to be quite a bit less than
6572  * cpu_operator_cost; which makes it probably not worth worrying about.
6573  *
6574  * A bigger issue is that chance hash-value collisions will result in
6575  * wasted probes into the heap. We don't currently attempt to model this
6576  * cost on the grounds that it's rare, but maybe it's not rare enough.
6577  * (Any fix for this ought to consider the generic lossy-operator problem,
6578  * though; it's not entirely hash-specific.)
6579  */
6580 
6581  *indexStartupCost = costs.indexStartupCost;
6582  *indexTotalCost = costs.indexTotalCost;
6583  *indexSelectivity = costs.indexSelectivity;
6584  *indexCorrelation = costs.indexCorrelation;
6585  *indexPages = costs.numIndexPages;
6586 }
Selectivity indexSelectivity
Definition: selfuncs.h:109
#define MemSet(start, val, len)
Definition: c.h:950
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6000
Cost indexTotalCost
Definition: selfuncs.h:108
double indexCorrelation
Definition: selfuncs.h:110
Cost indexStartupCost
Definition: selfuncs.h:107
double numIndexPages
Definition: selfuncs.h:113

◆ spgcostestimate()

void spgcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6646 of file selfuncs.c.

References cpu_operator_cost, genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, IndexOptInfo::pages, IndexOptInfo::tree_height, and IndexOptInfo::tuples.

Referenced by spghandler().

6650 {
6651  IndexOptInfo *index = path->indexinfo;
6652  GenericCosts costs;
6653  Cost descentCost;
6654 
6655  MemSet(&costs, 0, sizeof(costs));
6656 
6657  genericcostestimate(root, path, loop_count, &costs);
6658 
6659  /*
6660  * We model index descent costs similarly to those for btree, but to do
6661  * that we first need an idea of the tree height. We somewhat arbitrarily
6662  * assume that the fanout is 100, meaning the tree height is at most
6663  * log100(index->pages).
6664  *
6665  * Although this computation isn't really expensive enough to require
6666  * caching, we might as well use index->tree_height to cache it.
6667  */
6668  if (index->tree_height < 0) /* unknown? */
6669  {
6670  if (index->pages > 1) /* avoid computing log(0) */
6671  index->tree_height = (int) (log(index->pages) / log(100.0));
6672  else
6673  index->tree_height = 0;
6674  }
6675 
6676  /*
6677  * Add a CPU-cost component to represent the costs of initial descent. We
6678  * just use log(N) here not log2(N) since the branching factor isn't
6679  * necessarily two anyway. As for btree, charge once per SA scan.
6680  */
6681  if (index->tuples > 1) /* avoid computing log(0) */
6682  {
6683  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6684  costs.indexStartupCost += descentCost;
6685  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6686  }
6687 
6688  /*
6689  * Likewise add a per-page charge, calculated the same as for btrees.
6690  */
6691  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6692  costs.indexStartupCost += descentCost;
6693  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6694 
6695  *indexStartupCost = costs.indexStartupCost;
6696  *indexTotalCost = costs.indexTotalCost;
6697  *indexSelectivity = costs.indexSelectivity;
6698  *indexCorrelation = costs.indexCorrelation;
6699  *indexPages = costs.numIndexPages;
6700 }
Selectivity indexSelectivity
Definition: selfuncs.h:109
IndexOptInfo * indexinfo
Definition: pathnodes.h:1209
#define MemSet(start, val, len)
Definition: c.h:950
double tuples
Definition: pathnodes.h:823
int tree_height
Definition: pathnodes.h:824
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:822
double num_sa_scans
Definition: selfuncs.h:116
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6000
double cpu_operator_cost
Definition: costsize.c:122
Cost indexTotalCost
Definition: selfuncs.h:108
double indexCorrelation
Definition: selfuncs.h:110
Cost indexStartupCost
Definition: selfuncs.h:107
double Cost
Definition: nodes.h:662
double numIndexPages
Definition: selfuncs.h:113