mvdistinct.c File Reference

#include "postgres.h"
#include <math.h>
#include "catalog/pg_statistic_ext.h"
#include "catalog/pg_statistic_ext_data.h"
#include "statistics/extended_stats_internal.h"
#include "utils/syscache.h"
#include "utils/typcache.h"
#include "varatt.h"

Include dependency graph for mvdistinct.c:

Go to the source code of this file.

Data Structures
struct	CombinationGenerator

Macros
#define	SizeOfHeader   (3 * sizeof(uint32))
#define	SizeOfItem(natts)    (sizeof(double) + sizeof(int) + (natts) * sizeof(AttrNumber))
#define	MinSizeOfItem   SizeOfItem(2)
#define	MinSizeOfItems(nitems)    (SizeOfHeader + (nitems) * MinSizeOfItem)

Typedefs
typedef struct CombinationGenerator	CombinationGenerator

Functions
static double	ndistinct_for_combination (double totalrows, StatsBuildData *data, int k, int *combination)
static double	estimate_ndistinct (double totalrows, int numrows, int d, int f1)
static int	n_choose_k (int n, int k)
static int	num_combinations (int n)
static CombinationGenerator *	generator_init (int n, int k)
static void	generator_free (CombinationGenerator *state)
static int *	generator_next (CombinationGenerator *state)
static void	generate_combinations (CombinationGenerator *state)
MVNDistinct *	statext_ndistinct_build (double totalrows, StatsBuildData *data)
MVNDistinct *	statext_ndistinct_load (Oid mvoid, bool inh)
bytea *	statext_ndistinct_serialize (MVNDistinct *ndistinct)
MVNDistinct *	statext_ndistinct_deserialize (bytea *data)
void	statext_ndistinct_free (MVNDistinct *ndistinct)
bool	statext_ndistinct_validate (const MVNDistinct *ndistinct, const int2vector *stxkeys, int numexprs, int elevel)
static void	generate_combinations_recurse (CombinationGenerator *state, int index, int start, int *current)

Macro Definition Documentation

MinSizeOfItem

#define MinSizeOfItem   SizeOfItem(2)

Definition at line 49 of file mvdistinct.c.

MinSizeOfItems

#define MinSizeOfItems

(

nitems

)

(SizeOfHeader + (nitems) * MinSizeOfItem)

Definition at line 52 of file mvdistinct.c.

{
    int         k;              /* size of the combination */
    int         n;              /* total number of elements */
    int         current;        /* index of the next combination to return */
    int         ncombinations;  /* number of combinations (size of array) */
    int        *combinations;   /* array of pre-built combinations */
} CombinationGenerator;
 
static CombinationGenerator *generator_init(int n, int k);
static void generator_free(CombinationGenerator *state);
static int *generator_next(CombinationGenerator *state);
static void generate_combinations(CombinationGenerator *state);
 
 
/*
 * statext_ndistinct_build
 *      Compute ndistinct coefficient for the combination of attributes.
 *
 * This computes the ndistinct estimate using the same estimator used
 * in analyze.c and then computes the coefficient.
 *
 * To handle expressions easily, we treat them as system attributes with
 * negative attnums, and offset everything by number of expressions to
 * allow using Bitmapsets.
 */
MVNDistinct *
statext_ndistinct_build(double totalrows, StatsBuildData *data)
{
    MVNDistinct *result;
    int         k;
    int         itemcnt;
    int         numattrs = data->nattnums;
    int         numcombs = num_combinations(numattrs);
 
    result = palloc(offsetof(MVNDistinct, items) +
                    numcombs * sizeof(MVNDistinctItem));
    result->magic = STATS_NDISTINCT_MAGIC;
    result->type = STATS_NDISTINCT_TYPE_BASIC;
    result->nitems = numcombs;
 
    itemcnt = 0;
    for (k = 2; k <= numattrs; k++)
    {
        int        *combination;
        CombinationGenerator *generator;
 
        /* generate combinations of K out of N elements */
        generator = generator_init(numattrs, k);
 
        while ((combination = generator_next(generator)))
        {
            MVNDistinctItem *item = &result->items[itemcnt];
            int         j;
 
            item->attributes = palloc_array(AttrNumber, k);
            item->nattributes = k;
 
            /* translate the indexes to attnums */
            for (j = 0; j < k; j++)
            {
                item->attributes[j] = data->attnums[combination[j]];
 
                Assert(AttributeNumberIsValid(item->attributes[j]));
            }
 
            item->ndistinct =
                ndistinct_for_combination(totalrows, data, k, combination);
 
            itemcnt++;
            Assert(itemcnt <= result->nitems);
        }
 
        generator_free(generator);
    }
 
    /* must consume exactly the whole output array */
    Assert(itemcnt == result->nitems);
 
    return result;
}
 
/*
 * statext_ndistinct_load
 *      Load the ndistinct value for the indicated pg_statistic_ext tuple
 */
MVNDistinct *
statext_ndistinct_load(Oid mvoid, bool inh)
{
    MVNDistinct *result;
    bool        isnull;
    Datum       ndist;
    HeapTuple   htup;
 
    htup = SearchSysCache2(STATEXTDATASTXOID,
                           ObjectIdGetDatum(mvoid), BoolGetDatum(inh));
    if (!HeapTupleIsValid(htup))
        elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
 
    ndist = SysCacheGetAttr(STATEXTDATASTXOID, htup,
                            Anum_pg_statistic_ext_data_stxdndistinct, &isnull);
    if (isnull)
        elog(ERROR,
             "requested statistics kind \"%c\" is not yet built for statistics object %u",
             STATS_EXT_NDISTINCT, mvoid);
 
    result = statext_ndistinct_deserialize(DatumGetByteaPP(ndist));
 
    ReleaseSysCache(htup);
 
    return result;
}
 
/*
 * statext_ndistinct_serialize
 *      serialize ndistinct to the on-disk bytea format
 */
bytea *
statext_ndistinct_serialize(MVNDistinct *ndistinct)
{
    int         i;
    bytea      *output;
    char       *tmp;
    Size        len;
 
    Assert(ndistinct->magic == STATS_NDISTINCT_MAGIC);
    Assert(ndistinct->type == STATS_NDISTINCT_TYPE_BASIC);
 
    /*
     * Base size is size of scalar fields in the struct, plus one base struct
     * for each item, including number of items for each.
     */
    len = VARHDRSZ + SizeOfHeader;
 
    /* and also include space for the actual attribute numbers */
    for (i = 0; i < ndistinct->nitems; i++)
    {
        int         nmembers;
 
        nmembers = ndistinct->items[i].nattributes;
        Assert(nmembers >= 2);
 
        len += SizeOfItem(nmembers);
    }
 
    output = (bytea *) palloc(len);
    SET_VARSIZE(output, len);
 
    tmp = VARDATA(output);
 
    /* Store the base struct values (magic, type, nitems) */
    memcpy(tmp, &ndistinct->magic, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(tmp, &ndistinct->type, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(tmp, &ndistinct->nitems, sizeof(uint32));
    tmp += sizeof(uint32);
 
    /*
     * store number of attributes and attribute numbers for each entry
     */
    for (i = 0; i < ndistinct->nitems; i++)
    {
        MVNDistinctItem item = ndistinct->items[i];
        int         nmembers = item.nattributes;
 
        memcpy(tmp, &item.ndistinct, sizeof(double));
        tmp += sizeof(double);
        memcpy(tmp, &nmembers, sizeof(int));
        tmp += sizeof(int);
 
        memcpy(tmp, item.attributes, sizeof(AttrNumber) * nmembers);
        tmp += nmembers * sizeof(AttrNumber);
 
        /* protect against overflows */
        Assert(tmp <= ((char *) output + len));
    }
 
    /* check we used exactly the expected space */
    Assert(tmp == ((char *) output + len));
 
    return output;
}
 
/*
 * statext_ndistinct_deserialize
 *      Read an on-disk bytea format MVNDistinct to in-memory format
 */
MVNDistinct *
statext_ndistinct_deserialize(bytea *data)
{
    int         i;
    Size        minimum_size;
    MVNDistinct ndist;
    MVNDistinct *ndistinct;
    char       *tmp;
 
    if (data == NULL)
        return NULL;
 
    /* we expect at least the basic fields of MVNDistinct struct */
    if (VARSIZE_ANY_EXHDR(data) < SizeOfHeader)
        elog(ERROR, "invalid MVNDistinct size %zu (expected at least %zu)",
             VARSIZE_ANY_EXHDR(data), SizeOfHeader);
 
    /* initialize pointer to the data part (skip the varlena header) */
    tmp = VARDATA_ANY(data);
 
    /* read the header fields and perform basic sanity checks */
    memcpy(&ndist.magic, tmp, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(&ndist.type, tmp, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(&ndist.nitems, tmp, sizeof(uint32));
    tmp += sizeof(uint32);
 
    if (ndist.magic != STATS_NDISTINCT_MAGIC)
        elog(ERROR, "invalid ndistinct magic %08x (expected %08x)",
             ndist.magic, STATS_NDISTINCT_MAGIC);
    if (ndist.type != STATS_NDISTINCT_TYPE_BASIC)
        elog(ERROR, "invalid ndistinct type %d (expected %d)",
             ndist.type, STATS_NDISTINCT_TYPE_BASIC);
    if (ndist.nitems == 0)
        elog(ERROR, "invalid zero-length item array in MVNDistinct");
 
    /* what minimum bytea size do we expect for those parameters */
    minimum_size = MinSizeOfItems(ndist.nitems);
    if (VARSIZE_ANY_EXHDR(data) < minimum_size)
        elog(ERROR, "invalid MVNDistinct size %zu (expected at least %zu)",
             VARSIZE_ANY_EXHDR(data), minimum_size);
 
    /*
     * Allocate space for the ndistinct items (no space for each item's
     * attnos: those live in bitmapsets allocated separately)
     */
    ndistinct = palloc0(MAXALIGN(offsetof(MVNDistinct, items)) +
                        (ndist.nitems * sizeof(MVNDistinctItem)));
    ndistinct->magic = ndist.magic;
    ndistinct->type = ndist.type;
    ndistinct->nitems = ndist.nitems;
 
    for (i = 0; i < ndistinct->nitems; i++)
    {
        MVNDistinctItem *item = &ndistinct->items[i];
 
        /* ndistinct value */
        memcpy(&item->ndistinct, tmp, sizeof(double));
        tmp += sizeof(double);
 
        /* number of attributes */
        memcpy(&item->nattributes, tmp, sizeof(int));
        tmp += sizeof(int);
        Assert((item->nattributes >= 2) && (item->nattributes <= STATS_MAX_DIMENSIONS));
 
        item->attributes
            = (AttrNumber *) palloc(item->nattributes * sizeof(AttrNumber));
 
        memcpy(item->attributes, tmp, sizeof(AttrNumber) * item->nattributes);
        tmp += sizeof(AttrNumber) * item->nattributes;
 
        /* still within the bytea */
        Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
    }
 
    /* we should have consumed the whole bytea exactly */
    Assert(tmp == ((char *) data + VARSIZE_ANY(data)));
 
    return ndistinct;
}
 
/*
 * Free allocations of a MVNDistinct.
 */
void
statext_ndistinct_free(MVNDistinct *ndistinct)
{
    for (int i = 0; i < ndistinct->nitems; i++)
        pfree(ndistinct->items[i].attributes);
    pfree(ndistinct);
}
 
/*
 * Validate a set of MVNDistincts against the extended statistics object
 * definition.
 *
 * Every MVNDistinctItem must be checked to ensure that the attnums in the
 * attributes list correspond to attnums/expressions defined by the extended
 * statistics object.
 *
 * Positive attnums are attributes which must be found in the stxkeys,
 * while negative attnums correspond to an expression number, no attribute
 * number can be below (0 - numexprs).
 */
bool
statext_ndistinct_validate(const MVNDistinct *ndistinct,
                           const int2vector *stxkeys,
                           int numexprs, int elevel)
{
    int         attnum_expr_lowbound = 0 - numexprs;
 
    /* Scan through each MVNDistinct entry */
    for (int i = 0; i < ndistinct->nitems; i++)
    {
        MVNDistinctItem item = ndistinct->items[i];
 
        /*
         * Cross-check each attribute in a MVNDistinct entry with the extended
         * stats object definition.
         */
        for (int j = 0; j < item.nattributes; j++)
        {
            AttrNumber  attnum = item.attributes[j];
            bool        ok = false;
 
            if (attnum > 0)
            {
                /* attribute number in stxkeys */
                for (int k = 0; k < stxkeys->dim1; k++)
                {
                    if (attnum == stxkeys->values[k])
                    {
                        ok = true;
                        break;
                    }
                }
            }
            else if ((attnum < 0) && (attnum >= attnum_expr_lowbound))
            {
                /* attribute number for an expression */
                ok = true;
            }
 
            if (!ok)
            {
                ereport(elevel,
                        (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
                         errmsg("could not validate \"%s\" object: invalid attribute number %d found",
                                "pg_ndistinct", attnum)));
                return false;
            }
        }
    }
 
    return true;
}
 
/*
 * ndistinct_for_combination
 *      Estimates number of distinct values in a combination of columns.
 *
 * This uses the same ndistinct estimator as compute_scalar_stats() in
 * ANALYZE, i.e.,
 *      n*d / (n - f1 + f1*n/N)
 *
 * except that instead of values in a single column we are dealing with
 * combination of multiple columns.
 */
static double
ndistinct_for_combination(double totalrows, StatsBuildData *data,
                          int k, int *combination)
{
    int         i,
                j;
    int         f1,
                cnt,
                d;
    bool       *isnull;
    Datum      *values;
    SortItem   *items;
    MultiSortSupport mss;
    int         numrows = data->numrows;
 
    mss = multi_sort_init(k);
 
    /*
     * In order to determine the number of distinct elements, create separate
     * values[]/isnull[] arrays with all the data we have, then sort them
     * using the specified column combination as dimensions.  We could try to
     * sort in place, but it'd probably be more complex and bug-prone.
     */
    items = palloc_array(SortItem, numrows);
    values = palloc0_array(Datum, numrows * k);
    isnull = palloc0_array(bool, numrows * k);
 
    for (i = 0; i < numrows; i++)
    {
        items[i].values = &values[i * k];
        items[i].isnull = &isnull[i * k];
    }
 
    /*
     * For each dimension, set up sort-support and fill in the values from the
     * sample data.
     *
     * We use the column data types' default sort operators and collations;
     * perhaps at some point it'd be worth using column-specific collations?
     */
    for (i = 0; i < k; i++)
    {
        Oid         typid;
        TypeCacheEntry *type;
        Oid         collid = InvalidOid;
        VacAttrStats *colstat = data->stats[combination[i]];
 
        typid = colstat->attrtypid;
        collid = colstat->attrcollid;
 
        type = lookup_type_cache(typid, TYPECACHE_LT_OPR);
        if (type->lt_opr == InvalidOid) /* shouldn't happen */
            elog(ERROR, "cache lookup failed for ordering operator for type %u",
                 typid);
 
        /* prepare the sort function for this dimension */
        multi_sort_add_dimension(mss, i, type->lt_opr, collid);
 
        /* accumulate all the data for this dimension into the arrays */
        for (j = 0; j < numrows; j++)
        {
            items[j].values[i] = data->values[combination[i]][j];
            items[j].isnull[i] = data->nulls[combination[i]][j];
        }
    }
 
    /* We can sort the array now ... */
    qsort_interruptible(items, numrows, sizeof(SortItem),
                        multi_sort_compare, mss);
 
    /* ... and count the number of distinct combinations */
 
    f1 = 0;
    cnt = 1;
    d = 1;
    for (i = 1; i < numrows; i++)
    {
        if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
        {
            if (cnt == 1)
                f1 += 1;
 
            d++;
            cnt = 0;
        }
 
        cnt += 1;
    }
 
    if (cnt == 1)
        f1 += 1;
 
    return estimate_ndistinct(totalrows, numrows, d, f1);
}
 
/* The Duj1 estimator (already used in analyze.c). */
static double
estimate_ndistinct(double totalrows, int numrows, int d, int f1)
{
    double      numer,
                denom,
                ndistinct;
 
    numer = (double) numrows * (double) d;
 
    denom = (double) (numrows - f1) +
        (double) f1 * (double) numrows / totalrows;
 
    ndistinct = numer / denom;
 
    /* Clamp to sane range in case of roundoff error */
    if (ndistinct < (double) d)
        ndistinct = (double) d;
 
    if (ndistinct > totalrows)
        ndistinct = totalrows;
 
    return floor(ndistinct + 0.5);
}
 
/*
 * n_choose_k
 *      computes binomial coefficients using an algorithm that is both
 *      efficient and prevents overflows
 */
static int
n_choose_k(int n, int k)
{
    int         d,
                r;
 
    Assert((k > 0) && (n >= k));
 
    /* use symmetry of the binomial coefficients */
    k = Min(k, n - k);
 
    r = 1;
    for (d = 1; d <= k; ++d)
    {
        r *= n--;
        r /= d;
    }
 
    return r;
}
 
/*
 * num_combinations
 *      number of combinations, excluding single-value combinations
 */
static int
num_combinations(int n)
{
    return (1 << n) - (n + 1);
}
 
/*
 * generator_init
 *      initialize the generator of combinations
 *
 * The generator produces combinations of K elements in the interval (0..N).
 * We prebuild all the combinations in this method, which is simpler than
 * generating them on the fly.
 */
static CombinationGenerator *
generator_init(int n, int k)
{
    CombinationGenerator *state;
 
    Assert((n >= k) && (k > 0));
 
    /* allocate the generator state as a single chunk of memory */
    state = palloc_object(CombinationGenerator);
 
    state->ncombinations = n_choose_k(n, k);
 
    /* pre-allocate space for all combinations */
    state->combinations = palloc_array(int, k * state->ncombinations);
 
    state->current = 0;
    state->k = k;
    state->n = n;
 
    /* now actually pre-generate all the combinations of K elements */
    generate_combinations(state);
 
    /* make sure we got the expected number of combinations */
    Assert(state->current == state->ncombinations);
 
    /* reset the number, so we start with the first one */
    state->current = 0;
 
    return state;
}
 
/*
 * generator_next
 *      returns the next combination from the prebuilt list
 *
 * Returns a combination of K array indexes (0 .. N), as specified to
 * generator_init), or NULL when there are no more combination.
 */
static int *
generator_next(CombinationGenerator *state)
{
    if (state->current == state->ncombinations)
        return NULL;
 
    return &state->combinations[state->k * state->current++];
}
 
/*
 * generator_free
 *      free the internal state of the generator
 *
 * Releases the generator internal state (pre-built combinations).
 */
static void
generator_free(CombinationGenerator *state)
{
    pfree(state->combinations);
    pfree(state);
}
 
/*
 * generate_combinations_recurse
 *      given a prefix, generate all possible combinations
 *
 * Given a prefix (first few elements of the combination), generate following
 * elements recursively. We generate the combinations in lexicographic order,
 * which eliminates permutations of the same combination.
 */
static void
generate_combinations_recurse(CombinationGenerator *state,
                              int index, int start, int *current)
{
    /* If we haven't filled all the elements, simply recurse. */
    if (index < state->k)
    {
        int         i;
 
        /*
         * The values have to be in ascending order, so make sure we start
         * with the value passed by parameter.
         */
 
        for (i = start; i < state->n; i++)
        {
            current[index] = i;
            generate_combinations_recurse(state, (index + 1), (i + 1), current);
        }
 
        return;
    }
    else
    {
        /* we got a valid combination, add it to the array */
        memcpy(&state->combinations[(state->k * state->current)],
               current, state->k * sizeof(int));
        state->current++;
    }
}
 
/*
 * generate_combinations
 *      generate all k-combinations of N elements
 */
static void
generate_combinations(CombinationGenerator *state)
{
    int        *current = palloc0_array(int, state->k);
 
    generate_combinations_recurse(state, 0, 0, current);
 
    pfree(current);
}

SizeOfHeader

#define SizeOfHeader   (3 * sizeof(uint32))

Definition at line 42 of file mvdistinct.c.

SizeOfItem

#define SizeOfItem

(

natts

)

(sizeof(double) + sizeof(int) + (natts) * sizeof(AttrNumber))

Definition at line 45 of file mvdistinct.c.

Typedef Documentation

CombinationGenerator

typedef struct CombinationGenerator CombinationGenerator

Function Documentation

estimate_ndistinct()

static double estimate_ndistinct ( double  totalrows, int  numrows, int  d, int  f1  )

static

Definition at line 512 of file mvdistinct.c.

{
    double      numer,
                denom,
                ndistinct;
 
    numer = (double) numrows * (double) d;
 
    denom = (double) (numrows - f1) +
        (double) f1 * (double) numrows / totalrows;
 
    ndistinct = numer / denom;
 
    /* Clamp to sane range in case of roundoff error */
    if (ndistinct < (double) d)
        ndistinct = (double) d;
 
    if (ndistinct > totalrows)
        ndistinct = totalrows;
 
    return floor(ndistinct + 0.5);
}

References f1, and fb().

Referenced by ndistinct_for_combination().

generate_combinations()

static void generate_combinations ( CombinationGenerator *  state )

static

Definition at line 683 of file mvdistinct.c.

{
    int        *current = palloc0_array(int, state->k);
 
    generate_combinations_recurse(state, 0, 0, current);
 
    pfree(current);
}

References generate_combinations_recurse(), palloc0_array, and pfree().

Referenced by generator_init().

generate_combinations_recurse()

static void generate_combinations_recurse ( CombinationGenerator *  state, int  index, int  start, int *  current  )

static

Definition at line 648 of file mvdistinct.c.

{
    /* If we haven't filled all the elements, simply recurse. */
    if (index < state->k)
    {
        int         i;
 
        /*
         * The values have to be in ascending order, so make sure we start
         * with the value passed by parameter.
         */
 
        for (i = start; i < state->n; i++)
        {
            current[index] = i;
            generate_combinations_recurse(state, (index + 1), (i + 1), current);
        }
 
        return;
    }
    else
    {
        /* we got a valid combination, add it to the array */
        memcpy(&state->combinations[(state->k * state->current)],
               current, state->k * sizeof(int));
        state->current++;
    }
}

References fb(), generate_combinations_recurse(), i, and start.

Referenced by generate_combinations(), and generate_combinations_recurse().

generator_free()

static void generator_free ( CombinationGenerator *  state )

static

Definition at line 633 of file mvdistinct.c.

{
    pfree(state->combinations);
    pfree(state);
}

References pfree().

Referenced by statext_ndistinct_build().

generator_init()

static CombinationGenerator * generator_init ( int  n, int  k  )

static

Definition at line 580 of file mvdistinct.c.

{
    CombinationGenerator *state;
 
    Assert((n >= k) && (k > 0));
 
    /* allocate the generator state as a single chunk of memory */
    state = palloc_object(CombinationGenerator);
 
    state->ncombinations = n_choose_k(n, k);
 
    /* pre-allocate space for all combinations */
    state->combinations = palloc_array(int, k * state->ncombinations);
 
    state->current = 0;
    state->k = k;
    state->n = n;
 
    /* now actually pre-generate all the combinations of K elements */
    generate_combinations(state);
 
    /* make sure we got the expected number of combinations */
    Assert(state->current == state->ncombinations);
 
    /* reset the number, so we start with the first one */
    state->current = 0;
 
    return state;
}

References Assert, generate_combinations(), n_choose_k(), palloc_array, and palloc_object.

Referenced by statext_ndistinct_build().

generator_next()

static int * generator_next ( CombinationGenerator *  state )

static

Definition at line 618 of file mvdistinct.c.

{
    if (state->current == state->ncombinations)
        return NULL;
 
    return &state->combinations[state->k * state->current++];
}

References fb().

Referenced by statext_ndistinct_build().

n_choose_k()

static int n_choose_k ( int  n, int  k  )

static

Definition at line 541 of file mvdistinct.c.

{
    int         d,
                r;
 
    Assert((k > 0) && (n >= k));
 
    /* use symmetry of the binomial coefficients */
    k = Min(k, n - k);
 
    r = 1;
    for (d = 1; d <= k; ++d)
    {
        r *= n--;
        r /= d;
    }
 
    return r;
}

References Assert, and Min.

Referenced by generator_init().

ndistinct_for_combination()

static double ndistinct_for_combination ( double  totalrows, StatsBuildData *  data, int  k, int *  combination  )

static

Definition at line 416 of file mvdistinct.c.

{
    int         i,
                j;
    int         f1,
                cnt,
                d;
    bool       *isnull;
    Datum      *values;
    SortItem   *items;
    MultiSortSupport mss;
    int         numrows = data->numrows;
 
    mss = multi_sort_init(k);
 
    /*
     * In order to determine the number of distinct elements, create separate
     * values[]/isnull[] arrays with all the data we have, then sort them
     * using the specified column combination as dimensions.  We could try to
     * sort in place, but it'd probably be more complex and bug-prone.
     */
    items = palloc_array(SortItem, numrows);
    values = palloc0_array(Datum, numrows * k);
    isnull = palloc0_array(bool, numrows * k);
 
    for (i = 0; i < numrows; i++)
    {
        items[i].values = &values[i * k];
        items[i].isnull = &isnull[i * k];
    }
 
    /*
     * For each dimension, set up sort-support and fill in the values from the
     * sample data.
     *
     * We use the column data types' default sort operators and collations;
     * perhaps at some point it'd be worth using column-specific collations?
     */
    for (i = 0; i < k; i++)
    {
        Oid         typid;
        TypeCacheEntry *type;
        Oid         collid = InvalidOid;
        VacAttrStats *colstat = data->stats[combination[i]];
 
        typid = colstat->attrtypid;
        collid = colstat->attrcollid;
 
        type = lookup_type_cache(typid, TYPECACHE_LT_OPR);
        if (type->lt_opr == InvalidOid) /* shouldn't happen */
            elog(ERROR, "cache lookup failed for ordering operator for type %u",
                 typid);
 
        /* prepare the sort function for this dimension */
        multi_sort_add_dimension(mss, i, type->lt_opr, collid);
 
        /* accumulate all the data for this dimension into the arrays */
        for (j = 0; j < numrows; j++)
        {
            items[j].values[i] = data->values[combination[i]][j];
            items[j].isnull[i] = data->nulls[combination[i]][j];
        }
    }
 
    /* We can sort the array now ... */
    qsort_interruptible(items, numrows, sizeof(SortItem),
                        multi_sort_compare, mss);
 
    /* ... and count the number of distinct combinations */
 
    f1 = 0;
    cnt = 1;
    d = 1;
    for (i = 1; i < numrows; i++)
    {
        if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
        {
            if (cnt == 1)
                f1 += 1;
 
            d++;
            cnt = 0;
        }
 
        cnt += 1;
    }
 
    if (cnt == 1)
        f1 += 1;
 
    return estimate_ndistinct(totalrows, numrows, d, f1);
}

References VacAttrStats::attrtypid, collid, data, elog, ERROR, estimate_ndistinct(), f1, fb(), i, InvalidOid, items, j, lookup_type_cache(), multi_sort_add_dimension(), multi_sort_compare(), multi_sort_init(), palloc0_array, palloc_array, qsort_interruptible(), type, TYPECACHE_LT_OPR, and values.

Referenced by statext_ndistinct_build().

num_combinations()

static int num_combinations ( int  n )

static

Definition at line 566 of file mvdistinct.c.

{
    return (1 << n) - (n + 1);
}

Referenced by statext_ndistinct_build().

statext_ndistinct_build()

MVNDistinct * statext_ndistinct_build	(	double	totalrows,
		StatsBuildData *	data
	)

Definition at line 85 of file mvdistinct.c.

{
    MVNDistinct *result;
    int         k;
    int         itemcnt;
    int         numattrs = data->nattnums;
    int         numcombs = num_combinations(numattrs);
 
    result = palloc(offsetof(MVNDistinct, items) +
                    numcombs * sizeof(MVNDistinctItem));
    result->magic = STATS_NDISTINCT_MAGIC;
    result->type = STATS_NDISTINCT_TYPE_BASIC;
    result->nitems = numcombs;
 
    itemcnt = 0;
    for (k = 2; k <= numattrs; k++)
    {
        int        *combination;
        CombinationGenerator *generator;
 
        /* generate combinations of K out of N elements */
        generator = generator_init(numattrs, k);
 
        while ((combination = generator_next(generator)))
        {
            MVNDistinctItem *item = &result->items[itemcnt];
            int         j;
 
            item->attributes = palloc_array(AttrNumber, k);
            item->nattributes = k;
 
            /* translate the indexes to attnums */
            for (j = 0; j < k; j++)
            {
                item->attributes[j] = data->attnums[combination[j]];
 
                Assert(AttributeNumberIsValid(item->attributes[j]));
            }
 
            item->ndistinct =
                ndistinct_for_combination(totalrows, data, k, combination);
 
            itemcnt++;
            Assert(itemcnt <= result->nitems);
        }
 
        generator_free(generator);
    }
 
    /* must consume exactly the whole output array */
    Assert(itemcnt == result->nitems);
 
    return result;
}

References Assert, AttributeNumberIsValid, MVNDistinctItem::attributes, data, fb(), generator_free(), generator_init(), generator_next(), MVNDistinct::items, items, j, MVNDistinct::magic, MVNDistinctItem::nattributes, MVNDistinctItem::ndistinct, ndistinct_for_combination(), MVNDistinct::nitems, nitems, num_combinations(), palloc(), palloc_array, STATS_NDISTINCT_MAGIC, STATS_NDISTINCT_TYPE_BASIC, and MVNDistinct::type.

Referenced by BuildRelationExtStatistics().

statext_ndistinct_deserialize()

MVNDistinct * statext_ndistinct_deserialize

(

bytea *

data

)

Definition at line 247 of file mvdistinct.c.

{
    int         i;
    Size        minimum_size;
    MVNDistinct ndist;
    MVNDistinct *ndistinct;
    char       *tmp;
 
    if (data == NULL)
        return NULL;
 
    /* we expect at least the basic fields of MVNDistinct struct */
    if (VARSIZE_ANY_EXHDR(data) < SizeOfHeader)
        elog(ERROR, "invalid MVNDistinct size %zu (expected at least %zu)",
             VARSIZE_ANY_EXHDR(data), SizeOfHeader);
 
    /* initialize pointer to the data part (skip the varlena header) */
    tmp = VARDATA_ANY(data);
 
    /* read the header fields and perform basic sanity checks */
    memcpy(&ndist.magic, tmp, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(&ndist.type, tmp, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(&ndist.nitems, tmp, sizeof(uint32));
    tmp += sizeof(uint32);
 
    if (ndist.magic != STATS_NDISTINCT_MAGIC)
        elog(ERROR, "invalid ndistinct magic %08x (expected %08x)",
             ndist.magic, STATS_NDISTINCT_MAGIC);
    if (ndist.type != STATS_NDISTINCT_TYPE_BASIC)
        elog(ERROR, "invalid ndistinct type %d (expected %d)",
             ndist.type, STATS_NDISTINCT_TYPE_BASIC);
    if (ndist.nitems == 0)
        elog(ERROR, "invalid zero-length item array in MVNDistinct");
 
    /* what minimum bytea size do we expect for those parameters */
    minimum_size = MinSizeOfItems(ndist.nitems);
    if (VARSIZE_ANY_EXHDR(data) < minimum_size)
        elog(ERROR, "invalid MVNDistinct size %zu (expected at least %zu)",
             VARSIZE_ANY_EXHDR(data), minimum_size);
 
    /*
     * Allocate space for the ndistinct items (no space for each item's
     * attnos: those live in bitmapsets allocated separately)
     */
    ndistinct = palloc0(MAXALIGN(offsetof(MVNDistinct, items)) +
                        (ndist.nitems * sizeof(MVNDistinctItem)));
    ndistinct->magic = ndist.magic;
    ndistinct->type = ndist.type;
    ndistinct->nitems = ndist.nitems;
 
    for (i = 0; i < ndistinct->nitems; i++)
    {
        MVNDistinctItem *item = &ndistinct->items[i];
 
        /* ndistinct value */
        memcpy(&item->ndistinct, tmp, sizeof(double));
        tmp += sizeof(double);
 
        /* number of attributes */
        memcpy(&item->nattributes, tmp, sizeof(int));
        tmp += sizeof(int);
        Assert((item->nattributes >= 2) && (item->nattributes <= STATS_MAX_DIMENSIONS));
 
        item->attributes
            = (AttrNumber *) palloc(item->nattributes * sizeof(AttrNumber));
 
        memcpy(item->attributes, tmp, sizeof(AttrNumber) * item->nattributes);
        tmp += sizeof(AttrNumber) * item->nattributes;
 
        /* still within the bytea */
        Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
    }
 
    /* we should have consumed the whole bytea exactly */
    Assert(tmp == ((char *) data + VARSIZE_ANY(data)));
 
    return ndistinct;
}

References Assert, MVNDistinctItem::attributes, data, elog, ERROR, fb(), i, MVNDistinct::items, items, MVNDistinct::magic, MAXALIGN, MinSizeOfItems, MVNDistinctItem::nattributes, MVNDistinctItem::ndistinct, MVNDistinct::nitems, palloc(), palloc0(), SizeOfHeader, STATS_MAX_DIMENSIONS, STATS_NDISTINCT_MAGIC, STATS_NDISTINCT_TYPE_BASIC, MVNDistinct::type, VARDATA_ANY(), VARSIZE_ANY(), and VARSIZE_ANY_EXHDR().

Referenced by extended_statistics_update(), pg_ndistinct_out(), and statext_ndistinct_load().

statext_ndistinct_free()

void statext_ndistinct_free

(

MVNDistinct *

ndistinct

)

Definition at line 332 of file mvdistinct.c.

{
    for (int i = 0; i < ndistinct->nitems; i++)
        pfree(ndistinct->items[i].attributes);
    pfree(ndistinct);
}

References MVNDistinctItem::attributes, i, MVNDistinct::items, MVNDistinct::nitems, and pfree().

Referenced by extended_statistics_update().

statext_ndistinct_load()

MVNDistinct * statext_ndistinct_load	(	Oid	mvoid,
		bool	inh
	)

Definition at line 145 of file mvdistinct.c.

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

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

Referenced by estimate_multivariate_ndistinct().

statext_ndistinct_serialize()

bytea * statext_ndistinct_serialize

(

MVNDistinct *

ndistinct

)

Definition at line 176 of file mvdistinct.c.

{
    int         i;
    bytea      *output;
    char       *tmp;
    Size        len;
 
    Assert(ndistinct->magic == STATS_NDISTINCT_MAGIC);
    Assert(ndistinct->type == STATS_NDISTINCT_TYPE_BASIC);
 
    /*
     * Base size is size of scalar fields in the struct, plus one base struct
     * for each item, including number of items for each.
     */
    len = VARHDRSZ + SizeOfHeader;
 
    /* and also include space for the actual attribute numbers */
    for (i = 0; i < ndistinct->nitems; i++)
    {
        int         nmembers;
 
        nmembers = ndistinct->items[i].nattributes;
        Assert(nmembers >= 2);
 
        len += SizeOfItem(nmembers);
    }
 
    output = (bytea *) palloc(len);
    SET_VARSIZE(output, len);
 
    tmp = VARDATA(output);
 
    /* Store the base struct values (magic, type, nitems) */
    memcpy(tmp, &ndistinct->magic, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(tmp, &ndistinct->type, sizeof(uint32));
    tmp += sizeof(uint32);
    memcpy(tmp, &ndistinct->nitems, sizeof(uint32));
    tmp += sizeof(uint32);
 
    /*
     * store number of attributes and attribute numbers for each entry
     */
    for (i = 0; i < ndistinct->nitems; i++)
    {
        MVNDistinctItem item = ndistinct->items[i];
        int         nmembers = item.nattributes;
 
        memcpy(tmp, &item.ndistinct, sizeof(double));
        tmp += sizeof(double);
        memcpy(tmp, &nmembers, sizeof(int));
        tmp += sizeof(int);
 
        memcpy(tmp, item.attributes, sizeof(AttrNumber) * nmembers);
        tmp += nmembers * sizeof(AttrNumber);
 
        /* protect against overflows */
        Assert(tmp <= ((char *) output + len));
    }
 
    /* check we used exactly the expected space */
    Assert(tmp == ((char *) output + len));
 
    return output;
}

References Assert, MVNDistinctItem::attributes, fb(), i, MVNDistinct::items, len, MVNDistinct::magic, MVNDistinctItem::nattributes, MVNDistinctItem::ndistinct, MVNDistinct::nitems, output, palloc(), SET_VARSIZE(), SizeOfHeader, SizeOfItem, STATS_NDISTINCT_MAGIC, STATS_NDISTINCT_TYPE_BASIC, MVNDistinct::type, VARDATA(), and VARHDRSZ.

Referenced by build_mvndistinct(), and statext_store().

statext_ndistinct_validate()

bool statext_ndistinct_validate	(	const MVNDistinct *	ndistinct,
		const int2vector *	stxkeys,
		int	numexprs,
		int	elevel
	)

Definition at line 352 of file mvdistinct.c.

{
    int         attnum_expr_lowbound = 0 - numexprs;
 
    /* Scan through each MVNDistinct entry */
    for (int i = 0; i < ndistinct->nitems; i++)
    {
        MVNDistinctItem item = ndistinct->items[i];
 
        /*
         * Cross-check each attribute in a MVNDistinct entry with the extended
         * stats object definition.
         */
        for (int j = 0; j < item.nattributes; j++)
        {
            AttrNumber  attnum = item.attributes[j];
            bool        ok = false;
 
            if (attnum > 0)
            {
                /* attribute number in stxkeys */
                for (int k = 0; k < stxkeys->dim1; k++)
                {
                    if (attnum == stxkeys->values[k])
                    {
                        ok = true;
                        break;
                    }
                }
            }
            else if ((attnum < 0) && (attnum >= attnum_expr_lowbound))
            {
                /* attribute number for an expression */
                ok = true;
            }
 
            if (!ok)
            {
                ereport(elevel,
                        (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
                         errmsg("could not validate \"%s\" object: invalid attribute number %d found",
                                "pg_ndistinct", attnum)));
                return false;
            }
        }
    }
 
    return true;
}

References attnum, MVNDistinctItem::attributes, ereport, errcode(), errmsg(), fb(), i, MVNDistinct::items, j, MVNDistinctItem::nattributes, and MVNDistinct::nitems.

Referenced by extended_statistics_update().