0003-multivariate-MCV-lists.patch
text/x-diff
Filename: 0003-multivariate-MCV-lists.patch
Type: text/x-diff
Part: 2
Patch
Format: unified
Series: patch 0003
| File | + | − |
|---|---|---|
| src/backend/catalog/system_views.sql | 3 | 1 |
| src/backend/commands/tablecmds.c | 43 | 4 |
| src/backend/optimizer/path/clausesel.c | 1079 | 74 |
| src/backend/utils/mvstats/common.c | 49 | 9 |
| src/backend/utils/mvstats/common.h | 10 | 1 |
| src/backend/utils/mvstats/Makefile | 1 | 1 |
| src/backend/utils/mvstats/mcv.c | 1002 | 0 |
| src/include/catalog/pg_mv_statistic.h | 14 | 4 |
| src/include/catalog/pg_proc.h | 2 | 0 |
| src/include/utils/mvstats.h | 63 | 5 |
| src/test/regress/expected/mv_mcv.out | 210 | 0 |
| src/test/regress/expected/rules.out | 3 | 1 |
| src/test/regress/parallel_schedule | 1 | 1 |
| src/test/regress/serial_schedule | 1 | 0 |
| src/test/regress/sql/mv_mcv.sql | 181 | 0 |
>From 13c3d4cbe85bbbe6b9509de15dd08384df1df97f Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tv@fuzzy.cz>
Date: Sun, 11 Jan 2015 20:15:37 +0100
Subject: [PATCH 3/5] multivariate MCV lists
- extends the pg_mv_statistic catalog (add 'mcv' fields)
- building the MCV lists during ANALYZE
- simple estimation while planning the queries
Includes regression tests, mostly equal to regression tests for
functional dependencies.
---
src/backend/catalog/system_views.sql | 4 +-
src/backend/commands/tablecmds.c | 47 +-
src/backend/optimizer/path/clausesel.c | 1153 ++++++++++++++++++++++++++++++--
src/backend/utils/mvstats/Makefile | 2 +-
src/backend/utils/mvstats/common.c | 58 +-
src/backend/utils/mvstats/common.h | 11 +-
src/backend/utils/mvstats/mcv.c | 1002 +++++++++++++++++++++++++++
src/include/catalog/pg_mv_statistic.h | 18 +-
src/include/catalog/pg_proc.h | 2 +
src/include/utils/mvstats.h | 68 +-
src/test/regress/expected/mv_mcv.out | 210 ++++++
src/test/regress/expected/rules.out | 4 +-
src/test/regress/parallel_schedule | 2 +-
src/test/regress/serial_schedule | 1 +
src/test/regress/sql/mv_mcv.sql | 181 +++++
15 files changed, 2662 insertions(+), 101 deletions(-)
create mode 100644 src/backend/utils/mvstats/mcv.c
create mode 100644 src/test/regress/expected/mv_mcv.out
create mode 100644 src/test/regress/sql/mv_mcv.sql
diff --git a/src/backend/catalog/system_views.sql b/src/backend/catalog/system_views.sql
index d05a716..4538e63 100644
--- a/src/backend/catalog/system_views.sql
+++ b/src/backend/catalog/system_views.sql
@@ -156,7 +156,9 @@ CREATE VIEW pg_mv_stats AS
C.relname AS tablename,
S.stakeys AS attnums,
length(S.stadeps) as depsbytes,
- pg_mv_stats_dependencies_info(S.stadeps) as depsinfo
+ pg_mv_stats_dependencies_info(S.stadeps) as depsinfo,
+ length(S.stamcv) AS mcvbytes,
+ pg_mv_stats_mcvlist_info(S.stamcv) AS mcvinfo
FROM (pg_mv_statistic S JOIN pg_class C ON (C.oid = S.starelid))
LEFT JOIN pg_namespace N ON (N.oid = C.relnamespace);
diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 965d342..fae0fc7 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -11901,7 +11901,13 @@ static void ATExecAddStatistics(AlteredTableInfo *tab, Relation rel,
Relation mvstatrel;
/* by default build everything */
- bool build_dependencies = false;
+ bool build_dependencies = false,
+ build_mcv = false;
+
+ int32 max_mcv_items = -1;
+
+ /* options required because of other options */
+ bool require_mcv = false;
Assert(IsA(def, StatisticsDef));
@@ -11956,6 +11962,29 @@ static void ATExecAddStatistics(AlteredTableInfo *tab, Relation rel,
if (strcmp(opt->defname, "dependencies") == 0)
build_dependencies = defGetBoolean(opt);
+ else if (strcmp(opt->defname, "mcv") == 0)
+ build_mcv = defGetBoolean(opt);
+ else if (strcmp(opt->defname, "max_mcv_items") == 0)
+ {
+ max_mcv_items = defGetInt32(opt);
+
+ /* this option requires 'mcv' to be enabled */
+ require_mcv = true;
+
+ /* sanity check */
+ if (max_mcv_items < MVSTAT_MCVLIST_MIN_ITEMS)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("max number of MCV items must be at least %d",
+ MVSTAT_MCVLIST_MIN_ITEMS)));
+
+ else if (max_mcv_items > MVSTAT_MCVLIST_MAX_ITEMS)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("max number of MCV items is %d",
+ MVSTAT_MCVLIST_MAX_ITEMS)));
+
+ }
else
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
@@ -11964,10 +11993,16 @@ static void ATExecAddStatistics(AlteredTableInfo *tab, Relation rel,
}
/* check that at least some statistics were requested */
- if (! build_dependencies)
+ if (! (build_dependencies || build_mcv))
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
- errmsg("no statistics type (dependencies) was requested")));
+ errmsg("no statistics type (dependencies, mcv) was requested")));
+
+ /* now do some checking of the options */
+ if (require_mcv && (! build_mcv))
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("option 'mcv' is required by other options(s)")));
/* sort the attnums and build int2vector */
qsort(attnums, numcols, sizeof(int16), compare_int16);
@@ -11983,9 +12018,13 @@ static void ATExecAddStatistics(AlteredTableInfo *tab, Relation rel,
values[Anum_pg_mv_statistic_starelid-1] = ObjectIdGetDatum(RelationGetRelid(rel));
values[Anum_pg_mv_statistic_stakeys -1] = PointerGetDatum(stakeys);
+
values[Anum_pg_mv_statistic_deps_enabled -1] = BoolGetDatum(build_dependencies);
+ values[Anum_pg_mv_statistic_mcv_enabled -1] = BoolGetDatum(build_mcv);
+ values[Anum_pg_mv_statistic_mcv_max_items -1] = Int32GetDatum(max_mcv_items);
- nulls[Anum_pg_mv_statistic_stadeps -1] = true;
+ nulls[Anum_pg_mv_statistic_stadeps -1] = true;
+ nulls[Anum_pg_mv_statistic_stamcv -1] = true;
/* insert the tuple into pg_mv_statistic */
mvstatrel = heap_open(MvStatisticRelationId, RowExclusiveLock);
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index e742827..d24aedf 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -20,6 +20,7 @@
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/plancat.h"
+#include "optimizer/var.h"
#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
@@ -50,17 +51,46 @@ typedef struct RangeQueryClause
static void addRangeClause(RangeQueryClause **rqlist, Node *clause,
bool varonleft, bool isLTsel, Selectivity s2);
+#define MV_CLAUSE_TYPE_FDEP 0x01
+#define MV_CLAUSE_TYPE_MCV 0x02
static bool clause_is_mv_compatible(PlannerInfo *root, Node *clause, Oid varRelid,
- Oid *relid, AttrNumber *attnum, SpecialJoinInfo *sjinfo);
+ Oid *relid, Bitmapset **attnums, SpecialJoinInfo *sjinfo,
+ int type);
static Bitmapset *collect_mv_attnums(PlannerInfo *root, List *clauses,
- Oid varRelid, Oid *relid, SpecialJoinInfo *sjinfo);
+ Oid varRelid, Oid *relid, SpecialJoinInfo *sjinfo,
+ int type);
static List *clauselist_apply_dependencies(PlannerInfo *root, List *clauses,
Oid varRelid, int nmvstats, MVStats mvstats,
SpecialJoinInfo *sjinfo);
+static int choose_mv_statistics(int nmvstats, MVStats mvstats,
+ Bitmapset *attnums);
+static List *clauselist_mv_split(PlannerInfo *root, SpecialJoinInfo *sjinfo,
+ List *clauses, Oid varRelid,
+ List **mvclauses, MVStats mvstats, int types);
+
+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 int update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
+ int2vector *stakeys, MCVList mcvlist,
+ int nmatches, char * matches,
+ Selectivity *lowsel, bool *fullmatch,
+ bool is_or);
+
+/* used for merging bitmaps - AND (min), OR (max) */
+#define MAX(x, y) (((x) > (y)) ? (x) : (y))
+#define MIN(x, y) (((x) < (y)) ? (x) : (y))
+
+#define UPDATE_RESULT(m,r,or) \
+ (m) = (or) ? (MAX(m,r)) : (MIN(m,r))
+
/****************************************************************************
* ROUTINES TO COMPUTE SELECTIVITIES
****************************************************************************/
@@ -197,15 +227,19 @@ clauselist_selectivity(PlannerInfo *root,
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 referenced by mv-compatible clauses */
- mvattnums = collect_mv_attnums(root, clauses, varRelid, &relid, sjinfo);
+ /*
+ * Collect attributes referenced by mv-compatible clauses (looking
+ * for clauses compatible with functional dependencies for now).
+ */
+ mvattnums = collect_mv_attnums(root, clauses, varRelid, &relid, sjinfo,
+ MV_CLAUSE_TYPE_FDEP);
/*
* If there are mv-compatible clauses, referencing at least two
@@ -227,6 +261,49 @@ clauselist_selectivity(PlannerInfo *root,
}
/*
+ * Recollect attributes from mv-compatible clauses (maybe we've
+ * removed so many clauses we have a single mv-compatible attnum).
+ * From now on we're only interested in MCV-compatible clauses.
+ */
+ mvattnums = collect_mv_attnums(root, clauses, varRelid, &relid, sjinfo,
+ MV_CLAUSE_TYPE_MCV);
+
+ /*
+ * If there still are at least two columns, we'll try to select
+ * a suitable multivariate stats.
+ */
+ if (bms_num_members(mvattnums) >= 2)
+ {
+ /* fetch info from the catalog (not the serialized stats yet) */
+ mvstats = list_mv_stats(relid, &nmvstats, true);
+
+ /* see choose_mv_statistics() for details */
+ if (nmvstats > 0)
+ {
+ int idx = choose_mv_statistics(nmvstats, mvstats, mvattnums);
+
+ if (idx >= 0) /* we have a matching stats */
+ {
+ MVStats mvstat = &mvstats[idx];
+
+ /* clauses compatible with multi-variate stats */
+ List *mvclauses = NIL;
+
+ /* split the clauselist into regular and mv-clauses */
+ clauses = clauselist_mv_split(root, sjinfo, clauses,
+ varRelid, &mvclauses, mvstat,
+ MV_CLAUSE_TYPE_MCV);
+
+ /* 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
* does gets inserted into an rqlist entry.
@@ -901,12 +978,198 @@ 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;
+
+ /*
+ * 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 selectivity */
+ return clauselist_mv_selectivity_mcvlist(root, clauses, mvstats,
+ &fullmatch, &mcv_low);
+}
+
/*
* Collect attributes from mv-compatible clauses.
*/
static Bitmapset *
collect_mv_attnums(PlannerInfo *root, List *clauses, Oid varRelid,
- Oid *relid, SpecialJoinInfo *sjinfo)
+ Oid *relid, SpecialJoinInfo *sjinfo, int types)
{
Bitmapset *attnums = NULL;
ListCell *l;
@@ -922,12 +1185,11 @@ collect_mv_attnums(PlannerInfo *root, List *clauses, Oid varRelid,
*/
foreach (l, clauses)
{
- AttrNumber attnum;
Node *clause = (Node *) lfirst(l);
- /* ignore the result for now - we only need the info */
- if (clause_is_mv_compatible(root, clause, varRelid, relid, &attnum, sjinfo))
- attnums = bms_add_member(attnums, attnum);
+ /* ignore the result here - we only need the attnums */
+ clause_is_mv_compatible(root, clause, varRelid, relid, &attnums,
+ sjinfo, types);
}
/*
@@ -946,6 +1208,180 @@ collect_mv_attnums(PlannerInfo *root, List *clauses, Oid varRelid,
}
/*
+ * We're looking for statistics matching at least 2 attributes,
+ * referenced in the clauses compatible with multivariate statistics.
+ * The current selection criteria is very simple - we choose the
+ * statistics referencing the most attributes.
+ *
+ * If there are multiple statistics referencing the same number of
+ * columns (from the clauses), the one with less source columns
+ * (as listed in the ADD STATISTICS when creating the statistics) wins.
+ * Other wise the first one wins.
+ *
+ * This is a very simple criteria, and has several weaknesses:
+ *
+ * (a) does not consider the accuracy of the statistics
+ *
+ * If there are two histograms built on the same set of columns,
+ * but one has 100 buckets and the other one has 1000 buckets (thus
+ * likely providing better estimates), this is not currently
+ * considered.
+ *
+ * (b) does not consider the type of statistics
+ *
+ * If there are three statistics - one containing just a MCV list,
+ * another one with just a histogram and a third one with both,
+ * this is not considered.
+ *
+ * (c) does not consider the number of clauses
+ *
+ * As explained, only the number of referenced attributes counts,
+ * so if there are multiple clauses on a single attribute, this
+ * still counts as a single attribute.
+ *
+ * (d) does not consider type of condition
+ *
+ * Some clauses may work better with some statistics - for example
+ * equality clauses probably work better with MCV lists than with
+ * histograms. But IS [NOT] NULL conditions may often work better
+ * with histograms (thanks to NULL-buckets).
+ *
+ * So for example with five WHERE conditions
+ *
+ * WHERE (a = 1) AND (b = 1) AND (c = 1) AND (d = 1) AND (e = 1)
+ *
+ * and statistics on (a,b), (a,b,e) and (a,b,c,d), the last one will be
+ * selected as it references the most columns.
+ *
+ * Once we have selected the multivariate statistics, we split the list
+ * of clauses into two parts - conditions that are compatible with the
+ * selected stats, and conditions are estimated using simple statistics.
+ *
+ * From the example above, conditions
+ *
+ * (a = 1) AND (b = 1) AND (c = 1) AND (d = 1)
+ *
+ * will be estimated using the multivariate statistics (a,b,c,d) while
+ * the last condition (e = 1) will get estimated using the regular ones.
+ *
+ * There are various alternative selection criteria (e.g. counting
+ * conditions instead of just referenced attributes), but eventually
+ * the best option should be to combine multiple statistics. But that's
+ * much harder to do correctly.
+ *
+ * TODO Select multiple statistics and combine them when computing
+ * the estimate.
+ *
+ * TODO This will probably have to consider compatibility of clauses,
+ * because 'dependencies' will probably work only with equality
+ * clauses.
+ */
+static int
+choose_mv_statistics(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 */
+
+ /*
+ * Walk through the statistics (simple array with nmvstats elements)
+ * and for each one count the referenced attributes (encoded in
+ * the 'attnums' bitmap).
+ */
+ for (i = 0; i < nmvstats; i++)
+ {
+ /* columns matching this statistics */
+ int matches = 0;
+
+ 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 statistics when it improves the number of matches or
+ * when it matches the same number of attributes but 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 statistics, and the remaining
+ * clauses (either non-mvcompatible, or not related to the histogram).
+ */
+static List *
+clauselist_mv_split(PlannerInfo *root, SpecialJoinInfo *sjinfo,
+ List *clauses, Oid varRelid, List **mvclauses,
+ MVStats mvstats, int types)
+{
+ 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;
+
+ Bitmapset *mvattnums = NULL;
+
+ /* build bitmap of attributes covered by the stats, so we can
+ * do bms_is_subset later */
+ for (i = 0; i < numattrs; i++)
+ mvattnums = bms_add_member(mvattnums, attrs->values[i]);
+
+ /* erase the list of mv-compatible clauses */
+ *mvclauses = NIL;
+
+ foreach (l, clauses)
+ {
+ bool match = false; /* by default not mv-compatible */
+ Bitmapset *attnums = NULL;
+ Node *clause = (Node *) lfirst(l);
+
+ if (clause_is_mv_compatible(root, clause, varRelid, NULL,
+ &attnums, sjinfo, types))
+ {
+ /* are all the attributes part of the selected stats? */
+ if (bms_is_subset(attnums, mvattnums))
+ match = true;
+ }
+
+ /*
+ * The clause matches the selected stats, so put it to the list
+ * of mv-compatible clauses. Otherwise, keep it in the list of
+ * 'regular' clauses (that may be selected later).
+ */
+ if (match)
+ *mvclauses = lappend(*mvclauses, clause);
+ else
+ non_mvclauses = lappend(non_mvclauses, clause);
+ }
+
+ /*
+ * 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
@@ -964,96 +1400,205 @@ collect_mv_attnums(PlannerInfo *root, List *clauses, Oid varRelid,
*/
static bool
clause_is_mv_compatible(PlannerInfo *root, Node *clause, Oid varRelid,
- Oid *relid, AttrNumber *attnum, SpecialJoinInfo *sjinfo)
+ Oid *relid, Bitmapset **attnums, SpecialJoinInfo *sjinfo,
+ int types)
{
+ Relids clause_relids;
+ Relids left_relids;
+ Relids right_relids;
if (IsA(clause, RestrictInfo))
{
RestrictInfo *rinfo = (RestrictInfo *) clause;
- /* Pseudoconstants are not really interesting here. */
- if (rinfo->pseudoconstant)
+ if (! IsA(clause, RestrictInfo))
+ {
+ elog(WARNING, "expected RestrictInfo, got type %d", clause->type);
return false;
+ }
- /* no support for OR clauses at this point */
- if (rinfo->orclause)
+ /* Pseudoconstants are not really interesting here. */
+ if (rinfo->pseudoconstant)
return false;
/* get the actual clause from the RestrictInfo (it's not an OR clause) */
clause = (Node*)rinfo->clause;
- /* only simple opclauses are compatible with multivariate stats */
- if (! is_opclause(clause))
- return false;
-
/* we don't support join conditions at this moment */
if (treat_as_join_clause(clause, rinfo, varRelid, sjinfo))
return false;
+ clause_relids = rinfo->clause_relids;
+ left_relids = rinfo->left_relids;
+ right_relids = rinfo->right_relids;
+ }
+ else if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
+ {
+ left_relids = pull_varnos(get_leftop((Expr*)clause));
+ right_relids = pull_varnos(get_rightop((Expr*)clause));
+
+ clause_relids = bms_union(left_relids,
+ right_relids);
+ }
+ else
+ {
+ /* Not a binary opclause, so mark left/right relid sets as empty */
+ left_relids = NULL;
+ right_relids = NULL;
+ /* and get the total relid set the hard way */
+ clause_relids = pull_varnos((Node *) clause);
+ }
+
+ /*
+ * Only simple opclauses and IS NULL tests are compatible with
+ * multivariate stats at this point.
+ */
+ if ((is_opclause(clause))
+ && (list_length(((OpExpr *) clause)->args) == 2))
+ {
+ OpExpr *expr = (OpExpr *) clause;
+ bool varonleft = true;
+ bool ok;
+
/* is it 'variable op constant' ? */
- if (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)));
+ ok = (bms_membership(clause_relids) == BMS_SINGLETON) &&
+ (is_pseudo_constant_clause_relids(lsecond(expr->args),
+ right_relids) ||
+ (varonleft = false,
+ is_pseudo_constant_clause_relids(linitial(expr->args),
+ left_relids)));
- if (ok)
- {
- RangeTblEntry * rte;
- Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
+ if (ok)
+ {
+ RangeTblEntry * rte;
+ Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
- /*
- * Simple variables only - otherwise the planner_rt_fetch seems to fail
- * (return NULL).
- *
- * TODO Maybe use examine_variable() would fix that?
- */
- if (! (IsA(var, Var) && (varRelid == 0 || varRelid == var->varno)))
- return false;
+ /*
+ * Simple variables only - otherwise the planner_rt_fetch seems to fail
+ * (return NULL).
+ *
+ * TODO Maybe use examine_variable() would fix that?
+ */
+ if (! (IsA(var, Var) && (varRelid == 0 || varRelid == var->varno)))
+ return false;
- /*
- * Only consider this variable if (varRelid == 0) or when the varno
- * matches varRelid (see explanation at clause_selectivity).
- *
- * FIXME I suspect this may not be really necessary. The (varRelid == 0)
- * part seems to be enforced by treat_as_join_clause().
- */
- if (! ((varRelid == 0) || (varRelid == var->varno)))
- return false;
+ /*
+ * Only consider this variable if (varRelid == 0) or when the varno
+ * matches varRelid (see explanation at clause_selectivity).
+ *
+ * FIXME I suspect this may not be really necessary. The (varRelid == 0)
+ * part seems to be enforced by treat_as_join_clause().
+ */
+ 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;
+ /* Also skip special varno values, and system attributes ... */
+ if ((IS_SPECIAL_VARNO(var->varno)) || (! AttrNumberIsForUserDefinedAttr(var->varattno)))
+ return false;
- /* Lookup info about the base relation (we need to pass the OID out) */
+ /* Lookup info about the base relation (we need to pass the OID out) */
+ if (relid != NULL)
+ {
rte = planner_rt_fetch(var->varno, root);
*relid = rte->relid;
-
- /*
- * 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_EQSEL:
- *attnum = var->varattno;
- return true;
- }
}
+
+ /*
+ * 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:
+ /* not compatible with functional dependencies */
+ if (types & MV_CLAUSE_TYPE_MCV)
+ {
+ *attnums = bms_add_member(*attnums, var->varattno);
+ return (types & MV_CLAUSE_TYPE_MCV);
+ }
+ return false;
+
+ case F_EQSEL:
+ *attnums = bms_add_member(*attnums, var->varattno);
+ return true;
+ }
}
}
+ else if (IsA(clause, NullTest)
+ && IsA(((NullTest*)clause)->arg, Var))
+ {
+ RangeTblEntry * rte;
+ Var * var = (Var*)((NullTest*)clause)->arg;
- return false;
+ /*
+ * Simple variables only - otherwise the planner_rt_fetch seems to fail
+ * (return NULL).
+ *
+ * TODO Maybe use examine_variable() would fix that?
+ */
+ if (! (IsA(var, Var) && (varRelid == 0 || varRelid == var->varno)))
+ return false;
+ /*
+ * Only consider this variable if (varRelid == 0) or when the varno
+ * matches varRelid (see explanation at clause_selectivity).
+ *
+ * FIXME I suspect this may not be really necessary. The (varRelid == 0)
+ * part seems to be enforced by treat_as_join_clause().
+ */
+ 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;
+
+ /* Lookup info about the base relation (we need to pass the OID out) */
+ if (relid != NULL)
+ {
+ rte = planner_rt_fetch(var->varno, root);
+ *relid = rte->relid;
+ }
+
+ *attnums = bms_add_member(*attnums, var->varattno);
+
+ return true;
+ }
+ else if (or_clause(clause) || and_clause(clause))
+ {
+ /*
+ * AND/OR-clauses are supported if all sub-clauses are supported
+ *
+ * TODO We might support mixed case, where some of the clauses
+ * are supported and some are not, and treat all supported
+ * subclauses as a single clause, compute it's selectivity
+ * using mv stats, and compute the total selectivity using
+ * the current algorithm.
+ *
+ * TODO For RestrictInfo above an OR-clause, we might use the
+ * orclause with nested RestrictInfo - we won't have to
+ * call pull_varnos() for each clause, saving time.
+ */
+ Bitmapset *tmp = NULL;
+ ListCell *l;
+ foreach (l, ((BoolExpr*)clause)->args)
+ {
+ if (! clause_is_mv_compatible(root, (Node*)lfirst(l),
+ varRelid, relid, &tmp, sjinfo, types))
+ return false;
+ }
+
+ /* add the attnums from the OR-clause to the set of attnums */
+ *attnums = bms_join(*attnums, tmp);
+
+ return true;
+ }
+
+ return false;
}
/*
@@ -1115,6 +1660,13 @@ clause_is_mv_compatible(PlannerInfo *root, Node *clause, Oid varRelid,
*
* TODO Merge this docs to dependencies.c, as it's saying mostly the
* same things as the comments there.
+ *
+ * TODO Currently this is applied only to the top-level clauses, but
+ * maybe we could apply it to lists at subtrees too, e.g. to the
+ * two AND-clauses in
+ *
+ * (x=1 AND y=2) OR (z=3 AND q=10)
+ *
*/
static List *
clauselist_apply_dependencies(PlannerInfo *root, List *clauses, Oid varRelid,
@@ -1195,17 +1747,27 @@ clauselist_apply_dependencies(PlannerInfo *root, List *clauses, Oid varRelid,
*/
foreach (lc, clauses)
{
- AttrNumber attnum;
+ Bitmapset *attnums = NULL;
Node *clause = (Node *) lfirst(lc);
- if (! clause_is_mv_compatible(root, clause, varRelid, &relid, &attnum, sjinfo))
+ if (! clause_is_mv_compatible(root, clause, varRelid, &relid, &attnums,
+ sjinfo, MV_CLAUSE_TYPE_FDEP))
+ reduced_clauses = lappend(reduced_clauses, clause);
+ else if (bms_num_members(attnums) > 1)
+ /* FIXME This may happen thanks to OR-clauses, which should
+ * really be handled differently for functional
+ * dependencies.
+ */
reduced_clauses = lappend(reduced_clauses, clause);
else
{
+ /* functional dependencies support only [Var = Const] */
+ Assert(bms_num_members(attnums) == 1);
mvclauses[nmvclauses] = clause;
- mvattnums[nmvclauses] = attnum;
+ mvattnums[nmvclauses] = bms_singleton_member(attnums);
nmvclauses++;
- clause_attnums = bms_add_member(clause_attnums, attnum);
+ clause_attnums = bms_add_member(clause_attnums,
+ bms_singleton_member(attnums));
}
}
@@ -1430,3 +1992,446 @@ clauselist_apply_dependencies(PlannerInfo *root, List *clauses, Oid varRelid,
return reduced_clauses;
}
+
+/*
+ * 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,
+ * we can skip processing the histogram, as there can be no rows in
+ * it with the same values - all the rows matching the condition are
+ * represented by the MCV item. This can only happen with equality
+ * on all the attributes.
+ *
+ * The algorithm works like this:
+ *
+ * 1) mark all items as 'match'
+ * 2) walk through all the clauses
+ * 3) for a particular clause, walk through all the items
+ * 4) skip items that are already 'no match'
+ * 5) check clause for items that still match
+ * 6) sum frequencies for items to get selectivity
+ *
+ * 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 (all items not present in the MCV list are less frequent).
+ * This however seems useful only for cases with conditions on all
+ * attributes.
+ *
+ * TODO This only handles AND-ed clauses, but it might work for OR-ed
+ * lists too - it just needs to reverse the logic a bit. I.e. start
+ * with 'no match' for all items, and mark the items as a match
+ * as the clauses are processed (and skip items that are 'match').
+ */
+static Selectivity
+clauselist_mv_selectivity_mcvlist(PlannerInfo *root, List *clauses,
+ MVStats mvstats, bool *fullmatch,
+ Selectivity *lowsel)
+{
+ int i;
+ Selectivity s = 0.0;
+ MCVList mcvlist = NULL;
+ int nmatches = 0;
+
+ /* match/mismatch bitmap for each MCV item */
+ char * matches = NULL;
+
+ Assert(clauses != NIL);
+ Assert(list_length(clauses) >= 2);
+
+ /* there's no MCV list built yet */
+ if (! mvstats->mcv_built)
+ return 0.0;
+
+ mcvlist = deserialize_mv_mcvlist(fetch_mv_mcvlist(mvstats->mvoid));
+
+ Assert(mcvlist != NULL);
+ Assert(mcvlist->nitems > 0);
+
+ /* by default all the MCV items match the clauses fully */
+ matches = palloc0(sizeof(char) * mcvlist->nitems);
+ memset(matches, MVSTATS_MATCH_FULL, sizeof(char)*mcvlist->nitems);
+
+ /* number of matching MCV items */
+ nmatches = mcvlist->nitems;
+
+ nmatches = update_match_bitmap_mcvlist(root, clauses,
+ mvstats->stakeys, mcvlist,
+ nmatches, matches,
+ lowsel, fullmatch, false);
+
+ /* sum frequencies for all the matching MCV items */
+ for (i = 0; i < mcvlist->nitems; i++)
+ {
+ if (matches[i] != MVSTATS_MATCH_NONE)
+ s += mcvlist->items[i]->frequency;
+ }
+
+ pfree(matches);
+ pfree(mcvlist);
+
+ return s;
+}
+
+/*
+ * Evaluate clauses using the MCV list, and update the match bitmap.
+ *
+ * The bitmap may be already partially set, so this is really a way to
+ * combine results of several clause lists - either when computing
+ * conditional probability P(A|B) or a combination of AND/OR clauses.
+ *
+ * TODO This works with 'bitmap' where each bit is represented as a char,
+ * which is slightly wasteful. Instead, we could use a regular
+ * bitmap, reducing the size to ~1/8. Another thing is merging the
+ * bitmaps using & and |, which might be faster than min/max.
+ */
+static int
+update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
+ int2vector *stakeys, MCVList mcvlist,
+ int nmatches, char * matches,
+ Selectivity *lowsel, bool *fullmatch,
+ bool is_or)
+{
+ int i;
+ ListCell * l;
+
+ Bitmapset *eqmatches = NULL; /* attributes with equality matches */
+
+ /* The bitmap may be partially built. */
+ Assert(nmatches >= 0);
+ Assert(nmatches <= mcvlist->nitems);
+ Assert(clauses != NIL);
+ Assert(list_length(clauses) >= 1);
+ Assert(mcvlist != NULL);
+ Assert(mcvlist->nitems > 0);
+
+ /* No possible matches (only works for AND-ded clauses) */
+ if (((nmatches == 0) && (! is_or)) ||
+ ((nmatches == mcvlist->nitems) && is_or))
+ return nmatches;
+
+ /* frequency of the lowest MCV item */
+ *lowsel = 1.0;
+
+ /*
+ * Loop through the list of clauses, and for each of them evaluate
+ * all the MCV items not yet eliminated by the preceding clauses.
+ *
+ * FIXME This would probably deserve a refactoring, I guess. Unify
+ * the two loops and put the checks inside, or something like
+ * that.
+ */
+ foreach (l, clauses)
+ {
+ Node * clause = (Node*)lfirst(l);
+
+ /* if it's a RestrictInfo, then extract the clause */
+ if (IsA(clause, RestrictInfo))
+ clause = (Node*)((RestrictInfo*)clause)->clause;
+
+ /* if there are no remaining matches possible, we can stop */
+ if (((nmatches == 0) && (! is_or)) ||
+ ((nmatches == mcvlist->nitems) && is_or))
+ break;
+
+ /* it's either OpClause, or NullTest */
+ if (is_opclause(clause))
+ {
+ 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, stakeys);
+
+ fmgr_info(get_opcode(typecache->lt_opr), <proc);
+ fmgr_info(get_opcode(typecache->gt_opr), >proc);
+
+ /*
+ * Walk through the MCV items and evaluate the current clause. We can
+ * skip items that were already ruled out, and terminate if there are
+ * no remaining MCV items that might possibly match.
+ */
+ for (i = 0; i < mcvlist->nitems; i++)
+ {
+ bool mismatch = false;
+ MCVItem item = mcvlist->items[i];
+
+ /*
+ * find the lowest selectivity in the MCV
+ * FIXME Maybe not the best place do do this (in for all clauses).
+ */
+ if (item->frequency < *lowsel)
+ *lowsel = item->frequency;
+
+ /*
+ * If there are no more matches (AND) or no remaining unmatched
+ * items (OR), we can stop processing this clause.
+ */
+ if (((nmatches == 0) && (! is_or)) ||
+ ((nmatches == mcvlist->nitems) && is_or))
+ break;
+
+ /*
+ * For AND-lists, we can also mark NULL items as 'no match' (and
+ * then skip them). For OR-lists this is not possible.
+ */
+ if ((! is_or) && item->isnull[idx])
+ matches[i] = MVSTATS_MATCH_NONE;
+
+ /* skip MCV items that were already ruled out */
+ if ((! is_or) && (matches[i] == MVSTATS_MATCH_NONE))
+ continue;
+ else if (is_or && (matches[i] == MVSTATS_MATCH_FULL))
+ 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).
+ */
+ bool match = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ cst->constvalue,
+ item->values[idx]));
+
+ if (match)
+ eqmatches = bms_add_member(eqmatches, idx);
+
+ mismatch = (! match);
+ }
+ 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).
+ */
+ mismatch = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ cst->constvalue,
+ item->values[idx]));
+
+ } /* (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).
+ */
+ mismatch = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ item->values[idx],
+ cst->constvalue));
+ }
+ }
+ 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).
+ */
+ mismatch = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ cst->constvalue,
+ item->values[idx]));
+ }
+ 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).
+ */
+ mismatch = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ item->values[idx],
+ cst->constvalue));
+ }
+
+ } /* (get_oprrest(expr->opno) == F_SCALARGTSEL) */
+
+ /* XXX The conditions on matches[i] are not needed, as we
+ * skip MCV items that can't become true/false, depending
+ * on the current flag. See beginning of the loop over
+ * MCV items.
+ */
+
+ if ((is_or) && (matches[i] == MVSTATS_MATCH_NONE) && (! mismatch))
+ {
+ /* OR - was MATCH_NONE, but will be MATCH_FULL */
+ matches[i] = MVSTATS_MATCH_FULL;
+ ++nmatches;
+ continue;
+ }
+ else if ((! is_or) && (matches[i] == MVSTATS_MATCH_FULL) && mismatch)
+ {
+ /* AND - was MATC_FULL, but will be MATCH_NONE */
+ matches[i] = MVSTATS_MATCH_NONE;
+ --nmatches;
+ continue;
+ }
+
+ }
+ }
+ }
+ else if (IsA(clause, NullTest))
+ {
+ NullTest * expr = (NullTest*)clause;
+ Var * var = (Var*)(expr->arg);
+
+ /* FIXME proper matching attribute to dimension */
+ int idx = mv_get_index(var->varattno, stakeys);
+
+ /*
+ * Walk through the MCV items and evaluate the current clause. We can
+ * skip items that were already ruled out, and terminate if there are
+ * no remaining MCV items that might possibly match.
+ */
+ for (i = 0; i < mcvlist->nitems; i++)
+ {
+ MCVItem item = mcvlist->items[i];
+
+ /*
+ * find the lowest selectivity in the MCV
+ * FIXME Maybe not the best place do do this (in for all clauses).
+ */
+ if (item->frequency < *lowsel)
+ *lowsel = item->frequency;
+
+ /* if there are no more matches, we can stop processing this clause */
+ if (nmatches == 0)
+ break;
+
+ /* skip MCV items that were already ruled out */
+ if (matches[i] == MVSTATS_MATCH_NONE)
+ continue;
+
+ /* if the clause mismatches the MCV item, set it as MATCH_NONE */
+ if (((expr->nulltesttype == IS_NULL) && (! mcvlist->items[i]->isnull[idx])) ||
+ ((expr->nulltesttype == IS_NOT_NULL) && (mcvlist->items[i]->isnull[idx])))
+ {
+ matches[i] = MVSTATS_MATCH_NONE;
+ --nmatches;
+ }
+ }
+ }
+ else if (or_clause(clause) || and_clause(clause))
+ {
+ /* AND/OR clause, with all clauses compatible with the selected MV stat */
+
+ int i;
+ BoolExpr *orclause = ((BoolExpr*)clause);
+ List *orclauses = orclause->args;
+
+ /* match/mismatch bitmap for each MCV item */
+ int or_nmatches = 0;
+ char * or_matches = NULL;
+
+ Assert(orclauses != NIL);
+ Assert(list_length(orclauses) >= 2);
+
+ /* number of matching MCV items */
+ or_nmatches = mcvlist->nitems;
+
+ /* by default none of the MCV items matches the clauses */
+ or_matches = palloc0(sizeof(char) * or_nmatches);
+
+ if (or_clause(clause))
+ {
+ /* OR clauses assume nothing matches, initially */
+ memset(or_matches, MVSTATS_MATCH_NONE, sizeof(char)*or_nmatches);
+ or_nmatches = 0;
+ }
+ else
+ {
+ /* AND clauses assume nothing matches, initially */
+ memset(or_matches, MVSTATS_MATCH_FULL, sizeof(char)*or_nmatches);
+ }
+
+ /* build the match bitmap for the OR-clauses */
+ or_nmatches = update_match_bitmap_mcvlist(root, orclauses,
+ stakeys, mcvlist,
+ or_nmatches, or_matches,
+ lowsel, fullmatch, or_clause(clause));
+
+ /* merge the bitmap into the existing one*/
+ for (i = 0; i < mcvlist->nitems; i++)
+ {
+ /*
+ * To AND-merge the bitmaps, a MIN() semantics is used.
+ * For OR-merge, use MAX().
+ *
+ * FIXME this does not decrease the number of matches
+ */
+ UPDATE_RESULT(matches[i], or_matches[i], is_or);
+ }
+
+ pfree(or_matches);
+
+ }
+ else
+ {
+ elog(ERROR, "unknown clause type: %d", clause->type);
+ }
+ }
+
+ /*
+ * If all the columns were matched by equality, it's a full match.
+ * In this case there can be just a single MCV item, matching the
+ * clause (if there were two, both would match the other one).
+ */
+ *fullmatch = (bms_num_members(eqmatches) == mcvlist->ndimensions);
+
+ /* free the allocated pieces */
+ if (eqmatches)
+ pfree(eqmatches);
+
+ return nmatches;
+}
diff --git a/src/backend/utils/mvstats/Makefile b/src/backend/utils/mvstats/Makefile
index 099f1ed..3c0aff4 100644
--- a/src/backend/utils/mvstats/Makefile
+++ b/src/backend/utils/mvstats/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/utils/mvstats
top_builddir = ../../../..
include $(top_builddir)/src/Makefile.global
-OBJS = common.o dependencies.o
+OBJS = common.o mcv.o dependencies.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/utils/mvstats/common.c b/src/backend/utils/mvstats/common.c
index d44b95a..bd952c6 100644
--- a/src/backend/utils/mvstats/common.c
+++ b/src/backend/utils/mvstats/common.c
@@ -17,8 +17,8 @@
#include "common.h"
static VacAttrStats ** lookup_var_attr_stats(int2vector *attrs,
- int natts, VacAttrStats **vacattrstats);
-
+ int natts,
+ VacAttrStats **vacattrstats);
/*
* Compute requested multivariate stats, using the rows sampled for the
@@ -44,6 +44,8 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
for (i = 0; i < nmvstats; i++)
{
MVDependencies deps = NULL;
+ MCVList mcvlist = NULL;
+ int numrows_filtered = 0;
/* int2 vector of attnums the stats should be computed on */
int2vector * attrs = mvstats[i].stakeys;
@@ -60,8 +62,12 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
if (mvstats->deps_enabled)
deps = build_mv_dependencies(numrows, rows, attrs, stats);
+ /* build the MCV list */
+ if (mvstats->mcv_enabled)
+ mcvlist = build_mv_mcvlist(numrows, rows, attrs, stats, &numrows_filtered);
+
/* store the histogram / MCV list in the catalog */
- update_mv_stats(mvstats[i].mvoid, deps);
+ update_mv_stats(mvstats[i].mvoid, deps, mcvlist, attrs, stats);
}
}
@@ -143,7 +149,7 @@ list_mv_stats(Oid relid, int *nstats, bool built_only)
* Skip statistics that were not computed yet (if only stats
* that were already built were requested)
*/
- if (built_only && (! stats->deps_built))
+ if (built_only && (! (stats->mcv_built || stats->deps_built)))
continue;
/* double the array size if needed */
@@ -156,7 +162,9 @@ list_mv_stats(Oid relid, int *nstats, bool built_only)
result[*nstats].mvoid = HeapTupleGetOid(htup);
result[*nstats].stakeys = buildint2vector(stats->stakeys.values, stats->stakeys.dim1);
result[*nstats].deps_enabled = stats->deps_enabled;
+ result[*nstats].mcv_enabled = stats->mcv_enabled;
result[*nstats].deps_built = stats->deps_built;
+ result[*nstats].mcv_built = stats->mcv_built;
*nstats += 1;
}
@@ -171,7 +179,9 @@ list_mv_stats(Oid relid, int *nstats, bool built_only)
}
void
-update_mv_stats(Oid mvoid, MVDependencies dependencies)
+update_mv_stats(Oid mvoid,
+ MVDependencies dependencies, MCVList mcvlist,
+ int2vector *attrs, VacAttrStats **stats)
{
HeapTuple stup,
oldtup;
@@ -196,15 +206,26 @@ update_mv_stats(Oid mvoid, MVDependencies dependencies)
= PointerGetDatum(serialize_mv_dependencies(dependencies));
}
+ if (mcvlist != NULL)
+ {
+ bytea * data = serialize_mv_mcvlist(mcvlist, attrs, stats);
+ nulls[Anum_pg_mv_statistic_stamcv -1] = (data == NULL);
+ values[Anum_pg_mv_statistic_stamcv - 1] = PointerGetDatum(data);
+ }
+
/* always replace the value (either by bytea or NULL) */
replaces[Anum_pg_mv_statistic_stadeps -1] = true;
+ replaces[Anum_pg_mv_statistic_stamcv -1] = true;
/* always change the availability flags */
nulls[Anum_pg_mv_statistic_deps_built -1] = false;
+ nulls[Anum_pg_mv_statistic_mcv_built -1] = false;
replaces[Anum_pg_mv_statistic_deps_built-1] = true;
+ replaces[Anum_pg_mv_statistic_mcv_built -1] = true;
values[Anum_pg_mv_statistic_deps_built-1] = BoolGetDatum(dependencies != 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,
@@ -232,6 +253,21 @@ update_mv_stats(Oid mvoid, MVDependencies dependencies)
heap_close(sd, RowExclusiveLock);
}
+
+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;
+}
+
/* multi-variate stats comparator */
/*
@@ -242,11 +278,15 @@ update_mv_stats(Oid mvoid, MVDependencies dependencies)
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 compare_datums_simple(*(Datum*)a,
+ *(Datum*)b,
+ (SortSupport)arg);
+}
- return ApplySortComparator(da, false, db, false, ssup);
+int
+compare_datums_simple(Datum a, Datum b, SortSupport ssup)
+{
+ return ApplySortComparator(a, false, b, false, ssup);
}
/*
diff --git a/src/backend/utils/mvstats/common.h b/src/backend/utils/mvstats/common.h
index 6d5465b..f4309f7 100644
--- a/src/backend/utils/mvstats/common.h
+++ b/src/backend/utils/mvstats/common.h
@@ -46,7 +46,15 @@ typedef struct
Datum value; /* a data value */
int tupno; /* position index for tuple it came from */
} ScalarItem;
-
+
+/* (de)serialization info */
+typedef struct DimensionInfo {
+ int nvalues; /* number of deduplicated values */
+ int nbytes; /* number of bytes (serialized) */
+ int typlen; /* pg_type.typlen */
+ bool typbyval; /* pg_type.typbyval */
+} DimensionInfo;
+
/* multi-sort */
typedef struct MultiSortSupportData {
int ndims; /* number of dimensions supported by the */
@@ -71,5 +79,6 @@ int multi_sort_compare_dim(int dim, const SortItem *a,
const SortItem *b, MultiSortSupport mss);
/* comparators, used when constructing multivariate stats */
+int compare_datums_simple(Datum a, Datum b, SortSupport ssup);
int compare_scalars_simple(const void *a, const void *b, void *arg);
int compare_scalars_partition(const void *a, const void *b, void *arg);
diff --git a/src/backend/utils/mvstats/mcv.c b/src/backend/utils/mvstats/mcv.c
new file mode 100644
index 0000000..4466cee
--- /dev/null
+++ b/src/backend/utils/mvstats/mcv.c
@@ -0,0 +1,1002 @@
+/*-------------------------------------------------------------------------
+ *
+ * mcv.c
+ * POSTGRES multivariate MCV lists
+ *
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/utils/mvstats/mcv.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "common.h"
+
+/*
+ * Multivariate MCVs (most-common values lists) are a straightforward
+ * extension of regular MCV list by tracking combinations of values for
+ * several attributes (columns), including NULL flags, and frequency
+ * of the combination.
+ *
+ * For columns small number of distinct values, this works quite well
+ * and may represent the distribution pretty exactly. For columns with
+ * large number of distinct values (e.g. stored as FLOAT), this does
+ * not work that well.
+ *
+ * If we can represent the distribution as a MCV list, we can estimate
+ * some clauses (e.g. equality clauses) much accurately than using
+ * histograms for example.
+ *
+ * Discrete distributions are also easier to combine into a larger
+ * distribution (but this is not yet implemented).
+ *
+ *
+ * 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?
+ *
+ *
+ * Selectivity estimation
+ * ----------------------
+ * The estimation, implemented in clauselist_mv_selectivity_mcvlist(),
+ * is quite simple in principle - walk through the MCV items and sum
+ * frequencies of all the items that match all the clauses.
+ *
+ * The current implementation uses MCV lists to estimates those types
+ * of clauses (think of WHERE conditions):
+ *
+ * (a) equality clauses WHERE (a = 1) AND (b = 2)
+ *
+ * (b) inequality clauses WHERE (a < 1) AND (b >= 2)
+ *
+ * It's possible to add more clauses, for example:
+ *
+ * (a) NULL clauses WHERE (a IS NULL) AND (b IS NOT NULL)
+ *
+ * (b) multi-var clauses WHERE (a > b)
+ *
+ * and so on. These are tasks for the future, not yet implemented.
+ *
+ *
+ * Estimating equality clauses
+ * ---------------------------
+ * When computing selectivity estimate for equality clauses
+ *
+ * (a = 1) AND (b = 2)
+ *
+ * we can do this estimate pretty exactly assuming that two conditions
+ * are met:
+ *
+ * (1) there's an equality condition on each attribute
+ *
+ * (2) we find a matching item in the MCV list
+ *
+ * In that case we know the MCV item represents all the tuples matching
+ * the clauses, and the selectivity estimate is complete. This is what
+ * we call 'full match'.
+ *
+ * When only (1) holds, but there's no matching MCV item, we don't know
+ * whether there are no such rows or just are not very frequent. We can
+ * however use the frequency of the least frequent MCV item as an upper
+ * bound for the selectivity.
+ *
+ * If the equality conditions match only a subset of the attributes
+ * the MCV list is built on (i.e. we can't get a full match - we may get
+ * multiple MCV items matching the clauses, but even if we get a single
+ * match there may be items that did not get into the MCV list. But in
+ * this case we can still use the frequency of the last MCV item to clam
+ * the 'additional' selectivity not accounted for by the matching items.
+ *
+ * If there's no histogram, because the MCV list approximates the
+ * distribution accurately (not because the histogram was disabled),
+ * it does not really matter whether there are equality conditions on
+ * all the columns - we can do pretty accurate estimation using the MCV.
+ *
+ * TODO For a combination of equality conditions (not full-match case)
+ * we probably can clamp the selectivity by the 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 we know the estimate of number of combinations of the columns
+ * (i.e. ndistinct(A,B)), we may estimate the average frequency of
+ * items in the remaining 10% as [10% / ndistinct(A,B)].
+ *
+ *
+ * Bounding estimates
+ * ------------------
+ * In general the MCV lists may not provide estimates as accurate as
+ * for the full-match equality case, but may provide some useful
+ * lower/upper boundaries for the estimation error.
+ *
+ * With equality clauses we can do a few more tricks to narrow this
+ * error range (see the previous section and TODO), but with inequality
+ * clauses (or generally non-equality clauses), it's rather dificult.
+ * There's nothing like a 'full match' - we have to consider both the
+ * MCV items and the remaining part every time. We can't use the minimum
+ * selectivity of MCV items, as the clauses may match multiple items.
+ *
+ * For example with a MCV list on columns (A, B), covering 90% of the
+ * table (computed while building the MCV list), about ~10% of the table
+ * is not represented by the MCV list. So even if the conditions match
+ * all the remaining rows (not represented by the MCV items), we can't
+ * get selectivity higher than those 10%. We may use 1/2 the remaining
+ * selectivity as an estimate (minimizing average error).
+ *
+ * TODO Most of these ideas (error limiting) are not yet implemented.
+ *
+ *
+ * General TODO
+ * ------------
+ *
+ * FIXME Use max_mcv_items from ALTER TABLE ADD STATISTICS command.
+ *
+ * TODO Add support for IS [NOT] NULL clauses, and clauses referencing
+ * multiple columns (a < b).
+ *
+ * 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,
+ * which are very impractical for plain MCV list because of size.
+ * But for those data types we really want just the equality
+ * clauses, so it's actually a good solution.
+ *
+ * TODO Currently there's no logic to consider building only a MCV list
+ * (and not building the histogram at all), except for doing this
+ * decision manually in ADD STATISTICS.
+ */
+
+/*
+ * Each serialized item needs to store (in this order):
+ *
+ * - indexes (ndim * sizeof(int32))
+ * - null flags (ndim * sizeof(bool))
+ * - frequency (sizeof(double))
+ *
+ * So in total:
+ *
+ * ndim * (sizeof(int32) + sizeof(bool)) + sizeof(double)
+ */
+#define ITEM_SIZE(ndims) \
+ (ndims * (sizeof(int32) + sizeof(bool)) + sizeof(double))
+
+/* pointers into a flat serialized item of ITEM_SIZE(n) bytes */
+#define ITEM_INDEXES(item) ((int32*)item)
+#define ITEM_NULLS(item,ndims) ((bool*)(ITEM_INDEXES(item) + ndims))
+#define ITEM_FREQUENCY(item,ndims) ((double*)(ITEM_NULLS(item,ndims) + ndims))
+
+/*
+ * Builds MCV list from sample rows, and removes rows represented by
+ * the MCV list from the sample (the number of remaining sample rows is
+ * returned by the numrows_filtered parameter).
+ *
+ * The method is quite simple - in short it does about these steps:
+ *
+ * (1) sort the data (default collation, '<' for the data type)
+ *
+ * (2) count distinct groups, decide how many to keep
+ *
+ * (3) build the MCV list using the threshold determined in (2)
+ *
+ * (4) remove rows represented by the MCV from the sample
+ *
+ * For more details, see the comments in the code.
+ *
+ * FIXME Single-dimensional MCV is sorted by frequency (descending). We
+ * should do that too, because when walking through the list we
+ * want to check the most frequent items first.
+ *
+ * TODO We're using Datum (8B), even for data types (e.g. int4 or
+ * float4). Maybe we could save some space here, but the bytea
+ * compression should handle it just fine.
+ *
+ * TODO This probably should not use the ndistinct directly (as computed
+ * from the table, but rather estimate the number of distinct
+ * values in the table), no?
+ */
+MCVList
+build_mv_mcvlist(int numrows, HeapTuple *rows, int2vector *attrs,
+ VacAttrStats **stats, int *numrows_filtered)
+{
+ int i, j;
+ int numattrs = attrs->dim1;
+ int ndistinct = 0;
+ int mcv_threshold = 0;
+ int count = 0;
+ int nitems = 0;
+
+ MCVList mcvlist = NULL;
+
+ /* Sort by multiple columns (using array of SortSupport) */
+ MultiSortSupport mss = multi_sort_init(numattrs);
+
+ /*
+ * Preallocate space for all the items as a single chunk, and point
+ * the items to the appropriate parts of the array.
+ */
+ SortItem *items = (SortItem*)palloc0(numrows * sizeof(SortItem));
+ Datum *values = (Datum*)palloc0(sizeof(Datum) * numrows * numattrs);
+ bool *isnull = (bool*)palloc0(sizeof(bool) * numrows * numattrs);
+
+ /* keep all the rows by default (as if there was no MCV list) */
+ *numrows_filtered = numrows;
+
+ for (i = 0; i < numrows; i++)
+ {
+ items[i].values = &values[i * numattrs];
+ items[i].isnull = &isnull[i * numattrs];
+ }
+
+ /* load the values/null flags from sample rows */
+ for (j = 0; j < numrows; j++)
+ for (i = 0; i < numattrs; i++)
+ items[j].values[i] = heap_getattr(rows[j], attrs->values[i],
+ stats[i]->tupDesc, &items[j].isnull[i]);
+
+ /* prepare the sort functions for all the attributes */
+ for (i = 0; i < numattrs; i++)
+ multi_sort_add_dimension(mss, i, i, stats);
+
+ /* do the sort, using the multi-sort */
+ qsort_arg((void *) items, numrows, sizeof(SortItem),
+ multi_sort_compare, mss);
+
+ /*
+ * Count the number of distinct groups - just walk through the
+ * sorted list and count the number of key changes. We use this to
+ * determine the threshold (125% of the average frequency).
+ */
+ ndistinct = 1;
+ for (i = 1; i < numrows; i++)
+ if (multi_sort_compare(&items[i], &items[i-1], mss) != 0)
+ ndistinct += 1;
+
+ /*
+ * Determine how many groups actually exceed the threshold, and then
+ * walk the array again and collect them into an array. We'll always
+ * require at least 4 rows per group.
+ *
+ * But if we can fit all the distinct values in the MCV list (i.e.
+ * if there are less distinct groups than MVSTAT_MCVLIST_MAX_ITEMS),
+ * we'll require only 2 rows per group.
+ *
+ * TODO For now the threshold is the same as in the single-column
+ * case (average + 25%), but maybe that's worth revisiting
+ * for the multivariate case.
+ *
+ * TODO We can do this only if we believe we got all the distinct
+ * values of the table.
+ *
+ * FIXME This should really reference mcv_max_items (from catalog)
+ * instead of the constant MVSTAT_MCVLIST_MAX_ITEMS.
+ */
+ mcv_threshold = 1.25 * numrows / ndistinct;
+ mcv_threshold = (mcv_threshold < 4) ? 4 : mcv_threshold;
+
+ if (ndistinct <= MVSTAT_MCVLIST_MAX_ITEMS)
+ mcv_threshold = 2;
+
+ /*
+ * Walk through the sorted data again, and see how many groups
+ * reach the mcv_threshold (and become an item in the MCV list).
+ */
+ count = 1;
+ for (i = 1; i <= numrows; i++)
+ {
+ /* last row or new group, so check if we exceed mcv_threshold */
+ if ((i == numrows) || (multi_sort_compare(&items[i], &items[i-1], mss) != 0))
+ {
+ /* group hits the threshold, count the group as MCV item */
+ if (count >= mcv_threshold)
+ nitems += 1;
+
+ count = 1;
+ }
+ else /* within group, so increase the number of items */
+ count += 1;
+ }
+
+ /* we know the number of MCV list items, so let's build the list */
+ if (nitems > 0)
+ {
+ /* allocate the MCV list structure, set parameters we know */
+ mcvlist = (MCVList)palloc0(sizeof(MCVListData));
+
+ mcvlist->magic = MVSTAT_MCV_MAGIC;
+ mcvlist->type = MVSTAT_MCV_TYPE_BASIC;
+ mcvlist->ndimensions = numattrs;
+ mcvlist->nitems = nitems;
+
+ /*
+ * Preallocate Datum/isnull arrays (not as a single chunk, as
+ * we'll pass this outside this method and thus it needs to be
+ * easy to pfree() the data (and we wouldn't know where the
+ * arrays start).
+ *
+ * TODO Maybe the reasoning that we can't allocate a single
+ * piece because we're passing it out is bogus? Who'd
+ * free a single item of the MCV list, anyway?
+ *
+ * TODO Maybe with a proper encoding (stuffing all the values
+ * into a list-level array, this will be untrue)?
+ */
+ mcvlist->items = (MCVItem*)palloc0(sizeof(MCVItem)*nitems);
+
+ for (i = 0; i < nitems; i++)
+ {
+ mcvlist->items[i] = (MCVItem)palloc0(sizeof(MCVItemData));
+ mcvlist->items[i]->values = (Datum*)palloc0(sizeof(Datum)*numattrs);
+ mcvlist->items[i]->isnull = (bool*)palloc0(sizeof(bool)*numattrs);
+ }
+
+ /*
+ * Repeat the same loop as above, but this time copy the data
+ * into the MCV list (for items exceeding the threshold).
+ *
+ * TODO Maybe we could simply remember indexes of the last item
+ * in each group (from the previous loop)?
+ */
+ count = 1;
+ nitems = 0;
+ for (i = 1; i <= numrows; i++)
+ {
+ /* last row or a new group */
+ if ((i == numrows) || (multi_sort_compare(&items[i], &items[i-1], mss) != 0))
+ {
+ /* count the MCV item if exceeding the threshold (and copy into the array) */
+ if (count >= mcv_threshold)
+ {
+ /* just pointer to the proper place in the list */
+ MCVItem item = mcvlist->items[nitems];
+
+ /* copy values from the _previous_ group (last item of) */
+ memcpy(item->values, items[(i-1)].values, sizeof(Datum) * numattrs);
+ memcpy(item->isnull, items[(i-1)].isnull, sizeof(bool) * numattrs);
+
+
+ /* and finally the group frequency */
+ item->frequency = (double)count / numrows;
+
+ /* next 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 list (i.e. keep only rows
+ * that are not represented by the MCV list).
+ *
+ * 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.
+ *
+ * A better option would be keeping the ID of the row in
+ * the sort item, and then just walk through the items and
+ * mark rows to remove (in a bitmap of the same size).
+ * There's not space for that in SortItem at this moment,
+ * but it's trivial to add 'private' pointer, or just
+ * using another structure with extra field (starting with
+ * SortItem, so that the comparators etc. still work).
+ *
+ * Another option is to use the sorted array of items
+ * (because that's how we sorted the source data), and
+ * simply do a bsearch() into it. If we find a matching
+ * item, the row belongs to the MCV list.
+ */
+ 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);
+
+ /* used for the searches */
+ SortItem item, mcvitem;;
+
+ item.values = (Datum*)palloc0(numattrs * sizeof(Datum));
+ item.isnull = (bool*)palloc0(numattrs * sizeof(bool));
+
+ /*
+ * FIXME we don't need to allocate this, we can reference
+ * the MCV item directly ...
+ */
+ mcvitem.values = (Datum*)palloc0(numattrs * sizeof(Datum));
+ mcvitem.isnull = (bool*)palloc0(numattrs * sizeof(bool));
+
+ /* walk through the tuples, compare the values to MCV items */
+ for (i = 0; i < numrows; i++)
+ {
+ bool match = false;
+
+ /* collect the key values from the row */
+ for (j = 0; j < numattrs; j++)
+ item.values[j] = heap_getattr(rows[i], attrs->values[j],
+ stats[j]->tupDesc, &item.isnull[j]);
+
+ /* scan through the MCV list for matches */
+ for (j = 0; j < mcvlist->nitems; j++)
+ {
+ /*
+ * TODO Create a SortItem/MCVItem comparator so that
+ * we don't need to do memcpy() like crazy.
+ */
+ memcpy(mcvitem.values, mcvlist->items[j]->values,
+ numattrs * sizeof(Datum));
+ memcpy(mcvitem.isnull, mcvlist->items[j]->isnull,
+ numattrs * sizeof(bool));
+
+ if (multi_sort_compare(&item, &mcvitem, mss) == 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));
+ }
+
+ /* replace the rows and remember how many rows we kept */
+ memcpy(rows, rows_filtered, sizeof(HeapTuple) * nfiltered);
+ *numrows_filtered = nfiltered;
+
+ /* free all the data used here */
+ pfree(rows_filtered);
+ pfree(item.values);
+ pfree(item.isnull);
+ pfree(mcvitem.values);
+ pfree(mcvitem.isnull);
+ }
+ }
+
+ pfree(values);
+ pfree(items);
+ pfree(isnull);
+
+ return mcvlist;
+}
+
+
+/* fetch the MCV list (as a bytea) from the pg_mv_statistic catalog */
+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;
+}
+
+/* print some basic info about the MCV list
+ *
+ * TODO Add info about what part of the table this covers.
+ */
+Datum
+pg_mv_stats_mcvlist_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));
+}
+
+/* used to pass context into bsearch() */
+static SortSupport ssup_private = NULL;
+
+static int bsearch_comparator(const void * a, const void * b);
+
+/*
+ * Serialize MCV list into a bytea value. The basic algorithm is simple:
+ *
+ * (1) perform deduplication for each attribute (separately)
+ * (a) collect all (non-NULL) attribute values from all MCV items
+ * (b) sort the data (using 'lt' from VacAttrStats)
+ * (c) remove duplicate values from the array
+ *
+ * (2) serialize the arrays into a bytea value
+ *
+ * (3) process all MCV list items
+ * (a) replace values with indexes into the arrays
+ *
+ * Each attribute has to be processed separately, because we're mixing
+ * different datatypes, and we don't know what equality means for them.
+ * We're also mixing pass-by-value and pass-by-ref types, and so on.
+ *
+ * We'll use 32-bit values for the indexes in step (3), although we
+ * could probably use just 16 bits as we don't allow more than 8k
+ * items in the MCV list max_mcv_items (well, we might increase this to
+ * 32k and still fit into signed 16-bits). But let's be lazy and rely
+ * on the varlena compression to kick in. If most bytes will be 0x00
+ * so it should work nicely.
+ *
+ * FIXME This probably leaks memory, or at least uses it inefficiently
+ * (many small palloc() calls instead of a large one).
+ *
+ * TODO Consider using 16-bit values for the indexes in step (3).
+ *
+ * TODO Consider packing boolean flags (NULL) for each item into 'char'
+ * or a longer type (instead of using an array of bool items).
+ */
+bytea *
+serialize_mv_mcvlist(MCVList mcvlist, int2vector *attrs,
+ VacAttrStats **stats)
+{
+ int i, j;
+ int ndims = mcvlist->ndimensions;
+ int itemsize = ITEM_SIZE(ndims);
+
+ Size total_length = 0;
+
+ char *item = palloc0(itemsize);
+
+ /* serialized items (indexes into arrays, etc.) */
+ bytea *output;
+ char *data = NULL;
+
+ /* values per dimension (and number of non-NULL values) */
+ Datum **values = (Datum**)palloc0(sizeof(Datum*) * ndims);
+ int *counts = (int*)palloc0(sizeof(int) * ndims);
+
+ /* info about dimensions (for deserialize) */
+ DimensionInfo * info
+ = (DimensionInfo *)palloc0(sizeof(DimensionInfo)*ndims);
+
+ /* sort support data */
+ SortSupport ssup = (SortSupport)palloc0(sizeof(SortSupportData)*ndims);
+
+ /* collect and deduplicate values for each dimension */
+ for (i = 0; i < ndims; i++)
+ {
+ int count;
+ StdAnalyzeData *tmp = (StdAnalyzeData *)stats[i]->extra_data;
+
+ /* keep important info about the data type */
+ info[i].typlen = stats[i]->attrtype->typlen;
+ info[i].typbyval = stats[i]->attrtype->typbyval;
+
+ /* allocate space for all values, including NULLs (won't use them) */
+ values[i] = (Datum*)palloc0(sizeof(Datum) * mcvlist->nitems);
+
+ for (j = 0; j < mcvlist->nitems; j++)
+ {
+ if (! mcvlist->items[j]->isnull[i]) /* skip NULL values */
+ {
+ values[i][counts[i]] = mcvlist->items[j]->values[i];
+ counts[i] += 1;
+ }
+ }
+
+ /* there are just NULL values in this dimension */
+ if (counts[i] == 0)
+ continue;
+
+ /* sort and deduplicate */
+ ssup[i].ssup_cxt = CurrentMemoryContext;
+ ssup[i].ssup_collation = DEFAULT_COLLATION_OID;
+ ssup[i].ssup_nulls_first = false;
+
+ PrepareSortSupportFromOrderingOp(tmp->ltopr, &ssup[i]);
+
+ qsort_arg(values[i], counts[i], sizeof(Datum),
+ compare_scalars_simple, &ssup[i]);
+
+ /*
+ * Walk through the array and eliminate duplicitate values, but
+ * keep the ordering (so that we can do bsearch later). We know
+ * there's at least 1 item, so we can skip the first element.
+ */
+ count = 1; /* number of deduplicated items */
+ for (j = 1; j < counts[i]; j++)
+ {
+ /* if it's different from the previous value, we need to keep it */
+ if (compare_datums_simple(values[i][j-1], values[i][j], &ssup[i]) != 0)
+ {
+ /* XXX: not needed if (count == j) */
+ values[i][count] = values[i][j];
+ count += 1;
+ }
+ }
+
+ /* keep info about the deduplicated count */
+ info[i].nvalues = count;
+
+ /* compute size of the serialized data */
+ if (info[i].typbyval)
+ /*
+ * passed by value, so just Datum array (int4, int8, ...)
+ *
+ * TODO Might save a few bytes here, by storing just typlen
+ * bytes instead of whole Datum (8B) on 64-bits.
+ */
+ info[i].nbytes = info[i].nvalues * sizeof(Datum);
+ else if (info[i].typlen > 0)
+ /* pased by reference, but fixed length (name, tid, ...) */
+ info[i].nbytes = info[i].nvalues * info[i].typlen;
+ else if (info[i].typlen == -1)
+ /* varlena, so just use VARSIZE_ANY */
+ for (j = 0; j < info[i].nvalues; j++)
+ info[i].nbytes += VARSIZE_ANY(values[i][j]);
+ else if (info[i].typlen == -2)
+ /* cstring, so simply strlen */
+ for (j = 0; j < info[i].nvalues; j++)
+ info[i].nbytes += strlen(DatumGetPointer(values[i][j]));
+ else
+ elog(ERROR, "unknown data type typbyval=%d typlen=%d",
+ info[i].typbyval, info[i].typlen);
+ }
+
+ /*
+ * Now we finally know how much space we'll need for the serialized
+ * MCV list, as it contains these fields:
+ *
+ * - length (4B) for varlena
+ * - magic (4B)
+ * - type (4B)
+ * - ndimensions (4B)
+ * - nitems (4B)
+ * - info (ndim * sizeof(DimensionInfo)
+ * - arrays of values for each dimension
+ * - serialized items (nitems * itemsize)
+ *
+ * So the 'header' size is 20B + ndim * sizeof(DimensionInfo) and
+ * then we'll place the data.
+ */
+ total_length = (sizeof(int32) + offsetof(MCVListData, items)
+ + ndims * sizeof(DimensionInfo)
+ + mcvlist->nitems * itemsize);
+
+ for (i = 0; i < ndims; i++)
+ total_length += info[i].nbytes;
+
+ /* enforce arbitrary limit of 1MB */
+ if (total_length > 1024 * 1024)
+ elog(ERROR, "serialized MCV exceeds 1MB (%ld)", total_length);
+
+ /* allocate space for the serialized MCV list, set header fields */
+ output = (bytea*)palloc0(total_length);
+ SET_VARSIZE(output, total_length);
+
+ /* we'll use 'ptr' to keep track of the place to write data */
+ data = VARDATA(output);
+
+ memcpy(data, mcvlist, offsetof(MCVListData, items));
+ data += offsetof(MCVListData, items);
+
+ memcpy(data, info, sizeof(DimensionInfo) * ndims);
+ data += sizeof(DimensionInfo) * ndims;
+
+ /* value array for each dimension */
+ for (i = 0; i < ndims; i++)
+ {
+#ifdef USE_ASSERT_CHECKING
+ char *tmp = data;
+#endif
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ if (info[i].typbyval)
+ {
+ /* passed by value / Datum */
+ memcpy(data, &values[i][j], sizeof(Datum));
+ data += sizeof(Datum);
+ }
+ else if (info[i].typlen > 0)
+ {
+ /* pased by reference, but fixed length (name, tid, ...) */
+ memcpy(data, &values[i][j], info[i].typlen);
+ data += info[i].typlen;
+ }
+ else if (info[i].typlen == -1)
+ {
+ /* varlena */
+ memcpy(data, DatumGetPointer(values[i][j]),
+ VARSIZE_ANY(values[i][j]));
+ data += VARSIZE_ANY(values[i][j]);
+ }
+ else if (info[i].typlen == -2)
+ {
+ /* cstring (don't forget the \0 terminator!) */
+ memcpy(data, DatumGetPointer(values[i][j]),
+ strlen(DatumGetPointer(values[i][j])) + 1);
+ data += strlen(DatumGetPointer(values[i][j])) + 1;
+ }
+ }
+ Assert((data - tmp) == info[i].nbytes);
+ }
+
+ /* and finally, the MCV items */
+ for (i = 0; i < mcvlist->nitems; i++)
+ {
+ /* don't write beyond the allocated space */
+ Assert(data <= (char*)output + total_length - itemsize);
+
+ /* reset the values for each item */
+ memset(item, 0, itemsize);
+
+ for (j = 0; j < ndims; j++)
+ {
+ /* do the lookup only for non-NULL values */
+ if (! mcvlist->items[i]->isnull[j])
+ {
+ Datum * v = NULL;
+ ssup_private = &ssup[j];
+
+ v = (Datum*)bsearch(&mcvlist->items[i]->values[j],
+ values[j], info[j].nvalues, sizeof(Datum),
+ bsearch_comparator);
+
+ if (v == NULL)
+ elog(ERROR, "value for dim %d not found in array", j);
+
+ /* compute index within the array */
+ ITEM_INDEXES(item)[j] = (v - values[j]);
+
+ /* check the index is within expected bounds */
+ Assert(ITEM_INDEXES(item)[j] >= 0);
+ Assert(ITEM_INDEXES(item)[j] < info[j].nvalues);
+ }
+ }
+
+ /* copy NULL and frequency flags into the item */
+ memcpy(ITEM_NULLS(item, ndims),
+ mcvlist->items[i]->isnull, sizeof(bool) * ndims);
+ memcpy(ITEM_FREQUENCY(item, ndims),
+ &mcvlist->items[i]->frequency, sizeof(double));
+
+ /* copy the item into the array */
+ memcpy(data, item, itemsize);
+
+ data += itemsize;
+ }
+
+ /* at this point we expect to match the total_length exactly */
+ Assert((data - (char*)output) == total_length);
+
+ return output;
+}
+
+/* inverse to serialize_mv_mcvlist() - see the comment there */
+MCVList deserialize_mv_mcvlist(bytea * data)
+{
+ int i, j;
+ Size expected_size;
+ MCVList mcvlist;
+ char *tmp;
+
+ int ndims, nitems, itemsize;
+ DimensionInfo *info = NULL;
+
+ int32 *indexes = NULL;
+ Datum **values = NULL;
+
+ 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);
+
+ nitems = mcvlist->nitems;
+ ndims = mcvlist->ndimensions;
+ itemsize = ITEM_SIZE(ndims);
+
+ Assert(nitems > 0);
+ Assert((ndims >= 2) && (ndims <= MVSTATS_MAX_DIMENSIONS));
+
+ /*
+ * What size do we expect with those parameters (it's incomplete,
+ * as we yet have to count the array sizes (from DimensionInfo
+ * records).
+ */
+ expected_size = offsetof(MCVListData,items) +
+ ndims * sizeof(DimensionInfo) +
+ (nitems * itemsize);
+
+ /* check that we have at least the DimensionInfo records */
+ if (VARSIZE_ANY_EXHDR(data) < expected_size)
+ elog(ERROR, "invalid MCV Size %ld (expected %ld)",
+ VARSIZE_ANY_EXHDR(data), expected_size);
+
+ info = (DimensionInfo*)(tmp);
+ tmp += ndims * sizeof(DimensionInfo);
+
+ /* account for the value arrays */
+ for (i = 0; i < ndims; i++)
+ expected_size += info[i].nbytes;
+
+ if (VARSIZE_ANY_EXHDR(data) != expected_size)
+ elog(ERROR, "invalid MCV Size %ld (expected %ld)",
+ VARSIZE_ANY_EXHDR(data), expected_size);
+
+ /* looks OK - not corrupted or something */
+
+ /* let's parse the value arrays */
+ values = (Datum**)palloc0(sizeof(Datum*) * ndims);
+
+ /*
+ * FIXME This uses pointers to the original data array (the types
+ * not passed by value), so when someone frees the memory,
+ * e.g. by doing something like this:
+ *
+ * bytea * data = ... fetch the data from catalog ...
+ * MCVList mcvlist = deserialize_mcv_list(data);
+ * pfree(data);
+ *
+ * then 'mcvlist' references the freed memory. This needs to
+ * copy the pieces.
+ */
+ for (i = 0; i < ndims; i++)
+ {
+ if (info[i].typbyval)
+ {
+ /* passed by value / Datum - simply reuse the array */
+ values[i] = (Datum*)tmp;
+ tmp += info[i].nbytes;
+ }
+ else if (info[i].typlen > 0)
+ {
+ /* pased by reference, but fixed length (name, tid, ...) */
+ values[i] = (Datum*)palloc0(sizeof(Datum) * info[i].nvalues);
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ values[i][j] = PointerGetDatum(tmp);
+ tmp += info[i].typlen;
+ }
+ }
+ else if (info[i].typlen == -1)
+ {
+ /* varlena */
+ values[i] = (Datum*)palloc0(sizeof(Datum) * info[i].nvalues);
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ values[i][j] = PointerGetDatum(tmp);
+ tmp += VARSIZE_ANY(tmp);
+ }
+ }
+ else if (info[i].typlen == -2)
+ {
+ /* cstring */
+ values[i] = (Datum*)palloc0(sizeof(Datum) * info[i].nvalues);
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ values[i][j] = PointerGetDatum(tmp);
+ tmp += (strlen(tmp) + 1); /* don't forget the \0 */
+ }
+ }
+ }
+
+ /* allocate space for the MCV items */
+ mcvlist->items = (MCVItem*)palloc0(sizeof(MCVItem) * nitems);
+
+ for (i = 0; i < nitems; i++)
+ {
+ MCVItem item = (MCVItem)palloc0(sizeof(MCVItemData));
+
+ item->values = (Datum*)palloc0(sizeof(Datum)*ndims);
+ item->isnull = (bool*) palloc0(sizeof(bool) *ndims);
+
+ /* just point to the right place */
+ indexes = ITEM_INDEXES(tmp);
+
+ memcpy(item->isnull, ITEM_NULLS(tmp, ndims), sizeof(bool) * ndims);
+ memcpy(&item->frequency, ITEM_FREQUENCY(tmp, ndims), sizeof(double));
+
+ /* translate the values */
+ for (j = 0; j < ndims; j++)
+ if (! item->isnull[j])
+ item->values[j] = values[j][indexes[j]];
+
+ mcvlist->items[i] = item;
+
+ tmp += ITEM_SIZE(ndims);
+
+ Assert(tmp <= (char*)data + VARSIZE_ANY(data));
+ }
+
+ /* check that we processed all the data */
+ Assert(tmp == (char*)data + VARSIZE_ANY(data));
+
+ return mcvlist;
+}
+
+/*
+ * We need to pass the SortSupport to the comparator, but bsearch()
+ * has no 'context' parameter, so we use a global variable (ugly).
+ */
+static int
+bsearch_comparator(const void * a, const void * b)
+{
+ Assert(ssup_private != NULL);
+ return compare_scalars_simple(a, b, (void*)ssup_private);
+}
diff --git a/src/include/catalog/pg_mv_statistic.h b/src/include/catalog/pg_mv_statistic.h
index 81ec23b..c6e7d74 100644
--- a/src/include/catalog/pg_mv_statistic.h
+++ b/src/include/catalog/pg_mv_statistic.h
@@ -35,15 +35,21 @@ CATALOG(pg_mv_statistic,3381)
/* statistics requested to build */
bool deps_enabled; /* analyze dependencies? */
+ bool mcv_enabled; /* build MCV list? */
+
+ /* MCV size */
+ int32 mcv_max_items; /* max MCV items */
/* statistics that are available (if requested) */
bool deps_built; /* dependencies were built */
+ bool mcv_built; /* MCV list was built */
/* variable-length fields start here, but we allow direct access to stakeys */
int2vector stakeys; /* array of column keys */
#ifdef CATALOG_VARLEN
bytea stadeps; /* dependencies (serialized) */
+ bytea stamcv; /* MCV list (serialized) */
#endif
} FormData_pg_mv_statistic;
@@ -59,11 +65,15 @@ typedef FormData_pg_mv_statistic *Form_pg_mv_statistic;
* compiler constants for pg_attrdef
* ----------------
*/
-#define Natts_pg_mv_statistic 5
+#define Natts_pg_mv_statistic 9
#define Anum_pg_mv_statistic_starelid 1
#define Anum_pg_mv_statistic_deps_enabled 2
-#define Anum_pg_mv_statistic_deps_built 3
-#define Anum_pg_mv_statistic_stakeys 4
-#define Anum_pg_mv_statistic_stadeps 5
+#define Anum_pg_mv_statistic_mcv_enabled 3
+#define Anum_pg_mv_statistic_mcv_max_items 4
+#define Anum_pg_mv_statistic_deps_built 5
+#define Anum_pg_mv_statistic_mcv_built 6
+#define Anum_pg_mv_statistic_stakeys 7
+#define Anum_pg_mv_statistic_stadeps 8
+#define Anum_pg_mv_statistic_stamcv 9
#endif /* PG_MV_STATISTIC_H */
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 2916f11..b2aa815 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -2716,6 +2716,8 @@ DATA(insert OID = 3377 ( pg_mv_stats_dependencies_info PGNSP PGUID 12 1 0 0
DESCR("multivariate stats: functional dependencies info");
DATA(insert OID = 3378 ( pg_mv_stats_dependencies_show 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_dependencies_show _null_ _null_ _null_ ));
DESCR("multivariate stats: functional dependencies show");
+DATA(insert OID = 3376 ( pg_mv_stats_mcvlist_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_mcvlist_info _null_ _null_ _null_ ));
+DESCR("multi-variate statistics: MCV list info");
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");
diff --git a/src/include/utils/mvstats.h b/src/include/utils/mvstats.h
index ec6764b..6ff29d6 100644
--- a/src/include/utils/mvstats.h
+++ b/src/include/utils/mvstats.h
@@ -25,9 +25,11 @@ typedef struct MVStatsData {
/* statistics requested in ALTER TABLE ... ADD STATISTICS */
bool deps_enabled; /* analyze functional dependencies */
+ bool mcv_enabled; /* analyze MCV lists */
/* available statistics (computed by ANALYZE) */
bool deps_built; /* functional dependencies available */
+ bool mcv_built; /* MCV list is already available */
} MVStatsData;
typedef struct MVStatsData *MVStats;
@@ -66,6 +68,47 @@ typedef MVDependenciesData* MVDependencies;
#define MVSTAT_DEPS_TYPE_BASIC 1 /* basic dependencies type */
/*
+ * 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.
+ */
+typedef struct MCVItemData {
+ double frequency; /* frequency of this combination */
+ bool *isnull; /* lags of NULL values (up to 32 columns) */
+ Datum *values; /* 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 */
+
+/*
+ * Limits used for mcv_max_items option, i.e. we're always guaranteed
+ * to have space for at least MVSTAT_MCVLIST_MIN_ITEMS, and we cannot
+ * have more than MVSTAT_MCVLIST_MAX_ITEMS items.
+ *
+ * This is just a boundary for the 'max' threshold - the actual list
+ * may of course contain less items than MVSTAT_MCVLIST_MIN_ITEMS.
+ */
+#define MVSTAT_MCVLIST_MIN_ITEMS 128 /* min items in MCV list */
+#define MVSTAT_MCVLIST_MAX_ITEMS 8192 /* max items in MCV list */
+
+/*
* 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).
@@ -74,24 +117,39 @@ MVStats list_mv_stats(Oid relid, int *nstats, bool built_only);
bytea * fetch_mv_rules(Oid mvoid);
bytea * fetch_mv_dependencies(Oid mvoid);
+bytea * fetch_mv_mcvlist(Oid mvoid);
bytea * serialize_mv_dependencies(MVDependencies dependencies);
+bytea * serialize_mv_mcvlist(MCVList mcvlist, int2vector *attrs,
+ VacAttrStats **stats);
/* deserialization of stats (serialization is private to analyze) */
MVDependencies deserialize_mv_dependencies(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_dependencies_info(PG_FUNCTION_ARGS);
extern Datum pg_mv_stats_dependencies_show(PG_FUNCTION_ARGS);
+extern Datum pg_mv_stats_mcvlist_info(PG_FUNCTION_ARGS);
MVDependencies
-build_mv_dependencies(int numrows, HeapTuple *rows,
- int2vector *attrs,
- VacAttrStats **stats);
+build_mv_dependencies(int numrows, HeapTuple *rows, int2vector *attrs,
+ VacAttrStats **stats);
+
+MCVList
+build_mv_mcvlist(int numrows, HeapTuple *rows, int2vector *attrs,
+ VacAttrStats **stats, int *numrows_filtered);
void build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
- int natts, VacAttrStats **vacattrstats);
+ int natts, VacAttrStats **vacattrstats);
-void update_mv_stats(Oid relid, MVDependencies dependencies);
+void update_mv_stats(Oid relid, MVDependencies dependencies, MCVList mcvlist,
+ int2vector *attrs, VacAttrStats **stats);
#endif
diff --git a/src/test/regress/expected/mv_mcv.out b/src/test/regress/expected/mv_mcv.out
new file mode 100644
index 0000000..595cfbf
--- /dev/null
+++ b/src/test/regress/expected/mv_mcv.out
@@ -0,0 +1,210 @@
+-- data type passed by value
+CREATE TABLE mcv_list (
+ a INT,
+ b INT,
+ c INT
+);
+-- unknown column
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (unknown_column);
+ERROR: column "unknown_column" referenced in statistics does not exist
+-- single column
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a);
+ERROR: multivariate stats require 2 or more columns
+-- single column, duplicated
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, a);
+ERROR: duplicate column name in statistics definition
+-- two columns, one duplicated
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, a, b);
+ERROR: duplicate column name in statistics definition
+-- unknown option
+ALTER TABLE mcv_list ADD STATISTICS (unknown_option) ON (a, b, c);
+ERROR: unrecognized STATISTICS option "unknown_option"
+-- missing MCV statistics
+ALTER TABLE mcv_list ADD STATISTICS (dependencies, max_mcv_items 200) ON (a, b, c);
+ERROR: option 'mcv' is required by other options(s)
+-- invalid mcv_max_items value / too low
+ALTER TABLE mcv_list ADD STATISTICS (mcv, max_mcv_items 10) ON (a, b, c);
+ERROR: max number of MCV items must be at least 128
+-- invalid mcv_max_items value / too high
+ALTER TABLE mcv_list ADD STATISTICS (mcv, max_mcv_items 10000) ON (a, b, c);
+ERROR: max number of MCV items is 8192
+-- correct command
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, b, c);
+-- random data
+INSERT INTO mcv_list
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | f |
+(1 row)
+
+TRUNCATE mcv_list;
+-- a => b, a => c, b => c
+INSERT INTO mcv_list
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=1000
+(1 row)
+
+TRUNCATE mcv_list;
+-- a => b, a => c
+INSERT INTO mcv_list
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=1000
+(1 row)
+
+TRUNCATE mcv_list;
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mcv_list
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX mcv_idx ON mcv_list (a, b);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=100
+(1 row)
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mcv_list WHERE a = 10 AND b = 5;
+ QUERY PLAN
+--------------------------------------------
+ Bitmap Heap Scan on mcv_list
+ Recheck Cond: ((a = 10) AND (b = 5))
+ -> Bitmap Index Scan on mcv_idx
+ Index Cond: ((a = 10) AND (b = 5))
+(4 rows)
+
+DELETE FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+DROP TABLE mcv_list;
+-- varlena type (text)
+CREATE TABLE mcv_list (
+ a TEXT,
+ b TEXT,
+ c TEXT
+);
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, b, c);
+-- random data
+INSERT INTO mcv_list
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | f |
+(1 row)
+
+TRUNCATE mcv_list;
+-- a => b, a => c, b => c
+INSERT INTO mcv_list
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=1000
+(1 row)
+
+TRUNCATE mcv_list;
+-- a => b, a => c
+INSERT INTO mcv_list
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=1000
+(1 row)
+
+TRUNCATE mcv_list;
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mcv_list
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX mcv_idx ON mcv_list (a, b);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=100
+(1 row)
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mcv_list WHERE a = '10' AND b = '5';
+ QUERY PLAN
+------------------------------------------------------------
+ Bitmap Heap Scan on mcv_list
+ Recheck Cond: ((a = '10'::text) AND (b = '5'::text))
+ -> Bitmap Index Scan on mcv_idx
+ Index Cond: ((a = '10'::text) AND (b = '5'::text))
+(4 rows)
+
+TRUNCATE mcv_list;
+-- check explain (expect bitmap index scan, not plain index scan) with NULLs
+INSERT INTO mcv_list
+ SELECT
+ (CASE WHEN i/10000 = 0 THEN NULL ELSE i/10000 END),
+ (CASE WHEN i/20000 = 0 THEN NULL ELSE i/20000 END),
+ (CASE WHEN i/40000 = 0 THEN NULL ELSE i/40000 END)
+ FROM generate_series(1,1000000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=100
+(1 row)
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mcv_list WHERE a IS NULL AND b IS NULL;
+ QUERY PLAN
+---------------------------------------------------
+ Bitmap Heap Scan on mcv_list
+ Recheck Cond: ((a IS NULL) AND (b IS NULL))
+ -> Bitmap Index Scan on mcv_idx
+ Index Cond: ((a IS NULL) AND (b IS NULL))
+(4 rows)
+
+DELETE FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+DROP TABLE mcv_list;
+-- NULL values (mix of int and text columns)
+CREATE TABLE mcv_list (
+ a INT,
+ b TEXT,
+ c INT,
+ d TEXT
+);
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, b, c, d);
+INSERT INTO mcv_list
+ SELECT
+ mod(i, 100),
+ (CASE WHEN mod(i, 200) = 0 THEN NULL ELSE mod(i,200) END),
+ mod(i, 400),
+ (CASE WHEN mod(i, 300) = 0 THEN NULL ELSE mod(i,600) END)
+ FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+ mcv_enabled | mcv_built | pg_mv_stats_mcvlist_info
+-------------+-----------+--------------------------
+ t | t | nitems=1200
+(1 row)
+
+DELETE FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+DROP TABLE mcv_list;
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index f0117ca..6d9ab2f 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -1357,7 +1357,9 @@ pg_mv_stats| SELECT n.nspname AS schemaname,
c.relname AS tablename,
s.stakeys AS attnums,
length(s.stadeps) AS depsbytes,
- pg_mv_stats_dependencies_info(s.stadeps) AS depsinfo
+ pg_mv_stats_dependencies_info(s.stadeps) AS depsinfo,
+ length(s.stamcv) AS mcvbytes,
+ pg_mv_stats_mcvlist_info(s.stamcv) AS mcvinfo
FROM ((pg_mv_statistic s
JOIN pg_class c ON ((c.oid = s.starelid)))
LEFT JOIN pg_namespace n ON ((n.oid = c.relnamespace)));
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 00c6ddf..63727a4 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -111,4 +111,4 @@ test: event_trigger
test: stats
# run tests of multivariate stats
-test: mv_dependencies
+test: mv_dependencies mv_mcv
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index b818be9..5b07b3b 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -154,3 +154,4 @@ test: xml
test: event_trigger
test: stats
test: mv_dependencies
+test: mv_mcv
diff --git a/src/test/regress/sql/mv_mcv.sql b/src/test/regress/sql/mv_mcv.sql
new file mode 100644
index 0000000..410b52d
--- /dev/null
+++ b/src/test/regress/sql/mv_mcv.sql
@@ -0,0 +1,181 @@
+-- data type passed by value
+CREATE TABLE mcv_list (
+ a INT,
+ b INT,
+ c INT
+);
+
+-- unknown column
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (unknown_column);
+
+-- single column
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a);
+
+-- single column, duplicated
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, a);
+
+-- two columns, one duplicated
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, a, b);
+
+-- unknown option
+ALTER TABLE mcv_list ADD STATISTICS (unknown_option) ON (a, b, c);
+
+-- missing MCV statistics
+ALTER TABLE mcv_list ADD STATISTICS (dependencies, max_mcv_items 200) ON (a, b, c);
+
+-- invalid mcv_max_items value / too low
+ALTER TABLE mcv_list ADD STATISTICS (mcv, max_mcv_items 10) ON (a, b, c);
+
+-- invalid mcv_max_items value / too high
+ALTER TABLE mcv_list ADD STATISTICS (mcv, max_mcv_items 10000) ON (a, b, c);
+
+-- correct command
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, b, c);
+
+-- random data
+INSERT INTO mcv_list
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+TRUNCATE mcv_list;
+
+-- a => b, a => c, b => c
+INSERT INTO mcv_list
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+TRUNCATE mcv_list;
+
+-- a => b, a => c
+INSERT INTO mcv_list
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+TRUNCATE mcv_list;
+
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mcv_list
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX mcv_idx ON mcv_list (a, b);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mcv_list WHERE a = 10 AND b = 5;
+
+DELETE FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+DROP TABLE mcv_list;
+
+-- varlena type (text)
+CREATE TABLE mcv_list (
+ a TEXT,
+ b TEXT,
+ c TEXT
+);
+
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, b, c);
+
+-- random data
+INSERT INTO mcv_list
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+TRUNCATE mcv_list;
+
+-- a => b, a => c, b => c
+INSERT INTO mcv_list
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+TRUNCATE mcv_list;
+
+-- a => b, a => c
+INSERT INTO mcv_list
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+TRUNCATE mcv_list;
+
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mcv_list
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX mcv_idx ON mcv_list (a, b);
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mcv_list WHERE a = '10' AND b = '5';
+
+TRUNCATE mcv_list;
+
+-- check explain (expect bitmap index scan, not plain index scan) with NULLs
+INSERT INTO mcv_list
+ SELECT
+ (CASE WHEN i/10000 = 0 THEN NULL ELSE i/10000 END),
+ (CASE WHEN i/20000 = 0 THEN NULL ELSE i/20000 END),
+ (CASE WHEN i/40000 = 0 THEN NULL ELSE i/40000 END)
+ FROM generate_series(1,1000000) s(i);
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mcv_list WHERE a IS NULL AND b IS NULL;
+
+DELETE FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+DROP TABLE mcv_list;
+
+-- NULL values (mix of int and text columns)
+CREATE TABLE mcv_list (
+ a INT,
+ b TEXT,
+ c INT,
+ d TEXT
+);
+
+ALTER TABLE mcv_list ADD STATISTICS (mcv) ON (a, b, c, d);
+
+INSERT INTO mcv_list
+ SELECT
+ mod(i, 100),
+ (CASE WHEN mod(i, 200) = 0 THEN NULL ELSE mod(i,200) END),
+ mod(i, 400),
+ (CASE WHEN mod(i, 300) = 0 THEN NULL ELSE mod(i,600) END)
+ FROM generate_series(1,10000) s(i);
+
+ANALYZE mcv_list;
+
+SELECT mcv_enabled, mcv_built, pg_mv_stats_mcvlist_info(stamcv)
+ FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+
+DELETE FROM pg_mv_statistic WHERE starelid = 'mcv_list'::regclass;
+DROP TABLE mcv_list;
--
2.0.5