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

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

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

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

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

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

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

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

◆ 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 6547 of file selfuncs.c.

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

Referenced by hashhandler().

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

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

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