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 7726 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().

7730 {
7731  IndexOptInfo *index = path->indexinfo;
7732  List *indexQuals = path->indexquals;
7733  double numPages = index->pages;
7734  RelOptInfo *baserel = index->rel;
7735  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7736  List *qinfos;
7737  Cost spc_seq_page_cost;
7738  Cost spc_random_page_cost;
7739  double qual_arg_cost;
7740  double qualSelectivity;
7741  BrinStatsData statsData;
7742  double indexRanges;
7743  double minimalRanges;
7744  double estimatedRanges;
7745  double selec;
7746  Relation indexRel;
7747  ListCell *l;
7748  VariableStatData vardata;
7749 
7750  Assert(rte->rtekind == RTE_RELATION);
7751 
7752  /* fetch estimated page cost for the tablespace containing the index */
7754  &spc_random_page_cost,
7755  &spc_seq_page_cost);
7756 
7757  /*
7758  * Obtain some data from the index itself.
7759  */
7760  indexRel = index_open(index->indexoid, AccessShareLock);
7761  brinGetStats(indexRel, &statsData);
7762  index_close(indexRel, AccessShareLock);
7763 
7764  /*
7765  * Compute index correlation
7766  *
7767  * Because we can use all index quals equally when scanning, we can use
7768  * the largest correlation (in absolute value) among columns used by the
7769  * query. Start at zero, the worst possible case. If we cannot find any
7770  * correlation statistics, we will keep it as 0.
7771  */
7772  *indexCorrelation = 0;
7773 
7774  qinfos = deconstruct_indexquals(path);
7775  foreach(l, qinfos)
7776  {
7777  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7778  AttrNumber attnum = index->indexkeys[qinfo->indexcol];
7779 
7780  /* attempt to lookup stats in relation for this index column */
7781  if (attnum != 0)
7782  {
7783  /* Simple variable -- look to stats for the underlying table */
7785  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7786  {
7787  /*
7788  * The hook took control of acquiring a stats tuple. If it
7789  * did supply a tuple, it'd better have supplied a freefunc.
7790  */
7791  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7792  elog(ERROR,
7793  "no function provided to release variable stats with");
7794  }
7795  else
7796  {
7797  vardata.statsTuple =
7799  ObjectIdGetDatum(rte->relid),
7800  Int16GetDatum(attnum),
7801  BoolGetDatum(false));
7802  vardata.freefunc = ReleaseSysCache;
7803  }
7804  }
7805  else
7806  {
7807  /*
7808  * Looks like we've found an expression column in the index. Let's
7809  * see if there's any stats for it.
7810  */
7811 
7812  /* get the attnum from the 0-based index. */
7813  attnum = qinfo->indexcol + 1;
7814 
7815  if (get_index_stats_hook &&
7816  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7817  {
7818  /*
7819  * The hook took control of acquiring a stats tuple. If it
7820  * did supply a tuple, it'd better have supplied a freefunc.
7821  */
7822  if (HeapTupleIsValid(vardata.statsTuple) &&
7823  !vardata.freefunc)
7824  elog(ERROR, "no function provided to release variable stats with");
7825  }
7826  else
7827  {
7829  ObjectIdGetDatum(index->indexoid),
7830  Int16GetDatum(attnum),
7831  BoolGetDatum(false));
7832  vardata.freefunc = ReleaseSysCache;
7833  }
7834  }
7835 
7836  if (HeapTupleIsValid(vardata.statsTuple))
7837  {
7838  AttStatsSlot sslot;
7839 
7840  if (get_attstatsslot(&sslot, vardata.statsTuple,
7843  {
7844  double varCorrelation = 0.0;
7845 
7846  if (sslot.nnumbers > 0)
7847  varCorrelation = Abs(sslot.numbers[0]);
7848 
7849  if (varCorrelation > *indexCorrelation)
7850  *indexCorrelation = varCorrelation;
7851 
7852  free_attstatsslot(&sslot);
7853  }
7854  }
7855 
7856  ReleaseVariableStats(vardata);
7857  }
7858 
7859  qualSelectivity = clauselist_selectivity(root, indexQuals,
7860  baserel->relid,
7861  JOIN_INNER, NULL);
7862 
7863  /* work out the actual number of ranges in the index */
7864  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
7865  1.0);
7866 
7867  /*
7868  * Now calculate the minimum possible ranges we could match with if all of
7869  * the rows were in the perfect order in the table's heap.
7870  */
7871  minimalRanges = ceil(indexRanges * qualSelectivity);
7872 
7873  /*
7874  * Now estimate the number of ranges that we'll touch by using the
7875  * indexCorrelation from the stats. Careful not to divide by zero (note
7876  * we're using the absolute value of the correlation).
7877  */
7878  if (*indexCorrelation < 1.0e-10)
7879  estimatedRanges = indexRanges;
7880  else
7881  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7882 
7883  /* we expect to visit this portion of the table */
7884  selec = estimatedRanges / indexRanges;
7885 
7886  CLAMP_PROBABILITY(selec);
7887 
7888  *indexSelectivity = selec;
7889 
7890  /*
7891  * Compute the index qual costs, much as in genericcostestimate, to add to
7892  * the index costs.
7893  */
7894  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7895  orderby_operands_eval_cost(root, path);
7896 
7897  /*
7898  * Compute the startup cost as the cost to read the whole revmap
7899  * sequentially, including the cost to execute the index quals.
7900  */
7901  *indexStartupCost =
7902  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
7903  *indexStartupCost += qual_arg_cost;
7904 
7905  /*
7906  * To read a BRIN index there might be a bit of back and forth over
7907  * regular pages, as revmap might point to them out of sequential order;
7908  * calculate the total cost as reading the whole index in random order.
7909  */
7910  *indexTotalCost = *indexStartupCost +
7911  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
7912 
7913  /*
7914  * Charge a small amount per range tuple which we expect to match to. This
7915  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
7916  * will set a bit for each page in the range when we find a matching
7917  * range, so we must multiply the charge by the number of pages in the
7918  * range.
7919  */
7920  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
7921  statsData.pagesPerRange;
7922 
7923  *indexPages = index->pages;
7924 }
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:6351
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6256
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6376
#define Abs(x)
Definition: c.h:812
Definition: type.h:90
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:929
#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:639
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1063
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 6646 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().

6650 {
6651  IndexOptInfo *index = path->indexinfo;
6652  List *qinfos;
6653  GenericCosts costs;
6654  Oid relid;
6655  AttrNumber colnum;
6656  VariableStatData vardata;
6657  double numIndexTuples;
6658  Cost descentCost;
6659  List *indexBoundQuals;
6660  int indexcol;
6661  bool eqQualHere;
6662  bool found_saop;
6663  bool found_is_null_op;
6664  double num_sa_scans;
6665  ListCell *lc;
6666 
6667  /* Do preliminary analysis of indexquals */
6668  qinfos = deconstruct_indexquals(path);
6669 
6670  /*
6671  * For a btree scan, only leading '=' quals plus inequality quals for the
6672  * immediately next attribute contribute to index selectivity (these are
6673  * the "boundary quals" that determine the starting and stopping points of
6674  * the index scan). Additional quals can suppress visits to the heap, so
6675  * it's OK to count them in indexSelectivity, but they should not count
6676  * for estimating numIndexTuples. So we must examine the given indexquals
6677  * to find out which ones count as boundary quals. We rely on the
6678  * knowledge that they are given in index column order.
6679  *
6680  * For a RowCompareExpr, we consider only the first column, just as
6681  * rowcomparesel() does.
6682  *
6683  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6684  * index scans not one, but the ScalarArrayOpExpr's operator can be
6685  * considered to act the same as it normally does.
6686  */
6687  indexBoundQuals = NIL;
6688  indexcol = 0;
6689  eqQualHere = false;
6690  found_saop = false;
6691  found_is_null_op = false;
6692  num_sa_scans = 1;
6693  foreach(lc, qinfos)
6694  {
6695  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
6696  RestrictInfo *rinfo = qinfo->rinfo;
6697  Expr *clause = rinfo->clause;
6698  Oid clause_op;
6699  int op_strategy;
6700 
6701  if (indexcol != qinfo->indexcol)
6702  {
6703  /* Beginning of a new column's quals */
6704  if (!eqQualHere)
6705  break; /* done if no '=' qual for indexcol */
6706  eqQualHere = false;
6707  indexcol++;
6708  if (indexcol != qinfo->indexcol)
6709  break; /* no quals at all for indexcol */
6710  }
6711 
6712  if (IsA(clause, ScalarArrayOpExpr))
6713  {
6714  int alength = estimate_array_length(qinfo->other_operand);
6715 
6716  found_saop = true;
6717  /* count up number of SA scans induced by indexBoundQuals only */
6718  if (alength > 1)
6719  num_sa_scans *= alength;
6720  }
6721  else if (IsA(clause, NullTest))
6722  {
6723  NullTest *nt = (NullTest *) clause;
6724 
6725  if (nt->nulltesttype == IS_NULL)
6726  {
6727  found_is_null_op = true;
6728  /* IS NULL is like = for selectivity determination purposes */
6729  eqQualHere = true;
6730  }
6731  }
6732 
6733  /*
6734  * We would need to commute the clause_op if not varonleft, except
6735  * that we only care if it's equality or not, so that refinement is
6736  * unnecessary.
6737  */
6738  clause_op = qinfo->clause_op;
6739 
6740  /* check for equality operator */
6741  if (OidIsValid(clause_op))
6742  {
6743  op_strategy = get_op_opfamily_strategy(clause_op,
6744  index->opfamily[indexcol]);
6745  Assert(op_strategy != 0); /* not a member of opfamily?? */
6746  if (op_strategy == BTEqualStrategyNumber)
6747  eqQualHere = true;
6748  }
6749 
6750  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6751  }
6752 
6753  /*
6754  * If index is unique and we found an '=' clause for each column, we can
6755  * just assume numIndexTuples = 1 and skip the expensive
6756  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6757  * NullTest invalidates that theory, even though it sets eqQualHere.
6758  */
6759  if (index->unique &&
6760  indexcol == index->ncolumns - 1 &&
6761  eqQualHere &&
6762  !found_saop &&
6763  !found_is_null_op)
6764  numIndexTuples = 1.0;
6765  else
6766  {
6767  List *selectivityQuals;
6768  Selectivity btreeSelectivity;
6769 
6770  /*
6771  * If the index is partial, AND the index predicate with the
6772  * index-bound quals to produce a more accurate idea of the number of
6773  * rows covered by the bound conditions.
6774  */
6775  selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
6776 
6777  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6778  index->rel->relid,
6779  JOIN_INNER,
6780  NULL);
6781  numIndexTuples = btreeSelectivity * index->rel->tuples;
6782 
6783  /*
6784  * As in genericcostestimate(), we have to adjust for any
6785  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6786  * to integer.
6787  */
6788  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6789  }
6790 
6791  /*
6792  * Now do generic index cost estimation.
6793  */
6794  MemSet(&costs, 0, sizeof(costs));
6795  costs.numIndexTuples = numIndexTuples;
6796 
6797  genericcostestimate(root, path, loop_count, qinfos, &costs);
6798 
6799  /*
6800  * Add a CPU-cost component to represent the costs of initial btree
6801  * descent. We don't charge any I/O cost for touching upper btree levels,
6802  * since they tend to stay in cache, but we still have to do about log2(N)
6803  * comparisons to descend a btree of N leaf tuples. We charge one
6804  * cpu_operator_cost per comparison.
6805  *
6806  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6807  * ones after the first one are not startup cost so far as the overall
6808  * plan is concerned, so add them only to "total" cost.
6809  */
6810  if (index->tuples > 1) /* avoid computing log(0) */
6811  {
6812  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6813  costs.indexStartupCost += descentCost;
6814  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6815  }
6816 
6817  /*
6818  * Even though we're not charging I/O cost for touching upper btree pages,
6819  * it's still reasonable to charge some CPU cost per page descended
6820  * through. Moreover, if we had no such charge at all, bloated indexes
6821  * would appear to have the same search cost as unbloated ones, at least
6822  * in cases where only a single leaf page is expected to be visited. This
6823  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6824  * touched. The number of such pages is btree tree height plus one (ie,
6825  * we charge for the leaf page too). As above, charge once per SA scan.
6826  */
6827  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6828  costs.indexStartupCost += descentCost;
6829  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6830 
6831  /*
6832  * If we can get an estimate of the first column's ordering correlation C
6833  * from pg_statistic, estimate the index correlation as C for a
6834  * single-column index, or C * 0.75 for multiple columns. (The idea here
6835  * is that multiple columns dilute the importance of the first column's
6836  * ordering, but don't negate it entirely. Before 8.0 we divided the
6837  * correlation by the number of columns, but that seems too strong.)
6838  */
6839  MemSet(&vardata, 0, sizeof(vardata));
6840 
6841  if (index->indexkeys[0] != 0)
6842  {
6843  /* Simple variable --- look to stats for the underlying table */
6844  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6845 
6846  Assert(rte->rtekind == RTE_RELATION);
6847  relid = rte->relid;
6848  Assert(relid != InvalidOid);
6849  colnum = index->indexkeys[0];
6850 
6852  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6853  {
6854  /*
6855  * The hook took control of acquiring a stats tuple. If it did
6856  * supply a tuple, it'd better have supplied a freefunc.
6857  */
6858  if (HeapTupleIsValid(vardata.statsTuple) &&
6859  !vardata.freefunc)
6860  elog(ERROR, "no function provided to release variable stats with");
6861  }
6862  else
6863  {
6865  ObjectIdGetDatum(relid),
6866  Int16GetDatum(colnum),
6867  BoolGetDatum(rte->inh));
6868  vardata.freefunc = ReleaseSysCache;
6869  }
6870  }
6871  else
6872  {
6873  /* Expression --- maybe there are stats for the index itself */
6874  relid = index->indexoid;
6875  colnum = 1;
6876 
6877  if (get_index_stats_hook &&
6878  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6879  {
6880  /*
6881  * The hook took control of acquiring a stats tuple. If it did
6882  * supply a tuple, it'd better have supplied a freefunc.
6883  */
6884  if (HeapTupleIsValid(vardata.statsTuple) &&
6885  !vardata.freefunc)
6886  elog(ERROR, "no function provided to release variable stats with");
6887  }
6888  else
6889  {
6891  ObjectIdGetDatum(relid),
6892  Int16GetDatum(colnum),
6893  BoolGetDatum(false));
6894  vardata.freefunc = ReleaseSysCache;
6895  }
6896  }
6897 
6898  if (HeapTupleIsValid(vardata.statsTuple))
6899  {
6900  Oid sortop;
6901  AttStatsSlot sslot;
6902 
6903  sortop = get_opfamily_member(index->opfamily[0],
6904  index->opcintype[0],
6905  index->opcintype[0],
6907  if (OidIsValid(sortop) &&
6908  get_attstatsslot(&sslot, vardata.statsTuple,
6911  {
6912  double varCorrelation;
6913 
6914  Assert(sslot.nnumbers == 1);
6915  varCorrelation = sslot.numbers[0];
6916 
6917  if (index->reverse_sort[0])
6918  varCorrelation = -varCorrelation;
6919 
6920  if (index->ncolumns > 1)
6921  costs.indexCorrelation = varCorrelation * 0.75;
6922  else
6923  costs.indexCorrelation = varCorrelation;
6924 
6925  free_attstatsslot(&sslot);
6926  }
6927  }
6928 
6929  ReleaseVariableStats(vardata);
6930 
6931  *indexStartupCost = costs.indexStartupCost;
6932  *indexTotalCost = costs.indexTotalCost;
6933  *indexSelectivity = costs.indexSelectivity;
6934  *indexCorrelation = costs.indexCorrelation;
6935  *indexPages = costs.numIndexPages;
6936 }
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:6624
#define Int16GetDatum(X)
Definition: postgres.h:457
#define MemSet(start, val, len)
Definition: c.h:857
double Selectivity
Definition: nodes.h:638
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:6256
bool unique
Definition: relation.h:664
Definition: type.h:90
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2057
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:1180
#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:929
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:639
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6405
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 7401 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().

7405 {
7406  IndexOptInfo *index = path->indexinfo;
7407  List *indexQuals = path->indexquals;
7408  List *indexOrderBys = path->indexorderbys;
7409  List *qinfos;
7410  ListCell *l;
7411  List *selectivityQuals;
7412  double numPages = index->pages,
7413  numTuples = index->tuples;
7414  double numEntryPages,
7415  numDataPages,
7416  numPendingPages,
7417  numEntries;
7418  GinQualCounts counts;
7419  bool matchPossible;
7420  double partialScale;
7421  double entryPagesFetched,
7422  dataPagesFetched,
7423  dataPagesFetchedBySel;
7424  double qual_op_cost,
7425  qual_arg_cost,
7426  spc_random_page_cost,
7427  outer_scans;
7428  Relation indexRel;
7429  GinStatsData ginStats;
7430 
7431  /* Do preliminary analysis of indexquals */
7432  qinfos = deconstruct_indexquals(path);
7433 
7434  /*
7435  * Obtain statistical information from the meta page, if possible. Else
7436  * set ginStats to zeroes, and we'll cope below.
7437  */
7438  if (!index->hypothetical)
7439  {
7440  indexRel = index_open(index->indexoid, AccessShareLock);
7441  ginGetStats(indexRel, &ginStats);
7442  index_close(indexRel, AccessShareLock);
7443  }
7444  else
7445  {
7446  memset(&ginStats, 0, sizeof(ginStats));
7447  }
7448 
7449  /*
7450  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7451  * trusted, but the other fields are data as of the last VACUUM. We can
7452  * scale them up to account for growth since then, but that method only
7453  * goes so far; in the worst case, the stats might be for a completely
7454  * empty index, and scaling them will produce pretty bogus numbers.
7455  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7456  * it's grown more than that, fall back to estimating things only from the
7457  * assumed-accurate index size. But we'll trust nPendingPages in any case
7458  * so long as it's not clearly insane, ie, more than the index size.
7459  */
7460  if (ginStats.nPendingPages < numPages)
7461  numPendingPages = ginStats.nPendingPages;
7462  else
7463  numPendingPages = 0;
7464 
7465  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7466  ginStats.nTotalPages > numPages / 4 &&
7467  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7468  {
7469  /*
7470  * OK, the stats seem close enough to sane to be trusted. But we
7471  * still need to scale them by the ratio numPages / nTotalPages to
7472  * account for growth since the last VACUUM.
7473  */
7474  double scale = numPages / ginStats.nTotalPages;
7475 
7476  numEntryPages = ceil(ginStats.nEntryPages * scale);
7477  numDataPages = ceil(ginStats.nDataPages * scale);
7478  numEntries = ceil(ginStats.nEntries * scale);
7479  /* ensure we didn't round up too much */
7480  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7481  numDataPages = Min(numDataPages,
7482  numPages - numPendingPages - numEntryPages);
7483  }
7484  else
7485  {
7486  /*
7487  * We might get here because it's a hypothetical index, or an index
7488  * created pre-9.1 and never vacuumed since upgrading (in which case
7489  * its stats would read as zeroes), or just because it's grown too
7490  * much since the last VACUUM for us to put our faith in scaling.
7491  *
7492  * Invent some plausible internal statistics based on the index page
7493  * count (and clamp that to at least 10 pages, just in case). We
7494  * estimate that 90% of the index is entry pages, and the rest is data
7495  * pages. Estimate 100 entries per entry page; this is rather bogus
7496  * since it'll depend on the size of the keys, but it's more robust
7497  * than trying to predict the number of entries per heap tuple.
7498  */
7499  numPages = Max(numPages, 10);
7500  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7501  numDataPages = numPages - numPendingPages - numEntryPages;
7502  numEntries = floor(numEntryPages * 100);
7503  }
7504 
7505  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7506  if (numEntries < 1)
7507  numEntries = 1;
7508 
7509  /*
7510  * Include predicate in selectivityQuals (should match
7511  * genericcostestimate)
7512  */
7513  if (index->indpred != NIL)
7514  {
7515  List *predExtraQuals = NIL;
7516 
7517  foreach(l, index->indpred)
7518  {
7519  Node *predQual = (Node *) lfirst(l);
7520  List *oneQual = list_make1(predQual);
7521 
7522  if (!predicate_implied_by(oneQual, indexQuals))
7523  predExtraQuals = list_concat(predExtraQuals, oneQual);
7524  }
7525  /* list_concat avoids modifying the passed-in indexQuals list */
7526  selectivityQuals = list_concat(predExtraQuals, indexQuals);
7527  }
7528  else
7529  selectivityQuals = indexQuals;
7530 
7531  /* Estimate the fraction of main-table tuples that will be visited */
7532  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7533  index->rel->relid,
7534  JOIN_INNER,
7535  NULL);
7536 
7537  /* fetch estimated page cost for tablespace containing index */
7539  &spc_random_page_cost,
7540  NULL);
7541 
7542  /*
7543  * Generic assumption about index correlation: there isn't any.
7544  */
7545  *indexCorrelation = 0.0;
7546 
7547  /*
7548  * Examine quals to estimate number of search entries & partial matches
7549  */
7550  memset(&counts, 0, sizeof(counts));
7551  counts.arrayScans = 1;
7552  matchPossible = true;
7553 
7554  foreach(l, qinfos)
7555  {
7556  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7557  Expr *clause = qinfo->rinfo->clause;
7558 
7559  if (IsA(clause, OpExpr))
7560  {
7561  matchPossible = gincost_opexpr(root,
7562  index,
7563  qinfo,
7564  &counts);
7565  if (!matchPossible)
7566  break;
7567  }
7568  else if (IsA(clause, ScalarArrayOpExpr))
7569  {
7570  matchPossible = gincost_scalararrayopexpr(root,
7571  index,
7572  qinfo,
7573  numEntries,
7574  &counts);
7575  if (!matchPossible)
7576  break;
7577  }
7578  else
7579  {
7580  /* shouldn't be anything else for a GIN index */
7581  elog(ERROR, "unsupported GIN indexqual type: %d",
7582  (int) nodeTag(clause));
7583  }
7584  }
7585 
7586  /* Fall out if there were any provably-unsatisfiable quals */
7587  if (!matchPossible)
7588  {
7589  *indexStartupCost = 0;
7590  *indexTotalCost = 0;
7591  *indexSelectivity = 0;
7592  return;
7593  }
7594 
7595  if (counts.haveFullScan || indexQuals == NIL)
7596  {
7597  /*
7598  * Full index scan will be required. We treat this as if every key in
7599  * the index had been listed in the query; is that reasonable?
7600  */
7601  counts.partialEntries = 0;
7602  counts.exactEntries = numEntries;
7603  counts.searchEntries = numEntries;
7604  }
7605 
7606  /* Will we have more than one iteration of a nestloop scan? */
7607  outer_scans = loop_count;
7608 
7609  /*
7610  * Compute cost to begin scan, first of all, pay attention to pending
7611  * list.
7612  */
7613  entryPagesFetched = numPendingPages;
7614 
7615  /*
7616  * Estimate number of entry pages read. We need to do
7617  * counts.searchEntries searches. Use a power function as it should be,
7618  * but tuples on leaf pages usually is much greater. Here we include all
7619  * searches in entry tree, including search of first entry in partial
7620  * match algorithm
7621  */
7622  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7623 
7624  /*
7625  * Add an estimate of entry pages read by partial match algorithm. It's a
7626  * scan over leaf pages in entry tree. We haven't any useful stats here,
7627  * so estimate it as proportion. Because counts.partialEntries is really
7628  * pretty bogus (see code above), it's possible that it is more than
7629  * numEntries; clamp the proportion to ensure sanity.
7630  */
7631  partialScale = counts.partialEntries / numEntries;
7632  partialScale = Min(partialScale, 1.0);
7633 
7634  entryPagesFetched += ceil(numEntryPages * partialScale);
7635 
7636  /*
7637  * Partial match algorithm reads all data pages before doing actual scan,
7638  * so it's a startup cost. Again, we haven't any useful stats here, so
7639  * estimate it as proportion.
7640  */
7641  dataPagesFetched = ceil(numDataPages * partialScale);
7642 
7643  /*
7644  * Calculate cache effects if more than one scan due to nestloops or array
7645  * quals. The result is pro-rated per nestloop scan, but the array qual
7646  * factor shouldn't be pro-rated (compare genericcostestimate).
7647  */
7648  if (outer_scans > 1 || counts.arrayScans > 1)
7649  {
7650  entryPagesFetched *= outer_scans * counts.arrayScans;
7651  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7652  (BlockNumber) numEntryPages,
7653  numEntryPages, root);
7654  entryPagesFetched /= outer_scans;
7655  dataPagesFetched *= outer_scans * counts.arrayScans;
7656  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7657  (BlockNumber) numDataPages,
7658  numDataPages, root);
7659  dataPagesFetched /= outer_scans;
7660  }
7661 
7662  /*
7663  * Here we use random page cost because logically-close pages could be far
7664  * apart on disk.
7665  */
7666  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7667 
7668  /*
7669  * Now compute the number of data pages fetched during the scan.
7670  *
7671  * We assume every entry to have the same number of items, and that there
7672  * is no overlap between them. (XXX: tsvector and array opclasses collect
7673  * statistics on the frequency of individual keys; it would be nice to use
7674  * those here.)
7675  */
7676  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7677 
7678  /*
7679  * If there is a lot of overlap among the entries, in particular if one of
7680  * the entries is very frequent, the above calculation can grossly
7681  * under-estimate. As a simple cross-check, calculate a lower bound based
7682  * on the overall selectivity of the quals. At a minimum, we must read
7683  * one item pointer for each matching entry.
7684  *
7685  * The width of each item pointer varies, based on the level of
7686  * compression. We don't have statistics on that, but an average of
7687  * around 3 bytes per item is fairly typical.
7688  */
7689  dataPagesFetchedBySel = ceil(*indexSelectivity *
7690  (numTuples / (BLCKSZ / 3)));
7691  if (dataPagesFetchedBySel > dataPagesFetched)
7692  dataPagesFetched = dataPagesFetchedBySel;
7693 
7694  /* Account for cache effects, the same as above */
7695  if (outer_scans > 1 || counts.arrayScans > 1)
7696  {
7697  dataPagesFetched *= outer_scans * counts.arrayScans;
7698  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7699  (BlockNumber) numDataPages,
7700  numDataPages, root);
7701  dataPagesFetched /= outer_scans;
7702  }
7703 
7704  /* And apply random_page_cost as the cost per page */
7705  *indexTotalCost = *indexStartupCost +
7706  dataPagesFetched * spc_random_page_cost;
7707 
7708  /*
7709  * Add on index qual eval costs, much as in genericcostestimate
7710  */
7711  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7712  orderby_operands_eval_cost(root, path);
7713  qual_op_cost = cpu_operator_cost *
7714  (list_length(indexQuals) + list_length(indexOrderBys));
7715 
7716  *indexStartupCost += qual_arg_cost;
7717  *indexTotalCost += qual_arg_cost;
7718  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7719  *indexPages = dataPagesFetched;
7720 }
#define NIL
Definition: pg_list.h:69
BlockNumber nEntryPages
Definition: gin.h:45
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
IndexOptInfo * indexinfo
Definition: relation.h:1031
bool predicate_implied_by(List *predicate_list, List *restrictinfo_list)
Definition: predtest.c:128
#define Min(x, y)
Definition: c.h:806
#define AccessShareLock
Definition: lockdefs.h:36
double partialEntries
Definition: selfuncs.c:7116
Definition: nodes.h:509
double searchEntries
Definition: selfuncs.c:7118
Oid reltablespace
Definition: relation.h:632
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6351
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:666
double tuples
Definition: relation.h:637
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6256
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6376
Definition: type.h:90
double exactEntries
Definition: selfuncs.c:7117
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:7286
bool haveFullScan
Definition: selfuncs.c:7115
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:7119
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:7230
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 6987 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().

6991 {
6992  IndexOptInfo *index = path->indexinfo;
6993  List *qinfos;
6994  GenericCosts costs;
6995  Cost descentCost;
6996 
6997  /* Do preliminary analysis of indexquals */
6998  qinfos = deconstruct_indexquals(path);
6999 
7000  MemSet(&costs, 0, sizeof(costs));
7001 
7002  genericcostestimate(root, path, loop_count, qinfos, &costs);
7003 
7004  /*
7005  * We model index descent costs similarly to those for btree, but to do
7006  * that we first need an idea of the tree height. We somewhat arbitrarily
7007  * assume that the fanout is 100, meaning the tree height is at most
7008  * log100(index->pages).
7009  *
7010  * Although this computation isn't really expensive enough to require
7011  * caching, we might as well use index->tree_height to cache it.
7012  */
7013  if (index->tree_height < 0) /* unknown? */
7014  {
7015  if (index->pages > 1) /* avoid computing log(0) */
7016  index->tree_height = (int) (log(index->pages) / log(100.0));
7017  else
7018  index->tree_height = 0;
7019  }
7020 
7021  /*
7022  * Add a CPU-cost component to represent the costs of initial descent. We
7023  * just use log(N) here not log2(N) since the branching factor isn't
7024  * necessarily two anyway. As for btree, charge once per SA scan.
7025  */
7026  if (index->tuples > 1) /* avoid computing log(0) */
7027  {
7028  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7029  costs.indexStartupCost += descentCost;
7030  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7031  }
7032 
7033  /*
7034  * Likewise add a per-page charge, calculated the same as for btrees.
7035  */
7036  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7037  costs.indexStartupCost += descentCost;
7038  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7039 
7040  *indexStartupCost = costs.indexStartupCost;
7041  *indexTotalCost = costs.indexTotalCost;
7042  *indexSelectivity = costs.indexSelectivity;
7043  *indexCorrelation = costs.indexCorrelation;
7044  *indexPages = costs.numIndexPages;
7045 }
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:6256
Definition: type.h:90
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:639
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6405
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 6939 of file selfuncs.c.

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

Referenced by hashhandler().

6943 {
6944  List *qinfos;
6945  GenericCosts costs;
6946 
6947  /* Do preliminary analysis of indexquals */
6948  qinfos = deconstruct_indexquals(path);
6949 
6950  MemSet(&costs, 0, sizeof(costs));
6951 
6952  genericcostestimate(root, path, loop_count, qinfos, &costs);
6953 
6954  /*
6955  * A hash index has no descent costs as such, since the index AM can go
6956  * directly to the target bucket after computing the hash value. There
6957  * are a couple of other hash-specific costs that we could conceivably add
6958  * here, though:
6959  *
6960  * Ideally we'd charge spc_random_page_cost for each page in the target
6961  * bucket, not just the numIndexPages pages that genericcostestimate
6962  * thought we'd visit. However in most cases we don't know which bucket
6963  * that will be. There's no point in considering the average bucket size
6964  * because the hash AM makes sure that's always one page.
6965  *
6966  * Likewise, we could consider charging some CPU for each index tuple in
6967  * the bucket, if we knew how many there were. But the per-tuple cost is
6968  * just a hash value comparison, not a general datatype-dependent
6969  * comparison, so any such charge ought to be quite a bit less than
6970  * cpu_operator_cost; which makes it probably not worth worrying about.
6971  *
6972  * A bigger issue is that chance hash-value collisions will result in
6973  * wasted probes into the heap. We don't currently attempt to model this
6974  * cost on the grounds that it's rare, but maybe it's not rare enough.
6975  * (Any fix for this ought to consider the generic lossy-operator problem,
6976  * though; it's not entirely hash-specific.)
6977  */
6978 
6979  *indexStartupCost = costs.indexStartupCost;
6980  *indexTotalCost = costs.indexTotalCost;
6981  *indexSelectivity = costs.indexSelectivity;
6982  *indexCorrelation = costs.indexCorrelation;
6983  *indexPages = costs.numIndexPages;
6984 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
#define MemSet(start, val, len)
Definition: c.h:857
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6256
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:6405
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 7048 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().

7052 {
7053  IndexOptInfo *index = path->indexinfo;
7054  List *qinfos;
7055  GenericCosts costs;
7056  Cost descentCost;
7057 
7058  /* Do preliminary analysis of indexquals */
7059  qinfos = deconstruct_indexquals(path);
7060 
7061  MemSet(&costs, 0, sizeof(costs));
7062 
7063  genericcostestimate(root, path, loop_count, qinfos, &costs);
7064 
7065  /*
7066  * We model index descent costs similarly to those for btree, but to do
7067  * that we first need an idea of the tree height. We somewhat arbitrarily
7068  * assume that the fanout is 100, meaning the tree height is at most
7069  * log100(index->pages).
7070  *
7071  * Although this computation isn't really expensive enough to require
7072  * caching, we might as well use index->tree_height to cache it.
7073  */
7074  if (index->tree_height < 0) /* unknown? */
7075  {
7076  if (index->pages > 1) /* avoid computing log(0) */
7077  index->tree_height = (int) (log(index->pages) / log(100.0));
7078  else
7079  index->tree_height = 0;
7080  }
7081 
7082  /*
7083  * Add a CPU-cost component to represent the costs of initial descent. We
7084  * just use log(N) here not log2(N) since the branching factor isn't
7085  * necessarily two anyway. As for btree, charge once per SA scan.
7086  */
7087  if (index->tuples > 1) /* avoid computing log(0) */
7088  {
7089  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7090  costs.indexStartupCost += descentCost;
7091  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7092  }
7093 
7094  /*
7095  * Likewise add a per-page charge, calculated the same as for btrees.
7096  */
7097  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7098  costs.indexStartupCost += descentCost;
7099  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7100 
7101  *indexStartupCost = costs.indexStartupCost;
7102  *indexTotalCost = costs.indexTotalCost;
7103  *indexSelectivity = costs.indexSelectivity;
7104  *indexCorrelation = costs.indexCorrelation;
7105  *indexPages = costs.numIndexPages;
7106 }
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:6256
Definition: type.h:90
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:639
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6405
double numIndexPages
Definition: selfuncs.h:135