PostgreSQL Source Code  git master
index_selfuncs.h File Reference
#include "access/amapi.h"
Include dependency graph for index_selfuncs.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

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

Function Documentation

◆ brincostestimate()

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

Definition at line 7815 of file selfuncs.c.

7819 {
7820  IndexOptInfo *index = path->indexinfo;
7821  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7822  double numPages = index->pages;
7823  RelOptInfo *baserel = index->rel;
7824  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7825  Cost spc_seq_page_cost;
7826  Cost spc_random_page_cost;
7827  double qual_arg_cost;
7828  double qualSelectivity;
7829  BrinStatsData statsData;
7830  double indexRanges;
7831  double minimalRanges;
7832  double estimatedRanges;
7833  double selec;
7834  Relation indexRel;
7835  ListCell *l;
7836  VariableStatData vardata;
7837 
7838  Assert(rte->rtekind == RTE_RELATION);
7839 
7840  /* fetch estimated page cost for the tablespace containing the index */
7841  get_tablespace_page_costs(index->reltablespace,
7842  &spc_random_page_cost,
7843  &spc_seq_page_cost);
7844 
7845  /*
7846  * Obtain some data from the index itself, if possible. Otherwise invent
7847  * some plausible internal statistics based on the relation page count.
7848  */
7849  if (!index->hypothetical)
7850  {
7851  /*
7852  * A lock should have already been obtained on the index in plancat.c.
7853  */
7854  indexRel = index_open(index->indexoid, NoLock);
7855  brinGetStats(indexRel, &statsData);
7856  index_close(indexRel, NoLock);
7857 
7858  /* work out the actual number of ranges in the index */
7859  indexRanges = Max(ceil((double) baserel->pages /
7860  statsData.pagesPerRange), 1.0);
7861  }
7862  else
7863  {
7864  /*
7865  * Assume default number of pages per range, and estimate the number
7866  * of ranges based on that.
7867  */
7868  indexRanges = Max(ceil((double) baserel->pages /
7870 
7872  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
7873  }
7874 
7875  /*
7876  * Compute index correlation
7877  *
7878  * Because we can use all index quals equally when scanning, we can use
7879  * the largest correlation (in absolute value) among columns used by the
7880  * query. Start at zero, the worst possible case. If we cannot find any
7881  * correlation statistics, we will keep it as 0.
7882  */
7883  *indexCorrelation = 0;
7884 
7885  foreach(l, path->indexclauses)
7886  {
7887  IndexClause *iclause = lfirst_node(IndexClause, l);
7888  AttrNumber attnum = index->indexkeys[iclause->indexcol];
7889 
7890  /* attempt to lookup stats in relation for this index column */
7891  if (attnum != 0)
7892  {
7893  /* Simple variable -- look to stats for the underlying table */
7895  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7896  {
7897  /*
7898  * The hook took control of acquiring a stats tuple. If it
7899  * did supply a tuple, it'd better have supplied a freefunc.
7900  */
7901  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7902  elog(ERROR,
7903  "no function provided to release variable stats with");
7904  }
7905  else
7906  {
7907  vardata.statsTuple =
7909  ObjectIdGetDatum(rte->relid),
7911  BoolGetDatum(false));
7912  vardata.freefunc = ReleaseSysCache;
7913  }
7914  }
7915  else
7916  {
7917  /*
7918  * Looks like we've found an expression column in the index. Let's
7919  * see if there's any stats for it.
7920  */
7921 
7922  /* get the attnum from the 0-based index. */
7923  attnum = iclause->indexcol + 1;
7924 
7925  if (get_index_stats_hook &&
7926  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7927  {
7928  /*
7929  * The hook took control of acquiring a stats tuple. If it
7930  * did supply a tuple, it'd better have supplied a freefunc.
7931  */
7932  if (HeapTupleIsValid(vardata.statsTuple) &&
7933  !vardata.freefunc)
7934  elog(ERROR, "no function provided to release variable stats with");
7935  }
7936  else
7937  {
7939  ObjectIdGetDatum(index->indexoid),
7941  BoolGetDatum(false));
7942  vardata.freefunc = ReleaseSysCache;
7943  }
7944  }
7945 
7946  if (HeapTupleIsValid(vardata.statsTuple))
7947  {
7948  AttStatsSlot sslot;
7949 
7950  if (get_attstatsslot(&sslot, vardata.statsTuple,
7951  STATISTIC_KIND_CORRELATION, InvalidOid,
7953  {
7954  double varCorrelation = 0.0;
7955 
7956  if (sslot.nnumbers > 0)
7957  varCorrelation = fabs(sslot.numbers[0]);
7958 
7959  if (varCorrelation > *indexCorrelation)
7960  *indexCorrelation = varCorrelation;
7961 
7962  free_attstatsslot(&sslot);
7963  }
7964  }
7965 
7966  ReleaseVariableStats(vardata);
7967  }
7968 
7969  qualSelectivity = clauselist_selectivity(root, indexQuals,
7970  baserel->relid,
7971  JOIN_INNER, NULL);
7972 
7973  /*
7974  * Now calculate the minimum possible ranges we could match with if all of
7975  * the rows were in the perfect order in the table's heap.
7976  */
7977  minimalRanges = ceil(indexRanges * qualSelectivity);
7978 
7979  /*
7980  * Now estimate the number of ranges that we'll touch by using the
7981  * indexCorrelation from the stats. Careful not to divide by zero (note
7982  * we're using the absolute value of the correlation).
7983  */
7984  if (*indexCorrelation < 1.0e-10)
7985  estimatedRanges = indexRanges;
7986  else
7987  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
7988 
7989  /* we expect to visit this portion of the table */
7990  selec = estimatedRanges / indexRanges;
7991 
7992  CLAMP_PROBABILITY(selec);
7993 
7994  *indexSelectivity = selec;
7995 
7996  /*
7997  * Compute the index qual costs, much as in genericcostestimate, to add to
7998  * the index costs. We can disregard indexorderbys, since BRIN doesn't
7999  * support those.
8000  */
8001  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
8002 
8003  /*
8004  * Compute the startup cost as the cost to read the whole revmap
8005  * sequentially, including the cost to execute the index quals.
8006  */
8007  *indexStartupCost =
8008  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8009  *indexStartupCost += qual_arg_cost;
8010 
8011  /*
8012  * To read a BRIN index there might be a bit of back and forth over
8013  * regular pages, as revmap might point to them out of sequential order;
8014  * calculate the total cost as reading the whole index in random order.
8015  */
8016  *indexTotalCost = *indexStartupCost +
8017  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8018 
8019  /*
8020  * Charge a small amount per range tuple which we expect to match to. This
8021  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8022  * will set a bit for each page in the range when we find a matching
8023  * range, so we must multiply the charge by the number of pages in the
8024  * range.
8025  */
8026  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8027  statsData.pagesPerRange;
8028 
8029  *indexPages = index->pages;
8030 }
int16 AttrNumber
Definition: attnum.h:21
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1262
#define BRIN_DEFAULT_PAGES_PER_RANGE
Definition: brin.h:38
#define REVMAP_PAGE_MAXITEMS
Definition: brin_page.h:93
#define Min(x, y)
Definition: c.h:988
#define Max(x, y)
Definition: c.h:982
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:102
double cpu_operator_cost
Definition: costsize.c:124
#define ERROR
Definition: elog.h:39
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:158
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:132
Assert(fmt[strlen(fmt) - 1] !='\n')
#define NoLock
Definition: lockdefs.h:34
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3302
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3192
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
double Cost
Definition: nodes.h:262
@ JOIN_INNER
Definition: nodes.h:304
@ RTE_RELATION
Definition: parsenodes.h:1014
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:561
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
List * get_quals_from_indexclauses(List *indexclauses)
Definition: selfuncs.c:6347
get_index_stats_hook_type get_index_stats_hook
Definition: selfuncs.c:147
Cost index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
Definition: selfuncs.c:6377
get_relation_stats_hook_type get_relation_stats_hook
Definition: selfuncs.c:146
#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:34
BlockNumber pagesPerRange
Definition: brin.h:33
AttrNumber indexcol
Definition: pathnodes.h:1735
List * indexclauses
Definition: pathnodes.h:1685
IndexOptInfo * indexinfo
Definition: pathnodes.h:1684
Definition: pg_list.h:54
RTEKind rtekind
Definition: parsenodes.h:1033
Index relid
Definition: pathnodes.h:909
BlockNumber pages
Definition: pathnodes.h:933
HeapTuple statsTuple
Definition: selfuncs.h:89
void(* freefunc)(HeapTuple tuple)
Definition: selfuncs.h:91
Definition: type.h:95
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:866
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:840
@ STATRELATTINH
Definition: syscache.h:97

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

Referenced by brinhandler().

◆ btcostestimate()

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

Definition at line 6670 of file selfuncs.c.

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

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, 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, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, and VariableStatData::statsTuple.

Referenced by bthandler().

◆ gincostestimate()

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

Definition at line 7425 of file selfuncs.c.

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

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

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

Referenced by gisthandler().

◆ hashcostestimate()

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

Definition at line 6973 of file selfuncs.c.

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

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

Referenced by hashhandler().

◆ spgcostestimate()

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

Definition at line 7070 of file selfuncs.c.

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

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

Referenced by spghandler().