PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
index_selfuncs.h File Reference
#include "access/amapi.h"
Include dependency graph for index_selfuncs.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

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

Function Documentation

◆ brincostestimate()

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

Definition at line 7984 of file selfuncs.c.

7988 {
7989  IndexOptInfo *index = path->indexinfo;
7990  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7991  double numPages = index->pages;
7992  RelOptInfo *baserel = index->rel;
7993  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7994  Cost spc_seq_page_cost;
7995  Cost spc_random_page_cost;
7996  double qual_arg_cost;
7997  double qualSelectivity;
7998  BrinStatsData statsData;
7999  double indexRanges;
8000  double minimalRanges;
8001  double estimatedRanges;
8002  double selec;
8003  Relation indexRel;
8004  ListCell *l;
8005  VariableStatData vardata;
8006 
8007  Assert(rte->rtekind == RTE_RELATION);
8008 
8009  /* fetch estimated page cost for the tablespace containing the index */
8010  get_tablespace_page_costs(index->reltablespace,
8011  &spc_random_page_cost,
8012  &spc_seq_page_cost);
8013 
8014  /*
8015  * Obtain some data from the index itself, if possible. Otherwise invent
8016  * some plausible internal statistics based on the relation page count.
8017  */
8018  if (!index->hypothetical)
8019  {
8020  /*
8021  * A lock should have already been obtained on the index in plancat.c.
8022  */
8023  indexRel = index_open(index->indexoid, NoLock);
8024  brinGetStats(indexRel, &statsData);
8025  index_close(indexRel, NoLock);
8026 
8027  /* work out the actual number of ranges in the index */
8028  indexRanges = Max(ceil((double) baserel->pages /
8029  statsData.pagesPerRange), 1.0);
8030  }
8031  else
8032  {
8033  /*
8034  * Assume default number of pages per range, and estimate the number
8035  * of ranges based on that.
8036  */
8037  indexRanges = Max(ceil((double) baserel->pages /
8039 
8041  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
8042  }
8043 
8044  /*
8045  * Compute index correlation
8046  *
8047  * Because we can use all index quals equally when scanning, we can use
8048  * the largest correlation (in absolute value) among columns used by the
8049  * query. Start at zero, the worst possible case. If we cannot find any
8050  * correlation statistics, we will keep it as 0.
8051  */
8052  *indexCorrelation = 0;
8053 
8054  foreach(l, path->indexclauses)
8055  {
8056  IndexClause *iclause = lfirst_node(IndexClause, l);
8057  AttrNumber attnum = index->indexkeys[iclause->indexcol];
8058 
8059  /* attempt to lookup stats in relation for this index column */
8060  if (attnum != 0)
8061  {
8062  /* Simple variable -- look to stats for the underlying table */
8064  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
8065  {
8066  /*
8067  * The hook took control of acquiring a stats tuple. If it
8068  * did supply a tuple, it'd better have supplied a freefunc.
8069  */
8070  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
8071  elog(ERROR,
8072  "no function provided to release variable stats with");
8073  }
8074  else
8075  {
8076  vardata.statsTuple =
8077  SearchSysCache3(STATRELATTINH,
8078  ObjectIdGetDatum(rte->relid),
8080  BoolGetDatum(false));
8081  vardata.freefunc = ReleaseSysCache;
8082  }
8083  }
8084  else
8085  {
8086  /*
8087  * Looks like we've found an expression column in the index. Let's
8088  * see if there's any stats for it.
8089  */
8090 
8091  /* get the attnum from the 0-based index. */
8092  attnum = iclause->indexcol + 1;
8093 
8094  if (get_index_stats_hook &&
8095  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
8096  {
8097  /*
8098  * The hook took control of acquiring a stats tuple. If it
8099  * did supply a tuple, it'd better have supplied a freefunc.
8100  */
8101  if (HeapTupleIsValid(vardata.statsTuple) &&
8102  !vardata.freefunc)
8103  elog(ERROR, "no function provided to release variable stats with");
8104  }
8105  else
8106  {
8107  vardata.statsTuple = SearchSysCache3(STATRELATTINH,
8108  ObjectIdGetDatum(index->indexoid),
8110  BoolGetDatum(false));
8111  vardata.freefunc = ReleaseSysCache;
8112  }
8113  }
8114 
8115  if (HeapTupleIsValid(vardata.statsTuple))
8116  {
8117  AttStatsSlot sslot;
8118 
8119  if (get_attstatsslot(&sslot, vardata.statsTuple,
8120  STATISTIC_KIND_CORRELATION, InvalidOid,
8122  {
8123  double varCorrelation = 0.0;
8124 
8125  if (sslot.nnumbers > 0)
8126  varCorrelation = fabs(sslot.numbers[0]);
8127 
8128  if (varCorrelation > *indexCorrelation)
8129  *indexCorrelation = varCorrelation;
8130 
8131  free_attstatsslot(&sslot);
8132  }
8133  }
8134 
8135  ReleaseVariableStats(vardata);
8136  }
8137 
8138  qualSelectivity = clauselist_selectivity(root, indexQuals,
8139  baserel->relid,
8140  JOIN_INNER, NULL);
8141 
8142  /*
8143  * Now calculate the minimum possible ranges we could match with if all of
8144  * the rows were in the perfect order in the table's heap.
8145  */
8146  minimalRanges = ceil(indexRanges * qualSelectivity);
8147 
8148  /*
8149  * Now estimate the number of ranges that we'll touch by using the
8150  * indexCorrelation from the stats. Careful not to divide by zero (note
8151  * we're using the absolute value of the correlation).
8152  */
8153  if (*indexCorrelation < 1.0e-10)
8154  estimatedRanges = indexRanges;
8155  else
8156  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
8157 
8158  /* we expect to visit this portion of the table */
8159  selec = estimatedRanges / indexRanges;
8160 
8161  CLAMP_PROBABILITY(selec);
8162 
8163  *indexSelectivity = selec;
8164 
8165  /*
8166  * Compute the index qual costs, much as in genericcostestimate, to add to
8167  * the index costs. We can disregard indexorderbys, since BRIN doesn't
8168  * support those.
8169  */
8170  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
8171 
8172  /*
8173  * Compute the startup cost as the cost to read the whole revmap
8174  * sequentially, including the cost to execute the index quals.
8175  */
8176  *indexStartupCost =
8177  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8178  *indexStartupCost += qual_arg_cost;
8179 
8180  /*
8181  * To read a BRIN index there might be a bit of back and forth over
8182  * regular pages, as revmap might point to them out of sequential order;
8183  * calculate the total cost as reading the whole index in random order.
8184  */
8185  *indexTotalCost = *indexStartupCost +
8186  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8187 
8188  /*
8189  * Charge a small amount per range tuple which we expect to match to. This
8190  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8191  * will set a bit for each page in the range when we find a matching
8192  * range, so we must multiply the charge by the number of pages in the
8193  * range.
8194  */
8195  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8196  statsData.pagesPerRange;
8197 
8198  *indexPages = index->pages;
8199 }
int16 AttrNumber
Definition: attnum.h:21
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1640
#define BRIN_DEFAULT_PAGES_PER_RANGE
Definition: brin.h:39
#define REVMAP_PAGE_MAXITEMS
Definition: brin_page.h:93
#define Min(x, y)
Definition: c.h:983
#define Max(x, y)
Definition: c.h:977
#define Assert(condition)
Definition: c.h:837
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:100
double cpu_operator_cost
Definition: costsize.c:134
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:177
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:133
#define NoLock
Definition: lockdefs.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3344
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3234
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
double Cost
Definition: nodes.h:251
@ JOIN_INNER
Definition: nodes.h:293
@ RTE_RELATION
Definition: parsenodes.h:1017
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:570
int16 attnum
Definition: pg_attribute.h:74
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static Datum Int16GetDatum(int16 X)
Definition: postgres.h:172
static Datum BoolGetDatum(bool X)
Definition: postgres.h:102
static Datum ObjectIdGetDatum(Oid X)
Definition: postgres.h:252
#define InvalidOid
Definition: postgres_ext.h:36
tree ctl root
Definition: radixtree.h:1886
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:6471
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:148
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:6501
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:147
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:99
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
float4 * numbers
Definition: lsyscache.h:56
int nnumbers
Definition: lsyscache.h:57
BlockNumber revmapNumPages
Definition: brin.h:35
BlockNumber pagesPerRange
Definition: brin.h:34
AttrNumber indexcol
Definition: pathnodes.h:1771
List * indexclauses
Definition: pathnodes.h:1721
IndexOptInfo * indexinfo
Definition: pathnodes.h:1720
Definition: pg_list.h:54
RTEKind rtekind
Definition: parsenodes.h:1047
Index relid
Definition: pathnodes.h:918
BlockNumber pages
Definition: pathnodes.h:948
HeapTuple statsTuple
Definition: selfuncs.h:89
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:91
Definition: type.h:96
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:269
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:243

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

Referenced by brinhandler().

◆ btcostestimate()

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

Definition at line 6799 of file selfuncs.c.

6803 {
6804  IndexOptInfo *index = path->indexinfo;
6805  GenericCosts costs = {0};
6806  Oid relid;
6807  AttrNumber colnum;
6808  VariableStatData vardata = {0};
6809  double numIndexTuples;
6810  Cost descentCost;
6811  List *indexBoundQuals;
6812  int indexcol;
6813  bool eqQualHere;
6814  bool found_saop;
6815  bool found_is_null_op;
6816  double num_sa_scans;
6817  ListCell *lc;
6818 
6819  /*
6820  * For a btree scan, only leading '=' quals plus inequality quals for the
6821  * immediately next attribute contribute to index selectivity (these are
6822  * the "boundary quals" that determine the starting and stopping points of
6823  * the index scan). Additional quals can suppress visits to the heap, so
6824  * it's OK to count them in indexSelectivity, but they should not count
6825  * for estimating numIndexTuples. So we must examine the given indexquals
6826  * to find out which ones count as boundary quals. We rely on the
6827  * knowledge that they are given in index column order.
6828  *
6829  * For a RowCompareExpr, we consider only the first column, just as
6830  * rowcomparesel() does.
6831  *
6832  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform up
6833  * to N index descents (not just one), but the ScalarArrayOpExpr's
6834  * operator can be considered to act the same as it normally does.
6835  */
6836  indexBoundQuals = NIL;
6837  indexcol = 0;
6838  eqQualHere = false;
6839  found_saop = false;
6840  found_is_null_op = false;
6841  num_sa_scans = 1;
6842  foreach(lc, path->indexclauses)
6843  {
6844  IndexClause *iclause = lfirst_node(IndexClause, lc);
6845  ListCell *lc2;
6846 
6847  if (indexcol != iclause->indexcol)
6848  {
6849  /* Beginning of a new column's quals */
6850  if (!eqQualHere)
6851  break; /* done if no '=' qual for indexcol */
6852  eqQualHere = false;
6853  indexcol++;
6854  if (indexcol != iclause->indexcol)
6855  break; /* no quals at all for indexcol */
6856  }
6857 
6858  /* Examine each indexqual associated with this index clause */
6859  foreach(lc2, iclause->indexquals)
6860  {
6861  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6862  Expr *clause = rinfo->clause;
6863  Oid clause_op = InvalidOid;
6864  int op_strategy;
6865 
6866  if (IsA(clause, OpExpr))
6867  {
6868  OpExpr *op = (OpExpr *) clause;
6869 
6870  clause_op = op->opno;
6871  }
6872  else if (IsA(clause, RowCompareExpr))
6873  {
6874  RowCompareExpr *rc = (RowCompareExpr *) clause;
6875 
6876  clause_op = linitial_oid(rc->opnos);
6877  }
6878  else if (IsA(clause, ScalarArrayOpExpr))
6879  {
6880  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6881  Node *other_operand = (Node *) lsecond(saop->args);
6882  double alength = estimate_array_length(root, other_operand);
6883 
6884  clause_op = saop->opno;
6885  found_saop = true;
6886  /* estimate SA descents by indexBoundQuals only */
6887  if (alength > 1)
6888  num_sa_scans *= alength;
6889  }
6890  else if (IsA(clause, NullTest))
6891  {
6892  NullTest *nt = (NullTest *) clause;
6893 
6894  if (nt->nulltesttype == IS_NULL)
6895  {
6896  found_is_null_op = true;
6897  /* IS NULL is like = for selectivity purposes */
6898  eqQualHere = true;
6899  }
6900  }
6901  else
6902  elog(ERROR, "unsupported indexqual type: %d",
6903  (int) nodeTag(clause));
6904 
6905  /* check for equality operator */
6906  if (OidIsValid(clause_op))
6907  {
6908  op_strategy = get_op_opfamily_strategy(clause_op,
6909  index->opfamily[indexcol]);
6910  Assert(op_strategy != 0); /* not a member of opfamily?? */
6911  if (op_strategy == BTEqualStrategyNumber)
6912  eqQualHere = true;
6913  }
6914 
6915  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6916  }
6917  }
6918 
6919  /*
6920  * If index is unique and we found an '=' clause for each column, we can
6921  * just assume numIndexTuples = 1 and skip the expensive
6922  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6923  * NullTest invalidates that theory, even though it sets eqQualHere.
6924  */
6925  if (index->unique &&
6926  indexcol == index->nkeycolumns - 1 &&
6927  eqQualHere &&
6928  !found_saop &&
6929  !found_is_null_op)
6930  numIndexTuples = 1.0;
6931  else
6932  {
6933  List *selectivityQuals;
6934  Selectivity btreeSelectivity;
6935 
6936  /*
6937  * If the index is partial, AND the index predicate with the
6938  * index-bound quals to produce a more accurate idea of the number of
6939  * rows covered by the bound conditions.
6940  */
6941  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
6942 
6943  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6944  index->rel->relid,
6945  JOIN_INNER,
6946  NULL);
6947  numIndexTuples = btreeSelectivity * index->rel->tuples;
6948 
6949  /*
6950  * btree automatically combines individual ScalarArrayOpExpr primitive
6951  * index scans whenever the tuples covered by the next set of array
6952  * keys are close to tuples covered by the current set. That puts a
6953  * natural ceiling on the worst case number of descents -- there
6954  * cannot possibly be more than one descent per leaf page scanned.
6955  *
6956  * Clamp the number of descents to at most 1/3 the number of index
6957  * pages. This avoids implausibly high estimates with low selectivity
6958  * paths, where scans usually require only one or two descents. This
6959  * is most likely to help when there are several SAOP clauses, where
6960  * naively accepting the total number of distinct combinations of
6961  * array elements as the number of descents would frequently lead to
6962  * wild overestimates.
6963  *
6964  * We somewhat arbitrarily don't just make the cutoff the total number
6965  * of leaf pages (we make it 1/3 the total number of pages instead) to
6966  * give the btree code credit for its ability to continue on the leaf
6967  * level with low selectivity scans.
6968  */
6969  num_sa_scans = Min(num_sa_scans, ceil(index->pages * 0.3333333));
6970  num_sa_scans = Max(num_sa_scans, 1);
6971 
6972  /*
6973  * As in genericcostestimate(), we have to adjust for any
6974  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6975  * to integer.
6976  *
6977  * It is tempting to make genericcostestimate behave as if SAOP
6978  * clauses work in almost the same way as scalar operators during
6979  * btree scans, making the top-level scan look like a continuous scan
6980  * (as opposed to num_sa_scans-many primitive index scans). After
6981  * all, btree scans mostly work like that at runtime. However, such a
6982  * scheme would badly bias genericcostestimate's simplistic approach
6983  * to calculating numIndexPages through prorating.
6984  *
6985  * Stick with the approach taken by non-native SAOP scans for now.
6986  * genericcostestimate will use the Mackert-Lohman formula to
6987  * compensate for repeat page fetches, even though that definitely
6988  * won't happen during btree scans (not for leaf pages, at least).
6989  * We're usually very pessimistic about the number of primitive index
6990  * scans that will be required, but it's not clear how to do better.
6991  */
6992  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6993  }
6994 
6995  /*
6996  * Now do generic index cost estimation.
6997  */
6998  costs.numIndexTuples = numIndexTuples;
6999  costs.num_sa_scans = num_sa_scans;
7000 
7001  genericcostestimate(root, path, loop_count, &costs);
7002 
7003  /*
7004  * Add a CPU-cost component to represent the costs of initial btree
7005  * descent. We don't charge any I/O cost for touching upper btree levels,
7006  * since they tend to stay in cache, but we still have to do about log2(N)
7007  * comparisons to descend a btree of N leaf tuples. We charge one
7008  * cpu_operator_cost per comparison.
7009  *
7010  * If there are ScalarArrayOpExprs, charge this once per estimated SA
7011  * index descent. The ones after the first one are not startup cost so
7012  * far as the overall plan goes, so just add them to "total" cost.
7013  */
7014  if (index->tuples > 1) /* avoid computing log(0) */
7015  {
7016  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
7017  costs.indexStartupCost += descentCost;
7018  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7019  }
7020 
7021  /*
7022  * Even though we're not charging I/O cost for touching upper btree pages,
7023  * it's still reasonable to charge some CPU cost per page descended
7024  * through. Moreover, if we had no such charge at all, bloated indexes
7025  * would appear to have the same search cost as unbloated ones, at least
7026  * in cases where only a single leaf page is expected to be visited. This
7027  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
7028  * touched. The number of such pages is btree tree height plus one (ie,
7029  * we charge for the leaf page too). As above, charge once per estimated
7030  * SA index descent.
7031  */
7032  descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7033  costs.indexStartupCost += descentCost;
7034  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7035 
7036  /*
7037  * If we can get an estimate of the first column's ordering correlation C
7038  * from pg_statistic, estimate the index correlation as C for a
7039  * single-column index, or C * 0.75 for multiple columns. (The idea here
7040  * is that multiple columns dilute the importance of the first column's
7041  * ordering, but don't negate it entirely. Before 8.0 we divided the
7042  * correlation by the number of columns, but that seems too strong.)
7043  */
7044  if (index->indexkeys[0] != 0)
7045  {
7046  /* Simple variable --- look to stats for the underlying table */
7047  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
7048 
7049  Assert(rte->rtekind == RTE_RELATION);
7050  relid = rte->relid;
7051  Assert(relid != InvalidOid);
7052  colnum = index->indexkeys[0];
7053 
7055  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
7056  {
7057  /*
7058  * The hook took control of acquiring a stats tuple. If it did
7059  * supply a tuple, it'd better have supplied a freefunc.
7060  */
7061  if (HeapTupleIsValid(vardata.statsTuple) &&
7062  !vardata.freefunc)
7063  elog(ERROR, "no function provided to release variable stats with");
7064  }
7065  else
7066  {
7067  vardata.statsTuple = SearchSysCache3(STATRELATTINH,
7068  ObjectIdGetDatum(relid),
7069  Int16GetDatum(colnum),
7070  BoolGetDatum(rte->inh));
7071  vardata.freefunc = ReleaseSysCache;
7072  }
7073  }
7074  else
7075  {
7076  /* Expression --- maybe there are stats for the index itself */
7077  relid = index->indexoid;
7078  colnum = 1;
7079 
7080  if (get_index_stats_hook &&
7081  (*get_index_stats_hook) (root, relid, colnum, &vardata))
7082  {
7083  /*
7084  * The hook took control of acquiring a stats tuple. If it did
7085  * supply a tuple, it'd better have supplied a freefunc.
7086  */
7087  if (HeapTupleIsValid(vardata.statsTuple) &&
7088  !vardata.freefunc)
7089  elog(ERROR, "no function provided to release variable stats with");
7090  }
7091  else
7092  {
7093  vardata.statsTuple = SearchSysCache3(STATRELATTINH,
7094  ObjectIdGetDatum(relid),
7095  Int16GetDatum(colnum),
7096  BoolGetDatum(false));
7097  vardata.freefunc = ReleaseSysCache;
7098  }
7099  }
7100 
7101  if (HeapTupleIsValid(vardata.statsTuple))
7102  {
7103  Oid sortop;
7104  AttStatsSlot sslot;
7105 
7106  sortop = get_opfamily_member(index->opfamily[0],
7107  index->opcintype[0],
7108  index->opcintype[0],
7110  if (OidIsValid(sortop) &&
7111  get_attstatsslot(&sslot, vardata.statsTuple,
7112  STATISTIC_KIND_CORRELATION, sortop,
7114  {
7115  double varCorrelation;
7116 
7117  Assert(sslot.nnumbers == 1);
7118  varCorrelation = sslot.numbers[0];
7119 
7120  if (index->reverse_sort[0])
7121  varCorrelation = -varCorrelation;
7122 
7123  if (index->nkeycolumns > 1)
7124  costs.indexCorrelation = varCorrelation * 0.75;
7125  else
7126  costs.indexCorrelation = varCorrelation;
7127 
7128  free_attstatsslot(&sslot);
7129  }
7130  }
7131 
7132  ReleaseVariableStats(vardata);
7133 
7134  *indexStartupCost = costs.indexStartupCost;
7135  *indexTotalCost = costs.indexTotalCost;
7136  *indexSelectivity = costs.indexSelectivity;
7137  *indexCorrelation = costs.indexCorrelation;
7138  *indexPages = costs.numIndexPages;
7139 }
#define OidIsValid(objectId)
Definition: c.h:754
List * lappend(List *list, void *datum)
Definition: list.c:339
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition: lsyscache.c:83
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:166
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define nodeTag(nodeptr)
Definition: nodes.h:133
double Selectivity
Definition: nodes.h:250
#define NIL
Definition: pg_list.h:68
#define lsecond(l)
Definition: pg_list.h:183
#define linitial_oid(l)
Definition: pg_list.h:180
unsigned int Oid
Definition: postgres_ext.h:31
@ IS_NULL
Definition: primnodes.h:1952
#define DEFAULT_PAGE_CPU_MULTIPLIER
Definition: selfuncs.c:144
double estimate_array_length(PlannerInfo *root, Node *arrayexpr)
Definition: selfuncs.c:2139
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
Definition: selfuncs.c:6555
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6778
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTEqualStrategyNumber
Definition: stratnum.h:31
Selectivity indexSelectivity
Definition: selfuncs.h:127
Cost indexStartupCost
Definition: selfuncs.h:125
double indexCorrelation
Definition: selfuncs.h:128
double num_sa_scans
Definition: selfuncs.h:134
Cost indexTotalCost
Definition: selfuncs.h:126
double numIndexPages
Definition: selfuncs.h:131
double numIndexTuples
Definition: selfuncs.h:132
List * indexquals
Definition: pathnodes.h:1769
Definition: nodes.h:129
NullTestType nulltesttype
Definition: primnodes.h:1959
Oid opno
Definition: primnodes.h:818
Expr * clause
Definition: pathnodes.h:2574

References add_predicate_to_index_quals(), ScalarArrayOpExpr::args, Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum(), BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, clauselist_selectivity(), cpu_operator_cost, DEFAULT_PAGE_CPU_MULTIPLIER, elog, ERROR, estimate_array_length(), free_attstatsslot(), VariableStatData::freefunc, genericcostestimate(), get_attstatsslot(), get_index_stats_hook, get_op_opfamily_strategy(), get_opfamily_member(), get_relation_stats_hook, HeapTupleIsValid, IndexPath::indexclauses, IndexClause::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexClause::indexquals, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum(), InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst_node, linitial_oid, lsecond, Max, Min, NIL, AttStatsSlot::nnumbers, nodeTag, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum(), OidIsValid, OpExpr::opno, ScalarArrayOpExpr::opno, planner_rt_fetch, ReleaseSysCache(), ReleaseVariableStats, RangeTblEntry::relid, root, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), and VariableStatData::statsTuple.

Referenced by bthandler().

◆ gincostestimate()

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

Definition at line 7594 of file selfuncs.c.

7598 {
7599  IndexOptInfo *index = path->indexinfo;
7600  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7601  List *selectivityQuals;
7602  double numPages = index->pages,
7603  numTuples = index->tuples;
7604  double numEntryPages,
7605  numDataPages,
7606  numPendingPages,
7607  numEntries;
7608  GinQualCounts counts;
7609  bool matchPossible;
7610  bool fullIndexScan;
7611  double partialScale;
7612  double entryPagesFetched,
7613  dataPagesFetched,
7614  dataPagesFetchedBySel;
7615  double qual_op_cost,
7616  qual_arg_cost,
7617  spc_random_page_cost,
7618  outer_scans;
7619  Cost descentCost;
7620  Relation indexRel;
7621  GinStatsData ginStats;
7622  ListCell *lc;
7623  int i;
7624 
7625  /*
7626  * Obtain statistical information from the meta page, if possible. Else
7627  * set ginStats to zeroes, and we'll cope below.
7628  */
7629  if (!index->hypothetical)
7630  {
7631  /* Lock should have already been obtained in plancat.c */
7632  indexRel = index_open(index->indexoid, NoLock);
7633  ginGetStats(indexRel, &ginStats);
7634  index_close(indexRel, NoLock);
7635  }
7636  else
7637  {
7638  memset(&ginStats, 0, sizeof(ginStats));
7639  }
7640 
7641  /*
7642  * Assuming we got valid (nonzero) stats at all, nPendingPages can be
7643  * trusted, but the other fields are data as of the last VACUUM. We can
7644  * scale them up to account for growth since then, but that method only
7645  * goes so far; in the worst case, the stats might be for a completely
7646  * empty index, and scaling them will produce pretty bogus numbers.
7647  * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
7648  * it's grown more than that, fall back to estimating things only from the
7649  * assumed-accurate index size. But we'll trust nPendingPages in any case
7650  * so long as it's not clearly insane, ie, more than the index size.
7651  */
7652  if (ginStats.nPendingPages < numPages)
7653  numPendingPages = ginStats.nPendingPages;
7654  else
7655  numPendingPages = 0;
7656 
7657  if (numPages > 0 && ginStats.nTotalPages <= numPages &&
7658  ginStats.nTotalPages > numPages / 4 &&
7659  ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
7660  {
7661  /*
7662  * OK, the stats seem close enough to sane to be trusted. But we
7663  * still need to scale them by the ratio numPages / nTotalPages to
7664  * account for growth since the last VACUUM.
7665  */
7666  double scale = numPages / ginStats.nTotalPages;
7667 
7668  numEntryPages = ceil(ginStats.nEntryPages * scale);
7669  numDataPages = ceil(ginStats.nDataPages * scale);
7670  numEntries = ceil(ginStats.nEntries * scale);
7671  /* ensure we didn't round up too much */
7672  numEntryPages = Min(numEntryPages, numPages - numPendingPages);
7673  numDataPages = Min(numDataPages,
7674  numPages - numPendingPages - numEntryPages);
7675  }
7676  else
7677  {
7678  /*
7679  * We might get here because it's a hypothetical index, or an index
7680  * created pre-9.1 and never vacuumed since upgrading (in which case
7681  * its stats would read as zeroes), or just because it's grown too
7682  * much since the last VACUUM for us to put our faith in scaling.
7683  *
7684  * Invent some plausible internal statistics based on the index page
7685  * count (and clamp that to at least 10 pages, just in case). We
7686  * estimate that 90% of the index is entry pages, and the rest is data
7687  * pages. Estimate 100 entries per entry page; this is rather bogus
7688  * since it'll depend on the size of the keys, but it's more robust
7689  * than trying to predict the number of entries per heap tuple.
7690  */
7691  numPages = Max(numPages, 10);
7692  numEntryPages = floor((numPages - numPendingPages) * 0.90);
7693  numDataPages = numPages - numPendingPages - numEntryPages;
7694  numEntries = floor(numEntryPages * 100);
7695  }
7696 
7697  /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
7698  if (numEntries < 1)
7699  numEntries = 1;
7700 
7701  /*
7702  * If the index is partial, AND the index predicate with the index-bound
7703  * quals to produce a more accurate idea of the number of rows covered by
7704  * the bound conditions.
7705  */
7706  selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
7707 
7708  /* Estimate the fraction of main-table tuples that will be visited */
7709  *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7710  index->rel->relid,
7711  JOIN_INNER,
7712  NULL);
7713 
7714  /* fetch estimated page cost for tablespace containing index */
7715  get_tablespace_page_costs(index->reltablespace,
7716  &spc_random_page_cost,
7717  NULL);
7718 
7719  /*
7720  * Generic assumption about index correlation: there isn't any.
7721  */
7722  *indexCorrelation = 0.0;
7723 
7724  /*
7725  * Examine quals to estimate number of search entries & partial matches
7726  */
7727  memset(&counts, 0, sizeof(counts));
7728  counts.arrayScans = 1;
7729  matchPossible = true;
7730 
7731  foreach(lc, path->indexclauses)
7732  {
7733  IndexClause *iclause = lfirst_node(IndexClause, lc);
7734  ListCell *lc2;
7735 
7736  foreach(lc2, iclause->indexquals)
7737  {
7738  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
7739  Expr *clause = rinfo->clause;
7740 
7741  if (IsA(clause, OpExpr))
7742  {
7743  matchPossible = gincost_opexpr(root,
7744  index,
7745  iclause->indexcol,
7746  (OpExpr *) clause,
7747  &counts);
7748  if (!matchPossible)
7749  break;
7750  }
7751  else if (IsA(clause, ScalarArrayOpExpr))
7752  {
7753  matchPossible = gincost_scalararrayopexpr(root,
7754  index,
7755  iclause->indexcol,
7756  (ScalarArrayOpExpr *) clause,
7757  numEntries,
7758  &counts);
7759  if (!matchPossible)
7760  break;
7761  }
7762  else
7763  {
7764  /* shouldn't be anything else for a GIN index */
7765  elog(ERROR, "unsupported GIN indexqual type: %d",
7766  (int) nodeTag(clause));
7767  }
7768  }
7769  }
7770 
7771  /* Fall out if there were any provably-unsatisfiable quals */
7772  if (!matchPossible)
7773  {
7774  *indexStartupCost = 0;
7775  *indexTotalCost = 0;
7776  *indexSelectivity = 0;
7777  return;
7778  }
7779 
7780  /*
7781  * If attribute has a full scan and at the same time doesn't have normal
7782  * scan, then we'll have to scan all non-null entries of that attribute.
7783  * Currently, we don't have per-attribute statistics for GIN. Thus, we
7784  * must assume the whole GIN index has to be scanned in this case.
7785  */
7786  fullIndexScan = false;
7787  for (i = 0; i < index->nkeycolumns; i++)
7788  {
7789  if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
7790  {
7791  fullIndexScan = true;
7792  break;
7793  }
7794  }
7795 
7796  if (fullIndexScan || indexQuals == NIL)
7797  {
7798  /*
7799  * Full index scan will be required. We treat this as if every key in
7800  * the index had been listed in the query; is that reasonable?
7801  */
7802  counts.partialEntries = 0;
7803  counts.exactEntries = numEntries;
7804  counts.searchEntries = numEntries;
7805  }
7806 
7807  /* Will we have more than one iteration of a nestloop scan? */
7808  outer_scans = loop_count;
7809 
7810  /*
7811  * Compute cost to begin scan, first of all, pay attention to pending
7812  * list.
7813  */
7814  entryPagesFetched = numPendingPages;
7815 
7816  /*
7817  * Estimate number of entry pages read. We need to do
7818  * counts.searchEntries searches. Use a power function as it should be,
7819  * but tuples on leaf pages usually is much greater. Here we include all
7820  * searches in entry tree, including search of first entry in partial
7821  * match algorithm
7822  */
7823  entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7824 
7825  /*
7826  * Add an estimate of entry pages read by partial match algorithm. It's a
7827  * scan over leaf pages in entry tree. We haven't any useful stats here,
7828  * so estimate it as proportion. Because counts.partialEntries is really
7829  * pretty bogus (see code above), it's possible that it is more than
7830  * numEntries; clamp the proportion to ensure sanity.
7831  */
7832  partialScale = counts.partialEntries / numEntries;
7833  partialScale = Min(partialScale, 1.0);
7834 
7835  entryPagesFetched += ceil(numEntryPages * partialScale);
7836 
7837  /*
7838  * Partial match algorithm reads all data pages before doing actual scan,
7839  * so it's a startup cost. Again, we haven't any useful stats here, so
7840  * estimate it as proportion.
7841  */
7842  dataPagesFetched = ceil(numDataPages * partialScale);
7843 
7844  *indexStartupCost = 0;
7845  *indexTotalCost = 0;
7846 
7847  /*
7848  * Add a CPU-cost component to represent the costs of initial entry btree
7849  * descent. We don't charge any I/O cost for touching upper btree levels,
7850  * since they tend to stay in cache, but we still have to do about log2(N)
7851  * comparisons to descend a btree of N leaf tuples. We charge one
7852  * cpu_operator_cost per comparison.
7853  *
7854  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
7855  * ones after the first one are not startup cost so far as the overall
7856  * plan is concerned, so add them only to "total" cost.
7857  */
7858  if (numEntries > 1) /* avoid computing log(0) */
7859  {
7860  descentCost = ceil(log(numEntries) / log(2.0)) * cpu_operator_cost;
7861  *indexStartupCost += descentCost * counts.searchEntries;
7862  *indexTotalCost += counts.arrayScans * descentCost * counts.searchEntries;
7863  }
7864 
7865  /*
7866  * Add a cpu cost per entry-page fetched. This is not amortized over a
7867  * loop.
7868  */
7869  *indexStartupCost += entryPagesFetched * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7870  *indexTotalCost += entryPagesFetched * counts.arrayScans * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7871 
7872  /*
7873  * Add a cpu cost per data-page fetched. This is also not amortized over a
7874  * loop. Since those are the data pages from the partial match algorithm,
7875  * charge them as startup cost.
7876  */
7877  *indexStartupCost += DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost * dataPagesFetched;
7878 
7879  /*
7880  * Since we add the startup cost to the total cost later on, remove the
7881  * initial arrayscan from the total.
7882  */
7883  *indexTotalCost += dataPagesFetched * (counts.arrayScans - 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7884 
7885  /*
7886  * Calculate cache effects if more than one scan due to nestloops or array
7887  * quals. The result is pro-rated per nestloop scan, but the array qual
7888  * factor shouldn't be pro-rated (compare genericcostestimate).
7889  */
7890  if (outer_scans > 1 || counts.arrayScans > 1)
7891  {
7892  entryPagesFetched *= outer_scans * counts.arrayScans;
7893  entryPagesFetched = index_pages_fetched(entryPagesFetched,
7894  (BlockNumber) numEntryPages,
7895  numEntryPages, root);
7896  entryPagesFetched /= outer_scans;
7897  dataPagesFetched *= outer_scans * counts.arrayScans;
7898  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7899  (BlockNumber) numDataPages,
7900  numDataPages, root);
7901  dataPagesFetched /= outer_scans;
7902  }
7903 
7904  /*
7905  * Here we use random page cost because logically-close pages could be far
7906  * apart on disk.
7907  */
7908  *indexStartupCost += (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7909 
7910  /*
7911  * Now compute the number of data pages fetched during the scan.
7912  *
7913  * We assume every entry to have the same number of items, and that there
7914  * is no overlap between them. (XXX: tsvector and array opclasses collect
7915  * statistics on the frequency of individual keys; it would be nice to use
7916  * those here.)
7917  */
7918  dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7919 
7920  /*
7921  * If there is a lot of overlap among the entries, in particular if one of
7922  * the entries is very frequent, the above calculation can grossly
7923  * under-estimate. As a simple cross-check, calculate a lower bound based
7924  * on the overall selectivity of the quals. At a minimum, we must read
7925  * one item pointer for each matching entry.
7926  *
7927  * The width of each item pointer varies, based on the level of
7928  * compression. We don't have statistics on that, but an average of
7929  * around 3 bytes per item is fairly typical.
7930  */
7931  dataPagesFetchedBySel = ceil(*indexSelectivity *
7932  (numTuples / (BLCKSZ / 3)));
7933  if (dataPagesFetchedBySel > dataPagesFetched)
7934  dataPagesFetched = dataPagesFetchedBySel;
7935 
7936  /* Add one page cpu-cost to the startup cost */
7937  *indexStartupCost += DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost * counts.searchEntries;
7938 
7939  /*
7940  * Add once again a CPU-cost for those data pages, before amortizing for
7941  * cache.
7942  */
7943  *indexTotalCost += dataPagesFetched * counts.arrayScans * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7944 
7945  /* Account for cache effects, the same as above */
7946  if (outer_scans > 1 || counts.arrayScans > 1)
7947  {
7948  dataPagesFetched *= outer_scans * counts.arrayScans;
7949  dataPagesFetched = index_pages_fetched(dataPagesFetched,
7950  (BlockNumber) numDataPages,
7951  numDataPages, root);
7952  dataPagesFetched /= outer_scans;
7953  }
7954 
7955  /* And apply random_page_cost as the cost per page */
7956  *indexTotalCost += *indexStartupCost +
7957  dataPagesFetched * spc_random_page_cost;
7958 
7959  /*
7960  * Add on index qual eval costs, much as in genericcostestimate. We charge
7961  * cpu but we can disregard indexorderbys, since GIN doesn't support
7962  * those.
7963  */
7964  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
7965  qual_op_cost = cpu_operator_cost * list_length(indexQuals);
7966 
7967  *indexStartupCost += qual_arg_cost;
7968  *indexTotalCost += qual_arg_cost;
7969 
7970  /*
7971  * Add a cpu cost per search entry, corresponding to the actual visited
7972  * entries.
7973  */
7974  *indexTotalCost += (counts.searchEntries * counts.arrayScans) * (qual_op_cost);
7975  /* Now add a cpu cost per tuple in the posting lists / trees */
7976  *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost);
7977  *indexPages = dataPagesFetched;
7978 }
uint32 BlockNumber
Definition: block.h:31
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:908
double cpu_index_tuple_cost
Definition: costsize.c:133
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:624
int i
Definition: isn.c:72
static int list_length(const List *l)
Definition: pg_list.h:152
static int scale
Definition: pgbench.c:181
static bool gincost_scalararrayopexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, ScalarArrayOpExpr *clause, double numIndexEntries, GinQualCounts *counts)
Definition: selfuncs.c:7478
static bool gincost_opexpr(PlannerInfo *root, IndexOptInfo *index, int indexcol, OpExpr *clause, GinQualCounts *counts)
Definition: selfuncs.c:7428
bool attHasNormalScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:7301
double exactEntries
Definition: selfuncs.c:7303
double arrayScans
Definition: selfuncs.c:7305
double partialEntries
Definition: selfuncs.c:7302
bool attHasFullScan[INDEX_MAX_KEYS]
Definition: selfuncs.c:7300
double searchEntries
Definition: selfuncs.c:7304
BlockNumber nDataPages
Definition: gin.h:47
BlockNumber nPendingPages
Definition: gin.h:44
BlockNumber nEntryPages
Definition: gin.h:46
int64 nEntries
Definition: gin.h:48
BlockNumber nTotalPages
Definition: gin.h:45

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

Referenced by ginhandler().

◆ gistcostestimate()

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

Definition at line 7184 of file selfuncs.c.

7188 {
7189  IndexOptInfo *index = path->indexinfo;
7190  GenericCosts costs = {0};
7191  Cost descentCost;
7192 
7193  genericcostestimate(root, path, loop_count, &costs);
7194 
7195  /*
7196  * We model index descent costs similarly to those for btree, but to do
7197  * that we first need an idea of the tree height. We somewhat arbitrarily
7198  * assume that the fanout is 100, meaning the tree height is at most
7199  * log100(index->pages).
7200  *
7201  * Although this computation isn't really expensive enough to require
7202  * caching, we might as well use index->tree_height to cache it.
7203  */
7204  if (index->tree_height < 0) /* unknown? */
7205  {
7206  if (index->pages > 1) /* avoid computing log(0) */
7207  index->tree_height = (int) (log(index->pages) / log(100.0));
7208  else
7209  index->tree_height = 0;
7210  }
7211 
7212  /*
7213  * Add a CPU-cost component to represent the costs of initial descent. We
7214  * just use log(N) here not log2(N) since the branching factor isn't
7215  * necessarily two anyway. As for btree, charge once per SA scan.
7216  */
7217  if (index->tuples > 1) /* avoid computing log(0) */
7218  {
7219  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7220  costs.indexStartupCost += descentCost;
7221  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7222  }
7223 
7224  /*
7225  * Likewise add a per-page charge, calculated the same as for btrees.
7226  */
7227  descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7228  costs.indexStartupCost += descentCost;
7229  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7230 
7231  *indexStartupCost = costs.indexStartupCost;
7232  *indexTotalCost = costs.indexTotalCost;
7233  *indexSelectivity = costs.indexSelectivity;
7234  *indexCorrelation = costs.indexCorrelation;
7235  *indexPages = costs.numIndexPages;
7236 }

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

Referenced by gisthandler().

◆ hashcostestimate()

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

Definition at line 7142 of file selfuncs.c.

7146 {
7147  GenericCosts costs = {0};
7148 
7149  genericcostestimate(root, path, loop_count, &costs);
7150 
7151  /*
7152  * A hash index has no descent costs as such, since the index AM can go
7153  * directly to the target bucket after computing the hash value. There
7154  * are a couple of other hash-specific costs that we could conceivably add
7155  * here, though:
7156  *
7157  * Ideally we'd charge spc_random_page_cost for each page in the target
7158  * bucket, not just the numIndexPages pages that genericcostestimate
7159  * thought we'd visit. However in most cases we don't know which bucket
7160  * that will be. There's no point in considering the average bucket size
7161  * because the hash AM makes sure that's always one page.
7162  *
7163  * Likewise, we could consider charging some CPU for each index tuple in
7164  * the bucket, if we knew how many there were. But the per-tuple cost is
7165  * just a hash value comparison, not a general datatype-dependent
7166  * comparison, so any such charge ought to be quite a bit less than
7167  * cpu_operator_cost; which makes it probably not worth worrying about.
7168  *
7169  * A bigger issue is that chance hash-value collisions will result in
7170  * wasted probes into the heap. We don't currently attempt to model this
7171  * cost on the grounds that it's rare, but maybe it's not rare enough.
7172  * (Any fix for this ought to consider the generic lossy-operator problem,
7173  * though; it's not entirely hash-specific.)
7174  */
7175 
7176  *indexStartupCost = costs.indexStartupCost;
7177  *indexTotalCost = costs.indexTotalCost;
7178  *indexSelectivity = costs.indexSelectivity;
7179  *indexCorrelation = costs.indexCorrelation;
7180  *indexPages = costs.numIndexPages;
7181 }

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

Referenced by hashhandler().

◆ spgcostestimate()

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

Definition at line 7239 of file selfuncs.c.

7243 {
7244  IndexOptInfo *index = path->indexinfo;
7245  GenericCosts costs = {0};
7246  Cost descentCost;
7247 
7248  genericcostestimate(root, path, loop_count, &costs);
7249 
7250  /*
7251  * We model index descent costs similarly to those for btree, but to do
7252  * that we first need an idea of the tree height. We somewhat arbitrarily
7253  * assume that the fanout is 100, meaning the tree height is at most
7254  * log100(index->pages).
7255  *
7256  * Although this computation isn't really expensive enough to require
7257  * caching, we might as well use index->tree_height to cache it.
7258  */
7259  if (index->tree_height < 0) /* unknown? */
7260  {
7261  if (index->pages > 1) /* avoid computing log(0) */
7262  index->tree_height = (int) (log(index->pages) / log(100.0));
7263  else
7264  index->tree_height = 0;
7265  }
7266 
7267  /*
7268  * Add a CPU-cost component to represent the costs of initial descent. We
7269  * just use log(N) here not log2(N) since the branching factor isn't
7270  * necessarily two anyway. As for btree, charge once per SA scan.
7271  */
7272  if (index->tuples > 1) /* avoid computing log(0) */
7273  {
7274  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7275  costs.indexStartupCost += descentCost;
7276  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7277  }
7278 
7279  /*
7280  * Likewise add a per-page charge, calculated the same as for btrees.
7281  */
7282  descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7283  costs.indexStartupCost += descentCost;
7284  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7285 
7286  *indexStartupCost = costs.indexStartupCost;
7287  *indexTotalCost = costs.indexTotalCost;
7288  *indexSelectivity = costs.indexSelectivity;
7289  *indexCorrelation = costs.indexCorrelation;
7290  *indexPages = costs.numIndexPages;
7291 }

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

Referenced by spghandler().