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

{
    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 = fabs(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;
}

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

{
    IndexOptInfo *index = path->indexinfo;
    GenericCosts costs = {0};
    Oid         relid;
    AttrNumber  colnum;
    VariableStatData vardata = {0};
    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 up
     * to N index descents (not just 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);
                double      alength = estimate_array_length(root, other_operand);
 
                clause_op = saop->opno;
                found_saop = true;
                /* estimate SA descents 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;
 
        /*
         * btree automatically combines individual ScalarArrayOpExpr primitive
         * index scans whenever the tuples covered by the next set of array
         * keys are close to tuples covered by the current set.  That puts a
         * natural ceiling on the worst case number of descents -- there
         * cannot possibly be more than one descent per leaf page scanned.
         *
         * Clamp the number of descents to at most 1/3 the number of index
         * pages.  This avoids implausibly high estimates with low selectivity
         * paths, where scans usually require only one or two descents.  This
         * is most likely to help when there are several SAOP clauses, where
         * naively accepting the total number of distinct combinations of
         * array elements as the number of descents would frequently lead to
         * wild overestimates.
         *
         * We somewhat arbitrarily don't just make the cutoff the total number
         * of leaf pages (we make it 1/3 the total number of pages instead) to
         * give the btree code credit for its ability to continue on the leaf
         * level with low selectivity scans.
         */
        num_sa_scans = Min(num_sa_scans, ceil(index->pages * 0.3333333));
        num_sa_scans = Max(num_sa_scans, 1);
 
        /*
         * As in genericcostestimate(), we have to adjust for any
         * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
         * to integer.
         *
         * It is tempting to make genericcostestimate behave as if SAOP
         * clauses work in almost the same way as scalar operators during
         * btree scans, making the top-level scan look like a continuous scan
         * (as opposed to num_sa_scans-many primitive index scans).  After
         * all, btree scans mostly work like that at runtime.  However, such a
         * scheme would badly bias genericcostestimate's simplistic approach
         * to calculating numIndexPages through prorating.
         *
         * Stick with the approach taken by non-native SAOP scans for now.
         * genericcostestimate will use the Mackert-Lohman formula to
         * compensate for repeat page fetches, even though that definitely
         * won't happen during btree scans (not for leaf pages, at least).
         * We're usually very pessimistic about the number of primitive index
         * scans that will be required, but it's not clear how to do better.
         */
        numIndexTuples = rint(numIndexTuples / num_sa_scans);
    }
 
    /*
     * Now do generic index cost estimation.
     */
    costs.numIndexTuples = numIndexTuples;
    costs.num_sa_scans = num_sa_scans;
 
    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 estimated SA
     * index descent.  The ones after the first one are not startup cost so
     * far as the overall plan goes, so just add them 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 estimated
     * SA index descent.
     */
    descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * 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.)
     */
    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;
}

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

{
    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;
    Cost        descentCost;
    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);
 
    *indexStartupCost = 0;
    *indexTotalCost = 0;
 
    /*
     * Add a CPU-cost component to represent the costs of initial entry 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 (numEntries > 1)         /* avoid computing log(0) */
    {
        descentCost = ceil(log(numEntries) / log(2.0)) * cpu_operator_cost;
        *indexStartupCost += descentCost * counts.searchEntries;
        *indexTotalCost += counts.arrayScans * descentCost * counts.searchEntries;
    }
 
    /*
     * Add a cpu cost per entry-page fetched. This is not amortized over a
     * loop.
     */
    *indexStartupCost += entryPagesFetched * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
    *indexTotalCost += entryPagesFetched * counts.arrayScans * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
 
    /*
     * Add a cpu cost per data-page fetched. This is also not amortized over a
     * loop. Since those are the data pages from the partial match algorithm,
     * charge them as startup cost.
     */
    *indexStartupCost += DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost * dataPagesFetched;
 
    /*
     * Since we add the startup cost to the total cost later on, remove the
     * initial arrayscan from the total.
     */
    *indexTotalCost += dataPagesFetched * (counts.arrayScans - 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
 
    /*
     * 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;
 
    /* Add one page cpu-cost to the startup cost */
    *indexStartupCost += DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost * counts.searchEntries;
 
    /*
     * Add once again a CPU-cost for those data pages, before amortizing for
     * cache.
     */
    *indexTotalCost += dataPagesFetched * counts.arrayScans * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
 
    /* 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. We charge
     * cpu 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;
 
    /*
     * Add a cpu cost per search entry, corresponding to the actual visited
     * entries.
     */
    *indexTotalCost += (counts.searchEntries * counts.arrayScans) * (qual_op_cost);
    /* Now add a cpu cost per tuple in the posting lists / trees */
    *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost);
    *indexPages = dataPagesFetched;
}

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

{
    IndexOptInfo *index = path->indexinfo;
    GenericCosts costs = {0};
    Cost        descentCost;
 
    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) * DEFAULT_PAGE_CPU_MULTIPLIER * 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;
}

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

{
    GenericCosts costs = {0};
 
    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;
}

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

{
    IndexOptInfo *index = path->indexinfo;
    GenericCosts costs = {0};
    Cost        descentCost;
 
    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) * DEFAULT_PAGE_CPU_MULTIPLIER * 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;
}

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