From: Tomas Vondra <tv@fuzzy.cz>
To: pgsql-hackers@postgresql.org
Subject: Re: WIP: multivariate statistics / proof of concept
Date: Mon, 10 Nov 2014 03:34:52 +0100
Message-ID: <5460244C.8080109@fuzzy.cz> (raw)
In-Reply-To: <CAApHDvrTaW9fmL=chUX7H9bqLS+-4vX3Ou9vA0J8hk0or-rBig@mail.gmail.com>
References: <543AFA15.4080608@fuzzy.cz>
<CAApHDvpHNGUkp=n=drHssZymoN2yuUwJGjGZZYYvYSwuifDd5A@mail.gmail.com>
<32d9bff1ca469f85d6fd3ad5db1237b2.squirrel@2.emaily.eu>
<CAApHDvrTaW9fmL=chUX7H9bqLS+-4vX3Ou9vA0J8hk0or-rBig@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 30.10.2014 10:23, David Rowley wrote:
> On Thu, Oct 30, 2014 at 12:21 AM, Tomas Vondra <tv@fuzzy.cz
> <mailto:tv@fuzzy.cz>> wrote:
>
> Dne 29 Říjen 2014, 10:41, David Rowley napsal(a):
> > I'm quite interested in reviewing your work on this, but it
> appears that
> > some of your changes are not C89:
> >
> > src\backend\commands\analyze.c(3774): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(3774): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(3774): error C2133: 'indexes' :
> unknown
> > size [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2133: 'ndistincts' :
> unknown
> > size [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2133: 'keys' :
> unknown size
> > [D:\Postgres\a\postgres.vcxproj]
> >
>
> I'll look into that. The thing is I don't have access to MSVC, so
> it's a bit difficult to spot / fix those issues :-(
>
>
> It should be a pretty simple fix, just use the files and line
> numbers from the above. It's just a problem that in those 3 places
> you're declaring an array of a variable size, which is not allowed in
> C89. The thing to do instead would just be to palloc() the size you
> need and the pfree() it when you're done.
Attached is a patch that should fix these issues.
The bad news is there are a few installcheck failures (and were in the
previous patch, but I haven't noticed for some reason). Apparently,
there's some mixup in how the patch handles Var->varno in some causes,
causing issues with a handful of regression tests.
The problem is that is_mv_compatible (checking whether the condition is
compatible with multivariate stats) does this
if (! ((varRelid == 0) || (varRelid == var->varno)))
return false;
/* Also skip special varno values, and system attributes ... */
if ((IS_SPECIAL_VARNO(var->varno)) ||
(! AttrNumberIsForUserDefinedAttr(var->varattno)))
return false;
assuming that after this, varno represents an index into the range
table, and passes it out to the caller.
And the caller (collect_mv_attnums) does this:
RelOptInfo *rel = find_base_rel(root, varno);
which fails with errors like these:
ERROR: no relation entry for relid 0
ERROR: no relation entry for relid 1880
or whatever. What's even stranger is this:
regression=# SELECT table_name, is_updatable, is_insertable_into
regression-# FROM information_schema.views
regression-# WHERE table_name = 'rw_view1';
ERROR: no relation entry for relid 0
regression=# SELECT table_name, is_updatable, is_insertable_into
regression-# FROM information_schema.views
regression-# ;
regression=# SELECT table_name, is_updatable, is_insertable_into
regression-# FROM information_schema.views
regression-# WHERE table_name = 'rw_view1';
table_name | is_updatable | is_insertable_into
------------+--------------+--------------------
(0 rows)
regression=# explain SELECT table_name, is_updatable, is_insertable_into
FROM information_schema.views
WHERE table_name = 'rw_view1';
ERROR: no relation entry for relid 0
So, the query fails. After removing the WHERE clause it works, and this
somehow fixes the original query (with the WHERE clause). Nevertheless,
I still can't do explain on the query.
Clearly, I'm doing something wrong. I suspect it's caused either by
conditions involving function calls, or the fact that the view is a join
of multiple tables. But what?
For simple queries (single table, ...) it seems to be working fine.
regards
Tomas
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:
[text/x-diff] multivar-stats-v2.patch (161.6K, ../5460244C.8080109@fuzzy.cz/2-multivar-stats-v2.patch)
download | inline diff:diff --git a/src/backend/catalog/Makefile b/src/backend/catalog/Makefileindex b257b02..6e63afe 100644--- a/src/backend/catalog/Makefile+++ b/src/backend/catalog/Makefile@@ -32,6 +32,7 @@ POSTGRES_BKI_SRCS = $(addprefix $(top_srcdir)/src/include/catalog/,\
pg_attrdef.h pg_constraint.h pg_inherits.h pg_index.h pg_operator.h \
pg_opfamily.h pg_opclass.h pg_am.h pg_amop.h pg_amproc.h \
pg_language.h pg_largeobject_metadata.h pg_largeobject.h pg_aggregate.h \
+ pg_mv_statistic.h \
pg_statistic.h pg_rewrite.h pg_trigger.h pg_event_trigger.h pg_description.h \
pg_cast.h pg_enum.h pg_namespace.h pg_conversion.h pg_depend.h \
pg_database.h pg_db_role_setting.h pg_tablespace.h pg_pltemplate.h \
diff --git a/src/backend/catalog/system_views.sql b/src/backend/catalog/system_views.sqlindex a819952..bb82fe8 100644--- a/src/backend/catalog/system_views.sql+++ b/src/backend/catalog/system_views.sql@@ -152,6 +152,18 @@ CREATE VIEW pg_indexes AS
LEFT JOIN pg_tablespace T ON (T.oid = I.reltablespace)
WHERE C.relkind IN ('r', 'm') AND I.relkind = 'i';
+CREATE VIEW pg_mv_stats AS+ SELECT+ N.nspname AS schemaname,+ C.relname AS tablename,+ S.stakeys AS attnums,+ length(S.stamcv) AS mcvbytes,+ pg_mv_stats_mvclist_info(S.stamcv) AS mcvinfo,+ length(S.stahist) AS histbytes,+ pg_mv_stats_histogram_info(S.stahist) AS histinfo+ FROM (pg_mv_statistic S JOIN pg_class C ON (C.oid = S.starelid))+ LEFT JOIN pg_namespace N ON (N.oid = C.relnamespace);+
CREATE VIEW pg_stats AS
SELECT
nspname AS schemaname,
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.cindex 954e5a6..32e0d07 100644--- a/src/backend/commands/analyze.c+++ b/src/backend/commands/analyze.c@@ -27,6 +27,7 @@
#include "catalog/indexing.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_inherits_fn.h"
+#include "catalog/pg_mv_statistic.h"
#include "catalog/pg_namespace.h"
#include "commands/dbcommands.h"
#include "commands/tablecmds.h"
@@ -54,7 +55,11 @@
#include "utils/syscache.h"
#include "utils/timestamp.h"
#include "utils/tqual.h"
+#include "utils/fmgroids.h"+#include "utils/builtins.h"+#include "utils/mvstats.h"+#include "access/sysattr.h"
/* Data structure for Algorithm S from Knuth 3.4.2 */
typedef struct
@@ -111,6 +116,62 @@ static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
static Datum ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
+/* multivariate statistics (histogram, MCV list, associative rules) */++static void build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,+ int natts, VacAttrStats **vacattrstats);+static void update_mv_stats(Oid relid,+ MVHistogram histogram, MCVList mcvlist);++/* multivariate histograms */+static MVHistogram build_mv_histogram(int numrows, HeapTuple *rows,+ int2vector *attrs,+ int attr_cnt, VacAttrStats **vacattrstats,+ int numrows_total);+static MVBucket create_initial_mv_bucket(int numrows, HeapTuple *rows,+ int2vector *attrs, int natts,+ VacAttrStats **vacattrstats);+static MVBucket select_bucket_to_partition(int nbuckets, MVBucket * buckets);+static MVBucket partition_bucket(MVBucket bucket, int2vector *attrs,+ int natts, VacAttrStats **vacattrstats);+static MVBucket copy_mv_bucket(MVBucket bucket, uint32 ndimensions);++static void update_bucket_ndistinct(MVBucket bucket, int2vector *attrs,+ VacAttrStats ** stats);+static void update_dimension_ndistinct(MVBucket bucket, int dimension,+ int2vector *attrs,+ VacAttrStats ** stats,+ bool update_boundaries);+/* multivariate MCV list */+static MCVList build_mv_mcvlist(int numrows, HeapTuple *rows,+ int2vector *attrs,+ int natts, VacAttrStats **vacattrstats,+ int *numrows_filtered);++/* multivariate associative rules */+static void build_mv_associations(int numrows, HeapTuple *rows,+ int2vector *attrs,+ int natts, VacAttrStats **vacattrstats);++/* serialization */+static bytea * serialize_mv_histogram(MVHistogram histogram);+static bytea * serialize_mv_mcvlist(MCVList mcvlist);++/* comparators, used when constructing multivariate stats */+static int compare_scalars_simple(const void *a, const void *b, void *arg);+static int compare_scalars_partition(const void *a, const void *b, void *arg);+static int compare_scalars_memcmp(const void *a, const void *b, void *arg);+static int compare_scalars_memcmp_2(const void *a, const void *b);++static VacAttrStats ** lookup_var_attr_stats(int2vector *attrs,+ int natts, VacAttrStats **vacattrstats);++/* some debugging methods */+#ifdef MVSTATS_DEBUG+static void print_mv_histogram_info(MVHistogram histogram);+#endif++
/*
* analyze_rel() -- analyze one relation
*/
@@ -472,6 +533,13 @@ do_analyze_rel(Relation onerel, VacuumStmt *vacstmt,
* all analyzable columns. We use a lower bound of 100 rows to avoid
* possible overflow in Vitter's algorithm. (Note: that will also be the
* target in the corner case where there are no analyzable columns.)
+ * + * FIXME This sample sizing is mostly OK when computing stats for+ * individual columns, but when computing multi-variate stats+ * for multivariate stats (histograms, mcv, ...) it's rather+ * insufficient. For small number of dimensions it works, but+ * for complex stats it'd be nice use sample proportional to+ * the table (say, 0.5% - 1%) instead of a fixed size.
*/
targrows = 100;
for (i = 0; i < attr_cnt; i++)
@@ -574,6 +642,9 @@ do_analyze_rel(Relation onerel, VacuumStmt *vacstmt,
update_attstats(RelationGetRelid(Irel[ind]), false,
thisdata->attr_cnt, thisdata->vacattrstats);
}
++ /* Build multivariate stats (if there are any). */+ build_mv_stats(onerel, numrows, rows, attr_cnt, vacattrstats);
}
/*
@@ -2815,3 +2886,1985 @@ compare_mcvs(const void *a, const void *b)
return da - db;
}
++/*+ * Compute requested multivariate stats, using the rows sampled for the+ * plain (single-column) stats.+ *+ * This fetches a list of stats from pg_mv_statistic, computes the stats+ * and serializes them back into the catalog (as bytea values).+ */+static void+build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,+ int natts, VacAttrStats **vacattrstats)+{+ int i;+ MVStats mvstats;+ int nmvstats;++ /*+ * Fetch defined MV groups from pg_mv_statistic, and then compute+ * the MV statistics (histograms for now).+ * + * TODO move this to a separate method or something ...+ */+ mvstats = list_mv_stats(RelationGetRelid(onerel), &nmvstats, false);++ for (i = 0; i < nmvstats; i++)+ {+ MCVList mcvlist = NULL;+ MVHistogram histogram = NULL;+ int numrows_filtered = 0;++ /* int2 vector of attnums the stats should be computed on */+ int2vector * attrs = mvstats[i].stakeys;++ /* check allowed number of dimensions */+ Assert((attrs->dim1 >= 2) && (attrs->dim1 <= MVSTATS_MAX_DIMENSIONS));++ /*+ * Analyze associations between pairs of columns.+ * + * FIXME store the identified associations back to pg_mv_statistic+ */+ build_mv_associations(numrows, rows, attrs, natts, vacattrstats);++ /* build the MCV list */+ mcvlist = build_mv_mcvlist(numrows, rows, attrs, natts, vacattrstats, &numrows_filtered);++ /*+ * Build a multivariate histogram on the columns.+ *+ * FIXME remove the rows used to build the MCV from the histogram.+ * Another option might be subtracting the MCV selectivities+ * from the histogram, but I'm not sure whether that works+ * accurately (maybe it introduces additional errors).+ */+ if (numrows_filtered > 0)+ histogram = build_mv_histogram(numrows_filtered, rows, attrs, natts, vacattrstats, numrows);++ /* store the histogram / MCV list in the catalog */+ update_mv_stats(mvstats[i].mvoid, histogram, mcvlist);++#ifdef MVSTATS_DEBUG+ print_mv_histogram_info(histogram);+#endif++ }+}++/*+ * Lookup the VacAttrStats info for the selected columns, with indexes+ * matching the attrs vector (to make it easy to work with when+ * computing multivariate stats).+ */+static VacAttrStats **+lookup_var_attr_stats(int2vector *attrs, int natts, VacAttrStats **vacattrstats)+{+ int i, j;+ int numattrs = attrs->dim1;+ VacAttrStats **stats = (VacAttrStats**)palloc0(numattrs * sizeof(VacAttrStats*));++ /* lookup VacAttrStats info for the requested columns (same attnum) */+ for (i = 0; i < numattrs; i++)+ {+ stats[i] = NULL;+ for (j = 0; j < natts; j++)+ {+ if (attrs->values[i] == vacattrstats[j]->tupattnum)+ {+ stats[i] = vacattrstats[j];+ break;+ }+ }++ /*+ * Check that we found the info, that the attnum matches and+ * that there's the requested 'lt' operator and that the type+ * is 'passed-by-value'.+ */+ Assert(stats[i] != NULL);+ Assert(stats[i]->tupattnum == attrs->values[i]);++ /* FIXME This is rather ugly way to check for 'ltopr' (which+ * is defined for 'scalar' attributes).+ */+ Assert(stats[i]->compute_stats == compute_scalar_stats);++ /* TODO remove the 'pass by value' requirement */+ Assert(stats[i]->attrtype->typbyval);+ }++ return stats;+}++/*+ * TODO Add ndistinct estimation, probably the one described in "Towards+ * Estimation Error Guarantees for Distinct Values, PODS 2000,+ * p. 268-279" (the ones called GEE, or maybe AE).+ *+ * TODO The "combined" ndistinct is more likely to scale with the number+ * of rows (in the table), because a single column behaving this+ * way is sufficient for such behavior.+ */+static MVBucket+create_initial_mv_bucket(int numrows, HeapTuple *rows, int2vector *attrs,+ int natts, VacAttrStats **vacattrstats)+{+ int i;+ int numattrs = attrs->dim1;++ /* info for the interesting attributes only */+ VacAttrStats **stats = lookup_var_attr_stats(attrs, natts, vacattrstats);++ /* resulting bucket */+ MVBucket bucket = (MVBucket)palloc0(sizeof(MVBucketData));++ Assert(numrows > 0);+ Assert(rows != NULL);+ Assert((numattrs >= 2) && (numattrs <= MVSTATS_MAX_DIMENSIONS));++ /* allocate the per-dimension arrays */+ bucket->ndistincts = (uint32*)palloc0(numattrs * sizeof(uint32));+ bucket->nullsonly = (bool*)palloc0(numattrs * sizeof(bool));++ /* inclusiveness boundaries - lower/upper bounds */+ bucket->min_inclusive = (bool*)palloc0(numattrs * sizeof(bool));+ bucket->max_inclusive = (bool*)palloc0(numattrs * sizeof(bool));++ /* lower/upper boundaries */+ bucket->min = (Datum*)palloc0(numattrs * sizeof(Datum));+ bucket->max = (Datum*)palloc0(numattrs * sizeof(Datum));++ /*+ * All the sample rows fall into the initial bucket.+ * + * FIXME This is wrong (unless all columns are NOT NULL), because we+ * skipped the NULL values.+ */+ bucket->numrows = numrows;+ bucket->ntuples = numrows;+ bucket->rows = rows;++ /*+ * Update the number of ndistinct combinations in the bucket (which+ * we use when selecting bucket to partition), and then number of+ * distinct values for each partition (which we use when choosing+ * which dimension to split).+ */+ update_bucket_ndistinct(bucket, attrs, stats);++ for (i = 0; i < numattrs; i++)+ update_dimension_ndistinct(bucket, i, attrs, stats, true);++ /*+ * The initial bucket was not split at all, so we'll start with the+ * first dimension in the next round (index = 0).+ */+ bucket->last_split_dimension = -1;++ return bucket;+}++/*+ * TODO Fix to handle arbitrarily-sized histograms (not just 2D ones)+ * and call the right output procedures (for the particular type).+ *+ * TODO This should somehow fetch info about the data types, and use+ * the appropriate output functions to print the boundary values.+ * Right now this prints the 8B value as an integer.+ *+ * TODO Also, provide a special function for 2D histogram, printing+ * a gnuplot script (with rectangles).+ *+ * TODO For string types (once supported) we can sort the strings first,+ * assign them a sequence of integers and use the original values+ * as labels.+ */+#ifdef MVSTATS_DEBUG+static void+print_mv_histogram_info(MVHistogram histogram)+{+ int i = 0;++ elog(WARNING, "histogram nbuckets=%d", histogram->nbuckets);++ for (i = 0; i < histogram->nbuckets; i++)+ {+ MVBucket bucket = histogram->buckets[i];+ elog(WARNING, " bucket %d : ndistinct=%f ntuples=%d min=[%ld, %ld], max=[%ld, %ld] distinct=[%d,%d]",+ i, bucket->ndistinct, bucket->numrows,+ bucket->min[0], bucket->min[1], bucket->max[0], bucket->max[1],+ bucket->ndistincts[0], bucket->ndistincts[1]);+ }+}+#endif++/*+ * A very simple partitioning selection criteria - choose the bucket+ * with the highest number of distinct values.+ *+ * Returns either pointer to the bucket selected to be partitioned,+ * or NULL if there are no buckets that may be split (i.e. all buckets+ * contain a single distinct value).+ *+ * TODO Consider other partitioning criteria (v-optimal, maxdiff etc.).+ *+ * TODO Allowing the bucket to degenerate to a single combination of+ * values makes it rather strange MCV list. Maybe we should use+ * higher lower boundary, or maybe make the selection criteria+ * more complex (e.g. consider number of rows in the bucket, etc.).+ *+ * That however is different from buckets 'degenerated' only for+ * some dimensions (e.g. half of them), which is perfectly+ * appropriate for statistics on a combination of low and high+ * cardinality columns.+ */+static MVBucket+select_bucket_to_partition(int nbuckets, MVBucket * buckets)+{+ int i;+ int ndistinct = 1; /* if ndistinct=1, we can't split the bucket */+ MVBucket bucket = NULL;++ for (i = 0; i < nbuckets; i++)+ {+ /* if the ndistinct count is higher, use this bucket */+ if (buckets[i]->ndistinct > ndistinct) {+ bucket = buckets[i];+ ndistinct = buckets[i]->ndistinct;+ }+ }++ /* may be NULL if there are not buckets with (ndistinct>1) */+ return bucket;+}++/*+ * A simple bucket partitioning implementation - splits the dimensions in+ * a round-robin manner (considering only those with ndistinct>1). That+ * is first a dimension 0 is split, then 1, 2, ... until reaching the+ * end of attribute list, and then wrapping back to 0. Of course,+ * dimensions with a single distinct value are skipped.+ *+ * This is essentially what Muralikrishna/DeWitt described in their SIGMOD+ * article (M. Muralikrishna, David J. DeWitt: Equi-Depth Histograms For+ * Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD+ * Conference 1988: 28-36).+ *+ * There are multiple histogram options, centered around the partitioning+ * criteria, specifying both how to choose a bucket and the dimension+ * most in need of a split. For a nice summary and general overview, see+ * "rK-Hist : an R-Tree based histogram for multi-dimensional selectivity+ * estimation" thesis by J. A. Lopez, Concordia University, p.34-37 (and+ * possibly p. 32-34 for explanation of the terms).+ * + * This splits the bucket by tweaking the existing one, and returning the+ * new bucket (essentially shrinking the existing one in-place and returning+ * the other "half" as a new bucket). The caller is responsible for adding+ * the new bucket into the list of buckets.+ *+ * TODO It requires care to prevent splitting only one dimension and not+ * splitting another one at all (which might happen easily in case of+ * strongly dependent columns - e.g. y=x).+ *+ * TODO Should probably consider statistics target for the columns (e.g. to+ * split dimensions with higher statistics target more frequently).+ */+static MVBucket+partition_bucket(MVBucket bucket, int2vector *attrs,+ int natts, VacAttrStats **vacattrstats)+{+ int i;+ int dimension;+ int numattrs = attrs->dim1;++ Datum split_value;+ MVBucket new_bucket;++ /* needed for sort, when looking for the split value */+ bool isNull;+ int nvalues = 0;+ StdAnalyzeData * mystats = NULL;+ ScalarItem * values = (ScalarItem*)palloc0(bucket->numrows * sizeof(ScalarItem));+ SortSupportData ssup;++ /* looking for the split value */+ int ndistinct = 1; /* number of distinct values below current value */+ int nrows = 1; /* number of rows below current value */++ /* needed when splitting the values */+ HeapTuple * oldrows = bucket->rows;+ int oldnrows = bucket->numrows;++ /* info for the interesting attributes only */+ VacAttrStats **stats = lookup_var_attr_stats(attrs, natts, vacattrstats);++ /*+ * We can't split buckets with a single distinct value (this also+ * disqualifies NULL-only dimensions). Also, there has to be multiple+ * sample rows (otherwise, how could there be more distinct values).+ */+ Assert(bucket->ndistinct > 1);+ Assert(bucket->numrows > 1);+ Assert((numattrs >= 2) && (numattrs <= MVSTATS_MAX_DIMENSIONS));++ /*+ * Look for the next dimension to split, in a round robin manner.+ * We'll use the first one with (ndistinct > 1).+ *+ * If we happen to wrap around, something clearly went wrong (we+ * can't mess with the last_split_dimension directly, because we+ * couldn't do this check).+ */+ dimension = bucket->last_split_dimension;+ while (true)+ {+ dimension = (dimension + 1) % numattrs;++ if (bucket->ndistincts[dimension] > 1)+ break;++ /* if we ran the previous split dimension, it's infinite loop */+ Assert(dimension != bucket->last_split_dimension);+ }++ /* Remember the dimension for the next split of this bucket. */+ bucket->last_split_dimension = dimension;++ /*+ * Walk through the selected dimension, collect and sort the values+ * and then choose the value to use as the new boundary.+ */+ mystats = (StdAnalyzeData *) stats[dimension]->extra_data;++ /* initialize sort support, etc. */+ memset(&ssup, 0, sizeof(ssup));+ ssup.ssup_cxt = CurrentMemoryContext;++ /* We always use the default collation for statistics */+ ssup.ssup_collation = DEFAULT_COLLATION_OID;+ ssup.ssup_nulls_first = false;++ PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);++ for (i = 0; i < bucket->numrows; i++)+ {+ /* remember the index of the sample row, to make the partitioning simpler */+ values[nvalues].value = heap_getattr(bucket->rows[i], attrs->values[dimension],+ stats[dimension]->tupDesc, &isNull);+ values[nvalues].tupno = i;++ /* no NULL values allowed here (we don't do splits by null-only dimensions) */+ Assert(!isNull);++ nvalues++;+ }++ /* sort the array (pass-by-value datum */+ qsort_arg((void *) values, nvalues, sizeof(ScalarItem),+ compare_scalars_partition, (void *) &ssup);++ /*+ * We know there are bucket->ndistincts[dimension] distinct values+ * in this dimension, and we want to split this into half, so walk+ * through the array and stop once we see (ndistinct/2) values.+ *+ * We always choose the "next" value, i.e. (n/2+1)-th distinct value,+ * and use it as an exclusive upper boundary (and inclusive lower+ * boundary).+ *+ * TODO Maybe we should use "average" of the two middle distinct+ * values (at least for even distinct counts), but that would+ * require being able to do an average (which does not work+ * for non-arithmetic types).+ *+ * TODO Another option is to look for a split that'd give about+ * 50% tuples (not distinct values) in each partition. That+ * might work better when there are a few very frequent+ * values, and many rare ones.+ */+ split_value = values[0].value;+ for (i = 1; i < bucket->numrows; i++)+ {+ /* count distinct values */+ if (values[i].value != values[i-1].value)+ ndistinct += 1;++ /* once we've seen 1/2 distinct values (and use the value) */+ if (ndistinct > bucket->ndistincts[dimension] / 2)+ {+ split_value = values[i].value;+ break;+ }++ /* keep track how many rows belong to the first bucket */+ nrows += 1;+ }++ Assert(nrows > 0);+ Assert(nrows < bucket->numrows);++ /* create the new bucket as a (incomplete) copy of the one being partitioned. */+ new_bucket = copy_mv_bucket(bucket, numattrs);++ /*+ * Do the actual split of the chosen dimension, using the split value as the+ * upper bound for the existing bucket, and lower bound for the new one.+ */+ bucket->max[dimension] = split_value;+ new_bucket->min[dimension] = split_value;++ bucket->max_inclusive[dimension] = false;+ new_bucket->max_inclusive[dimension] = true;++ /*+ * Redistribute the sample tuples using the 'ScalarItem->tupno'+ * index. We know 'nrows' rows should remain in the original+ * bucket and the rest goes to the new one.+ */++ bucket->rows = (HeapTuple*)palloc0(nrows * sizeof(HeapTuple));+ new_bucket->rows = (HeapTuple*)palloc0((oldnrows - nrows) * sizeof(HeapTuple));++ bucket->numrows = nrows;+ new_bucket->numrows = (oldnrows - nrows);++ /*+ * The first nrows should go to the first bucket, the rest should+ * go to the new one. Use the tupno field to get the actual HeapTuple+ * row from the original array of sample rows.+ */+ for (i = 0; i < nrows; i++)+ memcpy(&bucket->rows[i], &oldrows[values[i].tupno], sizeof(HeapTuple));++ for (i = nrows; i < oldnrows; i++)+ memcpy(&new_bucket->rows[i-nrows], &oldrows[values[i].tupno], sizeof(HeapTuple));++ /* update ndistinct values for the buckets (total and per dimension) */+ update_bucket_ndistinct(bucket, attrs, stats);+ update_bucket_ndistinct(new_bucket, attrs, stats);++ /*+ * TODO We don't need to do this for the dimension we used for split,+ * because we know how many distinct values went to each partition.+ */+ for (i = 0; i < numattrs; i++)+ {+ update_dimension_ndistinct(bucket, i, attrs, stats, false);+ update_dimension_ndistinct(new_bucket, i, attrs, stats, false);+ }++ pfree(oldrows);+ pfree(values);++ return new_bucket;+}++/*+ * Copy a histogram bucket. The copy does not include the build-time+ * data, i.e. sampled rows etc.+ */+static MVBucket+copy_mv_bucket(MVBucket bucket, uint32 ndimensions)+{+ MVBucket new_bucket = (MVBucket)palloc0(sizeof(MVBucketData));++ /* Copy only the attributes that will stay the same after the split, and+ * we'll recompute the rest after the split. */++ new_bucket->last_split_dimension = bucket->last_split_dimension;++ /* allocate the per-dimension arrays */+ new_bucket->ndistincts = (uint32*)palloc0(ndimensions * sizeof(uint32));+ new_bucket->nullsonly = (bool*)palloc0(ndimensions * sizeof(bool));++ /* inclusiveness boundaries - lower/upper bounds */+ new_bucket->min_inclusive = (bool*)palloc0(ndimensions * sizeof(bool));+ new_bucket->max_inclusive = (bool*)palloc0(ndimensions * sizeof(bool));++ /* lower/upper boundaries */+ new_bucket->min = (Datum*)palloc0(ndimensions * sizeof(Datum));+ new_bucket->max = (Datum*)palloc0(ndimensions * sizeof(Datum));++ /* copy data */+ memcpy(new_bucket->nullsonly, bucket->nullsonly, ndimensions * sizeof(bool));++ memcpy(new_bucket->min_inclusive, bucket->min_inclusive, ndimensions*sizeof(bool));+ memcpy(new_bucket->min, bucket->min, ndimensions*sizeof(Datum));++ memcpy(new_bucket->max_inclusive, bucket->max_inclusive, ndimensions*sizeof(bool));+ memcpy(new_bucket->max, bucket->max, ndimensions*sizeof(Datum));++ return new_bucket;+}++/*+ * Counts the number of distinct values in the bucket. This just copies+ * the Datum values into a simple array, and sorts them using memcmp-based+ * comparator. That means it only works for pass-by-value data types+ * (assuming they don't use collations etc.)+ * + * FIXME Make this work with all types (not just pass-by-value ones).+ * + * TODO This might evaluate and store the distinct counts for all+ * possible attribute combinations. The assumption is this might be+ * useful for estimating things like GROUP BY cardinalities (e.g.+ * in cases when some buckets contain a lot of low-frequency+ * combinations, and other buckets contain few high-frequency ones).+ *+ * But it's unclear whether it's worth the price. Computing this+ * is actually quite cheap, because it may be evaluated at the very+ * end, when the buckets are rather small (so sorting it in 2^N ways+ * is not a big deal). Assuming the partitioning algorithm does not+ * use these values to do the decisions, of course (the current+ * algorithm does not).+ *+ * The overhead with storing, fetching and parsing the data is more+ * concerning - adding 2^N values per bucket (even if it's just+ * a 1B or 2B value) would significantly bloat the histogram, and+ * thus the impact on optimizer. Which is not really desirable.+ * + * TODO This only updates the ndistinct for the sample (or bucket), but+ * we eventually need an estimate of the total number of distinct+ * values in the dataset. It's possible to either use the current+ * 1D approach (i.e., if it's more than 10% of the sample, assume+ * it's proportional to the number of rows). Or it's possible to+ * implement the estimator suggested in the article, supposedly+ * giving 'optimal' estimates (w.r.t. probability of error).+ */+static void+update_bucket_ndistinct(MVBucket bucket, int2vector *attrs, VacAttrStats ** stats)+{+ int i, j, idx = 0;+ int numattrs = attrs->dim1;+ Size len = sizeof(Datum) * numattrs;+ bool isNull;++ /*+ * We could collect this while walking through all the attributes+ * above (this way we have to call heap_getattr twice).+ */+ Datum * values = palloc0(bucket->numrows * numattrs * sizeof(Datum));++ for (j = 0; j < bucket->numrows; j++)+ for (i = 0; i < numattrs; i++)+ values[idx++] = heap_getattr(bucket->rows[j], attrs->values[i],+ stats[i]->tupDesc, &isNull);++ qsort_arg((void *) values, bucket->numrows, sizeof(Datum) * numattrs,+ compare_scalars_memcmp, &len);++ bucket->ndistinct = 1;++ for (i = 1; i < bucket->numrows; i++)+ if (memcmp(&values[i * numattrs], &values[(i-1) * numattrs], len) != 0)+ bucket->ndistinct += 1;++ pfree(values);++}++/*+ * Count distinct values per bucket dimension.+ *+ * TODO Remove unnecessary parameters - don't pass in the whole arrays,+ * just the proper elements.+ */+static void+update_dimension_ndistinct(MVBucket bucket, int dimension, int2vector *attrs,+ VacAttrStats ** stats, bool update_boundaries)+{+ int j;+ int nvalues = 0;+ bool isNull;+ Datum * values = (Datum*)palloc0(bucket->numrows * sizeof(Datum));+ SortSupportData ssup;++ StdAnalyzeData * mystats = (StdAnalyzeData *) stats[dimension]->extra_data;++ memset(&ssup, 0, sizeof(ssup));+ ssup.ssup_cxt = CurrentMemoryContext;++ /* We always use the default collation for statistics */+ ssup.ssup_collation = DEFAULT_COLLATION_OID;+ ssup.ssup_nulls_first = false;++ PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);++ for (j = 0; j < bucket->numrows; j++)+ {+ values[nvalues] = heap_getattr(bucket->rows[j], attrs->values[dimension],+ stats[dimension]->tupDesc, &isNull);++ /* ignore NULL values */+ if (! isNull)+ nvalues++;+ }++ /* there's always at least 1 distinct value (may be NULL) */+ bucket->ndistincts[dimension] = 1;++ /* if there are only NULL values in the column, mark it so and continue+ * with the next one */+ if (nvalues == 0)+ {+ pfree(values);+ bucket->nullsonly[dimension] = true;+ return;+ }++ /* sort the array (pass-by-value datum */+ qsort_arg((void *) values, nvalues, sizeof(Datum),+ compare_scalars_simple, (void *) &ssup);++ /*+ * Update min/max boundaries to the smallest bounding box. Generally, this+ * needs to be done only when constructing the initial bucket.+ */+ if (update_boundaries)+ {+ /* store the min/max values */+ bucket->min[dimension] = values[0];+ bucket->min_inclusive[dimension] = true;++ bucket->max[dimension] = values[nvalues-1];+ bucket->max_inclusive[dimension] = true;+ }++ /*+ * Walk through the array and count distinct values by comparing+ * succeeding values.+ * + * FIXME This only works for pass-by-value types (i.e. not VARCHARs etc.).+ */+ for (j = 1; j < nvalues; j++) {+ if (values[j] != values[j-1])+ bucket->ndistincts[dimension] += 1;+ }++ pfree(values);+}++/*+ * Fetch list of MV stats defined on a table, without the actual data+ * for histograms, MCV lists etc.+ */+MVStats+list_mv_stats(Oid relid, int *nstats, bool built_only)+{+ Relation indrel;+ SysScanDesc indscan;+ ScanKeyData skey;+ HeapTuple htup;+ MVStats result;++ /* start with 16 items, that should be enough for most cases */+ int maxitems = 16;+ result = (MVStats)palloc0(sizeof(MVStatsData) * maxitems);+ *nstats = 0;++ /* Prepare to scan pg_mv_statistic for entries having indrelid = this rel. */+ ScanKeyInit(&skey,+ Anum_pg_mv_statistic_starelid,+ BTEqualStrategyNumber, F_OIDEQ,+ ObjectIdGetDatum(relid));++ indrel = heap_open(MvStatisticRelationId, AccessShareLock);+ indscan = systable_beginscan(indrel, MvStatisticRelidIndexId, true,+ NULL, 1, &skey);++ while (HeapTupleIsValid(htup = systable_getnext(indscan)))+ {+ Form_pg_mv_statistic stats = (Form_pg_mv_statistic) GETSTRUCT(htup);++ /*+ * Skip statistics that were not computed yet (if only stats+ * that were already built were requested)+ */+ if (built_only && (! (stats->hist_built || stats->mcv_built || stats->assoc_built)))+ continue;++ /* double the array size if needed */+ if (*nstats == maxitems)+ {+ maxitems *= 2;+ result = (MVStats)repalloc(result, sizeof(MVStatsData) * maxitems);+ }++ result[*nstats].mvoid = HeapTupleGetOid(htup);+ result[*nstats].stakeys = buildint2vector(stats->stakeys.values, stats->stakeys.dim1);+ result[*nstats].hist_built = stats->hist_built;+ result[*nstats].mcv_built = stats->mcv_built;+ result[*nstats].assoc_built = stats->assoc_built;+ *nstats += 1;+ }++ systable_endscan(indscan);++ heap_close(indrel, AccessShareLock);++ /* TODO maybe save the list into relcache, as in RelationGetIndexList+ * (which was used as an inspiration of this one)?. */++ return result;+}+++/*+ * Serialize the MV histogram into a bytea value.+ *+ * The serialized first deduplicates the boundary values into a separate+ * array, and uses 2B indexes when serializing the buckets. This stores+ * a significant amount of space because each bucket split adds a single+ * new boundary value, so e.g. with 4 attributes and 8191 splits (thus+ * 8192 buckets), there are only ~8200 distinct boundary values.+ *+ * But as each bucket has 8 boundary values (4+4), that's ~64k Datums.+ * That's roughly 65kB vs. 512kB, but we haven't included the indexes+ * used to reference the boundary values. By using int16 indexes (which+ * should be more than enough for all reasonable histogram sizes),+ * this amounts to ~128kB (8192*8*2). So in total it's ~196kB vs. 512kB,+ * i.e. more than 2x compression, which is nice.+ *+ * The implementation is simple - walk through the buckets, collect all+ * the boundary values, keep only distinct values (in a sorted array)+ * and then replace the values with indexes (using binary search).+ *+ * It's possible to either serialize/deserialize the histogram into+ * a MVHistogram, or create a special structure working with this+ * compressed structure (and keep MVBucket/MVHistogram only for the+ * building phase). This might actually work better thanks to better+ * CPU cache hit ratio, and simpler deserialization.+ *+ * This encoding will probably prevent automatic varlena compression,+ * because first part of the serialized bytea will be an array of unique+ * values (although sorted), and pglz decides whether to compress by+ * trying to compress the first part (~1kB or so). Which will be poor,+ * due to the lack of repetition.+ *+ * But in this case this is probably desirable - the data in general+ * won't be really compressible (in addition to the 2x compression we+ * got thanks to the encoding). In a sense the encoding scheme is+ * actually a context-aware compression (usually compressing to ~30%).+ * So this seems appropriate in this case.+ *+ * FIXME Make this work with arbitrary types.+ *+ * TODO Try to keep the compressed form, instead of deserializing it to+ * MVHistogram/MVBucket.+ *+ * TODO We might get a bit better compression by considering the actual+ * data type length. The current implementation treats all data as+ * 8B values, but for INT it's actually 4B etc. OTOH this is only+ * related to the lookup table, and most of the space is occupied+ * by the buckets (with int16 indexes). And we don't have type info+ * at the moment, so it would be difficult (but we'll nedd it to+ * support all types, so maybe then).+ */+static bytea *+serialize_mv_histogram(MVHistogram histogram)+{+ int i = 0, j = 0;++ /* total size (histogram header + all buckets) */+ Size total_len;+ char *tmp = NULL;+ bytea *result = NULL;++ /* we need to accumulate all boundary values (min/max) */+ int idx = 0;+ int max_values = histogram->nbuckets * histogram->ndimensions * 2;+ Datum * values = (Datum*)palloc0(max_values * sizeof(Datum));+ Size len = sizeof(Datum);++ /* we'll collect unique boundary values into this */+ int ndistinct = 0;+ Datum *lookup = NULL;+ uint16 *indexes = (uint16*)palloc0(sizeof(uint16) * histogram->ndimensions);++ /*+ * Collect the boundary values first, sort them and generate a small+ * array with only distinct values.+ */+ for (i = 0; i < histogram->nbuckets; i++)+ {+ for (j = 0; j < histogram->ndimensions; j++)+ {+ values[idx++] = histogram->buckets[i]->min[j];+ values[idx++] = histogram->buckets[i]->max[j];+ }+ }++ /*+ * We've allocated just enough space for all boundary values, but+ * this may change once we start handling NULL values (as we'll+ * probably skip those).+ *+ * Also, we expect at least one boundary value at this moment.+ */+ Assert(max_values == idx);+ Assert(idx > 1);++ /*+ * Sort the collected boundary values using a simple memcmp-based+ * comparator (this won't work for pass-by-reference types), and+ * then walk the data and count the distinct values.+ */+ qsort((void *) values, idx, len, compare_scalars_memcmp_2);++ ndistinct = 1;+ for (i = 1; i < max_values; i++)+ ndistinct += (values[i-1] != values[i]) ? 1 : 0;++ /*+ * At this moment we can allocate the bytea value (and we'll collect+ * the boundary values directly into it).+ *+ * The bytea will be structured like this:+ *+ * - varlena header : VARHDRSZ+ * - histogram header : offsetof(MVHistogram,buckets)+ * - number of boundary values : sizeof(uint32)+ * - boundary values : ndistinct * sizeof(Datum)+ * - buckets : nbuckets * BUCKET_SIZE_SERIALIZED+ *+ * We'll assume 2B indexes into the boundary values, because each+ * bucket 'split' introduces one boundary value. Moreover, multiple+ * splits may introduce the same value, so this should be enough for+ * at least 65k buckets (and likely more). That's more than enough+ * for reasonable histogram sizes.+ */++ Assert(ndistinct <= 65536);++ total_len = VARHDRSZ + offsetof(MVHistogramData, buckets) ++ (sizeof(uint32) + ndistinct * sizeof(Datum)) ++ histogram->nbuckets * BUCKET_SIZE_SERIALIZED(histogram->ndimensions);++ result = (bytea*)palloc0(total_len);+ tmp = VARDATA(result);++ SET_VARSIZE(result, total_len);++ /* copy the global histogram header */+ memcpy(tmp, histogram, offsetof(MVHistogramData, buckets));+ tmp += offsetof(MVHistogramData, buckets);++ /*+ * Copy the number of distinct values, and then all the distinct+ * values currently stored in the 'values' array (sorted).+ */+ memcpy(tmp, &ndistinct, sizeof(uint32));+ tmp += sizeof(uint32);++ lookup = (Datum*)tmp;++ for (i = 0; i < max_values; i++)+ {+ /* skip values that are equal to the previous one */+ if ((i > 0) && (values[i-1] == values[i]))+ continue;++ memcpy(tmp, &values[i], sizeof(Datum));+ tmp += sizeof(Datum);+ }++ Assert(tmp - (char*)lookup == ndistinct * sizeof(Datum));++ /* now serialize all the buckets - first the header, without the+ * variable-length part, then all the variable length parts */+ for (i = 0; i < histogram->nbuckets; i++)+ {+ MVBucket bucket = histogram->buckets[i];++ /* write the common bucket header */+ memcpy(tmp, bucket, offsetof(MVBucketData, ndistincts));+ tmp += offsetof(MVBucketData, ndistincts);++ /* per-dimension ndistincts / nullsonly */+ memcpy(tmp, bucket->ndistincts, sizeof(uint32)*histogram->ndimensions);+ tmp += sizeof(uint32)*histogram->ndimensions;++ memcpy(tmp, bucket->nullsonly, sizeof(bool)*histogram->ndimensions);+ tmp += sizeof(bool)*histogram->ndimensions;++ memcpy(tmp, bucket->min_inclusive, sizeof(bool)*histogram->ndimensions);+ tmp += sizeof(bool)*histogram->ndimensions;++ memcpy(tmp, bucket->max_inclusive, sizeof(bool)*histogram->ndimensions);+ tmp += sizeof(bool)*histogram->ndimensions;++ /* and now translate the min (and then max) boundaries to indexes */+ for (j = 0; j < histogram->ndimensions; j++)+ {+ Datum *v = (Datum*)bsearch(&bucket->min[j], lookup, ndistinct,+ sizeof(Datum), compare_scalars_memcmp_2);++ Assert(v != NULL);+ indexes[j] = (v - lookup); /* Datum arithmetics (not char) */+ Assert(indexes[j] < ndistinct); /* we have to be within the array */+ }++ memcpy(tmp, indexes, sizeof(uint16)*histogram->ndimensions);+ tmp += sizeof(uint16)*histogram->ndimensions;++ for (j = 0; j < histogram->ndimensions; j++)+ {+ Datum *v = (Datum*)bsearch(&bucket->max[j], lookup, ndistinct,+ sizeof(Datum), compare_scalars_memcmp_2);+ Assert(v != NULL);+ indexes[j] = (v - lookup); /* Datum arithmetics (not char) */+ Assert(indexes[j] < ndistinct); /* we have to be within the array */+ }++ memcpy(tmp, indexes, sizeof(uint16)*histogram->ndimensions);+ tmp += sizeof(uint16)*histogram->ndimensions;+ }++ pfree(indexes);++ return result;+}++/*+ * Reverse to serialize histogram. This essentially expands the serialized+ * form back to MVHistogram / MVBucket.+ */+MVHistogram+deserialize_mv_histogram(bytea * data)+{+ int i = 0, j = 0;++ Size expected_length;+ char *tmp = NULL;+ MVHistogram histogram;++ uint32 nlookup; /* Datum lookup table */+ Datum *lookup = NULL;++ if (data == NULL)+ return NULL;++ /* get pointer to the data part of the varlena */+ tmp = VARDATA(data);++ histogram = (MVHistogram)palloc0(sizeof(MVHistogramData));++ /* copy the histogram header in place */+ memcpy(histogram, tmp, offsetof(MVHistogramData, buckets));+ tmp += offsetof(MVHistogramData, buckets);++ if (histogram->magic != MVHIST_MAGIC)+ {+ pfree(histogram);+ elog(WARNING, "not a MV Histogram (magic number mismatch)");+ return NULL;+ }++ Assert(histogram->type == MVHIST_TYPE_BASIC);+ Assert(histogram->nbuckets > 0);+ Assert(histogram->nbuckets <= MVHIST_MAX_BUCKETS);+ Assert(histogram->ndimensions > 0);+ Assert(histogram->ndimensions <= MVSTATS_MAX_DIMENSIONS);++ /* now, get the size of the lookup table */+ memcpy(&nlookup, tmp, sizeof(uint32));+ tmp += sizeof(uint32);+ lookup = (Datum*)tmp;++ /* skip to the first bucket */+ tmp += sizeof(Datum) * nlookup;++ /* check the total serialized length */+ expected_length = offsetof(MVHistogramData, buckets) ++ sizeof(uint32) + nlookup * sizeof(Datum) ++ histogram->nbuckets * BUCKET_SIZE_SERIALIZED(histogram->ndimensions);++ /* check serialized length */+ if (VARSIZE_ANY_EXHDR(data) != expected_length)+ {+ elog(ERROR, "invalid MV histogram serialized size (expected %ld, got %ld)",+ VARSIZE_ANY_EXHDR(data), expected_length);+ return NULL;+ }++ /* allocate bucket pointers */+ histogram->buckets = (MVBucket*)palloc0(histogram->nbuckets * sizeof(MVBucket));++ /* deserialize the buckets, one by one */+ for (i = 0; i < histogram->nbuckets; i++)+ {+ /* don't allocate space for the build-only fields */+ MVBucket bucket = (MVBucket)palloc0(offsetof(MVBucketData, rows));+ uint16 *indexes = NULL;++ /* write the common bucket header */+ memcpy(bucket, tmp, offsetof(MVBucketData, ndistincts));+ tmp += offsetof(MVBucketData, ndistincts);++ /* per-dimension ndistincts / nullsonly */+ bucket->ndistincts = (uint32*)palloc0(sizeof(uint32)*histogram->ndimensions);+ memcpy(bucket->ndistincts, tmp, sizeof(uint32)*histogram->ndimensions);+ tmp += sizeof(uint32)*histogram->ndimensions;++ bucket->nullsonly = (bool*)palloc0(sizeof(bool)*histogram->ndimensions);+ memcpy(bucket->nullsonly, tmp, sizeof(bool)*histogram->ndimensions);+ tmp += sizeof(bool)*histogram->ndimensions;++ bucket->min_inclusive = (bool*)palloc0(sizeof(bool)*histogram->ndimensions);+ memcpy(bucket->min_inclusive, tmp, sizeof(bool)*histogram->ndimensions);+ tmp += sizeof(bool)*histogram->ndimensions;++ bucket->max_inclusive = (bool*)palloc0(sizeof(bool)*histogram->ndimensions);+ memcpy(bucket->max_inclusive, tmp, sizeof(bool)*histogram->ndimensions);+ tmp += sizeof(bool)*histogram->ndimensions;++ /* translate the indexes back to Datum values */+ bucket->min = (Datum*)palloc0(sizeof(Datum)*histogram->ndimensions);+ bucket->max = (Datum*)palloc0(sizeof(Datum)*histogram->ndimensions);++ indexes = (uint16*)tmp;+ tmp += sizeof(uint16) * histogram->ndimensions;+ for (j = 0; j < histogram->ndimensions; j++)+ memcpy(&bucket->min[j], &lookup[indexes[j]], sizeof(Datum));++ indexes = (uint16*)tmp;+ tmp += sizeof(uint16) * histogram->ndimensions;+ for (j = 0; j < histogram->ndimensions; j++)+ memcpy(&bucket->max[j], &lookup[indexes[j]], sizeof(Datum));++ histogram->buckets[i] = bucket;+ }++ return histogram;+}++/*+ * Serialize MCV list into a bytea value.+ *+ * This does not use any kind of deduplication (compared to histogram+ * serialization), as we don't expect the same efficiency here.+ *+ * This simply writes a MCV header (number of items, ...) and then Datum+ * values for all attribute of a item, followed by the item frequency+ * (as a double).+ */+static bytea *+serialize_mv_mcvlist(MCVList mcvlist)+{+ int i;++ /* we need to store nitems, and each needs ndimension * Datum, plus a double */+ Size len = VARHDRSZ + offsetof(MCVListData, items) + mcvlist->nitems * (sizeof(Datum) * mcvlist->ndimensions + sizeof(double));++ bytea * output = (bytea*)palloc0(len);++ char * tmp = VARDATA(output);++ SET_VARSIZE(output, len);++ /* first, store the number of dimensions / items */+ memcpy(tmp, mcvlist, offsetof(MCVListData, items));+ tmp += offsetof(MCVListData, items);++ /* now, walk through the items and store values + frequency for each MCV item */+ for (i = 0; i < mcvlist->nitems; i++)+ {+ memcpy(tmp, mcvlist->items[i]->values, mcvlist->ndimensions * sizeof(Datum));+ tmp += mcvlist->ndimensions * sizeof(Datum);++ memcpy(tmp, &mcvlist->items[i]->frequency, sizeof(double));+ tmp += sizeof(double);+ }++ return output;++}++MCVList deserialize_mv_mcvlist(bytea * data)+{+ int i;+ Size expected_size;+ MCVList mcvlist;+ char *tmp;++ if (data == NULL)+ return NULL;++ if (VARSIZE_ANY_EXHDR(data) < offsetof(MCVListData,items))+ elog(ERROR, "invalid MCV Size %ld (expected at least %ld)",+ VARSIZE_ANY_EXHDR(data), offsetof(MCVListData,items));++ /* read the MCV list header */+ mcvlist = (MCVList)palloc0(sizeof(MCVListData));++ /* initialize pointer to the data part (skip the varlena header) */+ tmp = VARDATA(data);++ /* get the header and perform basic sanity checks */+ memcpy(mcvlist, tmp, offsetof(MCVListData,items));+ tmp += offsetof(MCVListData,items);++ if (mcvlist->magic != MVSTAT_MCV_MAGIC)+ elog(ERROR, "invalid MCV magic %d (expected %dd)",+ mcvlist->magic, MVSTAT_MCV_MAGIC);++ if (mcvlist->type != MVSTAT_MCV_TYPE_BASIC)+ elog(ERROR, "invalid MCV type %d (expected %dd)",+ mcvlist->type, MVSTAT_MCV_TYPE_BASIC);++ Assert(mcvlist->nitems > 0);+ Assert((mcvlist->ndimensions >= 2) && (mcvlist->ndimensions <= MVSTATS_MAX_DIMENSIONS));++ /* what bytea size do we expect for those parameters */+ expected_size = offsetof(MCVListData,items) ++ mcvlist->nitems * (sizeof(Datum) * mcvlist->ndimensions + sizeof(double));++ if (VARSIZE_ANY_EXHDR(data) != expected_size)+ elog(ERROR, "invalid MCV Size %ld (expected %ld)",+ VARSIZE_ANY_EXHDR(data), expected_size);++ /* allocate space for the MCV items */+ mcvlist->items = (MCVItem*)palloc0(sizeof(MCVItem) * mcvlist->nitems);++ for (i = 0; i < mcvlist->nitems; i++)+ {+ MCVItem item = (MCVItem)palloc0(offsetof(MCVItemData, values) ++ mcvlist->ndimensions * sizeof(Datum));++ memcpy(item->values, tmp, mcvlist->ndimensions * sizeof(Datum));+ tmp += mcvlist->ndimensions * sizeof(Datum);++ memcpy(&item->frequency, tmp, sizeof(double));+ tmp += sizeof(double);++ mcvlist->items[i] = item;+ }++ return mcvlist;+}++static void+update_mv_stats(Oid mvoid, MVHistogram histogram, MCVList mcvlist)+{+ HeapTuple stup,+ oldtup;+ Datum values[Natts_pg_mv_statistic];+ bool nulls[Natts_pg_mv_statistic];+ bool replaces[Natts_pg_mv_statistic];++ Relation sd = heap_open(MvStatisticRelationId, RowExclusiveLock);++ memset(nulls, 1, Natts_pg_mv_statistic * sizeof(bool));+ memset(replaces, 0, Natts_pg_mv_statistic * sizeof(bool));+ memset(values, 0, Natts_pg_mv_statistic * sizeof(Datum));++ /*+ * Construct a new pg_mv_statistic tuple - replace only the histogram+ * and MCV list, depending whether it actually was computed.+ */+ if (histogram != NULL)+ {+ nulls[Anum_pg_mv_statistic_stahist-1] = false;+ values[Anum_pg_mv_statistic_stahist - 1]+ = PointerGetDatum(serialize_mv_histogram(histogram));+ }++ if (mcvlist != NULL)+ {+ nulls[Anum_pg_mv_statistic_stamcv -1] = false;+ values[Anum_pg_mv_statistic_stamcv - 1]+ = PointerGetDatum(serialize_mv_mcvlist(mcvlist));+ }++ /* always replace the value (either by bytea or NULL) */+ replaces[Anum_pg_mv_statistic_stahist-1] = true;+ replaces[Anum_pg_mv_statistic_stamcv -1] = true;++ /* always change the availability flags */+ nulls[Anum_pg_mv_statistic_hist_built-1] = false;+ nulls[Anum_pg_mv_statistic_mcv_built -1] = false;++ replaces[Anum_pg_mv_statistic_hist_built -1] = true;+ replaces[Anum_pg_mv_statistic_mcv_built -1] = true;++ values[Anum_pg_mv_statistic_hist_built -1] = BoolGetDatum(histogram != NULL);+ values[Anum_pg_mv_statistic_mcv_built -1] = BoolGetDatum(mcvlist != NULL);++ /* Is there already a pg_mv_statistic tuple for this attribute? */+ oldtup = SearchSysCache1(MVSTATOID,+ ObjectIdGetDatum(mvoid));++ if (HeapTupleIsValid(oldtup))+ {+ /* Yes, replace it */+ stup = heap_modify_tuple(oldtup,+ RelationGetDescr(sd),+ values,+ nulls,+ replaces);+ ReleaseSysCache(oldtup);+ simple_heap_update(sd, &stup->t_self, stup);+ }+ else+ elog(ERROR, "invalid pg_mv_statistic record (oid=%d)", mvoid);++ /* update indexes too */+ CatalogUpdateIndexes(sd, stup);++ heap_freetuple(stup);++ heap_close(sd, RowExclusiveLock);+}+++/* MV stats */++Datum+pg_mv_stats_histogram_info(PG_FUNCTION_ARGS)+{+ bytea *data = PG_GETARG_BYTEA_P(0);+ char *result;++ MVHistogram hist = deserialize_mv_histogram(data);++ result = palloc0(128);+ snprintf(result, 128, "nbuckets=%d", hist->nbuckets);++ PG_RETURN_TEXT_P(cstring_to_text(result));+}++Datum+pg_mv_stats_mvclist_info(PG_FUNCTION_ARGS)+{+ bytea *data = PG_GETARG_BYTEA_P(0);+ char *result;++ MCVList mcvlist = deserialize_mv_mcvlist(data);++ result = palloc0(128);+ snprintf(result, 128, "nitems=%d", mcvlist->nitems);++ pfree(mcvlist);++ PG_RETURN_TEXT_P(cstring_to_text(result));+}++Datum+pg_mv_stats_histogram_gnuplot(PG_FUNCTION_ARGS)+{+ int i = 0;++ /* FIXME (handle the length properly using StringBuilder */+ Size len = 1024*1024;+ char *buffer = palloc0(len);+ char *str = buffer;+ bytea *data = PG_GETARG_BYTEA_P(0);++ MVHistogram hist = deserialize_mv_histogram(data);++ for (i = 0; i < hist->nbuckets; i++)+ {+ str += snprintf(str, len - (str - buffer),+ "set object %d rect from %ld,%ld to %ld,%ld lw 1\n",+ (i+1),+ hist->buckets[i]->min[0], hist->buckets[i]->min[1],+ hist->buckets[i]->max[0], hist->buckets[i]->max[1]);+ }++ PG_RETURN_TEXT_P(cstring_to_text(buffer));++}++bytea *+fetch_mv_histogram(Oid mvoid)+{+ Relation indrel;+ SysScanDesc indscan;+ ScanKeyData skey;+ HeapTuple htup;+ bytea *stahist = NULL;++ /* Prepare to scan pg_mv_statistic for entries having indrelid = this rel. */+ ScanKeyInit(&skey,+ ObjectIdAttributeNumber,+ BTEqualStrategyNumber, F_OIDEQ,+ ObjectIdGetDatum(mvoid));++ indrel = heap_open(MvStatisticRelationId, AccessShareLock);+ indscan = systable_beginscan(indrel, MvStatisticOidIndexId, true,+ NULL, 1, &skey);++ while (HeapTupleIsValid(htup = systable_getnext(indscan)))+ {+ bool isnull = false;+ Datum hist = SysCacheGetAttr(MVSTATOID, htup,+ Anum_pg_mv_statistic_stahist, &isnull);++ Assert(!isnull);++ stahist = DatumGetByteaP(hist);++ break;+ }++ systable_endscan(indscan);++ heap_close(indrel, AccessShareLock);++ /* TODO maybe save the list into relcache, as in RelationGetIndexList+ * (which was used as an inspiration of this one)?. */++ return stahist;+}++bytea *+fetch_mv_mcvlist(Oid mvoid)+{+ Relation indrel;+ SysScanDesc indscan;+ ScanKeyData skey;+ HeapTuple htup;+ bytea *mcvlist = NULL;++ /* Prepare to scan pg_mv_statistic for entries having indrelid = this rel. */+ ScanKeyInit(&skey,+ ObjectIdAttributeNumber,+ BTEqualStrategyNumber, F_OIDEQ,+ ObjectIdGetDatum(mvoid));++ indrel = heap_open(MvStatisticRelationId, AccessShareLock);+ indscan = systable_beginscan(indrel, MvStatisticOidIndexId, true,+ NULL, 1, &skey);++ while (HeapTupleIsValid(htup = systable_getnext(indscan)))+ {+ bool isnull = false;+ Datum tmp = SysCacheGetAttr(MVSTATOID, htup,+ Anum_pg_mv_statistic_stamcv, &isnull);++ Assert(!isnull);++ mcvlist = DatumGetByteaP(tmp);++ break;+ }++ systable_endscan(indscan);++ heap_close(indrel, AccessShareLock);++ /* TODO maybe save the list into relcache, as in RelationGetIndexList+ * (which was used as an inspiration of this one)?. */++ return mcvlist;+}++int+mv_get_index(AttrNumber varattno, int2vector * stakeys)+{+ int i, idx = 0;+ for (i = 0; i < stakeys->dim1; i++)+ {+ if (stakeys->values[i] < varattno)+ idx += 1;+ else+ break;+ }+ return idx;+}++/*+ * Building a multivariate algorithm. In short it first creates a single+ * bucket containing all the rows, and then repeatedly split is by first+ * searching for the bucket / dimension most in need of a split.+ *+ * The current criteria is rather simple, by looking at the number of+ * distinct values (combination of column values for bucket, column+ * values for a dimension). This is somehow naive, but seems to work+ * quite well. See the discussion at select_bucket_to_partition and+ * partition_bucket for more details about alternative algorithms.+ *+ * So the current algorithm looks like this:+ *+ * while [not reaching maximum number of buckets]+ *+ * choose bucket to partition (max distinct combinations)+ * if no bucket to partition+ * terminate the algorithm+ *+ * choose bucket dimension to partition (max distinct values)+ * split the bucket into two buckets+ *+ */+static MVHistogram+build_mv_histogram(int numrows, HeapTuple *rows, int2vector *attrs,+ int attr_cnt, VacAttrStats **vacattrstats,+ int numrows_total)+{+ int i;+ int ndistinct;+ int numattrs = attrs->dim1;+ int *ndistincts = (int*)palloc0(sizeof(int) * numattrs);++ MVHistogram histogram = (MVHistogram)palloc0(sizeof(MVHistogramData));++ HeapTuple * rows_copy = (HeapTuple*)palloc0(numrows * sizeof(HeapTuple));+ memcpy(rows_copy, rows, sizeof(HeapTuple) * numrows);++ Assert((numattrs >= 2) && (numattrs <= MVSTATS_MAX_DIMENSIONS));++ histogram->ndimensions = numattrs;++ histogram->magic = MVHIST_MAGIC;+ histogram->type = MVHIST_TYPE_BASIC;+ histogram->nbuckets = 1;++ /* create max buckets (better than repalloc for short-lived objects) */+ histogram->buckets = (MVBucket*)palloc0(MVHIST_MAX_BUCKETS * sizeof(MVBucket));++ /* create the initial bucket, covering the whole sample set */+ histogram->buckets[0] = create_initial_mv_bucket(numrows, rows_copy, attrs,+ attr_cnt, vacattrstats);++ ndistinct = histogram->buckets[0]->ndistinct;++ /* keep the global ndistinct values */+ for (i = 0; i < numattrs; i++)+ ndistincts[i] = histogram->buckets[0]->ndistincts[i];++ while (histogram->nbuckets < MVHIST_MAX_BUCKETS)+ {+ MVBucket bucket = select_bucket_to_partition(histogram->nbuckets, histogram->buckets);++ /* no more buckets to partition */+ if (bucket == NULL)+ break;++ histogram->buckets[histogram->nbuckets] = partition_bucket(bucket, attrs,+ attr_cnt, vacattrstats);++ histogram->nbuckets += 1;+ }++ /*+ * FIXME store the histogram in a catalog in a serialized form (simple for+ * pass-by-value, more complicated for buckets on varlena types)+ */+ for (i = 0; i < histogram->nbuckets; i++)+ {+ int d;+ histogram->buckets[i]->ntuples = (histogram->buckets[i]->numrows * 1.0) / numrows_total;+ histogram->buckets[i]->ndistinct = (histogram->buckets[i]->ndistinct * 1.0) / ndistinct;++ for (d = 0; d < numattrs; d++)+ histogram->buckets[i]->ndistincts[d] = (histogram->buckets[i]->ndistincts[d] * 1.0) / ndistincts[d];+ }++ pfree(ndistincts);++ return histogram;++}++/*+ * Mine associations between the columns, in the form (A => B).+ *+ * At the moment this only works for associations between two columns,+ * but it might be useful to mine for rules involving multiple columns+ * on the left side. That is rules [A,B] => C and so on. Handling+ * multiple columns on the right side is not necessary, because such+ * rules may be decomposed into a set of rules, one for each column.+ * I.e. A => [B,C] is exactly the same as (A => B) & (A => C).+ *+ * Those rules don't immediately identify redundant clauses, because the+ * user may choose "incompatible conditions" (e.g. by using a zip code+ * and a mismatching city) and so on. This should however be easy to+ * identify from a histogram, because the conditions will match a bucket+ * with low frequencies.+ *+ * The question is whether this can be useful when we have a histogram,+ * because such incompatible conditions should result in not matching+ * any buckets (or matching only buckets with low frequencies).+ *+ * The problem is that histograms work like this when the sorting is+ * compatible with the meaning of the data. We're often using data types+ * that support sorting (e.g. INT, BIGING) as a kind of labels where+ * the sorting really does not make much sense. Sorting by ZIP code will+ * result in sorting the cities quite randomly, and similarly for most+ * surrogate primary / foreign keys. In such cases the histograms are+ * pretty useless.+ *+ * So, a good approach might be testing the independence of the data+ * (by building a contingency table) and buildint the MV histogram only+ * when there's a dependency. For the 'label' data this should notice+ * the histogram is useless. So we won't build it (and we may use that+ * as a sign supporting the association rule).+ *+ * Another option is to look at selectivity of A and B separately, and+ * then use the minimum of those.+ *+ * TODO investigate using histogram and MCV list to confirm the+ * associative rule+ *+ * TODO investigate statistical testing of the distribution (to decide+ * whether it makes sense to build the histogram)+ *+ * TODO Using a min/max of selectivities would probably make more sense+ * for the associated columns.+ */+static void+build_mv_associations(int numrows, HeapTuple *rows, int2vector *attrs,+ int natts, VacAttrStats **vacattrstats)+{+ int i;+ bool isNull;+ Size len = 2 * sizeof(Datum); /* only simple associations a => b */+ int numattrs = attrs->dim1;++ /* TODO Maybe this should be somehow related to the number of+ * distinct columns in the two columns we're currently analyzing.+ * Assuming the distribution is uniform, we should expected to+ * observe in the sample - we can then use the average group+ * size as a threshold. That seems better than a static approach.+ */+ int min_group_size = 10;++ /* dimension indexes we'll check for associations [a => b] */+ int dima, dimb;++ /* info for the interesting attributes only+ * + * TODO Compute this only once and pass it to all the methods+ * that need it.+ */+ VacAttrStats **stats = lookup_var_attr_stats(attrs, natts, vacattrstats);++ /* We'll reuse the same array for all the combinations */+ Datum * values = (Datum*)palloc0(numrows * 2 * sizeof(Datum));++ Assert(numattrs >= 2);++ for (dima = 0; dima < numattrs; dima++)+ {++ for (dimb = 0; dimb < numattrs; dimb++)+ {++ int supporting = 0;+ int contradicting = 0;++ Datum val_a, val_b;+ int violations = 0;+ int group_size = 0;++ int supporting_rows = 0;++ /* skip (dima==dimb) */+ if (dima == dimb)+ continue;++ /*+ * FIXME Not sure if this handles NULL values properly (not sure+ * how to do that). We assume that NULL means 0 for now,+ * handling it just like any other value.+ */+ for (i = 0; i < numrows; i++)+ {+ values[i*2] = heap_getattr(rows[i], attrs->values[dima], stats[dima]->tupDesc, &isNull);+ values[i*2+1] = heap_getattr(rows[i], attrs->values[dimb], stats[dimb]->tupDesc, &isNull);+ }++ qsort_arg((void *) values, numrows, sizeof(Datum) * 2, compare_scalars_memcmp, &len);++ /*+ * Walk through the array, split it into rows according to+ * the A value, and count distinct values in the other one.+ * If there's a single B value for the whole group, we count+ * it as supporting the association, otherwise we count it+ * as contradicting.+ * + * Furthermore we require a group to have at least a certain+ * number of rows to be considered useful. When contradicting,+ * use it always.+ */++ /* start with values from the first row */+ val_a = values[0];+ val_b = values[1];+ group_size = 1;++ for (i = 1; i < numrows; i++)+ {+ if (values[2*i] != val_a) /* end of the group */+ {+ /*+ * If there are no contradicting rows, count it as+ * supporting (otherwise contradicting), but only if+ * the group is large enough.+ *+ * The requirement of a minimum group size makes it+ * impossible to identify [unique,unique] cases, but+ * that's probably a different case. This is more+ * about [zip => city] associations etc.+ */+ supporting += ((violations == 0) && (group_size >= min_group_size)) ? 1 : 0;+ contradicting += (violations != 0) ? 1 : 0;++ supporting_rows += ((violations == 0) && (group_size >= min_group_size)) ? group_size : 0;++ /* current values start a new group */+ val_a = values[2*i];+ val_b = values[2*i+1];+ violations = 0;+ group_size = 1;+ }+ else+ {+ if (values[2*i+1] != val_b) /* mismatch of a B value */+ {+ val_b = values[2*i+1];+ violations += 1;+ }++ group_size += 1;+ }+ }++ /* FIXME handle the last group */+ supporting += ((violations == 0) && (group_size >= min_group_size)) ? 1 : 0;+ contradicting += (violations != 0) ? 1 : 0;+ supporting_rows += ((violations == 0) && (group_size >= min_group_size)) ? group_size : 0;++ /*+ * See if the number of rows supporting the association is at least+ * 10x the number of rows violating the hypothetical rule.+ *+ * TODO This is rather arbitrary limit - I guess it's possible to do+ * some math to come up with a better rule (e.g. testing a hypothesis+ * 'this is due to randomness'). We can create a contingency table+ * from the values and use it for testing. Possibly only when+ * there are no contradicting rows?+ * + * TODO Also, if (a => b) and (b => a) at the same time, it pretty much+ * means the columns have the same values (or one is a 'label'),+ * making the conditions rather redundant. Although it's possible+ * that the query uses incompatible combination of values.+ */+ if (supporting_rows > (numrows - supporting_rows) * 10)+ {+ // elog(WARNING, "%d => %d : supporting=%d contradicting=%d", dima, dimb, supporting, contradicting);+ }++ }+ }++ pfree(values);++}++/*+ * Compute the list of most common items, where item is a combination of+ * values for all the columns. For small number of distinct values, we+ * may be able to represent the distribution pretty exactly, with+ * per-item statistics.+ *+ * If we can represent the distribution using a MCV list only, it's great+ * because that allows much better estimates (especially for equality).+ * Such discrete distributions are also easier to combine (more+ * efficient and more accurate) than when using histograms.+ *+ * FIXME This does not handle NULL values at the moment.+ *+ * TODO When computing equality selectivity (a=1 AND b=2), we can do that+ * pretty exactly assuming (a) we hit a MCV item and (b) the+ * histogram is built on those two columns only (i.e. there are no+ * other columns). In that case we can estimate the selectivity+ * using only the MCV.+ *+ * When we don't hit a MCV item, we can use the frequency of the+ * least probable MCV item as upper bound of the selectivity+ * (otherwise it'd get into the MCV list). Again, this only works+ * when the histogram size matches the restricted columns.+ *+ * When the histogram is larger (i.e. there are additional columns),+ * we can't be sure how is the selectivity distributed among the MCV+ * list and the histogram (we may get several MCV items matching+ * the conditions and several histogram buckets at the same time).+ *+ * In this case we can probably clamp the selectivity by minimum of+ * selectivities for each condition. For example if we know the+ * number of distinct values for each column, we can use 1/ndistinct+ * as a per-column estimate. Or rather 1/ndistinct + selectivity+ * derived from the MCV list.+ *+ * If there's no histogram (thus the distribution is approximated+ * only by the MCV list), the size of the stats (whether there are+ * some other columns, not referenced in the conditions) does not+ * matter. We can do pretty accurate estimation using the MCV.+ *+ * TODO Currently there's no logic to consider building only a MCV list+ * (and not building the histogram at all).+ * + * TODO For types that don't reasonably support ordering (either because+ * the type does not support that or when the user adds some option+ * to the ADD STATISTICS command - e.g. UNSORTED_STATS), building+ * the histogram may be pointless and inefficient. This is esp.+ * true for varlena types that may be quite large and a large MCV+ * list may be a better choice, because it makes equality estimates+ * more accurate. Due to the unsorted nature, range queries on those+ * attributes are rather useless anyway.+ *+ * Another thing is that by restricting to MCV list and equality+ * conditions, we can use hash values instead of long varlena values.+ * The equality estimation will be very accurate.+ *+ * This however complicates matching the columns to available+ * statistics, as it will require matching clauses (not columns) to+ * stats. And it may get quite complex - e.g. what if there are+ * multiple clauses, each compatible with different stats subset?+ * + * FIXME Create a special-purpose type for MCV items (instead of a plain+ * Datum array, which is very difficult to work with).+ */+static MCVList+build_mv_mcvlist(int numrows, HeapTuple *rows, int2vector *attrs,+ int natts, VacAttrStats **vacattrstats,+ int *numrows_filtered)+{+ int i, j, idx = 0;+ int numattrs = attrs->dim1;+ Size len = sizeof(Datum) * numattrs;+ bool isNull;+ int ndistinct = 0;+ int mcv_threshold = 0;+ int count = 0;+ int nitems = 0;++ MCVList mcvlist = NULL;++ VacAttrStats **stats = lookup_var_attr_stats(attrs, natts, vacattrstats);++ /*+ * We could collect this while walking through all the attributes+ * above (this way we have to call heap_getattr twice).+ * + * TODO We're using Datum (8B), even for data types smaller than this+ * (notably int4 and float4). Maybe we could save some space here,+ * although it seems the bytea compression will handle it just fine.+ */+ Datum * values = palloc0(numrows * numattrs * sizeof(Datum));++ for (j = 0; j < numrows; j++)+ for (i = 0; i < numattrs; i++)+ values[idx++] = heap_getattr(rows[j], attrs->values[i], stats[i]->tupDesc, &isNull);++ qsort_arg((void *) values, numrows, sizeof(Datum) * numattrs, compare_scalars_memcmp, &len);++ /*+ * Count the number of distinct values - we need this to determine+ * the threshold (125% of the average frequency).+ */+ ndistinct = 1;+ for (i = 1; i < numrows; i++)+ if (memcmp(&values[i * numattrs], &values[(i-1) * numattrs], len) != 0)+ ndistinct += 1;++ /*+ * Determine how many groups actually exceed the threshold, and then+ * walk the array again and collect them into an array.+ * + * TODO for now the threshold is the same as in the single-column+ * case (average + 25%), but maybe that's worth revisiting+ * + * TODO see if we can fit all the distinct values in the MCV list+ */+ mcv_threshold = 1.25 * numrows / ndistinct;+ mcv_threshold = (mcv_threshold < 4) ? 4 : mcv_threshold;++ /*+ * If there are less than some number of items, store all with at+ * least two rows in the sample.+ * + * FIXME We can do this only if we believe we got all the distinct+ * values of the table.+ */+ if (ndistinct <= MVSTAT_MCVLIST_MAX_ITEMS)+ mcv_threshold = 2;++ count = 1;+ for (i = 1; i <= numrows; i++)+ {+ /* last row or a new group */+ if ((i == numrows) || (memcmp(&values[i * numattrs], &values[(i-1) * numattrs], len) != 0))+ {+ /* count the MCV item if exceeding the threshold */+ if (count >= mcv_threshold)+ nitems += 1;++ count = 1;+ }+ else /* same group, just increase the number of items */+ count += 1;+ }++ /* by default we keep all the rows (even if there's no MCV list) */+ *numrows_filtered = numrows;++ /* we know the number of mcvitems, now collect them in a 2nd pass */+ if (nitems > 0)+ {+ /* we need to store the frequency for each group, so (numattrs + 1) */+ mcvlist = (MCVList)palloc0(sizeof(MCVListData));++ mcvlist->magic = MVSTAT_MCV_MAGIC;+ mcvlist->type = MVSTAT_MCV_TYPE_BASIC;+ mcvlist->ndimensions = numattrs;+ mcvlist->nitems = nitems;+ mcvlist->items = (MCVItem*)palloc0(sizeof(MCVItem)*nitems);++ /* now repeat the same loop as above, but this time copy the data+ * for items exceeding the threshold */+ count = 1;+ nitems = 0;+ for (i = 1; i <= numrows; i++)+ {++ /* last row or a new group */+ if ((i == numrows) || (memcmp(&values[i * numattrs], &values[(i-1) * numattrs], len) != 0))+ {+ /* count the MCV item if exceeding the threshold (and copy into the array) */+ if (count >= mcv_threshold)+ {+ /* first, allocate the item (with the proper size of values) */+ MCVItem item = (MCVItem)palloc0(offsetof(MCVItemData, values) ++ sizeof(Datum)*mcvlist->ndimensions);++ /* then copy values from the _previous_ group */+ memcpy(item->values, &values[(i-1)*numattrs], len);++ /* and finally the group frequency */+ item->frequency = (double)count / numrows;++ mcvlist->items[nitems] = item;+ nitems += 1;+ }++ count = 1;+ }+ else /* same group, just increase the number of items */+ count += 1;+ }++ /* make sure the loops are consistent */+ Assert(nitems == mcvlist->nitems);++ /*+ * Remove the rows matching the MCV items.+ *+ * FIXME This implementation is rather naive, effectively O(N^2).+ * As the MCV list grows, the check will take longer and+ * longer. And as the number of sampled rows increases (by+ * increasing statistics target), it will take longer and+ * longer. One option is to sort the MCV items first and+ * then perform a binary search.+ */+ if (nitems == ndistinct) /* all rows are covered by MCV items */+ *numrows_filtered = 0;+ else /* (nitems < ndistinct) && (nitems > 0) */+ {+ int nfiltered = 0;+ HeapTuple *rows_filtered = (HeapTuple*)palloc0(sizeof(HeapTuple) * numrows);++ /* walk through the tuples, compare the values to MCV items */+ for (i = 0; i < numrows; i++)+ {+ bool match = false;+ Datum *keys = (Datum*)palloc0(numattrs * sizeof(Datum));++ /* collect the key values */+ for (j = 0; j < numattrs; j++)+ keys[j] = heap_getattr(rows[i], attrs->values[j], stats[j]->tupDesc, &isNull);++ /* scan through the MCV list for matches */+ for (j = 0; j < mcvlist->nitems; j++)+ if (memcmp(keys, mcvlist->items[j]->values, sizeof(Datum)*numattrs) == 0)+ {+ match = true;+ break;+ }++ /* if no match in the MCV list, copy the row into the filtered ones */+ if (! match)+ memcpy(&rows_filtered[nfiltered++], &rows[i], sizeof(HeapTuple));++ pfree(keys);+ }++ /* replace the first part */+ memcpy(rows, rows_filtered, sizeof(HeapTuple) * nfiltered);+ *numrows_filtered = nfiltered;++ pfree(rows_filtered);++ }+ }++ pfree(values);++ /*+ * TODO Single-dimensional MCV is stored sorted by frequency (descending).+ * Maybe this should be stored like that too?+ */++ return mcvlist;+}++/* multi-variate stats comparator */++/*+ * qsort_arg comparator for sorting Datums (MV stats)+ *+ * This does not maintain the tupnoLink array.+ */+static int+compare_scalars_simple(const void *a, const void *b, void *arg)+{+ Datum da = *(Datum*)a;+ Datum db = *(Datum*)b;+ SortSupport ssup= (SortSupport) arg;++ return ApplySortComparator(da, false, db, false, ssup);+}++/*+ * qsort_arg comparator for sorting data when partitioning a MV bucket+ */+static int+compare_scalars_partition(const void *a, const void *b, void *arg)+{+ Datum da = ((ScalarItem*)a)->value;+ Datum db = ((ScalarItem*)b)->value;+ SortSupport ssup= (SortSupport) arg;++ return ApplySortComparator(da, false, db, false, ssup);+}++/*+ * qsort_arg comparator for sorting Datum[] (row of Datums) when+ * counting distinct values.+ */+static int+compare_scalars_memcmp(const void *a, const void *b, void *arg)+{+ Size len = *(Size*)arg;++ return memcmp(a, b, len);+}++static int+compare_scalars_memcmp_2(const void *a, const void *b)+{+ return memcmp(a, b, sizeof(Datum));+}diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.cindex 714a9f1..7f9e54f 100644--- a/src/backend/commands/tablecmds.c+++ b/src/backend/commands/tablecmds.c@@ -35,6 +35,7 @@
#include "catalog/pg_foreign_table.h"
#include "catalog/pg_inherits.h"
#include "catalog/pg_inherits_fn.h"
+#include "catalog/pg_mv_statistic.h"
#include "catalog/pg_namespace.h"
#include "catalog/pg_opclass.h"
#include "catalog/pg_rowsecurity.h"
@@ -91,7 +92,7 @@
#include "utils/syscache.h"
#include "utils/tqual.h"
#include "utils/typcache.h"
-+#include "utils/mvstats.h"
/*
* ON COMMIT action list
@@ -139,8 +140,9 @@ static List *on_commits = NIL;
#define AT_PASS_ADD_COL 5 /* ADD COLUMN */
#define AT_PASS_ADD_INDEX 6 /* ADD indexes */
#define AT_PASS_ADD_CONSTR 7 /* ADD constraints, defaults */
-#define AT_PASS_MISC 8 /* other stuff */-#define AT_NUM_PASSES 9+#define AT_PASS_ADD_STATS 8 /* ADD statistics */+#define AT_PASS_MISC 9 /* other stuff */+#define AT_NUM_PASSES 10
typedef struct AlteredTableInfo
{
@@ -414,7 +416,8 @@ static void ATExecReplicaIdentity(Relation rel, ReplicaIdentityStmt *stmt, LOCKM
static void ATExecGenericOptions(Relation rel, List *options);
static void ATExecEnableRowSecurity(Relation rel);
static void ATExecDisableRowSecurity(Relation rel);
-+static void ATExecAddStatistics(AlteredTableInfo *tab, Relation rel,+ StatisticsDef *def, LOCKMODE lockmode);
static void copy_relation_data(SMgrRelation rel, SMgrRelation dst,
ForkNumber forkNum, char relpersistence);
static const char *storage_name(char c);
@@ -2965,6 +2968,7 @@ AlterTableGetLockLevel(List *cmds)
* updates.
*/
case AT_SetStatistics: /* Uses MVCC in getTableAttrs() */
+ case AT_AddStatistics: /* XXX not sure if the right level */
case AT_ClusterOn: /* Uses MVCC in getIndexes() */
case AT_DropCluster: /* Uses MVCC in getIndexes() */
case AT_SetOptions: /* Uses MVCC in getTableAttrs() */
@@ -3112,6 +3116,7 @@ ATPrepCmd(List **wqueue, Relation rel, AlterTableCmd *cmd,
pass = AT_PASS_ADD_CONSTR;
break;
case AT_SetStatistics: /* ALTER COLUMN SET STATISTICS */
+ case AT_AddStatistics: /* XXX maybe not the right place */
ATSimpleRecursion(wqueue, rel, cmd, recurse, lockmode);
/* Performs own permission checks */
ATPrepSetStatistics(rel, cmd->name, cmd->def, lockmode);
@@ -3407,6 +3412,9 @@ ATExecCmd(List **wqueue, AlteredTableInfo *tab, Relation rel,
case AT_SetStatistics: /* ALTER COLUMN SET STATISTICS */
ATExecSetStatistics(rel, cmd->name, cmd->def, lockmode);
break;
+ case AT_AddStatistics: /* ADD STATISTICS */+ ATExecAddStatistics(tab, rel, (StatisticsDef *) cmd->def, lockmode);+ break;
case AT_SetOptions: /* ALTER COLUMN SET ( options ) */
ATExecSetOptions(rel, cmd->name, cmd->def, false, lockmode);
break;
@@ -11616,3 +11624,197 @@ RangeVarCallbackForAlterRelation(const RangeVar *rv, Oid relid, Oid oldrelid,
ReleaseSysCache(tuple);
}
++/* used for sorting the attnums in ATExecAddStatistics */+static int compare_int16(const void *a, const void *b)+{+ return memcmp(a, b, sizeof(int16));+}++/*+ * Implements the ALTER TABLE ... ADD STATISTICS (options) ON (columns).+ *+ * The code is an unholy mix of pieces that really belong to other parts+ * of the source tree.+ *+ * FIXME Check that the types are pass-by-value and support sort,+ * although maybe we can live without the sort (and only build+ * MCV list / association rules).+ *+ * FIXME This should probably check for duplicate stats (i.e. same+ * keys, same options). Although maybe it's useful to have+ * multiple stats on the same columns with different options+ * (say, a detailed MCV-only stats for some queries, histogram+ * for others, etc.)+ */+static void ATExecAddStatistics(AlteredTableInfo *tab, Relation rel,+ StatisticsDef *def, LOCKMODE lockmode)+{+ int i, j;+ ListCell *l;+ int16 attnums[INDEX_MAX_KEYS];+ Oid atttypids[INDEX_MAX_KEYS];+ int numcols = 0;++ Oid mvstatoid;+ HeapTuple htup;+ Datum values[Natts_pg_mv_statistic];+ bool nulls[Natts_pg_mv_statistic];+ int2vector *stakeys;+ Relation mvstatrel;++ /* by default build everything */+ bool build_histogram = true,+ build_mcv = true,+ build_associations = true;++ /* build regular MCV (not hashed by default) */+ bool mcv_hashed = false;++ int32 max_buckets = -1,+ max_mcv_items = -1;++ Assert(IsA(def, StatisticsDef));++ /* transform the column names to attnum values */++ foreach(l, def->keys)+ {+ char *attname = strVal(lfirst(l));+ HeapTuple atttuple;++ atttuple = SearchSysCacheAttName(RelationGetRelid(rel), attname);++ if (!HeapTupleIsValid(atttuple))+ ereport(ERROR,+ (errcode(ERRCODE_UNDEFINED_COLUMN),+ errmsg("column \"%s\" referenced in statistics does not exist",+ attname)));++ /* more than MVHIST_MAX_DIMENSIONS columns not allowed */+ if (numcols >= MVSTATS_MAX_DIMENSIONS)+ ereport(ERROR,+ (errcode(ERRCODE_TOO_MANY_COLUMNS),+ errmsg("cannot have more than %d keys in a statistics",+ MVSTATS_MAX_DIMENSIONS)));++ attnums[numcols] = ((Form_pg_attribute) GETSTRUCT(atttuple))->attnum;+ atttypids[numcols] = ((Form_pg_attribute) GETSTRUCT(atttuple))->atttypid;+ ReleaseSysCache(atttuple);+ numcols++;+ }++ /*+ * Check the lower bound (at least 2 columns), the upper bound was+ * already checked in the loop.+ */+ if (numcols < 2)+ ereport(ERROR,+ (errcode(ERRCODE_TOO_MANY_COLUMNS),+ errmsg("multivariate stats require 2 or more columns")));++ /* look for duplicities */+ for (i = 0; i < numcols; i++)+ for (j = 0; j < numcols; j++)+ if ((i != j) && (attnums[i] == attnums[j]))+ ereport(ERROR,+ (errcode(ERRCODE_UNDEFINED_COLUMN),+ errmsg("duplicate column name in statistics definition")));++ /* parse the statistics options */+ foreach (l, def->options)+ {+ DefElem *opt = (DefElem*)lfirst(l);++ if (strcmp(opt->defname, "histogram") == 0)+ build_histogram = defGetBoolean(opt);+ else if (strcmp(opt->defname, "mcv") == 0)+ build_mcv = defGetBoolean(opt);+ else if (strcmp(opt->defname, "mcv_hashed") == 0)+ mcv_hashed = defGetBoolean(opt);+ else if (strcmp(opt->defname, "associations") == 0)+ build_associations = defGetBoolean(opt);+ else if (strcmp(opt->defname, "max_buckets") == 0)+ {+ max_buckets = defGetInt32(opt);++ /* TODO check that this is not used with 'histogram off' */++ /* sanity check */+ if (max_buckets < 1024)+ ereport(ERROR,+ (errcode(ERRCODE_SYNTAX_ERROR),+ errmsg("minimum number of buckets is 1024")));++ else if (max_buckets > 32768) /* FIXME use the proper constant */+ ereport(ERROR,+ (errcode(ERRCODE_SYNTAX_ERROR),+ errmsg("minimum number of buckets is 1024")));++ }+ else if (strcmp(opt->defname, "max_mcv_items") == 0)+ {+ max_mcv_items = defGetInt32(opt);++ /* TODO check that this is not used with 'mcv off' */++ /* sanity check */+ if (max_mcv_items < 0)+ ereport(ERROR,+ (errcode(ERRCODE_SYNTAX_ERROR),+ errmsg("max number of MCV items must be non-negative")));++ else if (max_mcv_items > 8192) /* FIXME use the proper constant */+ ereport(ERROR,+ (errcode(ERRCODE_SYNTAX_ERROR),+ errmsg("max number of MCV items is 8192")));++ }+ else+ ereport(ERROR,+ (errcode(ERRCODE_SYNTAX_ERROR),+ errmsg("unrecognized STATISTICS option \"%s\"",+ opt->defname)));+ }++ /* sort the attnums and build int2vector */+ qsort(attnums, numcols, sizeof(int16), compare_int16);+ stakeys = buildint2vector(attnums, numcols);++ /*+ * Okay, let's create the pg_mv_statistic entry.+ */+ memset(values, 0, sizeof(values));+ memset(nulls, false, sizeof(nulls));++ /* no stats collected yet, so just the keys */+ values[Anum_pg_mv_statistic_starelid-1] = ObjectIdGetDatum(RelationGetRelid(rel));++ values[Anum_pg_mv_statistic_stakeys -1] = PointerGetDatum(stakeys);+ values[Anum_pg_mv_statistic_hist_enabled -1] = BoolGetDatum(build_histogram);+ values[Anum_pg_mv_statistic_mcv_enabled -1] = BoolGetDatum(build_mcv);+ values[Anum_pg_mv_statistic_mcv_hashed -1] = BoolGetDatum(mcv_hashed);+ values[Anum_pg_mv_statistic_assoc_enabled -1] = BoolGetDatum(build_associations);++ values[Anum_pg_mv_statistic_hist_max_buckets -1] = Int32GetDatum(max_buckets);+ values[Anum_pg_mv_statistic_mcv_max_items -1] = Int32GetDatum(max_mcv_items);++ nulls[Anum_pg_mv_statistic_staassoc -1] = true;+ nulls[Anum_pg_mv_statistic_stamcv -1] = true;+ nulls[Anum_pg_mv_statistic_stahist -1] = true;++ /* insert the tuple into pg_mv_statistic */+ mvstatrel = heap_open(MvStatisticRelationId, RowExclusiveLock);++ htup = heap_form_tuple(mvstatrel->rd_att, values, nulls);++ mvstatoid = simple_heap_insert(mvstatrel, htup);++ CatalogUpdateIndexes(mvstatrel, htup);++ heap_freetuple(htup);++ heap_close(mvstatrel, RowExclusiveLock);++ return;+}diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.cindex e76b5b3..da35331 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -3903,6 +3903,17 @@ _copyAlterPolicyStmt(const AlterPolicyStmt *from)
return newnode;
}
+static StatisticsDef *+_copyStatisticsDef(const StatisticsDef *from)+{+ StatisticsDef *newnode = makeNode(StatisticsDef);++ COPY_NODE_FIELD(keys);+ COPY_NODE_FIELD(options);++ return newnode;+}+
/* ****************************************************************
* pg_list.h copy functions
* ****************************************************************
@@ -4717,6 +4728,9 @@ copyObject(const void *from)
case T_CommonTableExpr:
retval = _copyCommonTableExpr(from);
break;
+ case T_StatisticsDef:+ retval = _copyStatisticsDef(from);+ break;
case T_PrivGrantee:
retval = _copyPrivGrantee(from);
break;
@@ -4729,7 +4743,6 @@ copyObject(const void *from)
case T_XmlSerialize:
retval = _copyXmlSerialize(from);
break;
-
default:
elog(ERROR, "unrecognized node type: %d", (int) nodeTag(from));
retval = 0; /* keep compiler quiet */
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.cindex 9b657fb..9c32735 100644--- a/src/backend/optimizer/path/clausesel.c+++ b/src/backend/optimizer/path/clausesel.c@@ -24,6 +24,9 @@
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
+#include "utils/mvstats.h"+#include "catalog/pg_collation.h"+#include "utils/typcache.h"
/*
* Data structure for accumulating info about possible range-query
@@ -43,6 +46,23 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause,
bool varonleft, bool isLTsel, Selectivity s2);
+static bool is_mv_compatible(Node *clause, Oid varRelid, Index *varno,+ Bitmapset **attnums);+static Bitmapset *collect_mv_attnums(PlannerInfo *root, List *clauses,+ Oid varRelid, Oid *relid);+static int choose_mv_histogram(int nmvstats, MVStats mvstats,+ Bitmapset *attnums);+static List *clauselist_mv_split(List *clauses, Oid varRelid,+ List **mvclauses, MVStats mvstats);++static Selectivity clauselist_mv_selectivity(PlannerInfo *root,+ List *clauses, MVStats mvstats);+static Selectivity clauselist_mv_selectivity_mcvlist(PlannerInfo *root,+ List *clauses, MVStats mvstats,+ bool *fullmatch, Selectivity *lowsel);+static Selectivity clauselist_mv_selectivity_histogram(PlannerInfo *root,+ List *clauses, MVStats mvstats);+
/****************************************************************************
* ROUTINES TO COMPUTE SELECTIVITIES
****************************************************************************/
@@ -100,14 +120,74 @@ clauselist_selectivity(PlannerInfo *root,
RangeQueryClause *rqlist = NULL;
ListCell *l;
+ /* processing mv stats */+ Oid relid = InvalidOid;+ int nmvstats = 0;+ MVStats mvstats = NULL;++ /* attributes in mv-compatible clauses */+ Bitmapset *mvattnums = NULL;+
/*
- * If there's exactly one clause, then no use in trying to match up pairs,- * so just go directly to clause_selectivity().+ * If there's exactly one clause, then no use in trying to match up+ * pairs, so just go directly to clause_selectivity().
*/
if (list_length(clauses) == 1)
return clause_selectivity(root, (Node *) linitial(clauses),
varRelid, jointype, sjinfo);
+ /* collect attributes from mv-compatible clauses */+ mvattnums = collect_mv_attnums(root, clauses, varRelid, &relid);++ /*+ * If there are mv-compatible clauses, referencing at least two+ * columns (otherwise it makes no sense to use mv stats), fetch the+ * MV histograms for the relation (only the column keys, not the+ * histograms yet - we'll decide which histogram to use first).+ */+ if (bms_num_members(mvattnums) >= 2)+ {+ /* clauses compatible with multi-variate stats */+ List *mvclauses = NIL;++ /* fetch info from the catalog (not the serialized stats yet) */+ mvstats = list_mv_stats(relid, &nmvstats, true);++ /*+ * If there are candidate statistics, choose the histogram first.+ * At the moment we only use a single statistics, covering the+ * most columns (using info from the previous step). If there+ * are multiple such histograms, we'll use the smallest one+ * (with the lowest number of dimensions).+ * + * This may not be optimal choice, if the 'smaller' stats has+ * much less buckets than the rejected one (making it less+ * accurate).+ *+ * We may end up without multivariate statistics, if none of the+ * stats matches at least two columns from the clauses (in that+ * case we may just use the single dimensional stats).+ */+ if (nmvstats > 0)+ {+ int idx = choose_mv_histogram(nmvstats, mvstats, mvattnums);++ if (idx >= 0) /* we have a matching stats */+ {+ MVStats mvstat = &mvstats[idx];++ /* split the clauselist into regular and mv-clauses */+ clauses = clauselist_mv_split(clauses, varRelid, &mvclauses, mvstat);++ /* we've chosen the histogram to match the clauses */+ Assert(mvclauses != NIL);++ /* compute the multivariate stats */+ s1 *= clauselist_mv_selectivity(root, mvclauses, mvstat);+ }+ }+ }+
/*
* Initial scan over clauses. Anything that doesn't look like a potential
* rangequery clause gets multiplied into s1 and forgotten. Anything that
@@ -782,3 +862,1010 @@ clause_selectivity(PlannerInfo *root,
return s1;
}
++++/*+ * Estimate selectivity for the list of MV-compatible clauses, using that+ * particular histogram.+ *+ * When we hit a single bucket, we don't know what portion of it actually+ * matches the clauses (e.g. equality), and we use 1/2 the bucket by+ * default. However, the MV histograms are usually less detailed than+ * the per-column ones, meaning the sum of buckets is often quite high+ * (thanks to combining a lot of "partially hit" buckets).+ *+ * There are several ways to improve this, usually with cases when it+ * won't really help. Also, the more complex the process, the worse+ * the failures (i.e. misestimates).+ *+ * (1) Use the MV histogram only as a way to combine multiple+ * per-column histograms, essentially rewriting+ *+ * P(A & B) = P(A) * P(B|A)+ *+ * where P(B|A) may be computed using a proper "slice" of the+ * histogram, by first selecting only buckets where A is true, and+ * then using the boundaries to 'restrict' the per-colunm histogram.+ *+ * With more clauses, it gets more complicated, of course+ *+ * P(A & B & C) = P(A & C) * P(B|A & C)+ * = P(A) * P(C|A) * P(B|A & C)+ *+ * and so on.+ * + * Of course, the question is how well and efficiently we can+ * compute the conditional probabilities - whether this approach+ * can improve the estimates (instead of amplifying the errors).+ *+ * Also, this does not eliminate the need for histogram on [A,B,C].+ *+ * (2) Use multiple smaller (and more accurate) histograms, and combine+ * them using a process similar to the above. E.g. by assuming that+ * B and C are independent, we can rewrite+ *+ * P(B|A & C) = P(B|A)+ * + * so we can rewrite the whole formula to+ * + * P(A & B & C) = P(A) * P(C|A) * P(B|A)+ * + * and we're OK with two 2D histograms [A,C] and [A,B].+ *+ * It'd be nice to perform some sort of statistical test (Fisher+ * or another chi-squared test) to identify independent components+ * and automatically separate them into smaller histograms.+ *+ * (3) Using the estimated number of distinct values in a bucket to+ * decide the selectivity of equality in the bucket (instead of+ * blindly using 1/2 of the bucket, we may use 1/ndistinct).+ * Of course, if the ndistinct estimate is way off, or when the+ * distribution is not uniform (one distict items get much more+ * items), this will fail. Also, we currently don't have ndistinct+ * estimate available at this moment (but it shouldn't be that+ * difficult to compute as ndistinct and ntuples should be available).+ *+ * TODO Clamp the selectivity by min of the per-clause selectivities+ * (i.e. the selectivity of the most restrictive clause), because+ * that's the maximum we can ever get from ANDed list of clauses.+ * This may probably prevent issues with hitting too many buckets+ * and low precision histograms.+ *+ * TODO We may support some additional conditions, most importantly+ * those matching multiple columns (e.g. "a = b" or "a < b").+ * Ultimately we could track multi-table histograms for join+ * cardinality estimation.+ *+ * TODO Currently this is only estimating all clauses, or clauses+ * matching varRelid (when it's not 0). I'm not sure what's the+ * purpose of varRelid, but my assumption is this is used for+ * join conditions and such. In that case we can use those clauses+ * to restrict the other (i.e. filter the histogram buckets first,+ * before estimating the other clauses). This is essentially equal+ * to computing P(A|B) where "B" are the clauses not matching the+ * varRelid.+ * + * TODO Further thoughts on processing equality clauses - maybe it'd be+ * better to look for stats (with MCV) covered by the equality+ * clauses, because then we have a chance to find an exact match+ * in the MCV list, which is pretty much the best we can do. We may+ * also look at the least frequent MCV item, and use it as a upper+ * boundary for the selectivity (had there been a more frequent+ * item, it'd be in the MCV list).+ *+ * These conditions may then be used as a condition for the other+ * selectivities, i.e. we may estimate P(A,B) first, and then+ * compute P(C|A,B) from another histogram. This may be useful when+ * we can estimate P(A,B) accurately (e.g. because it's a complete+ * equality match evaluated on MCV list), and then compute the+ * conditional probability P(C|A,B), giving us the requested stats+ *+ * P(A,B,C) = P(A,B) * P(C|A,B)+ *+ * TODO There are several options for 'sanity clamping' the estimates.+ *+ * First, if we have selectivities for each condition, then+ * + * P(A,B) <= MIN(P(A), P(B))+ *+ * Because additional conditions (connected by AND) can only lower+ * the probability.+ *+ * So we can do some basic sanity checks using the single-variate+ * stats (the ones we have right now).+ *+ * Second, when we have multivariate stats with a MCV list, then+ *+ * (a) if we have a full equality condition (one equality condition+ * on each column) and we found a match in the MCV list, this is+ * the selectivity (and it's supposed to be exact)+ *+ * (b) if we have a full equality condition and we haven't found a+ * match in the MCV list, then the selectivity is below the+ * lowest selectivity in the MCV list+ *+ * (c) if we have a equality condition (not full), we can still+ * search the MCV for matches and use the sum of probabilities+ * as a lower boundary for the histogram (if there are no+ * matches in the MCV list, then we have no boundary)+ *+ * Third, if there are multiple multivariate stats for a set of+ * clauses, we may compute all of them and then somehow aggregate+ * them - e.g. by choosing the minimum, median or average. The+ * multi-variate stats are susceptible to overestimation (because+ * we take 50% of the bucket for partial matches). Some stats may+ * give better estimates than others, but it's very difficult to+ * say determine that in advance which one is the best (it depends+ * on the number of buckets, number of additional columns not+ * referenced in the clauses etc.) so we may compute all and then+ * choose a sane aggregation (minimum seems like a good approach).+ * Of course, this may result in longer / more expensive estimation+ * (CPU-wise), but it may be worth it.+ *+ * There are ways to address this, though. First, it's possible to+ * add a GUC choosing whether to do a 'simple' (using a single+ * stats expected to give the best estimate) and 'complex' (combining+ * the multiple estimates).+ * + * multivariate_estimates = (simple|full)+ *+ * Also, this might be enabled at a table level, by something like+ * + * ALTER TABLE ... SET STATISTICS (simple|full)+ * + * Which would make it possible to use this only for the tables+ * where the simple approach does not work.+ * + * Also, there are ways to optimize this algorithmically. E.g. we+ * may try to get an estimate from a matching MCV list first, and+ * if we happen to get a "full equality match" we may stop computing+ * the estimates from other stats (for this condition) because+ * that's probably the best estimate we can really get.+ *+ * TODO When applying the clauses to the histogram/MCV list, we can do+ * that from the most selective clauses first, because that'll+ * eliminate the buckets/items sooner (so we'll be able to skip+ * them without inspection, which is more expensive).+ */+static Selectivity+clauselist_mv_selectivity(PlannerInfo *root, List *clauses, MVStats mvstats)+{+ bool fullmatch = false;+ Selectivity s1 = 0.0, s2 = 0.0;++ /*+ * Lowest frequency in the MCV list (may be used as an upper bound+ * for full equality conditions that did not match any MCV item).+ */+ Selectivity mcv_low = 0.0;++ /* TODO Evaluate simple 1D selectivities, use the smallest one as+ * an upper bound, product as lower bound, and sort the+ * clauses in ascending order by selectivity (to optimize the+ * MCV/histogram evaluation). + */++ /* Evaluate the MCV first. */+ s1 = clauselist_mv_selectivity_mcvlist(root, clauses, mvstats,+ &fullmatch, &mcv_low);++ /*+ * If we got a full equality match on the MCV list, we're done (and+ * the estimate is pretty good).+ */+ if (fullmatch && (s1 > 0.0))+ return s1;++ /* FIXME if (fullmatch) without matching MCV item, use the mcv_low+ * selectivity as upper bound */++ s2 = clauselist_mv_selectivity_histogram(root, clauses, mvstats);++ /* TODO clamp to <= 1.0 (or more strictly, when possible) */+ return s1 + s2;+}++/*+ * Collect attributes from mv-compatible clauses.+ * + */+static Bitmapset *+collect_mv_attnums(PlannerInfo *root, List *clauses, Oid varRelid, Oid *relid)+{+ Index varno = 0;+ Bitmapset *attnums = NULL;+ ListCell *l;++ /*+ * Walk through the clauses and identify the ones we can estimate+ * using multivariate stats, and remember the relid/columns. We'll+ * then cross-check if we have suitable stats, and only if needed+ * we'll split the clauses into multivariate and regular lists.+ *+ * For now we're only interested in RestrictInfo nodes with nested+ * OpExpr, using either a range or equality.+ */+ foreach (l, clauses)+ {+ Node *clause = (Node *) lfirst(l);++ /* ignore the result for now - we only need the info */+ is_mv_compatible(clause, varRelid, &varno, &attnums);+ }++ /*+ * If there are at least two attributes referenced by the clause(s),+ * fetch the relation info (and pass back the Oid of the relation).+ */+ if (bms_num_members(attnums) > 1)+ {+ RelOptInfo *rel = find_base_rel(root, varno);+ *relid = root->simple_rte_array[bms_singleton_member(rel->relids)]->relid;+ }+ else+ {+ if (attnums != NULL)+ pfree(attnums);+ attnums = NULL;+ *relid = InvalidOid;+ }++ return attnums;+}++/*+ * We're looking for a histogram matching at least 2 attributes, and we+ * want the smallest histogram available wrt. to number of buckets (to+ * get efficient estimation and likely better precision. The precision+ * depends on the total number of buckets too, but the lower the number+ * of dimensions the smaller (and more precise) the buckets can get.+ */+static int+choose_mv_histogram(int nmvstats, MVStats mvstats, Bitmapset *attnums)+{+ int i, j;++ int choice = -1;+ int current_matches = 1; /* goal #1: maximize */+ int current_dims = (MVSTATS_MAX_DIMENSIONS+1); /* goal #2: minimize */++ for (i = 0; i < nmvstats; i++)+ {+ int matches = 0; /* columns matching this histogram */++ int2vector * attrs = mvstats[i].stakeys;+ int numattrs = mvstats[i].stakeys->dim1;++ /* count columns covered by the histogram */+ for (j = 0; j < numattrs; j++)+ if (bms_is_member(attrs->values[j], attnums))+ matches++;++ /*+ * Use this histogram when it improves the number of matches or+ * when it keeps the number of matches and is smaller.+ */+ if ((matches > current_matches) ||+ ((matches == current_matches) && (current_dims > numattrs)))+ {+ choice = i;+ current_matches = matches;+ current_dims = numattrs;+ }+ }++ return choice;+}++/*+ * This splits the clauses list into two parts - one containing clauses+ * that will be evaluated using the chosen histogram, and the remaining+ * clauses (either non-mvcompatible, or not related to the histogram).+ */+static List *+clauselist_mv_split(List *clauses, Oid varRelid, List **mvclauses, MVStats mvstats)+{+ int i;+ ListCell *l;+ List *non_mvclauses = NIL;++ /* FIXME is there a better way to get info on int2vector? */+ int2vector * attrs = mvstats->stakeys;+ int numattrs = mvstats->stakeys->dim1;++ /* erase the list of mv-compatible clauses */+ *mvclauses = NIL;++ foreach (l, clauses)+ {+ RestrictInfo *rinfo;+ Node *clause = (Node *) lfirst(l);++ /*+ * Only restrictinfo may be mv-compatible, so everything else+ * goes to the non-mv list directly+ * + * TODO create a macro/function to decide mv-compatible clauses+ * (along the is_opclause for example)+ */+ if (! IsA(clause, RestrictInfo))+ {+ non_mvclauses = lappend(non_mvclauses, clause);+ continue;+ }++ rinfo = (RestrictInfo *) clause;+ clause = (Node*)rinfo->clause;++ /* Pseudoconstants go directly to the non-mv list too. */+ if (rinfo->pseudoconstant)+ {+ non_mvclauses = lappend(non_mvclauses, rinfo);+ continue;+ }++ if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)+ {+ OpExpr *expr = (OpExpr *) clause;+ bool varonleft = true;+ bool ok;++ ok = (bms_membership(rinfo->clause_relids) == BMS_SINGLETON) &&+ (is_pseudo_constant_clause_relids(lsecond(expr->args),+ rinfo->right_relids) ||+ (varonleft = false,+ is_pseudo_constant_clause_relids(linitial(expr->args),+ rinfo->left_relids)));++ if (ok)+ {++ Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);++ /*+ * Only consider this variable if (varRelid == 0) or when the varno+ * matches varRelid (see explanation at clause_selectivity).+ */+ if (! ((varRelid == 0) || (varRelid == var->varno)))+ {+ non_mvclauses = lappend(non_mvclauses, rinfo);+ continue;+ }++ /*+ * If it's not a "<" or ">" or "=" operator, just ignore the+ * clause. Otherwise note the relid and attnum for the variable.+ */+ switch (get_oprrest(expr->opno))+ {+ case F_SCALARLTSEL:+ case F_SCALARGTSEL:+ case F_EQSEL:+ if (! IS_SPECIAL_VARNO(var->varno)) /* FIXME necessary here? */+ {+ bool match = false;+ for (i = 0; i < numattrs; i++)+ if (attrs->values[i] == var->varattno)+ match = true;++ if (match)+ *mvclauses = lappend(*mvclauses, clause);+ else+ non_mvclauses = lappend(non_mvclauses, rinfo);+ }+ }+ }+ }+ }++ /*+ * Perform regular estimation using the clauses incompatible+ * with the chosen histogram (or MV stats in general).+ */+ return non_mvclauses;++}++/*+ * Determines whether the clause is compatible with multivariate stats,+ * and if it is, returns some additional information - varno (index+ * into simple_rte_array) and a bitmap of attributes. This is then+ * used to fetch related multivariate statistics.+ *+ * At this moment we only support basic conditions of the form+ * + * variable OP constant+ *+ * where OP is one of [=,<,<=,>=,>] (which is however determined by+ * looking at the associated function for estimating selectivity, just+ * like with the single-dimensional case).+ */+static bool+is_mv_compatible(Node *clause, Oid varRelid, Index *varno, Bitmapset **attnums)+{++ if (IsA(clause, RestrictInfo))+ {+ RestrictInfo *rinfo = (RestrictInfo *) clause;++ /* Pseudoconstants are not really interesting here. */+ if (rinfo->pseudoconstant)+ return false;++ /* get the actual clause from the RestrictInfo ... */+ clause = (Node*)rinfo->clause;++ /* is it 'variable op constant' ? */+ if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)+ {+ OpExpr *expr = (OpExpr *) clause;+ bool varonleft = true;+ bool ok;++ ok = (bms_membership(rinfo->clause_relids) == BMS_SINGLETON) &&+ (is_pseudo_constant_clause_relids(lsecond(expr->args),+ rinfo->right_relids) ||+ (varonleft = false,+ is_pseudo_constant_clause_relids(linitial(expr->args),+ rinfo->left_relids)));++ if (ok)+ {++ Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);++ /*+ * Only consider this variable if (varRelid == 0) or when the varno+ * matches varRelid (see explanation at clause_selectivity).+ */+ if (! ((varRelid == 0) || (varRelid == var->varno)))+ return false;++ /* Also skip special varno values, and system attributes ... */+ if ((IS_SPECIAL_VARNO(var->varno)) || (! AttrNumberIsForUserDefinedAttr(var->varattno)))+ return false;++ /*+ * If it's not a "<" or ">" or "=" operator, just ignore the+ * clause. Otherwise note the relid and attnum for the variable.+ * This uses the function for estimating selectivity, ont the+ * operator directly (a bit awkward, but well ...).+ */+ switch (get_oprrest(expr->opno))+ {+ case F_SCALARLTSEL:+ case F_SCALARGTSEL:+ case F_EQSEL:+ *varno = var->varno;+ *attnums = bms_add_member(*attnums, var->varattno);+ return true;+ }+ }+ }+ }++ return false;++}++/*+ * Estimate selectivity of clauses using a MCV list.+ *+ * If there's no MCV list for the stats, the function returns 0.0.+ *+ * While computing the estimate, the function checks whether all the+ * columns were matched with an equality condition. If that's the case,+ * it's assumed we can skip computing the estimate from histogram,+ * because all the rows matching the condition are represented by the+ * MCV item.+ *+ * The function also returns the frequency of the least frequent item+ * on the MCV list, which may be useful for clamping estimate from the+ * histogram.+ */+static Selectivity+clauselist_mv_selectivity_mcvlist(PlannerInfo *root, List *clauses,+ MVStats mvstats, bool *fullmatch,+ Selectivity *lowsel)+{+ int i;+ Selectivity s = 0.0;+ ListCell * l;+ char * mcvitems = NULL;+ MCVList mcvlist = NULL;++ Bitmapset *matches = NULL; /* attributes with equality matches */++ /* there's no MCV list yet */+ if (! mvstats->mcv_built)+ return 0.0;++ mcvlist = deserialize_mv_mcvlist(fetch_mv_mcvlist(mvstats->mvoid));++ Assert(mcvlist != NULL);+ Assert (clauses != NIL);+ Assert (list_length(clauses) >= 2);++ mcvitems = palloc0(sizeof(char) * mcvlist->nitems);+ memset(mcvitems, MVSTATS_MATCH_FULL, sizeof(char)*mcvlist->nitems);++ /* no match here */+ *lowsel = 1.0;++ /* loop through the list of MV-compatible clauses and do the estimation */+ foreach (l, clauses)+ {+ Node * clause = (Node*)lfirst(l);+ OpExpr * expr = (OpExpr*)clause;+ bool varonleft = true;+ bool ok;++ /* operator */+ FmgrInfo opproc;++ fmgr_info(get_opcode(expr->opno), &opproc);++ ok = (NumRelids(clause) == 1) &&+ (is_pseudo_constant_clause(lsecond(expr->args)) ||+ (varonleft = false,+ is_pseudo_constant_clause(linitial(expr->args))));++ if (ok)+ {++ FmgrInfo ltproc, gtproc;+ Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);+ Const * cst = (varonleft) ? lsecond(expr->args) : linitial(expr->args);+ bool isgt = (! varonleft);++ /*+ * TODO Fetch only when really needed (probably for equality only)+ * TODO Technically either lt/gt is sufficient.+ * + * FIXME The code in analyze.c creates histograms only for types+ * with enough ordering (by calling get_sort_group_operators).+ * Is this the same assumption, i.e. are we certain that we+ * get the ltproc/gtproc every time we ask? Or are there types+ * where get_sort_group_operators returns ltopr and here we+ * get nothing?+ */+ TypeCacheEntry *typecache = lookup_type_cache(var->vartype, TYPECACHE_EQ_OPR | TYPECACHE_LT_OPR | TYPECACHE_GT_OPR);++ /* FIXME proper matching attribute to dimension */+ int idx = mv_get_index(var->varattno, mvstats->stakeys);++ fmgr_info(get_opcode(typecache->lt_opr), <proc);+ fmgr_info(get_opcode(typecache->gt_opr), >proc);++ /* process the MCV list first */+ for (i = 0; i < mcvlist->nitems; i++)+ {+ bool tmp;+ MCVItem item = mcvlist->items[i];++ /* find the lowest selectivity in the MCV */+ if (item->frequency < *lowsel)+ *lowsel = item->frequency;++ /* skip MCV items already ruled out */+ if (mcvitems[i] == MVSTATS_MATCH_NONE)+ continue;++ /* TODO consider bsearch here (list is sorted by values)+ * TODO handle other operators too (LT, GT)+ * TODO identify "full match" when the clauses fully+ * match the whole MCV list (so that checking the+ * histogram is not needed)+ */+ if (get_oprrest(expr->opno) == F_EQSEL)+ {+ /*+ * We don't care about isgt in equality, because it does not matter+ * whether it's (var = const) or (const = var).+ */+ if (memcmp(&cst->constvalue, &item->values[idx], sizeof(Datum)) != 0)+ mcvitems[i] = MVSTATS_MATCH_NONE;+ else+ matches = bms_add_member(matches, idx);+ }+ else if (get_oprrest(expr->opno) == F_SCALARLTSEL) /* column < constant */+ {++ if (! isgt) /* (var < const) */+ {+ /*+ * First check whether the constant is below the lower boundary (in that + * case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ item->values[idx]));++ if (tmp)+ {+ mcvitems[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }++ } /* (get_oprrest(expr->opno) == F_SCALARLTSEL) */+ else /* (const < var) */+ {+ /*+ * First check whether the constant is above the upper boundary (in that + * case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ item->values[idx],+ cst->constvalue));+ if (tmp)+ {+ mcvitems[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }+ }+ }+ else if (get_oprrest(expr->opno) == F_SCALARGTSEL) /* column > constant */+ {++ if (! isgt) /* (var > const) */+ {+ /*+ * First check whether the constant is above the upper boundary (in that + * case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ item->values[idx]));+ if (tmp)+ {+ mcvitems[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }++ }+ else /* (const > var) */+ {+ /*+ * First check whether the constant is below the lower boundary (in+ * that case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ item->values[idx],+ cst->constvalue));+ if (tmp)+ {+ mcvitems[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }+ }++ } /* (get_oprrest(expr->opno) == F_SCALARGTSEL) */++ }+ }+ }++ for (i = 0; i < mcvlist->nitems; i++)+ {+ if (mcvitems[i] != MVSTATS_MATCH_NONE)+ s += mcvlist->items[i]->frequency;+ }++ *fullmatch = (bms_num_members(matches) == mcvlist->ndimensions);++ pfree(mcvitems);+ pfree(mcvlist);++ return s;+}++/*+ * Estimate selectivity of clauses using a histogram.+ *+ * If there's no histogram list for the stats, the function returns 0.0.+ */+static Selectivity+clauselist_mv_selectivity_histogram(PlannerInfo *root, List *clauses,+ MVStats mvstats)+{+ int i;+ Selectivity s = 0.0;+ ListCell * l;+ char *buckets = NULL;+ MVHistogram mvhist = NULL;++ /* there's no histogram */+ if (! mvstats->hist_built)+ return 0.0;++ /* There may be no histogram in the stats (check hist_built flag) */+ mvhist = deserialize_mv_histogram(fetch_mv_histogram(mvstats->mvoid));++ Assert (mvhist != NULL);+ Assert (clauses != NIL);+ Assert (list_length(clauses) >= 2);++ /*+ * Bitmap of bucket matches (mismatch, partial, full). by default+ * all buckets fully match (and we'll eliminate them).+ */+ buckets = palloc0(sizeof(char) * mvhist->nbuckets);+ memset(buckets, MVSTATS_MATCH_FULL, sizeof(char)*mvhist->nbuckets);++ /* loop through the clauses and do the estimation */+ foreach (l, clauses)+ {+ Node * clause = (Node*)lfirst(l);+ OpExpr * expr = (OpExpr*)clause;+ bool varonleft = true;+ bool ok;++ FmgrInfo opproc; /* operator */+ fmgr_info(get_opcode(expr->opno), &opproc);++ ok = (NumRelids(clause) == 1) &&+ (is_pseudo_constant_clause(lsecond(expr->args)) ||+ (varonleft = false,+ is_pseudo_constant_clause(linitial(expr->args))));++ if (ok)+ {+ FmgrInfo ltproc;+ Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);+ Const * cst = (varonleft) ? lsecond(expr->args) : linitial(expr->args);+ bool isgt = (! varonleft);++ /*+ * TODO Fetch only when really needed (probably for equality only)+ *+ * TODO Technically either lt/gt is sufficient.+ * + * FIXME The code in analyze.c creates histograms only for types+ * with enough ordering (by calling get_sort_group_operators).+ * Is this the same assumption, i.e. are we certain that we+ * get the ltproc/gtproc every time we ask? Or are there types+ * where get_sort_group_operators returns ltopr and here we+ * get nothing?+ */+ TypeCacheEntry *typecache+ = lookup_type_cache(var->vartype, TYPECACHE_EQ_OPR | TYPECACHE_LT_OPR+ | TYPECACHE_GT_OPR);++ /* lookup dimension for the attribute */+ int idx = mv_get_index(var->varattno, mvstats->stakeys);++ fmgr_info(get_opcode(typecache->lt_opr), <proc);++ /*+ * Check this for all buckets that still have "true" in the bitmap+ * + * We already know the clauses use suitable operators (because that's+ * how we filtered them).+ */+ for (i = 0; i < mvhist->nbuckets; i++)+ {+ bool tmp;+ MVBucket bucket = mvhist->buckets[i];++ /*+ * Skip buckets that were already eliminated - this is impotant+ * considering how we update the info (we only lower the match)+ */+ if (buckets[i] == MVSTATS_MATCH_NONE)+ continue;++ /*+ * If it's not a "<" or ">" or "=" operator, just ignore the+ * clause. Otherwise note the relid and attnum for the variable.+ *+ * TODO I'm really unsure the handling of 'isgt' flag (that is, clauses+ * with reverse order of variable/constant) is correct. I wouldn't+ * be surprised if there was some mixup. Using the lt/gt operators+ * instead of messing with the opproc could make it simpler.+ * It would however be using a different operator than the query,+ * although it's not any shadier than using the selectivity function+ * as is done currently.+ *+ * FIXME Once the min/max values are deduplicated, we can easily minimize+ * the number of calls to the comparator (assuming we keep the+ * deduplicated structure). See the note on compression at MVBucket+ * serialize/deserialize methods.+ */+ switch (get_oprrest(expr->opno))+ {+ case F_SCALARLTSEL: /* column < constant */++ if (! isgt) /* (var < const) */+ {+ /*+ * First check whether the constant is below the lower boundary (in that + * case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ bucket->min[idx]));+ if (tmp)+ {+ buckets[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }++ /*+ * Now check whether the upper boundary is below the constant (in that+ * case it's a partial match).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ bucket->max[idx]));++ if (tmp)+ buckets[i] = MVSTATS_MATCH_PARTIAL; /* partial match */+ }+ else /* (const < var) */+ {+ /*+ * First check whether the constant is above the upper boundary (in that + * case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ bucket->max[idx],+ cst->constvalue));+ if (tmp)+ {+ buckets[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }++ /*+ * Now check whether the lower boundary is below the constant (in that+ * case it's a partial match).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ bucket->min[idx],+ cst->constvalue));++ if (tmp)+ buckets[i] = MVSTATS_MATCH_PARTIAL; /* partial match */+ }+ break;++ case F_SCALARGTSEL: /* column > constant */++ if (! isgt) /* (var > const) */+ {+ /*+ * First check whether the constant is above the upper boundary (in that + * case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ bucket->max[idx]));+ if (tmp)+ {+ buckets[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }++ /*+ * Now check whether the lower boundary is below the constant (in that+ * case it's a partial match).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ bucket->min[idx]));++ if (tmp)+ buckets[i] = MVSTATS_MATCH_PARTIAL; /* partial match */+ }+ else /* (const > var) */+ {+ /*+ * First check whether the constant is below the lower boundary (in+ * that case we can skip the bucket, because there's no overlap).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ bucket->min[idx],+ cst->constvalue));+ if (tmp)+ {+ buckets[i] = MVSTATS_MATCH_NONE; /* no match */+ continue;+ }++ /*+ * Now check whether the upper boundary is below the constant (in that+ * case it's a partial match).+ */+ tmp = DatumGetBool(FunctionCall2Coll(&opproc,+ DEFAULT_COLLATION_OID,+ bucket->max[idx],+ cst->constvalue));++ if (tmp)+ buckets[i] = MVSTATS_MATCH_PARTIAL; /* partial match */+ }++ break;++ case F_EQSEL:++ /*+ * We only check whether the value is within the bucket, using the lt/gt+ * operators fetched from type cache.+ * + * TODO We'll use the default 50% estimate, but that's probably way off+ * if there are multiple distinct values. Consider tweaking this a+ * somehow, e.g. using only a part inversely proportional to the+ * estimated number of distinct values in the bucket.+ *+ * TODO This does not handle inclusion flags at the moment, thus counting+ * some buckets twice (when hitting the boundary).+ * + * TODO Optimization is that if max[i] == min[i], it's effectively a MCV+ * item and we can count the whole bucket as a complete match (thus+ * using 100% bucket selectivity and not just 50%).+ * + * TODO Technically some buckets may "degenerate" into single-value+ * buckets (not necessarily for all the dimensions) - maybe this+ * is better than keeping a separate MCV list (multi-dimensional).+ * Update: Actually, that's unlikely to be better than a separate+ * MCV list for two reasons - first, it requires ~2x the space+ * (because of storing lower/upper boundaries) and second because+ * the buckets are ranges - depending on the partitioning algorithm+ * it may not even degenerate into (min=max) bucket. For example the+ * the current partitioning algorithm never does that.+ */+ tmp = DatumGetBool(FunctionCall2Coll(<proc,+ DEFAULT_COLLATION_OID,+ cst->constvalue,+ bucket->min[idx]));++ if (tmp)+ {+ buckets[i] = MVSTATS_MATCH_NONE; /* constvalue < min */+ continue;+ }++ tmp = DatumGetBool(FunctionCall2Coll(<proc,+ DEFAULT_COLLATION_OID,+ bucket->max[idx],+ cst->constvalue));++ if (tmp)+ {+ buckets[i] = MVSTATS_MATCH_NONE; /* constvalue > max */+ continue;+ }++ /* partial match */+ buckets[i] = MVSTATS_MATCH_PARTIAL;++ break;+ }+ }+ }+ }++ /* now, walk through the buckets and sum the selectivities */+ for (i = 0; i < mvhist->nbuckets; i++)+ {+ if (buckets[i] == MVSTATS_MATCH_FULL)+ s += mvhist->buckets[i]->ntuples;+ else if (buckets[i] == MVSTATS_MATCH_PARTIAL)+ s += 0.5 * mvhist->buckets[i]->ntuples;+ }++ return s;+}diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.yindex bd180e7..d725ae0 100644--- a/src/backend/parser/gram.y+++ b/src/backend/parser/gram.y@@ -366,6 +366,13 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
create_generic_options alter_generic_options
relation_expr_list dostmt_opt_list
+%type <list> OptStatsOptions +%type <str> stats_options_name+%type <node> stats_options_arg+%type <defelt> stats_options_elem+%type <list> stats_options_list++
%type <list> opt_fdw_options fdw_options
%type <defelt> fdw_option
@@ -484,7 +491,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
%type <keyword> unreserved_keyword type_func_name_keyword
%type <keyword> col_name_keyword reserved_keyword
-%type <node> TableConstraint TableLikeClause+%type <node> TableConstraint TableLikeClause TableStatistics
%type <ival> TableLikeOptionList TableLikeOption
%type <list> ColQualList
%type <node> ColConstraint ColConstraintElem ConstraintAttr
@@ -2312,6 +2319,14 @@ alter_table_cmd:
n->subtype = AT_DisableRowSecurity;
$$ = (Node *)n;
}
+ /* ALTER TABLE <name> ADD STATISTICS (options) ON (columns) ... */+ | ADD_P TableStatistics+ {+ AlterTableCmd *n = makeNode(AlterTableCmd);+ n->subtype = AT_AddStatistics;+ n->def = $2;+ $$ = (Node *)n;+ }
| alter_generic_options
{
AlterTableCmd *n = makeNode(AlterTableCmd);
@@ -3382,6 +3397,56 @@ OptConsTableSpace: USING INDEX TABLESPACE name { $$ = $4; }
ExistingIndex: USING INDEX index_name { $$ = $3; }
;
+/*****************************************************************************+ *+ * QUERY :+ * ALTER TABLE relname ADD STATISTICS (columns) WITH (options)+ *+ *****************************************************************************/++TableStatistics:+ STATISTICS OptStatsOptions ON '(' columnList ')'+ {+ StatisticsDef *n = makeNode(StatisticsDef);+ n->keys = $5;+ n->options = $2;+ $$ = (Node *) n;+ }+ ;++OptStatsOptions:+ '(' stats_options_list ')' { $$ = $2; }+ | /*EMPTY*/ { $$ = NIL; }+ ;++stats_options_list:+ stats_options_elem+ {+ $$ = list_make1($1);+ }+ | stats_options_list ',' stats_options_elem+ {+ $$ = lappend($1, $3);+ }+ ;++stats_options_elem:+ stats_options_name stats_options_arg+ {+ $$ = makeDefElem($1, $2);+ }+ ;++stats_options_name:+ NonReservedWord { $$ = $1; }+ ;++stats_options_arg:+ opt_boolean_or_string { $$ = (Node *) makeString($1); }+ | NumericOnly { $$ = (Node *) $1; }+ | /* EMPTY */ { $$ = NULL; }+ ;+
/*****************************************************************************
*
diff --git a/src/backend/utils/cache/syscache.c b/src/backend/utils/cache/syscache.cindex 94d951c..ec90773 100644--- a/src/backend/utils/cache/syscache.c+++ b/src/backend/utils/cache/syscache.c@@ -43,6 +43,7 @@
#include "catalog/pg_foreign_server.h"
#include "catalog/pg_foreign_table.h"
#include "catalog/pg_language.h"
+#include "catalog/pg_mv_statistic.h"
#include "catalog/pg_namespace.h"
#include "catalog/pg_opclass.h"
#include "catalog/pg_operator.h"
@@ -499,6 +500,17 @@ static const struct cachedesc cacheinfo[] = {
},
4
},
+ {MvStatisticRelationId, /* MVSTATOID */+ MvStatisticOidIndexId,+ 1,+ {+ ObjectIdAttributeNumber,+ 0,+ 0,+ 0+ },+ 128+ },
{NamespaceRelationId, /* NAMESPACENAME */
NamespaceNameIndexId,
1,
diff --git a/src/include/catalog/indexing.h b/src/include/catalog/indexing.hindex 870692c..d2266c0 100644--- a/src/include/catalog/indexing.h+++ b/src/include/catalog/indexing.h@@ -173,6 +173,11 @@ DECLARE_UNIQUE_INDEX(pg_largeobject_loid_pn_index, 2683, on pg_largeobject using
DECLARE_UNIQUE_INDEX(pg_largeobject_metadata_oid_index, 2996, on pg_largeobject_metadata using btree(oid oid_ops));
#define LargeObjectMetadataOidIndexId 2996
+DECLARE_UNIQUE_INDEX(pg_mv_statistic_oid_index, 3259, on pg_mv_statistic using btree(oid oid_ops));+#define MvStatisticOidIndexId 3259+DECLARE_INDEX(pg_mv_statistic_relid_index, 3264, on pg_mv_statistic using btree(starelid oid_ops));+#define MvStatisticRelidIndexId 3264+
DECLARE_UNIQUE_INDEX(pg_namespace_nspname_index, 2684, on pg_namespace using btree(nspname name_ops));
#define NamespaceNameIndexId 2684
DECLARE_UNIQUE_INDEX(pg_namespace_oid_index, 2685, on pg_namespace using btree(oid oid_ops));
diff --git a/src/include/catalog/pg_mv_statistic.h b/src/include/catalog/pg_mv_statistic.hnew file mode 100644index 0000000..d725957--- /dev/null+++ b/src/include/catalog/pg_mv_statistic.h@@ -0,0 +1,89 @@+/*-------------------------------------------------------------------------+ *+ * pg_mv_statistic.h+ * definition of the system "multivariate statistic" relation (pg_mv_statistic)+ * along with the relation's initial contents.+ *+ *+ * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group+ * Portions Copyright (c) 1994, Regents of the University of California+ *+ * src/include/catalog/pg_mv_statistic.h+ *+ * NOTES+ * the genbki.pl script reads this file and generates .bki+ * information from the DATA() statements.+ *+ *-------------------------------------------------------------------------+ */+#ifndef PG_MV_STATISTIC_H+#define PG_MV_STATISTIC_H++#include "catalog/genbki.h"++/* ----------------+ * pg_mv_statistic definition. cpp turns this into+ * typedef struct FormData_pg_mv_statistic+ * ----------------+ */+#define MvStatisticRelationId 3260++CATALOG(pg_mv_statistic,3260)+{+ /* These fields form the unique key for the entry: */+ Oid starelid; /* relation containing attributes */++ /* statistics requested to build */+ bool hist_enabled; /* build histogram? */+ bool mcv_enabled; /* build MCV list? */+ bool mcv_hashed; /* build hashed MCV? */+ bool assoc_enabled; /* analyze associations? */++ /* histogram / MCV size */+ int32 hist_max_buckets; /* max buckets */+ int32 mcv_max_items; /* max MCV items */++ /* statistics that are available (if requested) */+ bool hist_built; /* histogram was built */+ bool mcv_built; /* MCV list was built */+ bool assoc_built; /* associations were built */++ /* variable-length fields start here, but we allow direct access to stakeys */+ int2vector stakeys; /* array of column keys */++#ifdef CATALOG_VARLEN+ bytea staassoc; /* association rules (serialized) */+ bytea stamcv; /* MCV list (serialized) */+ bytea stahist; /* MV histogram (serialized) */+#endif++} FormData_pg_mv_statistic;++/* ----------------+ * Form_pg_mv_statistic corresponds to a pointer to a tuple with+ * the format of pg_mv_statistic relation.+ * ----------------+ */+typedef FormData_pg_mv_statistic *Form_pg_mv_statistic;++/* ----------------+ * compiler constants for pg_attrdef+ * ----------------+ */+#define Natts_pg_mv_statistic 14+#define Anum_pg_mv_statistic_starelid 1+#define Anum_pg_mv_statistic_hist_enabled 2+#define Anum_pg_mv_statistic_mcv_enabled 3+#define Anum_pg_mv_statistic_mcv_hashed 4+#define Anum_pg_mv_statistic_assoc_enabled 5+#define Anum_pg_mv_statistic_hist_max_buckets 6+#define Anum_pg_mv_statistic_mcv_max_items 7+#define Anum_pg_mv_statistic_hist_built 8+#define Anum_pg_mv_statistic_mcv_built 9+#define Anum_pg_mv_statistic_assoc_built 10+#define Anum_pg_mv_statistic_stakeys 11+#define Anum_pg_mv_statistic_staassoc 12+#define Anum_pg_mv_statistic_stamcv 13+#define Anum_pg_mv_statistic_stahist 14++#endif /* PG_MV_STATISTIC_H */diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.hindex 497e652..c3c03b6 100644--- a/src/include/catalog/pg_proc.h+++ b/src/include/catalog/pg_proc.h@@ -2676,6 +2676,13 @@ DESCR("current user privilege on any column by rel name");
DATA(insert OID = 3029 ( has_any_column_privilege PGNSP PGUID 12 10 0 0 0 f f f f t f s 2 0 16 "26 25" _null_ _null_ _null_ _null_ has_any_column_privilege_id _null_ _null_ _null_ ));
DESCR("current user privilege on any column by rel oid");
+DATA(insert OID = 3261 ( pg_mv_stats_histogram_info PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 25 "17" _null_ _null_ _null_ _null_ pg_mv_stats_histogram_info _null_ _null_ _null_ ));+DESCR("multi-variate statistics: histogram info");+DATA(insert OID = 3262 ( pg_mv_stats_mvclist_info PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 25 "17" _null_ _null_ _null_ _null_ pg_mv_stats_mvclist_info _null_ _null_ _null_ ));+DESCR("multi-variate statistics: MCV list info");+DATA(insert OID = 3263 ( pg_mv_stats_histogram_gnuplot PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 25 "17" _null_ _null_ _null_ _null_ pg_mv_stats_histogram_gnuplot _null_ _null_ _null_ ));+DESCR("multi-variate statistics: 2D histogram gnuplot");+
DATA(insert OID = 1928 ( pg_stat_get_numscans PGNSP PGUID 12 1 0 0 0 f f f f t f s 1 0 20 "26" _null_ _null_ _null_ _null_ pg_stat_get_numscans _null_ _null_ _null_ ));
DESCR("statistics: number of scans done for table/index");
DATA(insert OID = 1929 ( pg_stat_get_tuples_returned PGNSP PGUID 12 1 0 0 0 f f f f t f s 1 0 20 "26" _null_ _null_ _null_ _null_ pg_stat_get_tuples_returned _null_ _null_ _null_ ));
diff --git a/src/include/catalog/toasting.h b/src/include/catalog/toasting.hindex a4af551..c7839c0 100644--- a/src/include/catalog/toasting.h+++ b/src/include/catalog/toasting.h@@ -49,6 +49,7 @@ extern void BootstrapToastTable(char *relName,
DECLARE_TOAST(pg_attrdef, 2830, 2831);
DECLARE_TOAST(pg_constraint, 2832, 2833);
DECLARE_TOAST(pg_description, 2834, 2835);
+DECLARE_TOAST(pg_mv_statistic, 3265, 3954);
DECLARE_TOAST(pg_proc, 2836, 2837);
DECLARE_TOAST(pg_rewrite, 2838, 2839);
DECLARE_TOAST(pg_seclabel, 3598, 3599);
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.hindex bc71fea..b916edd 100644--- a/src/include/nodes/nodes.h+++ b/src/include/nodes/nodes.h@@ -413,6 +413,7 @@ typedef enum NodeTag
T_XmlSerialize,
T_WithClause,
T_CommonTableExpr,
+ T_StatisticsDef,
/*
* TAGS FOR REPLICATION GRAMMAR PARSE NODES (replnodes.h)
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.hindex 3e4f815..c3e458a 100644--- a/src/include/nodes/parsenodes.h+++ b/src/include/nodes/parsenodes.h@@ -543,6 +543,14 @@ typedef struct ColumnDef
int location; /* parse location, or -1 if none/unknown */
} ColumnDef;
+typedef struct StatisticsDef+{+ NodeTag type;+ List *keys; /* String nodes naming referenced column(s) */+ List *options; /* list of DefElem nodes */+} StatisticsDef;++
/*
* TableLikeClause - CREATE TABLE ( ... LIKE ... ) clause
*/
@@ -1338,7 +1346,8 @@ typedef enum AlterTableType
AT_ReplicaIdentity, /* REPLICA IDENTITY */
AT_EnableRowSecurity, /* ENABLE ROW SECURITY */
AT_DisableRowSecurity, /* DISABLE ROW SECURITY */
- AT_GenericOptions /* OPTIONS (...) */+ AT_GenericOptions, /* OPTIONS (...) */+ AT_AddStatistics /* add statistics */
} AlterTableType;
typedef struct ReplicaIdentityStmt
diff --git a/src/include/utils/mvstats.h b/src/include/utils/mvstats.hnew file mode 100644index 0000000..157891a--- /dev/null+++ b/src/include/utils/mvstats.h@@ -0,0 +1,283 @@+/*-------------------------------------------------------------------------+ *+ * mvstats.h+ * Multivariate statistics and selectivity estimation functions.+ *+ *+ * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group+ * Portions Copyright (c) 1994, Regents of the University of California+ *+ * src/include/utils/mvstats.h+ *+ *-------------------------------------------------------------------------+ */+#ifndef MVSTATS_H+#define MVSTATS_H++/*+ * Multivariate statistics for planner/optimizer, implementing extensions+ * of the single-column statistics:+ * + * - multivariate MCV list+ * - multivariate histograms+ *+ * There's also an experimental support for associative rules (values in+ * one column implying values in other columns - e.g. ZIP code implies+ * name of a city, etc.).+ *+ * The current implementation has various limitations:+ *+ * (a) it supports only data types passed by value+ *+ * (b) no support for NULL values+ *+ * Both (a) and (b) should be straightforward to fix (and usually+ * described in comments at related data structures or functions).+ *+ * The stats may be built only directly on columns, not on expressions.+ * And there are usually some additional technical limits (e.g. number+ * of columns in a histogram, etc.).+ *+ * Those limits serve mostly as sanity checks and while increasing them+ * is possible (the implementation should not break), it's expected to+ * lead either to very bad precision or expensive planning.+ */++/*+ * Multivariate histograms+ *+ * Histograms are a collection of buckets, represented by n-dimensional+ * rectangles. Each rectangle is delimited by an array of lower and+ * upper boundaries, so that for for the i-th attribute+ * + * min[i] <= value[i] <= max[i]+ *+ * Each bucket tracks frequency (fraction of tuples it contains),+ * information about the inequalities, number of distinct values in+ * each dimension (which is used when building the histogram) etc.+ *+ * The boundaries may be either inclusive or exclusive, or the whole+ * dimension may be NULL.+ *+ * The buckets may overlap (assuming the build algorithm keeps the+ * frequencies additive) or may not cover the whole space (i.e. allow+ * gaps). This entirely depends on the algorithm used to build the+ * histogram.+ *+ * The histograms are marked with a 'magic' constant, mostly to make+ * sure the bytea really is a histogram in serialized form.+ *+ * We do expect to support multiple histogram types, with different+ * features etc. The 'type' field is used to identify those types.+ * Technically some histogram types might use completely different+ * bucket representation, but that's not expected at the moment.+ *+ * TODO Add pointer to 'private' data, meant for private data for+ * other algorithms for building the histogram.+ *+ * TODO The current implementation does not handle NULL values (it's+ * somehow prepared for that, but the algorithm building the+ * histogram ignores them). The idea is to build buckets with one+ * or more NULL-only dimensions - there'll be at most 2^ndimensions+ * such buckets, which for 8 atttributes (current limit) is 256.+ * That's quite reasonable, considering we expect thousands of+ * buckets in total.+ * + * TODO This structure is used both when building the histogram, and+ * then when using it to compute estimates. That's why the last+ * few elements are not used once the histogram is built.+ *+ * TODO The limit on number of buckets is quite arbitrary, aiming for+ * sufficient accuracy while still being fast. Probably should be+ * replaced with a dynamic limit dependent on statistics target,+ * number of attributes (dimensions) and statistics target+ * associated with the attributes. Also, this needs to be related+ * to the number of sampled rows, by either clamping it to a+ * reasonable number (after seeing the number of rows) or using+ * it when computing the number of rows to sample. Something like+ * 10 rows per bucket seems reasonable.+ *+ * TODO We may replace the bool arrays with a suitably large data type+ * (say, uint16 or uint32) and get rid of the allocations. It's+ * unlikely we'll ever support more than 32 columns as that'd+ * result in poor precision, huge histograms (splitting each+ * dimension once would mean 2^32 buckets), and very expensive+ * estimation. MCVItem already does it this way.+ *+ * TODO Actually the distinct stats (both for combination of all columns+ * and for combinations of various subsets of columns) should be+ * moved to a separate structure (next to histogram/MCV/...) to+ * make it useful even without a histogram computed etc.+ */+typedef struct MVBucketData {++ /* Frequencies of this bucket. */+ float ntuples; /* frequency of tuples tuples */+ float ndistinct; /* frequency of distinct values */++ /*+ * Number of distinct values in each dimension. This is used when+ * building the histogram (and is not serialized/deserialized), but+ * it could be useful for estimating ndistinct for combinations of+ * columns.+ *+ * It would mean tracking 2^N values for each bucket, and even if+ * those values might be stores in 1B it's still a lot of space+ * (considering the expected number of buckets).+ *+ * TODO Consider tracking ndistincts for all attribute combinations.+ */+ uint32 *ndistincts;++ /*+ * Information about dimensions being NULL-only. Not yet used.+ */ + bool *nullsonly;++ /* lower boundaries - values and information about the inequalities */+ Datum *min;+ bool *min_inclusive;++ /* upper boundaries - values and information about the inequalities */+ Datum *max;+ bool *max_inclusive;++ /*+ * Sample tuples falling into this bucket, index of the dimension+ * the bucket was split by in the last step.+ *+ * XXX These fields are needed only while building the histogram,+ * and are not serialized at all.+ */+ HeapTuple *rows;+ uint32 numrows;+ int last_split_dimension;++} MVBucketData;++typedef MVBucketData *MVBucket;+++typedef struct MVHistogramData {++ uint32 magic; /* magic constant marker */+ uint32 type; /* type of histogram (BASIC) */+ uint32 nbuckets; /* number of buckets (buckets array) */+ uint32 ndimensions; /* number of dimensions */++ MVBucket *buckets; /* array of buckets */++} MVHistogramData;++typedef MVHistogramData *MVHistogram;+++/* used to flag stats serialized to bytea */+#define MVHIST_MAGIC 0x7F8C5670 /* marks serialized bytea */+#define MVHIST_TYPE_BASIC 1 /* basic histogram type */++/* limits (mostly sanity check, may be relaxed in the future) */+#define MVHIST_MAX_BUCKETS 16384 /* max number of buckets */++/* bucket size in a serialized form */+#define BUCKET_SIZE_SERIALIZED(ndims) \+ (offsetof(MVBucketData, ndistincts) + \+ (ndims) * (2 * sizeof(uint16) + sizeof(uint32) + 3 * sizeof(bool)))+++/*+ * Multivariate MCV (most-common value) lists+ *+ * A straight-forward extension of MCV items - i.e. a list (array) of+ * combinations of attribute values, together with a frequency and+ * null flags.+ *+ * This already uses the trick with using uint32 as a null bitmap.+ * + * TODO Shouldn't the MCVItemData use plain pointer for values, instead+ * of the single-item array trick?+ *+ * TODO It's possible to build a special case of MCV list, storing not+ * the actual values but only 32/64-bit hash. This is only useful+ * for estimating equality clauses and for large varlena types.+ */+typedef struct MCVItemData {+ double frequency; /* frequency of this combination */+ uint32 nulls; /* lags of NULL values (up to 32 columns) */+ Datum values[1]; /* variable-length (ndimensions) */+} MCVItemData;++typedef MCVItemData *MCVItem;++/* multivariate MCV list - essentally an array of MCV items */ +typedef struct MCVListData {+ uint32 magic; /* magic constant marker */+ uint32 type; /* type of MCV list (BASIC) */+ uint32 ndimensions; /* number of dimensions */+ uint32 nitems; /* number of MCV items in the array */+ MCVItem *items; /* array of MCV items */+} MCVListData;++typedef MCVListData *MCVList;++/* used to flag stats serialized to bytea */+#define MVSTAT_MCV_MAGIC 0xE1A651C2 /* marks serialized bytea */+#define MVSTAT_MCV_TYPE_BASIC 1 /* basic MCV list type */++/* TODO consider increasing the limit, and/or using statistics target */+#define MVSTAT_MCVLIST_MAX_ITEMS 1024 /* max items in MCV list */+++/*+ * Basic info about the stats, used when choosing what to use+ * + * TODO Add info about what statistics is available (histogram, MCV,+ * hashed MCV, assciative rules).+ */+typedef struct MVStatsData {+ Oid mvoid; /* OID of the stats in pg_mv_statistic */+ int2vector *stakeys; /* attnums for columns in the stats */+ bool hist_built; /* histogram is already available */+ bool mcv_built; /* MCV list is already available */+ bool assoc_built; /* associative rules available */+} MVStatsData;++typedef struct MVStatsData *MVStats;+++/*+ * Degree of how much MCV item / histogram bucket matches a clause.+ * This is then considered when computing the selectivity.+ */+#define MVSTATS_MATCH_NONE 0 /* no match at all */+#define MVSTATS_MATCH_PARTIAL 1 /* partial match */+#define MVSTATS_MATCH_FULL 2 /* full match */+++#define MVSTATS_MAX_DIMENSIONS 8 /* max number of attributes */++/*+ * TODO Maybe fetching the histogram/MCV list separately is inefficient?+ * Consider adding a single `fetch_stats` method, fetching all+ * stats specified using flags (or something like that).+ */+MVStats list_mv_stats(Oid relid, int *nstats, bool built_only);+bytea * fetch_mv_histogram(Oid mvoid);+bytea * fetch_mv_mcvlist(Oid mvoid);++/* deserialization of stats (serialization is private to analyze) */+MVHistogram deserialize_mv_histogram(bytea * data);+MCVList deserialize_mv_mcvlist(bytea * data);++/*+ * Returns index of the attribute number within the vector (i.e. a+ * dimension within the stats).+ */+int mv_get_index(AttrNumber varattno, int2vector * stakeys);++/* FIXME this probably belongs somewhere else (not to operations stats) */+extern Datum pg_mv_stats_histogram_info(PG_FUNCTION_ARGS);+extern Datum pg_mv_stats_histogram_gnuplot(PG_FUNCTION_ARGS);+extern Datum pg_mv_stats_mvclist_info(PG_FUNCTION_ARGS);++#endifdiff --git a/src/include/utils/syscache.h b/src/include/utils/syscache.hindex f97229f..a275bd5 100644--- a/src/include/utils/syscache.h+++ b/src/include/utils/syscache.h@@ -66,6 +66,7 @@ enum SysCacheIdentifier
INDEXRELID,
LANGNAME,
LANGOID,
+ MVSTATOID,
NAMESPACENAME,
NAMESPACEOID,
OPERNAMENSP,
diff --git a/src/test/regress/regression.diffs b/src/test/regress/regression.diffsnew file mode 100644index 0000000..179c09d--- /dev/null+++ b/src/test/regress/regression.diffs@@ -0,0 +1,294 @@+*** /home/tomas/work/postgres/src/test/regress/expected/updatable_views.out 2014-10-29 00:22:04.820171312 +0100+--- /home/tomas/work/postgres/src/test/regress/results/updatable_views.out 2014-11-10 02:54:44.083052362 +0100+***************+*** 657,668 ****+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! table_name | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ------------+--------------+--------------------+----------------------+----------------------+----------------------------+! rw_view1 | NO | NO | NO | NO | NO+! rw_view2 | NO | NO | NO | NO | NO+! (2 rows)+! + SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+--- 657,663 ----+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! ERROR: no relation entry for relid 1880+ SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+***************+*** 710,721 ****+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! table_name | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ------------+--------------+--------------------+----------------------+----------------------+----------------------------+! rw_view1 | NO | NO | NO | NO | YES+! rw_view2 | NO | NO | NO | NO | NO+! (2 rows)+! + SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+--- 705,711 ----+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! ERROR: no relation entry for relid 1880+ SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+***************+*** 746,757 ****+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! table_name | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ------------+--------------+--------------------+----------------------+----------------------+----------------------------+! rw_view1 | NO | NO | YES | NO | YES+! rw_view2 | NO | NO | NO | NO | NO+! (2 rows)+! + SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+--- 736,742 ----+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! ERROR: no relation entry for relid 1880+ SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+***************+*** 782,793 ****+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! table_name | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ------------+--------------+--------------------+----------------------+----------------------+----------------------------+! rw_view1 | NO | NO | YES | YES | YES+! rw_view2 | NO | NO | NO | NO | NO+! (2 rows)+! + SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+--- 767,773 ----+ FROM information_schema.views+ WHERE table_name LIKE 'rw_view%'+ ORDER BY table_name;+! ERROR: no relation entry for relid 1880+ SELECT table_name, column_name, is_updatable+ FROM information_schema.columns+ WHERE table_name LIKE 'rw_view%'+***************+*** 1385,1398 ****+ Options: check_option=local+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view1';+! table_catalog | table_schema | table_name | view_definition | check_option | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ---------------+--------------+------------+------------------------------------+--------------+--------------+--------------------+----------------------+----------------------+----------------------------+! regression | public | rw_view1 | SELECT base_tbl.a, +| LOCAL | YES | YES | NO | NO | NO+! | | | base_tbl.b +| | | | | | +! | | | FROM base_tbl +| | | | | | +! | | | WHERE (base_tbl.a < base_tbl.b); | | | | | | +! (1 row)+! + INSERT INTO rw_view1 VALUES(3,4); -- ok+ INSERT INTO rw_view1 VALUES(4,3); -- should fail+ ERROR: new row violates WITH CHECK OPTION for "rw_view1"+--- 1365,1371 ----+ Options: check_option=local+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view1';+! ERROR: no relation entry for relid 1880+ INSERT INTO rw_view1 VALUES(3,4); -- ok+ INSERT INTO rw_view1 VALUES(4,3); -- should fail+ ERROR: new row violates WITH CHECK OPTION for "rw_view1"+***************+*** 1437,1449 ****+ Options: check_option=cascaded+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view2';+! table_catalog | table_schema | table_name | view_definition | check_option | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ---------------+--------------+------------+----------------------------+--------------+--------------+--------------------+----------------------+----------------------+----------------------------+! regression | public | rw_view2 | SELECT rw_view1.a +| CASCADED | YES | YES | NO | NO | NO+! | | | FROM rw_view1 +| | | | | | +! | | | WHERE (rw_view1.a < 10); | | | | | | +! (1 row)+! + INSERT INTO rw_view2 VALUES (-5); -- should fail+ ERROR: new row violates WITH CHECK OPTION for "rw_view1"+ DETAIL: Failing row contains (-5).+--- 1410,1416 ----+ Options: check_option=cascaded+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view2';+! ERROR: no relation entry for relid 1880+ INSERT INTO rw_view2 VALUES (-5); -- should fail+ ERROR: new row violates WITH CHECK OPTION for "rw_view1"+ DETAIL: Failing row contains (-5).+***************+*** 1477,1489 ****+ Options: check_option=local+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view2';+! table_catalog | table_schema | table_name | view_definition | check_option | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ---------------+--------------+------------+----------------------------+--------------+--------------+--------------------+----------------------+----------------------+----------------------------+! regression | public | rw_view2 | SELECT rw_view1.a +| LOCAL | YES | YES | NO | NO | NO+! | | | FROM rw_view1 +| | | | | | +! | | | WHERE (rw_view1.a < 10); | | | | | | +! (1 row)+! + INSERT INTO rw_view2 VALUES (-10); -- ok, but not in view+ INSERT INTO rw_view2 VALUES (20); -- should fail+ ERROR: new row violates WITH CHECK OPTION for "rw_view2"+--- 1444,1450 ----+ Options: check_option=local+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view2';+! ERROR: no relation entry for relid 1880+ INSERT INTO rw_view2 VALUES (-10); -- ok, but not in view+ INSERT INTO rw_view2 VALUES (20); -- should fail+ ERROR: new row violates WITH CHECK OPTION for "rw_view2"+***************+*** 1517,1529 ****+ WHERE rw_view1.a < 10;+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view2';+! table_catalog | table_schema | table_name | view_definition | check_option | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ---------------+--------------+------------+----------------------------+--------------+--------------+--------------------+----------------------+----------------------+----------------------------+! regression | public | rw_view2 | SELECT rw_view1.a +| NONE | YES | YES | NO | NO | NO+! | | | FROM rw_view1 +| | | | | | +! | | | WHERE (rw_view1.a < 10); | | | | | | +! (1 row)+! + INSERT INTO rw_view2 VALUES (30); -- ok, but not in view+ SELECT * FROM base_tbl;+ a +--- 1478,1484 ----+ WHERE rw_view1.a < 10;+ + SELECT * FROM information_schema.views WHERE table_name = 'rw_view2';+! ERROR: no relation entry for relid 1880+ INSERT INTO rw_view2 VALUES (30); -- ok, but not in view+ SELECT * FROM base_tbl;+ a +***************+*** 1543,1559 ****+ CREATE VIEW rw_view2 AS SELECT * FROM rw_view1 WHERE a > 0;+ CREATE VIEW rw_view3 AS SELECT * FROM rw_view2 WITH CHECK OPTION;+ SELECT * FROM information_schema.views WHERE table_name LIKE E'rw\\_view_' ORDER BY table_name;+! table_catalog | table_schema | table_name | view_definition | check_option | is_updatable | is_insertable_into | is_trigger_updatable | is_trigger_deletable | is_trigger_insertable_into +! ---------------+--------------+------------+---------------------------+--------------+--------------+--------------------+----------------------+----------------------+----------------------------+! regression | public | rw_view1 | SELECT base_tbl.a +| CASCADED | YES | YES | NO | NO | NO+! | | | FROM base_tbl; | | | | | | +! regression | public | rw_view2 | SELECT rw_view1.a +| NONE | YES | YES | NO | NO | NO+! | | | FROM rw_view1 +| | | | | | +! | | | WHERE (rw_view1.a > 0); | | | | | | +! regression | public | rw_view3 | SELECT rw_view2.a +| CASCADED | YES | YES | NO | NO | NO+! | | | FROM rw_view2; | | | | | | +! (3 rows)+! + INSERT INTO rw_view1 VALUES (-1); -- ok+ INSERT INTO rw_view1 VALUES (1); -- ok+ INSERT INTO rw_view2 VALUES (-2); -- ok, but not in view+--- 1498,1504 ----+ CREATE VIEW rw_view2 AS SELECT * FROM rw_view1 WHERE a > 0;+ CREATE VIEW rw_view3 AS SELECT * FROM rw_view2 WITH CHECK OPTION;+ SELECT * FROM information_schema.views WHERE table_name LIKE E'rw\\_view_' ORDER BY table_name;+! ERROR: no relation entry for relid 1880+ INSERT INTO rw_view1 VALUES (-1); -- ok+ INSERT INTO rw_view1 VALUES (1); -- ok+ INSERT INTO rw_view2 VALUES (-2); -- ok, but not in view++======================================================================++*** /home/tomas/work/postgres/src/test/regress/expected/sanity_check.out 2014-10-29 00:22:04.812171313 +0100+--- /home/tomas/work/postgres/src/test/regress/results/sanity_check.out 2014-11-10 02:54:44.150052357 +0100+***************+*** 113,118 ****+--- 113,119 ----+ pg_language|t+ pg_largeobject|t+ pg_largeobject_metadata|t++ pg_mv_statistic|t+ pg_namespace|t+ pg_opclass|t+ pg_operator|t++======================================================================++*** /home/tomas/work/postgres/src/test/regress/expected/rowsecurity.out 2014-10-29 00:22:04.811171313 +0100+--- /home/tomas/work/postgres/src/test/regress/results/rowsecurity.out 2014-11-10 02:54:45.775052238 +0100+***************+*** 901,925 ****+ -- prepared statement with rls_regress_user0 privilege+ PREPARE p1(int) AS SELECT * FROM t1 WHERE a <= $1;+ EXECUTE p1(2);+! a | b +! ---+-----+! 2 | bbb+! 2 | bcd+! 2 | yyy+! (3 rows)+! + EXPLAIN (COSTS OFF) EXECUTE p1(2);+! QUERY PLAN +! ----------------------------------------------+! Append+! -> Seq Scan on t1+! Filter: ((a <= 2) AND ((a % 2) = 0))+! -> Seq Scan on t2+! Filter: ((a <= 2) AND ((a % 2) = 0))+! -> Seq Scan on t3+! Filter: ((a <= 2) AND ((a % 2) = 0))+! (7 rows)+! + -- superuser is allowed to bypass RLS checks+ RESET SESSION AUTHORIZATION;+ SET row_security TO OFF;+--- 901,909 ----+ -- prepared statement with rls_regress_user0 privilege+ PREPARE p1(int) AS SELECT * FROM t1 WHERE a <= $1;+ EXECUTE p1(2);+! ERROR: no relation entry for relid 530+ EXPLAIN (COSTS OFF) EXECUTE p1(2);+! ERROR: no relation entry for relid 530+ -- superuser is allowed to bypass RLS checks+ RESET SESSION AUTHORIZATION;+ SET row_security TO OFF;++======================================================================++*** /home/tomas/work/postgres/src/test/regress/expected/rules.out 2014-10-29 00:22:04.812171313 +0100+--- /home/tomas/work/postgres/src/test/regress/results/rules.out 2014-11-10 02:54:48.329052050 +0100+***************+*** 1353,1358 ****+--- 1353,1368 ----+ LEFT JOIN pg_namespace n ON ((n.oid = c.relnamespace)))+ LEFT JOIN pg_tablespace t ON ((t.oid = c.reltablespace)))+ WHERE (c.relkind = 'm'::"char");++ pg_mv_stats| SELECT n.nspname AS schemaname,++ c.relname AS tablename,++ s.stakeys AS attnums,++ length(s.stamcv) AS mcvbytes,++ pg_mv_stats_mvclist_info(s.stamcv) AS mcvinfo,++ length(s.stahist) AS histbytes,++ pg_mv_stats_histogram_info(s.stahist) AS histinfo++ FROM ((pg_mv_statistic s++ JOIN pg_class c ON ((c.oid = s.starelid)))++ LEFT JOIN pg_namespace n ON ((n.oid = c.relnamespace)));+ pg_policies| SELECT n.nspname AS schemaname,+ c.relname AS tablename,+ rs.rsecpolname AS policyname,++======================================================================+diff --git a/src/test/regress/regression.out b/src/test/regress/regression.outnew file mode 100644index 0000000..48a4a25--- /dev/null+++ b/src/test/regress/regression.out@@ -0,0 +1,147 @@+test tablespace ... ok+test boolean ... ok+test char ... ok+test name ... ok+test varchar ... ok+test text ... ok+test int2 ... ok+test int4 ... ok+test int8 ... ok+test oid ... ok+test float4 ... ok+test float8 ... ok+test bit ... ok+test numeric ... ok+test txid ... ok+test uuid ... ok+test enum ... ok+test money ... ok+test rangetypes ... ok+test pg_lsn ... ok+test regproc ... ok+test strings ... ok+test numerology ... ok+test point ... ok+test lseg ... ok+test line ... ok+test box ... ok+test path ... ok+test polygon ... ok+test circle ... ok+test date ... ok+test time ... ok+test timetz ... ok+test timestamp ... ok+test timestamptz ... ok+test interval ... ok+test abstime ... ok+test reltime ... ok+test tinterval ... ok+test inet ... ok+test macaddr ... ok+test tstypes ... ok+test comments ... ok+test geometry ... ok+test horology ... ok+test regex ... ok+test oidjoins ... ok+test type_sanity ... ok+test opr_sanity ... ok+test insert ... ok+test create_function_1 ... ok+test create_type ... ok+test create_table ... ok+test create_function_2 ... ok+test copy ... ok+test copyselect ... ok+test create_misc ... ok+test create_operator ... ok+test create_index ... ok+test create_view ... ok+test create_aggregate ... ok+test create_function_3 ... ok+test create_cast ... ok+test constraints ... ok+test triggers ... ok+test inherit ... ok+test create_table_like ... ok+test typed_table ... ok+test vacuum ... ok+test drop_if_exists ... ok+test updatable_views ... FAILED+test sanity_check ... FAILED+test errors ... ok+test select ... ok+test select_into ... ok+test select_distinct ... ok+test select_distinct_on ... ok+test select_implicit ... ok+test select_having ... ok+test subselect ... ok+test union ... ok+test case ... ok+test join ... ok+test aggregates ... ok+test transactions ... ok+test random ... ok+test portals ... ok+test arrays ... ok+test btree_index ... ok+test hash_index ... ok+test update ... ok+test delete ... ok+test namespace ... ok+test prepared_xacts ... ok+test privileges ... ok+test security_label ... ok+test collate ... ok+test matview ... ok+test lock ... ok+test replica_identity ... ok+test rowsecurity ... FAILED+test alter_generic ... ok+test brin ... ok+test misc ... ok+test psql ... ok+test async ... ok+test rules ... FAILED+test event_trigger ... ok+test select_views ... ok+test portals_p2 ... ok+test foreign_key ... ok+test cluster ... ok+test dependency ... ok+test guc ... ok+test bitmapops ... ok+test combocid ... ok+test tsearch ... ok+test tsdicts ... ok+test foreign_data ... ok+test window ... ok+test xmlmap ... ok+test functional_deps ... ok+test advisory_lock ... ok+test json ... ok+test jsonb ... ok+test indirect_toast ... ok+test equivclass ... ok+test plancache ... ok+test limit ... ok+test plpgsql ... ok+test copy2 ... ok+test temp ... ok+test domain ... ok+test rangefuncs ... ok+test prepare ... ok+test without_oid ... ok+test conversion ... ok+test truncate ... ok+test alter_table ... ok+test sequence ... ok+test polymorphism ... ok+test rowtypes ... ok+test returning ... ok+test largeobject ... ok+test with ... ok+test xml ... ok+test stats ... ok
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tv@fuzzy.cz
Subject: Re: WIP: multivariate statistics / proof of concept
In-Reply-To: <5460244C.8080109@fuzzy.cz>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox