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

Go to the source code of this file.

Functions

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

Function Documentation

◆ brincostestimate()

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

Definition at line 8007 of file selfuncs.c.

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

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

Referenced by brinhandler().

◆ btcostestimate()

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

Definition at line 6822 of file selfuncs.c.

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

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

Referenced by bthandler().

◆ gincostestimate()

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

Definition at line 7617 of file selfuncs.c.

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

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

Referenced by ginhandler().

◆ gistcostestimate()

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

Definition at line 7207 of file selfuncs.c.

7211{
7212 IndexOptInfo *index = path->indexinfo;
7213 GenericCosts costs = {0};
7214 Cost descentCost;
7215
7216 genericcostestimate(root, path, loop_count, &costs);
7217
7218 /*
7219 * We model index descent costs similarly to those for btree, but to do
7220 * that we first need an idea of the tree height. We somewhat arbitrarily
7221 * assume that the fanout is 100, meaning the tree height is at most
7222 * log100(index->pages).
7223 *
7224 * Although this computation isn't really expensive enough to require
7225 * caching, we might as well use index->tree_height to cache it.
7226 */
7227 if (index->tree_height < 0) /* unknown? */
7228 {
7229 if (index->pages > 1) /* avoid computing log(0) */
7230 index->tree_height = (int) (log(index->pages) / log(100.0));
7231 else
7232 index->tree_height = 0;
7233 }
7234
7235 /*
7236 * Add a CPU-cost component to represent the costs of initial descent. We
7237 * just use log(N) here not log2(N) since the branching factor isn't
7238 * necessarily two anyway. As for btree, charge once per SA scan.
7239 */
7240 if (index->tuples > 1) /* avoid computing log(0) */
7241 {
7242 descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7243 costs.indexStartupCost += descentCost;
7244 costs.indexTotalCost += costs.num_sa_scans * descentCost;
7245 }
7246
7247 /*
7248 * Likewise add a per-page charge, calculated the same as for btrees.
7249 */
7250 descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7251 costs.indexStartupCost += descentCost;
7252 costs.indexTotalCost += costs.num_sa_scans * descentCost;
7253
7254 *indexStartupCost = costs.indexStartupCost;
7255 *indexTotalCost = costs.indexTotalCost;
7256 *indexSelectivity = costs.indexSelectivity;
7257 *indexCorrelation = costs.indexCorrelation;
7258 *indexPages = costs.numIndexPages;
7259}

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

Referenced by gisthandler().

◆ hashcostestimate()

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

Definition at line 7165 of file selfuncs.c.

7169{
7170 GenericCosts costs = {0};
7171
7172 genericcostestimate(root, path, loop_count, &costs);
7173
7174 /*
7175 * A hash index has no descent costs as such, since the index AM can go
7176 * directly to the target bucket after computing the hash value. There
7177 * are a couple of other hash-specific costs that we could conceivably add
7178 * here, though:
7179 *
7180 * Ideally we'd charge spc_random_page_cost for each page in the target
7181 * bucket, not just the numIndexPages pages that genericcostestimate
7182 * thought we'd visit. However in most cases we don't know which bucket
7183 * that will be. There's no point in considering the average bucket size
7184 * because the hash AM makes sure that's always one page.
7185 *
7186 * Likewise, we could consider charging some CPU for each index tuple in
7187 * the bucket, if we knew how many there were. But the per-tuple cost is
7188 * just a hash value comparison, not a general datatype-dependent
7189 * comparison, so any such charge ought to be quite a bit less than
7190 * cpu_operator_cost; which makes it probably not worth worrying about.
7191 *
7192 * A bigger issue is that chance hash-value collisions will result in
7193 * wasted probes into the heap. We don't currently attempt to model this
7194 * cost on the grounds that it's rare, but maybe it's not rare enough.
7195 * (Any fix for this ought to consider the generic lossy-operator problem,
7196 * though; it's not entirely hash-specific.)
7197 */
7198
7199 *indexStartupCost = costs.indexStartupCost;
7200 *indexTotalCost = costs.indexTotalCost;
7201 *indexSelectivity = costs.indexSelectivity;
7202 *indexCorrelation = costs.indexCorrelation;
7203 *indexPages = costs.numIndexPages;
7204}

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

Referenced by hashhandler().

◆ spgcostestimate()

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

Definition at line 7262 of file selfuncs.c.

7266{
7267 IndexOptInfo *index = path->indexinfo;
7268 GenericCosts costs = {0};
7269 Cost descentCost;
7270
7271 genericcostestimate(root, path, loop_count, &costs);
7272
7273 /*
7274 * We model index descent costs similarly to those for btree, but to do
7275 * that we first need an idea of the tree height. We somewhat arbitrarily
7276 * assume that the fanout is 100, meaning the tree height is at most
7277 * log100(index->pages).
7278 *
7279 * Although this computation isn't really expensive enough to require
7280 * caching, we might as well use index->tree_height to cache it.
7281 */
7282 if (index->tree_height < 0) /* unknown? */
7283 {
7284 if (index->pages > 1) /* avoid computing log(0) */
7285 index->tree_height = (int) (log(index->pages) / log(100.0));
7286 else
7287 index->tree_height = 0;
7288 }
7289
7290 /*
7291 * Add a CPU-cost component to represent the costs of initial descent. We
7292 * just use log(N) here not log2(N) since the branching factor isn't
7293 * necessarily two anyway. As for btree, charge once per SA scan.
7294 */
7295 if (index->tuples > 1) /* avoid computing log(0) */
7296 {
7297 descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
7298 costs.indexStartupCost += descentCost;
7299 costs.indexTotalCost += costs.num_sa_scans * descentCost;
7300 }
7301
7302 /*
7303 * Likewise add a per-page charge, calculated the same as for btrees.
7304 */
7305 descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
7306 costs.indexStartupCost += descentCost;
7307 costs.indexTotalCost += costs.num_sa_scans * descentCost;
7308
7309 *indexStartupCost = costs.indexStartupCost;
7310 *indexTotalCost = costs.indexTotalCost;
7311 *indexSelectivity = costs.indexSelectivity;
7312 *indexCorrelation = costs.indexCorrelation;
7313 *indexPages = costs.numIndexPages;
7314}

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

Referenced by spghandler().