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

7765 {
7766  IndexOptInfo *index = path->indexinfo;
7767  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7768  double numPages = index->pages;
7769  RelOptInfo *baserel = index->rel;
7770  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7771  Cost spc_seq_page_cost;
7772  Cost spc_random_page_cost;
7773  double qual_arg_cost;
7774  double qualSelectivity;
7775  BrinStatsData statsData;
7776  double indexRanges;
7777  double minimalRanges;
7778  double estimatedRanges;
7779  double selec;
7780  Relation indexRel;
7781  ListCell *l;
7782  VariableStatData vardata;
7783 
7784  Assert(rte->rtekind == RTE_RELATION);
7785 
7786  /* fetch estimated page cost for the tablespace containing the index */
7787  get_tablespace_page_costs(index->reltablespace,
7788  &spc_random_page_cost,
7789  &spc_seq_page_cost);
7790 
7791  /*
7792  * Obtain some data from the index itself, if possible. Otherwise invent
7793  * some plausible internal statistics based on the relation page count.
7794  */
7795  if (!index->hypothetical)
7796  {
7797  /*
7798  * A lock should have already been obtained on the index in plancat.c.
7799  */
7800  indexRel = index_open(index->indexoid, NoLock);
7801  brinGetStats(indexRel, &statsData);
7802  index_close(indexRel, NoLock);
7803 
7804  /* work out the actual number of ranges in the index */
7805  indexRanges = Max(ceil((double) baserel->pages /
7806  statsData.pagesPerRange), 1.0);
7807  }
7808  else
7809  {
7810  /*
7811  * Assume default number of pages per range, and estimate the number
7812  * of ranges based on that.
7813  */
7814  indexRanges = Max(ceil((double) baserel->pages /
7816 
7818  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
7819  }
7820 
7821  /*
7822  * Compute index correlation
7823  *
7824  * Because we can use all index quals equally when scanning, we can use
7825  * the largest correlation (in absolute value) among columns used by the
7826  * query. Start at zero, the worst possible case. If we cannot find any
7827  * correlation statistics, we will keep it as 0.
7828  */
7829  *indexCorrelation = 0;
7830 
7831  foreach(l, path->indexclauses)
7832  {
7833  IndexClause *iclause = lfirst_node(IndexClause, l);
7834  AttrNumber attnum = index->indexkeys[iclause->indexcol];
7835 
7836  /* attempt to lookup stats in relation for this index column */
7837  if (attnum != 0)
7838  {
7839  /* Simple variable -- look to stats for the underlying table */
7841  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7842  {
7843  /*
7844  * The hook took control of acquiring a stats tuple. If it
7845  * did supply a tuple, it'd better have supplied a freefunc.
7846  */
7847  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7848  elog(ERROR,
7849  "no function provided to release variable stats with");
7850  }
7851  else
7852  {
7853  vardata.statsTuple =
7855  ObjectIdGetDatum(rte->relid),
7857  BoolGetDatum(false));
7858  vardata.freefunc = ReleaseSysCache;
7859  }
7860  }
7861  else
7862  {
7863  /*
7864  * Looks like we've found an expression column in the index. Let's
7865  * see if there's any stats for it.
7866  */
7867 
7868  /* get the attnum from the 0-based index. */
7869  attnum = iclause->indexcol + 1;
7870 
7871  if (get_index_stats_hook &&
7872  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7873  {
7874  /*
7875  * The hook took control of acquiring a stats tuple. If it
7876  * did supply a tuple, it'd better have supplied a freefunc.
7877  */
7878  if (HeapTupleIsValid(vardata.statsTuple) &&
7879  !vardata.freefunc)
7880  elog(ERROR, "no function provided to release variable stats with");
7881  }
7882  else
7883  {
7885  ObjectIdGetDatum(index->indexoid),
7887  BoolGetDatum(false));
7888  vardata.freefunc = ReleaseSysCache;
7889  }
7890  }
7891 
7892  if (HeapTupleIsValid(vardata.statsTuple))
7893  {
7894  AttStatsSlot sslot;
7895 
7896  if (get_attstatsslot(&sslot, vardata.statsTuple,
7897  STATISTIC_KIND_CORRELATION, InvalidOid,
7899  {
7900  double varCorrelation = 0.0;
7901 
7902  if (sslot.nnumbers > 0)
7903  varCorrelation = fabs(sslot.numbers[0]);
7904 
7905  if (varCorrelation > *indexCorrelation)
7906  *indexCorrelation = varCorrelation;
7907 
7908  free_attstatsslot(&sslot);
7909  }
7910  }
7911 
7912  ReleaseVariableStats(vardata);
7913  }
7914 
7915  qualSelectivity = clauselist_selectivity(root, indexQuals,
7916  baserel->relid,
7917  JOIN_INNER, NULL);
7918 
7919  /*
7920  * Now calculate the minimum possible ranges we could match with if all of
7921  * the rows were in the perfect order in the table's heap.
7922  */
7923  minimalRanges = ceil(indexRanges * qualSelectivity);
7924 
7925  /*
7926  * Now estimate the number of ranges that we'll touch by using the
7927  * indexCorrelation from the stats. Careful not to divide by zero (note
7928  * we're using the absolute value of the correlation).
7929  */
7930  if (*indexCorrelation < 1.0e-10)
7931  estimatedRanges = indexRanges;
7932  else
7933  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7934 
7935  /* we expect to visit this portion of the table */
7936  selec = estimatedRanges / indexRanges;
7937 
7938  CLAMP_PROBABILITY(selec);
7939 
7940  *indexSelectivity = selec;
7941 
7942  /*
7943  * Compute the index qual costs, much as in genericcostestimate, to add to
7944  * the index costs. We can disregard indexorderbys, since BRIN doesn't
7945  * support those.
7946  */
7947  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7948 
7949  /*
7950  * Compute the startup cost as the cost to read the whole revmap
7951  * sequentially, including the cost to execute the index quals.
7952  */
7953  *indexStartupCost =
7954  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7955  *indexStartupCost += qual_arg_cost;
7956 
7957  /*
7958  * To read a BRIN index there might be a bit of back and forth over
7959  * regular pages, as revmap might point to them out of sequential order;
7960  * calculate the total cost as reading the whole index in random order.
7961  */
7962  *indexTotalCost = *indexStartupCost +
7963  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7964 
7965  /*
7966  * Charge a small amount per range tuple which we expect to match to. This
7967  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7968  * will set a bit for each page in the range when we find a matching
7969  * range, so we must multiply the charge by the number of pages in the
7970  * range.
7971  */
7972  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7973  statsData.pagesPerRange;
7974 
7975  *indexPages = index->pages;
7976 }
int16 AttrNumber
Definition: attnum.h:21
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1254
#define BRIN_DEFAULT_PAGES_PER_RANGE
Definition: brin.h:38
#define REVMAP_PAGE_MAXITEMS
Definition: brin_page.h:93
#define Min(x, y)
Definition: c.h:937
#define Max(x, y)
Definition: c.h:931
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:102
double cpu_operator_cost
Definition: costsize.c:124
#define ERROR
Definition: elog.h:35
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:158
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:132
Assert(fmt[strlen(fmt) - 1] !='\n')
#define NoLock
Definition: lockdefs.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3309
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3192
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
double Cost
Definition: nodes.h:251
@ JOIN_INNER
Definition: nodes.h:293
@ RTE_RELATION
Definition: parsenodes.h:1011
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:520
int16 attnum
Definition: pg_attribute.h:83
#define lfirst_node(type, lc)
Definition: pg_list.h:174
static Datum Int16GetDatum(int16 X)
Definition: postgres.h:520
static Datum BoolGetDatum(bool X)
Definition: postgres.h:450
static Datum ObjectIdGetDatum(Oid X)
Definition: postgres.h:600
#define InvalidOid
Definition: postgres_ext.h:36
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:6352
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:146
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:6382
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:145
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:99
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:181
float4 * numbers
Definition: lsyscache.h:56
int nnumbers
Definition: lsyscache.h:57
BlockNumber revmapNumPages
Definition: brin.h:34
BlockNumber pagesPerRange
Definition: brin.h:33
AttrNumber indexcol
Definition: pathnodes.h:1648
List * indexclauses
Definition: pathnodes.h:1598
IndexOptInfo * indexinfo
Definition: pathnodes.h:1597
Definition: pg_list.h:52
RTEKind rtekind
Definition: parsenodes.h:1030
Index relid
Definition: pathnodes.h:868
BlockNumber pages
Definition: pathnodes.h:890
HeapTuple statsTuple
Definition: selfuncs.h:89
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:91
Definition: type.h:95
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1221
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:1195
@ STATRELATTINH
Definition: syscache.h:97

References 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, index_close(), index_open(), index_other_operands_eval_cost(), IndexPath::indexclauses, IndexClause::indexcol, IndexPath::indexinfo, Int16GetDatum(), InvalidOid, JOIN_INNER, lfirst_node, Max, Min, AttStatsSlot::nnumbers, NoLock, AttStatsSlot::numbers, ObjectIdGetDatum(), RelOptInfo::pages, BrinStatsData::pagesPerRange, planner_rt_fetch, ReleaseSysCache(), ReleaseVariableStats, RangeTblEntry::relid, RelOptInfo::relid, REVMAP_PAGE_MAXITEMS, BrinStatsData::revmapNumPages, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

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

6679 {
6680  IndexOptInfo *index = path->indexinfo;
6681  GenericCosts costs = {0};
6682  Oid relid;
6683  AttrNumber colnum;
6684  VariableStatData vardata = {0};
6685  double numIndexTuples;
6686  Cost descentCost;
6687  List *indexBoundQuals;
6688  int indexcol;
6689  bool eqQualHere;
6690  bool found_saop;
6691  bool found_is_null_op;
6692  double num_sa_scans;
6693  ListCell *lc;
6694 
6695  /*
6696  * For a btree scan, only leading '=' quals plus inequality quals for the
6697  * immediately next attribute contribute to index selectivity (these are
6698  * the "boundary quals" that determine the starting and stopping points of
6699  * the index scan). Additional quals can suppress visits to the heap, so
6700  * it's OK to count them in indexSelectivity, but they should not count
6701  * for estimating numIndexTuples. So we must examine the given indexquals
6702  * to find out which ones count as boundary quals. We rely on the
6703  * knowledge that they are given in index column order.
6704  *
6705  * For a RowCompareExpr, we consider only the first column, just as
6706  * rowcomparesel() does.
6707  *
6708  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6709  * index scans not one, but the ScalarArrayOpExpr's operator can be
6710  * considered to act the same as it normally does.
6711  */
6712  indexBoundQuals = NIL;
6713  indexcol = 0;
6714  eqQualHere = false;
6715  found_saop = false;
6716  found_is_null_op = false;
6717  num_sa_scans = 1;
6718  foreach(lc, path->indexclauses)
6719  {
6720  IndexClause *iclause = lfirst_node(IndexClause, lc);
6721  ListCell *lc2;
6722 
6723  if (indexcol != iclause->indexcol)
6724  {
6725  /* Beginning of a new column's quals */
6726  if (!eqQualHere)
6727  break; /* done if no '=' qual for indexcol */
6728  eqQualHere = false;
6729  indexcol++;
6730  if (indexcol != iclause->indexcol)
6731  break; /* no quals at all for indexcol */
6732  }
6733 
6734  /* Examine each indexqual associated with this index clause */
6735  foreach(lc2, iclause->indexquals)
6736  {
6737  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6738  Expr *clause = rinfo->clause;
6739  Oid clause_op = InvalidOid;
6740  int op_strategy;
6741 
6742  if (IsA(clause, OpExpr))
6743  {
6744  OpExpr *op = (OpExpr *) clause;
6745 
6746  clause_op = op->opno;
6747  }
6748  else if (IsA(clause, RowCompareExpr))
6749  {
6750  RowCompareExpr *rc = (RowCompareExpr *) clause;
6751 
6752  clause_op = linitial_oid(rc->opnos);
6753  }
6754  else if (IsA(clause, ScalarArrayOpExpr))
6755  {
6756  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6757  Node *other_operand = (Node *) lsecond(saop->args);
6758  int alength = estimate_array_length(other_operand);
6759 
6760  clause_op = saop->opno;
6761  found_saop = true;
6762  /* count number of SA scans induced by indexBoundQuals only */
6763  if (alength > 1)
6764  num_sa_scans *= alength;
6765  }
6766  else if (IsA(clause, NullTest))
6767  {
6768  NullTest *nt = (NullTest *) clause;
6769 
6770  if (nt->nulltesttype == IS_NULL)
6771  {
6772  found_is_null_op = true;
6773  /* IS NULL is like = for selectivity purposes */
6774  eqQualHere = true;
6775  }
6776  }
6777  else
6778  elog(ERROR, "unsupported indexqual type: %d",
6779  (int) nodeTag(clause));
6780 
6781  /* check for equality operator */
6782  if (OidIsValid(clause_op))
6783  {
6784  op_strategy = get_op_opfamily_strategy(clause_op,
6785  index->opfamily[indexcol]);
6786  Assert(op_strategy != 0); /* not a member of opfamily?? */
6787  if (op_strategy == BTEqualStrategyNumber)
6788  eqQualHere = true;
6789  }
6790 
6791  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6792  }
6793  }
6794 
6795  /*
6796  * If index is unique and we found an '=' clause for each column, we can
6797  * just assume numIndexTuples = 1 and skip the expensive
6798  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6799  * NullTest invalidates that theory, even though it sets eqQualHere.
6800  */
6801  if (index->unique &&
6802  indexcol == index->nkeycolumns - 1 &&
6803  eqQualHere &&
6804  !found_saop &&
6805  !found_is_null_op)
6806  numIndexTuples = 1.0;
6807  else
6808  {
6809  List *selectivityQuals;
6810  Selectivity btreeSelectivity;
6811 
6812  /*
6813  * If the index is partial, AND the index predicate with the
6814  * index-bound quals to produce a more accurate idea of the number of
6815  * rows covered by the bound conditions.
6816  */
6817  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
6818 
6819  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6820  index->rel->relid,
6821  JOIN_INNER,
6822  NULL);
6823  numIndexTuples = btreeSelectivity * index->rel->tuples;
6824 
6825  /*
6826  * As in genericcostestimate(), we have to adjust for any
6827  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6828  * to integer.
6829  */
6830  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6831  }
6832 
6833  /*
6834  * Now do generic index cost estimation.
6835  */
6836  costs.numIndexTuples = numIndexTuples;
6837 
6838  genericcostestimate(root, path, loop_count, &costs);
6839 
6840  /*
6841  * Add a CPU-cost component to represent the costs of initial btree
6842  * descent. We don't charge any I/O cost for touching upper btree levels,
6843  * since they tend to stay in cache, but we still have to do about log2(N)
6844  * comparisons to descend a btree of N leaf tuples. We charge one
6845  * cpu_operator_cost per comparison.
6846  *
6847  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6848  * ones after the first one are not startup cost so far as the overall
6849  * plan is concerned, so add them only to "total" cost.
6850  */
6851  if (index->tuples > 1) /* avoid computing log(0) */
6852  {
6853  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6854  costs.indexStartupCost += descentCost;
6855  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6856  }
6857 
6858  /*
6859  * Even though we're not charging I/O cost for touching upper btree pages,
6860  * it's still reasonable to charge some CPU cost per page descended
6861  * through. Moreover, if we had no such charge at all, bloated indexes
6862  * would appear to have the same search cost as unbloated ones, at least
6863  * in cases where only a single leaf page is expected to be visited. This
6864  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6865  * touched. The number of such pages is btree tree height plus one (ie,
6866  * we charge for the leaf page too). As above, charge once per SA scan.
6867  */
6868  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6869  costs.indexStartupCost += descentCost;
6870  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6871 
6872  /*
6873  * If we can get an estimate of the first column's ordering correlation C
6874  * from pg_statistic, estimate the index correlation as C for a
6875  * single-column index, or C * 0.75 for multiple columns. (The idea here
6876  * is that multiple columns dilute the importance of the first column's
6877  * ordering, but don't negate it entirely. Before 8.0 we divided the
6878  * correlation by the number of columns, but that seems too strong.)
6879  */
6880  if (index->indexkeys[0] != 0)
6881  {
6882  /* Simple variable --- look to stats for the underlying table */
6883  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6884 
6885  Assert(rte->rtekind == RTE_RELATION);
6886  relid = rte->relid;
6887  Assert(relid != InvalidOid);
6888  colnum = index->indexkeys[0];
6889 
6891  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6892  {
6893  /*
6894  * The hook took control of acquiring a stats tuple. If it did
6895  * supply a tuple, it'd better have supplied a freefunc.
6896  */
6897  if (HeapTupleIsValid(vardata.statsTuple) &&
6898  !vardata.freefunc)
6899  elog(ERROR, "no function provided to release variable stats with");
6900  }
6901  else
6902  {
6904  ObjectIdGetDatum(relid),
6905  Int16GetDatum(colnum),
6906  BoolGetDatum(rte->inh));
6907  vardata.freefunc = ReleaseSysCache;
6908  }
6909  }
6910  else
6911  {
6912  /* Expression --- maybe there are stats for the index itself */
6913  relid = index->indexoid;
6914  colnum = 1;
6915 
6916  if (get_index_stats_hook &&
6917  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6918  {
6919  /*
6920  * The hook took control of acquiring a stats tuple. If it did
6921  * 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(relid),
6931  Int16GetDatum(colnum),
6932  BoolGetDatum(false));
6933  vardata.freefunc = ReleaseSysCache;
6934  }
6935  }
6936 
6937  if (HeapTupleIsValid(vardata.statsTuple))
6938  {
6939  Oid sortop;
6940  AttStatsSlot sslot;
6941 
6942  sortop = get_opfamily_member(index->opfamily[0],
6943  index->opcintype[0],
6944  index->opcintype[0],
6946  if (OidIsValid(sortop) &&
6947  get_attstatsslot(&sslot, vardata.statsTuple,
6948  STATISTIC_KIND_CORRELATION, sortop,
6950  {
6951  double varCorrelation;
6952 
6953  Assert(sslot.nnumbers == 1);
6954  varCorrelation = sslot.numbers[0];
6955 
6956  if (index->reverse_sort[0])
6957  varCorrelation = -varCorrelation;
6958 
6959  if (index->nkeycolumns > 1)
6960  costs.indexCorrelation = varCorrelation * 0.75;
6961  else
6962  costs.indexCorrelation = varCorrelation;
6963 
6964  free_attstatsslot(&sslot);
6965  }
6966  }
6967 
6968  ReleaseVariableStats(vardata);
6969 
6970  *indexStartupCost = costs.indexStartupCost;
6971  *indexTotalCost = costs.indexTotalCost;
6972  *indexSelectivity = costs.indexSelectivity;
6973  *indexCorrelation = costs.indexCorrelation;
6974  *indexPages = costs.numIndexPages;
6975 }
#define OidIsValid(objectId)
Definition: c.h:711
List * lappend(List *list, void *datum)
Definition: list.c:338
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:82
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:165
#define IsA(nodeptr, _type_)
Definition: nodes.h:168
#define nodeTag(nodeptr)
Definition: nodes.h:122
double Selectivity
Definition: nodes.h:250
#define NIL
Definition: pg_list.h:66
#define lsecond(l)
Definition: pg_list.h:181
#define linitial_oid(l)
Definition: pg_list.h:178
unsigned int Oid
Definition: postgres_ext.h:31
@ IS_NULL
Definition: primnodes.h:1359
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2133
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6436
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6654
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTEqualStrategyNumber
Definition: stratnum.h:31
Selectivity indexSelectivity
Definition: selfuncs.h:124
Cost indexStartupCost
Definition: selfuncs.h:122
double indexCorrelation
Definition: selfuncs.h:125
double num_sa_scans
Definition: selfuncs.h:131
Cost indexTotalCost
Definition: selfuncs.h:123
double numIndexPages
Definition: selfuncs.h:128
double numIndexTuples
Definition: selfuncs.h:129
List * indexquals
Definition: pathnodes.h:1646
Definition: nodes.h:118
NullTestType nulltesttype
Definition: primnodes.h:1366
Oid opno
Definition: primnodes.h:648
Expr * clause
Definition: pathnodes.h:2432

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, IndexClause::indexquals, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum(), InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst_node, linitial_oid, lsecond, NIL, AttStatsSlot::nnumbers, nodeTag, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum(), OidIsValid, OpExpr::opno, ScalarArrayOpExpr::opno, RowCompareExpr::opnos, planner_rt_fetch, ReleaseSysCache(), ReleaseVariableStats, RangeTblEntry::relid, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, and VariableStatData::statsTuple.

Referenced by bthandler().

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

7434 {
7435  IndexOptInfo *index = path->indexinfo;
7436  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7437  List *selectivityQuals;
7438  double numPages = index->pages,
7439  numTuples = index->tuples;
7440  double numEntryPages,
7441  numDataPages,
7442  numPendingPages,
7443  numEntries;
7444  GinQualCounts counts;
7445  bool matchPossible;
7446  bool fullIndexScan;
7447  double partialScale;
7448  double entryPagesFetched,
7449  dataPagesFetched,
7450  dataPagesFetchedBySel;
7451  double qual_op_cost,
7452  qual_arg_cost,
7453  spc_random_page_cost,
7454  outer_scans;
7455  Relation indexRel;
7456  GinStatsData ginStats;
7457  ListCell *lc;
7458  int i;
7459 
7460  /*
7461  * Obtain statistical information from the meta page, if possible. Else
7462  * set ginStats to zeroes, and we'll cope below.
7463  */
7464  if (!index->hypothetical)
7465  {
7466  /* Lock should have already been obtained in plancat.c */
7467  indexRel = index_open(index->indexoid, NoLock);
7468  ginGetStats(indexRel, &ginStats);
7469  index_close(indexRel, NoLock);
7470  }
7471  else
7472  {
7473  memset(&ginStats, 0, sizeof(ginStats));
7474  }
7475 
7476  /*
7477  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7478  * trusted, but the other fields are data as of the last VACUUM. We can
7479  * scale them up to account for growth since then, but that method only
7480  * goes so far; in the worst case, the stats might be for a completely
7481  * empty index, and scaling them will produce pretty bogus numbers.
7482  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7483  * it's grown more than that, fall back to estimating things only from the
7484  * assumed-accurate index size. But we'll trust nPendingPages in any case
7485  * so long as it's not clearly insane, ie, more than the index size.
7486  */
7487  if (ginStats.nPendingPages < numPages)
7488  numPendingPages = ginStats.nPendingPages;
7489  else
7490  numPendingPages = 0;
7491 
7492  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7493  ginStats.nTotalPages > numPages / 4 &&
7494  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7495  {
7496  /*
7497  * OK, the stats seem close enough to sane to be trusted. But we
7498  * still need to scale them by the ratio numPages / nTotalPages to
7499  * account for growth since the last VACUUM.
7500  */
7501  double scale = numPages / ginStats.nTotalPages;
7502 
7503  numEntryPages = ceil(ginStats.nEntryPages * scale);
7504  numDataPages = ceil(ginStats.nDataPages * scale);
7505  numEntries = ceil(ginStats.nEntries * scale);
7506  /* ensure we didn't round up too much */
7507  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7508  numDataPages = Min(numDataPages,
7509  numPages - numPendingPages - numEntryPages);
7510  }
7511  else
7512  {
7513  /*
7514  * We might get here because it's a hypothetical index, or an index
7515  * created pre-9.1 and never vacuumed since upgrading (in which case
7516  * its stats would read as zeroes), or just because it's grown too
7517  * much since the last VACUUM for us to put our faith in scaling.
7518  *
7519  * Invent some plausible internal statistics based on the index page
7520  * count (and clamp that to at least 10 pages, just in case). We
7521  * estimate that 90% of the index is entry pages, and the rest is data
7522  * pages. Estimate 100 entries per entry page; this is rather bogus
7523  * since it'll depend on the size of the keys, but it's more robust
7524  * than trying to predict the number of entries per heap tuple.
7525  */
7526  numPages = Max(numPages, 10);
7527  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7528  numDataPages = numPages - numPendingPages - numEntryPages;
7529  numEntries = floor(numEntryPages * 100);
7530  }
7531 
7532  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7533  if (numEntries < 1)
7534  numEntries = 1;
7535 
7536  /*
7537  * If the index is partial, AND the index predicate with the index-bound
7538  * quals to produce a more accurate idea of the number of rows covered by
7539  * the bound conditions.
7540  */
7541  selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
7542 
7543  /* Estimate the fraction of main-table tuples that will be visited */
7544  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7545  index->rel->relid,
7546  JOIN_INNER,
7547  NULL);
7548 
7549  /* fetch estimated page cost for tablespace containing index */
7550  get_tablespace_page_costs(index->reltablespace,
7551  &spc_random_page_cost,
7552  NULL);
7553 
7554  /*
7555  * Generic assumption about index correlation: there isn't any.
7556  */
7557  *indexCorrelation = 0.0;
7558 
7559  /*
7560  * Examine quals to estimate number of search entries & partial matches
7561  */
7562  memset(&counts, 0, sizeof(counts));
7563  counts.arrayScans = 1;
7564  matchPossible = true;
7565 
7566  foreach(lc, path->indexclauses)
7567  {
7568  IndexClause *iclause = lfirst_node(IndexClause, lc);
7569  ListCell *lc2;
7570 
7571  foreach(lc2, iclause->indexquals)
7572  {
7573  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
7574  Expr *clause = rinfo->clause;
7575 
7576  if (IsA(clause, OpExpr))
7577  {
7578  matchPossible = gincost_opexpr(root,
7579  index,
7580  iclause->indexcol,
7581  (OpExpr *) clause,
7582  &counts);
7583  if (!matchPossible)
7584  break;
7585  }
7586  else if (IsA(clause, ScalarArrayOpExpr))
7587  {
7588  matchPossible = gincost_scalararrayopexpr(root,
7589  index,
7590  iclause->indexcol,
7591  (ScalarArrayOpExpr *) clause,
7592  numEntries,
7593  &counts);
7594  if (!matchPossible)
7595  break;
7596  }
7597  else
7598  {
7599  /* shouldn't be anything else for a GIN index */
7600  elog(ERROR, "unsupported GIN indexqual type: %d",
7601  (int) nodeTag(clause));
7602  }
7603  }
7604  }
7605 
7606  /* Fall out if there were any provably-unsatisfiable quals */
7607  if (!matchPossible)
7608  {
7609  *indexStartupCost = 0;
7610  *indexTotalCost = 0;
7611  *indexSelectivity = 0;
7612  return;
7613  }
7614 
7615  /*
7616  * If attribute has a full scan and at the same time doesn't have normal
7617  * scan, then we'll have to scan all non-null entries of that attribute.
7618  * Currently, we don't have per-attribute statistics for GIN. Thus, we
7619  * must assume the whole GIN index has to be scanned in this case.
7620  */
7621  fullIndexScan = false;
7622  for (i = 0; i < index->nkeycolumns; i++)
7623  {
7624  if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
7625  {
7626  fullIndexScan = true;
7627  break;
7628  }
7629  }
7630 
7631  if (fullIndexScan || indexQuals == NIL)
7632  {
7633  /*
7634  * Full index scan will be required. We treat this as if every key in
7635  * the index had been listed in the query; is that reasonable?
7636  */
7637  counts.partialEntries = 0;
7638  counts.exactEntries = numEntries;
7639  counts.searchEntries = numEntries;
7640  }
7641 
7642  /* Will we have more than one iteration of a nestloop scan? */
7643  outer_scans = loop_count;
7644 
7645  /*
7646  * Compute cost to begin scan, first of all, pay attention to pending
7647  * list.
7648  */
7649  entryPagesFetched = numPendingPages;
7650 
7651  /*
7652  * Estimate number of entry pages read. We need to do
7653  * counts.searchEntries searches. Use a power function as it should be,
7654  * but tuples on leaf pages usually is much greater. Here we include all
7655  * searches in entry tree, including search of first entry in partial
7656  * match algorithm
7657  */
7658  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7659 
7660  /*
7661  * Add an estimate of entry pages read by partial match algorithm. It's a
7662  * scan over leaf pages in entry tree. We haven't any useful stats here,
7663  * so estimate it as proportion. Because counts.partialEntries is really
7664  * pretty bogus (see code above), it's possible that it is more than
7665  * numEntries; clamp the proportion to ensure sanity.
7666  */
7667  partialScale = counts.partialEntries / numEntries;
7668  partialScale = Min(partialScale, 1.0);
7669 
7670  entryPagesFetched += ceil(numEntryPages * partialScale);
7671 
7672  /*
7673  * Partial match algorithm reads all data pages before doing actual scan,
7674  * so it's a startup cost. Again, we haven't any useful stats here, so
7675  * estimate it as proportion.
7676  */
7677  dataPagesFetched = ceil(numDataPages * partialScale);
7678 
7679  /*
7680  * Calculate cache effects if more than one scan due to nestloops or array
7681  * quals. The result is pro-rated per nestloop scan, but the array qual
7682  * factor shouldn't be pro-rated (compare genericcostestimate).
7683  */
7684  if (outer_scans > 1 || counts.arrayScans > 1)
7685  {
7686  entryPagesFetched *= outer_scans * counts.arrayScans;
7687  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7688  (BlockNumber) numEntryPages,
7689  numEntryPages, root);
7690  entryPagesFetched /= outer_scans;
7691  dataPagesFetched *= outer_scans * counts.arrayScans;
7692  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7693  (BlockNumber) numDataPages,
7694  numDataPages, root);
7695  dataPagesFetched /= outer_scans;
7696  }
7697 
7698  /*
7699  * Here we use random page cost because logically-close pages could be far
7700  * apart on disk.
7701  */
7702  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7703 
7704  /*
7705  * Now compute the number of data pages fetched during the scan.
7706  *
7707  * We assume every entry to have the same number of items, and that there
7708  * is no overlap between them. (XXX: tsvector and array opclasses collect
7709  * statistics on the frequency of individual keys; it would be nice to use
7710  * those here.)
7711  */
7712  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7713 
7714  /*
7715  * If there is a lot of overlap among the entries, in particular if one of
7716  * the entries is very frequent, the above calculation can grossly
7717  * under-estimate. As a simple cross-check, calculate a lower bound based
7718  * on the overall selectivity of the quals. At a minimum, we must read
7719  * one item pointer for each matching entry.
7720  *
7721  * The width of each item pointer varies, based on the level of
7722  * compression. We don't have statistics on that, but an average of
7723  * around 3 bytes per item is fairly typical.
7724  */
7725  dataPagesFetchedBySel = ceil(*indexSelectivity *
7726  (numTuples / (BLCKSZ / 3)));
7727  if (dataPagesFetchedBySel > dataPagesFetched)
7728  dataPagesFetched = dataPagesFetchedBySel;
7729 
7730  /* Account for cache effects, the same as above */
7731  if (outer_scans > 1 || counts.arrayScans > 1)
7732  {
7733  dataPagesFetched *= outer_scans * counts.arrayScans;
7734  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7735  (BlockNumber) numDataPages,
7736  numDataPages, root);
7737  dataPagesFetched /= outer_scans;
7738  }
7739 
7740  /* And apply random_page_cost as the cost per page */
7741  *indexTotalCost = *indexStartupCost +
7742  dataPagesFetched * spc_random_page_cost;
7743 
7744  /*
7745  * Add on index qual eval costs, much as in genericcostestimate. But we
7746  * can disregard indexorderbys, since GIN doesn't support those.
7747  */
7748  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7749  qual_op_cost = cpu_operator_cost * list_length(indexQuals);
7750 
7751  *indexStartupCost += qual_arg_cost;
7752  *indexTotalCost += qual_arg_cost;
7753  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7754  *indexPages = dataPagesFetched;
7755 }
uint32 BlockNumber
Definition: block.h:31
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:868
double cpu_index_tuple_cost
Definition: costsize.c:123
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:629
int i
Definition: isn.c:73
static int list_length(const List *l)
Definition: pg_list.h:150
int scale
Definition: pgbench.c:190
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, ScalarArrayOpExpr *clause, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7314
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, OpExpr *clause, GinQualCounts *counts)
Definition: selfuncs.c:7264
bool attHasNormalScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:7137
double exactEntries
Definition: selfuncs.c:7139
double arrayScans
Definition: selfuncs.c:7141
double partialEntries
Definition: selfuncs.c:7138
bool attHasFullScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:7136
double searchEntries
Definition: selfuncs.c:7140
BlockNumber nDataPages
Definition: gin.h:47
BlockNumber nPendingPages
Definition: gin.h:44
BlockNumber nEntryPages
Definition: gin.h:46
int64 nEntries
Definition: gin.h:48
BlockNumber nTotalPages
Definition: gin.h:45

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(), i, index_close(), index_open(), index_other_operands_eval_cost(), index_pages_fetched(), IndexPath::indexclauses, IndexClause::indexcol, IndexPath::indexinfo, IndexClause::indexquals, IsA, JOIN_INNER, lfirst_node, list_length(), Max, Min, GinStatsData::nDataPages, GinStatsData::nEntries, GinStatsData::nEntryPages, NIL, nodeTag, NoLock, GinStatsData::nPendingPages, GinStatsData::nTotalPages, GinQualCounts::partialEntries, scale, and GinQualCounts::searchEntries.

Referenced by ginhandler().

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

7024 {
7025  IndexOptInfo *index = path->indexinfo;
7026  GenericCosts costs = {0};
7027  Cost descentCost;
7028 
7029  genericcostestimate(root, path, loop_count, &costs);
7030 
7031  /*
7032  * We model index descent costs similarly to those for btree, but to do
7033  * that we first need an idea of the tree height. We somewhat arbitrarily
7034  * assume that the fanout is 100, meaning the tree height is at most
7035  * log100(index->pages).
7036  *
7037  * Although this computation isn't really expensive enough to require
7038  * caching, we might as well use index->tree_height to cache it.
7039  */
7040  if (index->tree_height < 0) /* unknown? */
7041  {
7042  if (index->pages > 1) /* avoid computing log(0) */
7043  index->tree_height = (int) (log(index->pages) / log(100.0));
7044  else
7045  index->tree_height = 0;
7046  }
7047 
7048  /*
7049  * Add a CPU-cost component to represent the costs of initial descent. We
7050  * just use log(N) here not log2(N) since the branching factor isn't
7051  * necessarily two anyway. As for btree, charge once per SA scan.
7052  */
7053  if (index->tuples > 1) /* avoid computing log(0) */
7054  {
7055  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7056  costs.indexStartupCost += descentCost;
7057  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7058  }
7059 
7060  /*
7061  * Likewise add a per-page charge, calculated the same as for btrees.
7062  */
7063  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7064  costs.indexStartupCost += descentCost;
7065  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7066 
7067  *indexStartupCost = costs.indexStartupCost;
7068  *indexTotalCost = costs.indexTotalCost;
7069  *indexSelectivity = costs.indexSelectivity;
7070  *indexCorrelation = costs.indexCorrelation;
7071  *indexPages = costs.numIndexPages;
7072 }

References cpu_operator_cost, genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, GenericCosts::num_sa_scans, and GenericCosts::numIndexPages.

Referenced by gisthandler().

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

6982 {
6983  GenericCosts costs = {0};
6984 
6985  genericcostestimate(root, path, loop_count, &costs);
6986 
6987  /*
6988  * A hash index has no descent costs as such, since the index AM can go
6989  * directly to the target bucket after computing the hash value. There
6990  * are a couple of other hash-specific costs that we could conceivably add
6991  * here, though:
6992  *
6993  * Ideally we'd charge spc_random_page_cost for each page in the target
6994  * bucket, not just the numIndexPages pages that genericcostestimate
6995  * thought we'd visit. However in most cases we don't know which bucket
6996  * that will be. There's no point in considering the average bucket size
6997  * because the hash AM makes sure that's always one page.
6998  *
6999  * Likewise, we could consider charging some CPU for each index tuple in
7000  * the bucket, if we knew how many there were. But the per-tuple cost is
7001  * just a hash value comparison, not a general datatype-dependent
7002  * comparison, so any such charge ought to be quite a bit less than
7003  * cpu_operator_cost; which makes it probably not worth worrying about.
7004  *
7005  * A bigger issue is that chance hash-value collisions will result in
7006  * wasted probes into the heap. We don't currently attempt to model this
7007  * cost on the grounds that it's rare, but maybe it's not rare enough.
7008  * (Any fix for this ought to consider the generic lossy-operator problem,
7009  * though; it's not entirely hash-specific.)
7010  */
7011 
7012  *indexStartupCost = costs.indexStartupCost;
7013  *indexTotalCost = costs.indexTotalCost;
7014  *indexSelectivity = costs.indexSelectivity;
7015  *indexCorrelation = costs.indexCorrelation;
7016  *indexPages = costs.numIndexPages;
7017 }

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

Referenced by hashhandler().

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

7079 {
7080  IndexOptInfo *index = path->indexinfo;
7081  GenericCosts costs = {0};
7082  Cost descentCost;
7083 
7084  genericcostestimate(root, path, loop_count, &costs);
7085 
7086  /*
7087  * We model index descent costs similarly to those for btree, but to do
7088  * that we first need an idea of the tree height. We somewhat arbitrarily
7089  * assume that the fanout is 100, meaning the tree height is at most
7090  * log100(index->pages).
7091  *
7092  * Although this computation isn't really expensive enough to require
7093  * caching, we might as well use index->tree_height to cache it.
7094  */
7095  if (index->tree_height < 0) /* unknown? */
7096  {
7097  if (index->pages > 1) /* avoid computing log(0) */
7098  index->tree_height = (int) (log(index->pages) / log(100.0));
7099  else
7100  index->tree_height = 0;
7101  }
7102 
7103  /*
7104  * Add a CPU-cost component to represent the costs of initial descent. We
7105  * just use log(N) here not log2(N) since the branching factor isn't
7106  * necessarily two anyway. As for btree, charge once per SA scan.
7107  */
7108  if (index->tuples > 1) /* avoid computing log(0) */
7109  {
7110  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7111  costs.indexStartupCost += descentCost;
7112  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7113  }
7114 
7115  /*
7116  * Likewise add a per-page charge, calculated the same as for btrees.
7117  */
7118  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7119  costs.indexStartupCost += descentCost;
7120  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7121 
7122  *indexStartupCost = costs.indexStartupCost;
7123  *indexTotalCost = costs.indexTotalCost;
7124  *indexSelectivity = costs.indexSelectivity;
7125  *indexCorrelation = costs.indexCorrelation;
7126  *indexPages = costs.numIndexPages;
7127 }

References cpu_operator_cost, genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, GenericCosts::num_sa_scans, and GenericCosts::numIndexPages.

Referenced by spghandler().