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

6983 {
6984  IndexOptInfo *index = path->indexinfo;
6985  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
6986  double numPages = index->pages;
6987  RelOptInfo *baserel = index->rel;
6988  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
6989  Cost spc_seq_page_cost;
6990  Cost spc_random_page_cost;
6991  double qual_arg_cost;
6992  double qualSelectivity;
6993  BrinStatsData statsData;
6994  double indexRanges;
6995  double minimalRanges;
6996  double estimatedRanges;
6997  double selec;
6998  Relation indexRel;
6999  ListCell *l;
7000  VariableStatData vardata;
7001 
7002  Assert(rte->rtekind == RTE_RELATION);
7003 
7004  /* fetch estimated page cost for the tablespace containing the index */
7006  &spc_random_page_cost,
7007  &spc_seq_page_cost);
7008 
7009  /*
7010  * Obtain some data from the index itself, if possible. Otherwise invent
7011  * some plausible internal statistics based on the relation page count.
7012  */
7013  if (!index->hypothetical)
7014  {
7015  /*
7016  * A lock should have already been obtained on the index in plancat.c.
7017  */
7018  indexRel = index_open(index->indexoid, NoLock);
7019  brinGetStats(indexRel, &statsData);
7020  index_close(indexRel, NoLock);
7021 
7022  /* work out the actual number of ranges in the index */
7023  indexRanges = Max(ceil((double) baserel->pages /
7024  statsData.pagesPerRange), 1.0);
7025  }
7026  else
7027  {
7028  /*
7029  * Assume default number of pages per range, and estimate the number
7030  * of ranges based on that.
7031  */
7032  indexRanges = Max(ceil((double) baserel->pages /
7034 
7036  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
7037  }
7038 
7039  /*
7040  * Compute index correlation
7041  *
7042  * Because we can use all index quals equally when scanning, we can use
7043  * the largest correlation (in absolute value) among columns used by the
7044  * query. Start at zero, the worst possible case. If we cannot find any
7045  * correlation statistics, we will keep it as 0.
7046  */
7047  *indexCorrelation = 0;
7048 
7049  foreach(l, path->indexclauses)
7050  {
7051  IndexClause *iclause = lfirst_node(IndexClause, l);
7052  AttrNumber attnum = index->indexkeys[iclause->indexcol];
7053 
7054  /* attempt to lookup stats in relation for this index column */
7055  if (attnum != 0)
7056  {
7057  /* Simple variable -- look to stats for the underlying table */
7059  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7060  {
7061  /*
7062  * The hook took control of acquiring a stats tuple. If it
7063  * did supply a tuple, it'd better have supplied a freefunc.
7064  */
7065  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7066  elog(ERROR,
7067  "no function provided to release variable stats with");
7068  }
7069  else
7070  {
7071  vardata.statsTuple =
7073  ObjectIdGetDatum(rte->relid),
7074  Int16GetDatum(attnum),
7075  BoolGetDatum(false));
7076  vardata.freefunc = ReleaseSysCache;
7077  }
7078  }
7079  else
7080  {
7081  /*
7082  * Looks like we've found an expression column in the index. Let's
7083  * see if there's any stats for it.
7084  */
7085 
7086  /* get the attnum from the 0-based index. */
7087  attnum = iclause->indexcol + 1;
7088 
7089  if (get_index_stats_hook &&
7090  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7091  {
7092  /*
7093  * The hook took control of acquiring a stats tuple. If it
7094  * did supply a tuple, it'd better have supplied a freefunc.
7095  */
7096  if (HeapTupleIsValid(vardata.statsTuple) &&
7097  !vardata.freefunc)
7098  elog(ERROR, "no function provided to release variable stats with");
7099  }
7100  else
7101  {
7103  ObjectIdGetDatum(index->indexoid),
7104  Int16GetDatum(attnum),
7105  BoolGetDatum(false));
7106  vardata.freefunc = ReleaseSysCache;
7107  }
7108  }
7109 
7110  if (HeapTupleIsValid(vardata.statsTuple))
7111  {
7112  AttStatsSlot sslot;
7113 
7114  if (get_attstatsslot(&sslot, vardata.statsTuple,
7115  STATISTIC_KIND_CORRELATION, InvalidOid,
7117  {
7118  double varCorrelation = 0.0;
7119 
7120  if (sslot.nnumbers > 0)
7121  varCorrelation = Abs(sslot.numbers[0]);
7122 
7123  if (varCorrelation > *indexCorrelation)
7124  *indexCorrelation = varCorrelation;
7125 
7126  free_attstatsslot(&sslot);
7127  }
7128  }
7129 
7130  ReleaseVariableStats(vardata);
7131  }
7132 
7133  qualSelectivity = clauselist_selectivity(root, indexQuals,
7134  baserel->relid,
7135  JOIN_INNER, NULL);
7136 
7137  /*
7138  * Now calculate the minimum possible ranges we could match with if all of
7139  * the rows were in the perfect order in the table's heap.
7140  */
7141  minimalRanges = ceil(indexRanges * qualSelectivity);
7142 
7143  /*
7144  * Now estimate the number of ranges that we'll touch by using the
7145  * indexCorrelation from the stats. Careful not to divide by zero (note
7146  * we're using the absolute value of the correlation).
7147  */
7148  if (*indexCorrelation < 1.0e-10)
7149  estimatedRanges = indexRanges;
7150  else
7151  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7152 
7153  /* we expect to visit this portion of the table */
7154  selec = estimatedRanges / indexRanges;
7155 
7156  CLAMP_PROBABILITY(selec);
7157 
7158  *indexSelectivity = selec;
7159 
7160  /*
7161  * Compute the index qual costs, much as in genericcostestimate, to add to
7162  * the index costs. We can disregard indexorderbys, since BRIN doesn't
7163  * support those.
7164  */
7165  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7166 
7167  /*
7168  * Compute the startup cost as the cost to read the whole revmap
7169  * sequentially, including the cost to execute the index quals.
7170  */
7171  *indexStartupCost =
7172  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7173  *indexStartupCost += qual_arg_cost;
7174 
7175  /*
7176  * To read a BRIN index there might be a bit of back and forth over
7177  * regular pages, as revmap might point to them out of sequential order;
7178  * calculate the total cost as reading the whole index in random order.
7179  */
7180  *indexTotalCost = *indexStartupCost +
7181  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7182 
7183  /*
7184  * Charge a small amount per range tuple which we expect to match to. This
7185  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7186  * will set a bit for each page in the range when we find a matching
7187  * range, so we must multiply the charge by the number of pages in the
7188  * range.
7189  */
7190  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7191  statsData.pagesPerRange;
7192 
7193  *indexPages = index->pages;
7194 }
IndexOptInfo * indexinfo
Definition: pathnodes.h:1179
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:54
#define Min(x, y)
Definition: c.h:911
#define Int16GetDatum(X)
Definition: postgres.h:451
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
Oid reltablespace
Definition: pathnodes.h:792
bool hypothetical
Definition: pathnodes.h:829
List * indexclauses
Definition: pathnodes.h:1180
#define Abs(x)
Definition: c.h:917
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:796
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
RelOptInfo * rel
Definition: pathnodes.h:793
#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:1228
#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:114
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:5566
#define BRIN_DEFAULT_PAGES_PER_RANGE
Definition: brin.h:38
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:147
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:671
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:905
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:5596
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
BlockNumber pages
Definition: pathnodes.h:682
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2942
#define Assert(condition)
Definition: c.h:739
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:148
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:152
RTEKind rtekind
Definition: parsenodes.h:974
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
#define elog(elevel,...)
Definition: elog.h:228
int * indexkeys
Definition: pathnodes.h:803
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:126
double Cost
Definition: nodes.h:659
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1083
BlockNumber revmapNumPages
Definition: brin.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3072

◆ 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 5889 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, rint(), RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

5893 {
5894  IndexOptInfo *index = path->indexinfo;
5895  GenericCosts costs;
5896  Oid relid;
5897  AttrNumber colnum;
5898  VariableStatData vardata;
5899  double numIndexTuples;
5900  Cost descentCost;
5901  List *indexBoundQuals;
5902  int indexcol;
5903  bool eqQualHere;
5904  bool found_saop;
5905  bool found_is_null_op;
5906  double num_sa_scans;
5907  ListCell *lc;
5908 
5909  /*
5910  * For a btree scan, only leading '=' quals plus inequality quals for the
5911  * immediately next attribute contribute to index selectivity (these are
5912  * the "boundary quals" that determine the starting and stopping points of
5913  * the index scan). Additional quals can suppress visits to the heap, so
5914  * it's OK to count them in indexSelectivity, but they should not count
5915  * for estimating numIndexTuples. So we must examine the given indexquals
5916  * to find out which ones count as boundary quals. We rely on the
5917  * knowledge that they are given in index column order.
5918  *
5919  * For a RowCompareExpr, we consider only the first column, just as
5920  * rowcomparesel() does.
5921  *
5922  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
5923  * index scans not one, but the ScalarArrayOpExpr's operator can be
5924  * considered to act the same as it normally does.
5925  */
5926  indexBoundQuals = NIL;
5927  indexcol = 0;
5928  eqQualHere = false;
5929  found_saop = false;
5930  found_is_null_op = false;
5931  num_sa_scans = 1;
5932  foreach(lc, path->indexclauses)
5933  {
5934  IndexClause *iclause = lfirst_node(IndexClause, lc);
5935  ListCell *lc2;
5936 
5937  if (indexcol != iclause->indexcol)
5938  {
5939  /* Beginning of a new column's quals */
5940  if (!eqQualHere)
5941  break; /* done if no '=' qual for indexcol */
5942  eqQualHere = false;
5943  indexcol++;
5944  if (indexcol != iclause->indexcol)
5945  break; /* no quals at all for indexcol */
5946  }
5947 
5948  /* Examine each indexqual associated with this index clause */
5949  foreach(lc2, iclause->indexquals)
5950  {
5951  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
5952  Expr *clause = rinfo->clause;
5953  Oid clause_op = InvalidOid;
5954  int op_strategy;
5955 
5956  if (IsA(clause, OpExpr))
5957  {
5958  OpExpr *op = (OpExpr *) clause;
5959 
5960  clause_op = op->opno;
5961  }
5962  else if (IsA(clause, RowCompareExpr))
5963  {
5964  RowCompareExpr *rc = (RowCompareExpr *) clause;
5965 
5966  clause_op = linitial_oid(rc->opnos);
5967  }
5968  else if (IsA(clause, ScalarArrayOpExpr))
5969  {
5970  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
5971  Node *other_operand = (Node *) lsecond(saop->args);
5972  int alength = estimate_array_length(other_operand);
5973 
5974  clause_op = saop->opno;
5975  found_saop = true;
5976  /* count number of SA scans induced by indexBoundQuals only */
5977  if (alength > 1)
5978  num_sa_scans *= alength;
5979  }
5980  else if (IsA(clause, NullTest))
5981  {
5982  NullTest *nt = (NullTest *) clause;
5983 
5984  if (nt->nulltesttype == IS_NULL)
5985  {
5986  found_is_null_op = true;
5987  /* IS NULL is like = for selectivity purposes */
5988  eqQualHere = true;
5989  }
5990  }
5991  else
5992  elog(ERROR, "unsupported indexqual type: %d",
5993  (int) nodeTag(clause));
5994 
5995  /* check for equality operator */
5996  if (OidIsValid(clause_op))
5997  {
5998  op_strategy = get_op_opfamily_strategy(clause_op,
5999  index->opfamily[indexcol]);
6000  Assert(op_strategy != 0); /* not a member of opfamily?? */
6001  if (op_strategy == BTEqualStrategyNumber)
6002  eqQualHere = true;
6003  }
6004 
6005  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6006  }
6007  }
6008 
6009  /*
6010  * If index is unique and we found an '=' clause for each column, we can
6011  * just assume numIndexTuples = 1 and skip the expensive
6012  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6013  * NullTest invalidates that theory, even though it sets eqQualHere.
6014  */
6015  if (index->unique &&
6016  indexcol == index->nkeycolumns - 1 &&
6017  eqQualHere &&
6018  !found_saop &&
6019  !found_is_null_op)
6020  numIndexTuples = 1.0;
6021  else
6022  {
6023  List *selectivityQuals;
6024  Selectivity btreeSelectivity;
6025 
6026  /*
6027  * If the index is partial, AND the index predicate with the
6028  * index-bound quals to produce a more accurate idea of the number of
6029  * rows covered by the bound conditions.
6030  */
6031  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
6032 
6033  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6034  index->rel->relid,
6035  JOIN_INNER,
6036  NULL);
6037  numIndexTuples = btreeSelectivity * index->rel->tuples;
6038 
6039  /*
6040  * As in genericcostestimate(), we have to adjust for any
6041  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6042  * to integer.
6043  */
6044  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6045  }
6046 
6047  /*
6048  * Now do generic index cost estimation.
6049  */
6050  MemSet(&costs, 0, sizeof(costs));
6051  costs.numIndexTuples = numIndexTuples;
6052 
6053  genericcostestimate(root, path, loop_count, &costs);
6054 
6055  /*
6056  * Add a CPU-cost component to represent the costs of initial btree
6057  * descent. We don't charge any I/O cost for touching upper btree levels,
6058  * since they tend to stay in cache, but we still have to do about log2(N)
6059  * comparisons to descend a btree of N leaf tuples. We charge one
6060  * cpu_operator_cost per comparison.
6061  *
6062  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6063  * ones after the first one are not startup cost so far as the overall
6064  * plan is concerned, so add them only to "total" cost.
6065  */
6066  if (index->tuples > 1) /* avoid computing log(0) */
6067  {
6068  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6069  costs.indexStartupCost += descentCost;
6070  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6071  }
6072 
6073  /*
6074  * Even though we're not charging I/O cost for touching upper btree pages,
6075  * it's still reasonable to charge some CPU cost per page descended
6076  * through. Moreover, if we had no such charge at all, bloated indexes
6077  * would appear to have the same search cost as unbloated ones, at least
6078  * in cases where only a single leaf page is expected to be visited. This
6079  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6080  * touched. The number of such pages is btree tree height plus one (ie,
6081  * we charge for the leaf page too). As above, charge once per SA scan.
6082  */
6083  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6084  costs.indexStartupCost += descentCost;
6085  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6086 
6087  /*
6088  * If we can get an estimate of the first column's ordering correlation C
6089  * from pg_statistic, estimate the index correlation as C for a
6090  * single-column index, or C * 0.75 for multiple columns. (The idea here
6091  * is that multiple columns dilute the importance of the first column's
6092  * ordering, but don't negate it entirely. Before 8.0 we divided the
6093  * correlation by the number of columns, but that seems too strong.)
6094  */
6095  MemSet(&vardata, 0, sizeof(vardata));
6096 
6097  if (index->indexkeys[0] != 0)
6098  {
6099  /* Simple variable --- look to stats for the underlying table */
6100  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6101 
6102  Assert(rte->rtekind == RTE_RELATION);
6103  relid = rte->relid;
6104  Assert(relid != InvalidOid);
6105  colnum = index->indexkeys[0];
6106 
6108  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6109  {
6110  /*
6111  * The hook took control of acquiring a stats tuple. If it did
6112  * supply a tuple, it'd better have supplied a freefunc.
6113  */
6114  if (HeapTupleIsValid(vardata.statsTuple) &&
6115  !vardata.freefunc)
6116  elog(ERROR, "no function provided to release variable stats with");
6117  }
6118  else
6119  {
6121  ObjectIdGetDatum(relid),
6122  Int16GetDatum(colnum),
6123  BoolGetDatum(rte->inh));
6124  vardata.freefunc = ReleaseSysCache;
6125  }
6126  }
6127  else
6128  {
6129  /* Expression --- maybe there are stats for the index itself */
6130  relid = index->indexoid;
6131  colnum = 1;
6132 
6133  if (get_index_stats_hook &&
6134  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6135  {
6136  /*
6137  * The hook took control of acquiring a stats tuple. If it did
6138  * supply a tuple, it'd better have supplied a freefunc.
6139  */
6140  if (HeapTupleIsValid(vardata.statsTuple) &&
6141  !vardata.freefunc)
6142  elog(ERROR, "no function provided to release variable stats with");
6143  }
6144  else
6145  {
6147  ObjectIdGetDatum(relid),
6148  Int16GetDatum(colnum),
6149  BoolGetDatum(false));
6150  vardata.freefunc = ReleaseSysCache;
6151  }
6152  }
6153 
6154  if (HeapTupleIsValid(vardata.statsTuple))
6155  {
6156  Oid sortop;
6157  AttStatsSlot sslot;
6158 
6159  sortop = get_opfamily_member(index->opfamily[0],
6160  index->opcintype[0],
6161  index->opcintype[0],
6163  if (OidIsValid(sortop) &&
6164  get_attstatsslot(&sslot, vardata.statsTuple,
6165  STATISTIC_KIND_CORRELATION, sortop,
6167  {
6168  double varCorrelation;
6169 
6170  Assert(sslot.nnumbers == 1);
6171  varCorrelation = sslot.numbers[0];
6172 
6173  if (index->reverse_sort[0])
6174  varCorrelation = -varCorrelation;
6175 
6176  if (index->nkeycolumns > 1)
6177  costs.indexCorrelation = varCorrelation * 0.75;
6178  else
6179  costs.indexCorrelation = varCorrelation;
6180 
6181  free_attstatsslot(&sslot);
6182  }
6183  }
6184 
6185  ReleaseVariableStats(vardata);
6186 
6187  *indexStartupCost = costs.indexStartupCost;
6188  *indexTotalCost = costs.indexTotalCost;
6189  *indexSelectivity = costs.indexSelectivity;
6190  *indexCorrelation = costs.indexCorrelation;
6191  *indexPages = costs.numIndexPages;
6192 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
#define NIL
Definition: pg_list.h:65
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
IndexOptInfo * indexinfo
Definition: pathnodes.h:1179
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:54
double tuples
Definition: pathnodes.h:683
#define Int16GetDatum(X)
Definition: postgres.h:451
Definition: nodes.h:525
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
#define MemSet(start, val, len)
Definition: c.h:962
List * indexclauses
Definition: pathnodes.h:1180
double Selectivity
Definition: nodes.h:658
double tuples
Definition: pathnodes.h:797
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: pathnodes.h:798
#define OidIsValid(objectId)
Definition: c.h:645
#define lsecond(l)
Definition: pg_list.h:200
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:1891
RelOptInfo * rel
Definition: pathnodes.h:793
#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:1228
double num_sa_scans
Definition: selfuncs.h:113
#define lfirst_node(type, lc)
Definition: pg_list.h:193
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5650
float4 * numbers
Definition: lsyscache.h:53
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:163
double cpu_operator_cost
Definition: costsize.c:114
Cost indexTotalCost
Definition: selfuncs.h:105
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:147
double rint(double x)
Definition: rint.c:21
List * indexquals
Definition: pathnodes.h:1226
Index relid
Definition: pathnodes.h:671
List * lappend(List *list, void *datum)
Definition: list.c:322
Expr * clause
Definition: pathnodes.h:1945
double indexCorrelation
Definition: selfuncs.h:107
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:111
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2942
#define Assert(condition)
Definition: c.h:739
#define linitial_oid(l)
Definition: pg_list.h:197
int nkeycolumns
Definition: pathnodes.h:802
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:148
Oid * opcintype
Definition: pathnodes.h:807
#define nodeTag(nodeptr)
Definition: nodes.h:530
Cost indexStartupCost
Definition: selfuncs.h:104
Oid * opfamily
Definition: pathnodes.h:806
RTEKind rtekind
Definition: parsenodes.h:974
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:80
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
#define elog(elevel,...)
Definition: elog.h:228
int * indexkeys
Definition: pathnodes.h:803
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:809
#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:659
double numIndexPages
Definition: selfuncs.h:110
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3072
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:5868

◆ 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 6648 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, rint(), scale, GinQualCounts::searchEntries, and IndexOptInfo::tuples.

Referenced by ginhandler().

6652 {
6653  IndexOptInfo *index = path->indexinfo;
6654  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
6655  List *selectivityQuals;
6656  double numPages = index->pages,
6657  numTuples = index->tuples;
6658  double numEntryPages,
6659  numDataPages,
6660  numPendingPages,
6661  numEntries;
6662  GinQualCounts counts;
6663  bool matchPossible;
6664  bool fullIndexScan;
6665  double partialScale;
6666  double entryPagesFetched,
6667  dataPagesFetched,
6668  dataPagesFetchedBySel;
6669  double qual_op_cost,
6670  qual_arg_cost,
6671  spc_random_page_cost,
6672  outer_scans;
6673  Relation indexRel;
6674  GinStatsData ginStats;
6675  ListCell *lc;
6676  int i;
6677 
6678  /*
6679  * Obtain statistical information from the meta page, if possible. Else
6680  * set ginStats to zeroes, and we'll cope below.
6681  */
6682  if (!index->hypothetical)
6683  {
6684  /* Lock should have already been obtained in plancat.c */
6685  indexRel = index_open(index->indexoid, NoLock);
6686  ginGetStats(indexRel, &ginStats);
6687  index_close(indexRel, NoLock);
6688  }
6689  else
6690  {
6691  memset(&ginStats, 0, sizeof(ginStats));
6692  }
6693 
6694  /*
6695  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
6696  * trusted, but the other fields are data as of the last VACUUM. We can
6697  * scale them up to account for growth since then, but that method only
6698  * goes so far; in the worst case, the stats might be for a completely
6699  * empty index, and scaling them will produce pretty bogus numbers.
6700  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
6701  * it's grown more than that, fall back to estimating things only from the
6702  * assumed-accurate index size. But we'll trust nPendingPages in any case
6703  * so long as it's not clearly insane, ie, more than the index size.
6704  */
6705  if (ginStats.nPendingPages < numPages)
6706  numPendingPages = ginStats.nPendingPages;
6707  else
6708  numPendingPages = 0;
6709 
6710  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
6711  ginStats.nTotalPages > numPages / 4 &&
6712  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
6713  {
6714  /*
6715  * OK, the stats seem close enough to sane to be trusted. But we
6716  * still need to scale them by the ratio numPages / nTotalPages to
6717  * account for growth since the last VACUUM.
6718  */
6719  double scale = numPages / ginStats.nTotalPages;
6720 
6721  numEntryPages = ceil(ginStats.nEntryPages * scale);
6722  numDataPages = ceil(ginStats.nDataPages * scale);
6723  numEntries = ceil(ginStats.nEntries * scale);
6724  /* ensure we didn't round up too much */
6725  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
6726  numDataPages = Min(numDataPages,
6727  numPages - numPendingPages - numEntryPages);
6728  }
6729  else
6730  {
6731  /*
6732  * We might get here because it's a hypothetical index, or an index
6733  * created pre-9.1 and never vacuumed since upgrading (in which case
6734  * its stats would read as zeroes), or just because it's grown too
6735  * much since the last VACUUM for us to put our faith in scaling.
6736  *
6737  * Invent some plausible internal statistics based on the index page
6738  * count (and clamp that to at least 10 pages, just in case). We
6739  * estimate that 90% of the index is entry pages, and the rest is data
6740  * pages. Estimate 100 entries per entry page; this is rather bogus
6741  * since it'll depend on the size of the keys, but it's more robust
6742  * than trying to predict the number of entries per heap tuple.
6743  */
6744  numPages = Max(numPages, 10);
6745  numEntryPages = floor((numPages - numPendingPages) * 0.90);
6746  numDataPages = numPages - numPendingPages - numEntryPages;
6747  numEntries = floor(numEntryPages * 100);
6748  }
6749 
6750  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
6751  if (numEntries < 1)
6752  numEntries = 1;
6753 
6754  /*
6755  * If the index is partial, AND the index predicate with the index-bound
6756  * quals to produce a more accurate idea of the number of rows covered by
6757  * the bound conditions.
6758  */
6759  selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
6760 
6761  /* Estimate the fraction of main-table tuples that will be visited */
6762  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
6763  index->rel->relid,
6764  JOIN_INNER,
6765  NULL);
6766 
6767  /* fetch estimated page cost for tablespace containing index */
6769  &spc_random_page_cost,
6770  NULL);
6771 
6772  /*
6773  * Generic assumption about index correlation: there isn't any.
6774  */
6775  *indexCorrelation = 0.0;
6776 
6777  /*
6778  * Examine quals to estimate number of search entries & partial matches
6779  */
6780  memset(&counts, 0, sizeof(counts));
6781  counts.arrayScans = 1;
6782  matchPossible = true;
6783 
6784  foreach(lc, path->indexclauses)
6785  {
6786  IndexClause *iclause = lfirst_node(IndexClause, lc);
6787  ListCell *lc2;
6788 
6789  foreach(lc2, iclause->indexquals)
6790  {
6791  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6792  Expr *clause = rinfo->clause;
6793 
6794  if (IsA(clause, OpExpr))
6795  {
6796  matchPossible = gincost_opexpr(root,
6797  index,
6798  iclause->indexcol,
6799  (OpExpr *) clause,
6800  &counts);
6801  if (!matchPossible)
6802  break;
6803  }
6804  else if (IsA(clause, ScalarArrayOpExpr))
6805  {
6806  matchPossible = gincost_scalararrayopexpr(root,
6807  index,
6808  iclause->indexcol,
6809  (ScalarArrayOpExpr *) clause,
6810  numEntries,
6811  &counts);
6812  if (!matchPossible)
6813  break;
6814  }
6815  else
6816  {
6817  /* shouldn't be anything else for a GIN index */
6818  elog(ERROR, "unsupported GIN indexqual type: %d",
6819  (int) nodeTag(clause));
6820  }
6821  }
6822  }
6823 
6824  /* Fall out if there were any provably-unsatisfiable quals */
6825  if (!matchPossible)
6826  {
6827  *indexStartupCost = 0;
6828  *indexTotalCost = 0;
6829  *indexSelectivity = 0;
6830  return;
6831  }
6832 
6833  /*
6834  * If attribute has a full scan and at the same time doesn't have normal
6835  * scan, then we'll have to scan all non-null entries of that attribute.
6836  * Currently, we don't have per-attribute statistics for GIN. Thus, we
6837  * must assume the whole GIN index has to be scanned in this case.
6838  */
6839  fullIndexScan = false;
6840  for (i = 0; i < index->nkeycolumns; i++)
6841  {
6842  if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
6843  {
6844  fullIndexScan = true;
6845  break;
6846  }
6847  }
6848 
6849  if (fullIndexScan || indexQuals == NIL)
6850  {
6851  /*
6852  * Full index scan will be required. We treat this as if every key in
6853  * the index had been listed in the query; is that reasonable?
6854  */
6855  counts.partialEntries = 0;
6856  counts.exactEntries = numEntries;
6857  counts.searchEntries = numEntries;
6858  }
6859 
6860  /* Will we have more than one iteration of a nestloop scan? */
6861  outer_scans = loop_count;
6862 
6863  /*
6864  * Compute cost to begin scan, first of all, pay attention to pending
6865  * list.
6866  */
6867  entryPagesFetched = numPendingPages;
6868 
6869  /*
6870  * Estimate number of entry pages read. We need to do
6871  * counts.searchEntries searches. Use a power function as it should be,
6872  * but tuples on leaf pages usually is much greater. Here we include all
6873  * searches in entry tree, including search of first entry in partial
6874  * match algorithm
6875  */
6876  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
6877 
6878  /*
6879  * Add an estimate of entry pages read by partial match algorithm. It's a
6880  * scan over leaf pages in entry tree. We haven't any useful stats here,
6881  * so estimate it as proportion. Because counts.partialEntries is really
6882  * pretty bogus (see code above), it's possible that it is more than
6883  * numEntries; clamp the proportion to ensure sanity.
6884  */
6885  partialScale = counts.partialEntries / numEntries;
6886  partialScale = Min(partialScale, 1.0);
6887 
6888  entryPagesFetched += ceil(numEntryPages * partialScale);
6889 
6890  /*
6891  * Partial match algorithm reads all data pages before doing actual scan,
6892  * so it's a startup cost. Again, we haven't any useful stats here, so
6893  * estimate it as proportion.
6894  */
6895  dataPagesFetched = ceil(numDataPages * partialScale);
6896 
6897  /*
6898  * Calculate cache effects if more than one scan due to nestloops or array
6899  * quals. The result is pro-rated per nestloop scan, but the array qual
6900  * factor shouldn't be pro-rated (compare genericcostestimate).
6901  */
6902  if (outer_scans > 1 || counts.arrayScans > 1)
6903  {
6904  entryPagesFetched *= outer_scans * counts.arrayScans;
6905  entryPagesFetched = index_pages_fetched(entryPagesFetched,
6906  (BlockNumber) numEntryPages,
6907  numEntryPages, root);
6908  entryPagesFetched /= outer_scans;
6909  dataPagesFetched *= outer_scans * counts.arrayScans;
6910  dataPagesFetched = index_pages_fetched(dataPagesFetched,
6911  (BlockNumber) numDataPages,
6912  numDataPages, root);
6913  dataPagesFetched /= outer_scans;
6914  }
6915 
6916  /*
6917  * Here we use random page cost because logically-close pages could be far
6918  * apart on disk.
6919  */
6920  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
6921 
6922  /*
6923  * Now compute the number of data pages fetched during the scan.
6924  *
6925  * We assume every entry to have the same number of items, and that there
6926  * is no overlap between them. (XXX: tsvector and array opclasses collect
6927  * statistics on the frequency of individual keys; it would be nice to use
6928  * those here.)
6929  */
6930  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
6931 
6932  /*
6933  * If there is a lot of overlap among the entries, in particular if one of
6934  * the entries is very frequent, the above calculation can grossly
6935  * under-estimate. As a simple cross-check, calculate a lower bound based
6936  * on the overall selectivity of the quals. At a minimum, we must read
6937  * one item pointer for each matching entry.
6938  *
6939  * The width of each item pointer varies, based on the level of
6940  * compression. We don't have statistics on that, but an average of
6941  * around 3 bytes per item is fairly typical.
6942  */
6943  dataPagesFetchedBySel = ceil(*indexSelectivity *
6944  (numTuples / (BLCKSZ / 3)));
6945  if (dataPagesFetchedBySel > dataPagesFetched)
6946  dataPagesFetched = dataPagesFetchedBySel;
6947 
6948  /* Account for cache effects, the same as above */
6949  if (outer_scans > 1 || counts.arrayScans > 1)
6950  {
6951  dataPagesFetched *= outer_scans * counts.arrayScans;
6952  dataPagesFetched = index_pages_fetched(dataPagesFetched,
6953  (BlockNumber) numDataPages,
6954  numDataPages, root);
6955  dataPagesFetched /= outer_scans;
6956  }
6957 
6958  /* And apply random_page_cost as the cost per page */
6959  *indexTotalCost = *indexStartupCost +
6960  dataPagesFetched * spc_random_page_cost;
6961 
6962  /*
6963  * Add on index qual eval costs, much as in genericcostestimate. But we
6964  * can disregard indexorderbys, since GIN doesn't support those.
6965  */
6966  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
6967  qual_op_cost = cpu_operator_cost * list_length(indexQuals);
6968 
6969  *indexStartupCost += qual_arg_cost;
6970  *indexTotalCost += qual_arg_cost;
6971  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
6972  *indexPages = dataPagesFetched;
6973 }
#define NIL
Definition: pg_list.h:65
BlockNumber nEntryPages
Definition: gin.h:45
bool attHasNormalScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:6360
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
IndexOptInfo * indexinfo
Definition: pathnodes.h:1179
bool attHasFullScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:6359
#define Min(x, y)
Definition: c.h:911
double partialEntries
Definition: selfuncs.c:6361
double searchEntries
Definition: selfuncs.c:6363
Oid reltablespace
Definition: pathnodes.h:792
int scale
Definition: pgbench.c:153
int64 nEntries
Definition: gin.h:47
uint32 BlockNumber
Definition: block.h:31
bool hypothetical
Definition: pathnodes.h:829
List * indexclauses
Definition: pathnodes.h:1180
double tuples
Definition: pathnodes.h:797
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:6362
BlockNumber pages
Definition: pathnodes.h:796
RelOptInfo * rel
Definition: pathnodes.h:793
#define ERROR
Definition: elog.h:43
AttrNumber indexcol
Definition: pathnodes.h:1228
#define lfirst_node(type, lc)
Definition: pg_list.h:193
#define NoLock
Definition: lockdefs.h:34
double cpu_operator_cost
Definition: costsize.c:114
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:5566
double rint(double x)
Definition: rint.c:21
List * indexquals
Definition: pathnodes.h:1226
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:671
Expr * clause
Definition: pathnodes.h:1945
BlockNumber nPendingPages
Definition: gin.h:43
double arrayScans
Definition: selfuncs.c:6364
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:628
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, OpExpr *clause, GinQualCounts *counts)
Definition: selfuncs.c:6482
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, ScalarArrayOpExpr *clause, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:6532
BlockNumber nDataPages
Definition: gin.h:46
#define Max(x, y)
Definition: c.h:905
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:5596
static int list_length(const List *l)
Definition: pg_list.h:169
BlockNumber nTotalPages
Definition: gin.h:44
int nkeycolumns
Definition: pathnodes.h:802
#define nodeTag(nodeptr)
Definition: nodes.h:530
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:152
#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:69
Definition: pg_list.h:50
double cpu_index_tuple_cost
Definition: costsize.c:113
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:126
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:825
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:5868

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

6243 {
6244  IndexOptInfo *index = path->indexinfo;
6245  GenericCosts costs;
6246  Cost descentCost;
6247 
6248  MemSet(&costs, 0, sizeof(costs));
6249 
6250  genericcostestimate(root, path, loop_count, &costs);
6251 
6252  /*
6253  * We model index descent costs similarly to those for btree, but to do
6254  * that we first need an idea of the tree height. We somewhat arbitrarily
6255  * assume that the fanout is 100, meaning the tree height is at most
6256  * log100(index->pages).
6257  *
6258  * Although this computation isn't really expensive enough to require
6259  * caching, we might as well use index->tree_height to cache it.
6260  */
6261  if (index->tree_height < 0) /* unknown? */
6262  {
6263  if (index->pages > 1) /* avoid computing log(0) */
6264  index->tree_height = (int) (log(index->pages) / log(100.0));
6265  else
6266  index->tree_height = 0;
6267  }
6268 
6269  /*
6270  * Add a CPU-cost component to represent the costs of initial descent. We
6271  * just use log(N) here not log2(N) since the branching factor isn't
6272  * necessarily two anyway. As for btree, charge once per SA scan.
6273  */
6274  if (index->tuples > 1) /* avoid computing log(0) */
6275  {
6276  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6277  costs.indexStartupCost += descentCost;
6278  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6279  }
6280 
6281  /*
6282  * Likewise add a per-page charge, calculated the same as for btrees.
6283  */
6284  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6285  costs.indexStartupCost += descentCost;
6286  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6287 
6288  *indexStartupCost = costs.indexStartupCost;
6289  *indexTotalCost = costs.indexTotalCost;
6290  *indexSelectivity = costs.indexSelectivity;
6291  *indexCorrelation = costs.indexCorrelation;
6292  *indexPages = costs.numIndexPages;
6293 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
IndexOptInfo * indexinfo
Definition: pathnodes.h:1179
#define MemSet(start, val, len)
Definition: c.h:962
double tuples
Definition: pathnodes.h:797
int tree_height
Definition: pathnodes.h:798
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:796
double num_sa_scans
Definition: selfuncs.h:113
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5650
double cpu_operator_cost
Definition: costsize.c:114
Cost indexTotalCost
Definition: selfuncs.h:105
double indexCorrelation
Definition: selfuncs.h:107
Cost indexStartupCost
Definition: selfuncs.h:104
double Cost
Definition: nodes.h:659
double numIndexPages
Definition: selfuncs.h:110

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

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

Referenced by hashhandler().

6199 {
6200  GenericCosts costs;
6201 
6202  MemSet(&costs, 0, sizeof(costs));
6203 
6204  genericcostestimate(root, path, loop_count, &costs);
6205 
6206  /*
6207  * A hash index has no descent costs as such, since the index AM can go
6208  * directly to the target bucket after computing the hash value. There
6209  * are a couple of other hash-specific costs that we could conceivably add
6210  * here, though:
6211  *
6212  * Ideally we'd charge spc_random_page_cost for each page in the target
6213  * bucket, not just the numIndexPages pages that genericcostestimate
6214  * thought we'd visit. However in most cases we don't know which bucket
6215  * that will be. There's no point in considering the average bucket size
6216  * because the hash AM makes sure that's always one page.
6217  *
6218  * Likewise, we could consider charging some CPU for each index tuple in
6219  * the bucket, if we knew how many there were. But the per-tuple cost is
6220  * just a hash value comparison, not a general datatype-dependent
6221  * comparison, so any such charge ought to be quite a bit less than
6222  * cpu_operator_cost; which makes it probably not worth worrying about.
6223  *
6224  * A bigger issue is that chance hash-value collisions will result in
6225  * wasted probes into the heap. We don't currently attempt to model this
6226  * cost on the grounds that it's rare, but maybe it's not rare enough.
6227  * (Any fix for this ought to consider the generic lossy-operator problem,
6228  * though; it's not entirely hash-specific.)
6229  */
6230 
6231  *indexStartupCost = costs.indexStartupCost;
6232  *indexTotalCost = costs.indexTotalCost;
6233  *indexSelectivity = costs.indexSelectivity;
6234  *indexCorrelation = costs.indexCorrelation;
6235  *indexPages = costs.numIndexPages;
6236 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
#define MemSet(start, val, len)
Definition: c.h:962
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5650
Cost indexTotalCost
Definition: selfuncs.h:105
double indexCorrelation
Definition: selfuncs.h:107
Cost indexStartupCost
Definition: selfuncs.h:104
double numIndexPages
Definition: selfuncs.h:110

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

6300 {
6301  IndexOptInfo *index = path->indexinfo;
6302  GenericCosts costs;
6303  Cost descentCost;
6304 
6305  MemSet(&costs, 0, sizeof(costs));
6306 
6307  genericcostestimate(root, path, loop_count, &costs);
6308 
6309  /*
6310  * We model index descent costs similarly to those for btree, but to do
6311  * that we first need an idea of the tree height. We somewhat arbitrarily
6312  * assume that the fanout is 100, meaning the tree height is at most
6313  * log100(index->pages).
6314  *
6315  * Although this computation isn't really expensive enough to require
6316  * caching, we might as well use index->tree_height to cache it.
6317  */
6318  if (index->tree_height < 0) /* unknown? */
6319  {
6320  if (index->pages > 1) /* avoid computing log(0) */
6321  index->tree_height = (int) (log(index->pages) / log(100.0));
6322  else
6323  index->tree_height = 0;
6324  }
6325 
6326  /*
6327  * Add a CPU-cost component to represent the costs of initial descent. We
6328  * just use log(N) here not log2(N) since the branching factor isn't
6329  * necessarily two anyway. As for btree, charge once per SA scan.
6330  */
6331  if (index->tuples > 1) /* avoid computing log(0) */
6332  {
6333  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6334  costs.indexStartupCost += descentCost;
6335  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6336  }
6337 
6338  /*
6339  * Likewise add a per-page charge, calculated the same as for btrees.
6340  */
6341  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6342  costs.indexStartupCost += descentCost;
6343  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6344 
6345  *indexStartupCost = costs.indexStartupCost;
6346  *indexTotalCost = costs.indexTotalCost;
6347  *indexSelectivity = costs.indexSelectivity;
6348  *indexCorrelation = costs.indexCorrelation;
6349  *indexPages = costs.numIndexPages;
6350 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
IndexOptInfo * indexinfo
Definition: pathnodes.h:1179
#define MemSet(start, val, len)
Definition: c.h:962
double tuples
Definition: pathnodes.h:797
int tree_height
Definition: pathnodes.h:798
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:796
double num_sa_scans
Definition: selfuncs.h:113
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5650
double cpu_operator_cost
Definition: costsize.c:114
Cost indexTotalCost
Definition: selfuncs.h:105
double indexCorrelation
Definition: selfuncs.h:107
Cost indexStartupCost
Definition: selfuncs.h:104
double Cost
Definition: nodes.h:659
double numIndexPages
Definition: selfuncs.h:110