PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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

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

Definition at line 7762 of file selfuncs.c.

References Abs, AccessShareLock, Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, brinGetStats(), CLAMP_PROBABILITY, clauselist_selectivity(), cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, free_attstatsslot(), VariableStatData::freefunc, get_attstatsslot(), get_index_stats_hook, get_relation_stats_hook, get_tablespace_page_costs(), HeapTupleIsValid, index_close(), index_open(), IndexQualInfo::indexcol, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, IndexPath::indexquals, Int16GetDatum, InvalidOid, JOIN_INNER, lfirst, Max, Min, AttStatsSlot::nnumbers, NULL, AttStatsSlot::numbers, ObjectIdGetDatum, orderby_operands_eval_cost(), other_operands_eval_cost(), RelOptInfo::pages, IndexOptInfo::pages, BrinStatsData::pagesPerRange, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, IndexOptInfo::reltablespace, BrinStatsData::revmapNumPages, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3, STATISTIC_KIND_CORRELATION, STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

7766 {
7767  IndexOptInfo *index = path->indexinfo;
7768  List *indexQuals = path->indexquals;
7769  double numPages = index->pages;
7770  RelOptInfo *baserel = index->rel;
7771  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7772  List *qinfos;
7773  Cost spc_seq_page_cost;
7774  Cost spc_random_page_cost;
7775  double qual_arg_cost;
7776  double qualSelectivity;
7777  BrinStatsData statsData;
7778  double indexRanges;
7779  double minimalRanges;
7780  double estimatedRanges;
7781  double selec;
7782  Relation indexRel;
7783  ListCell *l;
7784  VariableStatData vardata;
7785 
7786  Assert(rte->rtekind == RTE_RELATION);
7787 
7788  /* fetch estimated page cost for the tablespace containing the index */
7790  &spc_random_page_cost,
7791  &spc_seq_page_cost);
7792 
7793  /*
7794  * Obtain some data from the index itself.
7795  */
7796  indexRel = index_open(index->indexoid, AccessShareLock);
7797  brinGetStats(indexRel, &statsData);
7798  index_close(indexRel, AccessShareLock);
7799 
7800  /*
7801  * Compute index correlation
7802  *
7803  * Because we can use all index quals equally when scanning, we can use
7804  * the largest correlation (in absolute value) among columns used by the
7805  * query. Start at zero, the worst possible case. If we cannot find any
7806  * correlation statistics, we will keep it as 0.
7807  */
7808  *indexCorrelation = 0;
7809 
7810  qinfos = deconstruct_indexquals(path);
7811  foreach(l, qinfos)
7812  {
7813  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7814  AttrNumber attnum = index->indexkeys[qinfo->indexcol];
7815 
7816  /* attempt to lookup stats in relation for this index column */
7817  if (attnum != 0)
7818  {
7819  /* Simple variable -- look to stats for the underlying table */
7821  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7822  {
7823  /*
7824  * The hook took control of acquiring a stats tuple. If it
7825  * did supply a tuple, it'd better have supplied a freefunc.
7826  */
7827  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7828  elog(ERROR,
7829  "no function provided to release variable stats with");
7830  }
7831  else
7832  {
7833  vardata.statsTuple =
7835  ObjectIdGetDatum(rte->relid),
7836  Int16GetDatum(attnum),
7837  BoolGetDatum(false));
7838  vardata.freefunc = ReleaseSysCache;
7839  }
7840  }
7841  else
7842  {
7843  /*
7844  * Looks like we've found an expression column in the index. Let's
7845  * see if there's any stats for it.
7846  */
7847 
7848  /* get the attnum from the 0-based index. */
7849  attnum = qinfo->indexcol + 1;
7850 
7851  if (get_index_stats_hook &&
7852  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7853  {
7854  /*
7855  * The hook took control of acquiring a stats tuple. If it
7856  * did supply a tuple, it'd better have supplied a freefunc.
7857  */
7858  if (HeapTupleIsValid(vardata.statsTuple) &&
7859  !vardata.freefunc)
7860  elog(ERROR, "no function provided to release variable stats with");
7861  }
7862  else
7863  {
7865  ObjectIdGetDatum(index->indexoid),
7866  Int16GetDatum(attnum),
7867  BoolGetDatum(false));
7868  vardata.freefunc = ReleaseSysCache;
7869  }
7870  }
7871 
7872  if (HeapTupleIsValid(vardata.statsTuple))
7873  {
7874  AttStatsSlot sslot;
7875 
7876  if (get_attstatsslot(&sslot, vardata.statsTuple,
7879  {
7880  double varCorrelation = 0.0;
7881 
7882  if (sslot.nnumbers > 0)
7883  varCorrelation = Abs(sslot.numbers[0]);
7884 
7885  if (varCorrelation > *indexCorrelation)
7886  *indexCorrelation = varCorrelation;
7887 
7888  free_attstatsslot(&sslot);
7889  }
7890  }
7891 
7892  ReleaseVariableStats(vardata);
7893  }
7894 
7895  qualSelectivity = clauselist_selectivity(root, indexQuals,
7896  baserel->relid,
7897  JOIN_INNER, NULL);
7898 
7899  /* work out the actual number of ranges in the index */
7900  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
7901  1.0);
7902 
7903  /*
7904  * Now calculate the minimum possible ranges we could match with if all of
7905  * the rows were in the perfect order in the table's heap.
7906  */
7907  minimalRanges = ceil(indexRanges * qualSelectivity);
7908 
7909  /*
7910  * Now estimate the number of ranges that we'll touch by using the
7911  * indexCorrelation from the stats. Careful not to divide by zero (note
7912  * we're using the absolute value of the correlation).
7913  */
7914  if (*indexCorrelation < 1.0e-10)
7915  estimatedRanges = indexRanges;
7916  else
7917  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7918 
7919  /* we expect to visit this portion of the table */
7920  selec = estimatedRanges / indexRanges;
7921 
7922  CLAMP_PROBABILITY(selec);
7923 
7924  *indexSelectivity = selec;
7925 
7926  /*
7927  * Compute the index qual costs, much as in genericcostestimate, to add to
7928  * the index costs.
7929  */
7930  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7931  orderby_operands_eval_cost(root, path);
7932 
7933  /*
7934  * Compute the startup cost as the cost to read the whole revmap
7935  * sequentially, including the cost to execute the index quals.
7936  */
7937  *indexStartupCost =
7938  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7939  *indexStartupCost += qual_arg_cost;
7940 
7941  /*
7942  * To read a BRIN index there might be a bit of back and forth over
7943  * regular pages, as revmap might point to them out of sequential order;
7944  * calculate the total cost as reading the whole index in random order.
7945  */
7946  *indexTotalCost = *indexStartupCost +
7947  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7948 
7949  /*
7950  * Charge a small amount per range tuple which we expect to match to. This
7951  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7952  * will set a bit for each page in the range when we find a matching
7953  * range, so we must multiply the charge by the number of pages in the
7954  * range.
7955  */
7956  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7957  statsData.pagesPerRange;
7958 
7959  *indexPages = index->pages;
7960 }
IndexOptInfo * indexinfo
Definition: relation.h:1031
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
#define Min(x, y)
Definition: c.h:806
#define Int16GetDatum(X)
Definition: postgres.h:457
#define AccessShareLock
Definition: lockdefs.h:36
Oid reltablespace
Definition: relation.h:632
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6387
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6292
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6412
#define Abs(x)
Definition: c.h:812
Definition: type.h:89
BlockNumber pages
Definition: relation.h:636
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
List * indexquals
Definition: relation.h:1033
RelOptInfo * rel
Definition: relation.h:633
#define planner_rt_fetch(rti, root)
Definition: relation.h:325
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:513
#define ERROR
Definition: elog.h:43
#define STATISTIC_KIND_CORRELATION
Definition: pg_statistic.h:233
float4 * numbers
Definition: lsyscache.h:52
double cpu_operator_cost
Definition: costsize.c:108
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:154
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: relation.h:553
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1117
#define BoolGetDatum(X)
Definition: postgres.h:408
#define InvalidOid
Definition: postgres_ext.h:36
BlockNumber pagesPerRange
Definition: brin.h:34
#define Max(x, y)
Definition: c.h:800
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
BlockNumber pages
Definition: relation.h:564
#define NULL
Definition: c.h:229
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2895
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:155
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:176
RTEKind rtekind
Definition: parsenodes.h:944
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
#define SearchSysCache3(cacheId, key1, key2, key3)
Definition: syscache.h:160
int * indexkeys
Definition: relation.h:642
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:631
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
Definition: pg_list.h:45
int16 AttrNumber
Definition: attnum.h:21
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:151
double Cost
Definition: nodes.h:640
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1064
BlockNumber revmapNumPages
Definition: brin.h:35
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3011
void btcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6682 of file selfuncs.c.

References add_predicate_to_quals(), Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, IndexQualInfo::clause_op, clauselist_selectivity(), cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, estimate_array_length(), free_attstatsslot(), VariableStatData::freefunc, genericcostestimate(), get_attstatsslot(), get_index_stats_hook, get_op_opfamily_strategy(), get_opfamily_member(), get_relation_stats_hook, HeapTupleIsValid, IndexQualInfo::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst, MemSet, IndexOptInfo::ncolumns, NIL, AttStatsSlot::nnumbers, NULL, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum, OidIsValid, IndexOptInfo::opcintype, IndexOptInfo::opfamily, IndexQualInfo::other_operand, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reverse_sort, IndexQualInfo::rinfo, rint(), RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3, STATISTIC_KIND_CORRELATION, STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

6686 {
6687  IndexOptInfo *index = path->indexinfo;
6688  List *qinfos;
6689  GenericCosts costs;
6690  Oid relid;
6691  AttrNumber colnum;
6692  VariableStatData vardata;
6693  double numIndexTuples;
6694  Cost descentCost;
6695  List *indexBoundQuals;
6696  int indexcol;
6697  bool eqQualHere;
6698  bool found_saop;
6699  bool found_is_null_op;
6700  double num_sa_scans;
6701  ListCell *lc;
6702 
6703  /* Do preliminary analysis of indexquals */
6704  qinfos = deconstruct_indexquals(path);
6705 
6706  /*
6707  * For a btree scan, only leading '=' quals plus inequality quals for the
6708  * immediately next attribute contribute to index selectivity (these are
6709  * the "boundary quals" that determine the starting and stopping points of
6710  * the index scan). Additional quals can suppress visits to the heap, so
6711  * it's OK to count them in indexSelectivity, but they should not count
6712  * for estimating numIndexTuples. So we must examine the given indexquals
6713  * to find out which ones count as boundary quals. We rely on the
6714  * knowledge that they are given in index column order.
6715  *
6716  * For a RowCompareExpr, we consider only the first column, just as
6717  * rowcomparesel() does.
6718  *
6719  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6720  * index scans not one, but the ScalarArrayOpExpr's operator can be
6721  * considered to act the same as it normally does.
6722  */
6723  indexBoundQuals = NIL;
6724  indexcol = 0;
6725  eqQualHere = false;
6726  found_saop = false;
6727  found_is_null_op = false;
6728  num_sa_scans = 1;
6729  foreach(lc, qinfos)
6730  {
6731  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
6732  RestrictInfo *rinfo = qinfo->rinfo;
6733  Expr *clause = rinfo->clause;
6734  Oid clause_op;
6735  int op_strategy;
6736 
6737  if (indexcol != qinfo->indexcol)
6738  {
6739  /* Beginning of a new column's quals */
6740  if (!eqQualHere)
6741  break; /* done if no '=' qual for indexcol */
6742  eqQualHere = false;
6743  indexcol++;
6744  if (indexcol != qinfo->indexcol)
6745  break; /* no quals at all for indexcol */
6746  }
6747 
6748  if (IsA(clause, ScalarArrayOpExpr))
6749  {
6750  int alength = estimate_array_length(qinfo->other_operand);
6751 
6752  found_saop = true;
6753  /* count up number of SA scans induced by indexBoundQuals only */
6754  if (alength > 1)
6755  num_sa_scans *= alength;
6756  }
6757  else if (IsA(clause, NullTest))
6758  {
6759  NullTest *nt = (NullTest *) clause;
6760 
6761  if (nt->nulltesttype == IS_NULL)
6762  {
6763  found_is_null_op = true;
6764  /* IS NULL is like = for selectivity determination purposes */
6765  eqQualHere = true;
6766  }
6767  }
6768 
6769  /*
6770  * We would need to commute the clause_op if not varonleft, except
6771  * that we only care if it's equality or not, so that refinement is
6772  * unnecessary.
6773  */
6774  clause_op = qinfo->clause_op;
6775 
6776  /* check for equality operator */
6777  if (OidIsValid(clause_op))
6778  {
6779  op_strategy = get_op_opfamily_strategy(clause_op,
6780  index->opfamily[indexcol]);
6781  Assert(op_strategy != 0); /* not a member of opfamily?? */
6782  if (op_strategy == BTEqualStrategyNumber)
6783  eqQualHere = true;
6784  }
6785 
6786  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6787  }
6788 
6789  /*
6790  * If index is unique and we found an '=' clause for each column, we can
6791  * just assume numIndexTuples = 1 and skip the expensive
6792  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6793  * NullTest invalidates that theory, even though it sets eqQualHere.
6794  */
6795  if (index->unique &&
6796  indexcol == index->ncolumns - 1 &&
6797  eqQualHere &&
6798  !found_saop &&
6799  !found_is_null_op)
6800  numIndexTuples = 1.0;
6801  else
6802  {
6803  List *selectivityQuals;
6804  Selectivity btreeSelectivity;
6805 
6806  /*
6807  * If the index is partial, AND the index predicate with the
6808  * index-bound quals to produce a more accurate idea of the number of
6809  * rows covered by the bound conditions.
6810  */
6811  selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
6812 
6813  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6814  index->rel->relid,
6815  JOIN_INNER,
6816  NULL);
6817  numIndexTuples = btreeSelectivity * index->rel->tuples;
6818 
6819  /*
6820  * As in genericcostestimate(), we have to adjust for any
6821  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6822  * to integer.
6823  */
6824  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6825  }
6826 
6827  /*
6828  * Now do generic index cost estimation.
6829  */
6830  MemSet(&costs, 0, sizeof(costs));
6831  costs.numIndexTuples = numIndexTuples;
6832 
6833  genericcostestimate(root, path, loop_count, qinfos, &costs);
6834 
6835  /*
6836  * Add a CPU-cost component to represent the costs of initial btree
6837  * descent. We don't charge any I/O cost for touching upper btree levels,
6838  * since they tend to stay in cache, but we still have to do about log2(N)
6839  * comparisons to descend a btree of N leaf tuples. We charge one
6840  * cpu_operator_cost per comparison.
6841  *
6842  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6843  * ones after the first one are not startup cost so far as the overall
6844  * plan is concerned, so add them only to "total" cost.
6845  */
6846  if (index->tuples > 1) /* avoid computing log(0) */
6847  {
6848  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6849  costs.indexStartupCost += descentCost;
6850  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6851  }
6852 
6853  /*
6854  * Even though we're not charging I/O cost for touching upper btree pages,
6855  * it's still reasonable to charge some CPU cost per page descended
6856  * through. Moreover, if we had no such charge at all, bloated indexes
6857  * would appear to have the same search cost as unbloated ones, at least
6858  * in cases where only a single leaf page is expected to be visited. This
6859  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6860  * touched. The number of such pages is btree tree height plus one (ie,
6861  * we charge for the leaf page too). As above, charge once per SA scan.
6862  */
6863  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6864  costs.indexStartupCost += descentCost;
6865  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6866 
6867  /*
6868  * If we can get an estimate of the first column's ordering correlation C
6869  * from pg_statistic, estimate the index correlation as C for a
6870  * single-column index, or C * 0.75 for multiple columns. (The idea here
6871  * is that multiple columns dilute the importance of the first column's
6872  * ordering, but don't negate it entirely. Before 8.0 we divided the
6873  * correlation by the number of columns, but that seems too strong.)
6874  */
6875  MemSet(&vardata, 0, sizeof(vardata));
6876 
6877  if (index->indexkeys[0] != 0)
6878  {
6879  /* Simple variable --- look to stats for the underlying table */
6880  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6881 
6882  Assert(rte->rtekind == RTE_RELATION);
6883  relid = rte->relid;
6884  Assert(relid != InvalidOid);
6885  colnum = index->indexkeys[0];
6886 
6888  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6889  {
6890  /*
6891  * The hook took control of acquiring a stats tuple. If it did
6892  * supply a tuple, it'd better have supplied a freefunc.
6893  */
6894  if (HeapTupleIsValid(vardata.statsTuple) &&
6895  !vardata.freefunc)
6896  elog(ERROR, "no function provided to release variable stats with");
6897  }
6898  else
6899  {
6901  ObjectIdGetDatum(relid),
6902  Int16GetDatum(colnum),
6903  BoolGetDatum(rte->inh));
6904  vardata.freefunc = ReleaseSysCache;
6905  }
6906  }
6907  else
6908  {
6909  /* Expression --- maybe there are stats for the index itself */
6910  relid = index->indexoid;
6911  colnum = 1;
6912 
6913  if (get_index_stats_hook &&
6914  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6915  {
6916  /*
6917  * The hook took control of acquiring a stats tuple. If it did
6918  * supply a tuple, it'd better have supplied a freefunc.
6919  */
6920  if (HeapTupleIsValid(vardata.statsTuple) &&
6921  !vardata.freefunc)
6922  elog(ERROR, "no function provided to release variable stats with");
6923  }
6924  else
6925  {
6927  ObjectIdGetDatum(relid),
6928  Int16GetDatum(colnum),
6929  BoolGetDatum(false));
6930  vardata.freefunc = ReleaseSysCache;
6931  }
6932  }
6933 
6934  if (HeapTupleIsValid(vardata.statsTuple))
6935  {
6936  Oid sortop;
6937  AttStatsSlot sslot;
6938 
6939  sortop = get_opfamily_member(index->opfamily[0],
6940  index->opcintype[0],
6941  index->opcintype[0],
6943  if (OidIsValid(sortop) &&
6944  get_attstatsslot(&sslot, vardata.statsTuple,
6947  {
6948  double varCorrelation;
6949 
6950  Assert(sslot.nnumbers == 1);
6951  varCorrelation = sslot.numbers[0];
6952 
6953  if (index->reverse_sort[0])
6954  varCorrelation = -varCorrelation;
6955 
6956  if (index->ncolumns > 1)
6957  costs.indexCorrelation = varCorrelation * 0.75;
6958  else
6959  costs.indexCorrelation = varCorrelation;
6960 
6961  free_attstatsslot(&sslot);
6962  }
6963  }
6964 
6965  ReleaseVariableStats(vardata);
6966 
6967  *indexStartupCost = costs.indexStartupCost;
6968  *indexTotalCost = costs.indexTotalCost;
6969  *indexSelectivity = costs.indexSelectivity;
6970  *indexCorrelation = costs.indexCorrelation;
6971  *indexPages = costs.numIndexPages;
6972 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
IndexOptInfo * indexinfo
Definition: relation.h:1031
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
double tuples
Definition: relation.h:565
static List * add_predicate_to_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6660
#define Int16GetDatum(X)
Definition: postgres.h:457
#define MemSet(start, val, len)
Definition: c.h:857
double Selectivity
Definition: nodes.h:639
double tuples
Definition: relation.h:637
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: relation.h:638
#define OidIsValid(objectId)
Definition: c.h:538
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6292
bool unique
Definition: relation.h:665
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2094
RelOptInfo * rel
Definition: relation.h:633
#define planner_rt_fetch(rti, root)
Definition: relation.h:325
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define ObjectIdGetDatum(X)
Definition: postgres.h:513
#define ERROR
Definition: elog.h:43
double num_sa_scans
Definition: selfuncs.h:138
#define STATISTIC_KIND_CORRELATION
Definition: pg_statistic.h:233
float4 * numbers
Definition: lsyscache.h:52
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:163
double cpu_operator_cost
Definition: costsize.c:108
Cost indexTotalCost
Definition: selfuncs.h:130
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:154
double rint(double x)
Definition: rint.c:22
int ncolumns
Definition: relation.h:641
Index relid
Definition: relation.h:553
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1747
double indexCorrelation
Definition: selfuncs.h:132
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1117
NullTestType nulltesttype
Definition: primnodes.h:1181
#define BoolGetDatum(X)
Definition: postgres.h:408
#define InvalidOid
Definition: postgres_ext.h:36
double numIndexTuples
Definition: selfuncs.h:136
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
#define NULL
Definition: c.h:229
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2895
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:155
Oid * opcintype
Definition: relation.h:645
Cost indexStartupCost
Definition: selfuncs.h:129
Oid * opfamily
Definition: relation.h:644
RTEKind rtekind
Definition: parsenodes.h:944
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:80
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
Node * other_operand
Definition: selfuncs.h:110
#define SearchSysCache3(cacheId, key1, key2, key3)
Definition: syscache.h:160
int * indexkeys
Definition: relation.h:642
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:631
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:73
bool * reverse_sort
Definition: relation.h:647
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:45
int16 AttrNumber
Definition: attnum.h:21
#define BTEqualStrategyNumber
Definition: stratnum.h:31
double Cost
Definition: nodes.h:640
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6441
double numIndexPages
Definition: selfuncs.h:135
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3011
void gincostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 7437 of file selfuncs.c.

References AccessShareLock, GinQualCounts::arrayScans, RestrictInfo::clause, clauselist_selectivity(), cpu_index_tuple_cost, cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, GinQualCounts::exactEntries, get_tablespace_page_costs(), gincost_opexpr(), gincost_scalararrayopexpr(), ginGetStats(), GinQualCounts::haveFullScan, IndexOptInfo::hypothetical, index_close(), index_open(), index_pages_fetched(), IndexPath::indexinfo, IndexOptInfo::indexoid, IndexPath::indexorderbys, IndexPath::indexquals, IndexOptInfo::indpred, IsA, JOIN_INNER, lfirst, list_concat(), list_length(), list_make1, Max, Min, GinStatsData::nDataPages, GinStatsData::nEntries, GinStatsData::nEntryPages, NIL, nodeTag, GinStatsData::nPendingPages, GinStatsData::nTotalPages, NULL, orderby_operands_eval_cost(), other_operands_eval_cost(), IndexOptInfo::pages, GinQualCounts::partialEntries, predicate_implied_by(), IndexOptInfo::rel, RelOptInfo::relid, IndexOptInfo::reltablespace, IndexQualInfo::rinfo, rint(), scale, GinQualCounts::searchEntries, and IndexOptInfo::tuples.

Referenced by ginhandler().

7441 {
7442  IndexOptInfo *index = path->indexinfo;
7443  List *indexQuals = path->indexquals;
7444  List *indexOrderBys = path->indexorderbys;
7445  List *qinfos;
7446  ListCell *l;
7447  List *selectivityQuals;
7448  double numPages = index->pages,
7449  numTuples = index->tuples;
7450  double numEntryPages,
7451  numDataPages,
7452  numPendingPages,
7453  numEntries;
7454  GinQualCounts counts;
7455  bool matchPossible;
7456  double partialScale;
7457  double entryPagesFetched,
7458  dataPagesFetched,
7459  dataPagesFetchedBySel;
7460  double qual_op_cost,
7461  qual_arg_cost,
7462  spc_random_page_cost,
7463  outer_scans;
7464  Relation indexRel;
7465  GinStatsData ginStats;
7466 
7467  /* Do preliminary analysis of indexquals */
7468  qinfos = deconstruct_indexquals(path);
7469 
7470  /*
7471  * Obtain statistical information from the meta page, if possible. Else
7472  * set ginStats to zeroes, and we'll cope below.
7473  */
7474  if (!index->hypothetical)
7475  {
7476  indexRel = index_open(index->indexoid, AccessShareLock);
7477  ginGetStats(indexRel, &ginStats);
7478  index_close(indexRel, AccessShareLock);
7479  }
7480  else
7481  {
7482  memset(&ginStats, 0, sizeof(ginStats));
7483  }
7484 
7485  /*
7486  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7487  * trusted, but the other fields are data as of the last VACUUM. We can
7488  * scale them up to account for growth since then, but that method only
7489  * goes so far; in the worst case, the stats might be for a completely
7490  * empty index, and scaling them will produce pretty bogus numbers.
7491  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7492  * it's grown more than that, fall back to estimating things only from the
7493  * assumed-accurate index size. But we'll trust nPendingPages in any case
7494  * so long as it's not clearly insane, ie, more than the index size.
7495  */
7496  if (ginStats.nPendingPages < numPages)
7497  numPendingPages = ginStats.nPendingPages;
7498  else
7499  numPendingPages = 0;
7500 
7501  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7502  ginStats.nTotalPages > numPages / 4 &&
7503  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7504  {
7505  /*
7506  * OK, the stats seem close enough to sane to be trusted. But we
7507  * still need to scale them by the ratio numPages / nTotalPages to
7508  * account for growth since the last VACUUM.
7509  */
7510  double scale = numPages / ginStats.nTotalPages;
7511 
7512  numEntryPages = ceil(ginStats.nEntryPages * scale);
7513  numDataPages = ceil(ginStats.nDataPages * scale);
7514  numEntries = ceil(ginStats.nEntries * scale);
7515  /* ensure we didn't round up too much */
7516  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7517  numDataPages = Min(numDataPages,
7518  numPages - numPendingPages - numEntryPages);
7519  }
7520  else
7521  {
7522  /*
7523  * We might get here because it's a hypothetical index, or an index
7524  * created pre-9.1 and never vacuumed since upgrading (in which case
7525  * its stats would read as zeroes), or just because it's grown too
7526  * much since the last VACUUM for us to put our faith in scaling.
7527  *
7528  * Invent some plausible internal statistics based on the index page
7529  * count (and clamp that to at least 10 pages, just in case). We
7530  * estimate that 90% of the index is entry pages, and the rest is data
7531  * pages. Estimate 100 entries per entry page; this is rather bogus
7532  * since it'll depend on the size of the keys, but it's more robust
7533  * than trying to predict the number of entries per heap tuple.
7534  */
7535  numPages = Max(numPages, 10);
7536  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7537  numDataPages = numPages - numPendingPages - numEntryPages;
7538  numEntries = floor(numEntryPages * 100);
7539  }
7540 
7541  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7542  if (numEntries < 1)
7543  numEntries = 1;
7544 
7545  /*
7546  * Include predicate in selectivityQuals (should match
7547  * genericcostestimate)
7548  */
7549  if (index->indpred != NIL)
7550  {
7551  List *predExtraQuals = NIL;
7552 
7553  foreach(l, index->indpred)
7554  {
7555  Node *predQual = (Node *) lfirst(l);
7556  List *oneQual = list_make1(predQual);
7557 
7558  if (!predicate_implied_by(oneQual, indexQuals, false))
7559  predExtraQuals = list_concat(predExtraQuals, oneQual);
7560  }
7561  /* list_concat avoids modifying the passed-in indexQuals list */
7562  selectivityQuals = list_concat(predExtraQuals, indexQuals);
7563  }
7564  else
7565  selectivityQuals = indexQuals;
7566 
7567  /* Estimate the fraction of main-table tuples that will be visited */
7568  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7569  index->rel->relid,
7570  JOIN_INNER,
7571  NULL);
7572 
7573  /* fetch estimated page cost for tablespace containing index */
7575  &spc_random_page_cost,
7576  NULL);
7577 
7578  /*
7579  * Generic assumption about index correlation: there isn't any.
7580  */
7581  *indexCorrelation = 0.0;
7582 
7583  /*
7584  * Examine quals to estimate number of search entries & partial matches
7585  */
7586  memset(&counts, 0, sizeof(counts));
7587  counts.arrayScans = 1;
7588  matchPossible = true;
7589 
7590  foreach(l, qinfos)
7591  {
7592  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7593  Expr *clause = qinfo->rinfo->clause;
7594 
7595  if (IsA(clause, OpExpr))
7596  {
7597  matchPossible = gincost_opexpr(root,
7598  index,
7599  qinfo,
7600  &counts);
7601  if (!matchPossible)
7602  break;
7603  }
7604  else if (IsA(clause, ScalarArrayOpExpr))
7605  {
7606  matchPossible = gincost_scalararrayopexpr(root,
7607  index,
7608  qinfo,
7609  numEntries,
7610  &counts);
7611  if (!matchPossible)
7612  break;
7613  }
7614  else
7615  {
7616  /* shouldn't be anything else for a GIN index */
7617  elog(ERROR, "unsupported GIN indexqual type: %d",
7618  (int) nodeTag(clause));
7619  }
7620  }
7621 
7622  /* Fall out if there were any provably-unsatisfiable quals */
7623  if (!matchPossible)
7624  {
7625  *indexStartupCost = 0;
7626  *indexTotalCost = 0;
7627  *indexSelectivity = 0;
7628  return;
7629  }
7630 
7631  if (counts.haveFullScan || 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
7746  */
7747  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7748  orderby_operands_eval_cost(root, path);
7749  qual_op_cost = cpu_operator_cost *
7750  (list_length(indexQuals) + list_length(indexOrderBys));
7751 
7752  *indexStartupCost += qual_arg_cost;
7753  *indexTotalCost += qual_arg_cost;
7754  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7755  *indexPages = dataPagesFetched;
7756 }
#define NIL
Definition: pg_list.h:69
bool predicate_implied_by(List *predicate_list, List *clause_list, bool clause_is_check)
Definition: predtest.c:135
BlockNumber nEntryPages
Definition: gin.h:45
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
IndexOptInfo * indexinfo
Definition: relation.h:1031
#define Min(x, y)
Definition: c.h:806
#define AccessShareLock
Definition: lockdefs.h:36
double partialEntries
Definition: selfuncs.c:7152
Definition: nodes.h:509
double searchEntries
Definition: selfuncs.c:7154
Oid reltablespace
Definition: relation.h:632
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6387
int scale
Definition: pgbench.c:106
int64 nEntries
Definition: gin.h:47
List * list_concat(List *list1, List *list2)
Definition: list.c:321
uint32 BlockNumber
Definition: block.h:31
bool hypothetical
Definition: relation.h:667
double tuples
Definition: relation.h:637
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6292
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6412
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:7153
BlockNumber pages
Definition: relation.h:636
#define list_make1(x1)
Definition: pg_list.h:139
List * indexquals
Definition: relation.h:1033
RelOptInfo * rel
Definition: relation.h:633
#define ERROR
Definition: elog.h:43
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7322
bool haveFullScan
Definition: selfuncs.c:7151
double cpu_operator_cost
Definition: costsize.c:108
double rint(double x)
Definition: rint.c:22
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: relation.h:553
Expr * clause
Definition: relation.h:1747
BlockNumber nPendingPages
Definition: gin.h:43
double arrayScans
Definition: selfuncs.c:7155
List * indexorderbys
Definition: relation.h:1035
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:632
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, GinQualCounts *counts)
Definition: selfuncs.c:7266
BlockNumber nDataPages
Definition: gin.h:46
#define Max(x, y)
Definition: c.h:800
#define NULL
Definition: c.h:229
#define lfirst(lc)
Definition: pg_list.h:106
static int list_length(const List *l)
Definition: pg_list.h:89
BlockNumber nTotalPages
Definition: gin.h:44
#define nodeTag(nodeptr)
Definition: nodes.h:514
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:176
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:631
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
List * indpred
Definition: relation.h:654
Definition: pg_list.h:45
double cpu_index_tuple_cost
Definition: costsize.c:107
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:151
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:813
void gistcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 7023 of file selfuncs.c.

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

Referenced by gisthandler().

7027 {
7028  IndexOptInfo *index = path->indexinfo;
7029  List *qinfos;
7030  GenericCosts costs;
7031  Cost descentCost;
7032 
7033  /* Do preliminary analysis of indexquals */
7034  qinfos = deconstruct_indexquals(path);
7035 
7036  MemSet(&costs, 0, sizeof(costs));
7037 
7038  genericcostestimate(root, path, loop_count, qinfos, &costs);
7039 
7040  /*
7041  * We model index descent costs similarly to those for btree, but to do
7042  * that we first need an idea of the tree height. We somewhat arbitrarily
7043  * assume that the fanout is 100, meaning the tree height is at most
7044  * log100(index->pages).
7045  *
7046  * Although this computation isn't really expensive enough to require
7047  * caching, we might as well use index->tree_height to cache it.
7048  */
7049  if (index->tree_height < 0) /* unknown? */
7050  {
7051  if (index->pages > 1) /* avoid computing log(0) */
7052  index->tree_height = (int) (log(index->pages) / log(100.0));
7053  else
7054  index->tree_height = 0;
7055  }
7056 
7057  /*
7058  * Add a CPU-cost component to represent the costs of initial descent. We
7059  * just use log(N) here not log2(N) since the branching factor isn't
7060  * necessarily two anyway. As for btree, charge once per SA scan.
7061  */
7062  if (index->tuples > 1) /* avoid computing log(0) */
7063  {
7064  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7065  costs.indexStartupCost += descentCost;
7066  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7067  }
7068 
7069  /*
7070  * Likewise add a per-page charge, calculated the same as for btrees.
7071  */
7072  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7073  costs.indexStartupCost += descentCost;
7074  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7075 
7076  *indexStartupCost = costs.indexStartupCost;
7077  *indexTotalCost = costs.indexTotalCost;
7078  *indexSelectivity = costs.indexSelectivity;
7079  *indexCorrelation = costs.indexCorrelation;
7080  *indexPages = costs.numIndexPages;
7081 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
IndexOptInfo * indexinfo
Definition: relation.h:1031
#define MemSet(start, val, len)
Definition: c.h:857
double tuples
Definition: relation.h:637
int tree_height
Definition: relation.h:638
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6292
Definition: type.h:89
BlockNumber pages
Definition: relation.h:636
double num_sa_scans
Definition: selfuncs.h:138
double cpu_operator_cost
Definition: costsize.c:108
Cost indexTotalCost
Definition: selfuncs.h:130
double indexCorrelation
Definition: selfuncs.h:132
Cost indexStartupCost
Definition: selfuncs.h:129
Definition: pg_list.h:45
double Cost
Definition: nodes.h:640
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6441
double numIndexPages
Definition: selfuncs.h:135
void hashcostestimate ( struct PlannerInfo root,
struct IndexPath path,
double  loop_count,
Cost indexStartupCost,
Cost indexTotalCost,
Selectivity indexSelectivity,
double *  indexCorrelation,
double *  indexPages 
)

Definition at line 6975 of file selfuncs.c.

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

Referenced by hashhandler().

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

Definition at line 7084 of file selfuncs.c.

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

Referenced by spghandler().

7088 {
7089  IndexOptInfo *index = path->indexinfo;
7090  List *qinfos;
7091  GenericCosts costs;
7092  Cost descentCost;
7093 
7094  /* Do preliminary analysis of indexquals */
7095  qinfos = deconstruct_indexquals(path);
7096 
7097  MemSet(&costs, 0, sizeof(costs));
7098 
7099  genericcostestimate(root, path, loop_count, qinfos, &costs);
7100 
7101  /*
7102  * We model index descent costs similarly to those for btree, but to do
7103  * that we first need an idea of the tree height. We somewhat arbitrarily
7104  * assume that the fanout is 100, meaning the tree height is at most
7105  * log100(index->pages).
7106  *
7107  * Although this computation isn't really expensive enough to require
7108  * caching, we might as well use index->tree_height to cache it.
7109  */
7110  if (index->tree_height < 0) /* unknown? */
7111  {
7112  if (index->pages > 1) /* avoid computing log(0) */
7113  index->tree_height = (int) (log(index->pages) / log(100.0));
7114  else
7115  index->tree_height = 0;
7116  }
7117 
7118  /*
7119  * Add a CPU-cost component to represent the costs of initial descent. We
7120  * just use log(N) here not log2(N) since the branching factor isn't
7121  * necessarily two anyway. As for btree, charge once per SA scan.
7122  */
7123  if (index->tuples > 1) /* avoid computing log(0) */
7124  {
7125  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7126  costs.indexStartupCost += descentCost;
7127  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7128  }
7129 
7130  /*
7131  * Likewise add a per-page charge, calculated the same as for btrees.
7132  */
7133  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7134  costs.indexStartupCost += descentCost;
7135  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7136 
7137  *indexStartupCost = costs.indexStartupCost;
7138  *indexTotalCost = costs.indexTotalCost;
7139  *indexSelectivity = costs.indexSelectivity;
7140  *indexCorrelation = costs.indexCorrelation;
7141  *indexPages = costs.numIndexPages;
7142 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
IndexOptInfo * indexinfo
Definition: relation.h:1031
#define MemSet(start, val, len)
Definition: c.h:857
double tuples
Definition: relation.h:637
int tree_height
Definition: relation.h:638
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6292
Definition: type.h:89
BlockNumber pages
Definition: relation.h:636
double num_sa_scans
Definition: selfuncs.h:138
double cpu_operator_cost
Definition: costsize.c:108
Cost indexTotalCost
Definition: selfuncs.h:130
double indexCorrelation
Definition: selfuncs.h:132
Cost indexStartupCost
Definition: selfuncs.h:129
Definition: pg_list.h:45
double Cost
Definition: nodes.h:640
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6441
double numIndexPages
Definition: selfuncs.h:135