extended_stats.c File Reference

#include "postgres.h"
#include "access/detoast.h"
#include "access/genam.h"
#include "access/htup_details.h"
#include "access/table.h"
#include "catalog/indexing.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_statistic_ext.h"
#include "catalog/pg_statistic_ext_data.h"
#include "commands/progress.h"
#include "miscadmin.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/optimizer.h"
#include "pgstat.h"
#include "postmaster/autovacuum.h"
#include "statistics/extended_stats_internal.h"
#include "statistics/statistics.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"

Include dependency graph for extended_stats.c:

Go to the source code of this file.

Data Structures
struct	StatExtEntry

Macros
#define	WIDTH_THRESHOLD   1024

Typedefs
typedef struct StatExtEntry	StatExtEntry

Functions
static List *	fetch_statentries_for_relation (Relation pg_statext, Oid relid)
static VacAttrStats **	lookup_var_attr_stats (Relation rel, Bitmapset *attrs, int nvacatts, VacAttrStats **vacatts)
static void	statext_store (Oid relid, MVNDistinct *ndistinct, MVDependencies *dependencies, MCVList *mcv, VacAttrStats **stats)
static int	statext_compute_stattarget (int stattarget, int natts, VacAttrStats **stats)
void	BuildRelationExtStatistics (Relation onerel, 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)
MultiSortSupport	multi_sort_init (int ndims)
void	multi_sort_add_dimension (MultiSortSupport mss, int sortdim, Oid oper, Oid collation)
int	multi_sort_compare (const void *a, const void *b, void *arg)
int	multi_sort_compare_dim (int dim, const SortItem *a, const SortItem *b, MultiSortSupport mss)
int	multi_sort_compare_dims (int start, int end, const SortItem *a, const SortItem *b, MultiSortSupport mss)
int	compare_scalars_simple (const void *a, const void *b, void *arg)
int	compare_datums_simple (Datum a, Datum b, SortSupport ssup)
void *	bsearch_arg (const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
AttrNumber *	build_attnums_array (Bitmapset *attrs, int *numattrs)
SortItem *	build_sorted_items (int numrows, int *nitems, HeapTuple *rows, TupleDesc tdesc, MultiSortSupport mss, int numattrs, AttrNumber *attnums)
bool	has_stats_of_kind (List *stats, char requiredkind)
StatisticExtInfo *	choose_best_statistics (List *stats, char requiredkind, Bitmapset **clause_attnums, int nclauses)
static bool	statext_is_compatible_clause_internal (PlannerInfo *root, Node *clause, Index relid, Bitmapset **attnums)
static bool	statext_is_compatible_clause (PlannerInfo *root, Node *clause, Index relid, Bitmapset **attnums)
static Selectivity	statext_mcv_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	examine_opclause_expression (OpExpr *expr, Var **varp, Const **cstp, bool *varonleftp)

Macro Definition Documentation

WIDTH_THRESHOLD

#define WIDTH_THRESHOLD   1024

Definition at line 54 of file extended_stats.c.

Referenced by build_sorted_items().

Typedef Documentation

StatExtEntry

typedef struct StatExtEntry StatExtEntry

Function Documentation

bsearch_arg()

void* bsearch_arg	(	const void *	key,
		const void *	base,
		size_t	nmemb,
		size_t	size,
		int(*)(const void *, const void *, void *)	compar,
		void *	arg
	)

Definition at line 663 of file extended_stats.c.

References arg, idx(), and sort-test::key.

Referenced by statext_mcv_build(), and statext_mcv_serialize().

{
    size_t      l,
                u,
                idx;
    const void *p;
    int         comparison;

    l = 0;
    u = nmemb;
    while (l < u)
    {
        idx = (l + u) / 2;
        p = (void *) (((const char *) base) + (idx * size));
        comparison = (*compar) (key, p, arg);

        if (comparison < 0)
            u = idx;
        else if (comparison > 0)
            l = idx + 1;
        else
            return (void *) p;
    }

    return NULL;
}

build_attnums_array()

AttrNumber* build_attnums_array	(	Bitmapset *	attrs,
		int *	numattrs
	)

Definition at line 701 of file extended_stats.c.

References Assert, AttrNumberIsForUserDefinedAttr, bms_next_member(), bms_num_members(), i, MaxAttrNumber, and palloc().

Referenced by dependency_degree(), statext_dependencies_build(), and statext_mcv_build().

{
    int         i,
                j;
    AttrNumber *attnums;
    int         num = bms_num_members(attrs);

    if (numattrs)
        *numattrs = num;

    /* build attnums from the bitmapset */
    attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * num);
    i = 0;
    j = -1;
    while ((j = bms_next_member(attrs, j)) >= 0)
    {
        /*
         * Make sure the bitmap contains only user-defined attributes. As
         * bitmaps can't contain negative values, this can be violated in two
         * ways. Firstly, the bitmap might contain 0 as a member, and secondly
         * the integer value might be larger than MaxAttrNumber.
         */
        Assert(AttrNumberIsForUserDefinedAttr(j));
        Assert(j <= MaxAttrNumber);

        attnums[i++] = (AttrNumber) j;

        /* protect against overflows */
        Assert(i <= num);
    }

    return attnums;
}

build_sorted_items()

SortItem* build_sorted_items	(	int	numrows,
		int *	nitems,
		HeapTuple *	rows,
		TupleDesc	tdesc,
		MultiSortSupport	mss,
		int	numattrs,
		AttrNumber *	attnums
	)

Definition at line 743 of file extended_stats.c.

References Assert, attlen, heap_getattr, i, idx(), multi_sort_compare(), palloc0(), pfree(), PG_DETOAST_DATUM, PointerGetDatum, qsort_arg(), toast_raw_datum_size(), TupleDescAttr, value, values, and WIDTH_THRESHOLD.

Referenced by dependency_degree(), and statext_mcv_build().

{
    int         i,
                j,
                len,
                idx;
    int         nvalues = numrows * numattrs;

    SortItem   *items;
    Datum      *values;
    bool       *isnull;
    char       *ptr;

    /* Compute the total amount of memory we need (both items and values). */
    len = numrows * sizeof(SortItem) + nvalues * (sizeof(Datum) + sizeof(bool));

    /* Allocate the memory and split it into the pieces. */
    ptr = palloc0(len);

    /* items to sort */
    items = (SortItem *) ptr;
    ptr += numrows * sizeof(SortItem);

    /* values and null flags */
    values = (Datum *) ptr;
    ptr += nvalues * sizeof(Datum);

    isnull = (bool *) ptr;
    ptr += nvalues * sizeof(bool);

    /* make sure we consumed the whole buffer exactly */
    Assert((ptr - (char *) items) == len);

    /* fix the pointers to Datum and bool arrays */
    idx = 0;
    for (i = 0; i < numrows; i++)
    {
        bool        toowide = false;

        items[idx].values = &values[idx * numattrs];
        items[idx].isnull = &isnull[idx * numattrs];

        /* load the values/null flags from sample rows */
        for (j = 0; j < numattrs; j++)
        {
            Datum       value;
            bool        isnull;

            value = heap_getattr(rows[i], attnums[j], tdesc, &isnull);

            /*
             * If this is a varlena value, check if it's too wide and if yes
             * then skip the whole item. Otherwise detoast the value.
             *
             * XXX It may happen that we've already detoasted some preceding
             * values for the current item. We don't bother to cleanup those
             * on the assumption that those are small (below WIDTH_THRESHOLD)
             * and will be discarded at the end of analyze.
             */
            if ((!isnull) &&
                (TupleDescAttr(tdesc, attnums[j] - 1)->attlen == -1))
            {
                if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
                {
                    toowide = true;
                    break;
                }

                value = PointerGetDatum(PG_DETOAST_DATUM(value));
            }

            items[idx].values[j] = value;
            items[idx].isnull[j] = isnull;
        }

        if (toowide)
            continue;

        idx++;
    }

    /* store the actual number of items (ignoring the too-wide ones) */
    *nitems = idx;

    /* all items were too wide */
    if (idx == 0)
    {
        /* everything is allocated as a single chunk */
        pfree(items);
        return NULL;
    }

    /* do the sort, using the multi-sort */
    qsort_arg((void *) items, idx, sizeof(SortItem),
              multi_sort_compare, mss);

    return items;
}

BuildRelationExtStatistics()

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

Definition at line 88 of file extended_stats.c.

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert, bms_num_members(), StatExtEntry::columns, CurrentMemoryContext, ereport, errcode(), errmsg(), errtable(), fetch_statentries_for_relation(), get_namespace_name(), IsAutoVacuumWorkerProcess(), lfirst, lfirst_int, list_length(), lookup_var_attr_stats(), MemoryContextDelete(), MemoryContextSwitchTo(), StatExtEntry::name, 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, StatExtEntry::schema, stat, statext_compute_stattarget(), statext_dependencies_build(), statext_mcv_build(), statext_ndistinct_build(), statext_store(), StatExtEntry::statOid, STATS_MAX_DIMENSIONS, StatExtEntry::stattarget, table_close(), table_open(), StatExtEntry::types, val, and WARNING.

Referenced by do_analyze_rel().

{
    Relation    pg_stext;
    ListCell   *lc;
    List       *stats;
    MemoryContext cxt;
    MemoryContext oldcxt;
    int64       ext_cnt;

    cxt = AllocSetContextCreate(CurrentMemoryContext,
                                "BuildRelationExtStatistics",
                                ALLOCSET_DEFAULT_SIZES);
    oldcxt = MemoryContextSwitchTo(cxt);

    pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
    stats = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));

    /* report this phase */
    if (stats != NIL)
    {
        const int   index[] = {
            PROGRESS_ANALYZE_PHASE,
            PROGRESS_ANALYZE_EXT_STATS_TOTAL
        };
        const int64 val[] = {
            PROGRESS_ANALYZE_PHASE_COMPUTE_EXT_STATS,
            list_length(stats)
        };

        pgstat_progress_update_multi_param(2, index, val);
    }

    ext_cnt = 0;
    foreach(lc, stats)
    {
        StatExtEntry *stat = (StatExtEntry *) lfirst(lc);
        MVNDistinct *ndistinct = NULL;
        MVDependencies *dependencies = NULL;
        MCVList    *mcv = NULL;
        VacAttrStats **stats;
        ListCell   *lc2;
        int         stattarget;

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

        /* check allowed number of dimensions */
        Assert(bms_num_members(stat->columns) >= 2 &&
               bms_num_members(stat->columns) <= STATS_MAX_DIMENSIONS);

        /* compute statistics target for this statistics */
        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;

        /* 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, numrows, rows,
                                                    stat->columns, stats);
            else if (t == STATS_EXT_DEPENDENCIES)
                dependencies = statext_dependencies_build(numrows, rows,
                                                          stat->columns, stats);
            else if (t == STATS_EXT_MCV)
                mcv = statext_mcv_build(numrows, rows, stat->columns, stats,
                                        totalrows, stattarget);
        }

        /* store the statistics in the catalog */
        statext_store(stat->statOid, ndistinct, dependencies, mcv, stats);

        /* for reporting progress */
        pgstat_progress_update_param(PROGRESS_ANALYZE_EXT_STATS_COMPUTED,
                                     ++ext_cnt);
    }

    table_close(pg_stext, RowExclusiveLock);

    MemoryContextSwitchTo(oldcxt);
    MemoryContextDelete(cxt);
}

choose_best_statistics()

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

Definition at line 882 of file extended_stats.c.

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

Referenced by statext_mcv_clauselist_selectivity().

{
    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 = NULL;
        int         num_matched;
        int         numkeys;

        /* skip statistics that are not of the correct type */
        if (info->kind != requiredkind)
            continue;

        /*
         * Collect attributes in remaining (unestimated) clauses fully covered
         * by this statistic object.
         */
        for (i = 0; i < nclauses; i++)
        {
            /* ignore incompatible/estimated clauses */
            if (!clause_attnums[i])
                continue;

            /* ignore clauses that are not covered by this object */
            if (!bms_is_subset(clause_attnums[i], info->keys))
                continue;

            matched = bms_add_members(matched, clause_attnums[i]);
        }

        num_matched = bms_num_members(matched);
        bms_free(matched);

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

        /*
         * Use this object when it increases the number of matched clauses or
         * when it matches the same number of attributes 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;
}

compare_datums_simple()

int compare_datums_simple	(	Datum	a,
		Datum	b,
		SortSupport	ssup
	)

Definition at line 656 of file extended_stats.c.

References ApplySortComparator().

Referenced by compare_scalars_simple(), and statext_mcv_serialize().

{
    return ApplySortComparator(a, false, b, false, ssup);
}

compare_scalars_simple()

int compare_scalars_simple	(	const void *	a,
		const void *	b,
		void *	arg
	)

Definition at line 648 of file extended_stats.c.

References compare_datums_simple().

Referenced by statext_mcv_serialize().

{
    return compare_datums_simple(*(Datum *) a,
                                 *(Datum *) b,
                                 (SortSupport) arg);
}

ComputeExtStatisticsRows()

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

Definition at line 213 of file extended_stats.c.

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

Referenced by do_analyze_rel().

{
    Relation    pg_stext;
    ListCell   *lc;
    List       *lstats;
    MemoryContext cxt;
    MemoryContext oldcxt;
    int         result = 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 = stat->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,
                                      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);
}

examine_opclause_expression()

bool examine_opclause_expression	(	OpExpr *	expr,
		Var **	varp,
		Const **	cstp,
		bool *	varonleftp
	)

Definition at line 1398 of file extended_stats.c.

References arg, OpExpr::args, Assert, IsA, linitial, list_length(), and lsecond.

Referenced by mcv_get_match_bitmap(), and statext_is_compatible_clause_internal().

{
    Var    *var;
    Const  *cst;
    bool    varonleft;
    Node   *leftop,
           *rightop;

    /* enforced by statext_is_compatible_clause_internal */
    Assert(list_length(expr->args) == 2);

    leftop = linitial(expr->args);
    rightop = lsecond(expr->args);

    /* strip RelabelType from either side of the expression */
    if (IsA(leftop, RelabelType))
        leftop = (Node *) ((RelabelType *) leftop)->arg;

    if (IsA(rightop, RelabelType))
        rightop = (Node *) ((RelabelType *) rightop)->arg;

    if (IsA(leftop, Var) && IsA(rightop, Const))
    {
        var = (Var *) leftop;
        cst = (Const *) rightop;
        varonleft = true;
    }
    else if (IsA(leftop, Const) && IsA(rightop, Var))
    {
        var = (Var *) rightop;
        cst = (Const *) leftop;
        varonleft = false;
    }
    else
        return false;

    /* return pointers to the extracted parts if requested */
    if (varp)
        *varp = var;

    if (cstp)
        *cstp = cst;

    if (varonleftp)
        *varonleftp = varonleft;

    return true;
}

fetch_statentries_for_relation()

static List * fetch_statentries_for_relation ( Relation  pg_statext, Oid  relid  )

static

Definition at line 362 of file extended_stats.c.

References ARR_DATA_PTR, ARR_DIMS, ARR_ELEMTYPE, ARR_HASNULL, ARR_NDIM, Assert, bms_add_member(), BTEqualStrategyNumber, StatExtEntry::columns, DatumGetArrayTypeP, elog, ERROR, get_namespace_name(), GETSTRUCT, HeapTupleIsValid, i, lappend(), lappend_int(), StatExtEntry::name, NameStr, NIL, ObjectIdGetDatum, palloc0(), pstrdup(), ScanKeyInit(), StatExtEntry::schema, STATEXTOID, StatisticExtRelidIndexId, StatExtEntry::statOid, StatExtEntry::stattarget, SysCacheGetAttr(), systable_beginscan(), systable_endscan(), systable_getnext(), and StatExtEntry::types.

Referenced by BuildRelationExtStatistics(), and ComputeExtStatisticsRows().

{
    SysScanDesc scan;
    ScanKeyData skey;
    HeapTuple   htup;
    List       *result = NIL;

    /*
     * Prepare to scan pg_statistic_ext for entries having stxrelid = this
     * rel.
     */
    ScanKeyInit(&skey,
                Anum_pg_statistic_ext_stxrelid,
                BTEqualStrategyNumber, F_OIDEQ,
                ObjectIdGetDatum(relid));

    scan = systable_beginscan(pg_statext, StatisticExtRelidIndexId, true,
                              NULL, 1, &skey);

    while (HeapTupleIsValid(htup = systable_getnext(scan)))
    {
        StatExtEntry *entry;
        Datum       datum;
        bool        isnull;
        int         i;
        ArrayType  *arr;
        char       *enabled;
        Form_pg_statistic_ext staForm;

        entry = palloc0(sizeof(StatExtEntry));
        staForm = (Form_pg_statistic_ext) GETSTRUCT(htup);
        entry->statOid = staForm->oid;
        entry->schema = get_namespace_name(staForm->stxnamespace);
        entry->name = pstrdup(NameStr(staForm->stxname));
        entry->stattarget = staForm->stxstattarget;
        for (i = 0; i < staForm->stxkeys.dim1; i++)
        {
            entry->columns = bms_add_member(entry->columns,
                                            staForm->stxkeys.values[i]);
        }

        /* decode the stxkind char array into a list of chars */
        datum = SysCacheGetAttr(STATEXTOID, htup,
                                Anum_pg_statistic_ext_stxkind, &isnull);
        Assert(!isnull);
        arr = DatumGetArrayTypeP(datum);
        if (ARR_NDIM(arr) != 1 ||
            ARR_HASNULL(arr) ||
            ARR_ELEMTYPE(arr) != CHAROID)
            elog(ERROR, "stxkind is not a 1-D char array");
        enabled = (char *) ARR_DATA_PTR(arr);
        for (i = 0; i < ARR_DIMS(arr)[0]; i++)
        {
            Assert((enabled[i] == STATS_EXT_NDISTINCT) ||
                   (enabled[i] == STATS_EXT_DEPENDENCIES) ||
                   (enabled[i] == STATS_EXT_MCV));
            entry->types = lappend_int(entry->types, (int) enabled[i]);
        }

        result = lappend(result, entry);
    }

    systable_endscan(scan);

    return result;
}

has_stats_of_kind()

bool has_stats_of_kind	(	List *	stats,
		char	requiredkind
	)

Definition at line 848 of file extended_stats.c.

References StatisticExtInfo::kind, lfirst, and stat.

Referenced by dependencies_clauselist_selectivity(), and statext_mcv_clauselist_selectivity().

{
    ListCell   *l;

    foreach(l, stats)
    {
        StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);

        if (stat->kind == requiredkind)
            return true;
    }

    return false;
}

lookup_var_attr_stats()

static VacAttrStats ** lookup_var_attr_stats ( Relation  rel, Bitmapset *  attrs, int  nvacatts, VacAttrStats **  vacatts  )

static

Definition at line 437 of file extended_stats.c.

References Assert, bms_next_member(), bms_num_members(), i, palloc(), and pfree().

Referenced by BuildRelationExtStatistics(), and ComputeExtStatisticsRows().

{
    int         i = 0;
    int         x = -1;
    VacAttrStats **stats;

    stats = (VacAttrStats **)
        palloc(bms_num_members(attrs) * sizeof(VacAttrStats *));

    /* lookup VacAttrStats info for the requested columns (same attnum) */
    while ((x = bms_next_member(attrs, x)) >= 0)
    {
        int         j;

        stats[i] = NULL;
        for (j = 0; j < nvacatts; j++)
        {
            if (x == vacatts[j]->tupattnum)
            {
                stats[i] = vacatts[j];
                break;
            }
        }

        if (!stats[i])
        {
            /*
             * Looks like stats were not gathered for one of the columns
             * required. We'll be unable to build the extended stats without
             * this column.
             */
            pfree(stats);
            return NULL;
        }

        /*
         * Sanity check that the column is not dropped - stats should have
         * been removed in this case.
         */
        Assert(!stats[i]->attr->attisdropped);

        i++;
    }

    return stats;
}

multi_sort_add_dimension()

void multi_sort_add_dimension	(	MultiSortSupport	mss,
		int	sortdim,
		Oid	oper,
		Oid	collation
	)

Definition at line 580 of file extended_stats.c.

References CurrentMemoryContext, PrepareSortSupportFromOrderingOp(), MultiSortSupportData::ssup, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, and SortSupportData::ssup_nulls_first.

Referenced by build_mss(), dependency_degree(), and ndistinct_for_combination().

{
    SortSupport ssup = &mss->ssup[sortdim];

    ssup->ssup_cxt = CurrentMemoryContext;
    ssup->ssup_collation = collation;
    ssup->ssup_nulls_first = false;

    PrepareSortSupportFromOrderingOp(oper, ssup);
}

multi_sort_compare()

int multi_sort_compare	(	const void *	a,
		const void *	b,
		void *	arg
	)

Definition at line 594 of file extended_stats.c.

References ApplySortComparator(), compare(), i, SortItem::isnull, MultiSortSupportData::ndims, MultiSortSupportData::ssup, and SortItem::values.

Referenced by build_distinct_groups(), build_sorted_items(), count_distinct_groups(), ndistinct_for_combination(), and statext_mcv_build().

{
    MultiSortSupport mss = (MultiSortSupport) arg;
    SortItem   *ia = (SortItem *) a;
    SortItem   *ib = (SortItem *) b;
    int         i;

    for (i = 0; i < mss->ndims; i++)
    {
        int         compare;

        compare = ApplySortComparator(ia->values[i], ia->isnull[i],
                                      ib->values[i], ib->isnull[i],
                                      &mss->ssup[i]);

        if (compare != 0)
            return compare;
    }

    /* equal by default */
    return 0;
}

multi_sort_compare_dim()

int multi_sort_compare_dim	(	int	dim,
		const SortItem *	a,
		const SortItem *	b,
		MultiSortSupport	mss
	)

Definition at line 619 of file extended_stats.c.

References ApplySortComparator(), SortItem::isnull, MultiSortSupportData::ssup, and SortItem::values.

Referenced by dependency_degree().

{
    return ApplySortComparator(a->values[dim], a->isnull[dim],
                               b->values[dim], b->isnull[dim],
                               &mss->ssup[dim]);
}

multi_sort_compare_dims()

int multi_sort_compare_dims	(	int	start,
		int	end,
		const SortItem *	a,
		const SortItem *	b,
		MultiSortSupport	mss
	)

Definition at line 628 of file extended_stats.c.

References ApplySortComparator(), SortItem::isnull, MultiSortSupportData::ssup, and SortItem::values.

Referenced by dependency_degree().

{
    int         dim;

    for (dim = start; dim <= end; dim++)
    {
        int         r = ApplySortComparator(a->values[dim], a->isnull[dim],
                                            b->values[dim], b->isnull[dim],
                                            &mss->ssup[dim]);

        if (r != 0)
            return r;
    }

    return 0;
}

multi_sort_init()

MultiSortSupport multi_sort_init

(

int

ndims

)

Definition at line 561 of file extended_stats.c.

References Assert, MultiSortSupportData::ndims, offsetof, and palloc0().

Referenced by build_mss(), dependency_degree(), and ndistinct_for_combination().

{
    MultiSortSupport mss;

    Assert(ndims >= 2);

    mss = (MultiSortSupport) palloc0(offsetof(MultiSortSupportData, ssup)
                                     + sizeof(SortSupportData) * ndims);

    mss->ndims = ndims;

    return mss;
}

statext_clauselist_selectivity()

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

Definition at line 1355 of file extended_stats.c.

References dependencies_clauselist_selectivity(), and statext_mcv_clauselist_selectivity().

Referenced by clauselist_selectivity().

{
    Selectivity sel;

    /* First, try estimating clauses using a multivariate MCV list. */
    sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
                                             sjinfo, rel, estimatedclauses);

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

statext_compute_stattarget()

static int statext_compute_stattarget ( int  stattarget, int  natts, VacAttrStats **  stats  )

static

Definition at line 291 of file extended_stats.c.

References Assert, VacAttrStats::attr, default_statistics_target, i, and StatExtEntry::stattarget.

Referenced by BuildRelationExtStatistics(), and ComputeExtStatisticsRows().

{
    int i;

    /*
     * If there's statistics target set for the statistics object, use it.
     * It may be set to 0 which disables building of that statistic.
     */
    if (stattarget >= 0)
        return stattarget;

    /*
     * The target for the statistics object is set to -1, in which case we
     * look at the maximum target set for any of the attributes the object
     * is defined on.
     */
    for (i = 0; i < nattrs; i++)
    {
        /* keep the maximmum statistics target */
        if (stats[i]->attr->attstattarget > stattarget)
            stattarget = stats[i]->attr->attstattarget;
    }

    /*
     * If the value is still negative (so neither the statistics object nor
     * any of the columns have custom statistics target set), use the global
     * default target.
     */
    if (stattarget < 0)
        stattarget = default_statistics_target;

    /* As this point we should have a valid statistics target. */
    Assert((stattarget >= 0) && (stattarget <= 10000));

    return stattarget;
}

statext_is_compatible_clause()

static bool statext_is_compatible_clause ( PlannerInfo *  root, Node *  clause, Index  relid, Bitmapset **  attnums  )

static

Definition at line 1113 of file extended_stats.c.

References ACL_SELECT, ACLCHECK_OK, ACLMASK_ALL, attnum, bms_is_member(), bms_membership(), bms_next_member(), BMS_SINGLETON, RangeTblEntry::checkAsUser, RestrictInfo::clause, RestrictInfo::clause_relids, GetUserId(), InvalidAttrNumber, IsA, pg_attribute_aclcheck(), pg_attribute_aclcheck_all(), pg_class_aclcheck(), RestrictInfo::pseudoconstant, RangeTblEntry::relid, PlannerInfo::simple_rte_array, and statext_is_compatible_clause_internal().

Referenced by statext_mcv_clauselist_selectivity().

{
    RangeTblEntry *rte = root->simple_rte_array[relid];
    RestrictInfo *rinfo = (RestrictInfo *) clause;
    Oid         userid;

    if (!IsA(rinfo, RestrictInfo))
        return false;

    /* Pseudoconstants are not really interesting here. */
    if (rinfo->pseudoconstant)
        return false;

    /* clauses referencing multiple varnos are incompatible */
    if (bms_membership(rinfo->clause_relids) != BMS_SINGLETON)
        return false;

    /* Check the clause and determine what attributes it references. */
    if (!statext_is_compatible_clause_internal(root, (Node *) rinfo->clause,
                                               relid, attnums))
        return false;

    /*
     * Check that the user has permission to read all these attributes.  Use
     * checkAsUser if it's set, in case we're accessing the table via a view.
     */
    userid = rte->checkAsUser ? rte->checkAsUser : GetUserId();

    if (pg_class_aclcheck(rte->relid, userid, ACL_SELECT) != ACLCHECK_OK)
    {
        /* Don't have table privilege, must check individual columns */
        if (bms_is_member(InvalidAttrNumber, *attnums))
        {
            /* Have a whole-row reference, must have access to all columns */
            if (pg_attribute_aclcheck_all(rte->relid, userid, ACL_SELECT,
                                          ACLMASK_ALL) != ACLCHECK_OK)
                return false;
        }
        else
        {
            /* Check the columns referenced by the clause */
            int         attnum = -1;

            while ((attnum = bms_next_member(*attnums, attnum)) >= 0)
            {
                if (pg_attribute_aclcheck(rte->relid, attnum, userid,
                                          ACL_SELECT) != ACLCHECK_OK)
                    return false;
            }
        }
    }

    /* If we reach here, the clause is OK */
    return true;
}

statext_is_compatible_clause_internal()

static bool statext_is_compatible_clause_internal ( PlannerInfo *  root, Node *  clause, Index  relid, Bitmapset **  attnums  )

static

Definition at line 955 of file extended_stats.c.

References arg, NullTest::arg, OpExpr::args, BoolExpr::args, AttrNumberIsForUserDefinedAttr, bms_add_member(), examine_opclause_expression(), get_func_leakproof(), get_opcode(), get_oprrest(), is_andclause(), is_notclause(), is_opclause(), is_orclause(), IsA, lfirst, list_length(), NIL, OpExpr::opno, RangeTblEntry::securityQuals, PlannerInfo::simple_rte_array, Var::varattno, Var::varlevelsup, and Var::varno.

Referenced by statext_is_compatible_clause().

{
    /* Look inside any binary-compatible relabeling (as in examine_variable) */
    if (IsA(clause, RelabelType))
        clause = (Node *) ((RelabelType *) clause)->arg;

    /* plain Var references (boolean Vars or recursive checks) */
    if (IsA(clause, Var))
    {
        Var        *var = (Var *) clause;

        /* Ensure var is from the correct relation */
        if (var->varno != relid)
            return false;

        /* we also better ensure the Var is from the current level */
        if (var->varlevelsup > 0)
            return false;

        /* Also skip system attributes (we don't allow stats on those). */
        if (!AttrNumberIsForUserDefinedAttr(var->varattno))
            return false;

        *attnums = bms_add_member(*attnums, var->varattno);

        return true;
    }

    /* (Var op Const) or (Const op Var) */
    if (is_opclause(clause))
    {
        RangeTblEntry *rte = root->simple_rte_array[relid];
        OpExpr     *expr = (OpExpr *) clause;
        Var        *var;

        /* Only expressions with two arguments are considered compatible. */
        if (list_length(expr->args) != 2)
            return false;

        /* Check if the expression the right shape (one Var, one Const) */
        if (!examine_opclause_expression(expr, &var, NULL, NULL))
            return false;

        /*
         * If it's not one of the supported operators ("=", "<", ">", etc.),
         * just ignore the clause, as it's not compatible with MCV lists.
         *
         * This uses the function for estimating selectivity, not the operator
         * directly (a bit awkward, but well ...).
         */
        switch (get_oprrest(expr->opno))
        {
            case F_EQSEL:
            case F_NEQSEL:
            case F_SCALARLTSEL:
            case F_SCALARLESEL:
            case F_SCALARGTSEL:
            case F_SCALARGESEL:
                /* supported, will continue with inspection of the Var */
                break;

            default:
                /* other estimators are considered unknown/unsupported */
                return false;
        }

        /*
         * If there are any securityQuals on the RTE from security barrier
         * views or RLS policies, then the user may not have access to all the
         * table's data, and we must check that the operator is leak-proof.
         *
         * If the operator is leaky, then we must ignore this clause for the
         * purposes of estimating with MCV lists, otherwise the operator might
         * reveal values from the MCV list that the user doesn't have
         * permission to see.
         */
        if (rte->securityQuals != NIL &&
            !get_func_leakproof(get_opcode(expr->opno)))
            return false;

        return statext_is_compatible_clause_internal(root, (Node *) var,
                                                     relid, attnums);
    }

    /* AND/OR/NOT clause */
    if (is_andclause(clause) ||
        is_orclause(clause) ||
        is_notclause(clause))
    {
        /*
         * AND/OR/NOT-clauses are supported if all sub-clauses are supported
         *
         * Perhaps we could improve this by handling mixed cases, when some of
         * the clauses are supported and some are not. Selectivity for the
         * supported subclauses would be computed using extended statistics,
         * and the remaining clauses would be estimated using the traditional
         * algorithm (product of selectivities).
         *
         * It however seems overly complex, and in a way we already do that
         * because if we reject the whole clause as unsupported here, it will
         * be eventually passed to clauselist_selectivity() which does exactly
         * this (split into supported/unsupported clauses etc).
         */
        BoolExpr   *expr = (BoolExpr *) clause;
        ListCell   *lc;

        foreach(lc, expr->args)
        {
            /*
             * Had we found incompatible clause in the arguments, treat the
             * whole clause as incompatible.
             */
            if (!statext_is_compatible_clause_internal(root,
                                                       (Node *) lfirst(lc),
                                                       relid, attnums))
                return false;
        }

        return true;
    }

    /* Var IS NULL */
    if (IsA(clause, NullTest))
    {
        NullTest   *nt = (NullTest *) clause;

        /*
         * Only simple (Var IS NULL) expressions supported for now. Maybe we
         * could use examine_variable to fix this?
         */
        if (!IsA(nt->arg, Var))
            return false;

        return statext_is_compatible_clause_internal(root, (Node *) (nt->arg),
                                                     relid, attnums);
    }

    return false;
}

statext_is_kind_built()

bool statext_is_kind_built	(	HeapTuple	htup,
		char	type
	)

Definition at line 333 of file extended_stats.c.

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

Referenced by get_relation_statistics(), and UpdateStatisticsForTypeChange().

{
    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;

        default:
            elog(ERROR, "unexpected statistics type requested: %d", type);
    }

    return !heap_attisnull(htup, attnum, NULL);
}

statext_mcv_clauselist_selectivity()

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

static

Definition at line 1226 of file extended_stats.c.

References Assert, bms_add_member(), bms_free(), bms_is_member(), bms_is_subset(), choose_best_statistics(), CLAMP_PROBABILITY, clauselist_selectivity_simple(), has_stats_of_kind(), StatisticExtInfo::keys, StatisticExtInfo::kind, lappend(), lfirst, list_length(), mcv_clauselist_selectivity(), NIL, palloc(), RelOptInfo::relid, stat, statext_is_compatible_clause(), and RelOptInfo::statlist.

Referenced by statext_clauselist_selectivity().

{
    ListCell   *l;
    Bitmapset **list_attnums;
    int         listidx;
    Selectivity sel = 1.0;

    /* check if there's any stats that might be useful for us. */
    if (!has_stats_of_kind(rel->statlist, STATS_EXT_MCV))
        return 1.0;

    list_attnums = (Bitmapset **) palloc(sizeof(Bitmapset *) *
                                         list_length(clauses));

    /*
     * 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
     * selectivity estimations with extended stats. 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).
     */
    listidx = 0;
    foreach(l, clauses)
    {
        Node       *clause = (Node *) lfirst(l);
        Bitmapset  *attnums = NULL;

        if (!bms_is_member(listidx, *estimatedclauses) &&
            statext_is_compatible_clause(root, clause, rel->relid, &attnums))
            list_attnums[listidx] = attnums;
        else
            list_attnums[listidx] = NULL;

        listidx++;
    }

    /* apply as many extended statistics as possible */
    while (true)
    {
        StatisticExtInfo *stat;
        List       *stat_clauses;
        Selectivity simple_sel,
                    mcv_sel,
                    mcv_basesel,
                    mcv_totalsel,
                    other_sel,
                    stat_sel;

        /* find the best suited statistics object for these attnums */
        stat = choose_best_statistics(rel->statlist, STATS_EXT_MCV,
                                      list_attnums, list_length(clauses));

        /* if no (additional) matching stats could be found then we've nothing to do */
        if (!stat)
            break;

        /* Ensure choose_best_statistics produced an expected stats type. */
        Assert(stat->kind == STATS_EXT_MCV);

        /* now filter the clauses to be estimated using the selected MCV */
        stat_clauses = NIL;

        listidx = 0;
        foreach(l, clauses)
        {
            /*
             * If the clause is compatible with the selected statistics, mark it
             * as estimated and add it to the list to estimate.
             */
            if (list_attnums[listidx] != NULL &&
                bms_is_subset(list_attnums[listidx], stat->keys))
            {
                stat_clauses = lappend(stat_clauses, (Node *) lfirst(l));
                *estimatedclauses = bms_add_member(*estimatedclauses, listidx);

                bms_free(list_attnums[listidx]);
                list_attnums[listidx] = NULL;
            }

            listidx++;
        }

        /*
         * First compute "simple" selectivity, i.e. without the extended
         * statistics, and essentially assuming independence of the
         * columns/clauses. We'll then use the various selectivities computed from
         * MCV list to improve it.
         */
        simple_sel = clauselist_selectivity_simple(root, stat_clauses, varRelid,
                                                jointype, sjinfo, NULL);

        /*
         * Now compute the multi-column estimate from the MCV list, along with the
         * other selectivities (base & total selectivity).
         */
        mcv_sel = mcv_clauselist_selectivity(root, stat, stat_clauses, varRelid,
                                             jointype, sjinfo, rel,
                                             &mcv_basesel, &mcv_totalsel);

        /* Estimated selectivity of values not covered by MCV matches */
        other_sel = simple_sel - mcv_basesel;
        CLAMP_PROBABILITY(other_sel);

        /* The non-MCV selectivity can't exceed the 1 - mcv_totalsel. */
        if (other_sel > 1.0 - mcv_totalsel)
            other_sel = 1.0 - mcv_totalsel;

        /* Overall selectivity is the combination of MCV and non-MCV estimates. */
        stat_sel = mcv_sel + other_sel;
        CLAMP_PROBABILITY(stat_sel);

        /* Factor the estimate from this MCV to the oveall estimate. */
        sel *= stat_sel;
    }

    return sel;
}

statext_store()

static void statext_store ( Oid  relid, MVNDistinct *  ndistinct, MVDependencies *  dependencies, MCVList *  mcv, VacAttrStats **  stats  )

static

Definition at line 491 of file extended_stats.c.

References CatalogTupleUpdate(), elog, ERROR, heap_freetuple(), heap_modify_tuple(), HeapTupleIsValid, ObjectIdGetDatum, PointerGetDatum, RelationGetDescr, ReleaseSysCache(), RowExclusiveLock, SearchSysCache1(), statext_dependencies_serialize(), statext_mcv_serialize(), statext_ndistinct_serialize(), STATEXTDATASTXOID, HeapTupleData::t_self, table_close(), table_open(), and values.

Referenced by BuildRelationExtStatistics().

{
    HeapTuple   stup,
                oldtup;
    Datum       values[Natts_pg_statistic_ext_data];
    bool        nulls[Natts_pg_statistic_ext_data];
    bool        replaces[Natts_pg_statistic_ext_data];
    Relation    pg_stextdata;

    memset(nulls, true, sizeof(nulls));
    memset(replaces, false, sizeof(replaces));
    memset(values, 0, sizeof(values));

    /*
     * Construct a new pg_statistic_ext_data tuple, replacing the calculated
     * stats.
     */
    if (ndistinct != NULL)
    {
        bytea      *data = statext_ndistinct_serialize(ndistinct);

        nulls[Anum_pg_statistic_ext_data_stxdndistinct - 1] = (data == NULL);
        values[Anum_pg_statistic_ext_data_stxdndistinct - 1] = PointerGetDatum(data);
    }

    if (dependencies != NULL)
    {
        bytea      *data = statext_dependencies_serialize(dependencies);

        nulls[Anum_pg_statistic_ext_data_stxddependencies - 1] = (data == NULL);
        values[Anum_pg_statistic_ext_data_stxddependencies - 1] = PointerGetDatum(data);
    }
    if (mcv != NULL)
    {
        bytea      *data = statext_mcv_serialize(mcv, stats);

        nulls[Anum_pg_statistic_ext_data_stxdmcv - 1] = (data == NULL);
        values[Anum_pg_statistic_ext_data_stxdmcv - 1] = PointerGetDatum(data);
    }

    /* always replace the value (either by bytea or NULL) */
    replaces[Anum_pg_statistic_ext_data_stxdndistinct - 1] = true;
    replaces[Anum_pg_statistic_ext_data_stxddependencies - 1] = true;
    replaces[Anum_pg_statistic_ext_data_stxdmcv - 1] = true;

    /* there should already be a pg_statistic_ext_data tuple */
    oldtup = SearchSysCache1(STATEXTDATASTXOID, ObjectIdGetDatum(statOid));
    if (!HeapTupleIsValid(oldtup))
        elog(ERROR, "cache lookup failed for statistics object %u", statOid);

    /* replace it */
    pg_stextdata = table_open(StatisticExtDataRelationId, RowExclusiveLock);

    stup = heap_modify_tuple(oldtup,
                             RelationGetDescr(pg_stextdata),
                             values,
                             nulls,
                             replaces);
    ReleaseSysCache(oldtup);
    CatalogTupleUpdate(pg_stextdata, &stup->t_self, stup);

    heap_freetuple(stup);

    table_close(pg_stextdata, RowExclusiveLock);
}