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 7329 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().

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

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

◆ 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 6998 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().

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

◆ 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 6584 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().

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

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

Referenced by hashhandler().

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

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