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

References Abs, AccessShareLock, Assert, 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(), STATISTIC_KIND_CORRELATION, STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

7964 {
7965  IndexOptInfo *index = path->indexinfo;
7966  List *indexQuals = path->indexquals;
7967  double numPages = index->pages;
7968  RelOptInfo *baserel = index->rel;
7969  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7970  List *qinfos;
7971  Cost spc_seq_page_cost;
7972  Cost spc_random_page_cost;
7973  double qual_arg_cost;
7974  double qualSelectivity;
7975  BrinStatsData statsData;
7976  double indexRanges;
7977  double minimalRanges;
7978  double estimatedRanges;
7979  double selec;
7980  Relation indexRel;
7981  ListCell *l;
7982  VariableStatData vardata;
7983 
7984  Assert(rte->rtekind == RTE_RELATION);
7985 
7986  /* fetch estimated page cost for the tablespace containing the index */
7988  &spc_random_page_cost,
7989  &spc_seq_page_cost);
7990 
7991  /*
7992  * Obtain some data from the index itself.
7993  */
7994  indexRel = index_open(index->indexoid, AccessShareLock);
7995  brinGetStats(indexRel, &statsData);
7996  index_close(indexRel, AccessShareLock);
7997 
7998  /*
7999  * Compute index correlation
8000  *
8001  * Because we can use all index quals equally when scanning, we can use
8002  * the largest correlation (in absolute value) among columns used by the
8003  * query. Start at zero, the worst possible case. If we cannot find any
8004  * correlation statistics, we will keep it as 0.
8005  */
8006  *indexCorrelation = 0;
8007 
8008  qinfos = deconstruct_indexquals(path);
8009  foreach(l, qinfos)
8010  {
8011  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
8012  AttrNumber attnum = index->indexkeys[qinfo->indexcol];
8013 
8014  /* attempt to lookup stats in relation for this index column */
8015  if (attnum != 0)
8016  {
8017  /* Simple variable -- look to stats for the underlying table */
8019  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
8020  {
8021  /*
8022  * The hook took control of acquiring a stats tuple. If it
8023  * did supply a tuple, it'd better have supplied a freefunc.
8024  */
8025  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
8026  elog(ERROR,
8027  "no function provided to release variable stats with");
8028  }
8029  else
8030  {
8031  vardata.statsTuple =
8033  ObjectIdGetDatum(rte->relid),
8034  Int16GetDatum(attnum),
8035  BoolGetDatum(false));
8036  vardata.freefunc = ReleaseSysCache;
8037  }
8038  }
8039  else
8040  {
8041  /*
8042  * Looks like we've found an expression column in the index. Let's
8043  * see if there's any stats for it.
8044  */
8045 
8046  /* get the attnum from the 0-based index. */
8047  attnum = qinfo->indexcol + 1;
8048 
8049  if (get_index_stats_hook &&
8050  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
8051  {
8052  /*
8053  * The hook took control of acquiring a stats tuple. If it
8054  * did supply a tuple, it'd better have supplied a freefunc.
8055  */
8056  if (HeapTupleIsValid(vardata.statsTuple) &&
8057  !vardata.freefunc)
8058  elog(ERROR, "no function provided to release variable stats with");
8059  }
8060  else
8061  {
8063  ObjectIdGetDatum(index->indexoid),
8064  Int16GetDatum(attnum),
8065  BoolGetDatum(false));
8066  vardata.freefunc = ReleaseSysCache;
8067  }
8068  }
8069 
8070  if (HeapTupleIsValid(vardata.statsTuple))
8071  {
8072  AttStatsSlot sslot;
8073 
8074  if (get_attstatsslot(&sslot, vardata.statsTuple,
8077  {
8078  double varCorrelation = 0.0;
8079 
8080  if (sslot.nnumbers > 0)
8081  varCorrelation = Abs(sslot.numbers[0]);
8082 
8083  if (varCorrelation > *indexCorrelation)
8084  *indexCorrelation = varCorrelation;
8085 
8086  free_attstatsslot(&sslot);
8087  }
8088  }
8089 
8090  ReleaseVariableStats(vardata);
8091  }
8092 
8093  qualSelectivity = clauselist_selectivity(root, indexQuals,
8094  baserel->relid,
8095  JOIN_INNER, NULL);
8096 
8097  /* work out the actual number of ranges in the index */
8098  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
8099  1.0);
8100 
8101  /*
8102  * Now calculate the minimum possible ranges we could match with if all of
8103  * the rows were in the perfect order in the table's heap.
8104  */
8105  minimalRanges = ceil(indexRanges * qualSelectivity);
8106 
8107  /*
8108  * Now estimate the number of ranges that we'll touch by using the
8109  * indexCorrelation from the stats. Careful not to divide by zero (note
8110  * we're using the absolute value of the correlation).
8111  */
8112  if (*indexCorrelation < 1.0e-10)
8113  estimatedRanges = indexRanges;
8114  else
8115  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
8116 
8117  /* we expect to visit this portion of the table */
8118  selec = estimatedRanges / indexRanges;
8119 
8120  CLAMP_PROBABILITY(selec);
8121 
8122  *indexSelectivity = selec;
8123 
8124  /*
8125  * Compute the index qual costs, much as in genericcostestimate, to add to
8126  * the index costs.
8127  */
8128  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
8129  orderby_operands_eval_cost(root, path);
8130 
8131  /*
8132  * Compute the startup cost as the cost to read the whole revmap
8133  * sequentially, including the cost to execute the index quals.
8134  */
8135  *indexStartupCost =
8136  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8137  *indexStartupCost += qual_arg_cost;
8138 
8139  /*
8140  * To read a BRIN index there might be a bit of back and forth over
8141  * regular pages, as revmap might point to them out of sequential order;
8142  * calculate the total cost as reading the whole index in random order.
8143  */
8144  *indexTotalCost = *indexStartupCost +
8145  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8146 
8147  /*
8148  * Charge a small amount per range tuple which we expect to match to. This
8149  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8150  * will set a bit for each page in the range when we find a matching
8151  * range, so we must multiply the charge by the number of pages in the
8152  * range.
8153  */
8154  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8155  statsData.pagesPerRange;
8156 
8157  *indexPages = index->pages;
8158 }
IndexOptInfo * indexinfo
Definition: relation.h:1123
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
#define Min(x, y)
Definition: c.h:846
#define Int16GetDatum(X)
Definition: postgres.h:434
#define AccessShareLock
Definition: lockdefs.h:36
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
Oid reltablespace
Definition: relation.h:724
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6585
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6490
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6610
#define Abs(x)
Definition: c.h:852
Definition: type.h:89
BlockNumber pages
Definition: relation.h:728
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
List * indexquals
Definition: relation.h:1125
RelOptInfo * rel
Definition: relation.h:725
#define planner_rt_fetch(rti, root)
Definition: relation.h:328
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:490
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1134
#define STATISTIC_KIND_CORRELATION
Definition: pg_statistic.h:231
float4 * numbers
Definition: lsyscache.h:52
double cpu_operator_cost
Definition: costsize.c:108
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:613
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1160
#define BoolGetDatum(X)
Definition: postgres.h:385
#define InvalidOid
Definition: postgres_ext.h:36
BlockNumber pagesPerRange
Definition: brin.h:34
#define Max(x, y)
Definition: c.h:840
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
BlockNumber pages
Definition: relation.h:624
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2913
#define Assert(condition)
Definition: c.h:688
#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:177
RTEKind rtekind
Definition: parsenodes.h:959
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
int * indexkeys
Definition: relation.h:734
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:723
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:151
double Cost
Definition: nodes.h:644
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1066
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 6880 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, 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(), STATISTIC_KIND_CORRELATION, STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

6884 {
6885  IndexOptInfo *index = path->indexinfo;
6886  List *qinfos;
6887  GenericCosts costs;
6888  Oid relid;
6889  AttrNumber colnum;
6890  VariableStatData vardata;
6891  double numIndexTuples;
6892  Cost descentCost;
6893  List *indexBoundQuals;
6894  int indexcol;
6895  bool eqQualHere;
6896  bool found_saop;
6897  bool found_is_null_op;
6898  double num_sa_scans;
6899  ListCell *lc;
6900 
6901  /* Do preliminary analysis of indexquals */
6902  qinfos = deconstruct_indexquals(path);
6903 
6904  /*
6905  * For a btree scan, only leading '=' quals plus inequality quals for the
6906  * immediately next attribute contribute to index selectivity (these are
6907  * the "boundary quals" that determine the starting and stopping points of
6908  * the index scan). Additional quals can suppress visits to the heap, so
6909  * it's OK to count them in indexSelectivity, but they should not count
6910  * for estimating numIndexTuples. So we must examine the given indexquals
6911  * to find out which ones count as boundary quals. We rely on the
6912  * knowledge that they are given in index column order.
6913  *
6914  * For a RowCompareExpr, we consider only the first column, just as
6915  * rowcomparesel() does.
6916  *
6917  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6918  * index scans not one, but the ScalarArrayOpExpr's operator can be
6919  * considered to act the same as it normally does.
6920  */
6921  indexBoundQuals = NIL;
6922  indexcol = 0;
6923  eqQualHere = false;
6924  found_saop = false;
6925  found_is_null_op = false;
6926  num_sa_scans = 1;
6927  foreach(lc, qinfos)
6928  {
6929  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
6930  RestrictInfo *rinfo = qinfo->rinfo;
6931  Expr *clause = rinfo->clause;
6932  Oid clause_op;
6933  int op_strategy;
6934 
6935  if (indexcol != qinfo->indexcol)
6936  {
6937  /* Beginning of a new column's quals */
6938  if (!eqQualHere)
6939  break; /* done if no '=' qual for indexcol */
6940  eqQualHere = false;
6941  indexcol++;
6942  if (indexcol != qinfo->indexcol)
6943  break; /* no quals at all for indexcol */
6944  }
6945 
6946  if (IsA(clause, ScalarArrayOpExpr))
6947  {
6948  int alength = estimate_array_length(qinfo->other_operand);
6949 
6950  found_saop = true;
6951  /* count up number of SA scans induced by indexBoundQuals only */
6952  if (alength > 1)
6953  num_sa_scans *= alength;
6954  }
6955  else if (IsA(clause, NullTest))
6956  {
6957  NullTest *nt = (NullTest *) clause;
6958 
6959  if (nt->nulltesttype == IS_NULL)
6960  {
6961  found_is_null_op = true;
6962  /* IS NULL is like = for selectivity determination purposes */
6963  eqQualHere = true;
6964  }
6965  }
6966 
6967  /*
6968  * We would need to commute the clause_op if not varonleft, except
6969  * that we only care if it's equality or not, so that refinement is
6970  * unnecessary.
6971  */
6972  clause_op = qinfo->clause_op;
6973 
6974  /* check for equality operator */
6975  if (OidIsValid(clause_op))
6976  {
6977  op_strategy = get_op_opfamily_strategy(clause_op,
6978  index->opfamily[indexcol]);
6979  Assert(op_strategy != 0); /* not a member of opfamily?? */
6980  if (op_strategy == BTEqualStrategyNumber)
6981  eqQualHere = true;
6982  }
6983 
6984  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6985  }
6986 
6987  /*
6988  * If index is unique and we found an '=' clause for each column, we can
6989  * just assume numIndexTuples = 1 and skip the expensive
6990  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6991  * NullTest invalidates that theory, even though it sets eqQualHere.
6992  */
6993  if (index->unique &&
6994  indexcol == index->ncolumns - 1 &&
6995  eqQualHere &&
6996  !found_saop &&
6997  !found_is_null_op)
6998  numIndexTuples = 1.0;
6999  else
7000  {
7001  List *selectivityQuals;
7002  Selectivity btreeSelectivity;
7003 
7004  /*
7005  * If the index is partial, AND the index predicate with the
7006  * index-bound quals to produce a more accurate idea of the number of
7007  * rows covered by the bound conditions.
7008  */
7009  selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
7010 
7011  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
7012  index->rel->relid,
7013  JOIN_INNER,
7014  NULL);
7015  numIndexTuples = btreeSelectivity * index->rel->tuples;
7016 
7017  /*
7018  * As in genericcostestimate(), we have to adjust for any
7019  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
7020  * to integer.
7021  */
7022  numIndexTuples = rint(numIndexTuples / num_sa_scans);
7023  }
7024 
7025  /*
7026  * Now do generic index cost estimation.
7027  */
7028  MemSet(&costs, 0, sizeof(costs));
7029  costs.numIndexTuples = numIndexTuples;
7030 
7031  genericcostestimate(root, path, loop_count, qinfos, &costs);
7032 
7033  /*
7034  * Add a CPU-cost component to represent the costs of initial btree
7035  * descent. We don't charge any I/O cost for touching upper btree levels,
7036  * since they tend to stay in cache, but we still have to do about log2(N)
7037  * comparisons to descend a btree of N leaf tuples. We charge one
7038  * cpu_operator_cost per comparison.
7039  *
7040  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
7041  * ones after the first one are not startup cost so far as the overall
7042  * plan is concerned, so add them only to "total" cost.
7043  */
7044  if (index->tuples > 1) /* avoid computing log(0) */
7045  {
7046  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
7047  costs.indexStartupCost += descentCost;
7048  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7049  }
7050 
7051  /*
7052  * Even though we're not charging I/O cost for touching upper btree pages,
7053  * it's still reasonable to charge some CPU cost per page descended
7054  * through. Moreover, if we had no such charge at all, bloated indexes
7055  * would appear to have the same search cost as unbloated ones, at least
7056  * in cases where only a single leaf page is expected to be visited. This
7057  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
7058  * touched. The number of such pages is btree tree height plus one (ie,
7059  * we charge for the leaf page too). As above, charge once per SA scan.
7060  */
7061  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7062  costs.indexStartupCost += descentCost;
7063  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7064 
7065  /*
7066  * If we can get an estimate of the first column's ordering correlation C
7067  * from pg_statistic, estimate the index correlation as C for a
7068  * single-column index, or C * 0.75 for multiple columns. (The idea here
7069  * is that multiple columns dilute the importance of the first column's
7070  * ordering, but don't negate it entirely. Before 8.0 we divided the
7071  * correlation by the number of columns, but that seems too strong.)
7072  */
7073  MemSet(&vardata, 0, sizeof(vardata));
7074 
7075  if (index->indexkeys[0] != 0)
7076  {
7077  /* Simple variable --- look to stats for the underlying table */
7078  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
7079 
7080  Assert(rte->rtekind == RTE_RELATION);
7081  relid = rte->relid;
7082  Assert(relid != InvalidOid);
7083  colnum = index->indexkeys[0];
7084 
7086  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
7087  {
7088  /*
7089  * The hook took control of acquiring a stats tuple. If it did
7090  * supply a tuple, it'd better have supplied a freefunc.
7091  */
7092  if (HeapTupleIsValid(vardata.statsTuple) &&
7093  !vardata.freefunc)
7094  elog(ERROR, "no function provided to release variable stats with");
7095  }
7096  else
7097  {
7099  ObjectIdGetDatum(relid),
7100  Int16GetDatum(colnum),
7101  BoolGetDatum(rte->inh));
7102  vardata.freefunc = ReleaseSysCache;
7103  }
7104  }
7105  else
7106  {
7107  /* Expression --- maybe there are stats for the index itself */
7108  relid = index->indexoid;
7109  colnum = 1;
7110 
7111  if (get_index_stats_hook &&
7112  (*get_index_stats_hook) (root, relid, colnum, &vardata))
7113  {
7114  /*
7115  * The hook took control of acquiring a stats tuple. If it did
7116  * supply a tuple, it'd better have supplied a freefunc.
7117  */
7118  if (HeapTupleIsValid(vardata.statsTuple) &&
7119  !vardata.freefunc)
7120  elog(ERROR, "no function provided to release variable stats with");
7121  }
7122  else
7123  {
7125  ObjectIdGetDatum(relid),
7126  Int16GetDatum(colnum),
7127  BoolGetDatum(false));
7128  vardata.freefunc = ReleaseSysCache;
7129  }
7130  }
7131 
7132  if (HeapTupleIsValid(vardata.statsTuple))
7133  {
7134  Oid sortop;
7135  AttStatsSlot sslot;
7136 
7137  sortop = get_opfamily_member(index->opfamily[0],
7138  index->opcintype[0],
7139  index->opcintype[0],
7141  if (OidIsValid(sortop) &&
7142  get_attstatsslot(&sslot, vardata.statsTuple,
7145  {
7146  double varCorrelation;
7147 
7148  Assert(sslot.nnumbers == 1);
7149  varCorrelation = sslot.numbers[0];
7150 
7151  if (index->reverse_sort[0])
7152  varCorrelation = -varCorrelation;
7153 
7154  if (index->ncolumns > 1)
7155  costs.indexCorrelation = varCorrelation * 0.75;
7156  else
7157  costs.indexCorrelation = varCorrelation;
7158 
7159  free_attstatsslot(&sslot);
7160  }
7161  }
7162 
7163  ReleaseVariableStats(vardata);
7164 
7165  *indexStartupCost = costs.indexStartupCost;
7166  *indexTotalCost = costs.indexTotalCost;
7167  *indexSelectivity = costs.indexSelectivity;
7168  *indexCorrelation = costs.indexCorrelation;
7169  *indexPages = costs.numIndexPages;
7170 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:564
IndexOptInfo * indexinfo
Definition: relation.h:1123
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
double tuples
Definition: relation.h:625
static List * add_predicate_to_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6858
#define Int16GetDatum(X)
Definition: postgres.h:434
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
#define MemSet(start, val, len)
Definition: c.h:897
double Selectivity
Definition: nodes.h:643
double tuples
Definition: relation.h:729
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: relation.h:730
#define OidIsValid(objectId)
Definition: c.h:594
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6490
bool unique
Definition: relation.h:757
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2167
RelOptInfo * rel
Definition: relation.h:725
#define planner_rt_fetch(rti, root)
Definition: relation.h:328
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:490
#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:138
#define STATISTIC_KIND_CORRELATION
Definition: pg_statistic.h:231
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:108
Cost indexTotalCost
Definition: selfuncs.h:130
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:733
Index relid
Definition: relation.h:613
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1847
double indexCorrelation
Definition: selfuncs.h:132
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1160
NullTestType nulltesttype
Definition: primnodes.h:1188
#define BoolGetDatum(X)
Definition: postgres.h:385
#define InvalidOid
Definition: postgres_ext.h:36
double numIndexTuples
Definition: selfuncs.h:136
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2913
#define Assert(condition)
Definition: c.h:688
#define lfirst(lc)
Definition: pg_list.h:106
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:156
Oid * opcintype
Definition: relation.h:737
Cost indexStartupCost
Definition: selfuncs.h:129
Oid * opfamily
Definition: relation.h:736
RTEKind rtekind
Definition: parsenodes.h:959
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:110
int * indexkeys
Definition: relation.h:734
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:723
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
bool * reverse_sort
Definition: relation.h:739
#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:644
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6639
double numIndexPages
Definition: selfuncs.h:135
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 7635 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().

7639 {
7640  IndexOptInfo *index = path->indexinfo;
7641  List *indexQuals = path->indexquals;
7642  List *indexOrderBys = path->indexorderbys;
7643  List *qinfos;
7644  ListCell *l;
7645  List *selectivityQuals;
7646  double numPages = index->pages,
7647  numTuples = index->tuples;
7648  double numEntryPages,
7649  numDataPages,
7650  numPendingPages,
7651  numEntries;
7652  GinQualCounts counts;
7653  bool matchPossible;
7654  double partialScale;
7655  double entryPagesFetched,
7656  dataPagesFetched,
7657  dataPagesFetchedBySel;
7658  double qual_op_cost,
7659  qual_arg_cost,
7660  spc_random_page_cost,
7661  outer_scans;
7662  Relation indexRel;
7663  GinStatsData ginStats;
7664 
7665  /* Do preliminary analysis of indexquals */
7666  qinfos = deconstruct_indexquals(path);
7667 
7668  /*
7669  * Obtain statistical information from the meta page, if possible. Else
7670  * set ginStats to zeroes, and we'll cope below.
7671  */
7672  if (!index->hypothetical)
7673  {
7674  indexRel = index_open(index->indexoid, AccessShareLock);
7675  ginGetStats(indexRel, &ginStats);
7676  index_close(indexRel, AccessShareLock);
7677  }
7678  else
7679  {
7680  memset(&ginStats, 0, sizeof(ginStats));
7681  }
7682 
7683  /*
7684  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7685  * trusted, but the other fields are data as of the last VACUUM. We can
7686  * scale them up to account for growth since then, but that method only
7687  * goes so far; in the worst case, the stats might be for a completely
7688  * empty index, and scaling them will produce pretty bogus numbers.
7689  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7690  * it's grown more than that, fall back to estimating things only from the
7691  * assumed-accurate index size. But we'll trust nPendingPages in any case
7692  * so long as it's not clearly insane, ie, more than the index size.
7693  */
7694  if (ginStats.nPendingPages < numPages)
7695  numPendingPages = ginStats.nPendingPages;
7696  else
7697  numPendingPages = 0;
7698 
7699  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7700  ginStats.nTotalPages > numPages / 4 &&
7701  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7702  {
7703  /*
7704  * OK, the stats seem close enough to sane to be trusted. But we
7705  * still need to scale them by the ratio numPages / nTotalPages to
7706  * account for growth since the last VACUUM.
7707  */
7708  double scale = numPages / ginStats.nTotalPages;
7709 
7710  numEntryPages = ceil(ginStats.nEntryPages * scale);
7711  numDataPages = ceil(ginStats.nDataPages * scale);
7712  numEntries = ceil(ginStats.nEntries * scale);
7713  /* ensure we didn't round up too much */
7714  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7715  numDataPages = Min(numDataPages,
7716  numPages - numPendingPages - numEntryPages);
7717  }
7718  else
7719  {
7720  /*
7721  * We might get here because it's a hypothetical index, or an index
7722  * created pre-9.1 and never vacuumed since upgrading (in which case
7723  * its stats would read as zeroes), or just because it's grown too
7724  * much since the last VACUUM for us to put our faith in scaling.
7725  *
7726  * Invent some plausible internal statistics based on the index page
7727  * count (and clamp that to at least 10 pages, just in case). We
7728  * estimate that 90% of the index is entry pages, and the rest is data
7729  * pages. Estimate 100 entries per entry page; this is rather bogus
7730  * since it'll depend on the size of the keys, but it's more robust
7731  * than trying to predict the number of entries per heap tuple.
7732  */
7733  numPages = Max(numPages, 10);
7734  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7735  numDataPages = numPages - numPendingPages - numEntryPages;
7736  numEntries = floor(numEntryPages * 100);
7737  }
7738 
7739  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7740  if (numEntries < 1)
7741  numEntries = 1;
7742 
7743  /*
7744  * Include predicate in selectivityQuals (should match
7745  * genericcostestimate)
7746  */
7747  if (index->indpred != NIL)
7748  {
7749  List *predExtraQuals = NIL;
7750 
7751  foreach(l, index->indpred)
7752  {
7753  Node *predQual = (Node *) lfirst(l);
7754  List *oneQual = list_make1(predQual);
7755 
7756  if (!predicate_implied_by(oneQual, indexQuals, false))
7757  predExtraQuals = list_concat(predExtraQuals, oneQual);
7758  }
7759  /* list_concat avoids modifying the passed-in indexQuals list */
7760  selectivityQuals = list_concat(predExtraQuals, indexQuals);
7761  }
7762  else
7763  selectivityQuals = indexQuals;
7764 
7765  /* Estimate the fraction of main-table tuples that will be visited */
7766  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7767  index->rel->relid,
7768  JOIN_INNER,
7769  NULL);
7770 
7771  /* fetch estimated page cost for tablespace containing index */
7773  &spc_random_page_cost,
7774  NULL);
7775 
7776  /*
7777  * Generic assumption about index correlation: there isn't any.
7778  */
7779  *indexCorrelation = 0.0;
7780 
7781  /*
7782  * Examine quals to estimate number of search entries & partial matches
7783  */
7784  memset(&counts, 0, sizeof(counts));
7785  counts.arrayScans = 1;
7786  matchPossible = true;
7787 
7788  foreach(l, qinfos)
7789  {
7790  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7791  Expr *clause = qinfo->rinfo->clause;
7792 
7793  if (IsA(clause, OpExpr))
7794  {
7795  matchPossible = gincost_opexpr(root,
7796  index,
7797  qinfo,
7798  &counts);
7799  if (!matchPossible)
7800  break;
7801  }
7802  else if (IsA(clause, ScalarArrayOpExpr))
7803  {
7804  matchPossible = gincost_scalararrayopexpr(root,
7805  index,
7806  qinfo,
7807  numEntries,
7808  &counts);
7809  if (!matchPossible)
7810  break;
7811  }
7812  else
7813  {
7814  /* shouldn't be anything else for a GIN index */
7815  elog(ERROR, "unsupported GIN indexqual type: %d",
7816  (int) nodeTag(clause));
7817  }
7818  }
7819 
7820  /* Fall out if there were any provably-unsatisfiable quals */
7821  if (!matchPossible)
7822  {
7823  *indexStartupCost = 0;
7824  *indexTotalCost = 0;
7825  *indexSelectivity = 0;
7826  return;
7827  }
7828 
7829  if (counts.haveFullScan || indexQuals == NIL)
7830  {
7831  /*
7832  * Full index scan will be required. We treat this as if every key in
7833  * the index had been listed in the query; is that reasonable?
7834  */
7835  counts.partialEntries = 0;
7836  counts.exactEntries = numEntries;
7837  counts.searchEntries = numEntries;
7838  }
7839 
7840  /* Will we have more than one iteration of a nestloop scan? */
7841  outer_scans = loop_count;
7842 
7843  /*
7844  * Compute cost to begin scan, first of all, pay attention to pending
7845  * list.
7846  */
7847  entryPagesFetched = numPendingPages;
7848 
7849  /*
7850  * Estimate number of entry pages read. We need to do
7851  * counts.searchEntries searches. Use a power function as it should be,
7852  * but tuples on leaf pages usually is much greater. Here we include all
7853  * searches in entry tree, including search of first entry in partial
7854  * match algorithm
7855  */
7856  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7857 
7858  /*
7859  * Add an estimate of entry pages read by partial match algorithm. It's a
7860  * scan over leaf pages in entry tree. We haven't any useful stats here,
7861  * so estimate it as proportion. Because counts.partialEntries is really
7862  * pretty bogus (see code above), it's possible that it is more than
7863  * numEntries; clamp the proportion to ensure sanity.
7864  */
7865  partialScale = counts.partialEntries / numEntries;
7866  partialScale = Min(partialScale, 1.0);
7867 
7868  entryPagesFetched += ceil(numEntryPages * partialScale);
7869 
7870  /*
7871  * Partial match algorithm reads all data pages before doing actual scan,
7872  * so it's a startup cost. Again, we haven't any useful stats here, so
7873  * estimate it as proportion.
7874  */
7875  dataPagesFetched = ceil(numDataPages * partialScale);
7876 
7877  /*
7878  * Calculate cache effects if more than one scan due to nestloops or array
7879  * quals. The result is pro-rated per nestloop scan, but the array qual
7880  * factor shouldn't be pro-rated (compare genericcostestimate).
7881  */
7882  if (outer_scans > 1 || counts.arrayScans > 1)
7883  {
7884  entryPagesFetched *= outer_scans * counts.arrayScans;
7885  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7886  (BlockNumber) numEntryPages,
7887  numEntryPages, root);
7888  entryPagesFetched /= outer_scans;
7889  dataPagesFetched *= outer_scans * counts.arrayScans;
7890  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7891  (BlockNumber) numDataPages,
7892  numDataPages, root);
7893  dataPagesFetched /= outer_scans;
7894  }
7895 
7896  /*
7897  * Here we use random page cost because logically-close pages could be far
7898  * apart on disk.
7899  */
7900  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7901 
7902  /*
7903  * Now compute the number of data pages fetched during the scan.
7904  *
7905  * We assume every entry to have the same number of items, and that there
7906  * is no overlap between them. (XXX: tsvector and array opclasses collect
7907  * statistics on the frequency of individual keys; it would be nice to use
7908  * those here.)
7909  */
7910  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7911 
7912  /*
7913  * If there is a lot of overlap among the entries, in particular if one of
7914  * the entries is very frequent, the above calculation can grossly
7915  * under-estimate. As a simple cross-check, calculate a lower bound based
7916  * on the overall selectivity of the quals. At a minimum, we must read
7917  * one item pointer for each matching entry.
7918  *
7919  * The width of each item pointer varies, based on the level of
7920  * compression. We don't have statistics on that, but an average of
7921  * around 3 bytes per item is fairly typical.
7922  */
7923  dataPagesFetchedBySel = ceil(*indexSelectivity *
7924  (numTuples / (BLCKSZ / 3)));
7925  if (dataPagesFetchedBySel > dataPagesFetched)
7926  dataPagesFetched = dataPagesFetchedBySel;
7927 
7928  /* Account for cache effects, the same as above */
7929  if (outer_scans > 1 || counts.arrayScans > 1)
7930  {
7931  dataPagesFetched *= outer_scans * counts.arrayScans;
7932  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7933  (BlockNumber) numDataPages,
7934  numDataPages, root);
7935  dataPagesFetched /= outer_scans;
7936  }
7937 
7938  /* And apply random_page_cost as the cost per page */
7939  *indexTotalCost = *indexStartupCost +
7940  dataPagesFetched * spc_random_page_cost;
7941 
7942  /*
7943  * Add on index qual eval costs, much as in genericcostestimate
7944  */
7945  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7946  orderby_operands_eval_cost(root, path);
7947  qual_op_cost = cpu_operator_cost *
7948  (list_length(indexQuals) + list_length(indexOrderBys));
7949 
7950  *indexStartupCost += qual_arg_cost;
7951  *indexTotalCost += qual_arg_cost;
7952  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7953  *indexPages = dataPagesFetched;
7954 }
#define NIL
Definition: pg_list.h:69
bool predicate_implied_by(List *predicate_list, List *clause_list, bool clause_is_check)
Definition: predtest.c:135
BlockNumber nEntryPages
Definition: gin.h:45
#define IsA(nodeptr, _type_)
Definition: nodes.h:564
IndexOptInfo * indexinfo
Definition: relation.h:1123
#define Min(x, y)
Definition: c.h:846
#define AccessShareLock
Definition: lockdefs.h:36
double partialEntries
Definition: selfuncs.c:7350
Definition: nodes.h:513
double searchEntries
Definition: selfuncs.c:7352
Oid reltablespace
Definition: relation.h:724
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6585
int scale
Definition: pgbench.c:111
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:759
double tuples
Definition: relation.h:729
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6490
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6610
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:7351
BlockNumber pages
Definition: relation.h:728
#define list_make1(x1)
Definition: pg_list.h:139
List * indexquals
Definition: relation.h:1125
RelOptInfo * rel
Definition: relation.h:725
#define ERROR
Definition: elog.h:43
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7520
bool haveFullScan
Definition: selfuncs.c:7349
double cpu_operator_cost
Definition: costsize.c:108
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:613
Expr * clause
Definition: relation.h:1847
BlockNumber nPendingPages
Definition: gin.h:43
double arrayScans
Definition: selfuncs.c:7353
List * indexorderbys
Definition: relation.h:1127
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:640
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, GinQualCounts *counts)
Definition: selfuncs.c:7464
BlockNumber nDataPages
Definition: gin.h:46
#define Max(x, y)
Definition: c.h:840
#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:518
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:177
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:723
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
List * indpred
Definition: relation.h:746
Definition: pg_list.h:45
double cpu_index_tuple_cost
Definition: costsize.c:107
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:151
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:820

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

7225 {
7226  IndexOptInfo *index = path->indexinfo;
7227  List *qinfos;
7228  GenericCosts costs;
7229  Cost descentCost;
7230 
7231  /* Do preliminary analysis of indexquals */
7232  qinfos = deconstruct_indexquals(path);
7233 
7234  MemSet(&costs, 0, sizeof(costs));
7235 
7236  genericcostestimate(root, path, loop_count, qinfos, &costs);
7237 
7238  /*
7239  * We model index descent costs similarly to those for btree, but to do
7240  * that we first need an idea of the tree height. We somewhat arbitrarily
7241  * assume that the fanout is 100, meaning the tree height is at most
7242  * log100(index->pages).
7243  *
7244  * Although this computation isn't really expensive enough to require
7245  * caching, we might as well use index->tree_height to cache it.
7246  */
7247  if (index->tree_height < 0) /* unknown? */
7248  {
7249  if (index->pages > 1) /* avoid computing log(0) */
7250  index->tree_height = (int) (log(index->pages) / log(100.0));
7251  else
7252  index->tree_height = 0;
7253  }
7254 
7255  /*
7256  * Add a CPU-cost component to represent the costs of initial descent. We
7257  * just use log(N) here not log2(N) since the branching factor isn't
7258  * necessarily two anyway. As for btree, charge once per SA scan.
7259  */
7260  if (index->tuples > 1) /* avoid computing log(0) */
7261  {
7262  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7263  costs.indexStartupCost += descentCost;
7264  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7265  }
7266 
7267  /*
7268  * Likewise add a per-page charge, calculated the same as for btrees.
7269  */
7270  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7271  costs.indexStartupCost += descentCost;
7272  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7273 
7274  *indexStartupCost = costs.indexStartupCost;
7275  *indexTotalCost = costs.indexTotalCost;
7276  *indexSelectivity = costs.indexSelectivity;
7277  *indexCorrelation = costs.indexCorrelation;
7278  *indexPages = costs.numIndexPages;
7279 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
IndexOptInfo * indexinfo
Definition: relation.h:1123
#define MemSet(start, val, len)
Definition: c.h:897
double tuples
Definition: relation.h:729
int tree_height
Definition: relation.h:730
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6490
Definition: type.h:89
BlockNumber pages
Definition: relation.h:728
double num_sa_scans
Definition: selfuncs.h:138
double cpu_operator_cost
Definition: costsize.c:108
Cost indexTotalCost
Definition: selfuncs.h:130
double indexCorrelation
Definition: selfuncs.h:132
Cost indexStartupCost
Definition: selfuncs.h:129
Definition: pg_list.h:45
double Cost
Definition: nodes.h:644
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6639
double numIndexPages
Definition: selfuncs.h:135

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

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

Referenced by hashhandler().

7177 {
7178  List *qinfos;
7179  GenericCosts costs;
7180 
7181  /* Do preliminary analysis of indexquals */
7182  qinfos = deconstruct_indexquals(path);
7183 
7184  MemSet(&costs, 0, sizeof(costs));
7185 
7186  genericcostestimate(root, path, loop_count, qinfos, &costs);
7187 
7188  /*
7189  * A hash index has no descent costs as such, since the index AM can go
7190  * directly to the target bucket after computing the hash value. There
7191  * are a couple of other hash-specific costs that we could conceivably add
7192  * here, though:
7193  *
7194  * Ideally we'd charge spc_random_page_cost for each page in the target
7195  * bucket, not just the numIndexPages pages that genericcostestimate
7196  * thought we'd visit. However in most cases we don't know which bucket
7197  * that will be. There's no point in considering the average bucket size
7198  * because the hash AM makes sure that's always one page.
7199  *
7200  * Likewise, we could consider charging some CPU for each index tuple in
7201  * the bucket, if we knew how many there were. But the per-tuple cost is
7202  * just a hash value comparison, not a general datatype-dependent
7203  * comparison, so any such charge ought to be quite a bit less than
7204  * cpu_operator_cost; which makes it probably not worth worrying about.
7205  *
7206  * A bigger issue is that chance hash-value collisions will result in
7207  * wasted probes into the heap. We don't currently attempt to model this
7208  * cost on the grounds that it's rare, but maybe it's not rare enough.
7209  * (Any fix for this ought to consider the generic lossy-operator problem,
7210  * though; it's not entirely hash-specific.)
7211  */
7212 
7213  *indexStartupCost = costs.indexStartupCost;
7214  *indexTotalCost = costs.indexTotalCost;
7215  *indexSelectivity = costs.indexSelectivity;
7216  *indexCorrelation = costs.indexCorrelation;
7217  *indexPages = costs.numIndexPages;
7218 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
#define MemSet(start, val, len)
Definition: c.h:897
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6490
Cost indexTotalCost
Definition: selfuncs.h:130
double indexCorrelation
Definition: selfuncs.h:132
Cost indexStartupCost
Definition: selfuncs.h:129
Definition: pg_list.h:45
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6639
double numIndexPages
Definition: selfuncs.h:135

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

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