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

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

Referenced by brinhandler().

7690 {
7691  IndexOptInfo *index = path->indexinfo;
7692  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7693  double numPages = index->pages;
7694  RelOptInfo *baserel = index->rel;
7695  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7696  Cost spc_seq_page_cost;
7697  Cost spc_random_page_cost;
7698  double qual_arg_cost;
7699  double qualSelectivity;
7700  BrinStatsData statsData;
7701  double indexRanges;
7702  double minimalRanges;
7703  double estimatedRanges;
7704  double selec;
7705  Relation indexRel;
7706  ListCell *l;
7707  VariableStatData vardata;
7708 
7709  Assert(rte->rtekind == RTE_RELATION);
7710 
7711  /* fetch estimated page cost for the tablespace containing the index */
7713  &spc_random_page_cost,
7714  &spc_seq_page_cost);
7715 
7716  /*
7717  * Obtain some data from the index itself, if possible. Otherwise invent
7718  * some plausible internal statistics based on the relation page count.
7719  */
7720  if (!index->hypothetical)
7721  {
7722  /*
7723  * A lock should have already been obtained on the index in plancat.c.
7724  */
7725  indexRel = index_open(index->indexoid, NoLock);
7726  brinGetStats(indexRel, &statsData);
7727  index_close(indexRel, NoLock);
7728 
7729  /* work out the actual number of ranges in the index */
7730  indexRanges = Max(ceil((double) baserel->pages /
7731  statsData.pagesPerRange), 1.0);
7732  }
7733  else
7734  {
7735  /*
7736  * Assume default number of pages per range, and estimate the number
7737  * of ranges based on that.
7738  */
7739  indexRanges = Max(ceil((double) baserel->pages /
7741 
7743  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
7744  }
7745 
7746  /*
7747  * Compute index correlation
7748  *
7749  * Because we can use all index quals equally when scanning, we can use
7750  * the largest correlation (in absolute value) among columns used by the
7751  * query. Start at zero, the worst possible case. If we cannot find any
7752  * correlation statistics, we will keep it as 0.
7753  */
7754  *indexCorrelation = 0;
7755 
7756  foreach(l, path->indexclauses)
7757  {
7758  IndexClause *iclause = lfirst_node(IndexClause, l);
7759  AttrNumber attnum = index->indexkeys[iclause->indexcol];
7760 
7761  /* attempt to lookup stats in relation for this index column */
7762  if (attnum != 0)
7763  {
7764  /* Simple variable -- look to stats for the underlying table */
7766  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7767  {
7768  /*
7769  * The hook took control of acquiring a stats tuple. If it
7770  * did supply a tuple, it'd better have supplied a freefunc.
7771  */
7772  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7773  elog(ERROR,
7774  "no function provided to release variable stats with");
7775  }
7776  else
7777  {
7778  vardata.statsTuple =
7780  ObjectIdGetDatum(rte->relid),
7781  Int16GetDatum(attnum),
7782  BoolGetDatum(false));
7783  vardata.freefunc = ReleaseSysCache;
7784  }
7785  }
7786  else
7787  {
7788  /*
7789  * Looks like we've found an expression column in the index. Let's
7790  * see if there's any stats for it.
7791  */
7792 
7793  /* get the attnum from the 0-based index. */
7794  attnum = iclause->indexcol + 1;
7795 
7796  if (get_index_stats_hook &&
7797  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7798  {
7799  /*
7800  * The hook took control of acquiring a stats tuple. If it
7801  * did supply a tuple, it'd better have supplied a freefunc.
7802  */
7803  if (HeapTupleIsValid(vardata.statsTuple) &&
7804  !vardata.freefunc)
7805  elog(ERROR, "no function provided to release variable stats with");
7806  }
7807  else
7808  {
7810  ObjectIdGetDatum(index->indexoid),
7811  Int16GetDatum(attnum),
7812  BoolGetDatum(false));
7813  vardata.freefunc = ReleaseSysCache;
7814  }
7815  }
7816 
7817  if (HeapTupleIsValid(vardata.statsTuple))
7818  {
7819  AttStatsSlot sslot;
7820 
7821  if (get_attstatsslot(&sslot, vardata.statsTuple,
7822  STATISTIC_KIND_CORRELATION, InvalidOid,
7824  {
7825  double varCorrelation = 0.0;
7826 
7827  if (sslot.nnumbers > 0)
7828  varCorrelation = Abs(sslot.numbers[0]);
7829 
7830  if (varCorrelation > *indexCorrelation)
7831  *indexCorrelation = varCorrelation;
7832 
7833  free_attstatsslot(&sslot);
7834  }
7835  }
7836 
7837  ReleaseVariableStats(vardata);
7838  }
7839 
7840  qualSelectivity = clauselist_selectivity(root, indexQuals,
7841  baserel->relid,
7842  JOIN_INNER, NULL);
7843 
7844  /*
7845  * Now calculate the minimum possible ranges we could match with if all of
7846  * the rows were in the perfect order in the table's heap.
7847  */
7848  minimalRanges = ceil(indexRanges * qualSelectivity);
7849 
7850  /*
7851  * Now estimate the number of ranges that we'll touch by using the
7852  * indexCorrelation from the stats. Careful not to divide by zero (note
7853  * we're using the absolute value of the correlation).
7854  */
7855  if (*indexCorrelation < 1.0e-10)
7856  estimatedRanges = indexRanges;
7857  else
7858  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7859 
7860  /* we expect to visit this portion of the table */
7861  selec = estimatedRanges / indexRanges;
7862 
7863  CLAMP_PROBABILITY(selec);
7864 
7865  *indexSelectivity = selec;
7866 
7867  /*
7868  * Compute the index qual costs, much as in genericcostestimate, to add to
7869  * the index costs. We can disregard indexorderbys, since BRIN doesn't
7870  * support those.
7871  */
7872  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7873 
7874  /*
7875  * Compute the startup cost as the cost to read the whole revmap
7876  * sequentially, including the cost to execute the index quals.
7877  */
7878  *indexStartupCost =
7879  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7880  *indexStartupCost += qual_arg_cost;
7881 
7882  /*
7883  * To read a BRIN index there might be a bit of back and forth over
7884  * regular pages, as revmap might point to them out of sequential order;
7885  * calculate the total cost as reading the whole index in random order.
7886  */
7887  *indexTotalCost = *indexStartupCost +
7888  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7889 
7890  /*
7891  * Charge a small amount per range tuple which we expect to match to. This
7892  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7893  * will set a bit for each page in the range when we find a matching
7894  * range, so we must multiply the charge by the number of pages in the
7895  * range.
7896  */
7897  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7898  statsData.pagesPerRange;
7899 
7900  *indexPages = index->pages;
7901 }
IndexOptInfo * indexinfo
Definition: pathnodes.h:1245
HeapTuple statsTuple
Definition: selfuncs.h:91
int nnumbers
Definition: lsyscache.h:57
#define Min(x, y)
Definition: c.h:986
#define Int16GetDatum(X)
Definition: postgres.h:495
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:93
Oid reltablespace
Definition: pathnodes.h:839
bool hypothetical
Definition: pathnodes.h:877
List * indexclauses
Definition: pathnodes.h:1246
#define Abs(x)
Definition: c.h:992
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:843
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
RelOptInfo * rel
Definition: pathnodes.h:840
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
#define ObjectIdGetDatum(X)
Definition: postgres.h:551
#define ERROR
Definition: elog.h:46
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1149
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:388
AttrNumber indexcol
Definition: pathnodes.h:1294
#define lfirst_node(type, lc)
Definition: pg_list.h:172
#define NoLock
Definition: lockdefs.h:34
float4 * numbers
Definition: lsyscache.h:56
double cpu_operator_cost
Definition: costsize.c:123
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:6268
#define BRIN_DEFAULT_PAGES_PER_RANGE
Definition: brin.h:38
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:144
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:181
Index relid
Definition: pathnodes.h:709
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1175
#define REVMAP_PAGE_MAXITEMS
Definition: brin_page.h:93
#define BoolGetDatum(X)
Definition: postgres.h:446
#define InvalidOid
Definition: postgres_ext.h:36
BlockNumber pagesPerRange
Definition: brin.h:33
int16 attnum
Definition: pg_attribute.h:83
#define Max(x, y)
Definition: c.h:980
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:6298
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
BlockNumber pages
Definition: pathnodes.h:720
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3177
#define Assert(condition)
Definition: c.h:804
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:145
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:158
RTEKind rtekind
Definition: parsenodes.h:1007
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:101
e
Definition: preproc-init.c:82
#define elog(elevel,...)
Definition: elog.h:232
int * indexkeys
Definition: pathnodes.h:850
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:102
Definition: pg_list.h:50
int16 AttrNumber
Definition: attnum.h:21
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:132
double Cost
Definition: nodes.h:670
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1227
BlockNumber revmapNumPages
Definition: brin.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3294

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

Referenced by bthandler().

6595 {
6596  IndexOptInfo *index = path->indexinfo;
6597  GenericCosts costs;
6598  Oid relid;
6599  AttrNumber colnum;
6600  VariableStatData vardata;
6601  double numIndexTuples;
6602  Cost descentCost;
6603  List *indexBoundQuals;
6604  int indexcol;
6605  bool eqQualHere;
6606  bool found_saop;
6607  bool found_is_null_op;
6608  double num_sa_scans;
6609  ListCell *lc;
6610 
6611  /*
6612  * For a btree scan, only leading '=' quals plus inequality quals for the
6613  * immediately next attribute contribute to index selectivity (these are
6614  * the "boundary quals" that determine the starting and stopping points of
6615  * the index scan). Additional quals can suppress visits to the heap, so
6616  * it's OK to count them in indexSelectivity, but they should not count
6617  * for estimating numIndexTuples. So we must examine the given indexquals
6618  * to find out which ones count as boundary quals. We rely on the
6619  * knowledge that they are given in index column order.
6620  *
6621  * For a RowCompareExpr, we consider only the first column, just as
6622  * rowcomparesel() does.
6623  *
6624  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6625  * index scans not one, but the ScalarArrayOpExpr's operator can be
6626  * considered to act the same as it normally does.
6627  */
6628  indexBoundQuals = NIL;
6629  indexcol = 0;
6630  eqQualHere = false;
6631  found_saop = false;
6632  found_is_null_op = false;
6633  num_sa_scans = 1;
6634  foreach(lc, path->indexclauses)
6635  {
6636  IndexClause *iclause = lfirst_node(IndexClause, lc);
6637  ListCell *lc2;
6638 
6639  if (indexcol != iclause->indexcol)
6640  {
6641  /* Beginning of a new column's quals */
6642  if (!eqQualHere)
6643  break; /* done if no '=' qual for indexcol */
6644  eqQualHere = false;
6645  indexcol++;
6646  if (indexcol != iclause->indexcol)
6647  break; /* no quals at all for indexcol */
6648  }
6649 
6650  /* Examine each indexqual associated with this index clause */
6651  foreach(lc2, iclause->indexquals)
6652  {
6653  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6654  Expr *clause = rinfo->clause;
6655  Oid clause_op = InvalidOid;
6656  int op_strategy;
6657 
6658  if (IsA(clause, OpExpr))
6659  {
6660  OpExpr *op = (OpExpr *) clause;
6661 
6662  clause_op = op->opno;
6663  }
6664  else if (IsA(clause, RowCompareExpr))
6665  {
6666  RowCompareExpr *rc = (RowCompareExpr *) clause;
6667 
6668  clause_op = linitial_oid(rc->opnos);
6669  }
6670  else if (IsA(clause, ScalarArrayOpExpr))
6671  {
6672  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6673  Node *other_operand = (Node *) lsecond(saop->args);
6674  int alength = estimate_array_length(other_operand);
6675 
6676  clause_op = saop->opno;
6677  found_saop = true;
6678  /* count number of SA scans induced by indexBoundQuals only */
6679  if (alength > 1)
6680  num_sa_scans *= alength;
6681  }
6682  else if (IsA(clause, NullTest))
6683  {
6684  NullTest *nt = (NullTest *) clause;
6685 
6686  if (nt->nulltesttype == IS_NULL)
6687  {
6688  found_is_null_op = true;
6689  /* IS NULL is like = for selectivity purposes */
6690  eqQualHere = true;
6691  }
6692  }
6693  else
6694  elog(ERROR, "unsupported indexqual type: %d",
6695  (int) nodeTag(clause));
6696 
6697  /* check for equality operator */
6698  if (OidIsValid(clause_op))
6699  {
6700  op_strategy = get_op_opfamily_strategy(clause_op,
6701  index->opfamily[indexcol]);
6702  Assert(op_strategy != 0); /* not a member of opfamily?? */
6703  if (op_strategy == BTEqualStrategyNumber)
6704  eqQualHere = true;
6705  }
6706 
6707  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6708  }
6709  }
6710 
6711  /*
6712  * If index is unique and we found an '=' clause for each column, we can
6713  * just assume numIndexTuples = 1 and skip the expensive
6714  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6715  * NullTest invalidates that theory, even though it sets eqQualHere.
6716  */
6717  if (index->unique &&
6718  indexcol == index->nkeycolumns - 1 &&
6719  eqQualHere &&
6720  !found_saop &&
6721  !found_is_null_op)
6722  numIndexTuples = 1.0;
6723  else
6724  {
6725  List *selectivityQuals;
6726  Selectivity btreeSelectivity;
6727 
6728  /*
6729  * If the index is partial, AND the index predicate with the
6730  * index-bound quals to produce a more accurate idea of the number of
6731  * rows covered by the bound conditions.
6732  */
6733  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
6734 
6735  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6736  index->rel->relid,
6737  JOIN_INNER,
6738  NULL);
6739  numIndexTuples = btreeSelectivity * index->rel->tuples;
6740 
6741  /*
6742  * As in genericcostestimate(), we have to adjust for any
6743  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6744  * to integer.
6745  */
6746  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6747  }
6748 
6749  /*
6750  * Now do generic index cost estimation.
6751  */
6752  MemSet(&costs, 0, sizeof(costs));
6753  costs.numIndexTuples = numIndexTuples;
6754 
6755  genericcostestimate(root, path, loop_count, &costs);
6756 
6757  /*
6758  * Add a CPU-cost component to represent the costs of initial btree
6759  * descent. We don't charge any I/O cost for touching upper btree levels,
6760  * since they tend to stay in cache, but we still have to do about log2(N)
6761  * comparisons to descend a btree of N leaf tuples. We charge one
6762  * cpu_operator_cost per comparison.
6763  *
6764  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6765  * ones after the first one are not startup cost so far as the overall
6766  * plan is concerned, so add them only to "total" cost.
6767  */
6768  if (index->tuples > 1) /* avoid computing log(0) */
6769  {
6770  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6771  costs.indexStartupCost += descentCost;
6772  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6773  }
6774 
6775  /*
6776  * Even though we're not charging I/O cost for touching upper btree pages,
6777  * it's still reasonable to charge some CPU cost per page descended
6778  * through. Moreover, if we had no such charge at all, bloated indexes
6779  * would appear to have the same search cost as unbloated ones, at least
6780  * in cases where only a single leaf page is expected to be visited. This
6781  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6782  * touched. The number of such pages is btree tree height plus one (ie,
6783  * we charge for the leaf page too). As above, charge once per SA scan.
6784  */
6785  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6786  costs.indexStartupCost += descentCost;
6787  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6788 
6789  /*
6790  * If we can get an estimate of the first column's ordering correlation C
6791  * from pg_statistic, estimate the index correlation as C for a
6792  * single-column index, or C * 0.75 for multiple columns. (The idea here
6793  * is that multiple columns dilute the importance of the first column's
6794  * ordering, but don't negate it entirely. Before 8.0 we divided the
6795  * correlation by the number of columns, but that seems too strong.)
6796  */
6797  MemSet(&vardata, 0, sizeof(vardata));
6798 
6799  if (index->indexkeys[0] != 0)
6800  {
6801  /* Simple variable --- look to stats for the underlying table */
6802  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6803 
6804  Assert(rte->rtekind == RTE_RELATION);
6805  relid = rte->relid;
6806  Assert(relid != InvalidOid);
6807  colnum = index->indexkeys[0];
6808 
6810  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6811  {
6812  /*
6813  * The hook took control of acquiring a stats tuple. If it did
6814  * supply a tuple, it'd better have supplied a freefunc.
6815  */
6816  if (HeapTupleIsValid(vardata.statsTuple) &&
6817  !vardata.freefunc)
6818  elog(ERROR, "no function provided to release variable stats with");
6819  }
6820  else
6821  {
6823  ObjectIdGetDatum(relid),
6824  Int16GetDatum(colnum),
6825  BoolGetDatum(rte->inh));
6826  vardata.freefunc = ReleaseSysCache;
6827  }
6828  }
6829  else
6830  {
6831  /* Expression --- maybe there are stats for the index itself */
6832  relid = index->indexoid;
6833  colnum = 1;
6834 
6835  if (get_index_stats_hook &&
6836  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6837  {
6838  /*
6839  * The hook took control of acquiring a stats tuple. If it did
6840  * supply a tuple, it'd better have supplied a freefunc.
6841  */
6842  if (HeapTupleIsValid(vardata.statsTuple) &&
6843  !vardata.freefunc)
6844  elog(ERROR, "no function provided to release variable stats with");
6845  }
6846  else
6847  {
6849  ObjectIdGetDatum(relid),
6850  Int16GetDatum(colnum),
6851  BoolGetDatum(false));
6852  vardata.freefunc = ReleaseSysCache;
6853  }
6854  }
6855 
6856  if (HeapTupleIsValid(vardata.statsTuple))
6857  {
6858  Oid sortop;
6859  AttStatsSlot sslot;
6860 
6861  sortop = get_opfamily_member(index->opfamily[0],
6862  index->opcintype[0],
6863  index->opcintype[0],
6865  if (OidIsValid(sortop) &&
6866  get_attstatsslot(&sslot, vardata.statsTuple,
6867  STATISTIC_KIND_CORRELATION, sortop,
6869  {
6870  double varCorrelation;
6871 
6872  Assert(sslot.nnumbers == 1);
6873  varCorrelation = sslot.numbers[0];
6874 
6875  if (index->reverse_sort[0])
6876  varCorrelation = -varCorrelation;
6877 
6878  if (index->nkeycolumns > 1)
6879  costs.indexCorrelation = varCorrelation * 0.75;
6880  else
6881  costs.indexCorrelation = varCorrelation;
6882 
6883  free_attstatsslot(&sslot);
6884  }
6885  }
6886 
6887  ReleaseVariableStats(vardata);
6888 
6889  *indexStartupCost = costs.indexStartupCost;
6890  *indexTotalCost = costs.indexTotalCost;
6891  *indexSelectivity = costs.indexSelectivity;
6892  *indexCorrelation = costs.indexCorrelation;
6893  *indexPages = costs.numIndexPages;
6894 }
Selectivity indexSelectivity
Definition: selfuncs.h:126
#define NIL
Definition: pg_list.h:65
#define IsA(nodeptr, _type_)
Definition: nodes.h:587
IndexOptInfo * indexinfo
Definition: pathnodes.h:1245
HeapTuple statsTuple
Definition: selfuncs.h:91
int nnumbers
Definition: lsyscache.h:57
#define Int16GetDatum(X)
Definition: postgres.h:495
Definition: nodes.h:536
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:93
#define MemSet(start, val, len)
Definition: c.h:1008
List * indexclauses
Definition: pathnodes.h:1246
double Selectivity
Definition: nodes.h:669
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: pathnodes.h:845
#define OidIsValid(objectId)
Definition: c.h:710
#define lsecond(l)
Definition: pg_list.h:179
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2132
RelOptInfo * rel
Definition: pathnodes.h:840
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
#define ObjectIdGetDatum(X)
Definition: postgres.h:551
#define ERROR
Definition: elog.h:46
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1149
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:388
AttrNumber indexcol
Definition: pathnodes.h:1294
double num_sa_scans
Definition: selfuncs.h:133
#define lfirst_node(type, lc)
Definition: pg_list.h:172
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6352
float4 * numbers
Definition: lsyscache.h:56
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:164
double cpu_operator_cost
Definition: costsize.c:123
Cost indexTotalCost
Definition: selfuncs.h:125
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:144
List * indexquals
Definition: pathnodes.h:1292
Index relid
Definition: pathnodes.h:709
List * lappend(List *list, void *datum)
Definition: list.c:336
Expr * clause
Definition: pathnodes.h:2056
double indexCorrelation
Definition: selfuncs.h:127
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1175
NullTestType nulltesttype
Definition: primnodes.h:1266
#define BoolGetDatum(X)
Definition: postgres.h:446
#define InvalidOid
Definition: postgres_ext.h:36
double numIndexTuples
Definition: selfuncs.h:131
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3177
#define Assert(condition)
Definition: c.h:804
#define linitial_oid(l)
Definition: pg_list.h:176
int nkeycolumns
Definition: pathnodes.h:849
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:145
Oid * opcintype
Definition: pathnodes.h:854
Cardinality tuples
Definition: pathnodes.h:844
#define nodeTag(nodeptr)
Definition: nodes.h:541
Cost indexStartupCost
Definition: selfuncs.h:124
Oid * opfamily
Definition: pathnodes.h:853
RTEKind rtekind
Definition: parsenodes.h:1007
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:81
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:101
#define elog(elevel,...)
Definition: elog.h:232
int * indexkeys
Definition: pathnodes.h:850
Oid opno
Definition: primnodes.h:542
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:102
bool * reverse_sort
Definition: pathnodes.h:856
#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:670
double numIndexPages
Definition: selfuncs.h:130
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3294
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6570
Cardinality tuples
Definition: pathnodes.h:721

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

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

Referenced by ginhandler().

7359 {
7360  IndexOptInfo *index = path->indexinfo;
7361  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7362  List *selectivityQuals;
7363  double numPages = index->pages,
7364  numTuples = index->tuples;
7365  double numEntryPages,
7366  numDataPages,
7367  numPendingPages,
7368  numEntries;
7369  GinQualCounts counts;
7370  bool matchPossible;
7371  bool fullIndexScan;
7372  double partialScale;
7373  double entryPagesFetched,
7374  dataPagesFetched,
7375  dataPagesFetchedBySel;
7376  double qual_op_cost,
7377  qual_arg_cost,
7378  spc_random_page_cost,
7379  outer_scans;
7380  Relation indexRel;
7381  GinStatsData ginStats;
7382  ListCell *lc;
7383  int i;
7384 
7385  /*
7386  * Obtain statistical information from the meta page, if possible. Else
7387  * set ginStats to zeroes, and we'll cope below.
7388  */
7389  if (!index->hypothetical)
7390  {
7391  /* Lock should have already been obtained in plancat.c */
7392  indexRel = index_open(index->indexoid, NoLock);
7393  ginGetStats(indexRel, &ginStats);
7394  index_close(indexRel, NoLock);
7395  }
7396  else
7397  {
7398  memset(&ginStats, 0, sizeof(ginStats));
7399  }
7400 
7401  /*
7402  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7403  * trusted, but the other fields are data as of the last VACUUM. We can
7404  * scale them up to account for growth since then, but that method only
7405  * goes so far; in the worst case, the stats might be for a completely
7406  * empty index, and scaling them will produce pretty bogus numbers.
7407  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7408  * it's grown more than that, fall back to estimating things only from the
7409  * assumed-accurate index size. But we'll trust nPendingPages in any case
7410  * so long as it's not clearly insane, ie, more than the index size.
7411  */
7412  if (ginStats.nPendingPages < numPages)
7413  numPendingPages = ginStats.nPendingPages;
7414  else
7415  numPendingPages = 0;
7416 
7417  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7418  ginStats.nTotalPages > numPages / 4 &&
7419  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7420  {
7421  /*
7422  * OK, the stats seem close enough to sane to be trusted. But we
7423  * still need to scale them by the ratio numPages / nTotalPages to
7424  * account for growth since the last VACUUM.
7425  */
7426  double scale = numPages / ginStats.nTotalPages;
7427 
7428  numEntryPages = ceil(ginStats.nEntryPages * scale);
7429  numDataPages = ceil(ginStats.nDataPages * scale);
7430  numEntries = ceil(ginStats.nEntries * scale);
7431  /* ensure we didn't round up too much */
7432  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7433  numDataPages = Min(numDataPages,
7434  numPages - numPendingPages - numEntryPages);
7435  }
7436  else
7437  {
7438  /*
7439  * We might get here because it's a hypothetical index, or an index
7440  * created pre-9.1 and never vacuumed since upgrading (in which case
7441  * its stats would read as zeroes), or just because it's grown too
7442  * much since the last VACUUM for us to put our faith in scaling.
7443  *
7444  * Invent some plausible internal statistics based on the index page
7445  * count (and clamp that to at least 10 pages, just in case). We
7446  * estimate that 90% of the index is entry pages, and the rest is data
7447  * pages. Estimate 100 entries per entry page; this is rather bogus
7448  * since it'll depend on the size of the keys, but it's more robust
7449  * than trying to predict the number of entries per heap tuple.
7450  */
7451  numPages = Max(numPages, 10);
7452  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7453  numDataPages = numPages - numPendingPages - numEntryPages;
7454  numEntries = floor(numEntryPages * 100);
7455  }
7456 
7457  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7458  if (numEntries < 1)
7459  numEntries = 1;
7460 
7461  /*
7462  * If the index is partial, AND the index predicate with the index-bound
7463  * quals to produce a more accurate idea of the number of rows covered by
7464  * the bound conditions.
7465  */
7466  selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
7467 
7468  /* Estimate the fraction of main-table tuples that will be visited */
7469  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7470  index->rel->relid,
7471  JOIN_INNER,
7472  NULL);
7473 
7474  /* fetch estimated page cost for tablespace containing index */
7476  &spc_random_page_cost,
7477  NULL);
7478 
7479  /*
7480  * Generic assumption about index correlation: there isn't any.
7481  */
7482  *indexCorrelation = 0.0;
7483 
7484  /*
7485  * Examine quals to estimate number of search entries & partial matches
7486  */
7487  memset(&counts, 0, sizeof(counts));
7488  counts.arrayScans = 1;
7489  matchPossible = true;
7490 
7491  foreach(lc, path->indexclauses)
7492  {
7493  IndexClause *iclause = lfirst_node(IndexClause, lc);
7494  ListCell *lc2;
7495 
7496  foreach(lc2, iclause->indexquals)
7497  {
7498  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
7499  Expr *clause = rinfo->clause;
7500 
7501  if (IsA(clause, OpExpr))
7502  {
7503  matchPossible = gincost_opexpr(root,
7504  index,
7505  iclause->indexcol,
7506  (OpExpr *) clause,
7507  &counts);
7508  if (!matchPossible)
7509  break;
7510  }
7511  else if (IsA(clause, ScalarArrayOpExpr))
7512  {
7513  matchPossible = gincost_scalararrayopexpr(root,
7514  index,
7515  iclause->indexcol,
7516  (ScalarArrayOpExpr *) clause,
7517  numEntries,
7518  &counts);
7519  if (!matchPossible)
7520  break;
7521  }
7522  else
7523  {
7524  /* shouldn't be anything else for a GIN index */
7525  elog(ERROR, "unsupported GIN indexqual type: %d",
7526  (int) nodeTag(clause));
7527  }
7528  }
7529  }
7530 
7531  /* Fall out if there were any provably-unsatisfiable quals */
7532  if (!matchPossible)
7533  {
7534  *indexStartupCost = 0;
7535  *indexTotalCost = 0;
7536  *indexSelectivity = 0;
7537  return;
7538  }
7539 
7540  /*
7541  * If attribute has a full scan and at the same time doesn't have normal
7542  * scan, then we'll have to scan all non-null entries of that attribute.
7543  * Currently, we don't have per-attribute statistics for GIN. Thus, we
7544  * must assume the whole GIN index has to be scanned in this case.
7545  */
7546  fullIndexScan = false;
7547  for (i = 0; i < index->nkeycolumns; i++)
7548  {
7549  if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
7550  {
7551  fullIndexScan = true;
7552  break;
7553  }
7554  }
7555 
7556  if (fullIndexScan || indexQuals == NIL)
7557  {
7558  /*
7559  * Full index scan will be required. We treat this as if every key in
7560  * the index had been listed in the query; is that reasonable?
7561  */
7562  counts.partialEntries = 0;
7563  counts.exactEntries = numEntries;
7564  counts.searchEntries = numEntries;
7565  }
7566 
7567  /* Will we have more than one iteration of a nestloop scan? */
7568  outer_scans = loop_count;
7569 
7570  /*
7571  * Compute cost to begin scan, first of all, pay attention to pending
7572  * list.
7573  */
7574  entryPagesFetched = numPendingPages;
7575 
7576  /*
7577  * Estimate number of entry pages read. We need to do
7578  * counts.searchEntries searches. Use a power function as it should be,
7579  * but tuples on leaf pages usually is much greater. Here we include all
7580  * searches in entry tree, including search of first entry in partial
7581  * match algorithm
7582  */
7583  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7584 
7585  /*
7586  * Add an estimate of entry pages read by partial match algorithm. It's a
7587  * scan over leaf pages in entry tree. We haven't any useful stats here,
7588  * so estimate it as proportion. Because counts.partialEntries is really
7589  * pretty bogus (see code above), it's possible that it is more than
7590  * numEntries; clamp the proportion to ensure sanity.
7591  */
7592  partialScale = counts.partialEntries / numEntries;
7593  partialScale = Min(partialScale, 1.0);
7594 
7595  entryPagesFetched += ceil(numEntryPages * partialScale);
7596 
7597  /*
7598  * Partial match algorithm reads all data pages before doing actual scan,
7599  * so it's a startup cost. Again, we haven't any useful stats here, so
7600  * estimate it as proportion.
7601  */
7602  dataPagesFetched = ceil(numDataPages * partialScale);
7603 
7604  /*
7605  * Calculate cache effects if more than one scan due to nestloops or array
7606  * quals. The result is pro-rated per nestloop scan, but the array qual
7607  * factor shouldn't be pro-rated (compare genericcostestimate).
7608  */
7609  if (outer_scans > 1 || counts.arrayScans > 1)
7610  {
7611  entryPagesFetched *= outer_scans * counts.arrayScans;
7612  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7613  (BlockNumber) numEntryPages,
7614  numEntryPages, root);
7615  entryPagesFetched /= outer_scans;
7616  dataPagesFetched *= outer_scans * counts.arrayScans;
7617  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7618  (BlockNumber) numDataPages,
7619  numDataPages, root);
7620  dataPagesFetched /= outer_scans;
7621  }
7622 
7623  /*
7624  * Here we use random page cost because logically-close pages could be far
7625  * apart on disk.
7626  */
7627  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7628 
7629  /*
7630  * Now compute the number of data pages fetched during the scan.
7631  *
7632  * We assume every entry to have the same number of items, and that there
7633  * is no overlap between them. (XXX: tsvector and array opclasses collect
7634  * statistics on the frequency of individual keys; it would be nice to use
7635  * those here.)
7636  */
7637  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7638 
7639  /*
7640  * If there is a lot of overlap among the entries, in particular if one of
7641  * the entries is very frequent, the above calculation can grossly
7642  * under-estimate. As a simple cross-check, calculate a lower bound based
7643  * on the overall selectivity of the quals. At a minimum, we must read
7644  * one item pointer for each matching entry.
7645  *
7646  * The width of each item pointer varies, based on the level of
7647  * compression. We don't have statistics on that, but an average of
7648  * around 3 bytes per item is fairly typical.
7649  */
7650  dataPagesFetchedBySel = ceil(*indexSelectivity *
7651  (numTuples / (BLCKSZ / 3)));
7652  if (dataPagesFetchedBySel > dataPagesFetched)
7653  dataPagesFetched = dataPagesFetchedBySel;
7654 
7655  /* Account for cache effects, the same as above */
7656  if (outer_scans > 1 || counts.arrayScans > 1)
7657  {
7658  dataPagesFetched *= outer_scans * counts.arrayScans;
7659  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7660  (BlockNumber) numDataPages,
7661  numDataPages, root);
7662  dataPagesFetched /= outer_scans;
7663  }
7664 
7665  /* And apply random_page_cost as the cost per page */
7666  *indexTotalCost = *indexStartupCost +
7667  dataPagesFetched * spc_random_page_cost;
7668 
7669  /*
7670  * Add on index qual eval costs, much as in genericcostestimate. But we
7671  * can disregard indexorderbys, since GIN doesn't support those.
7672  */
7673  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7674  qual_op_cost = cpu_operator_cost * list_length(indexQuals);
7675 
7676  *indexStartupCost += qual_arg_cost;
7677  *indexTotalCost += qual_arg_cost;
7678  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7679  *indexPages = dataPagesFetched;
7680 }
#define NIL
Definition: pg_list.h:65
BlockNumber nEntryPages
Definition: gin.h:46
bool attHasNormalScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:7062
#define IsA(nodeptr, _type_)
Definition: nodes.h:587
IndexOptInfo * indexinfo
Definition: pathnodes.h:1245
bool attHasFullScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:7061
#define Min(x, y)
Definition: c.h:986
double partialEntries
Definition: selfuncs.c:7063
double searchEntries
Definition: selfuncs.c:7065
Oid reltablespace
Definition: pathnodes.h:839
int scale
Definition: pgbench.c:191
int64 nEntries
Definition: gin.h:48
uint32 BlockNumber
Definition: block.h:31
bool hypothetical
Definition: pathnodes.h:877
List * indexclauses
Definition: pathnodes.h:1246
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:7064
BlockNumber pages
Definition: pathnodes.h:843
RelOptInfo * rel
Definition: pathnodes.h:840
#define ERROR
Definition: elog.h:46
AttrNumber indexcol
Definition: pathnodes.h:1294
#define lfirst_node(type, lc)
Definition: pg_list.h:172
#define NoLock
Definition: lockdefs.h:34
double cpu_operator_cost
Definition: costsize.c:123
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:6268
List * indexquals
Definition: pathnodes.h:1292
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:181
Index relid
Definition: pathnodes.h:709
Expr * clause
Definition: pathnodes.h:2056
BlockNumber nPendingPages
Definition: gin.h:44
double arrayScans
Definition: selfuncs.c:7066
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:629
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, OpExpr *clause, GinQualCounts *counts)
Definition: selfuncs.c:7189
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, ScalarArrayOpExpr *clause, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7239
BlockNumber nDataPages
Definition: gin.h:47
#define Max(x, y)
Definition: c.h:980
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:6298
static int list_length(const List *l)
Definition: pg_list.h:149
BlockNumber nTotalPages
Definition: gin.h:45
int nkeycolumns
Definition: pathnodes.h:849
Cardinality tuples
Definition: pathnodes.h:844
#define nodeTag(nodeptr)
Definition: nodes.h:541
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:158
#define elog(elevel,...)
Definition: elog.h:232
int i
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:102
Definition: pg_list.h:50
double cpu_index_tuple_cost
Definition: costsize.c:122
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:132
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:840
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6570

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

6945 {
6946  IndexOptInfo *index = path->indexinfo;
6947  GenericCosts costs;
6948  Cost descentCost;
6949 
6950  MemSet(&costs, 0, sizeof(costs));
6951 
6952  genericcostestimate(root, path, loop_count, &costs);
6953 
6954  /*
6955  * We model index descent costs similarly to those for btree, but to do
6956  * that we first need an idea of the tree height. We somewhat arbitrarily
6957  * assume that the fanout is 100, meaning the tree height is at most
6958  * log100(index->pages).
6959  *
6960  * Although this computation isn't really expensive enough to require
6961  * caching, we might as well use index->tree_height to cache it.
6962  */
6963  if (index->tree_height < 0) /* unknown? */
6964  {
6965  if (index->pages > 1) /* avoid computing log(0) */
6966  index->tree_height = (int) (log(index->pages) / log(100.0));
6967  else
6968  index->tree_height = 0;
6969  }
6970 
6971  /*
6972  * Add a CPU-cost component to represent the costs of initial descent. We
6973  * just use log(N) here not log2(N) since the branching factor isn't
6974  * necessarily two anyway. As for btree, charge once per SA scan.
6975  */
6976  if (index->tuples > 1) /* avoid computing log(0) */
6977  {
6978  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6979  costs.indexStartupCost += descentCost;
6980  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6981  }
6982 
6983  /*
6984  * Likewise add a per-page charge, calculated the same as for btrees.
6985  */
6986  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6987  costs.indexStartupCost += descentCost;
6988  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6989 
6990  *indexStartupCost = costs.indexStartupCost;
6991  *indexTotalCost = costs.indexTotalCost;
6992  *indexSelectivity = costs.indexSelectivity;
6993  *indexCorrelation = costs.indexCorrelation;
6994  *indexPages = costs.numIndexPages;
6995 }
Selectivity indexSelectivity
Definition: selfuncs.h:126
IndexOptInfo * indexinfo
Definition: pathnodes.h:1245
#define MemSet(start, val, len)
Definition: c.h:1008
int tree_height
Definition: pathnodes.h:845
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:843
double num_sa_scans
Definition: selfuncs.h:133
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6352
double cpu_operator_cost
Definition: costsize.c:123
Cost indexTotalCost
Definition: selfuncs.h:125
double indexCorrelation
Definition: selfuncs.h:127
Cardinality tuples
Definition: pathnodes.h:844
Cost indexStartupCost
Definition: selfuncs.h:124
double Cost
Definition: nodes.h:670
double numIndexPages
Definition: selfuncs.h:130

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

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

Referenced by hashhandler().

6901 {
6902  GenericCosts costs;
6903 
6904  MemSet(&costs, 0, sizeof(costs));
6905 
6906  genericcostestimate(root, path, loop_count, &costs);
6907 
6908  /*
6909  * A hash index has no descent costs as such, since the index AM can go
6910  * directly to the target bucket after computing the hash value. There
6911  * are a couple of other hash-specific costs that we could conceivably add
6912  * here, though:
6913  *
6914  * Ideally we'd charge spc_random_page_cost for each page in the target
6915  * bucket, not just the numIndexPages pages that genericcostestimate
6916  * thought we'd visit. However in most cases we don't know which bucket
6917  * that will be. There's no point in considering the average bucket size
6918  * because the hash AM makes sure that's always one page.
6919  *
6920  * Likewise, we could consider charging some CPU for each index tuple in
6921  * the bucket, if we knew how many there were. But the per-tuple cost is
6922  * just a hash value comparison, not a general datatype-dependent
6923  * comparison, so any such charge ought to be quite a bit less than
6924  * cpu_operator_cost; which makes it probably not worth worrying about.
6925  *
6926  * A bigger issue is that chance hash-value collisions will result in
6927  * wasted probes into the heap. We don't currently attempt to model this
6928  * cost on the grounds that it's rare, but maybe it's not rare enough.
6929  * (Any fix for this ought to consider the generic lossy-operator problem,
6930  * though; it's not entirely hash-specific.)
6931  */
6932 
6933  *indexStartupCost = costs.indexStartupCost;
6934  *indexTotalCost = costs.indexTotalCost;
6935  *indexSelectivity = costs.indexSelectivity;
6936  *indexCorrelation = costs.indexCorrelation;
6937  *indexPages = costs.numIndexPages;
6938 }
Selectivity indexSelectivity
Definition: selfuncs.h:126
#define MemSet(start, val, len)
Definition: c.h:1008
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6352
Cost indexTotalCost
Definition: selfuncs.h:125
double indexCorrelation
Definition: selfuncs.h:127
Cost indexStartupCost
Definition: selfuncs.h:124
double numIndexPages
Definition: selfuncs.h:130

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

7002 {
7003  IndexOptInfo *index = path->indexinfo;
7004  GenericCosts costs;
7005  Cost descentCost;
7006 
7007  MemSet(&costs, 0, sizeof(costs));
7008 
7009  genericcostestimate(root, path, loop_count, &costs);
7010 
7011  /*
7012  * We model index descent costs similarly to those for btree, but to do
7013  * that we first need an idea of the tree height. We somewhat arbitrarily
7014  * assume that the fanout is 100, meaning the tree height is at most
7015  * log100(index->pages).
7016  *
7017  * Although this computation isn't really expensive enough to require
7018  * caching, we might as well use index->tree_height to cache it.
7019  */
7020  if (index->tree_height < 0) /* unknown? */
7021  {
7022  if (index->pages > 1) /* avoid computing log(0) */
7023  index->tree_height = (int) (log(index->pages) / log(100.0));
7024  else
7025  index->tree_height = 0;
7026  }
7027 
7028  /*
7029  * Add a CPU-cost component to represent the costs of initial descent. We
7030  * just use log(N) here not log2(N) since the branching factor isn't
7031  * necessarily two anyway. As for btree, charge once per SA scan.
7032  */
7033  if (index->tuples > 1) /* avoid computing log(0) */
7034  {
7035  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7036  costs.indexStartupCost += descentCost;
7037  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7038  }
7039 
7040  /*
7041  * Likewise add a per-page charge, calculated the same as for btrees.
7042  */
7043  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7044  costs.indexStartupCost += descentCost;
7045  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7046 
7047  *indexStartupCost = costs.indexStartupCost;
7048  *indexTotalCost = costs.indexTotalCost;
7049  *indexSelectivity = costs.indexSelectivity;
7050  *indexCorrelation = costs.indexCorrelation;
7051  *indexPages = costs.numIndexPages;
7052 }
Selectivity indexSelectivity
Definition: selfuncs.h:126
IndexOptInfo * indexinfo
Definition: pathnodes.h:1245
#define MemSet(start, val, len)
Definition: c.h:1008
int tree_height
Definition: pathnodes.h:845
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:843
double num_sa_scans
Definition: selfuncs.h:133
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6352
double cpu_operator_cost
Definition: costsize.c:123
Cost indexTotalCost
Definition: selfuncs.h:125
double indexCorrelation
Definition: selfuncs.h:127
Cardinality tuples
Definition: pathnodes.h:844
Cost indexStartupCost
Definition: selfuncs.h:124
double Cost
Definition: nodes.h:670
double numIndexPages
Definition: selfuncs.h:130