#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 8531 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, 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 7226 of file selfuncs.c.

{
    IndexOptInfo *index = path->indexinfo;
    GenericCosts costs = {0};
    VariableStatData vardata = {0};
    double      numIndexTuples;
    Cost        descentCost;
    List       *indexBoundQuals;
    List       *indexSkipQuals;
    int         indexcol;
    bool        eqQualHere;
    bool        found_row_compare;
    bool        found_array;
    bool        found_is_null_op;
    bool        have_correlation = false;
    double      num_sa_scans;
    double      correlation = 0.0;
    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.  Note that nbtree
     * preprocessing can add skip arrays that act as leading '=' quals in the
     * absence of ordinary input '=' quals, so in practice _most_ input quals
     * are able to act as index bound quals (which we take into account here).
     *
     * For a RowCompareExpr, we consider only the first column, just as
     * rowcomparesel() does.
     *
     * If there's a SAOP or skip array in the quals, we'll actually perform up
     * to N index descents (not just one), but the underlying array key's
     * operator can be considered to act the same as it normally does.
     */
    indexBoundQuals = NIL;
    indexSkipQuals = NIL;
    indexcol = 0;
    eqQualHere = false;
    found_row_compare = false;
    found_array = 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)
        {
            double      num_sa_scans_prev_cols = num_sa_scans;
 
            /*
             * Beginning of a new column's quals.
             *
             * Skip scans use skip arrays, which are ScalarArrayOp style
             * arrays that generate their elements procedurally and on demand.
             * Given a multi-column index on "(a, b)", and an SQL WHERE clause
             * "WHERE b = 42", a skip scan will effectively use an indexqual
             * "WHERE a = ANY('{every col a value}') AND b = 42".  (Obviously,
             * the array on "a" must also return "IS NULL" matches, since our
             * WHERE clause used no strict operator on "a").
             *
             * Here we consider how nbtree will backfill skip arrays for any
             * index columns that lacked an '=' qual.  This maintains our
             * num_sa_scans estimate, and determines if this new column (the
             * "iclause->indexcol" column, not the prior "indexcol" column)
             * can have its RestrictInfos/quals added to indexBoundQuals.
             *
             * We'll need to handle columns that have inequality quals, where
             * the skip array generates values from a range constrained by the
             * quals (not every possible value).  We've been maintaining
             * indexSkipQuals to help with this; it will now contain all of
             * the prior column's quals (that is, indexcol's quals) when they
             * might be used for this.
             */
            if (found_row_compare)
            {
                /*
                 * Skip arrays can't be added after a RowCompare input qual
                 * due to limitations in nbtree
                 */
                break;
            }
            if (eqQualHere)
            {
                /*
                 * Don't need to add a skip array for an indexcol that already
                 * has an '=' qual/equality constraint
                 */
                indexcol++;
                indexSkipQuals = NIL;
            }
            eqQualHere = false;
 
            while (indexcol < iclause->indexcol)
            {
                double      ndistinct;
                bool        isdefault = true;
 
                found_array = true;
 
                /*
                 * A skipped attribute's ndistinct forms the basis of our
                 * estimate of the total number of "array elements" used by
                 * its skip array at runtime.  Look that up first.
                 */
                examine_indexcol_variable(root, index, indexcol, &vardata);
                ndistinct = get_variable_numdistinct(&vardata, &isdefault);
 
                if (indexcol == 0)
                {
                    /*
                     * Get an estimate of the leading column's correlation in
                     * passing (avoids rereading variable stats below)
                     */
                    if (HeapTupleIsValid(vardata.statsTuple))
                        correlation = btcost_correlation(index, &vardata);
                    have_correlation = true;
                }
 
                ReleaseVariableStats(vardata);
 
                /*
                 * If ndistinct is a default estimate, conservatively assume
                 * that no skipping will happen at runtime
                 */
                if (isdefault)
                {
                    num_sa_scans = num_sa_scans_prev_cols;
                    break;      /* done building indexBoundQuals */
                }
 
                /*
                 * Apply indexcol's indexSkipQuals selectivity to ndistinct
                 */
                if (indexSkipQuals != NIL)
                {
                    List       *partialSkipQuals;
                    Selectivity ndistinctfrac;
 
                    /*
                     * If the index is partial, AND the index predicate with
                     * the index-bound quals to produce a more accurate idea
                     * of the number of distinct values for prior indexcol
                     */
                    partialSkipQuals = add_predicate_to_index_quals(index,
                                                                    indexSkipQuals);
 
                    ndistinctfrac = clauselist_selectivity(root, partialSkipQuals,
                                                           index->rel->relid,
                                                           JOIN_INNER,
                                                           NULL);
 
                    /*
                     * If ndistinctfrac is selective (on its own), the scan is
                     * unlikely to benefit from repositioning itself using
                     * later quals.  Do not allow iclause->indexcol's quals to
                     * be added to indexBoundQuals (it would increase descent
                     * costs, without lowering numIndexTuples costs by much).
                     */
                    if (ndistinctfrac < DEFAULT_RANGE_INEQ_SEL)
                    {
                        num_sa_scans = num_sa_scans_prev_cols;
                        break;  /* done building indexBoundQuals */
                    }
 
                    /* Adjust ndistinct downward */
                    ndistinct = rint(ndistinct * ndistinctfrac);
                    ndistinct = Max(ndistinct, 1);
                }
 
                /*
                 * When there's no inequality quals, account for the need to
                 * find an initial value by counting -inf/+inf as a value.
                 *
                 * We don't charge anything extra for possible next/prior key
                 * index probes, which are sometimes used to find the next
                 * valid skip array element (ahead of using the located
                 * element value to relocate the scan to the next position
                 * that might contain matching tuples).  It seems hard to do
                 * better here.  Use of the skip support infrastructure often
                 * avoids most next/prior key probes.  But even when it can't,
                 * there's a decent chance that most individual next/prior key
                 * probes will locate a leaf page whose key space overlaps all
                 * of the scan's keys (even the lower-order keys) -- which
                 * also avoids the need for a separate, extra index descent.
                 * Note also that these probes are much cheaper than non-probe
                 * primitive index scans: they're reliably very selective.
                 */
                if (indexSkipQuals == NIL)
                    ndistinct += 1;
 
                /*
                 * Update num_sa_scans estimate by multiplying by ndistinct.
                 *
                 * We make the pessimistic assumption that there is no
                 * naturally occurring cross-column correlation.  This is
                 * often wrong, but it seems best to err on the side of not
                 * expecting skipping to be helpful...
                 */
                num_sa_scans *= ndistinct;
 
                /*
                 * ...but back out of adding this latest group of 1 or more
                 * skip arrays when num_sa_scans exceeds the total number of
                 * index pages (revert to num_sa_scans from before indexcol).
                 * This causes a sharp discontinuity in cost (as a function of
                 * the indexcol's ndistinct), but that is representative of
                 * actual runtime costs.
                 *
                 * Note that skipping is helpful when each primitive index
                 * scan only manages to skip over 1 or 2 irrelevant leaf pages
                 * on average.  Skip arrays bring savings in CPU costs due to
                 * the scan not needing to evaluate indexquals against every
                 * tuple, which can greatly exceed any savings in I/O costs.
                 * This test is a test of whether num_sa_scans implies that
                 * we're past the point where the ability to skip ceases to
                 * lower the scan's costs (even qual evaluation CPU costs).
                 */
                if (index->pages < num_sa_scans)
                {
                    num_sa_scans = num_sa_scans_prev_cols;
                    break;      /* done building indexBoundQuals */
                }
 
                indexcol++;
                indexSkipQuals = NIL;
            }
 
            /*
             * Finished considering the need to add skip arrays to bridge an
             * initial eqQualHere gap between the old and new index columns
             * (or there was no initial eqQualHere gap in the first place).
             *
             * If an initial gap could not be bridged, then new column's quals
             * (i.e. iclause->indexcol's quals) won't go into indexBoundQuals,
             * and so won't affect our final numIndexTuples estimate.
             */
            if (indexcol != iclause->indexcol)
                break;          /* done building indexBoundQuals */
        }
 
        Assert(indexcol == iclause->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);
                found_row_compare = true;
            }
            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_array = 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/skip scan 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);
 
            /*
             * We apply inequality selectivities to estimate index descent
             * costs with scans that use skip arrays.  Save this indexcol's
             * RestrictInfos if it looks like they'll be needed for that.
             */
            if (!eqQualHere && !found_row_compare &&
                indexcol < index->nkeycolumns - 1)
                indexSkipQuals = lappend(indexSkipQuals, 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, an array or NullTest
     * always invalidates that theory (even when eqQualHere has been set).
     */
    if (index->unique &&
        indexcol == index->nkeycolumns - 1 &&
        eqQualHere &&
        !found_array &&
        !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 array element 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.
         *
         * Note: num_sa_scans includes both ScalarArrayOp array elements and
         * skip array elements whose qual affects our numIndexTuples estimate.
         */
        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 array quals
         * included in indexBoundQuals, and then round to integer.
         *
         * It is tempting to make genericcostestimate behave as if array
         * 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 SAOP or skip array keys, charge this once per estimated
     * 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
     * SAOP/skip array descent.
     */
    descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
    costs.indexStartupCost += descentCost;
    costs.indexTotalCost += costs.num_sa_scans * descentCost;
 
    if (!have_correlation)
    {
        examine_indexcol_variable(root, index, 0, &vardata);
        if (HeapTupleIsValid(vardata.statsTuple))
            costs.indexCorrelation = btcost_correlation(index, &vardata);
        ReleaseVariableStats(vardata);
    }
    else
    {
        /* btcost_correlation already called earlier on */
        costs.indexCorrelation = correlation;
    }
 
    *indexStartupCost = costs.indexStartupCost;
    *indexTotalCost = costs.indexTotalCost;
    *indexSelectivity = costs.indexSelectivity;
    *indexCorrelation = costs.indexCorrelation;
    *indexPages = costs.numIndexPages;
}

References add_predicate_to_index_quals(), ScalarArrayOpExpr::args, Assert(), btcost_correlation(), BTEqualStrategyNumber, RestrictInfo::clause, clauselist_selectivity(), cpu_operator_cost, DEFAULT_PAGE_CPU_MULTIPLIER, DEFAULT_RANGE_INEQ_SEL, elog, ERROR, estimate_array_length(), examine_indexcol_variable(), genericcostestimate(), get_op_opfamily_strategy(), get_variable_numdistinct(), HeapTupleIsValid, IndexPath::indexclauses, IndexClause::indexcol, GenericCosts::indexCorrelation, IndexPath::indexinfo, IndexClause::indexquals, GenericCosts::indexSelectivity, GenericCosts::indexStartupCost, GenericCosts::indexTotalCost, InvalidOid, IS_NULL, IsA, JOIN_INNER, lappend(), lfirst_node, linitial_oid, lsecond, Max, Min, NIL, nodeTag, NullTest::nulltesttype, GenericCosts::num_sa_scans, GenericCosts::numIndexPages, GenericCosts::numIndexTuples, OidIsValid, OpExpr::opno, ScalarArrayOpExpr::opno, ReleaseVariableStats, root, 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 8141 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 7731 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 7689 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 7786 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;
}