mcv.c File Reference

#include "postgres.h"
#include <math.h>
#include "access/htup_details.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_statistic_ext.h"
#include "catalog/pg_statistic_ext_data.h"
#include "fmgr.h"
#include "funcapi.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "statistics/extended_stats_internal.h"
#include "statistics/statistics.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/bytea.h"
#include "utils/fmgroids.h"
#include "utils/fmgrprotos.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"
#include "utils/typcache.h"

Include dependency graph for mcv.c:

Go to the source code of this file.

Macros
#define	ITEM_SIZE(ndims)    ((ndims) * (sizeof(uint16) + sizeof(bool)) + 2 * sizeof(double))
#define	MinSizeOfMCVList    (VARHDRSZ + sizeof(uint32) * 3 + sizeof(AttrNumber))
#define	SizeOfMCVList(ndims, nitems)
#define	RESULT_MERGE(value, is_or, match)    ((is_or) ? ((value) || (match)) : ((value) && (match)))
#define	RESULT_IS_FINAL(value, is_or)   ((is_or) ? (value) : (!(value)))

Functions
static MultiSortSupport	build_mss (StatsBuildData *data)
static SortItem *	build_distinct_groups (int numrows, SortItem *items, MultiSortSupport mss, int *ndistinct)
static SortItem **	build_column_frequencies (SortItem *groups, int ngroups, MultiSortSupport mss, int *ncounts)
static int	count_distinct_groups (int numrows, SortItem *items, MultiSortSupport mss)
static double	get_mincount_for_mcv_list (int samplerows, double totalrows)
MCVList *	statext_mcv_build (StatsBuildData *data, double totalrows, int stattarget)
static int	compare_sort_item_count (const void *a, const void *b, void *arg)
static int	sort_item_compare (const void *a, const void *b, void *arg)
MCVList *	statext_mcv_load (Oid mvoid, bool inh)
bytea *	statext_mcv_serialize (MCVList *mcvlist, VacAttrStats **stats)
MCVList *	statext_mcv_deserialize (bytea *data)
Datum	pg_stats_ext_mcvlist_items (PG_FUNCTION_ARGS)
Datum	pg_mcv_list_in (PG_FUNCTION_ARGS)
Datum	pg_mcv_list_out (PG_FUNCTION_ARGS)
Datum	pg_mcv_list_recv (PG_FUNCTION_ARGS)
Datum	pg_mcv_list_send (PG_FUNCTION_ARGS)
static int	mcv_match_expression (Node *expr, Bitmapset *keys, List *exprs, Oid *collid)
static bool *	mcv_get_match_bitmap (PlannerInfo *root, List *clauses, Bitmapset *keys, List *exprs, MCVList *mcvlist, bool is_or)
Selectivity	mcv_combine_selectivities (Selectivity simple_sel, Selectivity mcv_sel, Selectivity mcv_basesel, Selectivity mcv_totalsel)
Selectivity	mcv_clauselist_selectivity (PlannerInfo *root, StatisticExtInfo *stat, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Selectivity *basesel, Selectivity *totalsel)
Selectivity	mcv_clause_selectivity_or (PlannerInfo *root, StatisticExtInfo *stat, MCVList *mcv, Node *clause, bool **or_matches, Selectivity *basesel, Selectivity *overlap_mcvsel, Selectivity *overlap_basesel, Selectivity *totalsel)

Macro Definition Documentation

ITEM_SIZE

#define ITEM_SIZE

(

ndims

)

((ndims) * (sizeof(uint16) + sizeof(bool)) + 2 * sizeof(double))

Definition at line 57 of file mcv.c.

MinSizeOfMCVList

#define MinSizeOfMCVList    (VARHDRSZ + sizeof(uint32) * 3 + sizeof(AttrNumber))

Definition at line 63 of file mcv.c.

RESULT_IS_FINAL

#define RESULT_IS_FINAL	(		value,
			is_or
	)		((is_or) ? (value) : (!(value)))

Definition at line 104 of file mcv.c.

RESULT_MERGE

#define RESULT_MERGE	(		value,
			is_or,
			match
	)		((is_or) ? ((value) || (match)) : ((value) && (match)))

Definition at line 92 of file mcv.c.

SizeOfMCVList

#define SizeOfMCVList	(		ndims,
			nitems
	)

Value:

    ((MinSizeOfMCVList + sizeof(Oid) * (ndims)) + \
     ((ndims) * sizeof(DimensionInfo)) + \
     ((nitems) * ITEM_SIZE(ndims)))

Definition at line 72 of file mcv.c.

Function Documentation

build_column_frequencies()

static SortItem ** build_column_frequencies ( SortItem *  groups, int  ngroups, MultiSortSupport  mss, int *  ncounts  )

static

Definition at line 494 of file mcv.c.

{
    int         i,
                dim;
    SortItem  **result;
    char       *ptr;
 
    Assert(groups);
    Assert(ncounts);
 
    /* allocate arrays for all columns as a single chunk */
    ptr = palloc(MAXALIGN(sizeof(SortItem *) * mss->ndims) +
                 mss->ndims * MAXALIGN(sizeof(SortItem) * ngroups));
 
    /* initial array of pointers */
    result = (SortItem **) ptr;
    ptr += MAXALIGN(sizeof(SortItem *) * mss->ndims);
 
    for (dim = 0; dim < mss->ndims; dim++)
    {
        SortSupport ssup = &mss->ssup[dim];
 
        /* array of values for a single column */
        result[dim] = (SortItem *) ptr;
        ptr += MAXALIGN(sizeof(SortItem) * ngroups);
 
        /* extract data for the dimension */
        for (i = 0; i < ngroups; i++)
        {
            /* point into the input groups */
            result[dim][i].values = &groups[i].values[dim];
            result[dim][i].isnull = &groups[i].isnull[dim];
            result[dim][i].count = groups[i].count;
        }
 
        /* sort the values, deduplicate */
        qsort_interruptible(result[dim], ngroups, sizeof(SortItem),
                            sort_item_compare, ssup);
 
        /*
         * Identify distinct values, compute frequency (there might be
         * multiple MCV items containing this value, so we need to sum counts
         * from all of them.
         */
        ncounts[dim] = 1;
        for (i = 1; i < ngroups; i++)
        {
            if (sort_item_compare(&result[dim][i - 1], &result[dim][i], ssup) == 0)
            {
                result[dim][ncounts[dim] - 1].count += result[dim][i].count;
                continue;
            }
 
            result[dim][ncounts[dim]] = result[dim][i];
 
            ncounts[dim]++;
        }
    }
 
    return result;
}

References Assert(), SortItem::count, i, SortItem::isnull, MAXALIGN, MultiSortSupportData::ndims, palloc(), qsort_interruptible(), sort_item_compare(), MultiSortSupportData::ssup, and SortItem::values.

Referenced by statext_mcv_build().

build_distinct_groups()

static SortItem * build_distinct_groups ( int  numrows, SortItem *  items, MultiSortSupport  mss, int *  ndistinct  )

static

Definition at line 428 of file mcv.c.

{
    int         i,
                j;
    int         ngroups = count_distinct_groups(numrows, items, mss);
 
    SortItem   *groups = (SortItem *) palloc(ngroups * sizeof(SortItem));
 
    j = 0;
    groups[0] = items[0];
    groups[0].count = 1;
 
    for (i = 1; i < numrows; i++)
    {
        /* Assume sorted in ascending order. */
        Assert(multi_sort_compare(&items[i], &items[i - 1], mss) >= 0);
 
        /* New distinct group detected. */
        if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
        {
            groups[++j] = items[i];
            groups[j].count = 0;
        }
 
        groups[j].count++;
    }
 
    /* ensure we filled the expected number of distinct groups */
    Assert(j + 1 == ngroups);
 
    /* Sort the distinct groups by frequency (in descending order). */
    qsort_interruptible(groups, ngroups, sizeof(SortItem),
                        compare_sort_item_count, NULL);
 
    *ndistinct = ngroups;
    return groups;
}

References Assert(), compare_sort_item_count(), SortItem::count, count_distinct_groups(), i, j, multi_sort_compare(), palloc(), and qsort_interruptible().

Referenced by statext_mcv_build().

build_mss()

static MultiSortSupport build_mss ( StatsBuildData *  data )

static

Definition at line 351 of file mcv.c.

{
    int         i;
    int         numattrs = data->nattnums;
 
    /* Sort by multiple columns (using array of SortSupport) */
    MultiSortSupport mss = multi_sort_init(numattrs);
 
    /* prepare the sort functions for all the attributes */
    for (i = 0; i < numattrs; i++)
    {
        VacAttrStats *colstat = data->stats[i];
        TypeCacheEntry *type;
 
        type = lookup_type_cache(colstat->attrtypid, TYPECACHE_LT_OPR);
        if (type->lt_opr == InvalidOid) /* shouldn't happen */
            elog(ERROR, "cache lookup failed for ordering operator for type %u",
                 colstat->attrtypid);
 
        multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
    }
 
    return mss;
}

References VacAttrStats::attrcollid, VacAttrStats::attrtypid, data, elog(), ERROR, i, InvalidOid, lookup_type_cache(), multi_sort_add_dimension(), multi_sort_init(), type, and TYPECACHE_LT_OPR.

Referenced by statext_mcv_build().

compare_sort_item_count()

static int compare_sort_item_count ( const void *  a, const void *  b, void *  arg  )

static

Definition at line 407 of file mcv.c.

{
    SortItem   *ia = (SortItem *) a;
    SortItem   *ib = (SortItem *) b;
 
    if (ia->count == ib->count)
        return 0;
    else if (ia->count > ib->count)
        return -1;
 
    return 1;
}

References a, b, and SortItem::count.

Referenced by build_distinct_groups().

count_distinct_groups()

static int count_distinct_groups ( int  numrows, SortItem *  items, MultiSortSupport  mss  )

static

Definition at line 383 of file mcv.c.

{
    int         i;
    int         ndistinct;
 
    ndistinct = 1;
    for (i = 1; i < numrows; i++)
    {
        /* make sure the array really is sorted */
        Assert(multi_sort_compare(&items[i], &items[i - 1], mss) >= 0);
 
        if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
            ndistinct += 1;
    }
 
    return ndistinct;
}

References Assert(), i, and multi_sort_compare().

Referenced by build_distinct_groups().

get_mincount_for_mcv_list()

static double get_mincount_for_mcv_list ( int  samplerows, double  totalrows  )

static

Definition at line 152 of file mcv.c.

{
    double      n = samplerows;
    double      N = totalrows;
    double      numer,
                denom;
 
    numer = n * (N - n);
    denom = N - n + 0.04 * n * (N - 1);
 
    /* Guard against division by zero (possible if n = N = 1) */
    if (denom == 0.0)
        return 0.0;
 
    return numer / denom;
}

Referenced by statext_mcv_build().

mcv_clause_selectivity_or()

Selectivity mcv_clause_selectivity_or	(	PlannerInfo *	root,
		StatisticExtInfo *	stat,
		MCVList *	mcv,
		Node *	clause,
		bool **	or_matches,
		Selectivity *	basesel,
		Selectivity *	overlap_mcvsel,
		Selectivity *	overlap_basesel,
		Selectivity *	totalsel
	)

Definition at line 2130 of file mcv.c.

{
    Selectivity s = 0.0;
    bool       *new_matches;
    int         i;
 
    /* build the OR-matches bitmap, if not built already */
    if (*or_matches == NULL)
        *or_matches = palloc0(sizeof(bool) * mcv->nitems);
 
    /* build the match bitmap for the new clause */
    new_matches = mcv_get_match_bitmap(root, list_make1(clause), stat->keys,
                                       stat->exprs, mcv, false);
 
    /*
     * Sum the frequencies for all the MCV items matching this clause and also
     * those matching the overlap between this clause and any of the preceding
     * clauses as described above.
     */
    *basesel = 0.0;
    *overlap_mcvsel = 0.0;
    *overlap_basesel = 0.0;
    *totalsel = 0.0;
    for (i = 0; i < mcv->nitems; i++)
    {
        *totalsel += mcv->items[i].frequency;
 
        if (new_matches[i])
        {
            s += mcv->items[i].frequency;
            *basesel += mcv->items[i].base_frequency;
 
            if ((*or_matches)[i])
            {
                *overlap_mcvsel += mcv->items[i].frequency;
                *overlap_basesel += mcv->items[i].base_frequency;
            }
        }
 
        /* update the OR-matches bitmap for the next clause */
        (*or_matches)[i] = (*or_matches)[i] || new_matches[i];
    }
 
    pfree(new_matches);
 
    return s;
}

References MCVItem::base_frequency, MCVItem::frequency, i, MCVList::items, list_make1, mcv_get_match_bitmap(), MCVList::nitems, palloc0(), and pfree().

Referenced by statext_mcv_clauselist_selectivity().

mcv_clauselist_selectivity()

Selectivity mcv_clauselist_selectivity	(	PlannerInfo *	root,
		StatisticExtInfo *	stat,
		List *	clauses,
		int	varRelid,
		JoinType	jointype,
		SpecialJoinInfo *	sjinfo,
		RelOptInfo *	rel,
		Selectivity *	basesel,
		Selectivity *	totalsel
	)

Definition at line 2052 of file mcv.c.

{
    int         i;
    MCVList    *mcv;
    Selectivity s = 0.0;
    RangeTblEntry *rte = root->simple_rte_array[rel->relid];
 
    /* match/mismatch bitmap for each MCV item */
    bool       *matches = NULL;
 
    /* load the MCV list stored in the statistics object */
    mcv = statext_mcv_load(stat->statOid, rte->inh);
 
    /* build a match bitmap for the clauses */
    matches = mcv_get_match_bitmap(root, clauses, stat->keys, stat->exprs,
                                   mcv, false);
 
    /* sum frequencies for all the matching MCV items */
    *basesel = 0.0;
    *totalsel = 0.0;
    for (i = 0; i < mcv->nitems; i++)
    {
        *totalsel += mcv->items[i].frequency;
 
        if (matches[i] != false)
        {
            *basesel += mcv->items[i].base_frequency;
            s += mcv->items[i].frequency;
        }
    }
 
    return s;
}

References MCVItem::base_frequency, MCVItem::frequency, i, RangeTblEntry::inh, MCVList::items, mcv_get_match_bitmap(), MCVList::nitems, RelOptInfo::relid, and statext_mcv_load().

Referenced by statext_mcv_clauselist_selectivity().

mcv_combine_selectivities()

Selectivity mcv_combine_selectivities	(	Selectivity	simple_sel,
		Selectivity	mcv_sel,
		Selectivity	mcv_basesel,
		Selectivity	mcv_totalsel
	)

Definition at line 2010 of file mcv.c.

{
    Selectivity other_sel;
    Selectivity sel;
 
    /* estimated selectivity of values not covered by MCV matches */
    other_sel = simple_sel - mcv_basesel;
    CLAMP_PROBABILITY(other_sel);
 
    /* this non-MCV selectivity cannot exceed 1 - mcv_totalsel */
    if (other_sel > 1.0 - mcv_totalsel)
        other_sel = 1.0 - mcv_totalsel;
 
    /* overall selectivity is the sum of the MCV and non-MCV parts */
    sel = mcv_sel + other_sel;
    CLAMP_PROBABILITY(sel);
 
    return sel;
}

References CLAMP_PROBABILITY.

Referenced by statext_mcv_clauselist_selectivity().

mcv_get_match_bitmap()

static bool* mcv_get_match_bitmap ( PlannerInfo *  root, List *  clauses, Bitmapset *  keys, List *  exprs, MCVList *  mcvlist, bool  is_or  )

static

Definition at line 1603 of file mcv.c.

{
    ListCell   *l;
    bool       *matches;
 
    /* The bitmap may be partially built. */
    Assert(clauses != NIL);
    Assert(mcvlist != NULL);
    Assert(mcvlist->nitems > 0);
    Assert(mcvlist->nitems <= STATS_MCVLIST_MAX_ITEMS);
 
    matches = palloc(sizeof(bool) * mcvlist->nitems);
    memset(matches, !is_or, sizeof(bool) * mcvlist->nitems);
 
    /*
     * Loop through the list of clauses, and for each of them evaluate all the
     * MCV items not yet eliminated by the preceding clauses.
     */
    foreach(l, clauses)
    {
        Node       *clause = (Node *) lfirst(l);
 
        /* if it's a RestrictInfo, then extract the clause */
        if (IsA(clause, RestrictInfo))
            clause = (Node *) ((RestrictInfo *) clause)->clause;
 
        /*
         * Handle the various types of clauses - OpClause, NullTest and
         * AND/OR/NOT
         */
        if (is_opclause(clause))
        {
            OpExpr     *expr = (OpExpr *) clause;
            FmgrInfo    opproc;
 
            /* valid only after examine_opclause_args returns true */
            Node       *clause_expr;
            Const      *cst;
            bool        expronleft;
            int         idx;
            Oid         collid;
 
            fmgr_info(get_opcode(expr->opno), &opproc);
 
            /* extract the var/expr and const from the expression */
            if (!examine_opclause_args(expr->args, &clause_expr, &cst, &expronleft))
                elog(ERROR, "incompatible clause");
 
            /* match the attribute/expression to a dimension of the statistic */
            idx = mcv_match_expression(clause_expr, keys, exprs, &collid);
 
            /*
             * Walk through the MCV items and evaluate the current clause. We
             * can skip items that were already ruled out, and terminate if
             * there are no remaining MCV items that might possibly match.
             */
            for (int i = 0; i < mcvlist->nitems; i++)
            {
                bool        match = true;
                MCVItem    *item = &mcvlist->items[i];
 
                Assert(idx >= 0);
 
                /*
                 * When the MCV item or the Const value is NULL we can treat
                 * this as a mismatch. We must not call the operator because
                 * of strictness.
                 */
                if (item->isnull[idx] || cst->constisnull)
                {
                    matches[i] = RESULT_MERGE(matches[i], is_or, false);
                    continue;
                }
 
                /*
                 * Skip MCV items that can't change result in the bitmap. Once
                 * the value gets false for AND-lists, or true for OR-lists,
                 * we don't need to look at more clauses.
                 */
                if (RESULT_IS_FINAL(matches[i], is_or))
                    continue;
 
                /*
                 * First check whether the constant is below the lower
                 * boundary (in that case we can skip the bucket, because
                 * there's no overlap).
                 *
                 * We don't store collations used to build the statistics, but
                 * we can use the collation for the attribute itself, as
                 * stored in varcollid. We do reset the statistics after a
                 * type change (including collation change), so this is OK.
                 * For expressions, we use the collation extracted from the
                 * expression itself.
                 */
                if (expronleft)
                    match = DatumGetBool(FunctionCall2Coll(&opproc,
                                                           collid,
                                                           item->values[idx],
                                                           cst->constvalue));
                else
                    match = DatumGetBool(FunctionCall2Coll(&opproc,
                                                           collid,
                                                           cst->constvalue,
                                                           item->values[idx]));
 
                /* update the match bitmap with the result */
                matches[i] = RESULT_MERGE(matches[i], is_or, match);
            }
        }
        else if (IsA(clause, ScalarArrayOpExpr))
        {
            ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
            FmgrInfo    opproc;
 
            /* valid only after examine_opclause_args returns true */
            Node       *clause_expr;
            Const      *cst;
            bool        expronleft;
            Oid         collid;
            int         idx;
 
            /* array evaluation */
            ArrayType  *arrayval;
            int16       elmlen;
            bool        elmbyval;
            char        elmalign;
            int         num_elems;
            Datum      *elem_values;
            bool       *elem_nulls;
 
            fmgr_info(get_opcode(expr->opno), &opproc);
 
            /* extract the var/expr and const from the expression */
            if (!examine_opclause_args(expr->args, &clause_expr, &cst, &expronleft))
                elog(ERROR, "incompatible clause");
 
            /* We expect Var on left */
            if (!expronleft)
                elog(ERROR, "incompatible clause");
 
            /*
             * Deconstruct the array constant, unless it's NULL (we'll cover
             * that case below)
             */
            if (!cst->constisnull)
            {
                arrayval = DatumGetArrayTypeP(cst->constvalue);
                get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
                                     &elmlen, &elmbyval, &elmalign);
                deconstruct_array(arrayval,
                                  ARR_ELEMTYPE(arrayval),
                                  elmlen, elmbyval, elmalign,
                                  &elem_values, &elem_nulls, &num_elems);
            }
 
            /* match the attribute/expression to a dimension of the statistic */
            idx = mcv_match_expression(clause_expr, keys, exprs, &collid);
 
            /*
             * Walk through the MCV items and evaluate the current clause. We
             * can skip items that were already ruled out, and terminate if
             * there are no remaining MCV items that might possibly match.
             */
            for (int i = 0; i < mcvlist->nitems; i++)
            {
                int         j;
                bool        match = !expr->useOr;
                MCVItem    *item = &mcvlist->items[i];
 
                /*
                 * When the MCV item or the Const value is NULL we can treat
                 * this as a mismatch. We must not call the operator because
                 * of strictness.
                 */
                if (item->isnull[idx] || cst->constisnull)
                {
                    matches[i] = RESULT_MERGE(matches[i], is_or, false);
                    continue;
                }
 
                /*
                 * Skip MCV items that can't change result in the bitmap. Once
                 * the value gets false for AND-lists, or true for OR-lists,
                 * we don't need to look at more clauses.
                 */
                if (RESULT_IS_FINAL(matches[i], is_or))
                    continue;
 
                for (j = 0; j < num_elems; j++)
                {
                    Datum       elem_value = elem_values[j];
                    bool        elem_isnull = elem_nulls[j];
                    bool        elem_match;
 
                    /* NULL values always evaluate as not matching. */
                    if (elem_isnull)
                    {
                        match = RESULT_MERGE(match, expr->useOr, false);
                        continue;
                    }
 
                    /*
                     * Stop evaluating the array elements once we reach a
                     * matching value that can't change - ALL() is the same as
                     * AND-list, ANY() is the same as OR-list.
                     */
                    if (RESULT_IS_FINAL(match, expr->useOr))
                        break;
 
                    elem_match = DatumGetBool(FunctionCall2Coll(&opproc,
                                                                collid,
                                                                item->values[idx],
                                                                elem_value));
 
                    match = RESULT_MERGE(match, expr->useOr, elem_match);
                }
 
                /* update the match bitmap with the result */
                matches[i] = RESULT_MERGE(matches[i], is_or, match);
            }
        }
        else if (IsA(clause, NullTest))
        {
            NullTest   *expr = (NullTest *) clause;
            Node       *clause_expr = (Node *) (expr->arg);
 
            /* match the attribute/expression to a dimension of the statistic */
            int         idx = mcv_match_expression(clause_expr, keys, exprs, NULL);
 
            /*
             * Walk through the MCV items and evaluate the current clause. We
             * can skip items that were already ruled out, and terminate if
             * there are no remaining MCV items that might possibly match.
             */
            for (int i = 0; i < mcvlist->nitems; i++)
            {
                bool        match = false;  /* assume mismatch */
                MCVItem    *item = &mcvlist->items[i];
 
                /* if the clause mismatches the MCV item, update the bitmap */
                switch (expr->nulltesttype)
                {
                    case IS_NULL:
                        match = (item->isnull[idx]) ? true : match;
                        break;
 
                    case IS_NOT_NULL:
                        match = (!item->isnull[idx]) ? true : match;
                        break;
                }
 
                /* now, update the match bitmap, depending on OR/AND type */
                matches[i] = RESULT_MERGE(matches[i], is_or, match);
            }
        }
        else if (is_orclause(clause) || is_andclause(clause))
        {
            /* AND/OR clause, with all subclauses being compatible */
 
            int         i;
            BoolExpr   *bool_clause = ((BoolExpr *) clause);
            List       *bool_clauses = bool_clause->args;
 
            /* match/mismatch bitmap for each MCV item */
            bool       *bool_matches = NULL;
 
            Assert(bool_clauses != NIL);
            Assert(list_length(bool_clauses) >= 2);
 
            /* build the match bitmap for the OR-clauses */
            bool_matches = mcv_get_match_bitmap(root, bool_clauses, keys, exprs,
                                                mcvlist, is_orclause(clause));
 
            /*
             * Merge the bitmap produced by mcv_get_match_bitmap into the
             * current one. We need to consider if we're evaluating AND or OR
             * condition when merging the results.
             */
            for (i = 0; i < mcvlist->nitems; i++)
                matches[i] = RESULT_MERGE(matches[i], is_or, bool_matches[i]);
 
            pfree(bool_matches);
        }
        else if (is_notclause(clause))
        {
            /* NOT clause, with all subclauses compatible */
 
            int         i;
            BoolExpr   *not_clause = ((BoolExpr *) clause);
            List       *not_args = not_clause->args;
 
            /* match/mismatch bitmap for each MCV item */
            bool       *not_matches = NULL;
 
            Assert(not_args != NIL);
            Assert(list_length(not_args) == 1);
 
            /* build the match bitmap for the NOT-clause */
            not_matches = mcv_get_match_bitmap(root, not_args, keys, exprs,
                                               mcvlist, false);
 
            /*
             * Merge the bitmap produced by mcv_get_match_bitmap into the
             * current one. We're handling a NOT clause, so invert the result
             * before merging it into the global bitmap.
             */
            for (i = 0; i < mcvlist->nitems; i++)
                matches[i] = RESULT_MERGE(matches[i], is_or, !not_matches[i]);
 
            pfree(not_matches);
        }
        else if (IsA(clause, Var))
        {
            /* Var (has to be a boolean Var, possibly from below NOT) */
 
            Var        *var = (Var *) (clause);
 
            /* match the attribute to a dimension of the statistic */
            int         idx = bms_member_index(keys, var->varattno);
 
            Assert(var->vartype == BOOLOID);
 
            /*
             * Walk through the MCV items and evaluate the current clause. We
             * can skip items that were already ruled out, and terminate if
             * there are no remaining MCV items that might possibly match.
             */
            for (int i = 0; i < mcvlist->nitems; i++)
            {
                MCVItem    *item = &mcvlist->items[i];
                bool        match = false;
 
                /* if the item is NULL, it's a mismatch */
                if (!item->isnull[idx] && DatumGetBool(item->values[idx]))
                    match = true;
 
                /* update the result bitmap */
                matches[i] = RESULT_MERGE(matches[i], is_or, match);
            }
        }
        else
        {
            /* Otherwise, it must be a bare boolean-returning expression */
            int         idx;
 
            /* match the expression to a dimension of the statistic */
            idx = mcv_match_expression(clause, keys, exprs, NULL);
 
            /*
             * Walk through the MCV items and evaluate the current clause. We
             * can skip items that were already ruled out, and terminate if
             * there are no remaining MCV items that might possibly match.
             */
            for (int i = 0; i < mcvlist->nitems; i++)
            {
                bool        match;
                MCVItem    *item = &mcvlist->items[i];
 
                /* "match" just means it's bool TRUE */
                match = !item->isnull[idx] && DatumGetBool(item->values[idx]);
 
                /* now, update the match bitmap, depending on OR/AND type */
                matches[i] = RESULT_MERGE(matches[i], is_or, match);
            }
        }
    }
 
    return matches;
}

References NullTest::arg, OpExpr::args, ScalarArrayOpExpr::args, BoolExpr::args, ARR_ELEMTYPE, Assert(), bms_member_index(), collid, DatumGetArrayTypeP, DatumGetBool(), deconstruct_array(), elog(), ERROR, examine_opclause_args(), fmgr_info(), FunctionCall2Coll(), get_opcode(), get_typlenbyvalalign(), i, idx(), is_andclause(), IS_NOT_NULL, is_notclause(), IS_NULL, is_opclause(), is_orclause(), IsA, MCVItem::isnull, MCVList::items, j, lfirst, list_length(), mcv_match_expression(), NIL, MCVList::nitems, NullTest::nulltesttype, OpExpr::opno, ScalarArrayOpExpr::opno, palloc(), pfree(), RESULT_IS_FINAL, RESULT_MERGE, STATS_MCVLIST_MAX_ITEMS, ScalarArrayOpExpr::useOr, MCVItem::values, and Var::varattno.

Referenced by mcv_clause_selectivity_or(), and mcv_clauselist_selectivity().

mcv_match_expression()

static int mcv_match_expression ( Node *  expr, Bitmapset *  keys, List *  exprs, Oid *  collid  )

static

Definition at line 1539 of file mcv.c.

{
    int         idx;
 
    if (IsA(expr, Var))
    {
        /* simple Var, so just lookup using varattno */
        Var        *var = (Var *) expr;
 
        if (collid)
            *collid = var->varcollid;
 
        idx = bms_member_index(keys, var->varattno);
 
        if (idx < 0)
            elog(ERROR, "variable not found in statistics object");
    }
    else
    {
        /* expression - lookup in stats expressions */
        ListCell   *lc;
 
        if (collid)
            *collid = exprCollation(expr);
 
        /* expressions are stored after the simple columns */
        idx = bms_num_members(keys);
        foreach(lc, exprs)
        {
            Node       *stat_expr = (Node *) lfirst(lc);
 
            if (equal(expr, stat_expr))
                break;
 
            idx++;
        }
 
        if (lc == NULL)
            elog(ERROR, "expression not found in statistics object");
    }
 
    return idx;
}

References bms_member_index(), bms_num_members(), collid, elog(), equal(), ERROR, exprCollation(), idx(), IsA, lfirst, and Var::varattno.

Referenced by mcv_get_match_bitmap().

pg_mcv_list_in()

Datum pg_mcv_list_in

(

PG_FUNCTION_ARGS

)

Definition at line 1476 of file mcv.c.

{
    /*
     * pg_mcv_list stores the data in binary form and parsing text input is
     * not needed, so disallow this.
     */
    ereport(ERROR,
            (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
             errmsg("cannot accept a value of type %s", "pg_mcv_list")));
 
    PG_RETURN_VOID();           /* keep compiler quiet */
}

References ereport, errcode(), errmsg(), ERROR, and PG_RETURN_VOID.

pg_mcv_list_out()

Datum pg_mcv_list_out

(

PG_FUNCTION_ARGS

)

Definition at line 1502 of file mcv.c.

{
    return byteaout(fcinfo);
}

References byteaout().

pg_mcv_list_recv()

Datum pg_mcv_list_recv

(

PG_FUNCTION_ARGS

)

Definition at line 1511 of file mcv.c.

{
    ereport(ERROR,
            (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
             errmsg("cannot accept a value of type %s", "pg_mcv_list")));
 
    PG_RETURN_VOID();           /* keep compiler quiet */
}

References ereport, errcode(), errmsg(), ERROR, and PG_RETURN_VOID.

pg_mcv_list_send()

Datum pg_mcv_list_send

(

PG_FUNCTION_ARGS

)

Definition at line 1527 of file mcv.c.

{
    return byteasend(fcinfo);
}

References byteasend().

pg_stats_ext_mcvlist_items()

Datum pg_stats_ext_mcvlist_items

(

PG_FUNCTION_ARGS

)

Definition at line 1342 of file mcv.c.

{
    FuncCallContext *funcctx;
 
    /* stuff done only on the first call of the function */
    if (SRF_IS_FIRSTCALL())
    {
        MemoryContext oldcontext;
        MCVList    *mcvlist;
        TupleDesc   tupdesc;
 
        /* create a function context for cross-call persistence */
        funcctx = SRF_FIRSTCALL_INIT();
 
        /* switch to memory context appropriate for multiple function calls */
        oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
 
        mcvlist = statext_mcv_deserialize(PG_GETARG_BYTEA_P(0));
 
        funcctx->user_fctx = mcvlist;
 
        /* total number of tuples to be returned */
        funcctx->max_calls = 0;
        if (funcctx->user_fctx != NULL)
            funcctx->max_calls = mcvlist->nitems;
 
        /* Build a tuple descriptor for our result type */
        if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
            ereport(ERROR,
                    (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
                     errmsg("function returning record called in context "
                            "that cannot accept type record")));
        tupdesc = BlessTupleDesc(tupdesc);
 
        /*
         * generate attribute metadata needed later to produce tuples from raw
         * C strings
         */
        funcctx->attinmeta = TupleDescGetAttInMetadata(tupdesc);
 
        MemoryContextSwitchTo(oldcontext);
    }
 
    /* stuff done on every call of the function */
    funcctx = SRF_PERCALL_SETUP();
 
    if (funcctx->call_cntr < funcctx->max_calls)    /* do when there is more
                                                     * left to send */
    {
        Datum       values[5];
        bool        nulls[5];
        HeapTuple   tuple;
        Datum       result;
        ArrayBuildState *astate_values = NULL;
        ArrayBuildState *astate_nulls = NULL;
 
        int         i;
        MCVList    *mcvlist;
        MCVItem    *item;
 
        mcvlist = (MCVList *) funcctx->user_fctx;
 
        Assert(funcctx->call_cntr < mcvlist->nitems);
 
        item = &mcvlist->items[funcctx->call_cntr];
 
        for (i = 0; i < mcvlist->ndimensions; i++)
        {
 
            astate_nulls = accumArrayResult(astate_nulls,
                                            BoolGetDatum(item->isnull[i]),
                                            false,
                                            BOOLOID,
                                            CurrentMemoryContext);
 
            if (!item->isnull[i])
            {
                bool        isvarlena;
                Oid         outfunc;
                FmgrInfo    fmgrinfo;
                Datum       val;
                text       *txt;
 
                /* lookup output func for the type */
                getTypeOutputInfo(mcvlist->types[i], &outfunc, &isvarlena);
                fmgr_info(outfunc, &fmgrinfo);
 
                val = FunctionCall1(&fmgrinfo, item->values[i]);
                txt = cstring_to_text(DatumGetPointer(val));
 
                astate_values = accumArrayResult(astate_values,
                                                 PointerGetDatum(txt),
                                                 false,
                                                 TEXTOID,
                                                 CurrentMemoryContext);
            }
            else
                astate_values = accumArrayResult(astate_values,
                                                 (Datum) 0,
                                                 true,
                                                 TEXTOID,
                                                 CurrentMemoryContext);
        }
 
        values[0] = Int32GetDatum(funcctx->call_cntr);
        values[1] = makeArrayResult(astate_values, CurrentMemoryContext);
        values[2] = makeArrayResult(astate_nulls, CurrentMemoryContext);
        values[3] = Float8GetDatum(item->frequency);
        values[4] = Float8GetDatum(item->base_frequency);
 
        /* no NULLs in the tuple */
        memset(nulls, 0, sizeof(nulls));
 
        /* build a tuple */
        tuple = heap_form_tuple(funcctx->attinmeta->tupdesc, values, nulls);
 
        /* make the tuple into a datum */
        result = HeapTupleGetDatum(tuple);
 
        SRF_RETURN_NEXT(funcctx, result);
    }
    else                        /* do when there is no more left */
    {
        SRF_RETURN_DONE(funcctx);
    }
}

References accumArrayResult(), Assert(), FuncCallContext::attinmeta, MCVItem::base_frequency, BlessTupleDesc(), BoolGetDatum(), FuncCallContext::call_cntr, cstring_to_text(), CurrentMemoryContext, DatumGetPointer(), ereport, errcode(), errmsg(), ERROR, Float8GetDatum(), fmgr_info(), MCVItem::frequency, FunctionCall1, get_call_result_type(), getTypeOutputInfo(), heap_form_tuple(), HeapTupleGetDatum(), i, Int32GetDatum(), MCVItem::isnull, MCVList::items, makeArrayResult(), FuncCallContext::max_calls, MemoryContextSwitchTo(), FuncCallContext::multi_call_memory_ctx, MCVList::ndimensions, MCVList::nitems, PG_GETARG_BYTEA_P, PointerGetDatum(), SRF_FIRSTCALL_INIT, SRF_IS_FIRSTCALL, SRF_PERCALL_SETUP, SRF_RETURN_DONE, SRF_RETURN_NEXT, statext_mcv_deserialize(), AttInMetadata::tupdesc, TupleDescGetAttInMetadata(), TYPEFUNC_COMPOSITE, MCVList::types, FuncCallContext::user_fctx, val, values, and MCVItem::values.

sort_item_compare()

static int sort_item_compare ( const void *  a, const void *  b, void *  arg  )

static

Definition at line 469 of file mcv.c.

{
    SortSupport ssup = (SortSupport) arg;
    SortItem   *ia = (SortItem *) a;
    SortItem   *ib = (SortItem *) b;
 
    return ApplySortComparator(ia->values[0], ia->isnull[0],
                               ib->values[0], ib->isnull[0],
                               ssup);
}

References a, ApplySortComparator(), arg, b, SortItem::isnull, and SortItem::values.

Referenced by build_column_frequencies().

statext_mcv_build()

MCVList* statext_mcv_build	(	StatsBuildData *	data,
		double	totalrows,
		int	stattarget
	)

Definition at line 184 of file mcv.c.

{
    int         i,
                numattrs,
                numrows,
                ngroups,
                nitems;
    double      mincount;
    SortItem   *items;
    SortItem   *groups;
    MCVList    *mcvlist = NULL;
    MultiSortSupport mss;
 
    /* comparator for all the columns */
    mss = build_mss(data);
 
    /* sort the rows */
    items = build_sorted_items(data, &nitems, mss,
                               data->nattnums, data->attnums);
 
    if (!items)
        return NULL;
 
    /* for convenience */
    numattrs = data->nattnums;
    numrows = data->numrows;
 
    /* transform the sorted rows into groups (sorted by frequency) */
    groups = build_distinct_groups(nitems, items, mss, &ngroups);
 
    /*
     * The maximum number of MCV items to store, based on the statistics
     * target we computed for the statistics object (from the target set for
     * the object itself, attributes and the system default). In any case, we
     * can't keep more groups than we have available.
     */
    nitems = stattarget;
    if (nitems > ngroups)
        nitems = ngroups;
 
    /*
     * Decide how many items to keep in the MCV list. We can't use the same
     * algorithm as per-column MCV lists, because that only considers the
     * actual group frequency - but we're primarily interested in how the
     * actual frequency differs from the base frequency (product of simple
     * per-column frequencies, as if the columns were independent).
     *
     * Using the same algorithm might exclude items that are close to the
     * "average" frequency of the sample. But that does not say whether the
     * observed frequency is close to the base frequency or not. We also need
     * to consider unexpectedly uncommon items (again, compared to the base
     * frequency), and the single-column algorithm does not have to.
     *
     * We simply decide how many items to keep by computing the minimum count
     * using get_mincount_for_mcv_list() and then keep all items that seem to
     * be more common than that.
     */
    mincount = get_mincount_for_mcv_list(numrows, totalrows);
 
    /*
     * Walk the groups until we find the first group with a count below the
     * mincount threshold (the index of that group is the number of groups we
     * want to keep).
     */
    for (i = 0; i < nitems; i++)
    {
        if (groups[i].count < mincount)
        {
            nitems = i;
            break;
        }
    }
 
    /*
     * At this point, we know the number of items for the MCV list. There
     * might be none (for uniform distribution with many groups), and in that
     * case, there will be no MCV list. Otherwise, construct the MCV list.
     */
    if (nitems > 0)
    {
        int         j;
        SortItem    key;
        MultiSortSupport tmp;
 
        /* frequencies for values in each attribute */
        SortItem  **freqs;
        int        *nfreqs;
 
        /* used to search values */
        tmp = (MultiSortSupport) palloc(offsetof(MultiSortSupportData, ssup)
                                        + sizeof(SortSupportData));
 
        /* compute frequencies for values in each column */
        nfreqs = (int *) palloc0(sizeof(int) * numattrs);
        freqs = build_column_frequencies(groups, ngroups, mss, nfreqs);
 
        /*
         * Allocate the MCV list structure, set the global parameters.
         */
        mcvlist = (MCVList *) palloc0(offsetof(MCVList, items) +
                                      sizeof(MCVItem) * nitems);
 
        mcvlist->magic = STATS_MCV_MAGIC;
        mcvlist->type = STATS_MCV_TYPE_BASIC;
        mcvlist->ndimensions = numattrs;
        mcvlist->nitems = nitems;
 
        /* store info about data type OIDs */
        for (i = 0; i < numattrs; i++)
            mcvlist->types[i] = data->stats[i]->attrtypid;
 
        /* Copy the first chunk of groups into the result. */
        for (i = 0; i < nitems; i++)
        {
            /* just point to the proper place in the list */
            MCVItem    *item = &mcvlist->items[i];
 
            item->values = (Datum *) palloc(sizeof(Datum) * numattrs);
            item->isnull = (bool *) palloc(sizeof(bool) * numattrs);
 
            /* copy values for the group */
            memcpy(item->values, groups[i].values, sizeof(Datum) * numattrs);
            memcpy(item->isnull, groups[i].isnull, sizeof(bool) * numattrs);
 
            /* groups should be sorted by frequency in descending order */
            Assert((i == 0) || (groups[i - 1].count >= groups[i].count));
 
            /* group frequency */
            item->frequency = (double) groups[i].count / numrows;
 
            /* base frequency, if the attributes were independent */
            item->base_frequency = 1.0;
            for (j = 0; j < numattrs; j++)
            {
                SortItem   *freq;
 
                /* single dimension */
                tmp->ndims = 1;
                tmp->ssup[0] = mss->ssup[j];
 
                /* fill search key */
                key.values = &groups[i].values[j];
                key.isnull = &groups[i].isnull[j];
 
                freq = (SortItem *) bsearch_arg(&key, freqs[j], nfreqs[j],
                                                sizeof(SortItem),
                                                multi_sort_compare, tmp);
 
                item->base_frequency *= ((double) freq->count) / numrows;
            }
        }
 
        pfree(nfreqs);
        pfree(freqs);
    }
 
    pfree(items);
    pfree(groups);
 
    return mcvlist;
}

References Assert(), MCVItem::base_frequency, bsearch_arg(), build_column_frequencies(), build_distinct_groups(), build_mss(), build_sorted_items(), SortItem::count, data, MCVItem::frequency, get_mincount_for_mcv_list(), i, SortItem::isnull, MCVItem::isnull, MCVList::items, j, sort-test::key, MCVList::magic, multi_sort_compare(), MCVList::ndimensions, MultiSortSupportData::ndims, MCVList::nitems, nitems, palloc(), palloc0(), pfree(), MultiSortSupportData::ssup, STATS_MCV_MAGIC, STATS_MCV_TYPE_BASIC, MCVList::type, MCVList::types, SortItem::values, and MCVItem::values.

Referenced by BuildRelationExtStatistics().

statext_mcv_deserialize()

MCVList* statext_mcv_deserialize

(

bytea *

data

)

Definition at line 1000 of file mcv.c.

{
    int         dim,
                i;
    Size        expected_size;
    MCVList    *mcvlist;
    char       *raw;
    char       *ptr;
    char       *endptr PG_USED_FOR_ASSERTS_ONLY;
 
    int         ndims,
                nitems;
    DimensionInfo *info = NULL;
 
    /* local allocation buffer (used only for deserialization) */
    Datum     **map = NULL;
 
    /* MCV list */
    Size        mcvlen;
 
    /* buffer used for the result */
    Size        datalen;
    char       *dataptr;
    char       *valuesptr;
    char       *isnullptr;
 
    if (data == NULL)
        return NULL;
 
    /*
     * We can't possibly deserialize a MCV list if there's not even a complete
     * header. We need an explicit formula here, because we serialize the
     * header fields one by one, so we need to ignore struct alignment.
     */
    if (VARSIZE_ANY(data) < MinSizeOfMCVList)
        elog(ERROR, "invalid MCV size %zu (expected at least %zu)",
             VARSIZE_ANY(data), MinSizeOfMCVList);
 
    /* read the MCV list header */
    mcvlist = (MCVList *) palloc0(offsetof(MCVList, items));
 
    /* pointer to the data part (skip the varlena header) */
    raw = (char *) data;
    ptr = VARDATA_ANY(raw);
    endptr = (char *) raw + VARSIZE_ANY(data);
 
    /* get the header and perform further sanity checks */
    memcpy(&mcvlist->magic, ptr, sizeof(uint32));
    ptr += sizeof(uint32);
 
    memcpy(&mcvlist->type, ptr, sizeof(uint32));
    ptr += sizeof(uint32);
 
    memcpy(&mcvlist->nitems, ptr, sizeof(uint32));
    ptr += sizeof(uint32);
 
    memcpy(&mcvlist->ndimensions, ptr, sizeof(AttrNumber));
    ptr += sizeof(AttrNumber);
 
    if (mcvlist->magic != STATS_MCV_MAGIC)
        elog(ERROR, "invalid MCV magic %u (expected %u)",
             mcvlist->magic, STATS_MCV_MAGIC);
 
    if (mcvlist->type != STATS_MCV_TYPE_BASIC)
        elog(ERROR, "invalid MCV type %u (expected %u)",
             mcvlist->type, STATS_MCV_TYPE_BASIC);
 
    if (mcvlist->ndimensions == 0)
        elog(ERROR, "invalid zero-length dimension array in MCVList");
    else if ((mcvlist->ndimensions > STATS_MAX_DIMENSIONS) ||
             (mcvlist->ndimensions < 0))
        elog(ERROR, "invalid length (%d) dimension array in MCVList",
             mcvlist->ndimensions);
 
    if (mcvlist->nitems == 0)
        elog(ERROR, "invalid zero-length item array in MCVList");
    else if (mcvlist->nitems > STATS_MCVLIST_MAX_ITEMS)
        elog(ERROR, "invalid length (%u) item array in MCVList",
             mcvlist->nitems);
 
    nitems = mcvlist->nitems;
    ndims = mcvlist->ndimensions;
 
    /*
     * Check amount of data including DimensionInfo for all dimensions and
     * also the serialized items (including uint16 indexes). Also, walk
     * through the dimension information and add it to the sum.
     */
    expected_size = SizeOfMCVList(ndims, nitems);
 
    /*
     * Check that we have at least the dimension and info records, along with
     * the items. We don't know the size of the serialized values yet. We need
     * to do this check first, before accessing the dimension info.
     */
    if (VARSIZE_ANY(data) < expected_size)
        elog(ERROR, "invalid MCV size %zu (expected %zu)",
             VARSIZE_ANY(data), expected_size);
 
    /* Now copy the array of type Oids. */
    memcpy(mcvlist->types, ptr, sizeof(Oid) * ndims);
    ptr += (sizeof(Oid) * ndims);
 
    /* Now it's safe to access the dimension info. */
    info = palloc(ndims * sizeof(DimensionInfo));
 
    memcpy(info, ptr, ndims * sizeof(DimensionInfo));
    ptr += (ndims * sizeof(DimensionInfo));
 
    /* account for the value arrays */
    for (dim = 0; dim < ndims; dim++)
    {
        /*
         * XXX I wonder if we can/should rely on asserts here. Maybe those
         * checks should be done every time?
         */
        Assert(info[dim].nvalues >= 0);
        Assert(info[dim].nbytes >= 0);
 
        expected_size += info[dim].nbytes;
    }
 
    /*
     * Now we know the total expected MCV size, including all the pieces
     * (header, dimension info. items and deduplicated data). So do the final
     * check on size.
     */
    if (VARSIZE_ANY(data) != expected_size)
        elog(ERROR, "invalid MCV size %zu (expected %zu)",
             VARSIZE_ANY(data), expected_size);
 
    /*
     * We need an array of Datum values for each dimension, so that we can
     * easily translate the uint16 indexes later. We also need a top-level
     * array of pointers to those per-dimension arrays.
     *
     * While allocating the arrays for dimensions, compute how much space we
     * need for a copy of the by-ref data, as we can't simply point to the
     * original values (it might go away).
     */
    datalen = 0;                /* space for by-ref data */
    map = (Datum **) palloc(ndims * sizeof(Datum *));
 
    for (dim = 0; dim < ndims; dim++)
    {
        map[dim] = (Datum *) palloc(sizeof(Datum) * info[dim].nvalues);
 
        /* space needed for a copy of data for by-ref types */
        datalen += info[dim].nbytes_aligned;
    }
 
    /*
     * Now resize the MCV list so that the allocation includes all the data.
     *
     * Allocate space for a copy of the data, as we can't simply reference the
     * serialized data - it's not aligned properly, and it may disappear while
     * we're still using the MCV list, e.g. due to catcache release.
     *
     * We do care about alignment here, because we will allocate all the
     * pieces at once, but then use pointers to different parts.
     */
    mcvlen = MAXALIGN(offsetof(MCVList, items) + (sizeof(MCVItem) * nitems));
 
    /* arrays of values and isnull flags for all MCV items */
    mcvlen += nitems * MAXALIGN(sizeof(Datum) * ndims);
    mcvlen += nitems * MAXALIGN(sizeof(bool) * ndims);
 
    /* we don't quite need to align this, but it makes some asserts easier */
    mcvlen += MAXALIGN(datalen);
 
    /* now resize the deserialized MCV list, and compute pointers to parts */
    mcvlist = repalloc(mcvlist, mcvlen);
 
    /* pointer to the beginning of values/isnull arrays */
    valuesptr = (char *) mcvlist
        + MAXALIGN(offsetof(MCVList, items) + (sizeof(MCVItem) * nitems));
 
    isnullptr = valuesptr + (nitems * MAXALIGN(sizeof(Datum) * ndims));
 
    dataptr = isnullptr + (nitems * MAXALIGN(sizeof(bool) * ndims));
 
    /*
     * Build mapping (index => value) for translating the serialized data into
     * the in-memory representation.
     */
    for (dim = 0; dim < ndims; dim++)
    {
        /* remember start position in the input array */
        char       *start PG_USED_FOR_ASSERTS_ONLY = ptr;
 
        if (info[dim].typbyval)
        {
            /* for by-val types we simply copy data into the mapping */
            for (i = 0; i < info[dim].nvalues; i++)
            {
                Datum       v = 0;
 
                memcpy(&v, ptr, info[dim].typlen);
                ptr += info[dim].typlen;
 
                map[dim][i] = fetch_att(&v, true, info[dim].typlen);
 
                /* no under/overflow of input array */
                Assert(ptr <= (start + info[dim].nbytes));
            }
        }
        else
        {
            /* for by-ref types we need to also make a copy of the data */
 
            /* passed by reference, but fixed length (name, tid, ...) */
            if (info[dim].typlen > 0)
            {
                for (i = 0; i < info[dim].nvalues; i++)
                {
                    memcpy(dataptr, ptr, info[dim].typlen);
                    ptr += info[dim].typlen;
 
                    /* just point into the array */
                    map[dim][i] = PointerGetDatum(dataptr);
                    dataptr += MAXALIGN(info[dim].typlen);
                }
            }
            else if (info[dim].typlen == -1)
            {
                /* varlena */
                for (i = 0; i < info[dim].nvalues; i++)
                {
                    uint32      len;
 
                    /* read the uint32 length */
                    memcpy(&len, ptr, sizeof(uint32));
                    ptr += sizeof(uint32);
 
                    /* the length is data-only */
                    SET_VARSIZE(dataptr, len + VARHDRSZ);
                    memcpy(VARDATA(dataptr), ptr, len);
                    ptr += len;
 
                    /* just point into the array */
                    map[dim][i] = PointerGetDatum(dataptr);
 
                    /* skip to place of the next deserialized value */
                    dataptr += MAXALIGN(len + VARHDRSZ);
                }
            }
            else if (info[dim].typlen == -2)
            {
                /* cstring */
                for (i = 0; i < info[dim].nvalues; i++)
                {
                    uint32      len;
 
                    memcpy(&len, ptr, sizeof(uint32));
                    ptr += sizeof(uint32);
 
                    memcpy(dataptr, ptr, len);
                    ptr += len;
 
                    /* just point into the array */
                    map[dim][i] = PointerGetDatum(dataptr);
                    dataptr += MAXALIGN(len);
                }
            }
 
            /* no under/overflow of input array */
            Assert(ptr <= (start + info[dim].nbytes));
 
            /* no overflow of the output mcv value */
            Assert(dataptr <= ((char *) mcvlist + mcvlen));
        }
 
        /* check we consumed input data for this dimension exactly */
        Assert(ptr == (start + info[dim].nbytes));
    }
 
    /* we should have also filled the MCV list exactly */
    Assert(dataptr == ((char *) mcvlist + mcvlen));
 
    /* deserialize the MCV items and translate the indexes to Datums */
    for (i = 0; i < nitems; i++)
    {
        MCVItem    *item = &mcvlist->items[i];
 
        item->values = (Datum *) valuesptr;
        valuesptr += MAXALIGN(sizeof(Datum) * ndims);
 
        item->isnull = (bool *) isnullptr;
        isnullptr += MAXALIGN(sizeof(bool) * ndims);
 
        memcpy(item->isnull, ptr, sizeof(bool) * ndims);
        ptr += sizeof(bool) * ndims;
 
        memcpy(&item->frequency, ptr, sizeof(double));
        ptr += sizeof(double);
 
        memcpy(&item->base_frequency, ptr, sizeof(double));
        ptr += sizeof(double);
 
        /* finally translate the indexes (for non-NULL only) */
        for (dim = 0; dim < ndims; dim++)
        {
            uint16      index;
 
            memcpy(&index, ptr, sizeof(uint16));
            ptr += sizeof(uint16);
 
            if (item->isnull[dim])
                continue;
 
            item->values[dim] = map[dim][index];
        }
 
        /* check we're not overflowing the input */
        Assert(ptr <= endptr);
    }
 
    /* check that we processed all the data */
    Assert(ptr == endptr);
 
    /* release the buffers used for mapping */
    for (dim = 0; dim < ndims; dim++)
        pfree(map[dim]);
 
    pfree(map);
 
    return mcvlist;
}

References Assert(), MCVItem::base_frequency, data, elog(), ERROR, fetch_att(), MCVItem::frequency, i, MCVItem::isnull, MCVList::items, len, MCVList::magic, MAXALIGN, MinSizeOfMCVList, DimensionInfo::nbytes, DimensionInfo::nbytes_aligned, MCVList::ndimensions, MCVList::nitems, nitems, DimensionInfo::nvalues, palloc(), palloc0(), pfree(), PG_USED_FOR_ASSERTS_ONLY, PointerGetDatum(), repalloc(), SET_VARSIZE, SizeOfMCVList, STATS_MAX_DIMENSIONS, STATS_MCV_MAGIC, STATS_MCV_TYPE_BASIC, STATS_MCVLIST_MAX_ITEMS, MCVList::type, MCVList::types, DimensionInfo::typlen, MCVItem::values, VARDATA, VARDATA_ANY, VARHDRSZ, and VARSIZE_ANY.

Referenced by pg_stats_ext_mcvlist_items(), and statext_mcv_load().

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

bytea* statext_mcv_serialize	(	MCVList *	mcvlist,
		VacAttrStats **	stats
	)

Definition at line 625 of file mcv.c.

{
    int         i;
    int         dim;
    int         ndims = mcvlist->ndimensions;
 
    SortSupport ssup;
    DimensionInfo *info;
 
    Size        total_length;
 
    /* serialized items (indexes into arrays, etc.) */
    bytea      *raw;
    char       *ptr;
    char       *endptr PG_USED_FOR_ASSERTS_ONLY;
 
    /* values per dimension (and number of non-NULL values) */
    Datum     **values = (Datum **) palloc0(sizeof(Datum *) * ndims);
    int        *counts = (int *) palloc0(sizeof(int) * ndims);
 
    /*
     * We'll include some rudimentary information about the attribute types
     * (length, by-val flag), so that we don't have to look them up while
     * deserializing the MCV list (we already have the type OID in the
     * header).  This is safe because when changing the type of the attribute
     * the statistics gets dropped automatically.  We need to store the info
     * about the arrays of deduplicated values anyway.
     */
    info = (DimensionInfo *) palloc0(sizeof(DimensionInfo) * ndims);
 
    /* sort support data for all attributes included in the MCV list */
    ssup = (SortSupport) palloc0(sizeof(SortSupportData) * ndims);
 
    /* collect and deduplicate values for each dimension (attribute) */
    for (dim = 0; dim < ndims; dim++)
    {
        int         ndistinct;
        TypeCacheEntry *typentry;
 
        /*
         * Lookup the LT operator (can't get it from stats extra_data, as we
         * don't know how to interpret that - scalar vs. array etc.).
         */
        typentry = lookup_type_cache(stats[dim]->attrtypid, TYPECACHE_LT_OPR);
 
        /* copy important info about the data type (length, by-value) */
        info[dim].typlen = stats[dim]->attrtype->typlen;
        info[dim].typbyval = stats[dim]->attrtype->typbyval;
 
        /* allocate space for values in the attribute and collect them */
        values[dim] = (Datum *) palloc0(sizeof(Datum) * mcvlist->nitems);
 
        for (i = 0; i < mcvlist->nitems; i++)
        {
            /* skip NULL values - we don't need to deduplicate those */
            if (mcvlist->items[i].isnull[dim])
                continue;
 
            /* append the value at the end */
            values[dim][counts[dim]] = mcvlist->items[i].values[dim];
            counts[dim] += 1;
        }
 
        /* if there are just NULL values in this dimension, we're done */
        if (counts[dim] == 0)
            continue;
 
        /* sort and deduplicate the data */
        ssup[dim].ssup_cxt = CurrentMemoryContext;
        ssup[dim].ssup_collation = stats[dim]->attrcollid;
        ssup[dim].ssup_nulls_first = false;
 
        PrepareSortSupportFromOrderingOp(typentry->lt_opr, &ssup[dim]);
 
        qsort_interruptible(values[dim], counts[dim], sizeof(Datum),
                            compare_scalars_simple, &ssup[dim]);
 
        /*
         * Walk through the array and eliminate duplicate values, but keep the
         * ordering (so that we can do a binary search later). We know there's
         * at least one item as (counts[dim] != 0), so we can skip the first
         * element.
         */
        ndistinct = 1;          /* number of distinct values */
        for (i = 1; i < counts[dim]; i++)
        {
            /* expect sorted array */
            Assert(compare_datums_simple(values[dim][i - 1], values[dim][i], &ssup[dim]) <= 0);
 
            /* if the value is the same as the previous one, we can skip it */
            if (!compare_datums_simple(values[dim][i - 1], values[dim][i], &ssup[dim]))
                continue;
 
            values[dim][ndistinct] = values[dim][i];
            ndistinct += 1;
        }
 
        /* we must not exceed PG_UINT16_MAX, as we use uint16 indexes */
        Assert(ndistinct <= PG_UINT16_MAX);
 
        /*
         * Store additional info about the attribute - number of deduplicated
         * values, and also size of the serialized data. For fixed-length data
         * types this is trivial to compute, for varwidth types we need to
         * actually walk the array and sum the sizes.
         */
        info[dim].nvalues = ndistinct;
 
        if (info[dim].typbyval) /* by-value data types */
        {
            info[dim].nbytes = info[dim].nvalues * info[dim].typlen;
 
            /*
             * We copy the data into the MCV item during deserialization, so
             * we don't need to allocate any extra space.
             */
            info[dim].nbytes_aligned = 0;
        }
        else if (info[dim].typlen > 0)  /* fixed-length by-ref */
        {
            /*
             * We don't care about alignment in the serialized data, so we
             * pack the data as much as possible. But we also track how much
             * data will be needed after deserialization, and in that case we
             * need to account for alignment of each item.
             *
             * Note: As the items are fixed-length, we could easily compute
             * this during deserialization, but we do it here anyway.
             */
            info[dim].nbytes = info[dim].nvalues * info[dim].typlen;
            info[dim].nbytes_aligned = info[dim].nvalues * MAXALIGN(info[dim].typlen);
        }
        else if (info[dim].typlen == -1)    /* varlena */
        {
            info[dim].nbytes = 0;
            info[dim].nbytes_aligned = 0;
            for (i = 0; i < info[dim].nvalues; i++)
            {
                Size        len;
 
                /*
                 * For varlena values, we detoast the values and store the
                 * length and data separately. We don't bother with alignment
                 * here, which means that during deserialization we need to
                 * copy the fields and only access the copies.
                 */
                values[dim][i] = PointerGetDatum(PG_DETOAST_DATUM(values[dim][i]));
 
                /* serialized length (uint32 length + data) */
                len = VARSIZE_ANY_EXHDR(values[dim][i]);
                info[dim].nbytes += sizeof(uint32); /* length */
                info[dim].nbytes += len;    /* value (no header) */
 
                /*
                 * During deserialization we'll build regular varlena values
                 * with full headers, and we need to align them properly.
                 */
                info[dim].nbytes_aligned += MAXALIGN(VARHDRSZ + len);
            }
        }
        else if (info[dim].typlen == -2)    /* cstring */
        {
            info[dim].nbytes = 0;
            info[dim].nbytes_aligned = 0;
            for (i = 0; i < info[dim].nvalues; i++)
            {
                Size        len;
 
                /*
                 * cstring is handled similar to varlena - first we store the
                 * length as uint32 and then the data. We don't care about
                 * alignment, which means that during deserialization we need
                 * to copy the fields and only access the copies.
                 */
 
                /* c-strings include terminator, so +1 byte */
                len = strlen(DatumGetCString(values[dim][i])) + 1;
                info[dim].nbytes += sizeof(uint32); /* length */
                info[dim].nbytes += len;    /* value */
 
                /* space needed for properly aligned deserialized copies */
                info[dim].nbytes_aligned += MAXALIGN(len);
            }
        }
 
        /* we know (count>0) so there must be some data */
        Assert(info[dim].nbytes > 0);
    }
 
    /*
     * Now we can finally compute how much space we'll actually need for the
     * whole serialized MCV list (varlena header, MCV header, dimension info
     * for each attribute, deduplicated values and items).
     */
    total_length = (3 * sizeof(uint32)) /* magic + type + nitems */
        + sizeof(AttrNumber)    /* ndimensions */
        + (ndims * sizeof(Oid));    /* attribute types */
 
    /* dimension info */
    total_length += ndims * sizeof(DimensionInfo);
 
    /* add space for the arrays of deduplicated values */
    for (i = 0; i < ndims; i++)
        total_length += info[i].nbytes;
 
    /*
     * And finally account for the items (those are fixed-length, thanks to
     * replacing values with uint16 indexes into the deduplicated arrays).
     */
    total_length += mcvlist->nitems * ITEM_SIZE(dim);
 
    /*
     * Allocate space for the whole serialized MCV list (we'll skip bytes, so
     * we set them to zero to make the result more compressible).
     */
    raw = (bytea *) palloc0(VARHDRSZ + total_length);
    SET_VARSIZE(raw, VARHDRSZ + total_length);
 
    ptr = VARDATA(raw);
    endptr = ptr + total_length;
 
    /* copy the MCV list header fields, one by one */
    memcpy(ptr, &mcvlist->magic, sizeof(uint32));
    ptr += sizeof(uint32);
 
    memcpy(ptr, &mcvlist->type, sizeof(uint32));
    ptr += sizeof(uint32);
 
    memcpy(ptr, &mcvlist->nitems, sizeof(uint32));
    ptr += sizeof(uint32);
 
    memcpy(ptr, &mcvlist->ndimensions, sizeof(AttrNumber));
    ptr += sizeof(AttrNumber);
 
    memcpy(ptr, mcvlist->types, sizeof(Oid) * ndims);
    ptr += (sizeof(Oid) * ndims);
 
    /* store information about the attributes (data amounts, ...) */
    memcpy(ptr, info, sizeof(DimensionInfo) * ndims);
    ptr += sizeof(DimensionInfo) * ndims;
 
    /* Copy the deduplicated values for all attributes to the output. */
    for (dim = 0; dim < ndims; dim++)
    {
        /* remember the starting point for Asserts later */
        char       *start PG_USED_FOR_ASSERTS_ONLY = ptr;
 
        for (i = 0; i < info[dim].nvalues; i++)
        {
            Datum       value = values[dim][i];
 
            if (info[dim].typbyval) /* passed by value */
            {
                Datum       tmp;
 
                /*
                 * For byval types, we need to copy just the significant bytes
                 * - we can't use memcpy directly, as that assumes
                 * little-endian behavior.  store_att_byval does almost what
                 * we need, but it requires a properly aligned buffer - the
                 * output buffer does not guarantee that. So we simply use a
                 * local Datum variable (which guarantees proper alignment),
                 * and then copy the value from it.
                 */
                store_att_byval(&tmp, value, info[dim].typlen);
 
                memcpy(ptr, &tmp, info[dim].typlen);
                ptr += info[dim].typlen;
            }
            else if (info[dim].typlen > 0)  /* passed by reference */
            {
                /* no special alignment needed, treated as char array */
                memcpy(ptr, DatumGetPointer(value), info[dim].typlen);
                ptr += info[dim].typlen;
            }
            else if (info[dim].typlen == -1)    /* varlena */
            {
                uint32      len = VARSIZE_ANY_EXHDR(DatumGetPointer(value));
 
                /* copy the length */
                memcpy(ptr, &len, sizeof(uint32));
                ptr += sizeof(uint32);
 
                /* data from the varlena value (without the header) */
                memcpy(ptr, VARDATA_ANY(DatumGetPointer(value)), len);
                ptr += len;
            }
            else if (info[dim].typlen == -2)    /* cstring */
            {
                uint32      len = (uint32) strlen(DatumGetCString(value)) + 1;
 
                /* copy the length */
                memcpy(ptr, &len, sizeof(uint32));
                ptr += sizeof(uint32);
 
                /* value */
                memcpy(ptr, DatumGetCString(value), len);
                ptr += len;
            }
 
            /* no underflows or overflows */
            Assert((ptr > start) && ((ptr - start) <= info[dim].nbytes));
        }
 
        /* we should get exactly nbytes of data for this dimension */
        Assert((ptr - start) == info[dim].nbytes);
    }
 
    /* Serialize the items, with uint16 indexes instead of the values. */
    for (i = 0; i < mcvlist->nitems; i++)
    {
        MCVItem    *mcvitem = &mcvlist->items[i];
 
        /* don't write beyond the allocated space */
        Assert(ptr <= (endptr - ITEM_SIZE(dim)));
 
        /* copy NULL and frequency flags into the serialized MCV */
        memcpy(ptr, mcvitem->isnull, sizeof(bool) * ndims);
        ptr += sizeof(bool) * ndims;
 
        memcpy(ptr, &mcvitem->frequency, sizeof(double));
        ptr += sizeof(double);
 
        memcpy(ptr, &mcvitem->base_frequency, sizeof(double));
        ptr += sizeof(double);
 
        /* store the indexes last */
        for (dim = 0; dim < ndims; dim++)
        {
            uint16      index = 0;
            Datum      *value;
 
            /* do the lookup only for non-NULL values */
            if (!mcvitem->isnull[dim])
            {
                value = (Datum *) bsearch_arg(&mcvitem->values[dim], values[dim],
                                              info[dim].nvalues, sizeof(Datum),
                                              compare_scalars_simple, &ssup[dim]);
 
                Assert(value != NULL);  /* serialization or deduplication
                                         * error */
 
                /* compute index within the deduplicated array */
                index = (uint16) (value - values[dim]);
 
                /* check the index is within expected bounds */
                Assert(index < info[dim].nvalues);
            }
 
            /* copy the index into the serialized MCV */
            memcpy(ptr, &index, sizeof(uint16));
            ptr += sizeof(uint16);
        }
 
        /* make sure we don't overflow the allocated value */
        Assert(ptr <= endptr);
    }
 
    /* at this point we expect to match the total_length exactly */
    Assert(ptr == endptr);
 
    pfree(values);
    pfree(counts);
 
    return raw;
}

References Assert(), VacAttrStats::attrcollid, VacAttrStats::attrtype, MCVItem::base_frequency, bsearch_arg(), compare_datums_simple(), compare_scalars_simple(), CurrentMemoryContext, DatumGetCString(), DatumGetPointer(), MCVItem::frequency, i, MCVItem::isnull, ITEM_SIZE, MCVList::items, len, lookup_type_cache(), TypeCacheEntry::lt_opr, MCVList::magic, MAXALIGN, DimensionInfo::nbytes, DimensionInfo::nbytes_aligned, MCVList::ndimensions, MCVList::nitems, DimensionInfo::nvalues, palloc0(), pfree(), PG_DETOAST_DATUM, PG_UINT16_MAX, PG_USED_FOR_ASSERTS_ONLY, PointerGetDatum(), PrepareSortSupportFromOrderingOp(), qsort_interruptible(), SET_VARSIZE, SortSupportData::ssup_collation, SortSupportData::ssup_cxt, SortSupportData::ssup_nulls_first, store_att_byval(), DimensionInfo::typbyval, MCVList::type, TYPECACHE_LT_OPR, MCVList::types, DimensionInfo::typlen, value, values, MCVItem::values, VARDATA, VARDATA_ANY, VARHDRSZ, and VARSIZE_ANY_EXHDR.

Referenced by statext_store().