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

8028 {
8029  IndexOptInfo *index = path->indexinfo;
8030  List *indexQuals = path->indexquals;
8031  double numPages = index->pages;
8032  RelOptInfo *baserel = index->rel;
8033  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
8034  List *qinfos;
8035  Cost spc_seq_page_cost;
8036  Cost spc_random_page_cost;
8037  double qual_arg_cost;
8038  double qualSelectivity;
8039  BrinStatsData statsData;
8040  double indexRanges;
8041  double minimalRanges;
8042  double estimatedRanges;
8043  double selec;
8044  Relation indexRel;
8045  ListCell *l;
8046  VariableStatData vardata;
8047 
8048  Assert(rte->rtekind == RTE_RELATION);
8049 
8050  /* fetch estimated page cost for the tablespace containing the index */
8052  &spc_random_page_cost,
8053  &spc_seq_page_cost);
8054 
8055  /*
8056  * Obtain some data from the index itself.
8057  */
8058  indexRel = index_open(index->indexoid, AccessShareLock);
8059  brinGetStats(indexRel, &statsData);
8060  index_close(indexRel, AccessShareLock);
8061 
8062  /*
8063  * Compute index correlation
8064  *
8065  * Because we can use all index quals equally when scanning, we can use
8066  * the largest correlation (in absolute value) among columns used by the
8067  * query. Start at zero, the worst possible case. If we cannot find any
8068  * correlation statistics, we will keep it as 0.
8069  */
8070  *indexCorrelation = 0;
8071 
8072  qinfos = deconstruct_indexquals(path);
8073  foreach(l, qinfos)
8074  {
8075  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
8076  AttrNumber attnum = index->indexkeys[qinfo->indexcol];
8077 
8078  /* attempt to lookup stats in relation for this index column */
8079  if (attnum != 0)
8080  {
8081  /* Simple variable -- look to stats for the underlying table */
8083  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
8084  {
8085  /*
8086  * The hook took control of acquiring a stats tuple. If it
8087  * did supply a tuple, it'd better have supplied a freefunc.
8088  */
8089  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
8090  elog(ERROR,
8091  "no function provided to release variable stats with");
8092  }
8093  else
8094  {
8095  vardata.statsTuple =
8097  ObjectIdGetDatum(rte->relid),
8098  Int16GetDatum(attnum),
8099  BoolGetDatum(false));
8100  vardata.freefunc = ReleaseSysCache;
8101  }
8102  }
8103  else
8104  {
8105  /*
8106  * Looks like we've found an expression column in the index. Let's
8107  * see if there's any stats for it.
8108  */
8109 
8110  /* get the attnum from the 0-based index. */
8111  attnum = qinfo->indexcol + 1;
8112 
8113  if (get_index_stats_hook &&
8114  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
8115  {
8116  /*
8117  * The hook took control of acquiring a stats tuple. If it
8118  * did supply a tuple, it'd better have supplied a freefunc.
8119  */
8120  if (HeapTupleIsValid(vardata.statsTuple) &&
8121  !vardata.freefunc)
8122  elog(ERROR, "no function provided to release variable stats with");
8123  }
8124  else
8125  {
8127  ObjectIdGetDatum(index->indexoid),
8128  Int16GetDatum(attnum),
8129  BoolGetDatum(false));
8130  vardata.freefunc = ReleaseSysCache;
8131  }
8132  }
8133 
8134  if (HeapTupleIsValid(vardata.statsTuple))
8135  {
8136  AttStatsSlot sslot;
8137 
8138  if (get_attstatsslot(&sslot, vardata.statsTuple,
8139  STATISTIC_KIND_CORRELATION, InvalidOid,
8141  {
8142  double varCorrelation = 0.0;
8143 
8144  if (sslot.nnumbers > 0)
8145  varCorrelation = Abs(sslot.numbers[0]);
8146 
8147  if (varCorrelation > *indexCorrelation)
8148  *indexCorrelation = varCorrelation;
8149 
8150  free_attstatsslot(&sslot);
8151  }
8152  }
8153 
8154  ReleaseVariableStats(vardata);
8155  }
8156 
8157  qualSelectivity = clauselist_selectivity(root, indexQuals,
8158  baserel->relid,
8159  JOIN_INNER, NULL);
8160 
8161  /* work out the actual number of ranges in the index */
8162  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
8163  1.0);
8164 
8165  /*
8166  * Now calculate the minimum possible ranges we could match with if all of
8167  * the rows were in the perfect order in the table's heap.
8168  */
8169  minimalRanges = ceil(indexRanges * qualSelectivity);
8170 
8171  /*
8172  * Now estimate the number of ranges that we'll touch by using the
8173  * indexCorrelation from the stats. Careful not to divide by zero (note
8174  * we're using the absolute value of the correlation).
8175  */
8176  if (*indexCorrelation < 1.0e-10)
8177  estimatedRanges = indexRanges;
8178  else
8179  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
8180 
8181  /* we expect to visit this portion of the table */
8182  selec = estimatedRanges / indexRanges;
8183 
8184  CLAMP_PROBABILITY(selec);
8185 
8186  *indexSelectivity = selec;
8187 
8188  /*
8189  * Compute the index qual costs, much as in genericcostestimate, to add to
8190  * the index costs.
8191  */
8192  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
8193  orderby_operands_eval_cost(root, path);
8194 
8195  /*
8196  * Compute the startup cost as the cost to read the whole revmap
8197  * sequentially, including the cost to execute the index quals.
8198  */
8199  *indexStartupCost =
8200  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8201  *indexStartupCost += qual_arg_cost;
8202 
8203  /*
8204  * To read a BRIN index there might be a bit of back and forth over
8205  * regular pages, as revmap might point to them out of sequential order;
8206  * calculate the total cost as reading the whole index in random order.
8207  */
8208  *indexTotalCost = *indexStartupCost +
8209  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8210 
8211  /*
8212  * Charge a small amount per range tuple which we expect to match to. This
8213  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8214  * will set a bit for each page in the range when we find a matching
8215  * range, so we must multiply the charge by the number of pages in the
8216  * range.
8217  */
8218  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8219  statsData.pagesPerRange;
8220 
8221  *indexPages = index->pages;
8222 }
IndexOptInfo * indexinfo
Definition: relation.h:1155
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
#define Min(x, y)
Definition: c.h:857
#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:754
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6647
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6552
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6672
#define Abs(x)
Definition: c.h:863
Definition: type.h:89
BlockNumber pages
Definition: relation.h:758
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
List * indexquals
Definition: relation.h:1157
RelOptInfo * rel
Definition: relation.h:755
#define planner_rt_fetch(rti, root)
Definition: relation.h:344
#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:52
double cpu_operator_cost
Definition: costsize.c:115
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:640
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:851
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
BlockNumber pages
Definition: relation.h:651
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2913
#define Assert(condition)
Definition: c.h:699
#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:176
RTEKind rtekind
Definition: parsenodes.h:962
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
int * indexkeys
Definition: relation.h:765
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:753
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:150
double Cost
Definition: nodes.h:647
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1089
BlockNumber revmapNumPages
Definition: brin.h:35
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3029

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

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

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

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

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

7287 {
7288  IndexOptInfo *index = path->indexinfo;
7289  List *qinfos;
7290  GenericCosts costs;
7291  Cost descentCost;
7292 
7293  /* Do preliminary analysis of indexquals */
7294  qinfos = deconstruct_indexquals(path);
7295 
7296  MemSet(&costs, 0, sizeof(costs));
7297 
7298  genericcostestimate(root, path, loop_count, qinfos, &costs);
7299 
7300  /*
7301  * We model index descent costs similarly to those for btree, but to do
7302  * that we first need an idea of the tree height. We somewhat arbitrarily
7303  * assume that the fanout is 100, meaning the tree height is at most
7304  * log100(index->pages).
7305  *
7306  * Although this computation isn't really expensive enough to require
7307  * caching, we might as well use index->tree_height to cache it.
7308  */
7309  if (index->tree_height < 0) /* unknown? */
7310  {
7311  if (index->pages > 1) /* avoid computing log(0) */
7312  index->tree_height = (int) (log(index->pages) / log(100.0));
7313  else
7314  index->tree_height = 0;
7315  }
7316 
7317  /*
7318  * Add a CPU-cost component to represent the costs of initial descent. We
7319  * just use log(N) here not log2(N) since the branching factor isn't
7320  * necessarily two anyway. As for btree, charge once per SA scan.
7321  */
7322  if (index->tuples > 1) /* avoid computing log(0) */
7323  {
7324  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7325  costs.indexStartupCost += descentCost;
7326  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7327  }
7328 
7329  /*
7330  * Likewise add a per-page charge, calculated the same as for btrees.
7331  */
7332  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7333  costs.indexStartupCost += descentCost;
7334  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7335 
7336  *indexStartupCost = costs.indexStartupCost;
7337  *indexTotalCost = costs.indexTotalCost;
7338  *indexSelectivity = costs.indexSelectivity;
7339  *indexCorrelation = costs.indexCorrelation;
7340  *indexPages = costs.numIndexPages;
7341 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
IndexOptInfo * indexinfo
Definition: relation.h:1155
#define MemSet(start, val, len)
Definition: c.h:908
double tuples
Definition: relation.h:759
int tree_height
Definition: relation.h:760
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6552
Definition: type.h:89
BlockNumber pages
Definition: relation.h:758
double num_sa_scans
Definition: selfuncs.h:141
double cpu_operator_cost
Definition: costsize.c:115
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:647
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6701
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 7235 of file selfuncs.c.

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

Referenced by hashhandler().

7239 {
7240  List *qinfos;
7241  GenericCosts costs;
7242 
7243  /* Do preliminary analysis of indexquals */
7244  qinfos = deconstruct_indexquals(path);
7245 
7246  MemSet(&costs, 0, sizeof(costs));
7247 
7248  genericcostestimate(root, path, loop_count, qinfos, &costs);
7249 
7250  /*
7251  * A hash index has no descent costs as such, since the index AM can go
7252  * directly to the target bucket after computing the hash value. There
7253  * are a couple of other hash-specific costs that we could conceivably add
7254  * here, though:
7255  *
7256  * Ideally we'd charge spc_random_page_cost for each page in the target
7257  * bucket, not just the numIndexPages pages that genericcostestimate
7258  * thought we'd visit. However in most cases we don't know which bucket
7259  * that will be. There's no point in considering the average bucket size
7260  * because the hash AM makes sure that's always one page.
7261  *
7262  * Likewise, we could consider charging some CPU for each index tuple in
7263  * the bucket, if we knew how many there were. But the per-tuple cost is
7264  * just a hash value comparison, not a general datatype-dependent
7265  * comparison, so any such charge ought to be quite a bit less than
7266  * cpu_operator_cost; which makes it probably not worth worrying about.
7267  *
7268  * A bigger issue is that chance hash-value collisions will result in
7269  * wasted probes into the heap. We don't currently attempt to model this
7270  * cost on the grounds that it's rare, but maybe it's not rare enough.
7271  * (Any fix for this ought to consider the generic lossy-operator problem,
7272  * though; it's not entirely hash-specific.)
7273  */
7274 
7275  *indexStartupCost = costs.indexStartupCost;
7276  *indexTotalCost = costs.indexTotalCost;
7277  *indexSelectivity = costs.indexSelectivity;
7278  *indexCorrelation = costs.indexCorrelation;
7279  *indexPages = costs.numIndexPages;
7280 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
#define MemSet(start, val, len)
Definition: c.h:908
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6552
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:6701
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 7344 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().

7348 {
7349  IndexOptInfo *index = path->indexinfo;
7350  List *qinfos;
7351  GenericCosts costs;
7352  Cost descentCost;
7353 
7354  /* Do preliminary analysis of indexquals */
7355  qinfos = deconstruct_indexquals(path);
7356 
7357  MemSet(&costs, 0, sizeof(costs));
7358 
7359  genericcostestimate(root, path, loop_count, qinfos, &costs);
7360 
7361  /*
7362  * We model index descent costs similarly to those for btree, but to do
7363  * that we first need an idea of the tree height. We somewhat arbitrarily
7364  * assume that the fanout is 100, meaning the tree height is at most
7365  * log100(index->pages).
7366  *
7367  * Although this computation isn't really expensive enough to require
7368  * caching, we might as well use index->tree_height to cache it.
7369  */
7370  if (index->tree_height < 0) /* unknown? */
7371  {
7372  if (index->pages > 1) /* avoid computing log(0) */
7373  index->tree_height = (int) (log(index->pages) / log(100.0));
7374  else
7375  index->tree_height = 0;
7376  }
7377 
7378  /*
7379  * Add a CPU-cost component to represent the costs of initial descent. We
7380  * just use log(N) here not log2(N) since the branching factor isn't
7381  * necessarily two anyway. As for btree, charge once per SA scan.
7382  */
7383  if (index->tuples > 1) /* avoid computing log(0) */
7384  {
7385  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7386  costs.indexStartupCost += descentCost;
7387  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7388  }
7389 
7390  /*
7391  * Likewise add a per-page charge, calculated the same as for btrees.
7392  */
7393  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7394  costs.indexStartupCost += descentCost;
7395  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7396 
7397  *indexStartupCost = costs.indexStartupCost;
7398  *indexTotalCost = costs.indexTotalCost;
7399  *indexSelectivity = costs.indexSelectivity;
7400  *indexCorrelation = costs.indexCorrelation;
7401  *indexPages = costs.numIndexPages;
7402 }
Selectivity indexSelectivity
Definition: selfuncs.h:134
IndexOptInfo * indexinfo
Definition: relation.h:1155
#define MemSet(start, val, len)
Definition: c.h:908
double tuples
Definition: relation.h:759
int tree_height
Definition: relation.h:760
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6552
Definition: type.h:89
BlockNumber pages
Definition: relation.h:758
double num_sa_scans
Definition: selfuncs.h:141
double cpu_operator_cost
Definition: costsize.c:115
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:647
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6701
double numIndexPages
Definition: selfuncs.h:138