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 7886 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, 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().

7890 {
7891  IndexOptInfo *index = path->indexinfo;
7892  List *indexQuals = path->indexquals;
7893  double numPages = index->pages;
7894  RelOptInfo *baserel = index->rel;
7895  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7896  List *qinfos;
7897  Cost spc_seq_page_cost;
7898  Cost spc_random_page_cost;
7899  double qual_arg_cost;
7900  double qualSelectivity;
7901  BrinStatsData statsData;
7902  double indexRanges;
7903  double minimalRanges;
7904  double estimatedRanges;
7905  double selec;
7906  Relation indexRel;
7907  ListCell *l;
7908  VariableStatData vardata;
7909 
7910  Assert(rte->rtekind == RTE_RELATION);
7911 
7912  /* fetch estimated page cost for the tablespace containing the index */
7914  &spc_random_page_cost,
7915  &spc_seq_page_cost);
7916 
7917  /*
7918  * Obtain some data from the index itself.
7919  */
7920  indexRel = index_open(index->indexoid, AccessShareLock);
7921  brinGetStats(indexRel, &statsData);
7922  index_close(indexRel, AccessShareLock);
7923 
7924  /*
7925  * Compute index correlation
7926  *
7927  * Because we can use all index quals equally when scanning, we can use
7928  * the largest correlation (in absolute value) among columns used by the
7929  * query. Start at zero, the worst possible case. If we cannot find any
7930  * correlation statistics, we will keep it as 0.
7931  */
7932  *indexCorrelation = 0;
7933 
7934  qinfos = deconstruct_indexquals(path);
7935  foreach(l, qinfos)
7936  {
7937  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7938  AttrNumber attnum = index->indexkeys[qinfo->indexcol];
7939 
7940  /* attempt to lookup stats in relation for this index column */
7941  if (attnum != 0)
7942  {
7943  /* Simple variable -- look to stats for the underlying table */
7945  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7946  {
7947  /*
7948  * The hook took control of acquiring a stats tuple. If it
7949  * did supply a tuple, it'd better have supplied a freefunc.
7950  */
7951  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7952  elog(ERROR,
7953  "no function provided to release variable stats with");
7954  }
7955  else
7956  {
7957  vardata.statsTuple =
7959  ObjectIdGetDatum(rte->relid),
7960  Int16GetDatum(attnum),
7961  BoolGetDatum(false));
7962  vardata.freefunc = ReleaseSysCache;
7963  }
7964  }
7965  else
7966  {
7967  /*
7968  * Looks like we've found an expression column in the index. Let's
7969  * see if there's any stats for it.
7970  */
7971 
7972  /* get the attnum from the 0-based index. */
7973  attnum = qinfo->indexcol + 1;
7974 
7975  if (get_index_stats_hook &&
7976  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7977  {
7978  /*
7979  * The hook took control of acquiring a stats tuple. If it
7980  * did supply a tuple, it'd better have supplied a freefunc.
7981  */
7982  if (HeapTupleIsValid(vardata.statsTuple) &&
7983  !vardata.freefunc)
7984  elog(ERROR, "no function provided to release variable stats with");
7985  }
7986  else
7987  {
7989  ObjectIdGetDatum(index->indexoid),
7990  Int16GetDatum(attnum),
7991  BoolGetDatum(false));
7992  vardata.freefunc = ReleaseSysCache;
7993  }
7994  }
7995 
7996  if (HeapTupleIsValid(vardata.statsTuple))
7997  {
7998  AttStatsSlot sslot;
7999 
8000  if (get_attstatsslot(&sslot, vardata.statsTuple,
8003  {
8004  double varCorrelation = 0.0;
8005 
8006  if (sslot.nnumbers > 0)
8007  varCorrelation = Abs(sslot.numbers[0]);
8008 
8009  if (varCorrelation > *indexCorrelation)
8010  *indexCorrelation = varCorrelation;
8011 
8012  free_attstatsslot(&sslot);
8013  }
8014  }
8015 
8016  ReleaseVariableStats(vardata);
8017  }
8018 
8019  qualSelectivity = clauselist_selectivity(root, indexQuals,
8020  baserel->relid,
8021  JOIN_INNER, NULL);
8022 
8023  /* work out the actual number of ranges in the index */
8024  indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
8025  1.0);
8026 
8027  /*
8028  * Now calculate the minimum possible ranges we could match with if all of
8029  * the rows were in the perfect order in the table's heap.
8030  */
8031  minimalRanges = ceil(indexRanges * qualSelectivity);
8032 
8033  /*
8034  * Now estimate the number of ranges that we'll touch by using the
8035  * indexCorrelation from the stats. Careful not to divide by zero (note
8036  * we're using the absolute value of the correlation).
8037  */
8038  if (*indexCorrelation < 1.0e-10)
8039  estimatedRanges = indexRanges;
8040  else
8041  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
8042 
8043  /* we expect to visit this portion of the table */
8044  selec = estimatedRanges / indexRanges;
8045 
8046  CLAMP_PROBABILITY(selec);
8047 
8048  *indexSelectivity = selec;
8049 
8050  /*
8051  * Compute the index qual costs, much as in genericcostestimate, to add to
8052  * the index costs.
8053  */
8054  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
8055  orderby_operands_eval_cost(root, path);
8056 
8057  /*
8058  * Compute the startup cost as the cost to read the whole revmap
8059  * sequentially, including the cost to execute the index quals.
8060  */
8061  *indexStartupCost =
8062  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8063  *indexStartupCost += qual_arg_cost;
8064 
8065  /*
8066  * To read a BRIN index there might be a bit of back and forth over
8067  * regular pages, as revmap might point to them out of sequential order;
8068  * calculate the total cost as reading the whole index in random order.
8069  */
8070  *indexTotalCost = *indexStartupCost +
8071  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8072 
8073  /*
8074  * Charge a small amount per range tuple which we expect to match to. This
8075  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8076  * will set a bit for each page in the range when we find a matching
8077  * range, so we must multiply the charge by the number of pages in the
8078  * range.
8079  */
8080  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8081  statsData.pagesPerRange;
8082 
8083  *indexPages = index->pages;
8084 }
IndexOptInfo * indexinfo
Definition: relation.h:1085
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
#define Min(x, y)
Definition: c.h:795
#define Int16GetDatum(X)
Definition: postgres.h:457
#define AccessShareLock
Definition: lockdefs.h:36
Oid reltablespace
Definition: relation.h:686
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6511
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6416
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6536
#define Abs(x)
Definition: c.h:801
Definition: type.h:89
BlockNumber pages
Definition: relation.h:690
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
List * indexquals
Definition: relation.h:1087
RelOptInfo * rel
Definition: relation.h:687
#define planner_rt_fetch(rti, root)
Definition: relation.h:328
#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:155
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:599
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:789
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
BlockNumber pages
Definition: relation.h:610
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2895
#define Assert(condition)
Definition: c.h:664
#define lfirst(lc)
Definition: pg_list.h:106
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:156
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:176
RTEKind rtekind
Definition: parsenodes.h:945
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
e
Definition: preproc-init.c:82
#define SearchSysCache3(cacheId, key1, key2, key3)
Definition: syscache.h:163
int * indexkeys
Definition: relation.h:696
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:685
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:1066
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 6806 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, 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().

6810 {
6811  IndexOptInfo *index = path->indexinfo;
6812  List *qinfos;
6813  GenericCosts costs;
6814  Oid relid;
6815  AttrNumber colnum;
6816  VariableStatData vardata;
6817  double numIndexTuples;
6818  Cost descentCost;
6819  List *indexBoundQuals;
6820  int indexcol;
6821  bool eqQualHere;
6822  bool found_saop;
6823  bool found_is_null_op;
6824  double num_sa_scans;
6825  ListCell *lc;
6826 
6827  /* Do preliminary analysis of indexquals */
6828  qinfos = deconstruct_indexquals(path);
6829 
6830  /*
6831  * For a btree scan, only leading '=' quals plus inequality quals for the
6832  * immediately next attribute contribute to index selectivity (these are
6833  * the "boundary quals" that determine the starting and stopping points of
6834  * the index scan). Additional quals can suppress visits to the heap, so
6835  * it's OK to count them in indexSelectivity, but they should not count
6836  * for estimating numIndexTuples. So we must examine the given indexquals
6837  * to find out which ones count as boundary quals. We rely on the
6838  * knowledge that they are given in index column order.
6839  *
6840  * For a RowCompareExpr, we consider only the first column, just as
6841  * rowcomparesel() does.
6842  *
6843  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6844  * index scans not one, but the ScalarArrayOpExpr's operator can be
6845  * considered to act the same as it normally does.
6846  */
6847  indexBoundQuals = NIL;
6848  indexcol = 0;
6849  eqQualHere = false;
6850  found_saop = false;
6851  found_is_null_op = false;
6852  num_sa_scans = 1;
6853  foreach(lc, qinfos)
6854  {
6855  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
6856  RestrictInfo *rinfo = qinfo->rinfo;
6857  Expr *clause = rinfo->clause;
6858  Oid clause_op;
6859  int op_strategy;
6860 
6861  if (indexcol != qinfo->indexcol)
6862  {
6863  /* Beginning of a new column's quals */
6864  if (!eqQualHere)
6865  break; /* done if no '=' qual for indexcol */
6866  eqQualHere = false;
6867  indexcol++;
6868  if (indexcol != qinfo->indexcol)
6869  break; /* no quals at all for indexcol */
6870  }
6871 
6872  if (IsA(clause, ScalarArrayOpExpr))
6873  {
6874  int alength = estimate_array_length(qinfo->other_operand);
6875 
6876  found_saop = true;
6877  /* count up number of SA scans induced by indexBoundQuals only */
6878  if (alength > 1)
6879  num_sa_scans *= alength;
6880  }
6881  else if (IsA(clause, NullTest))
6882  {
6883  NullTest *nt = (NullTest *) clause;
6884 
6885  if (nt->nulltesttype == IS_NULL)
6886  {
6887  found_is_null_op = true;
6888  /* IS NULL is like = for selectivity determination purposes */
6889  eqQualHere = true;
6890  }
6891  }
6892 
6893  /*
6894  * We would need to commute the clause_op if not varonleft, except
6895  * that we only care if it's equality or not, so that refinement is
6896  * unnecessary.
6897  */
6898  clause_op = qinfo->clause_op;
6899 
6900  /* check for equality operator */
6901  if (OidIsValid(clause_op))
6902  {
6903  op_strategy = get_op_opfamily_strategy(clause_op,
6904  index->opfamily[indexcol]);
6905  Assert(op_strategy != 0); /* not a member of opfamily?? */
6906  if (op_strategy == BTEqualStrategyNumber)
6907  eqQualHere = true;
6908  }
6909 
6910  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6911  }
6912 
6913  /*
6914  * If index is unique and we found an '=' clause for each column, we can
6915  * just assume numIndexTuples = 1 and skip the expensive
6916  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6917  * NullTest invalidates that theory, even though it sets eqQualHere.
6918  */
6919  if (index->unique &&
6920  indexcol == index->ncolumns - 1 &&
6921  eqQualHere &&
6922  !found_saop &&
6923  !found_is_null_op)
6924  numIndexTuples = 1.0;
6925  else
6926  {
6927  List *selectivityQuals;
6928  Selectivity btreeSelectivity;
6929 
6930  /*
6931  * If the index is partial, AND the index predicate with the
6932  * index-bound quals to produce a more accurate idea of the number of
6933  * rows covered by the bound conditions.
6934  */
6935  selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
6936 
6937  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6938  index->rel->relid,
6939  JOIN_INNER,
6940  NULL);
6941  numIndexTuples = btreeSelectivity * index->rel->tuples;
6942 
6943  /*
6944  * As in genericcostestimate(), we have to adjust for any
6945  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6946  * to integer.
6947  */
6948  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6949  }
6950 
6951  /*
6952  * Now do generic index cost estimation.
6953  */
6954  MemSet(&costs, 0, sizeof(costs));
6955  costs.numIndexTuples = numIndexTuples;
6956 
6957  genericcostestimate(root, path, loop_count, qinfos, &costs);
6958 
6959  /*
6960  * Add a CPU-cost component to represent the costs of initial btree
6961  * descent. We don't charge any I/O cost for touching upper btree levels,
6962  * since they tend to stay in cache, but we still have to do about log2(N)
6963  * comparisons to descend a btree of N leaf tuples. We charge one
6964  * cpu_operator_cost per comparison.
6965  *
6966  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6967  * ones after the first one are not startup cost so far as the overall
6968  * plan is concerned, so add them only to "total" cost.
6969  */
6970  if (index->tuples > 1) /* avoid computing log(0) */
6971  {
6972  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6973  costs.indexStartupCost += descentCost;
6974  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6975  }
6976 
6977  /*
6978  * Even though we're not charging I/O cost for touching upper btree pages,
6979  * it's still reasonable to charge some CPU cost per page descended
6980  * through. Moreover, if we had no such charge at all, bloated indexes
6981  * would appear to have the same search cost as unbloated ones, at least
6982  * in cases where only a single leaf page is expected to be visited. This
6983  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6984  * touched. The number of such pages is btree tree height plus one (ie,
6985  * we charge for the leaf page too). As above, charge once per SA scan.
6986  */
6987  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6988  costs.indexStartupCost += descentCost;
6989  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6990 
6991  /*
6992  * If we can get an estimate of the first column's ordering correlation C
6993  * from pg_statistic, estimate the index correlation as C for a
6994  * single-column index, or C * 0.75 for multiple columns. (The idea here
6995  * is that multiple columns dilute the importance of the first column's
6996  * ordering, but don't negate it entirely. Before 8.0 we divided the
6997  * correlation by the number of columns, but that seems too strong.)
6998  */
6999  MemSet(&vardata, 0, sizeof(vardata));
7000 
7001  if (index->indexkeys[0] != 0)
7002  {
7003  /* Simple variable --- look to stats for the underlying table */
7004  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
7005 
7006  Assert(rte->rtekind == RTE_RELATION);
7007  relid = rte->relid;
7008  Assert(relid != InvalidOid);
7009  colnum = index->indexkeys[0];
7010 
7012  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
7013  {
7014  /*
7015  * The hook took control of acquiring a stats tuple. If it did
7016  * supply a tuple, it'd better have supplied a freefunc.
7017  */
7018  if (HeapTupleIsValid(vardata.statsTuple) &&
7019  !vardata.freefunc)
7020  elog(ERROR, "no function provided to release variable stats with");
7021  }
7022  else
7023  {
7025  ObjectIdGetDatum(relid),
7026  Int16GetDatum(colnum),
7027  BoolGetDatum(rte->inh));
7028  vardata.freefunc = ReleaseSysCache;
7029  }
7030  }
7031  else
7032  {
7033  /* Expression --- maybe there are stats for the index itself */
7034  relid = index->indexoid;
7035  colnum = 1;
7036 
7037  if (get_index_stats_hook &&
7038  (*get_index_stats_hook) (root, relid, colnum, &vardata))
7039  {
7040  /*
7041  * The hook took control of acquiring a stats tuple. If it did
7042  * supply a tuple, it'd better have supplied a freefunc.
7043  */
7044  if (HeapTupleIsValid(vardata.statsTuple) &&
7045  !vardata.freefunc)
7046  elog(ERROR, "no function provided to release variable stats with");
7047  }
7048  else
7049  {
7051  ObjectIdGetDatum(relid),
7052  Int16GetDatum(colnum),
7053  BoolGetDatum(false));
7054  vardata.freefunc = ReleaseSysCache;
7055  }
7056  }
7057 
7058  if (HeapTupleIsValid(vardata.statsTuple))
7059  {
7060  Oid sortop;
7061  AttStatsSlot sslot;
7062 
7063  sortop = get_opfamily_member(index->opfamily[0],
7064  index->opcintype[0],
7065  index->opcintype[0],
7067  if (OidIsValid(sortop) &&
7068  get_attstatsslot(&sslot, vardata.statsTuple,
7071  {
7072  double varCorrelation;
7073 
7074  Assert(sslot.nnumbers == 1);
7075  varCorrelation = sslot.numbers[0];
7076 
7077  if (index->reverse_sort[0])
7078  varCorrelation = -varCorrelation;
7079 
7080  if (index->ncolumns > 1)
7081  costs.indexCorrelation = varCorrelation * 0.75;
7082  else
7083  costs.indexCorrelation = varCorrelation;
7084 
7085  free_attstatsslot(&sslot);
7086  }
7087  }
7088 
7089  ReleaseVariableStats(vardata);
7090 
7091  *indexStartupCost = costs.indexStartupCost;
7092  *indexTotalCost = costs.indexTotalCost;
7093  *indexSelectivity = costs.indexSelectivity;
7094  *indexCorrelation = costs.indexCorrelation;
7095  *indexPages = costs.numIndexPages;
7096 }
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:1085
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
double tuples
Definition: relation.h:611
static List * add_predicate_to_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6784
#define Int16GetDatum(X)
Definition: postgres.h:457
#define MemSet(start, val, len)
Definition: c.h:846
double Selectivity
Definition: nodes.h:639
double tuples
Definition: relation.h:691
unsigned int Oid
Definition: postgres_ext.h:31
int tree_height
Definition: relation.h:692
#define OidIsValid(objectId)
Definition: c.h:532
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6416
bool unique
Definition: relation.h:719
Definition: type.h:89
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2158
RelOptInfo * rel
Definition: relation.h:687
#define planner_rt_fetch(rti, root)
Definition: relation.h:328
#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:155
double rint(double x)
Definition: rint.c:22
int ncolumns
Definition: relation.h:695
Index relid
Definition: relation.h:599
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1801
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
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2895
#define Assert(condition)
Definition: c.h:664
#define lfirst(lc)
Definition: pg_list.h:106
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:156
Oid * opcintype
Definition: relation.h:699
Cost indexStartupCost
Definition: selfuncs.h:129
Oid * opfamily
Definition: relation.h:698
RTEKind rtekind
Definition: parsenodes.h:945
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:163
int * indexkeys
Definition: relation.h:696
#define elog
Definition: elog.h:219
Oid indexoid
Definition: relation.h:685
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:701
#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:6565
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 7561 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, 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().

7565 {
7566  IndexOptInfo *index = path->indexinfo;
7567  List *indexQuals = path->indexquals;
7568  List *indexOrderBys = path->indexorderbys;
7569  List *qinfos;
7570  ListCell *l;
7571  List *selectivityQuals;
7572  double numPages = index->pages,
7573  numTuples = index->tuples;
7574  double numEntryPages,
7575  numDataPages,
7576  numPendingPages,
7577  numEntries;
7578  GinQualCounts counts;
7579  bool matchPossible;
7580  double partialScale;
7581  double entryPagesFetched,
7582  dataPagesFetched,
7583  dataPagesFetchedBySel;
7584  double qual_op_cost,
7585  qual_arg_cost,
7586  spc_random_page_cost,
7587  outer_scans;
7588  Relation indexRel;
7589  GinStatsData ginStats;
7590 
7591  /* Do preliminary analysis of indexquals */
7592  qinfos = deconstruct_indexquals(path);
7593 
7594  /*
7595  * Obtain statistical information from the meta page, if possible. Else
7596  * set ginStats to zeroes, and we'll cope below.
7597  */
7598  if (!index->hypothetical)
7599  {
7600  indexRel = index_open(index->indexoid, AccessShareLock);
7601  ginGetStats(indexRel, &ginStats);
7602  index_close(indexRel, AccessShareLock);
7603  }
7604  else
7605  {
7606  memset(&ginStats, 0, sizeof(ginStats));
7607  }
7608 
7609  /*
7610  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7611  * trusted, but the other fields are data as of the last VACUUM. We can
7612  * scale them up to account for growth since then, but that method only
7613  * goes so far; in the worst case, the stats might be for a completely
7614  * empty index, and scaling them will produce pretty bogus numbers.
7615  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7616  * it's grown more than that, fall back to estimating things only from the
7617  * assumed-accurate index size. But we'll trust nPendingPages in any case
7618  * so long as it's not clearly insane, ie, more than the index size.
7619  */
7620  if (ginStats.nPendingPages < numPages)
7621  numPendingPages = ginStats.nPendingPages;
7622  else
7623  numPendingPages = 0;
7624 
7625  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7626  ginStats.nTotalPages > numPages / 4 &&
7627  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7628  {
7629  /*
7630  * OK, the stats seem close enough to sane to be trusted. But we
7631  * still need to scale them by the ratio numPages / nTotalPages to
7632  * account for growth since the last VACUUM.
7633  */
7634  double scale = numPages / ginStats.nTotalPages;
7635 
7636  numEntryPages = ceil(ginStats.nEntryPages * scale);
7637  numDataPages = ceil(ginStats.nDataPages * scale);
7638  numEntries = ceil(ginStats.nEntries * scale);
7639  /* ensure we didn't round up too much */
7640  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7641  numDataPages = Min(numDataPages,
7642  numPages - numPendingPages - numEntryPages);
7643  }
7644  else
7645  {
7646  /*
7647  * We might get here because it's a hypothetical index, or an index
7648  * created pre-9.1 and never vacuumed since upgrading (in which case
7649  * its stats would read as zeroes), or just because it's grown too
7650  * much since the last VACUUM for us to put our faith in scaling.
7651  *
7652  * Invent some plausible internal statistics based on the index page
7653  * count (and clamp that to at least 10 pages, just in case). We
7654  * estimate that 90% of the index is entry pages, and the rest is data
7655  * pages. Estimate 100 entries per entry page; this is rather bogus
7656  * since it'll depend on the size of the keys, but it's more robust
7657  * than trying to predict the number of entries per heap tuple.
7658  */
7659  numPages = Max(numPages, 10);
7660  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7661  numDataPages = numPages - numPendingPages - numEntryPages;
7662  numEntries = floor(numEntryPages * 100);
7663  }
7664 
7665  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7666  if (numEntries < 1)
7667  numEntries = 1;
7668 
7669  /*
7670  * Include predicate in selectivityQuals (should match
7671  * genericcostestimate)
7672  */
7673  if (index->indpred != NIL)
7674  {
7675  List *predExtraQuals = NIL;
7676 
7677  foreach(l, index->indpred)
7678  {
7679  Node *predQual = (Node *) lfirst(l);
7680  List *oneQual = list_make1(predQual);
7681 
7682  if (!predicate_implied_by(oneQual, indexQuals, false))
7683  predExtraQuals = list_concat(predExtraQuals, oneQual);
7684  }
7685  /* list_concat avoids modifying the passed-in indexQuals list */
7686  selectivityQuals = list_concat(predExtraQuals, indexQuals);
7687  }
7688  else
7689  selectivityQuals = indexQuals;
7690 
7691  /* Estimate the fraction of main-table tuples that will be visited */
7692  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7693  index->rel->relid,
7694  JOIN_INNER,
7695  NULL);
7696 
7697  /* fetch estimated page cost for tablespace containing index */
7699  &spc_random_page_cost,
7700  NULL);
7701 
7702  /*
7703  * Generic assumption about index correlation: there isn't any.
7704  */
7705  *indexCorrelation = 0.0;
7706 
7707  /*
7708  * Examine quals to estimate number of search entries & partial matches
7709  */
7710  memset(&counts, 0, sizeof(counts));
7711  counts.arrayScans = 1;
7712  matchPossible = true;
7713 
7714  foreach(l, qinfos)
7715  {
7716  IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7717  Expr *clause = qinfo->rinfo->clause;
7718 
7719  if (IsA(clause, OpExpr))
7720  {
7721  matchPossible = gincost_opexpr(root,
7722  index,
7723  qinfo,
7724  &counts);
7725  if (!matchPossible)
7726  break;
7727  }
7728  else if (IsA(clause, ScalarArrayOpExpr))
7729  {
7730  matchPossible = gincost_scalararrayopexpr(root,
7731  index,
7732  qinfo,
7733  numEntries,
7734  &counts);
7735  if (!matchPossible)
7736  break;
7737  }
7738  else
7739  {
7740  /* shouldn't be anything else for a GIN index */
7741  elog(ERROR, "unsupported GIN indexqual type: %d",
7742  (int) nodeTag(clause));
7743  }
7744  }
7745 
7746  /* Fall out if there were any provably-unsatisfiable quals */
7747  if (!matchPossible)
7748  {
7749  *indexStartupCost = 0;
7750  *indexTotalCost = 0;
7751  *indexSelectivity = 0;
7752  return;
7753  }
7754 
7755  if (counts.haveFullScan || indexQuals == NIL)
7756  {
7757  /*
7758  * Full index scan will be required. We treat this as if every key in
7759  * the index had been listed in the query; is that reasonable?
7760  */
7761  counts.partialEntries = 0;
7762  counts.exactEntries = numEntries;
7763  counts.searchEntries = numEntries;
7764  }
7765 
7766  /* Will we have more than one iteration of a nestloop scan? */
7767  outer_scans = loop_count;
7768 
7769  /*
7770  * Compute cost to begin scan, first of all, pay attention to pending
7771  * list.
7772  */
7773  entryPagesFetched = numPendingPages;
7774 
7775  /*
7776  * Estimate number of entry pages read. We need to do
7777  * counts.searchEntries searches. Use a power function as it should be,
7778  * but tuples on leaf pages usually is much greater. Here we include all
7779  * searches in entry tree, including search of first entry in partial
7780  * match algorithm
7781  */
7782  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7783 
7784  /*
7785  * Add an estimate of entry pages read by partial match algorithm. It's a
7786  * scan over leaf pages in entry tree. We haven't any useful stats here,
7787  * so estimate it as proportion. Because counts.partialEntries is really
7788  * pretty bogus (see code above), it's possible that it is more than
7789  * numEntries; clamp the proportion to ensure sanity.
7790  */
7791  partialScale = counts.partialEntries / numEntries;
7792  partialScale = Min(partialScale, 1.0);
7793 
7794  entryPagesFetched += ceil(numEntryPages * partialScale);
7795 
7796  /*
7797  * Partial match algorithm reads all data pages before doing actual scan,
7798  * so it's a startup cost. Again, we haven't any useful stats here, so
7799  * estimate it as proportion.
7800  */
7801  dataPagesFetched = ceil(numDataPages * partialScale);
7802 
7803  /*
7804  * Calculate cache effects if more than one scan due to nestloops or array
7805  * quals. The result is pro-rated per nestloop scan, but the array qual
7806  * factor shouldn't be pro-rated (compare genericcostestimate).
7807  */
7808  if (outer_scans > 1 || counts.arrayScans > 1)
7809  {
7810  entryPagesFetched *= outer_scans * counts.arrayScans;
7811  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7812  (BlockNumber) numEntryPages,
7813  numEntryPages, root);
7814  entryPagesFetched /= outer_scans;
7815  dataPagesFetched *= outer_scans * counts.arrayScans;
7816  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7817  (BlockNumber) numDataPages,
7818  numDataPages, root);
7819  dataPagesFetched /= outer_scans;
7820  }
7821 
7822  /*
7823  * Here we use random page cost because logically-close pages could be far
7824  * apart on disk.
7825  */
7826  *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7827 
7828  /*
7829  * Now compute the number of data pages fetched during the scan.
7830  *
7831  * We assume every entry to have the same number of items, and that there
7832  * is no overlap between them. (XXX: tsvector and array opclasses collect
7833  * statistics on the frequency of individual keys; it would be nice to use
7834  * those here.)
7835  */
7836  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7837 
7838  /*
7839  * If there is a lot of overlap among the entries, in particular if one of
7840  * the entries is very frequent, the above calculation can grossly
7841  * under-estimate. As a simple cross-check, calculate a lower bound based
7842  * on the overall selectivity of the quals. At a minimum, we must read
7843  * one item pointer for each matching entry.
7844  *
7845  * The width of each item pointer varies, based on the level of
7846  * compression. We don't have statistics on that, but an average of
7847  * around 3 bytes per item is fairly typical.
7848  */
7849  dataPagesFetchedBySel = ceil(*indexSelectivity *
7850  (numTuples / (BLCKSZ / 3)));
7851  if (dataPagesFetchedBySel > dataPagesFetched)
7852  dataPagesFetched = dataPagesFetchedBySel;
7853 
7854  /* Account for cache effects, the same as above */
7855  if (outer_scans > 1 || counts.arrayScans > 1)
7856  {
7857  dataPagesFetched *= outer_scans * counts.arrayScans;
7858  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7859  (BlockNumber) numDataPages,
7860  numDataPages, root);
7861  dataPagesFetched /= outer_scans;
7862  }
7863 
7864  /* And apply random_page_cost as the cost per page */
7865  *indexTotalCost = *indexStartupCost +
7866  dataPagesFetched * spc_random_page_cost;
7867 
7868  /*
7869  * Add on index qual eval costs, much as in genericcostestimate
7870  */
7871  qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7872  orderby_operands_eval_cost(root, path);
7873  qual_op_cost = cpu_operator_cost *
7874  (list_length(indexQuals) + list_length(indexOrderBys));
7875 
7876  *indexStartupCost += qual_arg_cost;
7877  *indexTotalCost += qual_arg_cost;
7878  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7879  *indexPages = dataPagesFetched;
7880 }
#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:1085
#define Min(x, y)
Definition: c.h:795
#define AccessShareLock
Definition: lockdefs.h:36
double partialEntries
Definition: selfuncs.c:7276
Definition: nodes.h:509
double searchEntries
Definition: selfuncs.c:7278
Oid reltablespace
Definition: relation.h:686
static Cost other_operands_eval_cost(PlannerInfo *root, List *qinfos)
Definition: selfuncs.c:6511
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:721
double tuples
Definition: relation.h:691
RestrictInfo * rinfo
Definition: selfuncs.h:106
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6416
static Cost orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
Definition: selfuncs.c:6536
Definition: type.h:89
double exactEntries
Definition: selfuncs.c:7277
BlockNumber pages
Definition: relation.h:690
#define list_make1(x1)
Definition: pg_list.h:139
List * indexquals
Definition: relation.h:1087
RelOptInfo * rel
Definition: relation.h:687
#define ERROR
Definition: elog.h:43
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7446
bool haveFullScan
Definition: selfuncs.c:7275
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:599
Expr * clause
Definition: relation.h:1801
BlockNumber nPendingPages
Definition: gin.h:43
double arrayScans
Definition: selfuncs.c:7279
List * indexorderbys
Definition: relation.h:1089
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:634
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, IndexQualInfo *qinfo, GinQualCounts *counts)
Definition: selfuncs.c:7390
BlockNumber nDataPages
Definition: gin.h:46
#define Max(x, y)
Definition: c.h:789
#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:685
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:99
List * indpred
Definition: relation.h:708
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 7147 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().

7151 {
7152  IndexOptInfo *index = path->indexinfo;
7153  List *qinfos;
7154  GenericCosts costs;
7155  Cost descentCost;
7156 
7157  /* Do preliminary analysis of indexquals */
7158  qinfos = deconstruct_indexquals(path);
7159 
7160  MemSet(&costs, 0, sizeof(costs));
7161 
7162  genericcostestimate(root, path, loop_count, qinfos, &costs);
7163 
7164  /*
7165  * We model index descent costs similarly to those for btree, but to do
7166  * that we first need an idea of the tree height. We somewhat arbitrarily
7167  * assume that the fanout is 100, meaning the tree height is at most
7168  * log100(index->pages).
7169  *
7170  * Although this computation isn't really expensive enough to require
7171  * caching, we might as well use index->tree_height to cache it.
7172  */
7173  if (index->tree_height < 0) /* unknown? */
7174  {
7175  if (index->pages > 1) /* avoid computing log(0) */
7176  index->tree_height = (int) (log(index->pages) / log(100.0));
7177  else
7178  index->tree_height = 0;
7179  }
7180 
7181  /*
7182  * Add a CPU-cost component to represent the costs of initial descent. We
7183  * just use log(N) here not log2(N) since the branching factor isn't
7184  * necessarily two anyway. As for btree, charge once per SA scan.
7185  */
7186  if (index->tuples > 1) /* avoid computing log(0) */
7187  {
7188  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7189  costs.indexStartupCost += descentCost;
7190  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7191  }
7192 
7193  /*
7194  * Likewise add a per-page charge, calculated the same as for btrees.
7195  */
7196  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7197  costs.indexStartupCost += descentCost;
7198  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7199 
7200  *indexStartupCost = costs.indexStartupCost;
7201  *indexTotalCost = costs.indexTotalCost;
7202  *indexSelectivity = costs.indexSelectivity;
7203  *indexCorrelation = costs.indexCorrelation;
7204  *indexPages = costs.numIndexPages;
7205 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
IndexOptInfo * indexinfo
Definition: relation.h:1085
#define MemSet(start, val, len)
Definition: c.h:846
double tuples
Definition: relation.h:691
int tree_height
Definition: relation.h:692
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6416
Definition: type.h:89
BlockNumber pages
Definition: relation.h:690
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:6565
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 7099 of file selfuncs.c.

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

Referenced by hashhandler().

7103 {
7104  List *qinfos;
7105  GenericCosts costs;
7106 
7107  /* Do preliminary analysis of indexquals */
7108  qinfos = deconstruct_indexquals(path);
7109 
7110  MemSet(&costs, 0, sizeof(costs));
7111 
7112  genericcostestimate(root, path, loop_count, qinfos, &costs);
7113 
7114  /*
7115  * A hash index has no descent costs as such, since the index AM can go
7116  * directly to the target bucket after computing the hash value. There
7117  * are a couple of other hash-specific costs that we could conceivably add
7118  * here, though:
7119  *
7120  * Ideally we'd charge spc_random_page_cost for each page in the target
7121  * bucket, not just the numIndexPages pages that genericcostestimate
7122  * thought we'd visit. However in most cases we don't know which bucket
7123  * that will be. There's no point in considering the average bucket size
7124  * because the hash AM makes sure that's always one page.
7125  *
7126  * Likewise, we could consider charging some CPU for each index tuple in
7127  * the bucket, if we knew how many there were. But the per-tuple cost is
7128  * just a hash value comparison, not a general datatype-dependent
7129  * comparison, so any such charge ought to be quite a bit less than
7130  * cpu_operator_cost; which makes it probably not worth worrying about.
7131  *
7132  * A bigger issue is that chance hash-value collisions will result in
7133  * wasted probes into the heap. We don't currently attempt to model this
7134  * cost on the grounds that it's rare, but maybe it's not rare enough.
7135  * (Any fix for this ought to consider the generic lossy-operator problem,
7136  * though; it's not entirely hash-specific.)
7137  */
7138 
7139  *indexStartupCost = costs.indexStartupCost;
7140  *indexTotalCost = costs.indexTotalCost;
7141  *indexSelectivity = costs.indexSelectivity;
7142  *indexCorrelation = costs.indexCorrelation;
7143  *indexPages = costs.numIndexPages;
7144 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
#define MemSet(start, val, len)
Definition: c.h:846
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6416
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:6565
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 7208 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().

7212 {
7213  IndexOptInfo *index = path->indexinfo;
7214  List *qinfos;
7215  GenericCosts costs;
7216  Cost descentCost;
7217 
7218  /* Do preliminary analysis of indexquals */
7219  qinfos = deconstruct_indexquals(path);
7220 
7221  MemSet(&costs, 0, sizeof(costs));
7222 
7223  genericcostestimate(root, path, loop_count, qinfos, &costs);
7224 
7225  /*
7226  * We model index descent costs similarly to those for btree, but to do
7227  * that we first need an idea of the tree height. We somewhat arbitrarily
7228  * assume that the fanout is 100, meaning the tree height is at most
7229  * log100(index->pages).
7230  *
7231  * Although this computation isn't really expensive enough to require
7232  * caching, we might as well use index->tree_height to cache it.
7233  */
7234  if (index->tree_height < 0) /* unknown? */
7235  {
7236  if (index->pages > 1) /* avoid computing log(0) */
7237  index->tree_height = (int) (log(index->pages) / log(100.0));
7238  else
7239  index->tree_height = 0;
7240  }
7241 
7242  /*
7243  * Add a CPU-cost component to represent the costs of initial descent. We
7244  * just use log(N) here not log2(N) since the branching factor isn't
7245  * necessarily two anyway. As for btree, charge once per SA scan.
7246  */
7247  if (index->tuples > 1) /* avoid computing log(0) */
7248  {
7249  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7250  costs.indexStartupCost += descentCost;
7251  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7252  }
7253 
7254  /*
7255  * Likewise add a per-page charge, calculated the same as for btrees.
7256  */
7257  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7258  costs.indexStartupCost += descentCost;
7259  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7260 
7261  *indexStartupCost = costs.indexStartupCost;
7262  *indexTotalCost = costs.indexTotalCost;
7263  *indexSelectivity = costs.indexSelectivity;
7264  *indexCorrelation = costs.indexCorrelation;
7265  *indexPages = costs.numIndexPages;
7266 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
IndexOptInfo * indexinfo
Definition: relation.h:1085
#define MemSet(start, val, len)
Definition: c.h:846
double tuples
Definition: relation.h:691
int tree_height
Definition: relation.h:692
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6416
Definition: type.h:89
BlockNumber pages
Definition: relation.h:690
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:6565
double numIndexPages
Definition: selfuncs.h:135