statistics.h File Reference

#include "commands/vacuum.h"
#include "nodes/pathnodes.h"

Include dependency graph for statistics.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	MVNDistinctItem
struct	MVNDistinct
struct	MVDependency
struct	MVDependencies
struct	MCVItem
struct	MCVList

Macros
#define	STATS_MAX_DIMENSIONS   8 /* max number of attributes */
#define	STATS_NDISTINCT_MAGIC   0xA352BFA4 /* struct identifier */
#define	STATS_NDISTINCT_TYPE_BASIC   1 /* struct version */
#define	STATS_DEPS_MAGIC   0xB4549A2C /* marks serialized bytea */
#define	STATS_DEPS_TYPE_BASIC   1 /* basic dependencies type */
#define	STATS_MCV_MAGIC   0xE1A651C2 /* marks serialized bytea */
#define	STATS_MCV_TYPE_BASIC   1 /* basic MCV list type */
#define	STATS_MCVLIST_MAX_ITEMS   MAX_STATISTICS_TARGET

Typedefs
typedef struct MVNDistinctItem	MVNDistinctItem
typedef struct MVNDistinct	MVNDistinct
typedef struct MVDependency	MVDependency
typedef struct MVDependencies	MVDependencies
typedef struct MCVItem	MCVItem
typedef struct MCVList	MCVList

Functions
MVNDistinct *	statext_ndistinct_load (Oid mvoid, bool inh)
MVDependencies *	statext_dependencies_load (Oid mvoid, bool inh)
MCVList *	statext_mcv_load (Oid mvoid, bool inh)
void	BuildRelationExtStatistics (Relation onerel, bool inh, double totalrows, int numrows, HeapTuple *rows, int natts, VacAttrStats **vacattrstats)
int	ComputeExtStatisticsRows (Relation onerel, int natts, VacAttrStats **vacattrstats)
bool	statext_is_kind_built (HeapTuple htup, char type)
Selectivity	dependencies_clauselist_selectivity (PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Bitmapset **estimatedclauses)
Selectivity	statext_clauselist_selectivity (PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Bitmapset **estimatedclauses, bool is_or)
bool	has_stats_of_kind (List *stats, char requiredkind)
StatisticExtInfo *	choose_best_statistics (List *stats, char requiredkind, bool inh, Bitmapset **clause_attnums, List **clause_exprs, int nclauses)
HeapTuple	statext_expressions_load (Oid stxoid, bool inh, int idx)

Macro Definition Documentation

STATS_DEPS_MAGIC

#define STATS_DEPS_MAGIC   0xB4549A2C /* marks serialized bytea */

Definition at line 43 of file statistics.h.

STATS_DEPS_TYPE_BASIC

#define STATS_DEPS_TYPE_BASIC   1 /* basic dependencies type */

Definition at line 44 of file statistics.h.

STATS_MAX_DIMENSIONS

#define STATS_MAX_DIMENSIONS   8 /* max number of attributes */

Definition at line 19 of file statistics.h.

STATS_MCV_MAGIC

#define STATS_MCV_MAGIC   0xE1A651C2 /* marks serialized bytea */

Definition at line 66 of file statistics.h.

STATS_MCV_TYPE_BASIC

#define STATS_MCV_TYPE_BASIC   1 /* basic MCV list type */

Definition at line 67 of file statistics.h.

STATS_MCVLIST_MAX_ITEMS

#define STATS_MCVLIST_MAX_ITEMS   MAX_STATISTICS_TARGET

Definition at line 70 of file statistics.h.

STATS_NDISTINCT_MAGIC

#define STATS_NDISTINCT_MAGIC   0xA352BFA4 /* struct identifier */

Definition at line 22 of file statistics.h.

STATS_NDISTINCT_TYPE_BASIC

#define STATS_NDISTINCT_TYPE_BASIC   1 /* struct version */

Definition at line 23 of file statistics.h.

Typedef Documentation

MCVItem

typedef struct MCVItem MCVItem

MCVList

typedef struct MCVList MCVList

MVDependencies

typedef struct MVDependencies MVDependencies

MVDependency

typedef struct MVDependency MVDependency

MVNDistinct

typedef struct MVNDistinct MVNDistinct

MVNDistinctItem

typedef struct MVNDistinctItem MVNDistinctItem

Function Documentation

BuildRelationExtStatistics()

void BuildRelationExtStatistics	(	Relation	onerel,
		bool	inh,
		double	totalrows,
		int	numrows,
		HeapTuple *	rows,
		int	natts,
		VacAttrStats **	vacattrstats
	)

Definition at line 115 of file extended_stats.c.

{
    Relation    pg_stext;
    ListCell   *lc;
    List       *statslist;
    MemoryContext cxt;
    MemoryContext oldcxt;
    int64       ext_cnt;
 
    /* Do nothing if there are no columns to analyze. */
    if (!natts)
        return;
 
    /* the list of stats has to be allocated outside the memory context */
    pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
    statslist = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
 
    /* memory context for building each statistics object */
    cxt = AllocSetContextCreate(CurrentMemoryContext,
                                "BuildRelationExtStatistics",
                                ALLOCSET_DEFAULT_SIZES);
    oldcxt = MemoryContextSwitchTo(cxt);
 
    /* report this phase */
    if (statslist != NIL)
    {
        const int   index[] = {
            PROGRESS_ANALYZE_PHASE,
            PROGRESS_ANALYZE_EXT_STATS_TOTAL
        };
        const int64 val[] = {
            PROGRESS_ANALYZE_PHASE_COMPUTE_EXT_STATS,
            list_length(statslist)
        };
 
        pgstat_progress_update_multi_param(2, index, val);
    }
 
    ext_cnt = 0;
    foreach(lc, statslist)
    {
        StatExtEntry *stat = (StatExtEntry *) lfirst(lc);
        MVNDistinct *ndistinct = NULL;
        MVDependencies *dependencies = NULL;
        MCVList    *mcv = NULL;
        Datum       exprstats = (Datum) 0;
        VacAttrStats **stats;
        ListCell   *lc2;
        int         stattarget;
        StatsBuildData *data;
 
        /*
         * Check if we can build these stats based on the column analyzed. If
         * not, report this fact (except in autovacuum) and move on.
         */
        stats = lookup_var_attr_stats(onerel, stat->columns, stat->exprs,
                                      natts, vacattrstats);
        if (!stats)
        {
            if (!IsAutoVacuumWorkerProcess())
                ereport(WARNING,
                        (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                         errmsg("statistics object \"%s.%s\" could not be computed for relation \"%s.%s\"",
                                stat->schema, stat->name,
                                get_namespace_name(onerel->rd_rel->relnamespace),
                                RelationGetRelationName(onerel)),
                         errtable(onerel)));
            continue;
        }
 
        /* compute statistics target for this statistics object */
        stattarget = statext_compute_stattarget(stat->stattarget,
                                                bms_num_members(stat->columns),
                                                stats);
 
        /*
         * Don't rebuild statistics objects with statistics target set to 0
         * (we just leave the existing values around, just like we do for
         * regular per-column statistics).
         */
        if (stattarget == 0)
            continue;
 
        /* evaluate expressions (if the statistics object has any) */
        data = make_build_data(onerel, stat, numrows, rows, stats, stattarget);
 
        /* compute statistic of each requested type */
        foreach(lc2, stat->types)
        {
            char        t = (char) lfirst_int(lc2);
 
            if (t == STATS_EXT_NDISTINCT)
                ndistinct = statext_ndistinct_build(totalrows, data);
            else if (t == STATS_EXT_DEPENDENCIES)
                dependencies = statext_dependencies_build(data);
            else if (t == STATS_EXT_MCV)
                mcv = statext_mcv_build(data, totalrows, stattarget);
            else if (t == STATS_EXT_EXPRESSIONS)
            {
                AnlExprData *exprdata;
                int         nexprs;
 
                /* should not happen, thanks to checks when defining stats */
                if (!stat->exprs)
                    elog(ERROR, "requested expression stats, but there are no expressions");
 
                exprdata = build_expr_data(stat->exprs, stattarget);
                nexprs = list_length(stat->exprs);
 
                compute_expr_stats(onerel, totalrows,
                                   exprdata, nexprs,
                                   rows, numrows);
 
                exprstats = serialize_expr_stats(exprdata, nexprs);
            }
        }
 
        /* store the statistics in the catalog */
        statext_store(stat->statOid, inh,
                      ndistinct, dependencies, mcv, exprstats, stats);
 
        /* for reporting progress */
        pgstat_progress_update_param(PROGRESS_ANALYZE_EXT_STATS_COMPUTED,
                                     ++ext_cnt);
 
        /* free the data used for building this statistics object */
        MemoryContextReset(cxt);
    }
 
    MemoryContextSwitchTo(oldcxt);
    MemoryContextDelete(cxt);
 
    list_free(statslist);
 
    table_close(pg_stext, RowExclusiveLock);
}

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, bms_num_members(), build_expr_data(), compute_expr_stats(), CurrentMemoryContext, data, elog(), ereport, errcode(), errmsg(), ERROR, errtable(), fetch_statentries_for_relation(), get_namespace_name(), IsAutoVacuumWorkerProcess(), lfirst, lfirst_int, list_free(), list_length(), lookup_var_attr_stats(), make_build_data(), MemoryContextDelete(), MemoryContextReset(), MemoryContextSwitchTo(), NIL, pgstat_progress_update_multi_param(), pgstat_progress_update_param(), PROGRESS_ANALYZE_EXT_STATS_COMPUTED, PROGRESS_ANALYZE_EXT_STATS_TOTAL, PROGRESS_ANALYZE_PHASE, PROGRESS_ANALYZE_PHASE_COMPUTE_EXT_STATS, RelationData::rd_rel, RelationGetRelationName, RelationGetRelid, RowExclusiveLock, serialize_expr_stats(), statext_compute_stattarget(), statext_dependencies_build(), statext_mcv_build(), statext_ndistinct_build(), statext_store(), table_close(), table_open(), val, and WARNING.

Referenced by do_analyze_rel().

choose_best_statistics()

StatisticExtInfo* choose_best_statistics	(	List *	stats,
		char	requiredkind,
		bool	inh,
		Bitmapset **	clause_attnums,
		List **	clause_exprs,
		int	nclauses
	)

Definition at line 1210 of file extended_stats.c.

{
    ListCell   *lc;
    StatisticExtInfo *best_match = NULL;
    int         best_num_matched = 2;   /* goal #1: maximize */
    int         best_match_keys = (STATS_MAX_DIMENSIONS + 1);   /* goal #2: minimize */
 
    foreach(lc, stats)
    {
        int         i;
        StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
        Bitmapset  *matched_attnums = NULL;
        Bitmapset  *matched_exprs = NULL;
        int         num_matched;
        int         numkeys;
 
        /* skip statistics that are not of the correct type */
        if (info->kind != requiredkind)
            continue;
 
        /* skip statistics with mismatching inheritance flag */
        if (info->inherit != inh)
            continue;
 
        /*
         * Collect attributes and expressions in remaining (unestimated)
         * clauses fully covered by this statistic object.
         *
         * We know already estimated clauses have both clause_attnums and
         * clause_exprs set to NULL. We leave the pointers NULL if already
         * estimated, or we reset them to NULL after estimating the clause.
         */
        for (i = 0; i < nclauses; i++)
        {
            Bitmapset  *expr_idxs = NULL;
 
            /* ignore incompatible/estimated clauses */
            if (!clause_attnums[i] && !clause_exprs[i])
                continue;
 
            /* ignore clauses that are not covered by this object */
            if (!bms_is_subset(clause_attnums[i], info->keys) ||
                !stat_covers_expressions(info, clause_exprs[i], &expr_idxs))
                continue;
 
            /* record attnums and indexes of expressions covered */
            matched_attnums = bms_add_members(matched_attnums, clause_attnums[i]);
            matched_exprs = bms_add_members(matched_exprs, expr_idxs);
        }
 
        num_matched = bms_num_members(matched_attnums) + bms_num_members(matched_exprs);
 
        bms_free(matched_attnums);
        bms_free(matched_exprs);
 
        /*
         * save the actual number of keys in the stats so that we can choose
         * the narrowest stats with the most matching keys.
         */
        numkeys = bms_num_members(info->keys) + list_length(info->exprs);
 
        /*
         * Use this object when it increases the number of matched attributes
         * and expressions or when it matches the same number of attributes
         * and expressions but these stats have fewer keys than any previous
         * match.
         */
        if (num_matched > best_num_matched ||
            (num_matched == best_num_matched && numkeys < best_match_keys))
        {
            best_match = info;
            best_num_matched = num_matched;
            best_match_keys = numkeys;
        }
    }
 
    return best_match;
}

References bms_add_members(), bms_free(), bms_is_subset(), bms_num_members(), StatisticExtInfo::exprs, i, StatisticExtInfo::inherit, StatisticExtInfo::keys, StatisticExtInfo::kind, lfirst, list_length(), stat_covers_expressions(), and STATS_MAX_DIMENSIONS.

Referenced by statext_mcv_clauselist_selectivity().

ComputeExtStatisticsRows()

int ComputeExtStatisticsRows	(	Relation	onerel,
		int	natts,
		VacAttrStats **	vacattrstats
	)

Definition at line 268 of file extended_stats.c.

{
    Relation    pg_stext;
    ListCell   *lc;
    List       *lstats;
    MemoryContext cxt;
    MemoryContext oldcxt;
    int         result = 0;
 
    /* If there are no columns to analyze, just return 0. */
    if (!natts)
        return 0;
 
    cxt = AllocSetContextCreate(CurrentMemoryContext,
                                "ComputeExtStatisticsRows",
                                ALLOCSET_DEFAULT_SIZES);
    oldcxt = MemoryContextSwitchTo(cxt);
 
    pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
    lstats = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
 
    foreach(lc, lstats)
    {
        StatExtEntry *stat = (StatExtEntry *) lfirst(lc);
        int         stattarget;
        VacAttrStats **stats;
        int         nattrs = bms_num_members(stat->columns);
 
        /*
         * Check if we can build this statistics object based on the columns
         * analyzed. If not, ignore it (don't report anything, we'll do that
         * during the actual build BuildRelationExtStatistics).
         */
        stats = lookup_var_attr_stats(onerel, stat->columns, stat->exprs,
                                      natts, vacattrstats);
 
        if (!stats)
            continue;
 
        /*
         * Compute statistics target, based on what's set for the statistic
         * object itself, and for its attributes.
         */
        stattarget = statext_compute_stattarget(stat->stattarget,
                                                nattrs, stats);
 
        /* Use the largest value for all statistics objects. */
        if (stattarget > result)
            result = stattarget;
    }
 
    table_close(pg_stext, RowExclusiveLock);
 
    MemoryContextSwitchTo(oldcxt);
    MemoryContextDelete(cxt);
 
    /* compute sample size based on the statistics target */
    return (300 * result);
}

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, bms_num_members(), CurrentMemoryContext, fetch_statentries_for_relation(), lfirst, lookup_var_attr_stats(), MemoryContextDelete(), MemoryContextSwitchTo(), RelationGetRelid, RowExclusiveLock, statext_compute_stattarget(), table_close(), and table_open().

Referenced by do_analyze_rel().

dependencies_clauselist_selectivity()

Selectivity dependencies_clauselist_selectivity	(	PlannerInfo *	root,
		List *	clauses,
		int	varRelid,
		JoinType	jointype,
		SpecialJoinInfo *	sjinfo,
		RelOptInfo *	rel,
		Bitmapset **	estimatedclauses
	)

Definition at line 1372 of file dependencies.c.

{
    Selectivity s1 = 1.0;
    ListCell   *l;
    Bitmapset  *clauses_attnums = NULL;
    AttrNumber *list_attnums;
    int         listidx;
    MVDependencies **func_dependencies;
    int         nfunc_dependencies;
    int         total_ndeps;
    MVDependency **dependencies;
    int         ndependencies;
    int         i;
    AttrNumber  attnum_offset;
    RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
 
    /* unique expressions */
    Node      **unique_exprs;
    int         unique_exprs_cnt;
 
    /* check if there's any stats that might be useful for us. */
    if (!has_stats_of_kind(rel->statlist, STATS_EXT_DEPENDENCIES))
        return 1.0;
 
    list_attnums = (AttrNumber *) palloc(sizeof(AttrNumber) *
                                         list_length(clauses));
 
    /*
     * We allocate space as if every clause was a unique expression, although
     * that's probably overkill. Some will be simple column references that
     * we'll translate to attnums, and there might be duplicates. But it's
     * easier and cheaper to just do one allocation than repalloc later.
     */
    unique_exprs = (Node **) palloc(sizeof(Node *) * list_length(clauses));
    unique_exprs_cnt = 0;
 
    /*
     * Pre-process the clauses list to extract the attnums seen in each item.
     * We need to determine if there's any clauses which will be useful for
     * dependency selectivity estimations. Along the way we'll record all of
     * the attnums for each clause in a list which we'll reference later so we
     * don't need to repeat the same work again. We'll also keep track of all
     * attnums seen.
     *
     * We also skip clauses that we already estimated using different types of
     * statistics (we treat them as incompatible).
     *
     * To handle expressions, we assign them negative attnums, as if it was a
     * system attribute (this is fine, as we only allow extended stats on user
     * attributes). And then we offset everything by the number of
     * expressions, so that we can store the values in a bitmapset.
     */
    listidx = 0;
    foreach(l, clauses)
    {
        Node       *clause = (Node *) lfirst(l);
        AttrNumber  attnum;
        Node       *expr = NULL;
 
        /* ignore clause by default */
        list_attnums[listidx] = InvalidAttrNumber;
 
        if (!bms_is_member(listidx, *estimatedclauses))
        {
            /*
             * If it's a simple column reference, just extract the attnum. If
             * it's an expression, assign a negative attnum as if it was a
             * system attribute.
             */
            if (dependency_is_compatible_clause(clause, rel->relid, &attnum))
            {
                list_attnums[listidx] = attnum;
            }
            else if (dependency_is_compatible_expression(clause, rel->relid,
                                                         rel->statlist,
                                                         &expr))
            {
                /* special attnum assigned to this expression */
                attnum = InvalidAttrNumber;
 
                Assert(expr != NULL);
 
                /* If the expression is duplicate, use the same attnum. */
                for (i = 0; i < unique_exprs_cnt; i++)
                {
                    if (equal(unique_exprs[i], expr))
                    {
                        /* negative attribute number to expression */
                        attnum = -(i + 1);
                        break;
                    }
                }
 
                /* not found in the list, so add it */
                if (attnum == InvalidAttrNumber)
                {
                    unique_exprs[unique_exprs_cnt++] = expr;
 
                    /* after incrementing the value, to get -1, -2, ... */
                    attnum = (-unique_exprs_cnt);
                }
 
                /* remember which attnum was assigned to this clause */
                list_attnums[listidx] = attnum;
            }
        }
 
        listidx++;
    }
 
    Assert(listidx == list_length(clauses));
 
    /*
     * How much we need to offset the attnums? If there are no expressions,
     * then no offset is needed. Otherwise we need to offset enough for the
     * lowest value (-unique_exprs_cnt) to become 1.
     */
    if (unique_exprs_cnt > 0)
        attnum_offset = (unique_exprs_cnt + 1);
    else
        attnum_offset = 0;
 
    /*
     * Now that we know how many expressions there are, we can offset the
     * values just enough to build the bitmapset.
     */
    for (i = 0; i < list_length(clauses); i++)
    {
        AttrNumber  attnum;
 
        /* ignore incompatible or already estimated clauses */
        if (list_attnums[i] == InvalidAttrNumber)
            continue;
 
        /* make sure the attnum is in the expected range */
        Assert(list_attnums[i] >= (-unique_exprs_cnt));
        Assert(list_attnums[i] <= MaxHeapAttributeNumber);
 
        /* make sure the attnum is positive (valid AttrNumber) */
        attnum = list_attnums[i] + attnum_offset;
 
        /*
         * Either it's a regular attribute, or it's an expression, in which
         * case we must not have seen it before (expressions are unique).
         *
         * XXX Check whether it's a regular attribute has to be done using the
         * original attnum, while the second check has to use the value with
         * an offset.
         */
        Assert(AttrNumberIsForUserDefinedAttr(list_attnums[i]) ||
               !bms_is_member(attnum, clauses_attnums));
 
        /*
         * Remember the offset attnum, both for attributes and expressions.
         * We'll pass list_attnums to clauselist_apply_dependencies, which
         * uses it to identify clauses in a bitmap. We could also pass the
         * offset, but this is more convenient.
         */
        list_attnums[i] = attnum;
 
        clauses_attnums = bms_add_member(clauses_attnums, attnum);
    }
 
    /*
     * If there's not at least two distinct attnums and expressions, then
     * reject the whole list of clauses. We must return 1.0 so the calling
     * function's selectivity is unaffected.
     */
    if (bms_membership(clauses_attnums) != BMS_MULTIPLE)
    {
        bms_free(clauses_attnums);
        pfree(list_attnums);
        return 1.0;
    }
 
    /*
     * Load all functional dependencies matching at least two parameters. We
     * can simply consider all dependencies at once, without having to search
     * for the best statistics object.
     *
     * To not waste cycles and memory, we deserialize dependencies only for
     * statistics that match at least two attributes. The array is allocated
     * with the assumption that all objects match - we could grow the array to
     * make it just the right size, but it's likely wasteful anyway thanks to
     * moving the freed chunks to freelists etc.
     */
    func_dependencies = (MVDependencies **) palloc(sizeof(MVDependencies *) *
                                                   list_length(rel->statlist));
    nfunc_dependencies = 0;
    total_ndeps = 0;
 
    foreach(l, rel->statlist)
    {
        StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);
        int         nmatched;
        int         nexprs;
        int         k;
        MVDependencies *deps;
 
        /* skip statistics that are not of the correct type */
        if (stat->kind != STATS_EXT_DEPENDENCIES)
            continue;
 
        /* skip statistics with mismatching stxdinherit value */
        if (stat->inherit != rte->inh)
            continue;
 
        /*
         * Count matching attributes - we have to undo the attnum offsets. The
         * input attribute numbers are not offset (expressions are not
         * included in stat->keys, so it's not necessary). But we need to
         * offset it before checking against clauses_attnums.
         */
        nmatched = 0;
        k = -1;
        while ((k = bms_next_member(stat->keys, k)) >= 0)
        {
            AttrNumber  attnum = (AttrNumber) k;
 
            /* skip expressions */
            if (!AttrNumberIsForUserDefinedAttr(attnum))
                continue;
 
            /* apply the same offset as above */
            attnum += attnum_offset;
 
            if (bms_is_member(attnum, clauses_attnums))
                nmatched++;
        }
 
        /* count matching expressions */
        nexprs = 0;
        for (i = 0; i < unique_exprs_cnt; i++)
        {
            ListCell   *lc;
 
            foreach(lc, stat->exprs)
            {
                Node       *stat_expr = (Node *) lfirst(lc);
 
                /* try to match it */
                if (equal(stat_expr, unique_exprs[i]))
                    nexprs++;
            }
        }
 
        /*
         * Skip objects matching fewer than two attributes/expressions from
         * clauses.
         */
        if (nmatched + nexprs < 2)
            continue;
 
        deps = statext_dependencies_load(stat->statOid, rte->inh);
 
        /*
         * The expressions may be represented by different attnums in the
         * stats, we need to remap them to be consistent with the clauses.
         * That will make the later steps (e.g. picking the strongest item and
         * so on) much simpler and cheaper, because it won't need to care
         * about the offset at all.
         *
         * When we're at it, we can ignore dependencies that are not fully
         * matched by clauses (i.e. referencing attributes or expressions that
         * are not in the clauses).
         *
         * We have to do this for all statistics, as long as there are any
         * expressions - we need to shift the attnums in all dependencies.
         *
         * XXX Maybe we should do this always, because it also eliminates some
         * of the dependencies early. It might be cheaper than having to walk
         * the longer list in find_strongest_dependency later, especially as
         * we need to do that repeatedly?
         *
         * XXX We have to do this even when there are no expressions in
         * clauses, otherwise find_strongest_dependency may fail for stats
         * with expressions (due to lookup of negative value in bitmap). So we
         * need to at least filter out those dependencies. Maybe we could do
         * it in a cheaper way (if there are no expr clauses, we can just
         * discard all negative attnums without any lookups).
         */
        if (unique_exprs_cnt > 0 || stat->exprs != NIL)
        {
            int         ndeps = 0;
 
            for (i = 0; i < deps->ndeps; i++)
            {
                bool        skip = false;
                MVDependency *dep = deps->deps[i];
                int         j;
 
                for (j = 0; j < dep->nattributes; j++)
                {
                    int         idx;
                    Node       *expr;
                    AttrNumber  unique_attnum = InvalidAttrNumber;
                    AttrNumber  attnum;
 
                    /* undo the per-statistics offset */
                    attnum = dep->attributes[j];
 
                    /*
                     * For regular attributes we can simply check if it
                     * matches any clause. If there's no matching clause, we
                     * can just ignore it. We need to offset the attnum
                     * though.
                     */
                    if (AttrNumberIsForUserDefinedAttr(attnum))
                    {
                        dep->attributes[j] = attnum + attnum_offset;
 
                        if (!bms_is_member(dep->attributes[j], clauses_attnums))
                        {
                            skip = true;
                            break;
                        }
 
                        continue;
                    }
 
                    /*
                     * the attnum should be a valid system attnum (-1, -2,
                     * ...)
                     */
                    Assert(AttributeNumberIsValid(attnum));
 
                    /*
                     * For expressions, we need to do two translations. First
                     * we have to translate the negative attnum to index in
                     * the list of expressions (in the statistics object).
                     * Then we need to see if there's a matching clause. The
                     * index of the unique expression determines the attnum
                     * (and we offset it).
                     */
                    idx = -(1 + attnum);
 
                    /* Is the expression index is valid? */
                    Assert((idx >= 0) && (idx < list_length(stat->exprs)));
 
                    expr = (Node *) list_nth(stat->exprs, idx);
 
                    /* try to find the expression in the unique list */
                    for (int m = 0; m < unique_exprs_cnt; m++)
                    {
                        /*
                         * found a matching unique expression, use the attnum
                         * (derived from index of the unique expression)
                         */
                        if (equal(unique_exprs[m], expr))
                        {
                            unique_attnum = -(m + 1) + attnum_offset;
                            break;
                        }
                    }
 
                    /*
                     * Found no matching expression, so we can simply skip
                     * this dependency, because there's no chance it will be
                     * fully covered.
                     */
                    if (unique_attnum == InvalidAttrNumber)
                    {
                        skip = true;
                        break;
                    }
 
                    /* otherwise remap it to the new attnum */
                    dep->attributes[j] = unique_attnum;
                }
 
                /* if found a matching dependency, keep it */
                if (!skip)
                {
                    /* maybe we've skipped something earlier, so move it */
                    if (ndeps != i)
                        deps->deps[ndeps] = deps->deps[i];
 
                    ndeps++;
                }
            }
 
            deps->ndeps = ndeps;
        }
 
        /*
         * It's possible we've removed all dependencies, in which case we
         * don't bother adding it to the list.
         */
        if (deps->ndeps > 0)
        {
            func_dependencies[nfunc_dependencies] = deps;
            total_ndeps += deps->ndeps;
            nfunc_dependencies++;
        }
    }
 
    /* if no matching stats could be found then we've nothing to do */
    if (nfunc_dependencies == 0)
    {
        pfree(func_dependencies);
        bms_free(clauses_attnums);
        pfree(list_attnums);
        pfree(unique_exprs);
        return 1.0;
    }
 
    /*
     * Work out which dependencies we can apply, starting with the
     * widest/strongest ones, and proceeding to smaller/weaker ones.
     */
    dependencies = (MVDependency **) palloc(sizeof(MVDependency *) *
                                            total_ndeps);
    ndependencies = 0;
 
    while (true)
    {
        MVDependency *dependency;
        AttrNumber  attnum;
 
        /* the widest/strongest dependency, fully matched by clauses */
        dependency = find_strongest_dependency(func_dependencies,
                                               nfunc_dependencies,
                                               clauses_attnums);
        if (!dependency)
            break;
 
        dependencies[ndependencies++] = dependency;
 
        /* Ignore dependencies using this implied attribute in later loops */
        attnum = dependency->attributes[dependency->nattributes - 1];
        clauses_attnums = bms_del_member(clauses_attnums, attnum);
    }
 
    /*
     * If we found applicable dependencies, use them to estimate all
     * compatible clauses on attributes that they refer to.
     */
    if (ndependencies != 0)
        s1 = clauselist_apply_dependencies(root, clauses, varRelid, jointype,
                                           sjinfo, dependencies, ndependencies,
                                           list_attnums, estimatedclauses);
 
    /* free deserialized functional dependencies (and then the array) */
    for (i = 0; i < nfunc_dependencies; i++)
        pfree(func_dependencies[i]);
 
    pfree(dependencies);
    pfree(func_dependencies);
    bms_free(clauses_attnums);
    pfree(list_attnums);
    pfree(unique_exprs);
 
    return s1;
}

References Assert(), attnum, AttributeNumberIsValid, MVDependency::attributes, AttrNumberIsForUserDefinedAttr, bms_add_member(), bms_del_member(), bms_free(), bms_is_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), clauselist_apply_dependencies(), dependency_is_compatible_clause(), dependency_is_compatible_expression(), MVDependencies::deps, equal(), find_strongest_dependency(), has_stats_of_kind(), i, idx(), RangeTblEntry::inh, InvalidAttrNumber, j, lfirst, list_length(), list_nth(), MaxHeapAttributeNumber, MVDependency::nattributes, MVDependencies::ndeps, NIL, palloc(), pfree(), planner_rt_fetch, RelOptInfo::relid, s1, skip, statext_dependencies_load(), and RelOptInfo::statlist.

Referenced by statext_clauselist_selectivity().

has_stats_of_kind()

bool has_stats_of_kind	(	List *	stats,
		char	requiredkind
	)

Definition at line 1119 of file extended_stats.c.

{
    ListCell   *l;
 
    foreach(l, stats)
    {
        StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);
 
        if (stat->kind == requiredkind)
            return true;
    }
 
    return false;
}

References lfirst.

Referenced by dependencies_clauselist_selectivity(), and statext_mcv_clauselist_selectivity().

statext_clauselist_selectivity()

Selectivity statext_clauselist_selectivity	(	PlannerInfo *	root,
		List *	clauses,
		int	varRelid,
		JoinType	jointype,
		SpecialJoinInfo *	sjinfo,
		RelOptInfo *	rel,
		Bitmapset **	estimatedclauses,
		bool	is_or
	)

Definition at line 2005 of file extended_stats.c.

{
    Selectivity sel;
 
    /* First, try estimating clauses using a multivariate MCV list. */
    sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
                                             sjinfo, rel, estimatedclauses, is_or);
 
    /*
     * Functional dependencies only work for clauses connected by AND, so for
     * OR clauses we're done.
     */
    if (is_or)
        return sel;
 
    /*
     * Then, apply functional dependencies on the remaining clauses by calling
     * dependencies_clauselist_selectivity.  Pass 'estimatedclauses' so the
     * function can properly skip clauses already estimated above.
     *
     * The reasoning for applying dependencies last is that the more complex
     * stats can track more complex correlations between the attributes, and
     * so may be considered more reliable.
     *
     * For example, MCV list can give us an exact selectivity for values in
     * two columns, while functional dependencies can only provide information
     * about the overall strength of the dependency.
     */
    sel *= dependencies_clauselist_selectivity(root, clauses, varRelid,
                                               jointype, sjinfo, rel,
                                               estimatedclauses);
 
    return sel;
}

References dependencies_clauselist_selectivity(), and statext_mcv_clauselist_selectivity().

Referenced by clauselist_selectivity_ext(), and clauselist_selectivity_or().

statext_dependencies_load()

MVDependencies* statext_dependencies_load	(	Oid	mvoid,
		bool	inh
	)

Definition at line 621 of file dependencies.c.

{
    MVDependencies *result;
    bool        isnull;
    Datum       deps;
    HeapTuple   htup;
 
    htup = SearchSysCache2(STATEXTDATASTXOID,
                           ObjectIdGetDatum(mvoid),
                           BoolGetDatum(inh));
    if (!HeapTupleIsValid(htup))
        elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
 
    deps = SysCacheGetAttr(STATEXTDATASTXOID, htup,
                           Anum_pg_statistic_ext_data_stxddependencies, &isnull);
    if (isnull)
        elog(ERROR,
             "requested statistics kind \"%c\" is not yet built for statistics object %u",
             STATS_EXT_DEPENDENCIES, mvoid);
 
    result = statext_dependencies_deserialize(DatumGetByteaPP(deps));
 
    ReleaseSysCache(htup);
 
    return result;
}

References BoolGetDatum(), DatumGetByteaPP, elog(), ERROR, HeapTupleIsValid, ObjectIdGetDatum(), ReleaseSysCache(), SearchSysCache2(), statext_dependencies_deserialize(), STATEXTDATASTXOID, and SysCacheGetAttr().

Referenced by dependencies_clauselist_selectivity().

statext_expressions_load()

HeapTuple statext_expressions_load	(	Oid	stxoid,
		bool	inh,
		int	idx
	)

Definition at line 2426 of file extended_stats.c.

{
    bool        isnull;
    Datum       value;
    HeapTuple   htup;
    ExpandedArrayHeader *eah;
    HeapTupleHeader td;
    HeapTupleData tmptup;
    HeapTuple   tup;
 
    htup = SearchSysCache2(STATEXTDATASTXOID,
                           ObjectIdGetDatum(stxoid), BoolGetDatum(inh));
    if (!HeapTupleIsValid(htup))
        elog(ERROR, "cache lookup failed for statistics object %u", stxoid);
 
    value = SysCacheGetAttr(STATEXTDATASTXOID, htup,
                            Anum_pg_statistic_ext_data_stxdexpr, &isnull);
    if (isnull)
        elog(ERROR,
             "requested statistics kind \"%c\" is not yet built for statistics object %u",
             STATS_EXT_DEPENDENCIES, stxoid);
 
    eah = DatumGetExpandedArray(value);
 
    deconstruct_expanded_array(eah);
 
    td = DatumGetHeapTupleHeader(eah->dvalues[idx]);
 
    /* Build a temporary HeapTuple control structure */
    tmptup.t_len = HeapTupleHeaderGetDatumLength(td);
    ItemPointerSetInvalid(&(tmptup.t_self));
    tmptup.t_tableOid = InvalidOid;
    tmptup.t_data = td;
 
    tup = heap_copytuple(&tmptup);
 
    ReleaseSysCache(htup);
 
    return tup;
}

References BoolGetDatum(), DatumGetExpandedArray(), DatumGetHeapTupleHeader, deconstruct_expanded_array(), ExpandedArrayHeader::dvalues, elog(), ERROR, heap_copytuple(), HeapTupleHeaderGetDatumLength, HeapTupleIsValid, idx(), InvalidOid, ItemPointerSetInvalid(), ObjectIdGetDatum(), ReleaseSysCache(), SearchSysCache2(), STATEXTDATASTXOID, SysCacheGetAttr(), HeapTupleData::t_data, HeapTupleData::t_len, HeapTupleData::t_self, HeapTupleData::t_tableOid, and value.

Referenced by examine_variable().

statext_is_kind_built()

bool statext_is_kind_built	(	HeapTuple	htup,
		char	type
	)

Definition at line 392 of file extended_stats.c.

{
    AttrNumber  attnum;
 
    switch (type)
    {
        case STATS_EXT_NDISTINCT:
            attnum = Anum_pg_statistic_ext_data_stxdndistinct;
            break;
 
        case STATS_EXT_DEPENDENCIES:
            attnum = Anum_pg_statistic_ext_data_stxddependencies;
            break;
 
        case STATS_EXT_MCV:
            attnum = Anum_pg_statistic_ext_data_stxdmcv;
            break;
 
        case STATS_EXT_EXPRESSIONS:
            attnum = Anum_pg_statistic_ext_data_stxdexpr;
            break;
 
        default:
            elog(ERROR, "unexpected statistics type requested: %d", type);
    }
 
    return !heap_attisnull(htup, attnum, NULL);
}

References attnum, elog(), ERROR, heap_attisnull(), and type.

Referenced by get_relation_statistics_worker().

statext_mcv_load()

MCVList* statext_mcv_load	(	Oid	mvoid,
		bool	inh
	)

Definition at line 562 of file mcv.c.

{
    MCVList    *result;
    bool        isnull;
    Datum       mcvlist;
    HeapTuple   htup = SearchSysCache2(STATEXTDATASTXOID,
                                       ObjectIdGetDatum(mvoid), BoolGetDatum(inh));
 
    if (!HeapTupleIsValid(htup))
        elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
 
    mcvlist = SysCacheGetAttr(STATEXTDATASTXOID, htup,
                              Anum_pg_statistic_ext_data_stxdmcv, &isnull);
 
    if (isnull)
        elog(ERROR,
             "requested statistics kind \"%c\" is not yet built for statistics object %u",
             STATS_EXT_DEPENDENCIES, mvoid);
 
    result = statext_mcv_deserialize(DatumGetByteaP(mcvlist));
 
    ReleaseSysCache(htup);
 
    return result;
}

References BoolGetDatum(), DatumGetByteaP, elog(), ERROR, HeapTupleIsValid, ObjectIdGetDatum(), ReleaseSysCache(), SearchSysCache2(), statext_mcv_deserialize(), STATEXTDATASTXOID, and SysCacheGetAttr().

Referenced by mcv_clauselist_selectivity(), and statext_mcv_clauselist_selectivity().

statext_ndistinct_load()

MVNDistinct* statext_ndistinct_load	(	Oid	mvoid,
		bool	inh
	)

Definition at line 149 of file mvdistinct.c.

{
    MVNDistinct *result;
    bool        isnull;
    Datum       ndist;
    HeapTuple   htup;
 
    htup = SearchSysCache2(STATEXTDATASTXOID,
                           ObjectIdGetDatum(mvoid), BoolGetDatum(inh));
    if (!HeapTupleIsValid(htup))
        elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
 
    ndist = SysCacheGetAttr(STATEXTDATASTXOID, htup,
                            Anum_pg_statistic_ext_data_stxdndistinct, &isnull);
    if (isnull)
        elog(ERROR,
             "requested statistics kind \"%c\" is not yet built for statistics object %u",
             STATS_EXT_NDISTINCT, mvoid);
 
    result = statext_ndistinct_deserialize(DatumGetByteaPP(ndist));
 
    ReleaseSysCache(htup);
 
    return result;
}

References BoolGetDatum(), DatumGetByteaPP, elog(), ERROR, HeapTupleIsValid, ObjectIdGetDatum(), ReleaseSysCache(), SearchSysCache2(), statext_ndistinct_deserialize(), STATEXTDATASTXOID, and SysCacheGetAttr().

Referenced by estimate_multivariate_ndistinct().