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

References Abs, AccessShareLock, Assert, attnum, ATTSTATSSLOT_NUMBERS, BoolGetDatum, brinGetStats(), CLAMP_PROBABILITY, clauselist_selectivity(), cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, free_attstatsslot(), VariableStatData::freefunc, get_attstatsslot(), get_index_stats_hook, get_relation_stats_hook, get_tablespace_page_costs(), HeapTupleIsValid, index_close(), index_open(), IndexQualInfo::indexcol, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, IndexPath::indexquals, Int16GetDatum, InvalidOid, JOIN_INNER, lfirst, Max, Min, AttStatsSlot::nnumbers, AttStatsSlot::numbers, ObjectIdGetDatum, orderby_operands_eval_cost(), other_operands_eval_cost(), RelOptInfo::pages, IndexOptInfo::pages, BrinStatsData::pagesPerRange, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, IndexOptInfo::reltablespace, BrinStatsData::revmapNumPages, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

8047 {
8048  IndexOptInfo *index = path->indexinfo;
8049  List *indexQuals = path->indexquals;
8050  double numPages = index->pages;
8051  RelOptInfo *baserel = index->rel;
8052  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
8053  List *qinfos;
8054  Cost spc_seq_page_cost;
8055  Cost spc_random_page_cost;
8056  double qual_arg_cost;
8057  double qualSelectivity;
8058  BrinStatsData statsData;
8059  double indexRanges;
8060  double minimalRanges;
8061  double estimatedRanges;
8062  double selec;
8063  Relation indexRel;
8064  ListCell *l;
8065  VariableStatData vardata;
8066 
8067  Assert(rte->rtekind == RTE_RELATION);
8068 
8069  /* fetch estimated page cost for the tablespace containing the index */
8071  &spc_random_page_cost,
8072  &spc_seq_page_cost);
8073 
8074  /*
8075  * Obtain some data from the index itself.
8076  */
8077  indexRel = index_open(index->indexoid, AccessShareLock);
8078  brinGetStats(indexRel, &statsData);
8079  index_close(indexRel, AccessShareLock);
8080 
8081  /*
8082  * Compute index correlation
8083  *
8084  * Because we can use all index quals equally when scanning, we can use
8085  * the largest correlation (in absolute value) among columns used by the
8086  * query. Start at zero, the worst possible case. If we cannot find any
8087  * correlation statistics, we will keep it as 0.
8088  */
8089  *indexCorrelation = 0;
8090 
8091  qinfos = deconstruct_indexquals(path);
8092  foreach(l, qinfos)
8093  {
8094  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
8095  AttrNumber attnum = index->indexkeys[qinfo->indexcol];
8096 
8097  /* attempt to lookup stats in relation for this index column */
8098  if (attnum != 0)
8099  {
8100  /* Simple variable -- look to stats for the underlying table */
8102  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
8103  {
8104  /*
8105  * The hook took control of acquiring a stats tuple. If it
8106  * did supply a tuple, it'd better have supplied a freefunc.
8107  */
8108  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
8109  elog(ERROR,
8110  "no function provided to release variable stats with");
8111  }
8112  else
8113  {
8114  vardata.statsTuple =
8116  ObjectIdGetDatum(rte->relid),
8117  Int16GetDatum(attnum),
8118  BoolGetDatum(false));
8119  vardata.freefunc = ReleaseSysCache;
8120  }
8121  }
8122  else
8123  {
8124  /*
8125  * Looks like we've found an expression column in the index. Let's
8126  * see if there's any stats for it.
8127  */
8128 
8129  /* get the attnum from the 0-based index. */
8130  attnum = qinfo->indexcol + 1;
8131 
8132  if (get_index_stats_hook &&
8133  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
8134  {
8135  /*
8136  * The hook took control of acquiring a stats tuple. If it
8137  * did supply a tuple, it'd better have supplied a freefunc.
8138  */
8139  if (HeapTupleIsValid(vardata.statsTuple) &&
8140  !vardata.freefunc)
8141  elog(ERROR, "no function provided to release variable stats with");
8142  }
8143  else
8144  {
8146  ObjectIdGetDatum(index->indexoid),
8147  Int16GetDatum(attnum),
8148  BoolGetDatum(false));
8149  vardata.freefunc = ReleaseSysCache;
8150  }
8151  }
8152 
8153  if (HeapTupleIsValid(vardata.statsTuple))
8154  {
8155  AttStatsSlot sslot;
8156 
8157  if (get_attstatsslot(&sslot, vardata.statsTuple,
8158  STATISTIC_KIND_CORRELATION, InvalidOid,
8160  {
8161  double varCorrelation = 0.0;
8162 
8163  if (sslot.nnumbers > 0)
8164  varCorrelation = Abs(sslot.numbers[0]);
8165 
8166  if (varCorrelation > *indexCorrelation)
8167  *indexCorrelation = varCorrelation;
8168 
8169  free_attstatsslot(&sslot);
8170  }
8171  }
8172 
8173  ReleaseVariableStats(vardata);
8174  }
8175 
8176  qualSelectivity = clauselist_selectivity(root, indexQuals,
8177  baserel->relid,
8178  JOIN_INNER, NULL);
8179 
8180  /* work out the actual number of ranges in the index */
8181  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
8182  1.0);
8183 
8184  /*
8185  * Now calculate the minimum possible ranges we could match with if all of
8186  * the rows were in the perfect order in the table's heap.
8187  */
8188  minimalRanges = ceil(indexRanges * qualSelectivity);
8189 
8190  /*
8191  * Now estimate the number of ranges that we'll touch by using the
8192  * indexCorrelation from the stats. Careful not to divide by zero (note
8193  * we're using the absolute value of the correlation).
8194  */
8195  if (*indexCorrelation < 1.0e-10)
8196  estimatedRanges = indexRanges;
8197  else
8198  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
8199 
8200  /* we expect to visit this portion of the table */
8201  selec = estimatedRanges / indexRanges;
8202 
8203  CLAMP_PROBABILITY(selec);
8204 
8205  *indexSelectivity = selec;
8206 
8207  /*
8208  * Compute the index qual costs, much as in genericcostestimate, to add to
8209  * the index costs.
8210  */
8211  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
8212  orderby_operands_eval_cost(root, path);
8213 
8214  /*
8215  * Compute the startup cost as the cost to read the whole revmap
8216  * sequentially, including the cost to execute the index quals.
8217  */
8218  *indexStartupCost =
8219  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8220  *indexStartupCost += qual_arg_cost;
8221 
8222  /*
8223  * To read a BRIN index there might be a bit of back and forth over
8224  * regular pages, as revmap might point to them out of sequential order;
8225  * calculate the total cost as reading the whole index in random order.
8226  */
8227  *indexTotalCost = *indexStartupCost +
8228  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8229 
8230  /*
8231  * Charge a small amount per range tuple which we expect to match to. This
8232  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8233  * will set a bit for each page in the range when we find a matching
8234  * range, so we must multiply the charge by the number of pages in the
8235  * range.
8236  */
8237  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8238  statsData.pagesPerRange;
8239 
8240  *indexPages = index->pages;
8241 }
IndexOptInfo * indexinfo
Definition: relation.h:1168
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:54
#define Min(x, y)
Definition: c.h:890
#define Int16GetDatum(X)
Definition: postgres.h:436
#define AccessShareLock
Definition: lockdefs.h:36
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
Oid reltablespace
Definition: relation.h:767
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6666
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6571
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6691
#define Abs(x)
Definition: c.h:896
Definition: type.h:89
BlockNumber pages
Definition: relation.h:771
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
List * indexquals
Definition: relation.h:1170
RelOptInfo * rel
Definition: relation.h:768
#define planner_rt_fetch(rti, root)
Definition: relation.h:354
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:492
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1134
float4 * numbers
Definition: lsyscache.h:53
double cpu_operator_cost
Definition: costsize.c:112
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:155
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: relation.h:650
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1160
#define BoolGetDatum(X)
Definition: postgres.h:387
#define InvalidOid
Definition: postgres_ext.h:36
BlockNumber pagesPerRange
Definition: brin.h:34
int16 attnum
Definition: pg_attribute.h:79
#define Max(x, y)
Definition: c.h:884
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
BlockNumber pages
Definition: relation.h:661
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2909
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:106
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:156
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:178
RTEKind rtekind
Definition: parsenodes.h:960
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
#define elog(elevel,...)
Definition: elog.h:226
int * indexkeys
Definition: relation.h:778
Oid indexoid
Definition: relation.h:766
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
Definition: pg_list.h:45
int16 AttrNumber
Definition: attnum.h:21
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:152
double Cost
Definition: nodes.h:651
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1090
BlockNumber revmapNumPages
Definition: brin.h:35
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3039

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

References add_predicate_to_quals(), Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, IndexQualInfo::clause_op, clauselist_selectivity(), cpu_operator_cost, deconstruct_indexquals(), 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, IndexQualInfo::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst, MemSet, IndexOptInfo::ncolumns, NIL, IndexOptInfo::nkeycolumns, AttStatsSlot::nnumbers, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum, OidIsValid, IndexOptInfo::opcintype, IndexOptInfo::opfamily, IndexQualInfo::other_operand, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reverse_sort, IndexQualInfo::rinfo, rint(), RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

6965 {
6966  IndexOptInfo *index = path->indexinfo;
6967  List *qinfos;
6968  GenericCosts costs;
6969  Oid relid;
6970  AttrNumber colnum;
6971  VariableStatData vardata;
6972  double numIndexTuples;
6973  Cost descentCost;
6974  List *indexBoundQuals;
6975  int indexcol;
6976  bool eqQualHere;
6977  bool found_saop;
6978  bool found_is_null_op;
6979  double num_sa_scans;
6980  ListCell *lc;
6981 
6982  /* Do preliminary analysis of indexquals */
6983  qinfos = deconstruct_indexquals(path);
6984 
6985  /*
6986  * For a btree scan, only leading '=' quals plus inequality quals for the
6987  * immediately next attribute contribute to index selectivity (these are
6988  * the "boundary quals" that determine the starting and stopping points of
6989  * the index scan). Additional quals can suppress visits to the heap, so
6990  * it's OK to count them in indexSelectivity, but they should not count
6991  * for estimating numIndexTuples. So we must examine the given indexquals
6992  * to find out which ones count as boundary quals. We rely on the
6993  * knowledge that they are given in index column order.
6994  *
6995  * For a RowCompareExpr, we consider only the first column, just as
6996  * rowcomparesel() does.
6997  *
6998  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6999  * index scans not one, but the ScalarArrayOpExpr's operator can be
7000  * considered to act the same as it normally does.
7001  */
7002  indexBoundQuals = NIL;
7003  indexcol = 0;
7004  eqQualHere = false;
7005  found_saop = false;
7006  found_is_null_op = false;
7007  num_sa_scans = 1;
7008  foreach(lc, qinfos)
7009  {
7010  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
7011  RestrictInfo *rinfo = qinfo->rinfo;
7012  Expr *clause = rinfo->clause;
7013  Oid clause_op;
7014  int op_strategy;
7015 
7016  if (indexcol != qinfo->indexcol)
7017  {
7018  /* Beginning of a new column's quals */
7019  if (!eqQualHere)
7020  break; /* done if no '=' qual for indexcol */
7021  eqQualHere = false;
7022  indexcol++;
7023  if (indexcol != qinfo->indexcol)
7024  break; /* no quals at all for indexcol */
7025  }
7026 
7027  if (IsA(clause, ScalarArrayOpExpr))
7028  {
7029  int alength = estimate_array_length(qinfo->other_operand);
7030 
7031  found_saop = true;
7032  /* count up number of SA scans induced by indexBoundQuals only */
7033  if (alength > 1)
7034  num_sa_scans *= alength;
7035  }
7036  else if (IsA(clause, NullTest))
7037  {
7038  NullTest *nt = (NullTest *) clause;
7039 
7040  if (nt->nulltesttype == IS_NULL)
7041  {
7042  found_is_null_op = true;
7043  /* IS NULL is like = for selectivity determination purposes */
7044  eqQualHere = true;
7045  }
7046  }
7047 
7048  /*
7049  * We would need to commute the clause_op if not varonleft, except
7050  * that we only care if it's equality or not, so that refinement is
7051  * unnecessary.
7052  */
7053  clause_op = qinfo->clause_op;
7054 
7055  /* check for equality operator */
7056  if (OidIsValid(clause_op))
7057  {
7058  op_strategy = get_op_opfamily_strategy(clause_op,
7059  index->opfamily[indexcol]);
7060  Assert(op_strategy != 0); /* not a member of opfamily?? */
7061  if (op_strategy == BTEqualStrategyNumber)
7062  eqQualHere = true;
7063  }
7064 
7065  indexBoundQuals = lappend(indexBoundQuals, rinfo);
7066  }
7067 
7068  /*
7069  * If index is unique and we found an '=' clause for each column, we can
7070  * just assume numIndexTuples = 1 and skip the expensive
7071  * clauselist_selectivity calculations. However, a ScalarArrayOp or
7072  * NullTest invalidates that theory, even though it sets eqQualHere.
7073  */
7074  if (index->unique &&
7075  indexcol == index->nkeycolumns - 1 &&
7076  eqQualHere &&
7077  !found_saop &&
7078  !found_is_null_op)
7079  numIndexTuples = 1.0;
7080  else
7081  {
7082  List *selectivityQuals;
7083  Selectivity btreeSelectivity;
7084 
7085  /*
7086  * If the index is partial, AND the index predicate with the
7087  * index-bound quals to produce a more accurate idea of the number of
7088  * rows covered by the bound conditions.
7089  */
7090  selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
7091 
7092  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
7093  index->rel->relid,
7094  JOIN_INNER,
7095  NULL);
7096  numIndexTuples = btreeSelectivity * index->rel->tuples;
7097 
7098  /*
7099  * As in genericcostestimate(), we have to adjust for any
7100  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
7101  * to integer.
7102  */
7103  numIndexTuples = rint(numIndexTuples / num_sa_scans);
7104  }
7105 
7106  /*
7107  * Now do generic index cost estimation.
7108  */
7109  MemSet(&costs, 0, sizeof(costs));
7110  costs.numIndexTuples = numIndexTuples;
7111 
7112  genericcostestimate(root, path, loop_count, qinfos, &costs);
7113 
7114  /*
7115  * Add a CPU-cost component to represent the costs of initial btree
7116  * descent. We don't charge any I/O cost for touching upper btree levels,
7117  * since they tend to stay in cache, but we still have to do about log2(N)
7118  * comparisons to descend a btree of N leaf tuples. We charge one
7119  * cpu_operator_cost per comparison.
7120  *
7121  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
7122  * ones after the first one are not startup cost so far as the overall
7123  * plan is concerned, so add them only to "total" cost.
7124  */
7125  if (index->tuples > 1) /* avoid computing log(0) */
7126  {
7127  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
7128  costs.indexStartupCost += descentCost;
7129  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7130  }
7131 
7132  /*
7133  * Even though we're not charging I/O cost for touching upper btree pages,
7134  * it's still reasonable to charge some CPU cost per page descended
7135  * through. Moreover, if we had no such charge at all, bloated indexes
7136  * would appear to have the same search cost as unbloated ones, at least
7137  * in cases where only a single leaf page is expected to be visited. This
7138  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
7139  * touched. The number of such pages is btree tree height plus one (ie,
7140  * we charge for the leaf page too). As above, charge once per SA scan.
7141  */
7142  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7143  costs.indexStartupCost += descentCost;
7144  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7145 
7146  /*
7147  * If we can get an estimate of the first column's ordering correlation C
7148  * from pg_statistic, estimate the index correlation as C for a
7149  * single-column index, or C * 0.75 for multiple columns. (The idea here
7150  * is that multiple columns dilute the importance of the first column's
7151  * ordering, but don't negate it entirely. Before 8.0 we divided the
7152  * correlation by the number of columns, but that seems too strong.)
7153  */
7154  MemSet(&vardata, 0, sizeof(vardata));
7155 
7156  if (index->indexkeys[0] != 0)
7157  {
7158  /* Simple variable --- look to stats for the underlying table */
7159  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
7160 
7161  Assert(rte->rtekind == RTE_RELATION);
7162  relid = rte->relid;
7163  Assert(relid != InvalidOid);
7164  colnum = index->indexkeys[0];
7165 
7167  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
7168  {
7169  /*
7170  * The hook took control of acquiring a stats tuple. If it did
7171  * supply a tuple, it'd better have supplied a freefunc.
7172  */
7173  if (HeapTupleIsValid(vardata.statsTuple) &&
7174  !vardata.freefunc)
7175  elog(ERROR, "no function provided to release variable stats with");
7176  }
7177  else
7178  {
7180  ObjectIdGetDatum(relid),
7181  Int16GetDatum(colnum),
7182  BoolGetDatum(rte->inh));
7183  vardata.freefunc = ReleaseSysCache;
7184  }
7185  }
7186  else
7187  {
7188  /* Expression --- maybe there are stats for the index itself */
7189  relid = index->indexoid;
7190  colnum = 1;
7191 
7192  if (get_index_stats_hook &&
7193  (*get_index_stats_hook) (root, relid, colnum, &vardata))
7194  {
7195  /*
7196  * The hook took control of acquiring a stats tuple. If it did
7197  * supply a tuple, it'd better have supplied a freefunc.
7198  */
7199  if (HeapTupleIsValid(vardata.statsTuple) &&
7200  !vardata.freefunc)
7201  elog(ERROR, "no function provided to release variable stats with");
7202  }
7203  else
7204  {
7206  ObjectIdGetDatum(relid),
7207  Int16GetDatum(colnum),
7208  BoolGetDatum(false));
7209  vardata.freefunc = ReleaseSysCache;
7210  }
7211  }
7212 
7213  if (HeapTupleIsValid(vardata.statsTuple))
7214  {
7215  Oid sortop;
7216  AttStatsSlot sslot;
7217 
7218  sortop = get_opfamily_member(index->opfamily[0],
7219  index->opcintype[0],
7220  index->opcintype[0],
7222  if (OidIsValid(sortop) &&
7223  get_attstatsslot(&sslot, vardata.statsTuple,
7224  STATISTIC_KIND_CORRELATION, sortop,
7226  {
7227  double varCorrelation;
7228 
7229  Assert(sslot.nnumbers == 1);
7230  varCorrelation = sslot.numbers[0];
7231 
7232  if (index->reverse_sort[0])
7233  varCorrelation = -varCorrelation;
7234 
7235  if (index->ncolumns > 1)
7236  costs.indexCorrelation = varCorrelation * 0.75;
7237  else
7238  costs.indexCorrelation = varCorrelation;
7239 
7240  free_attstatsslot(&sslot);
7241  }
7242  }
7243 
7244  ReleaseVariableStats(vardata);
7245 
7246  *indexStartupCost = costs.indexStartupCost;
7247  *indexTotalCost = costs.indexTotalCost;
7248  *indexSelectivity = costs.indexSelectivity;
7249  *indexCorrelation = costs.indexCorrelation;
7250  *indexPages = costs.numIndexPages;
7251 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:568
IndexOptInfo * indexinfo
Definition: relation.h:1168
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:54
double tuples
Definition: relation.h:662
static List * add_predicate_to_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6939
#define Int16GetDatum(X)
Definition: postgres.h:436
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
#define MemSet(start, val, len)
Definition: c.h:941
double Selectivity
Definition: nodes.h:650
double tuples
Definition: relation.h:772
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: relation.h:773
#define OidIsValid(objectId)
Definition: c.h:638
RestrictInfo * rinfo
Definition: selfuncs.h:109
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6571
bool unique
Definition: relation.h:802
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2190
RelOptInfo * rel
Definition: relation.h:768
#define planner_rt_fetch(rti, root)
Definition: relation.h:354
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:492
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1134
double num_sa_scans
Definition: selfuncs.h:141
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:112
Cost indexTotalCost
Definition: selfuncs.h:133
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:155
double rint(double x)
Definition: rint.c:21
int ncolumns
Definition: relation.h:776
Index relid
Definition: relation.h:650
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1887
double indexCorrelation
Definition: selfuncs.h:135
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1160
NullTestType nulltesttype
Definition: primnodes.h:1203
#define BoolGetDatum(X)
Definition: postgres.h:387
#define InvalidOid
Definition: postgres_ext.h:36
double numIndexTuples
Definition: selfuncs.h:139
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2909
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:106
int nkeycolumns
Definition: relation.h:777
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:156
Oid * opcintype
Definition: relation.h:782
Cost indexStartupCost
Definition: selfuncs.h:132
Oid * opfamily
Definition: relation.h:781
RTEKind rtekind
Definition: parsenodes.h:960
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:80
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
Node * other_operand
Definition: selfuncs.h:113
#define elog(elevel,...)
Definition: elog.h:226
int * indexkeys
Definition: relation.h:778
Oid indexoid
Definition: relation.h:766
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
bool * reverse_sort
Definition: relation.h:784
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:45
int16 AttrNumber
Definition: attnum.h:21
#define BTEqualStrategyNumber
Definition: stratnum.h:31
double Cost
Definition: nodes.h:651
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6720
double numIndexPages
Definition: selfuncs.h:138
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3039

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

References AccessShareLock, GinQualCounts::arrayScans, RestrictInfo::clause, clauselist_selectivity(), cpu_index_tuple_cost, cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, GinQualCounts::exactEntries, get_tablespace_page_costs(), gincost_opexpr(), gincost_scalararrayopexpr(), ginGetStats(), GinQualCounts::haveFullScan, IndexOptInfo::hypothetical, index_close(), index_open(), index_pages_fetched(), IndexPath::indexinfo, IndexOptInfo::indexoid, IndexPath::indexorderbys, IndexPath::indexquals, IndexOptInfo::indpred, IsA, JOIN_INNER, lfirst, list_concat(), list_length(), list_make1, Max, Min, GinStatsData::nDataPages, GinStatsData::nEntries, GinStatsData::nEntryPages, NIL, nodeTag, GinStatsData::nPendingPages, GinStatsData::nTotalPages, orderby_operands_eval_cost(), other_operands_eval_cost(), IndexOptInfo::pages, GinQualCounts::partialEntries, predicate_implied_by(), IndexOptInfo::rel, RelOptInfo::relid, IndexOptInfo::reltablespace, IndexQualInfo::rinfo, rint(), scale, GinQualCounts::searchEntries, and IndexOptInfo::tuples.

Referenced by ginhandler().

7722 {
7723  IndexOptInfo *index = path->indexinfo;
7724  List *indexQuals = path->indexquals;
7725  List *indexOrderBys = path->indexorderbys;
7726  List *qinfos;
7727  ListCell *l;
7728  List *selectivityQuals;
7729  double numPages = index->pages,
7730  numTuples = index->tuples;
7731  double numEntryPages,
7732  numDataPages,
7733  numPendingPages,
7734  numEntries;
7735  GinQualCounts counts;
7736  bool matchPossible;
7737  double partialScale;
7738  double entryPagesFetched,
7739  dataPagesFetched,
7740  dataPagesFetchedBySel;
7741  double qual_op_cost,
7742  qual_arg_cost,
7743  spc_random_page_cost,
7744  outer_scans;
7745  Relation indexRel;
7746  GinStatsData ginStats;
7747 
7748  /* Do preliminary analysis of indexquals */
7749  qinfos = deconstruct_indexquals(path);
7750 
7751  /*
7752  * Obtain statistical information from the meta page, if possible. Else
7753  * set ginStats to zeroes, and we'll cope below.
7754  */
7755  if (!index->hypothetical)
7756  {
7757  indexRel = index_open(index->indexoid, AccessShareLock);
7758  ginGetStats(indexRel, &ginStats);
7759  index_close(indexRel, AccessShareLock);
7760  }
7761  else
7762  {
7763  memset(&ginStats, 0, sizeof(ginStats));
7764  }
7765 
7766  /*
7767  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7768  * trusted, but the other fields are data as of the last VACUUM. We can
7769  * scale them up to account for growth since then, but that method only
7770  * goes so far; in the worst case, the stats might be for a completely
7771  * empty index, and scaling them will produce pretty bogus numbers.
7772  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7773  * it's grown more than that, fall back to estimating things only from the
7774  * assumed-accurate index size. But we'll trust nPendingPages in any case
7775  * so long as it's not clearly insane, ie, more than the index size.
7776  */
7777  if (ginStats.nPendingPages < numPages)
7778  numPendingPages = ginStats.nPendingPages;
7779  else
7780  numPendingPages = 0;
7781 
7782  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7783  ginStats.nTotalPages > numPages / 4 &&
7784  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7785  {
7786  /*
7787  * OK, the stats seem close enough to sane to be trusted. But we
7788  * still need to scale them by the ratio numPages / nTotalPages to
7789  * account for growth since the last VACUUM.
7790  */
7791  double scale = numPages / ginStats.nTotalPages;
7792 
7793  numEntryPages = ceil(ginStats.nEntryPages * scale);
7794  numDataPages = ceil(ginStats.nDataPages * scale);
7795  numEntries = ceil(ginStats.nEntries * scale);
7796  /* ensure we didn't round up too much */
7797  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7798  numDataPages = Min(numDataPages,
7799  numPages - numPendingPages - numEntryPages);
7800  }
7801  else
7802  {
7803  /*
7804  * We might get here because it's a hypothetical index, or an index
7805  * created pre-9.1 and never vacuumed since upgrading (in which case
7806  * its stats would read as zeroes), or just because it's grown too
7807  * much since the last VACUUM for us to put our faith in scaling.
7808  *
7809  * Invent some plausible internal statistics based on the index page
7810  * count (and clamp that to at least 10 pages, just in case). We
7811  * estimate that 90% of the index is entry pages, and the rest is data
7812  * pages. Estimate 100 entries per entry page; this is rather bogus
7813  * since it'll depend on the size of the keys, but it's more robust
7814  * than trying to predict the number of entries per heap tuple.
7815  */
7816  numPages = Max(numPages, 10);
7817  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7818  numDataPages = numPages - numPendingPages - numEntryPages;
7819  numEntries = floor(numEntryPages * 100);
7820  }
7821 
7822  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7823  if (numEntries < 1)
7824  numEntries = 1;
7825 
7826  /*
7827  * Include predicate in selectivityQuals (should match
7828  * genericcostestimate)
7829  */
7830  if (index->indpred != NIL)
7831  {
7832  List *predExtraQuals = NIL;
7833 
7834  foreach(l, index->indpred)
7835  {
7836  Node *predQual = (Node *) lfirst(l);
7837  List *oneQual = list_make1(predQual);
7838 
7839  if (!predicate_implied_by(oneQual, indexQuals, false))
7840  predExtraQuals = list_concat(predExtraQuals, oneQual);
7841  }
7842  /* list_concat avoids modifying the passed-in indexQuals list */
7843  selectivityQuals = list_concat(predExtraQuals, indexQuals);
7844  }
7845  else
7846  selectivityQuals = indexQuals;
7847 
7848  /* Estimate the fraction of main-table tuples that will be visited */
7849  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7850  index->rel->relid,
7851  JOIN_INNER,
7852  NULL);
7853 
7854  /* fetch estimated page cost for tablespace containing index */
7856  &spc_random_page_cost,
7857  NULL);
7858 
7859  /*
7860  * Generic assumption about index correlation: there isn't any.
7861  */
7862  *indexCorrelation = 0.0;
7863 
7864  /*
7865  * Examine quals to estimate number of search entries & partial matches
7866  */
7867  memset(&counts, 0, sizeof(counts));
7868  counts.arrayScans = 1;
7869  matchPossible = true;
7870 
7871  foreach(l, qinfos)
7872  {
7873  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7874  Expr *clause = qinfo->rinfo->clause;
7875 
7876  if (IsA(clause, OpExpr))
7877  {
7878  matchPossible = gincost_opexpr(root,
7879  index,
7880  qinfo,
7881  &counts);
7882  if (!matchPossible)
7883  break;
7884  }
7885  else if (IsA(clause, ScalarArrayOpExpr))
7886  {
7887  matchPossible = gincost_scalararrayopexpr(root,
7888  index,
7889  qinfo,
7890  numEntries,
7891  &counts);
7892  if (!matchPossible)
7893  break;
7894  }
7895  else
7896  {
7897  /* shouldn't be anything else for a GIN index */
7898  elog(ERROR, "unsupported GIN indexqual type: %d",
7899  (int) nodeTag(clause));
7900  }
7901  }
7902 
7903  /* Fall out if there were any provably-unsatisfiable quals */
7904  if (!matchPossible)
7905  {
7906  *indexStartupCost = 0;
7907  *indexTotalCost = 0;
7908  *indexSelectivity = 0;
7909  return;
7910  }
7911 
7912  if (counts.haveFullScan || indexQuals == NIL)
7913  {
7914  /*
7915  * Full index scan will be required. We treat this as if every key in
7916  * the index had been listed in the query; is that reasonable?
7917  */
7918  counts.partialEntries = 0;
7919  counts.exactEntries = numEntries;
7920  counts.searchEntries = numEntries;
7921  }
7922 
7923  /* Will we have more than one iteration of a nestloop scan? */
7924  outer_scans = loop_count;
7925 
7926  /*
7927  * Compute cost to begin scan, first of all, pay attention to pending
7928  * list.
7929  */
7930  entryPagesFetched = numPendingPages;
7931 
7932  /*
7933  * Estimate number of entry pages read. We need to do
7934  * counts.searchEntries searches. Use a power function as it should be,
7935  * but tuples on leaf pages usually is much greater. Here we include all
7936  * searches in entry tree, including search of first entry in partial
7937  * match algorithm
7938  */
7939  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7940 
7941  /*
7942  * Add an estimate of entry pages read by partial match algorithm. It's a
7943  * scan over leaf pages in entry tree. We haven't any useful stats here,
7944  * so estimate it as proportion. Because counts.partialEntries is really
7945  * pretty bogus (see code above), it's possible that it is more than
7946  * numEntries; clamp the proportion to ensure sanity.
7947  */
7948  partialScale = counts.partialEntries / numEntries;
7949  partialScale = Min(partialScale, 1.0);
7950 
7951  entryPagesFetched += ceil(numEntryPages * partialScale);
7952 
7953  /*
7954  * Partial match algorithm reads all data pages before doing actual scan,
7955  * so it's a startup cost. Again, we haven't any useful stats here, so
7956  * estimate it as proportion.
7957  */
7958  dataPagesFetched = ceil(numDataPages * partialScale);
7959 
7960  /*
7961  * Calculate cache effects if more than one scan due to nestloops or array
7962  * quals. The result is pro-rated per nestloop scan, but the array qual
7963  * factor shouldn't be pro-rated (compare genericcostestimate).
7964  */
7965  if (outer_scans > 1 || counts.arrayScans > 1)
7966  {
7967  entryPagesFetched *= outer_scans * counts.arrayScans;
7968  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7969  (BlockNumber) numEntryPages,
7970  numEntryPages, root);
7971  entryPagesFetched /= outer_scans;
7972  dataPagesFetched *= outer_scans * counts.arrayScans;
7973  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7974  (BlockNumber) numDataPages,
7975  numDataPages, root);
7976  dataPagesFetched /= outer_scans;
7977  }
7978 
7979  /*
7980  * Here we use random page cost because logically-close pages could be far
7981  * apart on disk.
7982  */
7983  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7984 
7985  /*
7986  * Now compute the number of data pages fetched during the scan.
7987  *
7988  * We assume every entry to have the same number of items, and that there
7989  * is no overlap between them. (XXX: tsvector and array opclasses collect
7990  * statistics on the frequency of individual keys; it would be nice to use
7991  * those here.)
7992  */
7993  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7994 
7995  /*
7996  * If there is a lot of overlap among the entries, in particular if one of
7997  * the entries is very frequent, the above calculation can grossly
7998  * under-estimate. As a simple cross-check, calculate a lower bound based
7999  * on the overall selectivity of the quals. At a minimum, we must read
8000  * one item pointer for each matching entry.
8001  *
8002  * The width of each item pointer varies, based on the level of
8003  * compression. We don't have statistics on that, but an average of
8004  * around 3 bytes per item is fairly typical.
8005  */
8006  dataPagesFetchedBySel = ceil(*indexSelectivity *
8007  (numTuples / (BLCKSZ / 3)));
8008  if (dataPagesFetchedBySel > dataPagesFetched)
8009  dataPagesFetched = dataPagesFetchedBySel;
8010 
8011  /* Account for cache effects, the same as above */
8012  if (outer_scans > 1 || counts.arrayScans > 1)
8013  {
8014  dataPagesFetched *= outer_scans * counts.arrayScans;
8015  dataPagesFetched = index_pages_fetched(dataPagesFetched,
8016  (BlockNumber) numDataPages,
8017  numDataPages, root);
8018  dataPagesFetched /= outer_scans;
8019  }
8020 
8021  /* And apply random_page_cost as the cost per page */
8022  *indexTotalCost = *indexStartupCost +
8023  dataPagesFetched * spc_random_page_cost;
8024 
8025  /*
8026  * Add on index qual eval costs, much as in genericcostestimate
8027  */
8028  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
8029  orderby_operands_eval_cost(root, path);
8030  qual_op_cost = cpu_operator_cost *
8031  (list_length(indexQuals) + list_length(indexOrderBys));
8032 
8033  *indexStartupCost += qual_arg_cost;
8034  *indexTotalCost += qual_arg_cost;
8035  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
8036  *indexPages = dataPagesFetched;
8037 }
#define NIL
Definition: pg_list.h:69
BlockNumber nEntryPages
Definition: gin.h:45
#define IsA(nodeptr, _type_)
Definition: nodes.h:568
IndexOptInfo * indexinfo
Definition: relation.h:1168
#define Min(x, y)
Definition: c.h:890
#define AccessShareLock
Definition: lockdefs.h:36
double partialEntries
Definition: selfuncs.c:7431
Definition: nodes.h:517
double searchEntries
Definition: selfuncs.c:7433
Oid reltablespace
Definition: relation.h:767
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6666
int scale
Definition: pgbench.c:150
int64 nEntries
Definition: gin.h:47
List * list_concat(List *list1, List *list2)
Definition: list.c:321
uint32 BlockNumber
Definition: block.h:31
bool hypothetical
Definition: relation.h:804
double tuples
Definition: relation.h:772
RestrictInfo * rinfo
Definition: selfuncs.h:109
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6571
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6691
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:7432
BlockNumber pages
Definition: relation.h:771
#define list_make1(x1)
Definition: pg_list.h:139
List * indexquals
Definition: relation.h:1170
RelOptInfo * rel
Definition: relation.h:768
#define ERROR
Definition: elog.h:43
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7603
bool haveFullScan
Definition: selfuncs.c:7430
double cpu_operator_cost
Definition: costsize.c:112
double rint(double x)
Definition: rint.c:21
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: relation.h:650
Expr * clause
Definition: relation.h:1887
BlockNumber nPendingPages
Definition: gin.h:43
double arrayScans
Definition: selfuncs.c:7434
List * indexorderbys
Definition: relation.h:1172
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:637
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, GinQualCounts *counts)
Definition: selfuncs.c:7547
BlockNumber nDataPages
Definition: gin.h:46
#define Max(x, y)
Definition: c.h:884
#define lfirst(lc)
Definition: pg_list.h:106
static int list_length(const List *l)
Definition: pg_list.h:89
BlockNumber nTotalPages
Definition: gin.h:44
#define nodeTag(nodeptr)
Definition: nodes.h:522
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:178
#define elog(elevel,...)
Definition: elog.h:226
Oid indexoid
Definition: relation.h:766
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
List * indpred
Definition: relation.h:791
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition: predtest.c:149
Definition: pg_list.h:45
double cpu_index_tuple_cost
Definition: costsize.c:111
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:152
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:827

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

References cpu_operator_cost, deconstruct_indexquals(), 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().

7306 {
7307  IndexOptInfo *index = path->indexinfo;
7308  List *qinfos;
7309  GenericCosts costs;
7310  Cost descentCost;
7311 
7312  /* Do preliminary analysis of indexquals */
7313  qinfos = deconstruct_indexquals(path);
7314 
7315  MemSet(&costs, 0, sizeof(costs));
7316 
7317  genericcostestimate(root, path, loop_count, qinfos, &costs);
7318 
7319  /*
7320  * We model index descent costs similarly to those for btree, but to do
7321  * that we first need an idea of the tree height. We somewhat arbitrarily
7322  * assume that the fanout is 100, meaning the tree height is at most
7323  * log100(index->pages).
7324  *
7325  * Although this computation isn't really expensive enough to require
7326  * caching, we might as well use index->tree_height to cache it.
7327  */
7328  if (index->tree_height < 0) /* unknown? */
7329  {
7330  if (index->pages > 1) /* avoid computing log(0) */
7331  index->tree_height = (int) (log(index->pages) / log(100.0));
7332  else
7333  index->tree_height = 0;
7334  }
7335 
7336  /*
7337  * Add a CPU-cost component to represent the costs of initial descent. We
7338  * just use log(N) here not log2(N) since the branching factor isn't
7339  * necessarily two anyway. As for btree, charge once per SA scan.
7340  */
7341  if (index->tuples > 1) /* avoid computing log(0) */
7342  {
7343  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7344  costs.indexStartupCost += descentCost;
7345  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7346  }
7347 
7348  /*
7349  * Likewise add a per-page charge, calculated the same as for btrees.
7350  */
7351  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7352  costs.indexStartupCost += descentCost;
7353  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7354 
7355  *indexStartupCost = costs.indexStartupCost;
7356  *indexTotalCost = costs.indexTotalCost;
7357  *indexSelectivity = costs.indexSelectivity;
7358  *indexCorrelation = costs.indexCorrelation;
7359  *indexPages = costs.numIndexPages;
7360 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
IndexOptInfo * indexinfo
Definition: relation.h:1168
#define MemSet(start, val, len)
Definition: c.h:941
double tuples
Definition: relation.h:772
int tree_height
Definition: relation.h:773
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6571
Definition: type.h:89
BlockNumber pages
Definition: relation.h:771
double num_sa_scans
Definition: selfuncs.h:141
double cpu_operator_cost
Definition: costsize.c:112
Cost indexTotalCost
Definition: selfuncs.h:133
double indexCorrelation
Definition: selfuncs.h:135
Cost indexStartupCost
Definition: selfuncs.h:132
Definition: pg_list.h:45
double Cost
Definition: nodes.h:651
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6720
double numIndexPages
Definition: selfuncs.h:138

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

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

Referenced by hashhandler().

7258 {
7259  List *qinfos;
7260  GenericCosts costs;
7261 
7262  /* Do preliminary analysis of indexquals */
7263  qinfos = deconstruct_indexquals(path);
7264 
7265  MemSet(&costs, 0, sizeof(costs));
7266 
7267  genericcostestimate(root, path, loop_count, qinfos, &costs);
7268 
7269  /*
7270  * A hash index has no descent costs as such, since the index AM can go
7271  * directly to the target bucket after computing the hash value. There
7272  * are a couple of other hash-specific costs that we could conceivably add
7273  * here, though:
7274  *
7275  * Ideally we'd charge spc_random_page_cost for each page in the target
7276  * bucket, not just the numIndexPages pages that genericcostestimate
7277  * thought we'd visit. However in most cases we don't know which bucket
7278  * that will be. There's no point in considering the average bucket size
7279  * because the hash AM makes sure that's always one page.
7280  *
7281  * Likewise, we could consider charging some CPU for each index tuple in
7282  * the bucket, if we knew how many there were. But the per-tuple cost is
7283  * just a hash value comparison, not a general datatype-dependent
7284  * comparison, so any such charge ought to be quite a bit less than
7285  * cpu_operator_cost; which makes it probably not worth worrying about.
7286  *
7287  * A bigger issue is that chance hash-value collisions will result in
7288  * wasted probes into the heap. We don't currently attempt to model this
7289  * cost on the grounds that it's rare, but maybe it's not rare enough.
7290  * (Any fix for this ought to consider the generic lossy-operator problem,
7291  * though; it's not entirely hash-specific.)
7292  */
7293 
7294  *indexStartupCost = costs.indexStartupCost;
7295  *indexTotalCost = costs.indexTotalCost;
7296  *indexSelectivity = costs.indexSelectivity;
7297  *indexCorrelation = costs.indexCorrelation;
7298  *indexPages = costs.numIndexPages;
7299 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
#define MemSet(start, val, len)
Definition: c.h:941
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6571
Cost indexTotalCost
Definition: selfuncs.h:133
double indexCorrelation
Definition: selfuncs.h:135
Cost indexStartupCost
Definition: selfuncs.h:132
Definition: pg_list.h:45
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6720
double numIndexPages
Definition: selfuncs.h:138

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

References cpu_operator_cost, deconstruct_indexquals(), 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().

7367 {
7368  IndexOptInfo *index = path->indexinfo;
7369  List *qinfos;
7370  GenericCosts costs;
7371  Cost descentCost;
7372 
7373  /* Do preliminary analysis of indexquals */
7374  qinfos = deconstruct_indexquals(path);
7375 
7376  MemSet(&costs, 0, sizeof(costs));
7377 
7378  genericcostestimate(root, path, loop_count, qinfos, &costs);
7379 
7380  /*
7381  * We model index descent costs similarly to those for btree, but to do
7382  * that we first need an idea of the tree height. We somewhat arbitrarily
7383  * assume that the fanout is 100, meaning the tree height is at most
7384  * log100(index->pages).
7385  *
7386  * Although this computation isn't really expensive enough to require
7387  * caching, we might as well use index->tree_height to cache it.
7388  */
7389  if (index->tree_height < 0) /* unknown? */
7390  {
7391  if (index->pages > 1) /* avoid computing log(0) */
7392  index->tree_height = (int) (log(index->pages) / log(100.0));
7393  else
7394  index->tree_height = 0;
7395  }
7396 
7397  /*
7398  * Add a CPU-cost component to represent the costs of initial descent. We
7399  * just use log(N) here not log2(N) since the branching factor isn't
7400  * necessarily two anyway. As for btree, charge once per SA scan.
7401  */
7402  if (index->tuples > 1) /* avoid computing log(0) */
7403  {
7404  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7405  costs.indexStartupCost += descentCost;
7406  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7407  }
7408 
7409  /*
7410  * Likewise add a per-page charge, calculated the same as for btrees.
7411  */
7412  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7413  costs.indexStartupCost += descentCost;
7414  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7415 
7416  *indexStartupCost = costs.indexStartupCost;
7417  *indexTotalCost = costs.indexTotalCost;
7418  *indexSelectivity = costs.indexSelectivity;
7419  *indexCorrelation = costs.indexCorrelation;
7420  *indexPages = costs.numIndexPages;
7421 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
IndexOptInfo * indexinfo
Definition: relation.h:1168
#define MemSet(start, val, len)
Definition: c.h:941
double tuples
Definition: relation.h:772
int tree_height
Definition: relation.h:773
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6571
Definition: type.h:89
BlockNumber pages
Definition: relation.h:771
double num_sa_scans
Definition: selfuncs.h:141
double cpu_operator_cost
Definition: costsize.c:112
Cost indexTotalCost
Definition: selfuncs.h:133
double indexCorrelation
Definition: selfuncs.h:135
Cost indexStartupCost
Definition: selfuncs.h:132
Definition: pg_list.h:45
double Cost
Definition: nodes.h:651
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6720
double numIndexPages
Definition: selfuncs.h:138