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 7885 of file selfuncs.c.

7889 {
7890  IndexOptInfo *index = path->indexinfo;
7891  List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
7892  double numPages = index->pages;
7893  RelOptInfo *baserel = index->rel;
7894  RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
7895  Cost spc_seq_page_cost;
7896  Cost spc_random_page_cost;
7897  double qual_arg_cost;
7898  double qualSelectivity;
7899  BrinStatsData statsData;
7900  double indexRanges;
7901  double minimalRanges;
7902  double estimatedRanges;
7903  double selec;
7904  Relation indexRel;
7905  ListCell *l;
7906  VariableStatData vardata;
7907 
7908  Assert(rte->rtekind == RTE_RELATION);
7909 
7910  /* fetch estimated page cost for the tablespace containing the index */
7911  get_tablespace_page_costs(index->reltablespace,
7912  &spc_random_page_cost,
7913  &spc_seq_page_cost);
7914 
7915  /*
7916  * Obtain some data from the index itself, if possible. Otherwise invent
7917  * some plausible internal statistics based on the relation page count.
7918  */
7919  if (!index->hypothetical)
7920  {
7921  /*
7922  * A lock should have already been obtained on the index in plancat.c.
7923  */
7924  indexRel = index_open(index->indexoid, NoLock);
7925  brinGetStats(indexRel, &statsData);
7926  index_close(indexRel, NoLock);
7927 
7928  /* work out the actual number of ranges in the index */
7929  indexRanges = Max(ceil((double) baserel->pages /
7930  statsData.pagesPerRange), 1.0);
7931  }
7932  else
7933  {
7934  /*
7935  * Assume default number of pages per range, and estimate the number
7936  * of ranges based on that.
7937  */
7938  indexRanges = Max(ceil((double) baserel->pages /
7940 
7942  statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
7943  }
7944 
7945  /*
7946  * Compute index correlation
7947  *
7948  * Because we can use all index quals equally when scanning, we can use
7949  * the largest correlation (in absolute value) among columns used by the
7950  * query. Start at zero, the worst possible case. If we cannot find any
7951  * correlation statistics, we will keep it as 0.
7952  */
7953  *indexCorrelation = 0;
7954 
7955  foreach(l, path->indexclauses)
7956  {
7957  IndexClause *iclause = lfirst_node(IndexClause, l);
7958  AttrNumber attnum = index->indexkeys[iclause->indexcol];
7959 
7960  /* attempt to lookup stats in relation for this index column */
7961  if (attnum != 0)
7962  {
7963  /* Simple variable -- look to stats for the underlying table */
7965  (*get_relation_stats_hook) (root, rte, attnum, &vardata))
7966  {
7967  /*
7968  * The hook took control of acquiring a stats tuple. If it
7969  * did supply a tuple, it'd better have supplied a freefunc.
7970  */
7971  if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
7972  elog(ERROR,
7973  "no function provided to release variable stats with");
7974  }
7975  else
7976  {
7977  vardata.statsTuple =
7979  ObjectIdGetDatum(rte->relid),
7981  BoolGetDatum(false));
7982  vardata.freefunc = ReleaseSysCache;
7983  }
7984  }
7985  else
7986  {
7987  /*
7988  * Looks like we've found an expression column in the index. Let's
7989  * see if there's any stats for it.
7990  */
7991 
7992  /* get the attnum from the 0-based index. */
7993  attnum = iclause->indexcol + 1;
7994 
7995  if (get_index_stats_hook &&
7996  (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
7997  {
7998  /*
7999  * The hook took control of acquiring a stats tuple. If it
8000  * did supply a tuple, it'd better have supplied a freefunc.
8001  */
8002  if (HeapTupleIsValid(vardata.statsTuple) &&
8003  !vardata.freefunc)
8004  elog(ERROR, "no function provided to release variable stats with");
8005  }
8006  else
8007  {
8009  ObjectIdGetDatum(index->indexoid),
8011  BoolGetDatum(false));
8012  vardata.freefunc = ReleaseSysCache;
8013  }
8014  }
8015 
8016  if (HeapTupleIsValid(vardata.statsTuple))
8017  {
8018  AttStatsSlot sslot;
8019 
8020  if (get_attstatsslot(&sslot, vardata.statsTuple,
8021  STATISTIC_KIND_CORRELATION, InvalidOid,
8023  {
8024  double varCorrelation = 0.0;
8025 
8026  if (sslot.nnumbers > 0)
8027  varCorrelation = fabs(sslot.numbers[0]);
8028 
8029  if (varCorrelation > *indexCorrelation)
8030  *indexCorrelation = varCorrelation;
8031 
8032  free_attstatsslot(&sslot);
8033  }
8034  }
8035 
8036  ReleaseVariableStats(vardata);
8037  }
8038 
8039  qualSelectivity = clauselist_selectivity(root, indexQuals,
8040  baserel->relid,
8041  JOIN_INNER, NULL);
8042 
8043  /*
8044  * Now calculate the minimum possible ranges we could match with if all of
8045  * the rows were in the perfect order in the table's heap.
8046  */
8047  minimalRanges = ceil(indexRanges * qualSelectivity);
8048 
8049  /*
8050  * Now estimate the number of ranges that we'll touch by using the
8051  * indexCorrelation from the stats. Careful not to divide by zero (note
8052  * we're using the absolute value of the correlation).
8053  */
8054  if (*indexCorrelation < 1.0e-10)
8055  estimatedRanges = indexRanges;
8056  else
8057  estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
8058 
8059  /* we expect to visit this portion of the table */
8060  selec = estimatedRanges / indexRanges;
8061 
8062  CLAMP_PROBABILITY(selec);
8063 
8064  *indexSelectivity = selec;
8065 
8066  /*
8067  * Compute the index qual costs, much as in genericcostestimate, to add to
8068  * the index costs. We can disregard indexorderbys, since BRIN doesn't
8069  * support those.
8070  */
8071  qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
8072 
8073  /*
8074  * Compute the startup cost as the cost to read the whole revmap
8075  * sequentially, including the cost to execute the index quals.
8076  */
8077  *indexStartupCost =
8078  spc_seq_page_cost * statsData.revmapNumPages * loop_count;
8079  *indexStartupCost += qual_arg_cost;
8080 
8081  /*
8082  * To read a BRIN index there might be a bit of back and forth over
8083  * regular pages, as revmap might point to them out of sequential order;
8084  * calculate the total cost as reading the whole index in random order.
8085  */
8086  *indexTotalCost = *indexStartupCost +
8087  spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
8088 
8089  /*
8090  * Charge a small amount per range tuple which we expect to match to. This
8091  * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
8092  * will set a bit for each page in the range when we find a matching
8093  * range, so we must multiply the charge by the number of pages in the
8094  * range.
8095  */
8096  *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
8097  statsData.pagesPerRange;
8098 
8099  *indexPages = index->pages;
8100 }
int16 AttrNumber
Definition: attnum.h:21
void brinGetStats(Relation index, BrinStatsData *stats)
Definition: brin.c:1339
#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:993
#define Max(x, y)
Definition: c.h:987
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:3326
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3216
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
double Cost
Definition: nodes.h:262
@ JOIN_INNER
Definition: nodes.h:304
@ RTE_RELATION
Definition: parsenodes.h:1006
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:555
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:6417
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:6447
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:1729
List * indexclauses
Definition: pathnodes.h:1679
IndexOptInfo * indexinfo
Definition: pathnodes.h:1678
Definition: pg_list.h:54
RTEKind rtekind
Definition: parsenodes.h:1025
Index relid
Definition: pathnodes.h:903
BlockNumber pages
Definition: pathnodes.h:927
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:868
HeapTuple SearchSysCache3(int cacheId, Datum key1, Datum key2, Datum key3)
Definition: syscache.c:842
@ 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 6740 of file selfuncs.c.

6744 {
6745  IndexOptInfo *index = path->indexinfo;
6746  GenericCosts costs = {0};
6747  Oid relid;
6748  AttrNumber colnum;
6749  VariableStatData vardata = {0};
6750  double numIndexTuples;
6751  Cost descentCost;
6752  List *indexBoundQuals;
6753  int indexcol;
6754  bool eqQualHere;
6755  bool found_saop;
6756  bool found_is_null_op;
6757  double num_sa_scans;
6758  ListCell *lc;
6759 
6760  /*
6761  * For a btree scan, only leading '=' quals plus inequality quals for the
6762  * immediately next attribute contribute to index selectivity (these are
6763  * the "boundary quals" that determine the starting and stopping points of
6764  * the index scan). Additional quals can suppress visits to the heap, so
6765  * it's OK to count them in indexSelectivity, but they should not count
6766  * for estimating numIndexTuples. So we must examine the given indexquals
6767  * to find out which ones count as boundary quals. We rely on the
6768  * knowledge that they are given in index column order.
6769  *
6770  * For a RowCompareExpr, we consider only the first column, just as
6771  * rowcomparesel() does.
6772  *
6773  * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6774  * index scans not one, but the ScalarArrayOpExpr's operator can be
6775  * considered to act the same as it normally does.
6776  */
6777  indexBoundQuals = NIL;
6778  indexcol = 0;
6779  eqQualHere = false;
6780  found_saop = false;
6781  found_is_null_op = false;
6782  num_sa_scans = 1;
6783  foreach(lc, path->indexclauses)
6784  {
6785  IndexClause *iclause = lfirst_node(IndexClause, lc);
6786  ListCell *lc2;
6787 
6788  if (indexcol != iclause->indexcol)
6789  {
6790  /* Beginning of a new column's quals */
6791  if (!eqQualHere)
6792  break; /* done if no '=' qual for indexcol */
6793  eqQualHere = false;
6794  indexcol++;
6795  if (indexcol != iclause->indexcol)
6796  break; /* no quals at all for indexcol */
6797  }
6798 
6799  /* Examine each indexqual associated with this index clause */
6800  foreach(lc2, iclause->indexquals)
6801  {
6802  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6803  Expr *clause = rinfo->clause;
6804  Oid clause_op = InvalidOid;
6805  int op_strategy;
6806 
6807  if (IsA(clause, OpExpr))
6808  {
6809  OpExpr *op = (OpExpr *) clause;
6810 
6811  clause_op = op->opno;
6812  }
6813  else if (IsA(clause, RowCompareExpr))
6814  {
6815  RowCompareExpr *rc = (RowCompareExpr *) clause;
6816 
6817  clause_op = linitial_oid(rc->opnos);
6818  }
6819  else if (IsA(clause, ScalarArrayOpExpr))
6820  {
6821  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6822  Node *other_operand = (Node *) lsecond(saop->args);
6823  int alength = estimate_array_length(other_operand);
6824 
6825  clause_op = saop->opno;
6826  found_saop = true;
6827  /* count number of SA scans induced by indexBoundQuals only */
6828  if (alength > 1)
6829  num_sa_scans *= alength;
6830  }
6831  else if (IsA(clause, NullTest))
6832  {
6833  NullTest *nt = (NullTest *) clause;
6834 
6835  if (nt->nulltesttype == IS_NULL)
6836  {
6837  found_is_null_op = true;
6838  /* IS NULL is like = for selectivity purposes */
6839  eqQualHere = true;
6840  }
6841  }
6842  else
6843  elog(ERROR, "unsupported indexqual type: %d",
6844  (int) nodeTag(clause));
6845 
6846  /* check for equality operator */
6847  if (OidIsValid(clause_op))
6848  {
6849  op_strategy = get_op_opfamily_strategy(clause_op,
6850  index->opfamily[indexcol]);
6851  Assert(op_strategy != 0); /* not a member of opfamily?? */
6852  if (op_strategy == BTEqualStrategyNumber)
6853  eqQualHere = true;
6854  }
6855 
6856  indexBoundQuals = lappend(indexBoundQuals, rinfo);
6857  }
6858  }
6859 
6860  /*
6861  * If index is unique and we found an '=' clause for each column, we can
6862  * just assume numIndexTuples = 1 and skip the expensive
6863  * clauselist_selectivity calculations. However, a ScalarArrayOp or
6864  * NullTest invalidates that theory, even though it sets eqQualHere.
6865  */
6866  if (index->unique &&
6867  indexcol == index->nkeycolumns - 1 &&
6868  eqQualHere &&
6869  !found_saop &&
6870  !found_is_null_op)
6871  numIndexTuples = 1.0;
6872  else
6873  {
6874  List *selectivityQuals;
6875  Selectivity btreeSelectivity;
6876 
6877  /*
6878  * If the index is partial, AND the index predicate with the
6879  * index-bound quals to produce a more accurate idea of the number of
6880  * rows covered by the bound conditions.
6881  */
6882  selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
6883 
6884  btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6885  index->rel->relid,
6886  JOIN_INNER,
6887  NULL);
6888  numIndexTuples = btreeSelectivity * index->rel->tuples;
6889 
6890  /*
6891  * As in genericcostestimate(), we have to adjust for any
6892  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6893  * to integer.
6894  */
6895  numIndexTuples = rint(numIndexTuples / num_sa_scans);
6896  }
6897 
6898  /*
6899  * Now do generic index cost estimation.
6900  */
6901  costs.numIndexTuples = numIndexTuples;
6902 
6903  genericcostestimate(root, path, loop_count, &costs);
6904 
6905  /*
6906  * Add a CPU-cost component to represent the costs of initial btree
6907  * descent. We don't charge any I/O cost for touching upper btree levels,
6908  * since they tend to stay in cache, but we still have to do about log2(N)
6909  * comparisons to descend a btree of N leaf tuples. We charge one
6910  * cpu_operator_cost per comparison.
6911  *
6912  * If there are ScalarArrayOpExprs, charge this once per SA scan. The
6913  * ones after the first one are not startup cost so far as the overall
6914  * plan is concerned, so add them only to "total" cost.
6915  */
6916  if (index->tuples > 1) /* avoid computing log(0) */
6917  {
6918  descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6919  costs.indexStartupCost += descentCost;
6920  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6921  }
6922 
6923  /*
6924  * Even though we're not charging I/O cost for touching upper btree pages,
6925  * it's still reasonable to charge some CPU cost per page descended
6926  * through. Moreover, if we had no such charge at all, bloated indexes
6927  * would appear to have the same search cost as unbloated ones, at least
6928  * in cases where only a single leaf page is expected to be visited. This
6929  * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6930  * touched. The number of such pages is btree tree height plus one (ie,
6931  * we charge for the leaf page too). As above, charge once per SA scan.
6932  */
6933  descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
6934  costs.indexStartupCost += descentCost;
6935  costs.indexTotalCost += costs.num_sa_scans * descentCost;
6936 
6937  /*
6938  * If we can get an estimate of the first column's ordering correlation C
6939  * from pg_statistic, estimate the index correlation as C for a
6940  * single-column index, or C * 0.75 for multiple columns. (The idea here
6941  * is that multiple columns dilute the importance of the first column's
6942  * ordering, but don't negate it entirely. Before 8.0 we divided the
6943  * correlation by the number of columns, but that seems too strong.)
6944  */
6945  if (index->indexkeys[0] != 0)
6946  {
6947  /* Simple variable --- look to stats for the underlying table */
6948  RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6949 
6950  Assert(rte->rtekind == RTE_RELATION);
6951  relid = rte->relid;
6952  Assert(relid != InvalidOid);
6953  colnum = index->indexkeys[0];
6954 
6956  (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6957  {
6958  /*
6959  * The hook took control of acquiring a stats tuple. If it did
6960  * supply a tuple, it'd better have supplied a freefunc.
6961  */
6962  if (HeapTupleIsValid(vardata.statsTuple) &&
6963  !vardata.freefunc)
6964  elog(ERROR, "no function provided to release variable stats with");
6965  }
6966  else
6967  {
6969  ObjectIdGetDatum(relid),
6970  Int16GetDatum(colnum),
6971  BoolGetDatum(rte->inh));
6972  vardata.freefunc = ReleaseSysCache;
6973  }
6974  }
6975  else
6976  {
6977  /* Expression --- maybe there are stats for the index itself */
6978  relid = index->indexoid;
6979  colnum = 1;
6980 
6981  if (get_index_stats_hook &&
6982  (*get_index_stats_hook) (root, relid, colnum, &vardata))
6983  {
6984  /*
6985  * The hook took control of acquiring a stats tuple. If it did
6986  * supply a tuple, it'd better have supplied a freefunc.
6987  */
6988  if (HeapTupleIsValid(vardata.statsTuple) &&
6989  !vardata.freefunc)
6990  elog(ERROR, "no function provided to release variable stats with");
6991  }
6992  else
6993  {
6995  ObjectIdGetDatum(relid),
6996  Int16GetDatum(colnum),
6997  BoolGetDatum(false));
6998  vardata.freefunc = ReleaseSysCache;
6999  }
7000  }
7001 
7002  if (HeapTupleIsValid(vardata.statsTuple))
7003  {
7004  Oid sortop;
7005  AttStatsSlot sslot;
7006 
7007  sortop = get_opfamily_member(index->opfamily[0],
7008  index->opcintype[0],
7009  index->opcintype[0],
7011  if (OidIsValid(sortop) &&
7012  get_attstatsslot(&sslot, vardata.statsTuple,
7013  STATISTIC_KIND_CORRELATION, sortop,
7015  {
7016  double varCorrelation;
7017 
7018  Assert(sslot.nnumbers == 1);
7019  varCorrelation = sslot.numbers[0];
7020 
7021  if (index->reverse_sort[0])
7022  varCorrelation = -varCorrelation;
7023 
7024  if (index->nkeycolumns > 1)
7025  costs.indexCorrelation = varCorrelation * 0.75;
7026  else
7027  costs.indexCorrelation = varCorrelation;
7028 
7029  free_attstatsslot(&sslot);
7030  }
7031  }
7032 
7033  ReleaseVariableStats(vardata);
7034 
7035  *indexStartupCost = costs.indexStartupCost;
7036  *indexTotalCost = costs.indexTotalCost;
7037  *indexSelectivity = costs.indexSelectivity;
7038  *indexCorrelation = costs.indexCorrelation;
7039  *indexPages = costs.numIndexPages;
7040 }
#define OidIsValid(objectId)
Definition: c.h:764
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:1694
#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:6501
List * add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
Definition: selfuncs.c:6719
#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:1727
Definition: nodes.h:129
NullTestType nulltesttype
Definition: primnodes.h:1701
Oid opno
Definition: primnodes.h:753
Expr * clause
Definition: pathnodes.h:2529

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 7495 of file selfuncs.c.

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

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

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 7043 of file selfuncs.c.

7047 {
7048  GenericCosts costs = {0};
7049 
7050  genericcostestimate(root, path, loop_count, &costs);
7051 
7052  /*
7053  * A hash index has no descent costs as such, since the index AM can go
7054  * directly to the target bucket after computing the hash value. There
7055  * are a couple of other hash-specific costs that we could conceivably add
7056  * here, though:
7057  *
7058  * Ideally we'd charge spc_random_page_cost for each page in the target
7059  * bucket, not just the numIndexPages pages that genericcostestimate
7060  * thought we'd visit. However in most cases we don't know which bucket
7061  * that will be. There's no point in considering the average bucket size
7062  * because the hash AM makes sure that's always one page.
7063  *
7064  * Likewise, we could consider charging some CPU for each index tuple in
7065  * the bucket, if we knew how many there were. But the per-tuple cost is
7066  * just a hash value comparison, not a general datatype-dependent
7067  * comparison, so any such charge ought to be quite a bit less than
7068  * cpu_operator_cost; which makes it probably not worth worrying about.
7069  *
7070  * A bigger issue is that chance hash-value collisions will result in
7071  * wasted probes into the heap. We don't currently attempt to model this
7072  * cost on the grounds that it's rare, but maybe it's not rare enough.
7073  * (Any fix for this ought to consider the generic lossy-operator problem,
7074  * though; it's not entirely hash-specific.)
7075  */
7076 
7077  *indexStartupCost = costs.indexStartupCost;
7078  *indexTotalCost = costs.indexTotalCost;
7079  *indexSelectivity = costs.indexSelectivity;
7080  *indexCorrelation = costs.indexCorrelation;
7081  *indexPages = costs.numIndexPages;
7082 }

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 7140 of file selfuncs.c.

7144 {
7145  IndexOptInfo *index = path->indexinfo;
7146  GenericCosts costs = {0};
7147  Cost descentCost;
7148 
7149  genericcostestimate(root, path, loop_count, &costs);
7150 
7151  /*
7152  * We model index descent costs similarly to those for btree, but to do
7153  * that we first need an idea of the tree height. We somewhat arbitrarily
7154  * assume that the fanout is 100, meaning the tree height is at most
7155  * log100(index->pages).
7156  *
7157  * Although this computation isn't really expensive enough to require
7158  * caching, we might as well use index->tree_height to cache it.
7159  */
7160  if (index->tree_height < 0) /* unknown? */
7161  {
7162  if (index->pages > 1) /* avoid computing log(0) */
7163  index->tree_height = (int) (log(index->pages) / log(100.0));
7164  else
7165  index->tree_height = 0;
7166  }
7167 
7168  /*
7169  * Add a CPU-cost component to represent the costs of initial descent. We
7170  * just use log(N) here not log2(N) since the branching factor isn't
7171  * necessarily two anyway. As for btree, charge once per SA scan.
7172  */
7173  if (index->tuples > 1) /* avoid computing log(0) */
7174  {
7175  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7176  costs.indexStartupCost += descentCost;
7177  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7178  }
7179 
7180  /*
7181  * Likewise add a per-page charge, calculated the same as for btrees.
7182  */
7183  descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7184  costs.indexStartupCost += descentCost;
7185  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7186 
7187  *indexStartupCost = costs.indexStartupCost;
7188  *indexTotalCost = costs.indexTotalCost;
7189  *indexSelectivity = costs.indexSelectivity;
7190  *indexCorrelation = costs.indexCorrelation;
7191  *indexPages = costs.numIndexPages;
7192 }

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