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

References Abs, AccessShareLock, Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, brinGetStats(), CLAMP_PROBABILITY, clauselist_selectivity(), cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, free_attstatsslot(), VariableStatData::freefunc, get_attstatsslot(), get_index_stats_hook, get_relation_stats_hook, get_tablespace_page_costs(), HeapTupleIsValid, index_close(), index_open(), IndexQualInfo::indexcol, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, IndexPath::indexquals, Int16GetDatum, InvalidOid, JOIN_INNER, lfirst, Max, Min, AttStatsSlot::nnumbers, AttStatsSlot::numbers, ObjectIdGetDatum, orderby_operands_eval_cost(), other_operands_eval_cost(), RelOptInfo::pages, IndexOptInfo::pages, BrinStatsData::pagesPerRange, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, IndexOptInfo::reltablespace, BrinStatsData::revmapNumPages, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATISTIC_KIND_CORRELATION, STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

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

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

References add_predicate_to_quals(), Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, IndexQualInfo::clause_op, clauselist_selectivity(), cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, estimate_array_length(), free_attstatsslot(), VariableStatData::freefunc, genericcostestimate(), get_attstatsslot(), get_index_stats_hook, get_op_opfamily_strategy(), get_opfamily_member(), get_relation_stats_hook, HeapTupleIsValid, IndexQualInfo::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst, MemSet, IndexOptInfo::ncolumns, NIL, AttStatsSlot::nnumbers, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum, OidIsValid, IndexOptInfo::opcintype, IndexOptInfo::opfamily, IndexQualInfo::other_operand, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reverse_sort, IndexQualInfo::rinfo, rint(), RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATISTIC_KIND_CORRELATION, STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

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

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

References AccessShareLock, GinQualCounts::arrayScans, RestrictInfo::clause, clauselist_selectivity(), cpu_index_tuple_cost, cpu_operator_cost, deconstruct_indexquals(), elog, ERROR, GinQualCounts::exactEntries, get_tablespace_page_costs(), gincost_opexpr(), gincost_scalararrayopexpr(), ginGetStats(), GinQualCounts::haveFullScan, IndexOptInfo::hypothetical, index_close(), index_open(), index_pages_fetched(), IndexPath::indexinfo, IndexOptInfo::indexoid, IndexPath::indexorderbys, IndexPath::indexquals, IndexOptInfo::indpred, IsA, JOIN_INNER, lfirst, list_concat(), list_length(), list_make1, Max, Min, GinStatsData::nDataPages, GinStatsData::nEntries, GinStatsData::nEntryPages, NIL, nodeTag, GinStatsData::nPendingPages, GinStatsData::nTotalPages, orderby_operands_eval_cost(), other_operands_eval_cost(), IndexOptInfo::pages, GinQualCounts::partialEntries, predicate_implied_by(), IndexOptInfo::rel, RelOptInfo::relid, IndexOptInfo::reltablespace, IndexQualInfo::rinfo, rint(), scale, GinQualCounts::searchEntries, and IndexOptInfo::tuples.

Referenced by ginhandler().

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

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

References cpu_operator_cost, deconstruct_indexquals(), genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, IndexOptInfo::pages, IndexOptInfo::tree_height, and IndexOptInfo::tuples.

Referenced by gisthandler().

7160 {
7161  IndexOptInfo *index = path->indexinfo;
7162  List *qinfos;
7163  GenericCosts costs;
7164  Cost descentCost;
7165 
7166  /* Do preliminary analysis of indexquals */
7167  qinfos = deconstruct_indexquals(path);
7168 
7169  MemSet(&costs, 0, sizeof(costs));
7170 
7171  genericcostestimate(root, path, loop_count, qinfos, &costs);
7172 
7173  /*
7174  * We model index descent costs similarly to those for btree, but to do
7175  * that we first need an idea of the tree height. We somewhat arbitrarily
7176  * assume that the fanout is 100, meaning the tree height is at most
7177  * log100(index->pages).
7178  *
7179  * Although this computation isn't really expensive enough to require
7180  * caching, we might as well use index->tree_height to cache it.
7181  */
7182  if (index->tree_height < 0) /* unknown? */
7183  {
7184  if (index->pages > 1) /* avoid computing log(0) */
7185  index->tree_height = (int) (log(index->pages) / log(100.0));
7186  else
7187  index->tree_height = 0;
7188  }
7189 
7190  /*
7191  * Add a CPU-cost component to represent the costs of initial descent. We
7192  * just use log(N) here not log2(N) since the branching factor isn't
7193  * necessarily two anyway. As for btree, charge once per SA scan.
7194  */
7195  if (index->tuples > 1) /* avoid computing log(0) */
7196  {
7197  descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7198  costs.indexStartupCost += descentCost;
7199  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7200  }
7201 
7202  /*
7203  * Likewise add a per-page charge, calculated the same as for btrees.
7204  */
7205  descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
7206  costs.indexStartupCost += descentCost;
7207  costs.indexTotalCost += costs.num_sa_scans * descentCost;
7208 
7209  *indexStartupCost = costs.indexStartupCost;
7210  *indexTotalCost = costs.indexTotalCost;
7211  *indexSelectivity = costs.indexSelectivity;
7212  *indexCorrelation = costs.indexCorrelation;
7213  *indexPages = costs.numIndexPages;
7214 }
Selectivity indexSelectivity
Definition: selfuncs.h:131
IndexOptInfo * indexinfo
Definition: relation.h:1119
#define MemSet(start, val, len)
Definition: c.h:853
double tuples
Definition: relation.h:725
int tree_height
Definition: relation.h:726
List * deconstruct_indexquals(IndexPath *path)
Definition: selfuncs.c:6425
Definition: type.h:89
BlockNumber pages
Definition: relation.h:724
double num_sa_scans
Definition: selfuncs.h:138
double cpu_operator_cost
Definition: costsize.c:108
Cost indexTotalCost
Definition: selfuncs.h:130
double indexCorrelation
Definition: selfuncs.h:132
Cost indexStartupCost
Definition: selfuncs.h:129
Definition: pg_list.h:45
double Cost
Definition: nodes.h:642
void genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, List *qinfos, GenericCosts *costs)
Definition: selfuncs.c:6574
double numIndexPages
Definition: selfuncs.h:135

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

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

Referenced by hashhandler().

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

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

References cpu_operator_cost, deconstruct_indexquals(), genericcostestimate(), GenericCosts::indexCorrelation, IndexPath::indexinfo, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, MemSet, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, IndexOptInfo::pages, IndexOptInfo::tree_height, and IndexOptInfo::tuples.

Referenced by spghandler().

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