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

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

Definition at line 7886 of file selfuncs.c.

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

Referenced by brinhandler().

{
    IndexOptInfo *index = path->indexinfo;
    List       *indexQuals = path->indexquals;
    double      numPages = index->pages;
    RelOptInfo *baserel = index->rel;
    RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
    List       *qinfos;
    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.
     */
    indexRel = index_open(index->indexoid, AccessShareLock);
    brinGetStats(indexRel, &statsData);
    index_close(indexRel, AccessShareLock);

    /*
     * 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;

    qinfos = deconstruct_indexquals(path);
    foreach(l, qinfos)
    {
        IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
        AttrNumber  attnum = index->indexkeys[qinfo->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 = qinfo->indexcol + 1;

            if (get_index_stats_hook &&
                (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
            {
                /*
                 * The hook took control of acquiring a stats tuple.  If it
                 * did supply a tuple, it'd better have supplied a freefunc.
                 */
                if (HeapTupleIsValid(vardata.statsTuple) &&
                    !vardata.freefunc)
                    elog(ERROR, "no function provided to release variable stats with");
            }
            else
            {
                vardata.statsTuple = SearchSysCache3(STATRELATTINH,
                                                     ObjectIdGetDatum(index->indexoid),
                                                     Int16GetDatum(attnum),
                                                     BoolGetDatum(false));
                vardata.freefunc = ReleaseSysCache;
            }
        }

        if (HeapTupleIsValid(vardata.statsTuple))
        {
            AttStatsSlot sslot;

            if (get_attstatsslot(&sslot, vardata.statsTuple,
                                 STATISTIC_KIND_CORRELATION, InvalidOid,
                                 ATTSTATSSLOT_NUMBERS))
            {
                double      varCorrelation = 0.0;

                if (sslot.nnumbers > 0)
                    varCorrelation = Abs(sslot.numbers[0]);

                if (varCorrelation > *indexCorrelation)
                    *indexCorrelation = varCorrelation;

                free_attstatsslot(&sslot);
            }
        }

        ReleaseVariableStats(vardata);
    }

    qualSelectivity = clauselist_selectivity(root, indexQuals,
                                             baserel->relid,
                                             JOIN_INNER, NULL);

    /* work out the actual number of ranges in the index */
    indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
                      1.0);

    /*
     * 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.
     */
    qual_arg_cost = other_operands_eval_cost(root, qinfos) +
        orderby_operands_eval_cost(root, path);

    /*
     * 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;
}

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

Definition at line 6806 of file selfuncs.c.

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

Referenced by bthandler().

{
    IndexOptInfo *index = path->indexinfo;
    List       *qinfos;
    GenericCosts costs;
    Oid         relid;
    AttrNumber  colnum;
    VariableStatData vardata;
    double      numIndexTuples;
    Cost        descentCost;
    List       *indexBoundQuals;
    int         indexcol;
    bool        eqQualHere;
    bool        found_saop;
    bool        found_is_null_op;
    double      num_sa_scans;
    ListCell   *lc;

    /* Do preliminary analysis of indexquals */
    qinfos = deconstruct_indexquals(path);

    /*
     * For a btree scan, only leading '=' quals plus inequality quals for the
     * immediately next attribute contribute to index selectivity (these are
     * the "boundary quals" that determine the starting and stopping points of
     * the index scan).  Additional quals can suppress visits to the heap, so
     * it's OK to count them in indexSelectivity, but they should not count
     * for estimating numIndexTuples.  So we must examine the given indexquals
     * to find out which ones count as boundary quals.  We rely on the
     * knowledge that they are given in index column order.
     *
     * For a RowCompareExpr, we consider only the first column, just as
     * rowcomparesel() does.
     *
     * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
     * index scans not one, but the ScalarArrayOpExpr's operator can be
     * considered to act the same as it normally does.
     */
    indexBoundQuals = NIL;
    indexcol = 0;
    eqQualHere = false;
    found_saop = false;
    found_is_null_op = false;
    num_sa_scans = 1;
    foreach(lc, qinfos)
    {
        IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
        RestrictInfo *rinfo = qinfo->rinfo;
        Expr       *clause = rinfo->clause;
        Oid         clause_op;
        int         op_strategy;

        if (indexcol != qinfo->indexcol)
        {
            /* Beginning of a new column's quals */
            if (!eqQualHere)
                break;          /* done if no '=' qual for indexcol */
            eqQualHere = false;
            indexcol++;
            if (indexcol != qinfo->indexcol)
                break;          /* no quals at all for indexcol */
        }

        if (IsA(clause, ScalarArrayOpExpr))
        {
            int         alength = estimate_array_length(qinfo->other_operand);

            found_saop = true;
            /* count up number of SA scans induced by indexBoundQuals only */
            if (alength > 1)
                num_sa_scans *= alength;
        }
        else if (IsA(clause, NullTest))
        {
            NullTest   *nt = (NullTest *) clause;

            if (nt->nulltesttype == IS_NULL)
            {
                found_is_null_op = true;
                /* IS NULL is like = for selectivity determination purposes */
                eqQualHere = true;
            }
        }

        /*
         * We would need to commute the clause_op if not varonleft, except
         * that we only care if it's equality or not, so that refinement is
         * unnecessary.
         */
        clause_op = qinfo->clause_op;

        /* 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->ncolumns - 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_quals(index, indexBoundQuals);

        btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
                                                  index->rel->relid,
                                                  JOIN_INNER,
                                                  NULL);
        numIndexTuples = btreeSelectivity * index->rel->tuples;

        /*
         * As in genericcostestimate(), we have to adjust for any
         * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
         * to integer.
         */
        numIndexTuples = rint(numIndexTuples / num_sa_scans);
    }

    /*
     * Now do generic index cost estimation.
     */
    MemSet(&costs, 0, sizeof(costs));
    costs.numIndexTuples = numIndexTuples;

    genericcostestimate(root, path, loop_count, qinfos, &costs);

    /*
     * Add a CPU-cost component to represent the costs of initial btree
     * descent.  We don't charge any I/O cost for touching upper btree levels,
     * since they tend to stay in cache, but we still have to do about log2(N)
     * comparisons to descend a btree of N leaf tuples.  We charge one
     * cpu_operator_cost per comparison.
     *
     * If there are ScalarArrayOpExprs, charge this once per SA scan.  The
     * ones after the first one are not startup cost so far as the overall
     * plan is concerned, so add them only to "total" cost.
     */
    if (index->tuples > 1)      /* avoid computing log(0) */
    {
        descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
        costs.indexStartupCost += descentCost;
        costs.indexTotalCost += costs.num_sa_scans * descentCost;
    }

    /*
     * Even though we're not charging I/O cost for touching upper btree pages,
     * it's still reasonable to charge some CPU cost per page descended
     * through.  Moreover, if we had no such charge at all, bloated indexes
     * would appear to have the same search cost as unbloated ones, at least
     * in cases where only a single leaf page is expected to be visited.  This
     * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
     * touched.  The number of such pages is btree tree height plus one (ie,
     * we charge for the leaf page too).  As above, charge once per SA scan.
     */
    descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
    costs.indexStartupCost += descentCost;
    costs.indexTotalCost += costs.num_sa_scans * descentCost;

    /*
     * If we can get an estimate of the first column's ordering correlation C
     * from pg_statistic, estimate the index correlation as C for a
     * single-column index, or C * 0.75 for multiple columns. (The idea here
     * is that multiple columns dilute the importance of the first column's
     * ordering, but don't negate it entirely.  Before 8.0 we divided the
     * correlation by the number of columns, but that seems too strong.)
     */
    MemSet(&vardata, 0, sizeof(vardata));

    if (index->indexkeys[0] != 0)
    {
        /* Simple variable --- look to stats for the underlying table */
        RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);

        Assert(rte->rtekind == RTE_RELATION);
        relid = rte->relid;
        Assert(relid != InvalidOid);
        colnum = index->indexkeys[0];

        if (get_relation_stats_hook &&
            (*get_relation_stats_hook) (root, rte, colnum, &vardata))
        {
            /*
             * The hook took control of acquiring a stats tuple.  If it did
             * supply a tuple, it'd better have supplied a freefunc.
             */
            if (HeapTupleIsValid(vardata.statsTuple) &&
                !vardata.freefunc)
                elog(ERROR, "no function provided to release variable stats with");
        }
        else
        {
            vardata.statsTuple = SearchSysCache3(STATRELATTINH,
                                                 ObjectIdGetDatum(relid),
                                                 Int16GetDatum(colnum),
                                                 BoolGetDatum(rte->inh));
            vardata.freefunc = ReleaseSysCache;
        }
    }
    else
    {
        /* Expression --- maybe there are stats for the index itself */
        relid = index->indexoid;
        colnum = 1;

        if (get_index_stats_hook &&
            (*get_index_stats_hook) (root, relid, colnum, &vardata))
        {
            /*
             * The hook took control of acquiring a stats tuple.  If it did
             * supply a tuple, it'd better have supplied a freefunc.
             */
            if (HeapTupleIsValid(vardata.statsTuple) &&
                !vardata.freefunc)
                elog(ERROR, "no function provided to release variable stats with");
        }
        else
        {
            vardata.statsTuple = SearchSysCache3(STATRELATTINH,
                                                 ObjectIdGetDatum(relid),
                                                 Int16GetDatum(colnum),
                                                 BoolGetDatum(false));
            vardata.freefunc = ReleaseSysCache;
        }
    }

    if (HeapTupleIsValid(vardata.statsTuple))
    {
        Oid         sortop;
        AttStatsSlot sslot;

        sortop = get_opfamily_member(index->opfamily[0],
                                     index->opcintype[0],
                                     index->opcintype[0],
                                     BTLessStrategyNumber);
        if (OidIsValid(sortop) &&
            get_attstatsslot(&sslot, vardata.statsTuple,
                             STATISTIC_KIND_CORRELATION, sortop,
                             ATTSTATSSLOT_NUMBERS))
        {
            double      varCorrelation;

            Assert(sslot.nnumbers == 1);
            varCorrelation = sslot.numbers[0];

            if (index->reverse_sort[0])
                varCorrelation = -varCorrelation;

            if (index->ncolumns > 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;
}

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

Definition at line 7561 of file selfuncs.c.

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

Referenced by ginhandler().

{
    IndexOptInfo *index = path->indexinfo;
    List       *indexQuals = path->indexquals;
    List       *indexOrderBys = path->indexorderbys;
    List       *qinfos;
    ListCell   *l;
    List       *selectivityQuals;
    double      numPages = index->pages,
                numTuples = index->tuples;
    double      numEntryPages,
                numDataPages,
                numPendingPages,
                numEntries;
    GinQualCounts counts;
    bool        matchPossible;
    double      partialScale;
    double      entryPagesFetched,
                dataPagesFetched,
                dataPagesFetchedBySel;
    double      qual_op_cost,
                qual_arg_cost,
                spc_random_page_cost,
                outer_scans;
    Relation    indexRel;
    GinStatsData ginStats;

    /* Do preliminary analysis of indexquals */
    qinfos = deconstruct_indexquals(path);

    /*
     * Obtain statistical information from the meta page, if possible.  Else
     * set ginStats to zeroes, and we'll cope below.
     */
    if (!index->hypothetical)
    {
        indexRel = index_open(index->indexoid, AccessShareLock);
        ginGetStats(indexRel, &ginStats);
        index_close(indexRel, AccessShareLock);
    }
    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;

    /*
     * Include predicate in selectivityQuals (should match
     * genericcostestimate)
     */
    if (index->indpred != NIL)
    {
        List       *predExtraQuals = NIL;

        foreach(l, index->indpred)
        {
            Node       *predQual = (Node *) lfirst(l);
            List       *oneQual = list_make1(predQual);

            if (!predicate_implied_by(oneQual, indexQuals, false))
                predExtraQuals = list_concat(predExtraQuals, oneQual);
        }
        /* list_concat avoids modifying the passed-in indexQuals list */
        selectivityQuals = list_concat(predExtraQuals, indexQuals);
    }
    else
        selectivityQuals = 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(l, qinfos)
    {
        IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
        Expr       *clause = qinfo->rinfo->clause;

        if (IsA(clause, OpExpr))
        {
            matchPossible = gincost_opexpr(root,
                                           index,
                                           qinfo,
                                           &counts);
            if (!matchPossible)
                break;
        }
        else if (IsA(clause, ScalarArrayOpExpr))
        {
            matchPossible = gincost_scalararrayopexpr(root,
                                                      index,
                                                      qinfo,
                                                      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 (counts.haveFullScan || indexQuals == NIL)
    {
        /*
         * Full index scan will be required.  We treat this as if every key in
         * the index had been listed in the query; is that reasonable?
         */
        counts.partialEntries = 0;
        counts.exactEntries = numEntries;
        counts.searchEntries = numEntries;
    }

    /* Will we have more than one iteration of a nestloop scan? */
    outer_scans = loop_count;

    /*
     * Compute cost to begin scan, first of all, pay attention to pending
     * list.
     */
    entryPagesFetched = numPendingPages;

    /*
     * Estimate number of entry pages read.  We need to do
     * counts.searchEntries searches.  Use a power function as it should be,
     * but tuples on leaf pages usually is much greater. Here we include all
     * searches in entry tree, including search of first entry in partial
     * match algorithm
     */
    entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));

    /*
     * Add an estimate of entry pages read by partial match algorithm. It's a
     * scan over leaf pages in entry tree.  We haven't any useful stats here,
     * so estimate it as proportion.  Because counts.partialEntries is really
     * pretty bogus (see code above), it's possible that it is more than
     * numEntries; clamp the proportion to ensure sanity.
     */
    partialScale = counts.partialEntries / numEntries;
    partialScale = Min(partialScale, 1.0);

    entryPagesFetched += ceil(numEntryPages * partialScale);

    /*
     * Partial match algorithm reads all data pages before doing actual scan,
     * so it's a startup cost.  Again, we haven't any useful stats here, so
     * estimate it as proportion.
     */
    dataPagesFetched = ceil(numDataPages * partialScale);

    /*
     * Calculate cache effects if more than one scan due to nestloops or array
     * quals.  The result is pro-rated per nestloop scan, but the array qual
     * factor shouldn't be pro-rated (compare genericcostestimate).
     */
    if (outer_scans > 1 || counts.arrayScans > 1)
    {
        entryPagesFetched *= outer_scans * counts.arrayScans;
        entryPagesFetched = index_pages_fetched(entryPagesFetched,
                                                (BlockNumber) numEntryPages,
                                                numEntryPages, root);
        entryPagesFetched /= outer_scans;
        dataPagesFetched *= outer_scans * counts.arrayScans;
        dataPagesFetched = index_pages_fetched(dataPagesFetched,
                                               (BlockNumber) numDataPages,
                                               numDataPages, root);
        dataPagesFetched /= outer_scans;
    }

    /*
     * Here we use random page cost because logically-close pages could be far
     * apart on disk.
     */
    *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;

    /*
     * Now compute the number of data pages fetched during the scan.
     *
     * We assume every entry to have the same number of items, and that there
     * is no overlap between them. (XXX: tsvector and array opclasses collect
     * statistics on the frequency of individual keys; it would be nice to use
     * those here.)
     */
    dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);

    /*
     * If there is a lot of overlap among the entries, in particular if one of
     * the entries is very frequent, the above calculation can grossly
     * under-estimate.  As a simple cross-check, calculate a lower bound based
     * on the overall selectivity of the quals.  At a minimum, we must read
     * one item pointer for each matching entry.
     *
     * The width of each item pointer varies, based on the level of
     * compression.  We don't have statistics on that, but an average of
     * around 3 bytes per item is fairly typical.
     */
    dataPagesFetchedBySel = ceil(*indexSelectivity *
                                 (numTuples / (BLCKSZ / 3)));
    if (dataPagesFetchedBySel > dataPagesFetched)
        dataPagesFetched = dataPagesFetchedBySel;

    /* Account for cache effects, the same as above */
    if (outer_scans > 1 || counts.arrayScans > 1)
    {
        dataPagesFetched *= outer_scans * counts.arrayScans;
        dataPagesFetched = index_pages_fetched(dataPagesFetched,
                                               (BlockNumber) numDataPages,
                                               numDataPages, root);
        dataPagesFetched /= outer_scans;
    }

    /* And apply random_page_cost as the cost per page */
    *indexTotalCost = *indexStartupCost +
        dataPagesFetched * spc_random_page_cost;

    /*
     * Add on index qual eval costs, much as in genericcostestimate
     */
    qual_arg_cost = other_operands_eval_cost(root, qinfos) +
        orderby_operands_eval_cost(root, path);
    qual_op_cost = cpu_operator_cost *
        (list_length(indexQuals) + list_length(indexOrderBys));

    *indexStartupCost += qual_arg_cost;
    *indexTotalCost += qual_arg_cost;
    *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
    *indexPages = dataPagesFetched;
}

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

Definition at line 7147 of file selfuncs.c.

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

Referenced by gisthandler().

{
    IndexOptInfo *index = path->indexinfo;
    List       *qinfos;
    GenericCosts costs;
    Cost        descentCost;

    /* Do preliminary analysis of indexquals */
    qinfos = deconstruct_indexquals(path);

    MemSet(&costs, 0, sizeof(costs));

    genericcostestimate(root, path, loop_count, qinfos, &costs);

    /*
     * We model index descent costs similarly to those for btree, but to do
     * that we first need an idea of the tree height.  We somewhat arbitrarily
     * assume that the fanout is 100, meaning the tree height is at most
     * log100(index->pages).
     *
     * Although this computation isn't really expensive enough to require
     * caching, we might as well use index->tree_height to cache it.
     */
    if (index->tree_height < 0) /* unknown? */
    {
        if (index->pages > 1)   /* avoid computing log(0) */
            index->tree_height = (int) (log(index->pages) / log(100.0));
        else
            index->tree_height = 0;
    }

    /*
     * Add a CPU-cost component to represent the costs of initial descent. We
     * just use log(N) here not log2(N) since the branching factor isn't
     * necessarily two anyway.  As for btree, charge once per SA scan.
     */
    if (index->tuples > 1)      /* avoid computing log(0) */
    {
        descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
        costs.indexStartupCost += descentCost;
        costs.indexTotalCost += costs.num_sa_scans * descentCost;
    }

    /*
     * Likewise add a per-page charge, calculated the same as for btrees.
     */
    descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
    costs.indexStartupCost += descentCost;
    costs.indexTotalCost += costs.num_sa_scans * descentCost;

    *indexStartupCost = costs.indexStartupCost;
    *indexTotalCost = costs.indexTotalCost;
    *indexSelectivity = costs.indexSelectivity;
    *indexCorrelation = costs.indexCorrelation;
    *indexPages = costs.numIndexPages;
}

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

Definition at line 7099 of file selfuncs.c.

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

Referenced by hashhandler().

{
    List       *qinfos;
    GenericCosts costs;

    /* Do preliminary analysis of indexquals */
    qinfos = deconstruct_indexquals(path);

    MemSet(&costs, 0, sizeof(costs));

    genericcostestimate(root, path, loop_count, qinfos, &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;
}

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

Definition at line 7208 of file selfuncs.c.

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

Referenced by spghandler().

{
    IndexOptInfo *index = path->indexinfo;
    List       *qinfos;
    GenericCosts costs;
    Cost        descentCost;

    /* Do preliminary analysis of indexquals */
    qinfos = deconstruct_indexquals(path);

    MemSet(&costs, 0, sizeof(costs));

    genericcostestimate(root, path, loop_count, qinfos, &costs);

    /*
     * We model index descent costs similarly to those for btree, but to do
     * that we first need an idea of the tree height.  We somewhat arbitrarily
     * assume that the fanout is 100, meaning the tree height is at most
     * log100(index->pages).
     *
     * Although this computation isn't really expensive enough to require
     * caching, we might as well use index->tree_height to cache it.
     */
    if (index->tree_height < 0) /* unknown? */
    {
        if (index->pages > 1)   /* avoid computing log(0) */
            index->tree_height = (int) (log(index->pages) / log(100.0));
        else
            index->tree_height = 0;
    }

    /*
     * Add a CPU-cost component to represent the costs of initial descent. We
     * just use log(N) here not log2(N) since the branching factor isn't
     * necessarily two anyway.  As for btree, charge once per SA scan.
     */
    if (index->tuples > 1)      /* avoid computing log(0) */
    {
        descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
        costs.indexStartupCost += descentCost;
        costs.indexTotalCost += costs.num_sa_scans * descentCost;
    }

    /*
     * Likewise add a per-page charge, calculated the same as for btrees.
     */
    descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
    costs.indexStartupCost += descentCost;
    costs.indexTotalCost += costs.num_sa_scans * descentCost;

    *indexStartupCost = costs.indexStartupCost;
    *indexTotalCost = costs.indexTotalCost;
    *indexSelectivity = costs.indexSelectivity;
    *indexCorrelation = costs.indexCorrelation;
    *indexPages = costs.numIndexPages;
}