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

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

Referenced by brinhandler().

6832 {
6833  IndexOptInfo *index = path->indexinfo;
6834  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
6835  double numPages = index->pages;
6836  RelOptInfo *baserel = index->rel;
6837  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
6838  Cost spc_seq_page_cost;
6839  Cost spc_random_page_cost;
6840  double qual_arg_cost;
6841  double qualSelectivity;
6842  BrinStatsData statsData;
6843  double indexRanges;
6844  double minimalRanges;
6845  double estimatedRanges;
6846  double selec;
6847  Relation indexRel;
6848  ListCell *l;
6849  VariableStatData vardata;
6850 
6851  Assert(rte->rtekind == RTE_RELATION);
6852 
6853  /* fetch estimated page cost for the tablespace containing the index */
6855  &spc_random_page_cost,
6856  &spc_seq_page_cost);
6857 
6858  /*
6859  * Obtain some data from the index itself. A lock should have already
6860  * been obtained on the index in plancat.c.
6861  */
6862  indexRel = index_open(index->indexoid, NoLock);
6863  brinGetStats(indexRel, &statsData);
6864  index_close(indexRel, NoLock);
6865 
6866  /*
6867  * Compute index correlation
6868  *
6869  * Because we can use all index quals equally when scanning, we can use
6870  * the largest correlation (in absolute value) among columns used by the
6871  * query. Start at zero, the worst possible case. If we cannot find any
6872  * correlation statistics, we will keep it as 0.
6873  */
6874  *indexCorrelation = 0;
6875 
6876  foreach(l, path->indexclauses)
6877  {
6878  IndexClause *iclause = lfirst_node(IndexClause, l);
6879  AttrNumber attnum = index->indexkeys[iclause->indexcol];
6880 
6881  /* attempt to lookup stats in relation for this index column */
6882  if (attnum != 0)
6883  {
6884  /* Simple variable -- look to stats for the underlying table */
6886  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
6887  {
6888  /*
6889  * The hook took control of acquiring a stats tuple. If it
6890  * did supply a tuple, it'd better have supplied a freefunc.
6891  */
6892  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
6893  elog(ERROR,
6894  "no function provided to release variable stats with");
6895  }
6896  else
6897  {
6898  vardata.statsTuple =
6900  ObjectIdGetDatum(rte->relid),
6901  Int16GetDatum(attnum),
6902  BoolGetDatum(false));
6903  vardata.freefunc = ReleaseSysCache;
6904  }
6905  }
6906  else
6907  {
6908  /*
6909  * Looks like we've found an expression column in the index. Let's
6910  * see if there's any stats for it.
6911  */
6912 
6913  /* get the attnum from the 0-based index. */
6914  attnum = iclause->indexcol + 1;
6915 
6916  if (get_index_stats_hook &&
6917  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
6918  {
6919  /*
6920  * The hook took control of acquiring a stats tuple. If it
6921  * did supply a tuple, it'd better have supplied a freefunc.
6922  */
6923  if (HeapTupleIsValid(vardata.statsTuple) &&
6924  !vardata.freefunc)
6925  elog(ERROR, "no function provided to release variable stats with");
6926  }
6927  else
6928  {
6930  ObjectIdGetDatum(index->indexoid),
6931  Int16GetDatum(attnum),
6932  BoolGetDatum(false));
6933  vardata.freefunc = ReleaseSysCache;
6934  }
6935  }
6936 
6937  if (HeapTupleIsValid(vardata.statsTuple))
6938  {
6939  AttStatsSlot sslot;
6940 
6941  if (get_attstatsslot(&sslot, vardata.statsTuple,
6942  STATISTIC_KIND_CORRELATION, InvalidOid,
6944  {
6945  double varCorrelation = 0.0;
6946 
6947  if (sslot.nnumbers > 0)
6948  varCorrelation = Abs(sslot.numbers[0]);
6949 
6950  if (varCorrelation > *indexCorrelation)
6951  *indexCorrelation = varCorrelation;
6952 
6953  free_attstatsslot(&sslot);
6954  }
6955  }
6956 
6957  ReleaseVariableStats(vardata);
6958  }
6959 
6960  qualSelectivity = clauselist_selectivity(root, indexQuals,
6961  baserel->relid,
6962  JOIN_INNER, NULL);
6963 
6964  /* work out the actual number of ranges in the index */
6965  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
6966  1.0);
6967 
6968  /*
6969  * Now calculate the minimum possible ranges we could match with if all of
6970  * the rows were in the perfect order in the table's heap.
6971  */
6972  minimalRanges = ceil(indexRanges * qualSelectivity);
6973 
6974  /*
6975  * Now estimate the number of ranges that we'll touch by using the
6976  * indexCorrelation from the stats. Careful not to divide by zero (note
6977  * we're using the absolute value of the correlation).
6978  */
6979  if (*indexCorrelation < 1.0e-10)
6980  estimatedRanges = indexRanges;
6981  else
6982  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
6983 
6984  /* we expect to visit this portion of the table */
6985  selec = estimatedRanges / indexRanges;
6986 
6987  CLAMP_PROBABILITY(selec);
6988 
6989  *indexSelectivity = selec;
6990 
6991  /*
6992  * Compute the index qual costs, much as in genericcostestimate, to add to
6993  * the index costs. We can disregard indexorderbys, since BRIN doesn't
6994  * support those.
6995  */
6996  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
6997 
6998  /*
6999  * Compute the startup cost as the cost to read the whole revmap
7000  * sequentially, including the cost to execute the index quals.
7001  */
7002  *indexStartupCost =
7003  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7004  *indexStartupCost += qual_arg_cost;
7005 
7006  /*
7007  * To read a BRIN index there might be a bit of back and forth over
7008  * regular pages, as revmap might point to them out of sequential order;
7009  * calculate the total cost as reading the whole index in random order.
7010  */
7011  *indexTotalCost = *indexStartupCost +
7012  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7013 
7014  /*
7015  * Charge a small amount per range tuple which we expect to match to. This
7016  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7017  * will set a bit for each page in the range when we find a matching
7018  * range, so we must multiply the charge by the number of pages in the
7019  * range.
7020  */
7021  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7022  statsData.pagesPerRange;
7023 
7024  *indexPages = index->pages;
7025 }
IndexOptInfo * indexinfo
Definition: pathnodes.h:1177
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:54
#define Min(x, y)
Definition: c.h:904
#define Int16GetDatum(X)
Definition: postgres.h:451
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
Oid reltablespace
Definition: pathnodes.h:790
List * indexclauses
Definition: pathnodes.h:1178
#define Abs(x)
Definition: c.h:910
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:794
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
RelOptInfo * rel
Definition: pathnodes.h:791
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1146
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:371
AttrNumber indexcol
Definition: pathnodes.h:1226
#define lfirst_node(type, lc)
Definition: pg_list.h:193
#define NoLock
Definition: lockdefs.h:34
float4 * numbers
Definition: lsyscache.h:53
double cpu_operator_cost
Definition: costsize.c:114
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:5440
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:146
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:669
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1172
#define BoolGetDatum(X)
Definition: postgres.h:402
#define InvalidOid
Definition: postgres_ext.h:36
BlockNumber pagesPerRange
Definition: brin.h:33
int16 attnum
Definition: pg_attribute.h:79
#define Max(x, y)
Definition: c.h:898
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:5470
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
BlockNumber pages
Definition: pathnodes.h:680
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2942
#define Assert(condition)
Definition: c.h:732
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:147
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:152
RTEKind rtekind
Definition: parsenodes.h:974
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
#define elog(elevel,...)
Definition: elog.h:226
int * indexkeys
Definition: pathnodes.h:801
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:70
Definition: pg_list.h:50
int16 AttrNumber
Definition: attnum.h:21
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:126
double Cost
Definition: nodes.h:659
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1093
BlockNumber revmapNumPages
Definition: brin.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3072

◆ btcostestimate()

void btcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 5763 of file selfuncs.c.

References add_predicate_to_index_quals(), ScalarArrayOpExpr::args, Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, clauselist_selectivity(), cpu_operator_cost, elog, ERROR, estimate_array_length(), free_attstatsslot(), VariableStatData::freefunc, genericcostestimate(), get_attstatsslot(), get_index_stats_hook, get_op_opfamily_strategy(), get_opfamily_member(), get_relation_stats_hook, HeapTupleIsValid, IndexPath::indexclauses, IndexClause::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, IndexClause::indexquals, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst_node, linitial_oid, lsecond, MemSet, NIL, IndexOptInfo::nkeycolumns, AttStatsSlot::nnumbers, nodeTag, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum, OidIsValid, IndexOptInfo::opcintype, IndexOptInfo::opfamily, OpExpr::opno, ScalarArrayOpExpr::opno, RowCompareExpr::opnos, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reverse_sort, rint(), RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

5767 {
5768  IndexOptInfo *index = path->indexinfo;
5769  GenericCosts costs;
5770  Oid relid;
5771  AttrNumber colnum;
5772  VariableStatData vardata;
5773  double numIndexTuples;
5774  Cost descentCost;
5775  List *indexBoundQuals;
5776  int indexcol;
5777  bool eqQualHere;
5778  bool found_saop;
5779  bool found_is_null_op;
5780  double num_sa_scans;
5781  ListCell *lc;
5782 
5783  /*
5784  * For a btree scan, only leading '=' quals plus inequality quals for the
5785  * immediately next attribute contribute to index selectivity (these are
5786  * the "boundary quals" that determine the starting and stopping points of
5787  * the index scan). Additional quals can suppress visits to the heap, so
5788  * it's OK to count them in indexSelectivity, but they should not count
5789  * for estimating numIndexTuples. So we must examine the given indexquals
5790  * to find out which ones count as boundary quals. We rely on the
5791  * knowledge that they are given in index column order.
5792  *
5793  * For a RowCompareExpr, we consider only the first column, just as
5794  * rowcomparesel() does.
5795  *
5796  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
5797  * index scans not one, but the ScalarArrayOpExpr's operator can be
5798  * considered to act the same as it normally does.
5799  */
5800  indexBoundQuals = NIL;
5801  indexcol = 0;
5802  eqQualHere = false;
5803  found_saop = false;
5804  found_is_null_op = false;
5805  num_sa_scans = 1;
5806  foreach(lc, path->indexclauses)
5807  {
5808  IndexClause *iclause = lfirst_node(IndexClause, lc);
5809  ListCell *lc2;
5810 
5811  if (indexcol != iclause->indexcol)
5812  {
5813  /* Beginning of a new column's quals */
5814  if (!eqQualHere)
5815  break; /* done if no '=' qual for indexcol */
5816  eqQualHere = false;
5817  indexcol++;
5818  if (indexcol != iclause->indexcol)
5819  break; /* no quals at all for indexcol */
5820  }
5821 
5822  /* Examine each indexqual associated with this index clause */
5823  foreach(lc2, iclause->indexquals)
5824  {
5825  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
5826  Expr *clause = rinfo->clause;
5827  Oid clause_op = InvalidOid;
5828  int op_strategy;
5829 
5830  if (IsA(clause, OpExpr))
5831  {
5832  OpExpr *op = (OpExpr *) clause;
5833 
5834  clause_op = op->opno;
5835  }
5836  else if (IsA(clause, RowCompareExpr))
5837  {
5838  RowCompareExpr *rc = (RowCompareExpr *) clause;
5839 
5840  clause_op = linitial_oid(rc->opnos);
5841  }
5842  else if (IsA(clause, ScalarArrayOpExpr))
5843  {
5844  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
5845  Node *other_operand = (Node *) lsecond(saop->args);
5846  int alength = estimate_array_length(other_operand);
5847 
5848  clause_op = saop->opno;
5849  found_saop = true;
5850  /* count number of SA scans induced by indexBoundQuals only */
5851  if (alength > 1)
5852  num_sa_scans *= alength;
5853  }
5854  else if (IsA(clause, NullTest))
5855  {
5856  NullTest *nt = (NullTest *) clause;
5857 
5858  if (nt->nulltesttype == IS_NULL)
5859  {
5860  found_is_null_op = true;
5861  /* IS NULL is like = for selectivity purposes */
5862  eqQualHere = true;
5863  }
5864  }
5865  else
5866  elog(ERROR, "unsupported indexqual type: %d",
5867  (int) nodeTag(clause));
5868 
5869  /* check for equality operator */
5870  if (OidIsValid(clause_op))
5871  {
5872  op_strategy = get_op_opfamily_strategy(clause_op,
5873  index->opfamily[indexcol]);
5874  Assert(op_strategy != 0); /* not a member of opfamily?? */
5875  if (op_strategy == BTEqualStrategyNumber)
5876  eqQualHere = true;
5877  }
5878 
5879  indexBoundQuals = lappend(indexBoundQuals, rinfo);
5880  }
5881  }
5882 
5883  /*
5884  * If index is unique and we found an '=' clause for each column, we can
5885  * just assume numIndexTuples = 1 and skip the expensive
5886  * clauselist_selectivity calculations. However, a ScalarArrayOp or
5887  * NullTest invalidates that theory, even though it sets eqQualHere.
5888  */
5889  if (index->unique &&
5890  indexcol == index->nkeycolumns - 1 &&
5891  eqQualHere &&
5892  !found_saop &&
5893  !found_is_null_op)
5894  numIndexTuples = 1.0;
5895  else
5896  {
5897  List *selectivityQuals;
5898  Selectivity btreeSelectivity;
5899 
5900  /*
5901  * If the index is partial, AND the index predicate with the
5902  * index-bound quals to produce a more accurate idea of the number of
5903  * rows covered by the bound conditions.
5904  */
5905  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
5906 
5907  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
5908  index->rel->relid,
5909  JOIN_INNER,
5910  NULL);
5911  numIndexTuples = btreeSelectivity * index->rel->tuples;
5912 
5913  /*
5914  * As in genericcostestimate(), we have to adjust for any
5915  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
5916  * to integer.
5917  */
5918  numIndexTuples = rint(numIndexTuples / num_sa_scans);
5919  }
5920 
5921  /*
5922  * Now do generic index cost estimation.
5923  */
5924  MemSet(&costs, 0, sizeof(costs));
5925  costs.numIndexTuples = numIndexTuples;
5926 
5927  genericcostestimate(root, path, loop_count, &costs);
5928 
5929  /*
5930  * Add a CPU-cost component to represent the costs of initial btree
5931  * descent. We don't charge any I/O cost for touching upper btree levels,
5932  * since they tend to stay in cache, but we still have to do about log2(N)
5933  * comparisons to descend a btree of N leaf tuples. We charge one
5934  * cpu_operator_cost per comparison.
5935  *
5936  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
5937  * ones after the first one are not startup cost so far as the overall
5938  * plan is concerned, so add them only to "total" cost.
5939  */
5940  if (index->tuples > 1) /* avoid computing log(0) */
5941  {
5942  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
5943  costs.indexStartupCost += descentCost;
5944  costs.indexTotalCost += costs.num_sa_scans * descentCost;
5945  }
5946 
5947  /*
5948  * Even though we're not charging I/O cost for touching upper btree pages,
5949  * it's still reasonable to charge some CPU cost per page descended
5950  * through. Moreover, if we had no such charge at all, bloated indexes
5951  * would appear to have the same search cost as unbloated ones, at least
5952  * in cases where only a single leaf page is expected to be visited. This
5953  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
5954  * touched. The number of such pages is btree tree height plus one (ie,
5955  * we charge for the leaf page too). As above, charge once per SA scan.
5956  */
5957  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
5958  costs.indexStartupCost += descentCost;
5959  costs.indexTotalCost += costs.num_sa_scans * descentCost;
5960 
5961  /*
5962  * If we can get an estimate of the first column's ordering correlation C
5963  * from pg_statistic, estimate the index correlation as C for a
5964  * single-column index, or C * 0.75 for multiple columns. (The idea here
5965  * is that multiple columns dilute the importance of the first column's
5966  * ordering, but don't negate it entirely. Before 8.0 we divided the
5967  * correlation by the number of columns, but that seems too strong.)
5968  */
5969  MemSet(&vardata, 0, sizeof(vardata));
5970 
5971  if (index->indexkeys[0] != 0)
5972  {
5973  /* Simple variable --- look to stats for the underlying table */
5974  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
5975 
5976  Assert(rte->rtekind == RTE_RELATION);
5977  relid = rte->relid;
5978  Assert(relid != InvalidOid);
5979  colnum = index->indexkeys[0];
5980 
5982  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
5983  {
5984  /*
5985  * The hook took control of acquiring a stats tuple. If it did
5986  * supply a tuple, it'd better have supplied a freefunc.
5987  */
5988  if (HeapTupleIsValid(vardata.statsTuple) &&
5989  !vardata.freefunc)
5990  elog(ERROR, "no function provided to release variable stats with");
5991  }
5992  else
5993  {
5995  ObjectIdGetDatum(relid),
5996  Int16GetDatum(colnum),
5997  BoolGetDatum(rte->inh));
5998  vardata.freefunc = ReleaseSysCache;
5999  }
6000  }
6001  else
6002  {
6003  /* Expression --- maybe there are stats for the index itself */
6004  relid = index->indexoid;
6005  colnum = 1;
6006 
6007  if (get_index_stats_hook &&
6008  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6009  {
6010  /*
6011  * The hook took control of acquiring a stats tuple. If it did
6012  * supply a tuple, it'd better have supplied a freefunc.
6013  */
6014  if (HeapTupleIsValid(vardata.statsTuple) &&
6015  !vardata.freefunc)
6016  elog(ERROR, "no function provided to release variable stats with");
6017  }
6018  else
6019  {
6021  ObjectIdGetDatum(relid),
6022  Int16GetDatum(colnum),
6023  BoolGetDatum(false));
6024  vardata.freefunc = ReleaseSysCache;
6025  }
6026  }
6027 
6028  if (HeapTupleIsValid(vardata.statsTuple))
6029  {
6030  Oid sortop;
6031  AttStatsSlot sslot;
6032 
6033  sortop = get_opfamily_member(index->opfamily[0],
6034  index->opcintype[0],
6035  index->opcintype[0],
6037  if (OidIsValid(sortop) &&
6038  get_attstatsslot(&sslot, vardata.statsTuple,
6039  STATISTIC_KIND_CORRELATION, sortop,
6041  {
6042  double varCorrelation;
6043 
6044  Assert(sslot.nnumbers == 1);
6045  varCorrelation = sslot.numbers[0];
6046 
6047  if (index->reverse_sort[0])
6048  varCorrelation = -varCorrelation;
6049 
6050  if (index->nkeycolumns > 1)
6051  costs.indexCorrelation = varCorrelation * 0.75;
6052  else
6053  costs.indexCorrelation = varCorrelation;
6054 
6055  free_attstatsslot(&sslot);
6056  }
6057  }
6058 
6059  ReleaseVariableStats(vardata);
6060 
6061  *indexStartupCost = costs.indexStartupCost;
6062  *indexTotalCost = costs.indexTotalCost;
6063  *indexSelectivity = costs.indexSelectivity;
6064  *indexCorrelation = costs.indexCorrelation;
6065  *indexPages = costs.numIndexPages;
6066 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
#define NIL
Definition: pg_list.h:65
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
IndexOptInfo * indexinfo
Definition: pathnodes.h:1177
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:54
double tuples
Definition: pathnodes.h:681
#define Int16GetDatum(X)
Definition: postgres.h:451
Definition: nodes.h:525
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
#define MemSet(start, val, len)
Definition: c.h:955
List * indexclauses
Definition: pathnodes.h:1178
double Selectivity
Definition: nodes.h:658
double tuples
Definition: pathnodes.h:795
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: pathnodes.h:796
#define OidIsValid(objectId)
Definition: c.h:638
#define lsecond(l)
Definition: pg_list.h:200
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:1890
RelOptInfo * rel
Definition: pathnodes.h:791
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1146
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:371
AttrNumber indexcol
Definition: pathnodes.h:1226
double num_sa_scans
Definition: selfuncs.h:113
#define lfirst_node(type, lc)
Definition: pg_list.h:193
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5524
float4 * numbers
Definition: lsyscache.h:53
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:163
double cpu_operator_cost
Definition: costsize.c:114
Cost indexTotalCost
Definition: selfuncs.h:105
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:146
double rint(double x)
Definition: rint.c:21
List * indexquals
Definition: pathnodes.h:1224
Index relid
Definition: pathnodes.h:669
List * lappend(List *list, void *datum)
Definition: list.c:322
Expr * clause
Definition: pathnodes.h:1943
double indexCorrelation
Definition: selfuncs.h:107
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1172
NullTestType nulltesttype
Definition: primnodes.h:1206
#define BoolGetDatum(X)
Definition: postgres.h:402
#define InvalidOid
Definition: postgres_ext.h:36
double numIndexTuples
Definition: selfuncs.h:111
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2942
#define Assert(condition)
Definition: c.h:732
#define linitial_oid(l)
Definition: pg_list.h:197
int nkeycolumns
Definition: pathnodes.h:800
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:147
Oid * opcintype
Definition: pathnodes.h:805
#define nodeTag(nodeptr)
Definition: nodes.h:530
Cost indexStartupCost
Definition: selfuncs.h:104
Oid * opfamily
Definition: pathnodes.h:804
RTEKind rtekind
Definition: parsenodes.h:974
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:80
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
#define elog(elevel,...)
Definition: elog.h:226
int * indexkeys
Definition: pathnodes.h:801
Oid opno
Definition: primnodes.h:502
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:70
bool * reverse_sort
Definition: pathnodes.h:807
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:50
int16 AttrNumber
Definition: attnum.h:21
#define BTEqualStrategyNumber
Definition: stratnum.h:31
double Cost
Definition: nodes.h:659
double numIndexPages
Definition: selfuncs.h:110
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3072
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:5742

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

References add_predicate_to_index_quals(), GinQualCounts::arrayScans, RestrictInfo::clause, clauselist_selectivity(), cpu_index_tuple_cost, cpu_operator_cost, elog, ERROR, GinQualCounts::exactEntries, get_quals_from_indexclauses(), get_tablespace_page_costs(), gincost_opexpr(), gincost_scalararrayopexpr(), ginGetStats(), GinQualCounts::haveFullScan, IndexOptInfo::hypothetical, index_close(), index_open(), index_other_operands_eval_cost(), index_pages_fetched(), IndexPath::indexclauses, IndexClause::indexcol, IndexPath::indexinfo, IndexOptInfo::indexoid, IndexClause::indexquals, IsA, JOIN_INNER, lfirst_node, list_length(), Max, Min, GinStatsData::nDataPages, GinStatsData::nEntries, GinStatsData::nEntryPages, NIL, nodeTag, NoLock, GinStatsData::nPendingPages, GinStatsData::nTotalPages, IndexOptInfo::pages, GinQualCounts::partialEntries, IndexOptInfo::rel, RelOptInfo::relid, IndexOptInfo::reltablespace, rint(), scale, GinQualCounts::searchEntries, and IndexOptInfo::tuples.

Referenced by ginhandler().

6519 {
6520  IndexOptInfo *index = path->indexinfo;
6521  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
6522  List *selectivityQuals;
6523  double numPages = index->pages,
6524  numTuples = index->tuples;
6525  double numEntryPages,
6526  numDataPages,
6527  numPendingPages,
6528  numEntries;
6529  GinQualCounts counts;
6530  bool matchPossible;
6531  double partialScale;
6532  double entryPagesFetched,
6533  dataPagesFetched,
6534  dataPagesFetchedBySel;
6535  double qual_op_cost,
6536  qual_arg_cost,
6537  spc_random_page_cost,
6538  outer_scans;
6539  Relation indexRel;
6540  GinStatsData ginStats;
6541  ListCell *lc;
6542 
6543  /*
6544  * Obtain statistical information from the meta page, if possible. Else
6545  * set ginStats to zeroes, and we'll cope below.
6546  */
6547  if (!index->hypothetical)
6548  {
6549  /* Lock should have already been obtained in plancat.c */
6550  indexRel = index_open(index->indexoid, NoLock);
6551  ginGetStats(indexRel, &ginStats);
6552  index_close(indexRel, NoLock);
6553  }
6554  else
6555  {
6556  memset(&ginStats, 0, sizeof(ginStats));
6557  }
6558 
6559  /*
6560  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
6561  * trusted, but the other fields are data as of the last VACUUM. We can
6562  * scale them up to account for growth since then, but that method only
6563  * goes so far; in the worst case, the stats might be for a completely
6564  * empty index, and scaling them will produce pretty bogus numbers.
6565  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
6566  * it's grown more than that, fall back to estimating things only from the
6567  * assumed-accurate index size. But we'll trust nPendingPages in any case
6568  * so long as it's not clearly insane, ie, more than the index size.
6569  */
6570  if (ginStats.nPendingPages < numPages)
6571  numPendingPages = ginStats.nPendingPages;
6572  else
6573  numPendingPages = 0;
6574 
6575  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
6576  ginStats.nTotalPages > numPages / 4 &&
6577  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
6578  {
6579  /*
6580  * OK, the stats seem close enough to sane to be trusted. But we
6581  * still need to scale them by the ratio numPages / nTotalPages to
6582  * account for growth since the last VACUUM.
6583  */
6584  double scale = numPages / ginStats.nTotalPages;
6585 
6586  numEntryPages = ceil(ginStats.nEntryPages * scale);
6587  numDataPages = ceil(ginStats.nDataPages * scale);
6588  numEntries = ceil(ginStats.nEntries * scale);
6589  /* ensure we didn't round up too much */
6590  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
6591  numDataPages = Min(numDataPages,
6592  numPages - numPendingPages - numEntryPages);
6593  }
6594  else
6595  {
6596  /*
6597  * We might get here because it's a hypothetical index, or an index
6598  * created pre-9.1 and never vacuumed since upgrading (in which case
6599  * its stats would read as zeroes), or just because it's grown too
6600  * much since the last VACUUM for us to put our faith in scaling.
6601  *
6602  * Invent some plausible internal statistics based on the index page
6603  * count (and clamp that to at least 10 pages, just in case). We
6604  * estimate that 90% of the index is entry pages, and the rest is data
6605  * pages. Estimate 100 entries per entry page; this is rather bogus
6606  * since it'll depend on the size of the keys, but it's more robust
6607  * than trying to predict the number of entries per heap tuple.
6608  */
6609  numPages = Max(numPages, 10);
6610  numEntryPages = floor((numPages - numPendingPages) * 0.90);
6611  numDataPages = numPages - numPendingPages - numEntryPages;
6612  numEntries = floor(numEntryPages * 100);
6613  }
6614 
6615  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
6616  if (numEntries < 1)
6617  numEntries = 1;
6618 
6619  /*
6620  * If the index is partial, AND the index predicate with the index-bound
6621  * quals to produce a more accurate idea of the number of rows covered by
6622  * the bound conditions.
6623  */
6624  selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
6625 
6626  /* Estimate the fraction of main-table tuples that will be visited */
6627  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
6628  index->rel->relid,
6629  JOIN_INNER,
6630  NULL);
6631 
6632  /* fetch estimated page cost for tablespace containing index */
6634  &spc_random_page_cost,
6635  NULL);
6636 
6637  /*
6638  * Generic assumption about index correlation: there isn't any.
6639  */
6640  *indexCorrelation = 0.0;
6641 
6642  /*
6643  * Examine quals to estimate number of search entries & partial matches
6644  */
6645  memset(&counts, 0, sizeof(counts));
6646  counts.arrayScans = 1;
6647  matchPossible = true;
6648 
6649  foreach(lc, path->indexclauses)
6650  {
6651  IndexClause *iclause = lfirst_node(IndexClause, lc);
6652  ListCell *lc2;
6653 
6654  foreach(lc2, iclause->indexquals)
6655  {
6656  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6657  Expr *clause = rinfo->clause;
6658 
6659  if (IsA(clause, OpExpr))
6660  {
6661  matchPossible = gincost_opexpr(root,
6662  index,
6663  iclause->indexcol,
6664  (OpExpr *) clause,
6665  &counts);
6666  if (!matchPossible)
6667  break;
6668  }
6669  else if (IsA(clause, ScalarArrayOpExpr))
6670  {
6671  matchPossible = gincost_scalararrayopexpr(root,
6672  index,
6673  iclause->indexcol,
6674  (ScalarArrayOpExpr *) clause,
6675  numEntries,
6676  &counts);
6677  if (!matchPossible)
6678  break;
6679  }
6680  else
6681  {
6682  /* shouldn't be anything else for a GIN index */
6683  elog(ERROR, "unsupported GIN indexqual type: %d",
6684  (int) nodeTag(clause));
6685  }
6686  }
6687  }
6688 
6689  /* Fall out if there were any provably-unsatisfiable quals */
6690  if (!matchPossible)
6691  {
6692  *indexStartupCost = 0;
6693  *indexTotalCost = 0;
6694  *indexSelectivity = 0;
6695  return;
6696  }
6697 
6698  if (counts.haveFullScan || indexQuals == NIL)
6699  {
6700  /*
6701  * Full index scan will be required. We treat this as if every key in
6702  * the index had been listed in the query; is that reasonable?
6703  */
6704  counts.partialEntries = 0;
6705  counts.exactEntries = numEntries;
6706  counts.searchEntries = numEntries;
6707  }
6708 
6709  /* Will we have more than one iteration of a nestloop scan? */
6710  outer_scans = loop_count;
6711 
6712  /*
6713  * Compute cost to begin scan, first of all, pay attention to pending
6714  * list.
6715  */
6716  entryPagesFetched = numPendingPages;
6717 
6718  /*
6719  * Estimate number of entry pages read. We need to do
6720  * counts.searchEntries searches. Use a power function as it should be,
6721  * but tuples on leaf pages usually is much greater. Here we include all
6722  * searches in entry tree, including search of first entry in partial
6723  * match algorithm
6724  */
6725  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
6726 
6727  /*
6728  * Add an estimate of entry pages read by partial match algorithm. It's a
6729  * scan over leaf pages in entry tree. We haven't any useful stats here,
6730  * so estimate it as proportion. Because counts.partialEntries is really
6731  * pretty bogus (see code above), it's possible that it is more than
6732  * numEntries; clamp the proportion to ensure sanity.
6733  */
6734  partialScale = counts.partialEntries / numEntries;
6735  partialScale = Min(partialScale, 1.0);
6736 
6737  entryPagesFetched += ceil(numEntryPages * partialScale);
6738 
6739  /*
6740  * Partial match algorithm reads all data pages before doing actual scan,
6741  * so it's a startup cost. Again, we haven't any useful stats here, so
6742  * estimate it as proportion.
6743  */
6744  dataPagesFetched = ceil(numDataPages * partialScale);
6745 
6746  /*
6747  * Calculate cache effects if more than one scan due to nestloops or array
6748  * quals. The result is pro-rated per nestloop scan, but the array qual
6749  * factor shouldn't be pro-rated (compare genericcostestimate).
6750  */
6751  if (outer_scans > 1 || counts.arrayScans > 1)
6752  {
6753  entryPagesFetched *= outer_scans * counts.arrayScans;
6754  entryPagesFetched = index_pages_fetched(entryPagesFetched,
6755  (BlockNumber) numEntryPages,
6756  numEntryPages, root);
6757  entryPagesFetched /= outer_scans;
6758  dataPagesFetched *= outer_scans * counts.arrayScans;
6759  dataPagesFetched = index_pages_fetched(dataPagesFetched,
6760  (BlockNumber) numDataPages,
6761  numDataPages, root);
6762  dataPagesFetched /= outer_scans;
6763  }
6764 
6765  /*
6766  * Here we use random page cost because logically-close pages could be far
6767  * apart on disk.
6768  */
6769  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
6770 
6771  /*
6772  * Now compute the number of data pages fetched during the scan.
6773  *
6774  * We assume every entry to have the same number of items, and that there
6775  * is no overlap between them. (XXX: tsvector and array opclasses collect
6776  * statistics on the frequency of individual keys; it would be nice to use
6777  * those here.)
6778  */
6779  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
6780 
6781  /*
6782  * If there is a lot of overlap among the entries, in particular if one of
6783  * the entries is very frequent, the above calculation can grossly
6784  * under-estimate. As a simple cross-check, calculate a lower bound based
6785  * on the overall selectivity of the quals. At a minimum, we must read
6786  * one item pointer for each matching entry.
6787  *
6788  * The width of each item pointer varies, based on the level of
6789  * compression. We don't have statistics on that, but an average of
6790  * around 3 bytes per item is fairly typical.
6791  */
6792  dataPagesFetchedBySel = ceil(*indexSelectivity *
6793  (numTuples / (BLCKSZ / 3)));
6794  if (dataPagesFetchedBySel > dataPagesFetched)
6795  dataPagesFetched = dataPagesFetchedBySel;
6796 
6797  /* Account for cache effects, the same as above */
6798  if (outer_scans > 1 || counts.arrayScans > 1)
6799  {
6800  dataPagesFetched *= outer_scans * counts.arrayScans;
6801  dataPagesFetched = index_pages_fetched(dataPagesFetched,
6802  (BlockNumber) numDataPages,
6803  numDataPages, root);
6804  dataPagesFetched /= outer_scans;
6805  }
6806 
6807  /* And apply random_page_cost as the cost per page */
6808  *indexTotalCost = *indexStartupCost +
6809  dataPagesFetched * spc_random_page_cost;
6810 
6811  /*
6812  * Add on index qual eval costs, much as in genericcostestimate. But we
6813  * can disregard indexorderbys, since GIN doesn't support those.
6814  */
6815  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
6816  qual_op_cost = cpu_operator_cost * list_length(indexQuals);
6817 
6818  *indexStartupCost += qual_arg_cost;
6819  *indexTotalCost += qual_arg_cost;
6820  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
6821  *indexPages = dataPagesFetched;
6822 }
#define NIL
Definition: pg_list.h:65
BlockNumber nEntryPages
Definition: gin.h:45
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
IndexOptInfo * indexinfo
Definition: pathnodes.h:1177
#define Min(x, y)
Definition: c.h:904
double partialEntries
Definition: selfuncs.c:6234
double searchEntries
Definition: selfuncs.c:6236
Oid reltablespace
Definition: pathnodes.h:790
int scale
Definition: pgbench.c:151
int64 nEntries
Definition: gin.h:47
uint32 BlockNumber
Definition: block.h:31
bool hypothetical
Definition: pathnodes.h:827
List * indexclauses
Definition: pathnodes.h:1178
double tuples
Definition: pathnodes.h:795
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:6235
BlockNumber pages
Definition: pathnodes.h:794
RelOptInfo * rel
Definition: pathnodes.h:791
#define ERROR
Definition: elog.h:43
AttrNumber indexcol
Definition: pathnodes.h:1226
#define lfirst_node(type, lc)
Definition: pg_list.h:193
#define NoLock
Definition: lockdefs.h:34
bool haveFullScan
Definition: selfuncs.c:6233
double cpu_operator_cost
Definition: costsize.c:114
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:5440
double rint(double x)
Definition: rint.c:21
List * indexquals
Definition: pathnodes.h:1224
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:669
Expr * clause
Definition: pathnodes.h:1943
BlockNumber nPendingPages
Definition: gin.h:43
double arrayScans
Definition: selfuncs.c:6237
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:638
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, OpExpr *clause, GinQualCounts *counts)
Definition: selfuncs.c:6350
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, ScalarArrayOpExpr *clause, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:6400
BlockNumber nDataPages
Definition: gin.h:46
#define Max(x, y)
Definition: c.h:898
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:5470
static int list_length(const List *l)
Definition: pg_list.h:169
BlockNumber nTotalPages
Definition: gin.h:44
#define nodeTag(nodeptr)
Definition: nodes.h:530
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:152
#define elog(elevel,...)
Definition: elog.h:226
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:70
Definition: pg_list.h:50
double cpu_index_tuple_cost
Definition: costsize.c:113
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:126
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:825
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:5742

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

References cpu_operator_cost, genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, IndexOptInfo::pages, IndexOptInfo::tree_height, and IndexOptInfo::tuples.

Referenced by gisthandler().

6117 {
6118  IndexOptInfo *index = path->indexinfo;
6119  GenericCosts costs;
6120  Cost descentCost;
6121 
6122  MemSet(&costs, 0, sizeof(costs));
6123 
6124  genericcostestimate(root, path, loop_count, &costs);
6125 
6126  /*
6127  * We model index descent costs similarly to those for btree, but to do
6128  * that we first need an idea of the tree height. We somewhat arbitrarily
6129  * assume that the fanout is 100, meaning the tree height is at most
6130  * log100(index->pages).
6131  *
6132  * Although this computation isn't really expensive enough to require
6133  * caching, we might as well use index->tree_height to cache it.
6134  */
6135  if (index->tree_height < 0) /* unknown? */
6136  {
6137  if (index->pages > 1) /* avoid computing log(0) */
6138  index->tree_height = (int) (log(index->pages) / log(100.0));
6139  else
6140  index->tree_height = 0;
6141  }
6142 
6143  /*
6144  * Add a CPU-cost component to represent the costs of initial descent. We
6145  * just use log(N) here not log2(N) since the branching factor isn't
6146  * necessarily two anyway. As for btree, charge once per SA scan.
6147  */
6148  if (index->tuples > 1) /* avoid computing log(0) */
6149  {
6150  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6151  costs.indexStartupCost += descentCost;
6152  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6153  }
6154 
6155  /*
6156  * Likewise add a per-page charge, calculated the same as for btrees.
6157  */
6158  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6159  costs.indexStartupCost += descentCost;
6160  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6161 
6162  *indexStartupCost = costs.indexStartupCost;
6163  *indexTotalCost = costs.indexTotalCost;
6164  *indexSelectivity = costs.indexSelectivity;
6165  *indexCorrelation = costs.indexCorrelation;
6166  *indexPages = costs.numIndexPages;
6167 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
IndexOptInfo * indexinfo
Definition: pathnodes.h:1177
#define MemSet(start, val, len)
Definition: c.h:955
double tuples
Definition: pathnodes.h:795
int tree_height
Definition: pathnodes.h:796
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:794
double num_sa_scans
Definition: selfuncs.h:113
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5524
double cpu_operator_cost
Definition: costsize.c:114
Cost indexTotalCost
Definition: selfuncs.h:105
double indexCorrelation
Definition: selfuncs.h:107
Cost indexStartupCost
Definition: selfuncs.h:104
double Cost
Definition: nodes.h:659
double numIndexPages
Definition: selfuncs.h:110

◆ hashcostestimate()

void hashcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6069 of file selfuncs.c.

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

Referenced by hashhandler().

6073 {
6074  GenericCosts costs;
6075 
6076  MemSet(&costs, 0, sizeof(costs));
6077 
6078  genericcostestimate(root, path, loop_count, &costs);
6079 
6080  /*
6081  * A hash index has no descent costs as such, since the index AM can go
6082  * directly to the target bucket after computing the hash value. There
6083  * are a couple of other hash-specific costs that we could conceivably add
6084  * here, though:
6085  *
6086  * Ideally we'd charge spc_random_page_cost for each page in the target
6087  * bucket, not just the numIndexPages pages that genericcostestimate
6088  * thought we'd visit. However in most cases we don't know which bucket
6089  * that will be. There's no point in considering the average bucket size
6090  * because the hash AM makes sure that's always one page.
6091  *
6092  * Likewise, we could consider charging some CPU for each index tuple in
6093  * the bucket, if we knew how many there were. But the per-tuple cost is
6094  * just a hash value comparison, not a general datatype-dependent
6095  * comparison, so any such charge ought to be quite a bit less than
6096  * cpu_operator_cost; which makes it probably not worth worrying about.
6097  *
6098  * A bigger issue is that chance hash-value collisions will result in
6099  * wasted probes into the heap. We don't currently attempt to model this
6100  * cost on the grounds that it's rare, but maybe it's not rare enough.
6101  * (Any fix for this ought to consider the generic lossy-operator problem,
6102  * though; it's not entirely hash-specific.)
6103  */
6104 
6105  *indexStartupCost = costs.indexStartupCost;
6106  *indexTotalCost = costs.indexTotalCost;
6107  *indexSelectivity = costs.indexSelectivity;
6108  *indexCorrelation = costs.indexCorrelation;
6109  *indexPages = costs.numIndexPages;
6110 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
#define MemSet(start, val, len)
Definition: c.h:955
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5524
Cost indexTotalCost
Definition: selfuncs.h:105
double indexCorrelation
Definition: selfuncs.h:107
Cost indexStartupCost
Definition: selfuncs.h:104
double numIndexPages
Definition: selfuncs.h:110

◆ spgcostestimate()

void spgcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6170 of file selfuncs.c.

References cpu_operator_cost, genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, IndexOptInfo::pages, IndexOptInfo::tree_height, and IndexOptInfo::tuples.

Referenced by spghandler().

6174 {
6175  IndexOptInfo *index = path->indexinfo;
6176  GenericCosts costs;
6177  Cost descentCost;
6178 
6179  MemSet(&costs, 0, sizeof(costs));
6180 
6181  genericcostestimate(root, path, loop_count, &costs);
6182 
6183  /*
6184  * We model index descent costs similarly to those for btree, but to do
6185  * that we first need an idea of the tree height. We somewhat arbitrarily
6186  * assume that the fanout is 100, meaning the tree height is at most
6187  * log100(index->pages).
6188  *
6189  * Although this computation isn't really expensive enough to require
6190  * caching, we might as well use index->tree_height to cache it.
6191  */
6192  if (index->tree_height < 0) /* unknown? */
6193  {
6194  if (index->pages > 1) /* avoid computing log(0) */
6195  index->tree_height = (int) (log(index->pages) / log(100.0));
6196  else
6197  index->tree_height = 0;
6198  }
6199 
6200  /*
6201  * Add a CPU-cost component to represent the costs of initial descent. We
6202  * just use log(N) here not log2(N) since the branching factor isn't
6203  * necessarily two anyway. As for btree, charge once per SA scan.
6204  */
6205  if (index->tuples > 1) /* avoid computing log(0) */
6206  {
6207  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6208  costs.indexStartupCost += descentCost;
6209  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6210  }
6211 
6212  /*
6213  * Likewise add a per-page charge, calculated the same as for btrees.
6214  */
6215  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6216  costs.indexStartupCost += descentCost;
6217  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6218 
6219  *indexStartupCost = costs.indexStartupCost;
6220  *indexTotalCost = costs.indexTotalCost;
6221  *indexSelectivity = costs.indexSelectivity;
6222  *indexCorrelation = costs.indexCorrelation;
6223  *indexPages = costs.numIndexPages;
6224 }
Selectivity indexSelectivity
Definition: selfuncs.h:106
IndexOptInfo * indexinfo
Definition: pathnodes.h:1177
#define MemSet(start, val, len)
Definition: c.h:955
double tuples
Definition: pathnodes.h:795
int tree_height
Definition: pathnodes.h:796
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:794
double num_sa_scans
Definition: selfuncs.h:113
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:5524
double cpu_operator_cost
Definition: costsize.c:114
Cost indexTotalCost
Definition: selfuncs.h:105
double indexCorrelation
Definition: selfuncs.h:107
Cost indexStartupCost
Definition: selfuncs.h:104
double Cost
Definition: nodes.h:659
double numIndexPages
Definition: selfuncs.h:110