#include "access/amapi.h"

Include dependency graph for index_selfuncs.h:

This graph shows which files directly or indirectly include 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 6977 of file selfuncs.c.

References Abs, 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, IndexOptInfo::hypothetical, index_close(), index_open(), index_other_operands_eval_cost(), IndexPath::indexclauses, IndexClause::indexcol, IndexPath::indexinfo, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, Int16GetDatum, InvalidOid, JOIN_INNER, lfirst_node, Max, Min, AttStatsSlot::nnumbers, NoLock, AttStatsSlot::numbers, ObjectIdGetDatum, RelOptInfo::pages, IndexOptInfo::pages, BrinStatsData::pagesPerRange, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reltablespace, REVMAP_PAGE_MAXITEMS, BrinStatsData::revmapNumPages, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, and VariableStatData::statsTuple.

Referenced by brinhandler().

 {
     IndexOptInfo *index = path->indexinfo;
     List       *indexQuals = get_quals_from_indexclauses(path->indexclauses);
     double      numPages = index->pages;
     RelOptInfo *baserel = index->rel;
     RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
     Cost        spc_seq_page_cost;
     Cost        spc_random_page_cost;
     double      qual_arg_cost;
     double      qualSelectivity;
     BrinStatsData statsData;
     double      indexRanges;
     double      minimalRanges;
     double      estimatedRanges;
     double      selec;
     Relation    indexRel;
     ListCell   *l;
     VariableStatData vardata;
 
     Assert(rte->rtekind == RTE_RELATION);
 
     /* fetch estimated page cost for the tablespace containing the index */
     get_tablespace_page_costs(index->reltablespace,
                               &spc_random_page_cost,
                               &spc_seq_page_cost);
 
     /*
      * Obtain some data from the index itself, if possible.  Otherwise invent
      * some plausible internal statistics based on the relation page count.
      */
     if (!index->hypothetical)
     {
         /*
          * A lock should have already been obtained on the index in plancat.c.
          */
         indexRel = index_open(index->indexoid, NoLock);
         brinGetStats(indexRel, &statsData);
         index_close(indexRel, NoLock);
 
         /* work out the actual number of ranges in the index */
         indexRanges = Max(ceil((double) baserel->pages /
                                statsData.pagesPerRange), 1.0);
     }
     else
     {
         /*
          * Assume default number of pages per range, and estimate the number
          * of ranges based on that.
          */
         indexRanges = Max(ceil((double) baserel->pages /
                                BRIN_DEFAULT_PAGES_PER_RANGE), 1.0);
 
         statsData.pagesPerRange = BRIN_DEFAULT_PAGES_PER_RANGE;
         statsData.revmapNumPages = (indexRanges / REVMAP_PAGE_MAXITEMS) + 1;
     }
 
     /*
      * Compute index correlation
      *
      * Because we can use all index quals equally when scanning, we can use
      * the largest correlation (in absolute value) among columns used by the
      * query.  Start at zero, the worst possible case.  If we cannot find any
      * correlation statistics, we will keep it as 0.
      */
     *indexCorrelation = 0;
 
     foreach(l, path->indexclauses)
     {
         IndexClause *iclause = lfirst_node(IndexClause, l);
         AttrNumber  attnum = index->indexkeys[iclause->indexcol];
 
         /* attempt to lookup stats in relation for this index column */
         if (attnum != 0)
         {
             /* Simple variable -- look to stats for the underlying table */
             if (get_relation_stats_hook &&
                 (*get_relation_stats_hook) (root, rte, attnum, &vardata))
             {
                 /*
                  * The hook took control of acquiring a stats tuple.  If it
                  * did supply a tuple, it'd better have supplied a freefunc.
                  */
                 if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
                     elog(ERROR,
                          "no function provided to release variable stats with");
             }
             else
             {
                 vardata.statsTuple =
                     SearchSysCache3(STATRELATTINH,
                                     ObjectIdGetDatum(rte->relid),
                                     Int16GetDatum(attnum),
                                     BoolGetDatum(false));
                 vardata.freefunc = ReleaseSysCache;
             }
         }
         else
         {
             /*
              * Looks like we've found an expression column in the index. Let's
              * see if there's any stats for it.
              */
 
             /* get the attnum from the 0-based index. */
             attnum = iclause->indexcol + 1;
 
             if (get_index_stats_hook &&
                 (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
             {
                 /*
                  * The hook took control of acquiring a stats tuple.  If it
                  * did supply a tuple, it'd better have supplied a freefunc.
                  */
                 if (HeapTupleIsValid(vardata.statsTuple) &&
                     !vardata.freefunc)
                     elog(ERROR, "no function provided to release variable stats with");
             }
             else
             {
                 vardata.statsTuple = SearchSysCache3(STATRELATTINH,
                                                      ObjectIdGetDatum(index->indexoid),
                                                      Int16GetDatum(attnum),
                                                      BoolGetDatum(false));
                 vardata.freefunc = ReleaseSysCache;
             }
         }
 
         if (HeapTupleIsValid(vardata.statsTuple))
         {
             AttStatsSlot sslot;
 
             if (get_attstatsslot(&sslot, vardata.statsTuple,
                                  STATISTIC_KIND_CORRELATION, InvalidOid,
                                  ATTSTATSSLOT_NUMBERS))
             {
                 double      varCorrelation = 0.0;
 
                 if (sslot.nnumbers > 0)
                     varCorrelation = Abs(sslot.numbers[0]);
 
                 if (varCorrelation > *indexCorrelation)
                     *indexCorrelation = varCorrelation;
 
                 free_attstatsslot(&sslot);
             }
         }
 
         ReleaseVariableStats(vardata);
     }
 
     qualSelectivity = clauselist_selectivity(root, indexQuals,
                                              baserel->relid,
                                              JOIN_INNER, NULL);
 
     /*
      * Now calculate the minimum possible ranges we could match with if all of
      * the rows were in the perfect order in the table's heap.
      */
     minimalRanges = ceil(indexRanges * qualSelectivity);
 
     /*
      * Now estimate the number of ranges that we'll touch by using the
      * indexCorrelation from the stats. Careful not to divide by zero (note
      * we're using the absolute value of the correlation).
      */
     if (*indexCorrelation < 1.0e-10)
         estimatedRanges = indexRanges;
     else
         estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
 
     /* we expect to visit this portion of the table */
     selec = estimatedRanges / indexRanges;
 
     CLAMP_PROBABILITY(selec);
 
     *indexSelectivity = selec;
 
     /*
      * Compute the index qual costs, much as in genericcostestimate, to add to
      * the index costs.  We can disregard indexorderbys, since BRIN doesn't
      * support those.
      */
     qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
 
     /*
      * Compute the startup cost as the cost to read the whole revmap
      * sequentially, including the cost to execute the index quals.
      */
     *indexStartupCost =
         spc_seq_page_cost * statsData.revmapNumPages * loop_count;
     *indexStartupCost += qual_arg_cost;
 
     /*
      * To read a BRIN index there might be a bit of back and forth over
      * regular pages, as revmap might point to them out of sequential order;
      * calculate the total cost as reading the whole index in random order.
      */
     *indexTotalCost = *indexStartupCost +
         spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
 
     /*
      * Charge a small amount per range tuple which we expect to match to. This
      * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
      * will set a bit for each page in the range when we find a matching
      * range, so we must multiply the charge by the number of pages in the
      * range.
      */
     *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
         statsData.pagesPerRange;
 
     *indexPages = index->pages;
 }

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

References add_predicate_to_index_quals(), ScalarArrayOpExpr::args, Assert, ATTSTATSSLOT_NUMBERS, BoolGetDatum, BTEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, clauselist_selectivity(), cpu_operator_cost, 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, IndexOptInfo::indexkeys, IndexOptInfo::indexoid, IndexClause::indexquals, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, RangeTblEntry::inh, Int16GetDatum, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst_node, linitial_oid, lsecond, MemSet, NIL, IndexOptInfo::nkeycolumns, AttStatsSlot::nnumbers, nodeTag, NullTest::nulltesttype, GenericCosts::num_sa_scans, AttStatsSlot::numbers, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, ObjectIdGetDatum, OidIsValid, IndexOptInfo::opcintype, IndexOptInfo::opfamily, OpExpr::opno, ScalarArrayOpExpr::opno, RowCompareExpr::opnos, planner_rt_fetch, IndexOptInfo::rel, ReleaseSysCache(), ReleaseVariableStats, RelOptInfo::relid, RangeTblEntry::relid, IndexOptInfo::reverse_sort, RTE_RELATION, RangeTblEntry::rtekind, SearchSysCache3(), STATRELATTINH, VariableStatData::statsTuple, IndexOptInfo::tree_height, RelOptInfo::tuples, IndexOptInfo::tuples, and IndexOptInfo::unique.

Referenced by bthandler().

 {
     IndexOptInfo *index = path->indexinfo;
     GenericCosts costs;
     Oid         relid;
     AttrNumber  colnum;
     VariableStatData vardata;
     double      numIndexTuples;
     Cost        descentCost;
     List       *indexBoundQuals;
     int         indexcol;
     bool        eqQualHere;
     bool        found_saop;
     bool        found_is_null_op;
     double      num_sa_scans;
     ListCell   *lc;
 
     /*
      * For a btree scan, only leading '=' quals plus inequality quals for the
      * immediately next attribute contribute to index selectivity (these are
      * the "boundary quals" that determine the starting and stopping points of
      * the index scan).  Additional quals can suppress visits to the heap, so
      * it's OK to count them in indexSelectivity, but they should not count
      * for estimating numIndexTuples.  So we must examine the given indexquals
      * to find out which ones count as boundary quals.  We rely on the
      * knowledge that they are given in index column order.
      *
      * For a RowCompareExpr, we consider only the first column, just as
      * rowcomparesel() does.
      *
      * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
      * index scans not one, but the ScalarArrayOpExpr's operator can be
      * considered to act the same as it normally does.
      */
     indexBoundQuals = NIL;
     indexcol = 0;
     eqQualHere = false;
     found_saop = false;
     found_is_null_op = false;
     num_sa_scans = 1;
     foreach(lc, path->indexclauses)
     {
         IndexClause *iclause = lfirst_node(IndexClause, lc);
         ListCell   *lc2;
 
         if (indexcol != iclause->indexcol)
         {
             /* Beginning of a new column's quals */
             if (!eqQualHere)
                 break;          /* done if no '=' qual for indexcol */
             eqQualHere = false;
             indexcol++;
             if (indexcol != iclause->indexcol)
                 break;          /* no quals at all for indexcol */
         }
 
         /* Examine each indexqual associated with this index clause */
         foreach(lc2, iclause->indexquals)
         {
             RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
             Expr       *clause = rinfo->clause;
             Oid         clause_op = InvalidOid;
             int         op_strategy;
 
             if (IsA(clause, OpExpr))
             {
                 OpExpr     *op = (OpExpr *) clause;
 
                 clause_op = op->opno;
             }
             else if (IsA(clause, RowCompareExpr))
             {
                 RowCompareExpr *rc = (RowCompareExpr *) clause;
 
                 clause_op = linitial_oid(rc->opnos);
             }
             else if (IsA(clause, ScalarArrayOpExpr))
             {
                 ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
                 Node       *other_operand = (Node *) lsecond(saop->args);
                 int         alength = estimate_array_length(other_operand);
 
                 clause_op = saop->opno;
                 found_saop = true;
                 /* count number of SA scans induced by indexBoundQuals only */
                 if (alength > 1)
                     num_sa_scans *= alength;
             }
             else if (IsA(clause, NullTest))
             {
                 NullTest   *nt = (NullTest *) clause;
 
                 if (nt->nulltesttype == IS_NULL)
                 {
                     found_is_null_op = true;
                     /* IS NULL is like = for selectivity purposes */
                     eqQualHere = true;
                 }
             }
             else
                 elog(ERROR, "unsupported indexqual type: %d",
                      (int) nodeTag(clause));
 
             /* check for equality operator */
             if (OidIsValid(clause_op))
             {
                 op_strategy = get_op_opfamily_strategy(clause_op,
                                                        index->opfamily[indexcol]);
                 Assert(op_strategy != 0);   /* not a member of opfamily?? */
                 if (op_strategy == BTEqualStrategyNumber)
                     eqQualHere = true;
             }
 
             indexBoundQuals = lappend(indexBoundQuals, rinfo);
         }
     }
 
     /*
      * If index is unique and we found an '=' clause for each column, we can
      * just assume numIndexTuples = 1 and skip the expensive
      * clauselist_selectivity calculations.  However, a ScalarArrayOp or
      * NullTest invalidates that theory, even though it sets eqQualHere.
      */
     if (index->unique &&
         indexcol == index->nkeycolumns - 1 &&
         eqQualHere &&
         !found_saop &&
         !found_is_null_op)
         numIndexTuples = 1.0;
     else
     {
         List       *selectivityQuals;
         Selectivity btreeSelectivity;
 
         /*
          * If the index is partial, AND the index predicate with the
          * index-bound quals to produce a more accurate idea of the number of
          * rows covered by the bound conditions.
          */
         selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
 
         btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
                                                   index->rel->relid,
                                                   JOIN_INNER,
                                                   NULL);
         numIndexTuples = btreeSelectivity * index->rel->tuples;
 
         /*
          * As in genericcostestimate(), we have to adjust for any
          * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
          * to integer.
          */
         numIndexTuples = rint(numIndexTuples / num_sa_scans);
     }
 
     /*
      * Now do generic index cost estimation.
      */
     MemSet(&costs, 0, sizeof(costs));
     costs.numIndexTuples = numIndexTuples;
 
     genericcostestimate(root, path, loop_count, &costs);
 
     /*
      * Add a CPU-cost component to represent the costs of initial btree
      * descent.  We don't charge any I/O cost for touching upper btree levels,
      * since they tend to stay in cache, but we still have to do about log2(N)
      * comparisons to descend a btree of N leaf tuples.  We charge one
      * cpu_operator_cost per comparison.
      *
      * If there are ScalarArrayOpExprs, charge this once per SA scan.  The
      * ones after the first one are not startup cost so far as the overall
      * plan is concerned, so add them only to "total" cost.
      */
     if (index->tuples > 1)      /* avoid computing log(0) */
     {
         descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
         costs.indexStartupCost += descentCost;
         costs.indexTotalCost += costs.num_sa_scans * descentCost;
     }
 
     /*
      * Even though we're not charging I/O cost for touching upper btree pages,
      * it's still reasonable to charge some CPU cost per page descended
      * through.  Moreover, if we had no such charge at all, bloated indexes
      * would appear to have the same search cost as unbloated ones, at least
      * in cases where only a single leaf page is expected to be visited.  This
      * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
      * touched.  The number of such pages is btree tree height plus one (ie,
      * we charge for the leaf page too).  As above, charge once per SA scan.
      */
     descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
     costs.indexStartupCost += descentCost;
     costs.indexTotalCost += costs.num_sa_scans * descentCost;
 
     /*
      * If we can get an estimate of the first column's ordering correlation C
      * from pg_statistic, estimate the index correlation as C for a
      * single-column index, or C * 0.75 for multiple columns. (The idea here
      * is that multiple columns dilute the importance of the first column's
      * ordering, but don't negate it entirely.  Before 8.0 we divided the
      * correlation by the number of columns, but that seems too strong.)
      */
     MemSet(&vardata, 0, sizeof(vardata));
 
     if (index->indexkeys[0] != 0)
     {
         /* Simple variable --- look to stats for the underlying table */
         RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
 
         Assert(rte->rtekind == RTE_RELATION);
         relid = rte->relid;
         Assert(relid != InvalidOid);
         colnum = index->indexkeys[0];
 
         if (get_relation_stats_hook &&
             (*get_relation_stats_hook) (root, rte, colnum, &vardata))
         {
             /*
              * The hook took control of acquiring a stats tuple.  If it did
              * supply a tuple, it'd better have supplied a freefunc.
              */
             if (HeapTupleIsValid(vardata.statsTuple) &&
                 !vardata.freefunc)
                 elog(ERROR, "no function provided to release variable stats with");
         }
         else
         {
             vardata.statsTuple = SearchSysCache3(STATRELATTINH,
                                                  ObjectIdGetDatum(relid),
                                                  Int16GetDatum(colnum),
                                                  BoolGetDatum(rte->inh));
             vardata.freefunc = ReleaseSysCache;
         }
     }
     else
     {
         /* Expression --- maybe there are stats for the index itself */
         relid = index->indexoid;
         colnum = 1;
 
         if (get_index_stats_hook &&
             (*get_index_stats_hook) (root, relid, colnum, &vardata))
         {
             /*
              * The hook took control of acquiring a stats tuple.  If it did
              * supply a tuple, it'd better have supplied a freefunc.
              */
             if (HeapTupleIsValid(vardata.statsTuple) &&
                 !vardata.freefunc)
                 elog(ERROR, "no function provided to release variable stats with");
         }
         else
         {
             vardata.statsTuple = SearchSysCache3(STATRELATTINH,
                                                  ObjectIdGetDatum(relid),
                                                  Int16GetDatum(colnum),
                                                  BoolGetDatum(false));
             vardata.freefunc = ReleaseSysCache;
         }
     }
 
     if (HeapTupleIsValid(vardata.statsTuple))
     {
         Oid         sortop;
         AttStatsSlot sslot;
 
         sortop = get_opfamily_member(index->opfamily[0],
                                      index->opcintype[0],
                                      index->opcintype[0],
                                      BTLessStrategyNumber);
         if (OidIsValid(sortop) &&
             get_attstatsslot(&sslot, vardata.statsTuple,
                              STATISTIC_KIND_CORRELATION, sortop,
                              ATTSTATSSLOT_NUMBERS))
         {
             double      varCorrelation;
 
             Assert(sslot.nnumbers == 1);
             varCorrelation = sslot.numbers[0];
 
             if (index->reverse_sort[0])
                 varCorrelation = -varCorrelation;
 
             if (index->nkeycolumns > 1)
                 costs.indexCorrelation = varCorrelation * 0.75;
             else
                 costs.indexCorrelation = varCorrelation;
 
             free_attstatsslot(&sslot);
         }
     }
 
     ReleaseVariableStats(vardata);
 
     *indexStartupCost = costs.indexStartupCost;
     *indexTotalCost = costs.indexTotalCost;
     *indexSelectivity = costs.indexSelectivity;
     *indexCorrelation = costs.indexCorrelation;
     *indexPages = costs.numIndexPages;
 }

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

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

Referenced by ginhandler().

 {
     IndexOptInfo *index = path->indexinfo;
     List       *indexQuals = get_quals_from_indexclauses(path->indexclauses);
     List       *selectivityQuals;
     double      numPages = index->pages,
                 numTuples = index->tuples;
     double      numEntryPages,
                 numDataPages,
                 numPendingPages,
                 numEntries;
     GinQualCounts counts;
     bool        matchPossible;
     bool        fullIndexScan;
     double      partialScale;
     double      entryPagesFetched,
                 dataPagesFetched,
                 dataPagesFetchedBySel;
     double      qual_op_cost,
                 qual_arg_cost,
                 spc_random_page_cost,
                 outer_scans;
     Relation    indexRel;
     GinStatsData ginStats;
     ListCell   *lc;
     int         i;
 
     /*
      * Obtain statistical information from the meta page, if possible.  Else
      * set ginStats to zeroes, and we'll cope below.
      */
     if (!index->hypothetical)
     {
         /* Lock should have already been obtained in plancat.c */
         indexRel = index_open(index->indexoid, NoLock);
         ginGetStats(indexRel, &ginStats);
         index_close(indexRel, NoLock);
     }
     else
     {
         memset(&ginStats, 0, sizeof(ginStats));
     }
 
     /*
      * Assuming we got valid (nonzero) stats at all, nPendingPages can be
      * trusted, but the other fields are data as of the last VACUUM.  We can
      * scale them up to account for growth since then, but that method only
      * goes so far; in the worst case, the stats might be for a completely
      * empty index, and scaling them will produce pretty bogus numbers.
      * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
      * it's grown more than that, fall back to estimating things only from the
      * assumed-accurate index size.  But we'll trust nPendingPages in any case
      * so long as it's not clearly insane, ie, more than the index size.
      */
     if (ginStats.nPendingPages < numPages)
         numPendingPages = ginStats.nPendingPages;
     else
         numPendingPages = 0;
 
     if (numPages > 0 && ginStats.nTotalPages <= numPages &&
         ginStats.nTotalPages > numPages / 4 &&
         ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
     {
         /*
          * OK, the stats seem close enough to sane to be trusted.  But we
          * still need to scale them by the ratio numPages / nTotalPages to
          * account for growth since the last VACUUM.
          */
         double      scale = numPages / ginStats.nTotalPages;
 
         numEntryPages = ceil(ginStats.nEntryPages * scale);
         numDataPages = ceil(ginStats.nDataPages * scale);
         numEntries = ceil(ginStats.nEntries * scale);
         /* ensure we didn't round up too much */
         numEntryPages = Min(numEntryPages, numPages - numPendingPages);
         numDataPages = Min(numDataPages,
                            numPages - numPendingPages - numEntryPages);
     }
     else
     {
         /*
          * We might get here because it's a hypothetical index, or an index
          * created pre-9.1 and never vacuumed since upgrading (in which case
          * its stats would read as zeroes), or just because it's grown too
          * much since the last VACUUM for us to put our faith in scaling.
          *
          * Invent some plausible internal statistics based on the index page
          * count (and clamp that to at least 10 pages, just in case).  We
          * estimate that 90% of the index is entry pages, and the rest is data
          * pages.  Estimate 100 entries per entry page; this is rather bogus
          * since it'll depend on the size of the keys, but it's more robust
          * than trying to predict the number of entries per heap tuple.
          */
         numPages = Max(numPages, 10);
         numEntryPages = floor((numPages - numPendingPages) * 0.90);
         numDataPages = numPages - numPendingPages - numEntryPages;
         numEntries = floor(numEntryPages * 100);
     }
 
     /* In an empty index, numEntries could be zero.  Avoid divide-by-zero */
     if (numEntries < 1)
         numEntries = 1;
 
     /*
      * If the index is partial, AND the index predicate with the index-bound
      * quals to produce a more accurate idea of the number of rows covered by
      * the bound conditions.
      */
     selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
 
     /* Estimate the fraction of main-table tuples that will be visited */
     *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
                                                index->rel->relid,
                                                JOIN_INNER,
                                                NULL);
 
     /* fetch estimated page cost for tablespace containing index */
     get_tablespace_page_costs(index->reltablespace,
                               &spc_random_page_cost,
                               NULL);
 
     /*
      * Generic assumption about index correlation: there isn't any.
      */
     *indexCorrelation = 0.0;
 
     /*
      * Examine quals to estimate number of search entries & partial matches
      */
     memset(&counts, 0, sizeof(counts));
     counts.arrayScans = 1;
     matchPossible = true;
 
     foreach(lc, path->indexclauses)
     {
         IndexClause *iclause = lfirst_node(IndexClause, lc);
         ListCell   *lc2;
 
         foreach(lc2, iclause->indexquals)
         {
             RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
             Expr       *clause = rinfo->clause;
 
             if (IsA(clause, OpExpr))
             {
                 matchPossible = gincost_opexpr(root,
                                                index,
                                                iclause->indexcol,
                                                (OpExpr *) clause,
                                                &counts);
                 if (!matchPossible)
                     break;
             }
             else if (IsA(clause, ScalarArrayOpExpr))
             {
                 matchPossible = gincost_scalararrayopexpr(root,
                                                           index,
                                                           iclause->indexcol,
                                                           (ScalarArrayOpExpr *) clause,
                                                           numEntries,
                                                           &counts);
                 if (!matchPossible)
                     break;
             }
             else
             {
                 /* shouldn't be anything else for a GIN index */
                 elog(ERROR, "unsupported GIN indexqual type: %d",
                      (int) nodeTag(clause));
             }
         }
     }
 
     /* Fall out if there were any provably-unsatisfiable quals */
     if (!matchPossible)
     {
         *indexStartupCost = 0;
         *indexTotalCost = 0;
         *indexSelectivity = 0;
         return;
     }
 
     /*
      * If attribute has a full scan and at the same time doesn't have normal
      * scan, then we'll have to scan all non-null entries of that attribute.
      * Currently, we don't have per-attribute statistics for GIN.  Thus, we
      * must assume the whole GIN index has to be scanned in this case.
      */
     fullIndexScan = false;
     for (i = 0; i < index->nkeycolumns; i++)
     {
         if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
         {
             fullIndexScan = true;
             break;
         }
     }
 
     if (fullIndexScan || indexQuals == NIL)
     {
         /*
          * Full index scan will be required.  We treat this as if every key in
          * the index had been listed in the query; is that reasonable?
          */
         counts.partialEntries = 0;
         counts.exactEntries = numEntries;
         counts.searchEntries = numEntries;
     }
 
     /* Will we have more than one iteration of a nestloop scan? */
     outer_scans = loop_count;
 
     /*
      * Compute cost to begin scan, first of all, pay attention to pending
      * list.
      */
     entryPagesFetched = numPendingPages;
 
     /*
      * Estimate number of entry pages read.  We need to do
      * counts.searchEntries searches.  Use a power function as it should be,
      * but tuples on leaf pages usually is much greater. Here we include all
      * searches in entry tree, including search of first entry in partial
      * match algorithm
      */
     entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
 
     /*
      * Add an estimate of entry pages read by partial match algorithm. It's a
      * scan over leaf pages in entry tree.  We haven't any useful stats here,
      * so estimate it as proportion.  Because counts.partialEntries is really
      * pretty bogus (see code above), it's possible that it is more than
      * numEntries; clamp the proportion to ensure sanity.
      */
     partialScale = counts.partialEntries / numEntries;
     partialScale = Min(partialScale, 1.0);
 
     entryPagesFetched += ceil(numEntryPages * partialScale);
 
     /*
      * Partial match algorithm reads all data pages before doing actual scan,
      * so it's a startup cost.  Again, we haven't any useful stats here, so
      * estimate it as proportion.
      */
     dataPagesFetched = ceil(numDataPages * partialScale);
 
     /*
      * Calculate cache effects if more than one scan due to nestloops or array
      * quals.  The result is pro-rated per nestloop scan, but the array qual
      * factor shouldn't be pro-rated (compare genericcostestimate).
      */
     if (outer_scans > 1 || counts.arrayScans > 1)
     {
         entryPagesFetched *= outer_scans * counts.arrayScans;
         entryPagesFetched = index_pages_fetched(entryPagesFetched,
                                                 (BlockNumber) numEntryPages,
                                                 numEntryPages, root);
         entryPagesFetched /= outer_scans;
         dataPagesFetched *= outer_scans * counts.arrayScans;
         dataPagesFetched = index_pages_fetched(dataPagesFetched,
                                                (BlockNumber) numDataPages,
                                                numDataPages, root);
         dataPagesFetched /= outer_scans;
     }
 
     /*
      * Here we use random page cost because logically-close pages could be far
      * apart on disk.
      */
     *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
 
     /*
      * Now compute the number of data pages fetched during the scan.
      *
      * We assume every entry to have the same number of items, and that there
      * is no overlap between them. (XXX: tsvector and array opclasses collect
      * statistics on the frequency of individual keys; it would be nice to use
      * those here.)
      */
     dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
 
     /*
      * If there is a lot of overlap among the entries, in particular if one of
      * the entries is very frequent, the above calculation can grossly
      * under-estimate.  As a simple cross-check, calculate a lower bound based
      * on the overall selectivity of the quals.  At a minimum, we must read
      * one item pointer for each matching entry.
      *
      * The width of each item pointer varies, based on the level of
      * compression.  We don't have statistics on that, but an average of
      * around 3 bytes per item is fairly typical.
      */
     dataPagesFetchedBySel = ceil(*indexSelectivity *
                                  (numTuples / (BLCKSZ / 3)));
     if (dataPagesFetchedBySel > dataPagesFetched)
         dataPagesFetched = dataPagesFetchedBySel;
 
     /* Account for cache effects, the same as above */
     if (outer_scans > 1 || counts.arrayScans > 1)
     {
         dataPagesFetched *= outer_scans * counts.arrayScans;
         dataPagesFetched = index_pages_fetched(dataPagesFetched,
                                                (BlockNumber) numDataPages,
                                                numDataPages, root);
         dataPagesFetched /= outer_scans;
     }
 
     /* And apply random_page_cost as the cost per page */
     *indexTotalCost = *indexStartupCost +
         dataPagesFetched * spc_random_page_cost;
 
     /*
      * Add on index qual eval costs, much as in genericcostestimate.  But we
      * can disregard indexorderbys, since GIN doesn't support those.
      */
     qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
     qual_op_cost = cpu_operator_cost * list_length(indexQuals);
 
     *indexStartupCost += qual_arg_cost;
     *indexTotalCost += qual_arg_cost;
     *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
     *indexPages = dataPagesFetched;
 }

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

References cpu_operator_cost, 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().

 {
     IndexOptInfo *index = path->indexinfo;
     GenericCosts costs;
     Cost        descentCost;
 
     MemSet(&costs, 0, sizeof(costs));
 
     genericcostestimate(root, path, loop_count, &costs);
 
     /*
      * We model index descent costs similarly to those for btree, but to do
      * that we first need an idea of the tree height.  We somewhat arbitrarily
      * assume that the fanout is 100, meaning the tree height is at most
      * log100(index->pages).
      *
      * Although this computation isn't really expensive enough to require
      * caching, we might as well use index->tree_height to cache it.
      */
     if (index->tree_height < 0) /* unknown? */
     {
         if (index->pages > 1)   /* avoid computing log(0) */
             index->tree_height = (int) (log(index->pages) / log(100.0));
         else
             index->tree_height = 0;
     }
 
     /*
      * Add a CPU-cost component to represent the costs of initial descent. We
      * just use log(N) here not log2(N) since the branching factor isn't
      * necessarily two anyway.  As for btree, charge once per SA scan.
      */
     if (index->tuples > 1)      /* avoid computing log(0) */
     {
         descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
         costs.indexStartupCost += descentCost;
         costs.indexTotalCost += costs.num_sa_scans * descentCost;
     }
 
     /*
      * Likewise add a per-page charge, calculated the same as for btrees.
      */
     descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
     costs.indexStartupCost += descentCost;
     costs.indexTotalCost += costs.num_sa_scans * descentCost;
 
     *indexStartupCost = costs.indexStartupCost;
     *indexTotalCost = costs.indexTotalCost;
     *indexSelectivity = costs.indexSelectivity;
     *indexCorrelation = costs.indexCorrelation;
     *indexPages = costs.numIndexPages;
 }

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

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

Referenced by hashhandler().

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

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