0005-multivariate-histograms.patch
text/x-patch
Filename: 0005-multivariate-histograms.patch
Type: text/x-patch
Part: 4
Message:
Re: multivariate statistics v11
Patch
Format: format-patch
Series: patch 0005
Subject: multivariate histograms
| File | + | − |
|---|---|---|
| doc/src/sgml/ref/create_statistics.sgml | 18 | 0 |
| src/backend/catalog/system_views.sql | 3 | 1 |
| src/backend/commands/statscmds.c | 39 | 5 |
| src/backend/nodes/outfuncs.c | 2 | 0 |
| src/backend/optimizer/path/clausesel.c | 562 | 9 |
| src/backend/optimizer/util/plancat.c | 3 | 1 |
| src/backend/utils/mvstats/common.c | 31 | 6 |
| src/backend/utils/mvstats/histogram.c | 2032 | 0 |
| src/backend/utils/mvstats/Makefile | 1 | 1 |
| src/backend/utils/mvstats/README.histogram | 287 | 0 |
| src/backend/utils/mvstats/README.stats | 2 | 0 |
| src/bin/psql/describe.c | 13 | 4 |
| src/include/catalog/pg_mv_statistic.h | 16 | 8 |
| src/include/catalog/pg_proc.h | 4 | 0 |
| src/include/nodes/relation.h | 2 | 0 |
| src/include/utils/mvstats.h | 135 | 1 |
| src/test/regress/expected/mv_histogram.out | 207 | 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_histogram.sql | 176 | 0 |
From 31ff6cd36727d73e72aaa5fa1a0c52da460dae5b Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tv@fuzzy.cz>
Date: Sun, 11 Jan 2015 20:18:24 +0100
Subject: [PATCH 5/9] multivariate histograms
- extends the pg_mv_statistic catalog (add 'hist' fields)
- building the histograms during ANALYZE
- simple estimation while planning the queries
Includes regression tests mostly equal to those for functional
dependencies / MCV lists.
---
doc/src/sgml/ref/create_statistics.sgml | 18 +
src/backend/catalog/system_views.sql | 4 +-
src/backend/commands/statscmds.c | 44 +-
src/backend/nodes/outfuncs.c | 2 +
src/backend/optimizer/path/clausesel.c | 571 +++++++-
src/backend/optimizer/util/plancat.c | 4 +-
src/backend/utils/mvstats/Makefile | 2 +-
src/backend/utils/mvstats/README.histogram | 287 ++++
src/backend/utils/mvstats/README.stats | 2 +
src/backend/utils/mvstats/common.c | 37 +-
src/backend/utils/mvstats/histogram.c | 2032 ++++++++++++++++++++++++++++
src/bin/psql/describe.c | 17 +-
src/include/catalog/pg_mv_statistic.h | 24 +-
src/include/catalog/pg_proc.h | 4 +
src/include/nodes/relation.h | 2 +
src/include/utils/mvstats.h | 136 +-
src/test/regress/expected/mv_histogram.out | 207 +++
src/test/regress/expected/rules.out | 4 +-
src/test/regress/parallel_schedule | 2 +-
src/test/regress/serial_schedule | 1 +
src/test/regress/sql/mv_histogram.sql | 176 +++
21 files changed, 3538 insertions(+), 38 deletions(-)
create mode 100644 src/backend/utils/mvstats/README.histogram
create mode 100644 src/backend/utils/mvstats/histogram.c
create mode 100644 src/test/regress/expected/mv_histogram.out
create mode 100644 src/test/regress/sql/mv_histogram.sql
diff --git a/doc/src/sgml/ref/create_statistics.sgml b/doc/src/sgml/ref/create_statistics.sgml
index 193e4b0..fd3382e 100644
--- a/doc/src/sgml/ref/create_statistics.sgml
+++ b/doc/src/sgml/ref/create_statistics.sgml
@@ -133,6 +133,24 @@ CREATE STATISTICS [ IF NOT EXISTS ] <replaceable class="PARAMETER">statistics_na
</varlistentry>
<varlistentry>
+ <term><literal>histogram</> (<type>boolean</>)</term>
+ <listitem>
+ <para>
+ Enables histogram for the statistics.
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term><literal>max_buckets</> (<type>integer</>)</term>
+ <listitem>
+ <para>
+ Maximum number of histogram buckets.
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
<term><literal>max_mcv_items</> (<type>integer</>)</term>
<listitem>
<para>
diff --git a/src/backend/catalog/system_views.sql b/src/backend/catalog/system_views.sql
index 2d570ee..6afdee0 100644
--- a/src/backend/catalog/system_views.sql
+++ b/src/backend/catalog/system_views.sql
@@ -167,7 +167,9 @@ CREATE VIEW pg_mv_stats AS
length(S.stadeps) as depsbytes,
pg_mv_stats_dependencies_info(S.stadeps) as depsinfo,
length(S.stamcv) AS mcvbytes,
- pg_mv_stats_mcvlist_info(S.stamcv) AS mcvinfo
+ pg_mv_stats_mcvlist_info(S.stamcv) AS mcvinfo,
+ length(S.stahist) AS histbytes,
+ pg_mv_stats_histogram_info(S.stahist) AS histinfo
FROM (pg_mv_statistic S JOIN pg_class C ON (C.oid = S.starelid))
LEFT JOIN pg_namespace N ON (N.oid = C.relnamespace);
diff --git a/src/backend/commands/statscmds.c b/src/backend/commands/statscmds.c
index 90bfaed..b974655 100644
--- a/src/backend/commands/statscmds.c
+++ b/src/backend/commands/statscmds.c
@@ -137,12 +137,15 @@ CreateStatistics(CreateStatsStmt *stmt)
/* by default build nothing */
bool build_dependencies = false,
- build_mcv = false;
+ build_mcv = false,
+ build_histogram = false;
- int32 max_mcv_items = -1;
+ int32 max_buckets = -1,
+ max_mcv_items = -1;
/* options required because of other options */
- bool require_mcv = false;
+ bool require_mcv = false,
+ require_histogram = false;
Assert(IsA(stmt, CreateStatsStmt));
@@ -241,6 +244,29 @@ CreateStatistics(CreateStatsStmt *stmt)
MVSTAT_MCVLIST_MAX_ITEMS)));
}
+ else if (strcmp(opt->defname, "histogram") == 0)
+ build_histogram = defGetBoolean(opt);
+ else if (strcmp(opt->defname, "max_buckets") == 0)
+ {
+ max_buckets = defGetInt32(opt);
+
+ /* this option requires 'histogram' to be enabled */
+ require_histogram = true;
+
+ /* sanity check */
+ if (max_buckets < MVSTAT_HIST_MIN_BUCKETS)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("minimum number of buckets is %d",
+ MVSTAT_HIST_MIN_BUCKETS)));
+
+ else if (max_buckets > MVSTAT_HIST_MAX_BUCKETS)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("maximum number of buckets is %d",
+ MVSTAT_HIST_MAX_BUCKETS)));
+
+ }
else
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
@@ -249,10 +275,10 @@ CreateStatistics(CreateStatsStmt *stmt)
}
/* check that at least some statistics were requested */
- if (! (build_dependencies || build_mcv))
+ if (! (build_dependencies || build_mcv || build_histogram))
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
- errmsg("no statistics type (dependencies, mcv) was requested")));
+ errmsg("no statistics type (dependencies, mcv, histogram) was requested")));
/* now do some checking of the options */
if (require_mcv && (! build_mcv))
@@ -260,6 +286,11 @@ CreateStatistics(CreateStatsStmt *stmt)
(errcode(ERRCODE_SYNTAX_ERROR),
errmsg("option 'mcv' is required by other options(s)")));
+ if (require_histogram && (! build_histogram))
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("option 'histogram' is required by other options(s)")));
+
/* sort the attnums and build int2vector */
qsort(attnums, numcols, sizeof(int16), compare_int16);
stakeys = buildint2vector(attnums, numcols);
@@ -279,11 +310,14 @@ CreateStatistics(CreateStatsStmt *stmt)
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_hist_enabled -1] = BoolGetDatum(build_histogram);
values[Anum_pg_mv_statistic_mcv_max_items -1] = Int32GetDatum(max_mcv_items);
+ values[Anum_pg_mv_statistic_hist_max_buckets -1] = Int32GetDatum(max_buckets);
nulls[Anum_pg_mv_statistic_stadeps -1] = true;
nulls[Anum_pg_mv_statistic_stamcv -1] = true;
+ nulls[Anum_pg_mv_statistic_stahist -1] = true;
/* insert the tuple into pg_mv_statistic */
mvstatrel = heap_open(MvStatisticRelationId, RowExclusiveLock);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index e3983fd..d3a96f0 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1978,10 +1978,12 @@ _outMVStatisticInfo(StringInfo str, const MVStatisticInfo *node)
/* enabled statistics */
WRITE_BOOL_FIELD(deps_enabled);
WRITE_BOOL_FIELD(mcv_enabled);
+ WRITE_BOOL_FIELD(hist_enabled);
/* built/available statistics */
WRITE_BOOL_FIELD(deps_built);
WRITE_BOOL_FIELD(mcv_built);
+ WRITE_BOOL_FIELD(hist_built);
}
static void
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 977f88e..0de2418 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -49,6 +49,7 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause,
#define MV_CLAUSE_TYPE_FDEP 0x01
#define MV_CLAUSE_TYPE_MCV 0x02
+#define MV_CLAUSE_TYPE_HIST 0x04
static bool clause_is_mv_compatible(Node *clause, Index relid, Bitmapset **attnums,
int type);
@@ -74,6 +75,8 @@ static Selectivity clauselist_mv_selectivity(PlannerInfo *root,
static Selectivity clauselist_mv_selectivity_mcvlist(PlannerInfo *root,
List *clauses, MVStatisticInfo *mvstats,
bool *fullmatch, Selectivity *lowsel);
+static Selectivity clauselist_mv_selectivity_histogram(PlannerInfo *root,
+ List *clauses, MVStatisticInfo *mvstats);
static int update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
int2vector *stakeys, MCVList mcvlist,
@@ -81,6 +84,12 @@ static int update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
Selectivity *lowsel, bool *fullmatch,
bool is_or);
+static int update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
+ int2vector *stakeys,
+ MVSerializedHistogram mvhist,
+ int nmatches, char * matches,
+ bool is_or);
+
static bool has_stats(List *stats, int type);
static List * find_stats(PlannerInfo *root, Index relid);
@@ -93,6 +102,7 @@ static List * find_stats(PlannerInfo *root, Index relid);
#define UPDATE_RESULT(m,r,isor) \
(m) = (isor) ? (MAX(m,r)) : (MIN(m,r))
+
/****************************************************************************
* ROUTINES TO COMPUTE SELECTIVITIES
****************************************************************************/
@@ -121,7 +131,7 @@ static List * find_stats(PlannerInfo *root, Index relid);
*
* First we try to reduce the list of clauses by applying (soft) functional
* dependencies, and then we try to estimate the selectivity of the reduced
- * list of clauses using the multivariate MCV list.
+ * list of clauses using the multivariate MCV list and histograms.
*
* Finally we remove the portion of clauses estimated using multivariate stats,
* and process the rest of the clauses using the regular per-column stats.
@@ -214,11 +224,13 @@ clauselist_selectivity(PlannerInfo *root,
* with the multivariate code and simply skip to estimation using the
* regular per-column stats.
*/
- if (has_stats(stats, MV_CLAUSE_TYPE_MCV) &&
- (count_mv_attnums(clauses, relid, MV_CLAUSE_TYPE_MCV) >= 2))
+ if (has_stats(stats, MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST) &&
+ (count_mv_attnums(clauses, relid,
+ MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST) >= 2))
{
/* collect attributes from the compatible conditions */
- Bitmapset *mvattnums = collect_mv_attnums(clauses, relid, MV_CLAUSE_TYPE_MCV);
+ Bitmapset *mvattnums = collect_mv_attnums(clauses, relid,
+ MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST);
/* and search for the statistic covering the most attributes */
MVStatisticInfo *mvstat = choose_mv_statistics(stats, mvattnums);
@@ -230,7 +242,7 @@ clauselist_selectivity(PlannerInfo *root,
/* split the clauselist into regular and mv-clauses */
clauses = clauselist_mv_split(root, relid, clauses, &mvclauses,
- mvstat, MV_CLAUSE_TYPE_MCV);
+ mvstat, MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST);
/* we've chosen the histogram to match the clauses */
Assert(mvclauses != NIL);
@@ -942,6 +954,7 @@ static Selectivity
clauselist_mv_selectivity(PlannerInfo *root, List *clauses, MVStatisticInfo *mvstats)
{
bool fullmatch = false;
+ Selectivity s1 = 0.0, s2 = 0.0;
/*
* Lowest frequency in the MCV list (may be used as an upper bound
@@ -955,9 +968,24 @@ clauselist_mv_selectivity(PlannerInfo *root, List *clauses, MVStatisticInfo *mvs
* MCV/histogram evaluation).
*/
- /* Evaluate the MCV selectivity */
- return clauselist_mv_selectivity_mcvlist(root, clauses, mvstats,
+ /* Evaluate the MCV first. */
+ s1 = clauselist_mv_selectivity_mcvlist(root, clauses, mvstats,
&fullmatch, &mcv_low);
+
+ /*
+ * If we got a full equality match on the MCV list, we're done (and
+ * the estimate is pretty good).
+ */
+ if (fullmatch && (s1 > 0.0))
+ return s1;
+
+ /* TODO if (fullmatch) without matching MCV item, use the mcv_low
+ * selectivity as upper bound */
+
+ s2 = clauselist_mv_selectivity_histogram(root, clauses, mvstats);
+
+ /* TODO clamp to <= 1.0 (or more strictly, when possible) */
+ return s1 + s2;
}
/*
@@ -1160,7 +1188,7 @@ choose_mv_statistics(List *stats, Bitmapset *attnums)
int numattrs = attrs->dim1;
/* skip dependencies-only stats */
- if (! info->mcv_built)
+ if (! (info->mcv_built || info->hist_built))
continue;
/* count columns covered by the histogram */
@@ -1391,7 +1419,7 @@ mv_compatible_walker(Node *node, mv_compatible_context *context)
case F_SCALARGTSEL:
/* not compatible with functional dependencies */
- if (! (context->types & MV_CLAUSE_TYPE_MCV))
+ if (! (context->types & (MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST)))
return true; /* terminate */
break;
@@ -2007,6 +2035,9 @@ has_stats(List *stats, int type)
if ((type & MV_CLAUSE_TYPE_MCV) && stat->mcv_built)
return true;
+
+ if ((type & MV_CLAUSE_TYPE_HIST) && stat->hist_built)
+ return true;
}
return false;
@@ -2411,3 +2442,525 @@ update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
return nmatches;
}
+
+/*
+ * Estimate selectivity of clauses using a histogram.
+ *
+ * If there's no histogram for the stats, the function returns 0.0.
+ *
+ * The general idea of this method is similar to how MCV lists are
+ * processed, except that this introduces the concept of a partial
+ * match (MCV only works with full match / mismatch).
+ *
+ * The algorithm works like this:
+ *
+ * 1) mark all buckets as 'full match'
+ * 2) walk through all the clauses
+ * 3) for a particular clause, walk through all the buckets
+ * 4) skip buckets that are already 'no match'
+ * 5) check clause for buckets that still match (at least partially)
+ * 6) sum frequencies for buckets to get selectivity
+ *
+ * Unlike MCV lists, histograms have a concept of a partial match. In
+ * that case we use 1/2 the bucket, to minimize the average error. The
+ * MV histograms are usually less detailed than the per-column ones,
+ * meaning the sum is often quite high (thanks to combining a lot of
+ * "partially hit" buckets).
+ *
+ * Maybe we could use per-bucket information with number of distinct
+ * values it contains (for each dimension), and then use that to correct
+ * the estimate (so with 10 distinct values, we'd use 1/10 of the bucket
+ * frequency). We might also scale the value depending on the actual
+ * ndistinct estimate (not just the values observed in the sample).
+ *
+ * Another option would be to multiply the selectivities, i.e. if we get
+ * 'partial match' for a bucket for multiple conditions, we might use
+ * 0.5^k (where k is the number of conditions), instead of 0.5. This
+ * probably does not minimize the average error, though.
+ *
+ * TODO This might use a similar shortcut to MCV lists - count buckets
+ * marked as partial/full match, and terminate once this drop to 0.
+ * Not sure if it's really worth it - for MCV lists a situation like
+ * this is not uncommon, but for histograms it's not that clear.
+ */
+static Selectivity
+clauselist_mv_selectivity_histogram(PlannerInfo *root, List *clauses,
+ MVStatisticInfo *mvstats)
+{
+ int i;
+ Selectivity s = 0.0;
+ Selectivity u = 0.0;
+
+ int nmatches = 0;
+ char *matches = NULL;
+
+ MVSerializedHistogram mvhist = NULL;
+
+ /* there's no histogram */
+ if (! mvstats->hist_built)
+ return 0.0;
+
+ /* There may be no histogram in the stats (check hist_built flag) */
+ mvhist = load_mv_histogram(mvstats->mvoid);
+
+ Assert (mvhist != NULL);
+ Assert (clauses != NIL);
+ Assert (list_length(clauses) >= 2);
+
+ /*
+ * Bitmap of bucket matches (mismatch, partial, full). by default
+ * all buckets fully match (and we'll eliminate them).
+ */
+ matches = palloc0(sizeof(char) * mvhist->nbuckets);
+ memset(matches, MVSTATS_MATCH_FULL, sizeof(char)*mvhist->nbuckets);
+
+ nmatches = mvhist->nbuckets;
+
+ /* build the match bitmap */
+ update_match_bitmap_histogram(root, clauses,
+ mvstats->stakeys, mvhist,
+ nmatches, matches, false);
+
+ /* now, walk through the buckets and sum the selectivities */
+ for (i = 0; i < mvhist->nbuckets; i++)
+ {
+ /*
+ * Find out what part of the data is covered by the histogram,
+ * so that we can 'scale' the selectivity properly (e.g. when
+ * only 50% of the sample got into the histogram, and the rest
+ * is in a MCV list).
+ *
+ * TODO This might be handled by keeping a global "frequency"
+ * for the whole histogram, which might save us some time
+ * spent accessing the not-matching part of the histogram.
+ * Although it's likely in a cache, so it's very fast.
+ */
+ u += mvhist->buckets[i]->ntuples;
+
+ if (matches[i] == MVSTATS_MATCH_FULL)
+ s += mvhist->buckets[i]->ntuples;
+ else if (matches[i] == MVSTATS_MATCH_PARTIAL)
+ s += 0.5 * mvhist->buckets[i]->ntuples;
+ }
+
+#ifdef DEBUG_MVHIST
+ debug_histogram_matches(mvhist, matches);
+#endif
+
+ /* release the allocated bitmap and deserialized histogram */
+ pfree(matches);
+ pfree(mvhist);
+
+ return s * u;
+}
+
+/* cached result of bucket boundary comparison for a single dimension */
+
+#define HIST_CACHE_NOT_FOUND 0x00
+#define HIST_CACHE_FALSE 0x01
+#define HIST_CACHE_TRUE 0x03
+#define HIST_CACHE_MASK 0x02
+
+static char
+bucket_contains_value(FmgrInfo ltproc, Datum constvalue,
+ Datum min_value, Datum max_value,
+ int min_index, int max_index,
+ bool min_include, bool max_include,
+ char * callcache)
+{
+ bool a, b;
+
+ char min_cached = callcache[min_index];
+ char max_cached = callcache[max_index];
+
+ /*
+ * First some quick checks on equality - if any of the boundaries equals,
+ * we have a partial match (so no need to call the comparator).
+ */
+ if (((min_value == constvalue) && (min_include)) ||
+ ((max_value == constvalue) && (max_include)))
+ return MVSTATS_MATCH_PARTIAL;
+
+ /* Keep the values 0/1 because of the XOR at the end. */
+ a = ((min_cached & HIST_CACHE_MASK) >> 1);
+ b = ((max_cached & HIST_CACHE_MASK) >> 1);
+
+ /*
+ * If result for the bucket lower bound not in cache, evaluate the function
+ * and store the result in the cache.
+ */
+ if (! min_cached)
+ {
+ a = DatumGetBool(FunctionCall2Coll(<proc,
+ DEFAULT_COLLATION_OID,
+ constvalue, min_value));
+ /* remember the result */
+ callcache[min_index] = (a) ? HIST_CACHE_TRUE : HIST_CACHE_FALSE;
+ }
+
+ /* And do the same for the upper bound. */
+ if (! max_cached)
+ {
+ b = DatumGetBool(FunctionCall2Coll(<proc,
+ DEFAULT_COLLATION_OID,
+ constvalue, max_value));
+ /* remember the result */
+ callcache[max_index] = (b) ? HIST_CACHE_TRUE : HIST_CACHE_FALSE;
+ }
+
+ return (a ^ b) ? MVSTATS_MATCH_PARTIAL : MVSTATS_MATCH_NONE;
+}
+
+static char
+bucket_is_smaller_than_value(FmgrInfo opproc, Datum constvalue,
+ Datum min_value, Datum max_value,
+ int min_index, int max_index,
+ bool min_include, bool max_include,
+ char * callcache, bool isgt)
+{
+ char min_cached = callcache[min_index];
+ char max_cached = callcache[max_index];
+
+ /* Keep the values 0/1 because of the XOR at the end. */
+ bool a = ((min_cached & HIST_CACHE_MASK) >> 1);
+ bool b = ((max_cached & HIST_CACHE_MASK) >> 1);
+
+ if (! min_cached)
+ {
+ a = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ min_value,
+ constvalue));
+ /* remember the result */
+ callcache[min_index] = (a) ? HIST_CACHE_TRUE : HIST_CACHE_FALSE;
+ }
+
+ if (! max_cached)
+ {
+ b = DatumGetBool(FunctionCall2Coll(&opproc,
+ DEFAULT_COLLATION_OID,
+ max_value,
+ constvalue));
+ /* remember the result */
+ callcache[max_index] = (b) ? HIST_CACHE_TRUE : HIST_CACHE_FALSE;
+ }
+
+ /*
+ * Now, we need to combine both results into the final answer, and we need
+ * to be careful about the 'isgt' variable which kinda inverts the meaning.
+ *
+ * First, we handle the case when each boundary returns different results.
+ * In that case the outcome can only be 'partial' match.
+ */
+ if (a != b)
+ return MVSTATS_MATCH_PARTIAL;
+
+ /*
+ * When the results are the same, then it depends on the 'isgt' value. There
+ * are four options:
+ *
+ * isgt=false a=b=true => full match
+ * isgt=false a=b=false => empty
+ * isgt=true a=b=true => empty
+ * isgt=true a=b=false => full match
+ *
+ * We'll cheat a bit, because we know that (a=b) so we'll use just one of them.
+ */
+ if (isgt)
+ return (!a) ? MVSTATS_MATCH_FULL : MVSTATS_MATCH_NONE;
+ else
+ return ( a) ? MVSTATS_MATCH_FULL : MVSTATS_MATCH_NONE;
+}
+
+/*
+ * Evaluate clauses using the histogram, 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.
+ *
+ * Note: This is not a simple bitmap in the sense that there are more
+ * than two possible values for each item - no match, partial
+ * match and full match. So we need 2 bits per item.
+ *
+ * TODO This works with 'bitmap' where each item is represented as a
+ * char, which is slightly wasteful. Instead, we could use a bitmap
+ * with 2 bits per item, reducing the size to ~1/4. By using values
+ * 0, 1 and 3 (instead of 0, 1 and 2), the operations (merging etc.)
+ * might be performed just like for simple bitmap by using & and |,
+ * which might be faster than min/max.
+ */
+static int
+update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
+ int2vector *stakeys,
+ MVSerializedHistogram mvhist,
+ int nmatches, char * matches,
+ bool is_or)
+{
+ int i;
+ ListCell * l;
+
+ /*
+ * Used for caching function calls, only once per deduplicated value.
+ *
+ * We know may have up to (2 * nbuckets) values per dimension. It's
+ * probably overkill, but let's allocate that once for all clauses,
+ * to minimize overhead.
+ *
+ * Also, we only need two bits per value, but this allocates byte
+ * per value. Might be worth optimizing.
+ *
+ * 0x00 - not yet called
+ * 0x01 - called, result is 'false'
+ * 0x03 - called, result is 'true'
+ */
+ char *callcache = palloc(mvhist->nbuckets);
+
+ Assert(mvhist != NULL);
+ Assert(mvhist->nbuckets > 0);
+ Assert(nmatches >= 0);
+ Assert(nmatches <= mvhist->nbuckets);
+
+ Assert(clauses != NIL);
+ Assert(list_length(clauses) >= 1);
+
+ /* loop through the clauses and do the estimation */
+ 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;
+
+ /* it's either OpClause, or NullTest */
+ if (is_opclause(clause))
+ {
+ OpExpr * expr = (OpExpr*)clause;
+ bool varonleft = true;
+ bool ok;
+
+ FmgrInfo opproc; /* operator */
+ fmgr_info(get_opcode(expr->opno), &opproc);
+
+ /* reset the cache (per clause) */
+ memset(callcache, 0, mvhist->nbuckets);
+
+ ok = (NumRelids(clause) == 1) &&
+ (is_pseudo_constant_clause(lsecond(expr->args)) ||
+ (varonleft = false,
+ is_pseudo_constant_clause(linitial(expr->args))));
+
+ if (ok)
+ {
+ FmgrInfo ltproc;
+ RegProcedure oprrest = get_oprrest(expr->opno);
+
+ Var * var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
+ Const * cst = (varonleft) ? lsecond(expr->args) : linitial(expr->args);
+ bool isgt = (! varonleft);
+
+ TypeCacheEntry *typecache
+ = lookup_type_cache(var->vartype, TYPECACHE_LT_OPR);
+
+ /* lookup dimension for the attribute */
+ int idx = mv_get_index(var->varattno, stakeys);
+
+ fmgr_info(get_opcode(typecache->lt_opr), <proc);
+
+ /*
+ * Check this for all buckets that still have "true" in the bitmap
+ *
+ * We already know the clauses use suitable operators (because that's
+ * how we filtered them).
+ */
+ for (i = 0; i < mvhist->nbuckets; i++)
+ {
+ char res = MVSTATS_MATCH_NONE;
+
+ MVSerializedBucket bucket = mvhist->buckets[i];
+
+ /* histogram boundaries */
+ Datum minval, maxval;
+ bool mininclude, maxinclude;
+ int minidx, maxidx;
+
+ /*
+ * For AND-lists, we can also mark NULL buckets as 'no match'
+ * (and then skip them). For OR-lists this is not possible.
+ */
+ if ((! is_or) && bucket->nullsonly[idx])
+ matches[i] = MVSTATS_MATCH_NONE;
+
+ /*
+ * Skip buckets that were already eliminated - this is impotant
+ * considering how we update the info (we only lower the match).
+ * We can't really do anything about the MATCH_PARTIAL buckets.
+ */
+ if ((! is_or) && (matches[i] == MVSTATS_MATCH_NONE))
+ continue;
+ else if (is_or && (matches[i] == MVSTATS_MATCH_FULL))
+ continue;
+
+ /* lookup the values and cache of function calls */
+ minidx = bucket->min[idx];
+ maxidx = bucket->max[idx];
+
+ minval = mvhist->values[idx][bucket->min[idx]];
+ maxval = mvhist->values[idx][bucket->max[idx]];
+
+ mininclude = bucket->min_inclusive[idx];
+ maxinclude = bucket->max_inclusive[idx];
+
+ /*
+ * TODO Maybe it's possible to add here a similar optimization
+ * as for the MCV lists:
+ *
+ * (nmatches == 0) && AND-list => all eliminated (FALSE)
+ * (nmatches == N) && OR-list => all eliminated (TRUE)
+ *
+ * But it's more complex because of the partial matches.
+ */
+
+ /*
+ * If it's not a "<" or ">" or "=" operator, just ignore the
+ * clause. Otherwise note the relid and attnum for the variable.
+ *
+ * TODO I'm really unsure the handling of 'isgt' flag (that is, clauses
+ * with reverse order of variable/constant) is correct. I wouldn't
+ * be surprised if there was some mixup. Using the lt/gt operators
+ * instead of messing with the opproc could make it simpler.
+ * It would however be using a different operator than the query,
+ * although it's not any shadier than using the selectivity function
+ * as is done currently.
+ */
+ switch (oprrest)
+ {
+ case F_SCALARLTSEL: /* Var < Const */
+ case F_SCALARGTSEL: /* Var > Const */
+
+ res = bucket_is_smaller_than_value(opproc, cst->constvalue,
+ minval, maxval,
+ minidx, maxidx,
+ mininclude, maxinclude,
+ callcache, isgt);
+ break;
+
+ case F_EQSEL:
+
+ /*
+ * We only check whether the value is within the bucket, using the
+ * lt operator, and we also check for equality with the boundaries.
+ */
+
+ res = bucket_contains_value(ltproc, cst->constvalue,
+ minval, maxval,
+ minidx, maxidx,
+ mininclude, maxinclude,
+ callcache);
+ break;
+ }
+
+ UPDATE_RESULT(matches[i], res, is_or);
+
+ }
+ }
+ }
+ 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 buckets and evaluate the current clause. We can
+ * skip items that were already ruled out, and terminate if there are
+ * no remaining buckets that might possibly match.
+ */
+ for (i = 0; i < mvhist->nbuckets; i++)
+ {
+ MVSerializedBucket bucket = mvhist->buckets[i];
+
+ /*
+ * Skip buckets that were already eliminated - this is impotant
+ * considering how we update the info (we only lower the match)
+ */
+ if ((! is_or) && (matches[i] == MVSTATS_MATCH_NONE))
+ continue;
+ else if (is_or && (matches[i] == MVSTATS_MATCH_FULL))
+ continue;
+
+ /* if the clause mismatches the bucket, set it as MATCH_NONE */
+ if ((expr->nulltesttype == IS_NULL)
+ && (! bucket->nullsonly[idx]))
+ UPDATE_RESULT(matches[i], MVSTATS_MATCH_NONE, is_or);
+
+ else if ((expr->nulltesttype == IS_NOT_NULL) &&
+ (bucket->nullsonly[idx]))
+ UPDATE_RESULT(matches[i], MVSTATS_MATCH_NONE, is_or);
+ }
+ }
+ 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 bucket */
+ int or_nmatches = 0;
+ char * or_matches = NULL;
+
+ Assert(orclauses != NIL);
+ Assert(list_length(orclauses) >= 2);
+
+ /* number of matching buckets */
+ or_nmatches = mvhist->nbuckets;
+
+ /* by default none of the buckets 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_histogram(root, orclauses,
+ stakeys, mvhist,
+ or_nmatches, or_matches, or_clause(clause));
+
+ /* merge the bitmap into the existing one*/
+ for (i = 0; i < mvhist->nbuckets; 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);
+ }
+
+ /* free the call cache */
+ pfree(callcache);
+
+ return nmatches;
+}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index a92f889..d46aed2 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -416,7 +416,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
mvstat = (Form_pg_mv_statistic) GETSTRUCT(htup);
/* unavailable stats are not interesting for the planner */
- if (mvstat->deps_built || mvstat->mcv_built)
+ if (mvstat->deps_built || mvstat->mcv_built || mvstat->hist_built)
{
info = makeNode(MVStatisticInfo);
@@ -426,10 +426,12 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
/* enabled statistics */
info->deps_enabled = mvstat->deps_enabled;
info->mcv_enabled = mvstat->mcv_enabled;
+ info->hist_enabled = mvstat->hist_enabled;
/* built/available statistics */
info->deps_built = mvstat->deps_built;
info->mcv_built = mvstat->mcv_built;
+ info->hist_built = mvstat->hist_built;
/* stakeys */
adatum = SysCacheGetAttr(MVSTATOID, htup,
diff --git a/src/backend/utils/mvstats/Makefile b/src/backend/utils/mvstats/Makefile
index f9bf10c..9dbb3b6 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 mcv.o
+OBJS = common.o dependencies.o histogram.o mcv.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/utils/mvstats/README.histogram b/src/backend/utils/mvstats/README.histogram
new file mode 100644
index 0000000..8234d2c
--- /dev/null
+++ b/src/backend/utils/mvstats/README.histogram
@@ -0,0 +1,287 @@
+Multivariate histograms
+=======================
+
+Histograms on individual attributes consist of buckets represented by ranges,
+covering the domain of the attribute. That is, each bucket is a [min,max]
+interval, and contains all values in this range. The histogram is built in such
+a way that all buckets have about the same frequency.
+
+Multivariate histograms are an extension into n-dimensional space - the buckets
+are n-dimensional intervals (i.e. n-dimensional rectagles), covering the domain
+of the combination of attributes. That is, each bucket has a vector of lower
+and upper boundaries, denoted min[i] and max[i] (where i = 1..n).
+
+In addition to the boundaries, each bucket tracks additional info:
+
+ * frequency (fraction of tuples in the bucket)
+ * whether the boundaries are inclusive or exclusive
+ * whether the dimension contains only NULL values
+ * number of distinct values in each dimension (for building only)
+
+It's possible that in the future we'll multiple histogram types, with different
+features. We do however expect all the types to share the same representation
+(buckets as ranges) and only differ in how we build them.
+
+The current implementation builds non-overlapping buckets, that may not be true
+for some histogram types and the code should not rely on this assumption. There
+are interesting types of histograms (or algorithms) with overlapping buckets.
+
+When used on low-cardinality data, histograms usually perform considerably worse
+than MCV lists (which are a good fit for this kind of data). This is especially
+true on label-like values, where ordering of the values is mostly unrelated to
+meaning of the data, as proper ordering is crucial for histograms.
+
+On high-cardinality data the histograms are usually a better choice, because MCV
+lists can't represent the distribution accurately enough.
+
+
+Selectivity estimation
+----------------------
+
+The estimation is implemented in clauselist_mv_selectivity_histogram(), and
+works very similarly to clauselist_mv_selectivity_mcvlist.
+
+The main difference is that while MCV lists support exact matches, histograms
+often result in approximate matches - e.g. with equality we can only say if
+the constant would be part of the bucket, but not whether it really is there
+or what fraction of the bucket it corresponds to. In this case we rely on
+some defaults just like in the per-column histograms.
+
+The current implementation uses histograms 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)
+ (c) NULL clauses WHERE (a IS NULL) AND (b IS NOT NULL)
+ (d) OR-clauses WHERE (a = 1) OR (b = 2)
+
+Similarly to MCV lists, it's possible to add support for additional types of
+clauses, for example:
+
+ (e) multi-var clauses WHERE (a > b)
+
+and so on. These are tasks for the future, not yet implemented.
+
+
+When evaluating a clause on a bucket, we may get one of three results:
+
+ (a) FULL_MATCH - The bucket definitely matches the clause.
+
+ (b) PARTIAL_MATCH - The bucket matches the clause, but not necessarily all
+ the tuples it represents.
+
+ (c) NO_MATCH - The bucket definitely does not match the clause.
+
+This may be illustrated using a range [1, 5], which is essentially a 1-D bucket.
+With clause
+
+ WHERE (a < 10) => FULL_MATCH (all range values are below
+ 10, so the whole bucket matches)
+
+ WHERE (a < 3) => PARTIAL_MATCH (there may be values matching
+ the clause, but we don't know how many)
+
+ WHERE (a < 0) => NO_MATCH (the whole range is above 1, so
+ no values from the bucket can match)
+
+Some clauses may produce only some of those results - for example equality
+clauses may never produce FULL_MATCH as we always hit only part of the bucket
+(we can't match both boundaries at the same time). This results in less accurate
+estimates compared to MCV lists, where we can hit a MCV items exactly (there's
+no PARTIAL match in MCV).
+
+There are also clauses that may not produce any PARTIAL_MATCH results. A nice
+example of that is 'IS [NOT] NULL' clause, which either matches the bucket
+completely (FULL_MATCH) or not at all (NO_MATCH), thanks to how the NULL-buckets
+are constructed.
+
+Computing the total selectivity estimate is trivial - simply sum selectivities
+from all the FULL_MATCH and PARTIAL_MATCH buckets (but for buckets marked with
+PARTIAL_MATCH, multiply the frequency by 0.5 to minimize the average error).
+
+
+Building a histogram
+---------------------
+
+The algorithm of building a histogram in general is quite simple:
+
+ (a) create an initial bucket (containing all sample rows)
+
+ (b) create NULL buckets (by splitting the initial bucket)
+
+ (c) repeat
+
+ (1) choose bucket to split next
+
+ (2) terminate if no bucket that might be split found, or if we've
+ reached the maximum number of buckets (16384)
+
+ (3) choose dimension to partition the bucket by
+
+ (4) partition the bucket by the selected dimension
+
+The main complexity is hidden in steps (c.1) and (c.3), i.e. how we choose the
+bucket and dimension for the split.
+
+Similarly to one-dimensional histograms, we want to produce buckets with roughly
+the same frequency. We also need to produce "regular" buckets, because buckets
+with one "side" much longer than the others are very likely to match a lot of
+conditions (which increases error, even if the bucket frequency is very low).
+
+To achieve this, we choose the largest bucket (containing the most sample rows),
+but we only choose buckets that can actually be split (have at least 3 different
+combinations of values).
+
+Then we choose the "longest" dimension of the bucket, which is computed by using
+the distinct values in the sample as a measure.
+
+For details see functions select_bucket_to_partition() and partition_bucket().
+
+The current limit on number of buckets (16384) is mostly arbitrary, but chosen
+so that it guarantees we don't exceed the number of distinct values indexable by
+uint16 in any of the dimensions. In practice we could handle more buckets as we
+index each dimension separately and the splits should use the dimensions evenly.
+
+Also, histograms this large (with 16k values in multiple dimensions) would be
+quite expensive to build and process, so the 16k limit is rather reasonable.
+
+The actual number of buckets is also related to statistics target, because we
+require MIN_BUCKET_ROWS (10) tuples per bucket before a split, so we can't have
+more than (2 * 300 * target / 10) buckets. For the default target (100) this
+evaluates to ~6k.
+
+
+NULL handling (create_null_buckets)
+-----------------------------------
+
+When building histograms on a single attribute, we first filter out NULL values.
+In the multivariate case, we can't really do that because the rows may contain
+a mix of NULL and non-NULL values in different columns (so we can't simply
+filter all of them out).
+
+For this reason, the histograms are built in a way so that for each bucket, each
+dimension only contains only NULL or non-NULL values. Building the NULL-buckets
+happens as the first step in the build, by the create_null_buckets() function.
+The number of NULL buckets, as produced by this function, has a clear upper
+boundary (2^N) where N is the number of dimensions (attributes the histogram is
+built on). Or rather 2^K where K is the number of attributes that are not marked
+as not-NULL.
+
+The buckets with NULL dimensions are then subject to the same build algorithm
+(i.e. may be split into smaller buckets) just like any other bucket, but may
+only be split by non-NULL dimension.
+
+
+Serialization
+-------------
+
+To store the histogram in pg_mv_statistic table, it is serialized into a more
+efficient form. We also use the representation for estimation, i.e. we don't
+fully deserialize the histogram.
+
+For example the boundary values are deduplicated to minimize the required space.
+How much redundancy is there, actually? Let's assume there are no NULL values,
+so we start with a single bucket - in that case we have 2*N boundaries. Each
+time we split a bucket we introduce one new value (in the "middle" of one of
+the dimensions), and keep boundries for all the other dimensions. So after K
+splits, we have up to
+
+ 2*N + K
+
+unique boundary values (we may have fewe values, if the same value is used for
+several splits). But after K splits we do have (K+1) buckets, so
+
+ (K+1) * 2 * N
+
+boundary values. Using e.g. N=4 and K=999, we arrive to those numbers:
+
+ 2*N + K = 1007
+ (K+1) * 2 * N = 8000
+
+wich means a lot of redundancy. It's somewhat counter-intuitive that the number
+of distinct values does not really depend on the number of dimensions (except
+for the initial bucket, but that's negligible compared to the total).
+
+By deduplicating the values and replacing them with 16-bit indexes (uint16), we
+reduce the required space to
+
+ 1007 * 8 + 8000 * 2 ~= 24kB
+
+which is significantly less than 64kB required for the 'raw' histogram (assuming
+the values are 8B).
+
+While the bytea compression (pglz) might achieve the same reduction of space,
+the deduplicated representation is used to optimize the estimation by caching
+results of function calls for already visited values. This significantly
+reduces the number of calls to (often quite expensive) operators.
+
+Note: Of course, this reasoning only holds for histograms built by the algorithm
+that simply splits the buckets in half. Other histograms types (e.g. containing
+overlapping buckets) may behave differently and require different serialization.
+
+Serialized histograms are marked with 'magic' constant, to make it easier to
+check the bytea value really is a serialized histogram.
+
+
+varlena compression
+-------------------
+
+This serialization may however disable automatic varlena compression, the array
+of unique values is placed at the beginning of the serialized form. Which is
+exactly the chunk used by pglz to check if the data is compressible, and it
+will probably decide it's not very compressible. This is similar to the issue
+we had with JSONB initially.
+
+Maybe storing buckets first would make it work, as the buckets may be better
+compressible.
+
+On the other hand the serialization is actually a context-aware compression,
+usually compressing to ~30% (or even less, with large data types). So the lack
+of additional pglz compression may be acceptable.
+
+
+Deserialization
+---------------
+
+The deserialization is not a perfect inverse of the serialization, as we keep
+the deduplicated arrays. This reduces the amount of memory and also allows
+optimizations during estimation (e.g. we can cache results for the distinct
+values, saving expensive function calls).
+
+
+Inspecting the histogram
+------------------------
+
+Inspecting the regular (per-attribute) histograms is trivial, as it's enough
+to select the columns from pg_stats - the data is encoded as anyarray, so we
+simply get the text representation of the array.
+
+With multivariate histograms it's not that simple due to the possible mix of
+data types in the histogram. It might be possible to produce similar array-like
+text representation, but that'd unnecessarily complicate further processing
+and analysis of the histogram. Instead, there's a SRF function that allows
+access to lower/upper boundaries, frequencies etc.
+
+ SELECT * FROM pg_mv_histogram_buckets();
+
+It has two input parameters:
+
+ oid - OID of the histogram (pg_mv_statistic.staoid)
+ otype - type of output
+
+and produces a table with these columns:
+
+ - bucket ID (0...nbuckets-1)
+ - lower bucket boundaries (string array)
+ - upper bucket boundaries (string array)
+ - nulls only dimensions (boolean array)
+ - lower boundary inclusive (boolean array)
+ - upper boundary includive (boolean array)
+ - frequency (double precision)
+
+The 'otype' accepts three values, determining what will be returned in the
+lower/upper boundary arrays:
+
+ - 0 - values stored in the histogram, encoded as text
+ - 1 - indexes into the deduplicated arrays
+ - 2 - idnexes into the deduplicated arrays, scaled to [0,1]
diff --git a/src/backend/utils/mvstats/README.stats b/src/backend/utils/mvstats/README.stats
index 5c5c59a..3e4f4d1 100644
--- a/src/backend/utils/mvstats/README.stats
+++ b/src/backend/utils/mvstats/README.stats
@@ -18,6 +18,8 @@ Currently we only have two kinds of multivariate statistics
(b) MCV lists (README.mcv)
+ (c) multivariate histograms (README.histogram)
+
Compatible clause types
-----------------------
diff --git a/src/backend/utils/mvstats/common.c b/src/backend/utils/mvstats/common.c
index d1da714..ffb76f4 100644
--- a/src/backend/utils/mvstats/common.c
+++ b/src/backend/utils/mvstats/common.c
@@ -13,11 +13,11 @@
*
*-------------------------------------------------------------------------
*/
+#include "postgres.h"
+#include "utils/array.h"
#include "common.h"
-#include "utils/array.h"
-
static VacAttrStats ** lookup_var_attr_stats(int2vector *attrs,
int natts,
VacAttrStats **vacattrstats);
@@ -52,7 +52,8 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
MVStatisticInfo *stat = (MVStatisticInfo *)lfirst(lc);
MVDependencies deps = NULL;
MCVList mcvlist = NULL;
- int numrows_filtered = 0;
+ MVHistogram histogram = NULL;
+ int numrows_filtered = numrows;
VacAttrStats **stats = NULL;
int numatts = 0;
@@ -95,8 +96,12 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
if (stat->mcv_enabled)
mcvlist = build_mv_mcvlist(numrows, rows, attrs, stats, &numrows_filtered);
+ /* build a multivariate histogram on the columns */
+ if ((numrows_filtered > 0) && (stat->hist_enabled))
+ histogram = build_mv_histogram(numrows_filtered, rows, attrs, stats, numrows);
+
/* store the histogram / MCV list in the catalog */
- update_mv_stats(stat->mvoid, deps, mcvlist, attrs, stats);
+ update_mv_stats(stat->mvoid, deps, mcvlist, histogram, attrs, stats);
}
}
@@ -176,6 +181,8 @@ list_mv_stats(Oid relid)
info->deps_built = stats->deps_built;
info->mcv_enabled = stats->mcv_enabled;
info->mcv_built = stats->mcv_built;
+ info->hist_enabled = stats->hist_enabled;
+ info->hist_built = stats->hist_built;
result = lappend(result, info);
}
@@ -190,7 +197,6 @@ list_mv_stats(Oid relid)
return result;
}
-
/*
* Find attnims of MV stats using the mvoid.
*/
@@ -236,9 +242,16 @@ find_mv_attnums(Oid mvoid, Oid *relid)
}
+/*
+ * FIXME This adds statistics, but we need to drop statistics when the
+ * table is dropped. Not sure what to do when a column is dropped.
+ * Either we can (a) remove all stats on that column, (b) remove
+ * the column from defined stats and force rebuild, (c) remove the
+ * column on next ANALYZE. Or maybe something else?
+ */
void
update_mv_stats(Oid mvoid,
- MVDependencies dependencies, MCVList mcvlist,
+ MVDependencies dependencies, MCVList mcvlist, MVHistogram histogram,
int2vector *attrs, VacAttrStats **stats)
{
HeapTuple stup,
@@ -271,22 +284,34 @@ update_mv_stats(Oid mvoid,
values[Anum_pg_mv_statistic_stamcv - 1] = PointerGetDatum(data);
}
+ if (histogram != NULL)
+ {
+ bytea * data = serialize_mv_histogram(histogram, attrs, stats);
+ nulls[Anum_pg_mv_statistic_stahist-1] = (data == NULL);
+ values[Anum_pg_mv_statistic_stahist - 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;
+ replaces[Anum_pg_mv_statistic_stahist-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;
+ nulls[Anum_pg_mv_statistic_hist_built-1] = false;
nulls[Anum_pg_mv_statistic_stakeys-1] = false;
/* use the new attnums, in case we removed some dropped ones */
replaces[Anum_pg_mv_statistic_deps_built-1] = true;
replaces[Anum_pg_mv_statistic_mcv_built -1] = true;
+ replaces[Anum_pg_mv_statistic_hist_built -1] = true;
replaces[Anum_pg_mv_statistic_stakeys -1] = true;
values[Anum_pg_mv_statistic_deps_built-1] = BoolGetDatum(dependencies != NULL);
values[Anum_pg_mv_statistic_mcv_built -1] = BoolGetDatum(mcvlist != NULL);
+ values[Anum_pg_mv_statistic_hist_built -1] = BoolGetDatum(histogram != NULL);
values[Anum_pg_mv_statistic_stakeys -1] = PointerGetDatum(attrs);
/* Is there already a pg_mv_statistic tuple for this attribute? */
diff --git a/src/backend/utils/mvstats/histogram.c b/src/backend/utils/mvstats/histogram.c
new file mode 100644
index 0000000..9e5620a
--- /dev/null
+++ b/src/backend/utils/mvstats/histogram.c
@@ -0,0 +1,2032 @@
+/*-------------------------------------------------------------------------
+ *
+ * histogram.c
+ * POSTGRES multivariate histograms
+ *
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/utils/mvstats/histogram.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "fmgr.h"
+#include "funcapi.h"
+
+#include "utils/lsyscache.h"
+
+#include "common.h"
+#include <math.h>
+
+
+static MVBucket create_initial_mv_bucket(int numrows, HeapTuple *rows,
+ int2vector *attrs,
+ VacAttrStats **stats);
+
+static MVBucket select_bucket_to_partition(int nbuckets, MVBucket * buckets);
+
+static MVBucket partition_bucket(MVBucket bucket, int2vector *attrs,
+ VacAttrStats **stats,
+ int *ndistvalues, Datum **distvalues);
+
+static MVBucket copy_mv_bucket(MVBucket bucket, uint32 ndimensions);
+
+static void update_bucket_ndistinct(MVBucket bucket, int2vector *attrs,
+ VacAttrStats ** stats);
+
+static void update_dimension_ndistinct(MVBucket bucket, int dimension,
+ int2vector *attrs,
+ VacAttrStats ** stats,
+ bool update_boundaries);
+
+static void create_null_buckets(MVHistogram histogram, int bucket_idx,
+ int2vector *attrs, VacAttrStats ** stats);
+
+static int bsearch_comparator(const void * a, const void * b);
+
+/*
+ * Each serialized bucket needs to store (in this order):
+ *
+ * - number of tuples (float)
+ * - number of distinct (float)
+ * - min inclusive flags (ndim * sizeof(bool))
+ * - max inclusive flags (ndim * sizeof(bool))
+ * - null dimension flags (ndim * sizeof(bool))
+ * - min boundary indexes (2 * ndim * sizeof(int32))
+ * - max boundary indexes (2 * ndim * sizeof(int32))
+ *
+ * So in total:
+ *
+ * ndim * (4 * sizeof(int32) + 3 * sizeof(bool)) +
+ * 2 * sizeof(float)
+ */
+#define BUCKET_SIZE(ndims) \
+ (ndims * (4 * sizeof(uint16) + 3 * sizeof(bool)) + sizeof(float))
+
+/* pointers into a flat serialized bucket of BUCKET_SIZE(n) bytes */
+#define BUCKET_NTUPLES(b) ((float*)b)
+#define BUCKET_MIN_INCL(b,n) ((bool*)(b + sizeof(float)))
+#define BUCKET_MAX_INCL(b,n) (BUCKET_MIN_INCL(b,n) + n)
+#define BUCKET_NULLS_ONLY(b,n) (BUCKET_MAX_INCL(b,n) + n)
+#define BUCKET_MIN_INDEXES(b,n) ((uint16*)(BUCKET_NULLS_ONLY(b,n) + n))
+#define BUCKET_MAX_INDEXES(b,n) ((BUCKET_MIN_INDEXES(b,n) + n))
+
+/* can't split bucket with less than 10 rows */
+#define MIN_BUCKET_ROWS 10
+
+/*
+ * Data used while building the histogram.
+ */
+typedef struct HistogramBuildData {
+
+ float ndistinct; /* frequency of distinct values */
+
+ HeapTuple *rows; /* aray of sample rows */
+ uint32 numrows; /* number of sample rows (array size) */
+
+ /*
+ * Number of distinct values in each dimension. This is used when
+ * building the histogram (and is not serialized/deserialized).
+ */
+ uint32 *ndistincts;
+
+} HistogramBuildData;
+
+typedef HistogramBuildData *HistogramBuild;
+
+/*
+ * Building a multivariate algorithm. In short it first creates a single
+ * bucket containing all the rows, and then repeatedly split is by first
+ * searching for the bucket / dimension most in need of a split.
+ *
+ * The current criteria is rather simple, chosen so that the algorithm
+ * produces buckets with about equal frequency and regular size.
+ *
+ * See the discussion at select_bucket_to_partition and partition_bucket
+ * for more details about the algorithm.
+ *
+ * The current algorithm works like this:
+ *
+ * build NULL-buckets (create_null_buckets)
+ *
+ * while [not reaching maximum number of buckets]
+ *
+ * choose bucket to partition (largest bucket)
+ * if no bucket to partition
+ * terminate the algorithm
+ *
+ * choose bucket dimension to partition (largest dimension)
+ * split the bucket into two buckets
+ */
+MVHistogram
+build_mv_histogram(int numrows, HeapTuple *rows, int2vector *attrs,
+ VacAttrStats **stats, int numrows_total)
+{
+ int i;
+ int numattrs = attrs->dim1;
+
+ int *ndistvalues;
+ Datum **distvalues;
+
+ MVHistogram histogram = (MVHistogram)palloc0(sizeof(MVHistogramData));
+
+ HeapTuple * rows_copy = (HeapTuple*)palloc0(numrows * sizeof(HeapTuple));
+ memcpy(rows_copy, rows, sizeof(HeapTuple) * numrows);
+
+ Assert((numattrs >= 2) && (numattrs <= MVSTATS_MAX_DIMENSIONS));
+
+ histogram->ndimensions = numattrs;
+
+ histogram->magic = MVSTAT_HIST_MAGIC;
+ histogram->type = MVSTAT_HIST_TYPE_BASIC;
+ histogram->nbuckets = 1;
+
+ /* create max buckets (better than repalloc for short-lived objects) */
+ histogram->buckets
+ = (MVBucket*)palloc0(MVSTAT_HIST_MAX_BUCKETS * sizeof(MVBucket));
+
+ /* create the initial bucket, covering the whole sample set */
+ histogram->buckets[0]
+ = create_initial_mv_bucket(numrows, rows_copy, attrs, stats);
+
+ /*
+ * Collect info on distinct values in each dimension (used later
+ * to select dimension to partition).
+ */
+ ndistvalues = (int*)palloc0(sizeof(int) * numattrs);
+ distvalues = (Datum**)palloc0(sizeof(Datum*) * numattrs);
+
+ for (i = 0; i < numattrs; i++)
+ {
+ int j;
+ int nvals;
+ Datum *tmp;
+
+ SortSupportData ssup;
+ StdAnalyzeData *mystats = (StdAnalyzeData *) stats[i]->extra_data;
+
+ /* initialize sort support, etc. */
+ memset(&ssup, 0, sizeof(ssup));
+ ssup.ssup_cxt = CurrentMemoryContext;
+
+ /* We always use the default collation for statistics */
+ ssup.ssup_collation = DEFAULT_COLLATION_OID;
+ ssup.ssup_nulls_first = false;
+
+ PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);
+
+ nvals = 0;
+ tmp = (Datum*)palloc0(sizeof(Datum) * numrows);
+
+ for (j = 0; j < numrows; j++)
+ {
+ bool isnull;
+
+ /* remember the index of the sample row, to make the partitioning simpler */
+ Datum value = heap_getattr(rows[j], attrs->values[i],
+ stats[i]->tupDesc, &isnull);
+
+ if (isnull)
+ continue;
+
+ tmp[nvals++] = value;
+ }
+
+ /* do the sort and stuff only if there are non-NULL values */
+ if (nvals > 0)
+ {
+ /* sort the array of values */
+ qsort_arg((void *) tmp, nvals, sizeof(Datum),
+ compare_scalars_simple, (void *) &ssup);
+
+ /* count distinct values */
+ ndistvalues[i] = 1;
+ for (j = 1; j < nvals; j++)
+ if (compare_scalars_simple(&tmp[j], &tmp[j-1], &ssup) != 0)
+ ndistvalues[i] += 1;
+
+ /* FIXME allocate only needed space (count ndistinct first) */
+ distvalues[i] = (Datum*)palloc0(sizeof(Datum) * ndistvalues[i]);
+
+ /* now collect distinct values into the array */
+ distvalues[i][0] = tmp[0];
+ ndistvalues[i] = 1;
+
+ for (j = 1; j < nvals; j++)
+ {
+ if (compare_scalars_simple(&tmp[j], &tmp[j-1], &ssup) != 0)
+ {
+ distvalues[i][ndistvalues[i]] = tmp[j];
+ ndistvalues[i] += 1;
+ }
+ }
+ }
+
+ pfree(tmp);
+ }
+
+ /*
+ * The initial bucket may contain NULL values, so we have to create
+ * buckets with NULL-only dimensions.
+ *
+ * FIXME We may need up to 2^ndims buckets - check that there are
+ * enough buckets (MVSTAT_HIST_MAX_BUCKETS >= 2^ndims).
+ */
+ create_null_buckets(histogram, 0, attrs, stats);
+
+ while (histogram->nbuckets < MVSTAT_HIST_MAX_BUCKETS)
+ {
+ MVBucket bucket = select_bucket_to_partition(histogram->nbuckets,
+ histogram->buckets);
+
+ /* no more buckets to partition */
+ if (bucket == NULL)
+ break;
+
+ histogram->buckets[histogram->nbuckets]
+ = partition_bucket(bucket, attrs, stats,
+ ndistvalues, distvalues);
+
+ histogram->nbuckets += 1;
+ }
+
+ /* finalize the frequencies etc. */
+ for (i = 0; i < histogram->nbuckets; i++)
+ {
+ HistogramBuild build_data
+ = ((HistogramBuild)histogram->buckets[i]->build_data);
+
+ /*
+ * The frequency has to be computed from the whole sample, in
+ * case some of the rows were used for MCV (and thus are missing
+ * from the histogram).
+ */
+ histogram->buckets[i]->ntuples
+ = (build_data->numrows * 1.0) / numrows_total;
+ }
+
+ return histogram;
+}
+
+/* fetch the histogram (as a bytea) from the pg_mv_statistic catalog */
+MVSerializedHistogram
+load_mv_histogram(Oid mvoid)
+{
+ bool isnull = false;
+ Datum histogram;
+
+#ifdef USE_ASSERT_CHECKING
+ Form_pg_mv_statistic mvstat;
+#endif
+
+ /* Prepare to scan pg_mv_statistic for entries having indrelid = this rel. */
+ HeapTuple htup = SearchSysCache1(MVSTATOID, ObjectIdGetDatum(mvoid));
+
+ if (! HeapTupleIsValid(htup))
+ return NULL;
+
+#ifdef USE_ASSERT_CHECKING
+ mvstat = (Form_pg_mv_statistic) GETSTRUCT(htup);
+ Assert(mvstat->hist_enabled && mvstat->hist_built);
+#endif
+
+ histogram = SysCacheGetAttr(MVSTATOID, htup,
+ Anum_pg_mv_statistic_stahist, &isnull);
+
+ Assert(!isnull);
+
+ ReleaseSysCache(htup);
+
+ return deserialize_mv_histogram(DatumGetByteaP(histogram));
+}
+
+/* print some basic info about the histogram */
+Datum
+pg_mv_stats_histogram_info(PG_FUNCTION_ARGS)
+{
+ bytea *data = PG_GETARG_BYTEA_P(0);
+ char *result;
+
+ MVSerializedHistogram hist = deserialize_mv_histogram(data);
+
+ result = palloc0(128);
+ snprintf(result, 128, "nbuckets=%d", hist->nbuckets);
+
+ PG_RETURN_TEXT_P(cstring_to_text(result));
+}
+
+
+/* used to pass context into bsearch() */
+static SortSupport ssup_private = NULL;
+
+/*
+ * Serialize the MV histogram into a bytea value. The basic algorithm is quite
+ * simple, and mostly mimincs the MCV serialization:
+ *
+ * (1) perform deduplication for each attribute (separately)
+ *
+ * (a) collect all (non-NULL) attribute values from all buckets
+ * (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 buckets
+ *
+ * (a) replace min/max values with indexes into the arrays
+ *
+ * Each attribute has to be processed separately, as we're mixing different
+ * datatypes, and we we need to use the right operators to compare/sort them.
+ * We're also mixing pass-by-value and pass-by-ref types, and so on.
+ *
+ *
+ * FIXME This probably leaks memory, or at least uses it inefficiently
+ * (many small palloc() calls instead of a large one).
+ *
+ * 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_histogram(MVHistogram histogram, int2vector *attrs,
+ VacAttrStats **stats)
+{
+ int i = 0, j = 0;
+ Size total_length = 0;
+
+ bytea *output = NULL;
+ char *data = NULL;
+
+ int nbuckets = histogram->nbuckets;
+ int ndims = histogram->ndimensions;
+
+ /* allocated for serialized bucket data */
+ int bucketsize = BUCKET_SIZE(ndims);
+ char *bucket = palloc0(bucketsize);
+
+ /* 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 separately */
+ 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 min/max values, including NULLs
+ * (we won't use them, but we don't know how many are there),
+ * and then collect all non-NULL values.
+ */
+ values[i] = (Datum*)palloc0(sizeof(Datum) * nbuckets * 2);
+
+ for (j = 0; j < histogram->nbuckets; j++)
+ {
+ /* skip buckets where this dimension is NULL-only */
+ if (! histogram->buckets[j]->nullsonly[i])
+ {
+ values[i][counts[i]] = histogram->buckets[j]->min[i];
+ counts[i] += 1;
+
+ values[i][counts[i]] = histogram->buckets[j]->max[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;
+ }
+ }
+
+ /* make sure we fit into uint16 */
+ Assert(count <= UINT16_MAX);
+
+ /* keep info about the deduplicated count */
+ info[i].nvalues = count;
+
+ /* compute size of the serialized data */
+ if (info[i].typlen > 0)
+ /* byval or byref, but with 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
+ * histogram, as it contains these fields:
+ *
+ * - length (4B) for varlena
+ * - magic (4B)
+ * - type (4B)
+ * - ndimensions (4B)
+ * - nbuckets (4B)
+ * - info (ndim * sizeof(DimensionInfo)
+ * - arrays of values for each dimension
+ * - serialized buckets (nbuckets * bucketsize)
+ *
+ * So the 'header' size is 20B + ndim * sizeof(DimensionInfo) and
+ * then we'll place the data (and buckets).
+ */
+ total_length = (sizeof(int32) + offsetof(MVHistogramData, buckets)
+ + ndims * sizeof(DimensionInfo)
+ + nbuckets * bucketsize);
+
+ /* account for the deduplicated data */
+ for (i = 0; i < ndims; i++)
+ total_length += info[i].nbytes;
+
+ /* enforce arbitrary limit of 1MB */
+ if (total_length > (10 * 1024 * 1024))
+ elog(ERROR, "serialized histogram exceeds 10MB (%ld > %d)",
+ total_length, (10 * 1024 * 1024));
+
+ /* allocate space for the serialized histogram list, set header */
+ output = (bytea*)palloc0(total_length);
+ SET_VARSIZE(output, total_length);
+
+ /* we'll use 'data' to keep track of the place to write data */
+ data = VARDATA(output);
+
+ memcpy(data, histogram, offsetof(MVHistogramData, buckets));
+ data += offsetof(MVHistogramData, buckets);
+
+ 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].typlen > 0)
+ {
+ /* pased by value or reference, but fixed length */
+ 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 histogram buckets */
+ for (i = 0; i < nbuckets; i++)
+ {
+ /* don't write beyond the allocated space */
+ Assert(data <= (char*)output + total_length - bucketsize);
+
+ /* reset the values for each item */
+ memset(bucket, 0, bucketsize);
+
+ *BUCKET_NTUPLES(bucket) = histogram->buckets[i]->ntuples;
+
+ for (j = 0; j < ndims; j++)
+ {
+ /* do the lookup only for non-NULL values */
+ if (! histogram->buckets[i]->nullsonly[j])
+ {
+ uint16 idx;
+ Datum * v = NULL;
+ ssup_private = &ssup[j];
+
+ /* min boundary */
+ v = (Datum*)bsearch(&histogram->buckets[i]->min[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 */
+ idx = (v - values[j]);
+
+ Assert((idx >= 0) && (idx < info[j].nvalues));
+
+ BUCKET_MIN_INDEXES(bucket, ndims)[j] = idx;
+
+ /* max boundary */
+ v = (Datum*)bsearch(&histogram->buckets[i]->max[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 */
+ idx = (v - values[j]);
+
+ Assert((idx >= 0) && (idx < info[j].nvalues));
+
+ BUCKET_MAX_INDEXES(bucket, ndims)[j] = idx;
+ }
+ }
+
+ /* copy flags (nulls, min/max inclusive) */
+ memcpy(BUCKET_NULLS_ONLY(bucket, ndims),
+ histogram->buckets[i]->nullsonly, sizeof(bool) * ndims);
+
+ memcpy(BUCKET_MIN_INCL(bucket, ndims),
+ histogram->buckets[i]->min_inclusive, sizeof(bool) * ndims);
+
+ memcpy(BUCKET_MAX_INCL(bucket, ndims),
+ histogram->buckets[i]->max_inclusive, sizeof(bool) * ndims);
+
+ /* copy the item into the array */
+ memcpy(data, bucket, bucketsize);
+
+ data += bucketsize;
+ }
+
+ /* at this point we expect to match the total_length exactly */
+ Assert((data - (char*)output) == total_length);
+
+ /* FIXME free the values/counts arrays here */
+
+ return output;
+}
+
+/*
+ * Returns histogram in a partially-serialized form (keeps the boundary
+ * values deduplicated, so that it's possible to optimize the estimation
+ * part by caching function call results between buckets etc.).
+ */
+MVSerializedHistogram
+deserialize_mv_histogram(bytea * data)
+{
+ int i = 0, j = 0;
+
+ Size expected_size;
+ char *tmp = NULL;
+
+ MVSerializedHistogram histogram;
+ DimensionInfo *info;
+
+ int nbuckets;
+ int ndims;
+ int bucketsize;
+
+ /* temporary deserialization buffer */
+ int bufflen;
+ char *buff;
+ char *ptr;
+
+ if (data == NULL)
+ return NULL;
+
+ if (VARSIZE_ANY_EXHDR(data) < offsetof(MVSerializedHistogramData,buckets))
+ elog(ERROR, "invalid histogram size %ld (expected at least %ld)",
+ VARSIZE_ANY_EXHDR(data), offsetof(MVSerializedHistogramData,buckets));
+
+ /* read the histogram header */
+ histogram
+ = (MVSerializedHistogram)palloc(sizeof(MVSerializedHistogramData));
+
+ /* initialize pointer to the data part (skip the varlena header) */
+ tmp = VARDATA(data);
+
+ /* get the header and perform basic sanity checks */
+ memcpy(histogram, tmp, offsetof(MVSerializedHistogramData, buckets));
+ tmp += offsetof(MVSerializedHistogramData, buckets);
+
+ if (histogram->magic != MVSTAT_HIST_MAGIC)
+ elog(ERROR, "invalid histogram magic %d (expected %dd)",
+ histogram->magic, MVSTAT_HIST_MAGIC);
+
+ if (histogram->type != MVSTAT_HIST_TYPE_BASIC)
+ elog(ERROR, "invalid histogram type %d (expected %dd)",
+ histogram->type, MVSTAT_HIST_TYPE_BASIC);
+
+ nbuckets = histogram->nbuckets;
+ ndims = histogram->ndimensions;
+ bucketsize = BUCKET_SIZE(ndims);
+
+ Assert((nbuckets > 0) && (nbuckets <= MVSTAT_HIST_MAX_BUCKETS));
+ 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(MVSerializedHistogramData,buckets) +
+ ndims * sizeof(DimensionInfo) +
+ (nbuckets * bucketsize);
+
+ /* check that we have at least the DimensionInfo records */
+ if (VARSIZE_ANY_EXHDR(data) < expected_size)
+ elog(ERROR, "invalid histogram 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 histogram size %ld (expected %ld)",
+ VARSIZE_ANY_EXHDR(data), expected_size);
+
+ /* looks OK - not corrupted or something */
+
+ /* now let's allocate a single buffer for all the values and counts */
+
+ bufflen = (sizeof(int) + sizeof(Datum*)) * ndims;
+ for (i = 0; i < ndims; i++)
+ {
+ /* don't allocate space for byval types, matching Datum */
+ if (! (info[i].typbyval && (info[i].typlen == sizeof(Datum))))
+ bufflen += (sizeof(Datum) * info[i].nvalues);
+ }
+
+ /* also, include space for the result, tracking the buckets */
+ bufflen += nbuckets * (
+ sizeof(MVSerializedBucket) + /* bucket pointer */
+ sizeof(MVSerializedBucketData)); /* bucket data */
+
+ buff = palloc0(bufflen);
+ ptr = buff;
+
+ histogram->nvalues = (int*)ptr;
+ ptr += (sizeof(int) * ndims);
+
+ histogram->values = (Datum**)ptr;
+ ptr += (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.
+ *
+ * TODO same as in MCV deserialization / consider moving to common.c
+ */
+ for (i = 0; i < ndims; i++)
+ {
+ histogram->nvalues[i] = info[i].nvalues;
+
+ if (info[i].typbyval && info[i].typlen == sizeof(Datum))
+ {
+ /* passed by value / Datum - simply reuse the array */
+ histogram->values[i] = (Datum*)tmp;
+ tmp += info[i].nbytes;
+ }
+ else
+ {
+ /* all the varlena data need a chunk from the buffer */
+ histogram->values[i] = (Datum*)ptr;
+ ptr += (sizeof(Datum) * info[i].nvalues);
+
+ if (info[i].typbyval)
+ {
+ /* pased by value, but smaller than Datum */
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ memcpy(&histogram->values[i][j], tmp, info[i].typlen);
+ tmp += info[i].typlen;
+ }
+ }
+ else if (info[i].typlen > 0)
+ {
+ /* pased by reference, but fixed length (name, tid, ...) */
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ histogram->values[i][j] = PointerGetDatum(tmp);
+ tmp += info[i].typlen;
+ }
+ }
+ else if (info[i].typlen == -1)
+ {
+ /* varlena */
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ histogram->values[i][j] = PointerGetDatum(tmp);
+ tmp += VARSIZE_ANY(tmp);
+ }
+ }
+ else if (info[i].typlen == -2)
+ {
+ /* cstring */
+ for (j = 0; j < info[i].nvalues; j++)
+ {
+ /* just point into the array */
+ histogram->values[i][j] = PointerGetDatum(tmp);
+ tmp += (strlen(tmp) + 1); /* don't forget the \0 */
+ }
+ }
+ }
+ }
+
+ histogram->buckets = (MVSerializedBucket*)ptr;
+ ptr += (sizeof(MVSerializedBucket) * nbuckets);
+
+ for (i = 0; i < nbuckets; i++)
+ {
+ MVSerializedBucket bucket = (MVSerializedBucket)ptr;
+ ptr += sizeof(MVSerializedBucketData);
+
+ bucket->ntuples = *BUCKET_NTUPLES(tmp);
+ bucket->nullsonly = BUCKET_NULLS_ONLY(tmp, ndims);
+ bucket->min_inclusive = BUCKET_MIN_INCL(tmp, ndims);
+ bucket->max_inclusive = BUCKET_MAX_INCL(tmp, ndims);
+
+ bucket->min = BUCKET_MIN_INDEXES(tmp, ndims);
+ bucket->max = BUCKET_MAX_INDEXES(tmp, ndims);
+
+ histogram->buckets[i] = bucket;
+
+ Assert(tmp <= (char*)data + VARSIZE_ANY(data));
+
+ tmp += bucketsize;
+ }
+
+ /* at this point we expect to match the total_length exactly */
+ Assert((tmp - VARDATA(data)) == expected_size);
+
+ /* we should exhaust the output buffer exactly */
+ Assert((ptr - buff) == bufflen);
+
+ return histogram;
+}
+
+/*
+ * Build the initial bucket, which will be then split into smaller ones.
+ */
+static MVBucket
+create_initial_mv_bucket(int numrows, HeapTuple *rows, int2vector *attrs,
+ VacAttrStats **stats)
+{
+ int i;
+ int numattrs = attrs->dim1;
+ HistogramBuild data = NULL;
+
+ /* TODO allocate bucket as a single piece, including all the fields. */
+ MVBucket bucket = (MVBucket)palloc0(sizeof(MVBucketData));
+
+ Assert(numrows > 0);
+ Assert(rows != NULL);
+ Assert((numattrs >= 2) && (numattrs <= MVSTATS_MAX_DIMENSIONS));
+
+ /* allocate the per-dimension arrays */
+
+ /* flags for null-only dimensions */
+ bucket->nullsonly = (bool*)palloc0(numattrs * sizeof(bool));
+
+ /* inclusiveness boundaries - lower/upper bounds */
+ bucket->min_inclusive = (bool*)palloc0(numattrs * sizeof(bool));
+ bucket->max_inclusive = (bool*)palloc0(numattrs * sizeof(bool));
+
+ /* lower/upper boundaries */
+ bucket->min = (Datum*)palloc0(numattrs * sizeof(Datum));
+ bucket->max = (Datum*)palloc0(numattrs * sizeof(Datum));
+
+ /* build-data */
+ data = (HistogramBuild)palloc0(sizeof(HistogramBuildData));
+
+ /* number of distinct values (per dimension) */
+ data->ndistincts = (uint32*)palloc0(numattrs * sizeof(uint32));
+
+ /* all the sample rows fall into the initial bucket */
+ data->numrows = numrows;
+ data->rows = rows;
+
+ bucket->build_data = data;
+
+ /*
+ * Update the number of ndistinct combinations in the bucket (which
+ * we use when selecting bucket to partition), and then number of
+ * distinct values for each partition (which we use when choosing
+ * which dimension to split).
+ */
+ update_bucket_ndistinct(bucket, attrs, stats);
+
+ /* Update ndistinct (and also set min/max) for all dimensions. */
+ for (i = 0; i < numattrs; i++)
+ update_dimension_ndistinct(bucket, i, attrs, stats, true);
+
+ return bucket;
+}
+
+/*
+ * Choose the bucket to partition next.
+ *
+ * The current criteria is rather simple, chosen so that the algorithm
+ * produces buckets with about equal frequency and regular size. We
+ * select the bucket with the highest number of distinct values, and
+ * then split it by the longest dimension.
+ *
+ * The distinct values are uniformly mapped to [0,1] interval, and this
+ * is used to compute length of the value range.
+ *
+ * NOTE: This is not the same array used for deduplication, as this
+ * contains values for all the tuples from the sample, not just
+ * the boundary values.
+ *
+ * Returns either pointer to the bucket selected to be partitioned,
+ * or NULL if there are no buckets that may be split (i.e. all buckets
+ * contain a single distinct value).
+ *
+ * TODO Consider other partitioning criteria (v-optimal, maxdiff etc.).
+ * For example use the "bucket volume" (product of dimension
+ * lengths) to select the bucket.
+ *
+ * We need buckets containing about the same number of tuples (so
+ * about the same frequency), as that limits the error when we
+ * match the bucket partially (in that case use 1/2 the bucket).
+ *
+ * We also need buckets with "regular" size, i.e. not "narrow" in
+ * some dimensions and "wide" in the others, because that makes
+ * partial matches more likely and increases the estimation error,
+ * especially when the clauses match many buckets partially. This
+ * is especially serious for OR-clauses, because in that case any
+ * of them may add the bucket as a (partial) match. With AND-clauses
+ * all the clauses have to match the bucket, which makes this issue
+ * somewhat less pressing.
+ *
+ * For example this table:
+ *
+ * CREATE TABLE t AS SELECT i AS a, i AS b
+ * FROM generate_series(1,1000000) s(i);
+ * ALTER TABLE t ADD STATISTICS (histogram) ON (a,b);
+ * ANALYZE t;
+ *
+ * It's a very specific (and perhaps artificial) example, because
+ * every bucket always has exactly the same number of distinct
+ * values in all dimensions, which makes the partitioning tricky.
+ *
+ * Then:
+ *
+ * SELECT * FROM t WHERE a < 10 AND b < 10;
+ *
+ * is estimated to return ~120 rows, while in reality it returns 9.
+ *
+ * QUERY PLAN
+ * ----------------------------------------------------------------
+ * Seq Scan on t (cost=0.00..19425.00 rows=117 width=8)
+ * (actual time=0.185..270.774 rows=9 loops=1)
+ * Filter: ((a < 10) AND (b < 10))
+ * Rows Removed by Filter: 999991
+ *
+ * while the query using OR clauses is estimated like this:
+ *
+ * QUERY PLAN
+ * ----------------------------------------------------------------
+ * Seq Scan on t (cost=0.00..19425.00 rows=8100 width=8)
+ * (actual time=0.118..189.919 rows=9 loops=1)
+ * Filter: ((a < 10) OR (b < 10))
+ * Rows Removed by Filter: 999991
+ *
+ * which is clearly much worse. This happens because the histogram
+ * contains buckets like this:
+ *
+ * bucket 592 [3 30310] [30134 30593] => [0.000233]
+ *
+ * i.e. the length of "a" dimension is (30310-3)=30307, while the
+ * length of "b" is (30593-30134)=459. So the "b" dimension is much
+ * narrower than "a". Of course, there are buckets where "b" is the
+ * wider dimension.
+ *
+ * This is partially mitigated by selecting the "longest" dimension
+ * in partition_bucket() but that only happens after we already
+ * selected the bucket. So if we never select the bucket, we can't
+ * really fix it there.
+ *
+ * The other reason why this particular example behaves so poorly
+ * is due to the way we split the partition in partition_bucket().
+ * Currently we attempt to divide the bucket into two parts with
+ * the same number of sampled tuples (frequency), but that does not
+ * work well when all the tuples are squashed on one end of the
+ * bucket (e.g. exactly at the diagonal, as a=b). In that case we
+ * split the bucket into a tiny bucket on the diagonal, and a huge
+ * remaining part of the bucket, which is still going to be narrow
+ * and we're unlikely to fix that.
+ *
+ * So perhaps we need two partitioning strategies - one aiming to
+ * split buckets with high frequency (number of sampled rows), the
+ * other aiming to split "large" buckets. And alternating between
+ * them, somehow.
+ *
+ * TODO Allowing the bucket to degenerate to a single combination of
+ * values makes it rather strange MCV list. Maybe we should use
+ * higher lower boundary, or maybe make the selection criteria
+ * more complex (e.g. consider number of rows in the bucket, etc.).
+ *
+ * That however is different from buckets 'degenerated' only for
+ * some dimensions (e.g. half of them), which is perfectly
+ * appropriate for statistics on a combination of low and high
+ * cardinality columns.
+ *
+ * TODO Consider using similar lower boundary for row count as for simple
+ * histograms, i.e. 300 tuples per bucket.
+ */
+static MVBucket
+select_bucket_to_partition(int nbuckets, MVBucket * buckets)
+{
+ int i;
+ int numrows = 0;
+ MVBucket bucket = NULL;
+
+ for (i = 0; i < nbuckets; i++)
+ {
+ HistogramBuild data = (HistogramBuild)buckets[i]->build_data;
+ /* if the number of rows is higher, use this bucket */
+ if ((data->ndistinct > 2) &&
+ (data->numrows > numrows) &&
+ (data->numrows >= MIN_BUCKET_ROWS)) {
+ bucket = buckets[i];
+ numrows = data->numrows;
+ }
+ }
+
+ /* may be NULL if there are not buckets with (ndistinct>1) */
+ return bucket;
+}
+
+/*
+ * A simple bucket partitioning implementation - we choose the longest
+ * bucket dimension, measured using the array of distinct values built
+ * at the very beginning of the build.
+ *
+ * We map all the distinct values to a [0,1] interval, uniformly
+ * distributed, and then use this to measure length. It's essentially
+ * a number of distinct values within the range, normalized to [0,1].
+ *
+ * Then we choose a 'middle' value splitting the bucket into two parts
+ * with roughly the same frequency.
+ *
+ * This splits the bucket by tweaking the existing one, and returning
+ * the new bucket (essentially shrinking the existing one in-place and
+ * returning the other "half" as a new bucket). The caller is responsible
+ * for adding the new bucket into the list of buckets.
+ *
+ * There are multiple histogram options, centered around the partitioning
+ * criteria, specifying both how to choose a bucket and the dimension
+ * most in need of a split. For a nice summary and general overview, see
+ * "rK-Hist : an R-Tree based histogram for multi-dimensional selectivity
+ * estimation" thesis by J. A. Lopez, Concordia University, p.34-37 (and
+ * possibly p. 32-34 for explanation of the terms).
+ *
+ * TODO It requires care to prevent splitting only one dimension and not
+ * splitting another one at all (which might happen easily in case
+ * of strongly dependent columns - e.g. y=x). The current algorithm
+ * minimizes this, but may still happen for perfectly dependent
+ * examples (when all the dimensions have equal length, the first
+ * one will be selected).
+ *
+ * TODO Should probably consider statistics target for the columns (e.g.
+ * to split dimensions with higher statistics target more frequently).
+ */
+static MVBucket
+partition_bucket(MVBucket bucket, int2vector *attrs,
+ VacAttrStats **stats,
+ int *ndistvalues, Datum **distvalues)
+{
+ int i;
+ int dimension;
+ int numattrs = attrs->dim1;
+
+ Datum split_value;
+ MVBucket new_bucket;
+ HistogramBuild new_data;
+
+ /* needed for sort, when looking for the split value */
+ bool isNull;
+ int nvalues = 0;
+ HistogramBuild data = (HistogramBuild)bucket->build_data;
+ StdAnalyzeData * mystats = NULL;
+ ScalarItem * values = (ScalarItem*)palloc0(data->numrows * sizeof(ScalarItem));
+ SortSupportData ssup;
+
+ /* looking for the split value */
+ // int ndistinct = 1; /* number of distinct values below current value */
+ int nrows = 1; /* number of rows below current value */
+ double delta;
+
+ /* needed when splitting the values */
+ HeapTuple * oldrows = data->rows;
+ int oldnrows = data->numrows;
+
+ /*
+ * We can't split buckets with a single distinct value (this also
+ * disqualifies NULL-only dimensions). Also, there has to be multiple
+ * sample rows (otherwise, how could there be more distinct values).
+ */
+ Assert(data->ndistinct > 1);
+ Assert(data->numrows > 1);
+ Assert((numattrs >= 2) && (numattrs <= MVSTATS_MAX_DIMENSIONS));
+
+ /*
+ * Look for the next dimension to split.
+ */
+ delta = 0.0;
+ dimension = -1;
+
+ for (i = 0; i < numattrs; i++)
+ {
+ Datum *a, *b;
+
+ mystats = (StdAnalyzeData *) stats[i]->extra_data;
+
+ /* initialize sort support, etc. */
+ memset(&ssup, 0, sizeof(ssup));
+ ssup.ssup_cxt = CurrentMemoryContext;
+
+ /* We always use the default collation for statistics */
+ ssup.ssup_collation = DEFAULT_COLLATION_OID;
+ ssup.ssup_nulls_first = false;
+
+ PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);
+
+ /* can't split NULL-only dimension */
+ if (bucket->nullsonly[i])
+ continue;
+
+ /* can't split dimension with a single ndistinct value */
+ if (data->ndistincts[i] <= 1)
+ continue;
+
+ /* sort support for the bsearch_comparator */
+ ssup_private = &ssup;
+
+ /* search for min boundary in the distinct list */
+ a = (Datum*)bsearch(&bucket->min[i],
+ distvalues[i], ndistvalues[i],
+ sizeof(Datum), bsearch_comparator);
+
+ b = (Datum*)bsearch(&bucket->max[i],
+ distvalues[i], ndistvalues[i],
+ sizeof(Datum), bsearch_comparator);
+
+ /* if this dimension is 'larger' then partition by it */
+ if (((b-a)*1.0 / ndistvalues[i]) > delta)
+ {
+ delta = ((b-a)*1.0 / ndistvalues[i]);
+ dimension = i;
+ }
+ }
+
+ /*
+ * If we haven't found a dimension here, we've done something
+ * wrong in select_bucket_to_partition.
+ */
+ Assert(dimension != -1);
+
+ /*
+ * Walk through the selected dimension, collect and sort the values
+ * and then choose the value to use as the new boundary.
+ */
+ mystats = (StdAnalyzeData *) stats[dimension]->extra_data;
+
+ /* initialize sort support, etc. */
+ memset(&ssup, 0, sizeof(ssup));
+ ssup.ssup_cxt = CurrentMemoryContext;
+
+ /* We always use the default collation for statistics */
+ ssup.ssup_collation = DEFAULT_COLLATION_OID;
+ ssup.ssup_nulls_first = false;
+
+ PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);
+
+ for (i = 0; i < data->numrows; i++)
+ {
+ /* remember the index of the sample row, to make the partitioning simpler */
+ values[nvalues].value = heap_getattr(data->rows[i], attrs->values[dimension],
+ stats[dimension]->tupDesc, &isNull);
+ values[nvalues].tupno = i;
+
+ /* no NULL values allowed here (we don't do splits by null-only dimensions) */
+ Assert(!isNull);
+
+ nvalues++;
+ }
+
+ /* sort the array of values */
+ qsort_arg((void *) values, nvalues, sizeof(ScalarItem),
+ compare_scalars_partition, (void *) &ssup);
+
+ /*
+ * We know there are bucket->ndistincts[dimension] distinct values
+ * in this dimension, and we want to split this into half, so walk
+ * through the array and stop once we see (ndistinct/2) values.
+ *
+ * We always choose the "next" value, i.e. (n/2+1)-th distinct value,
+ * and use it as an exclusive upper boundary (and inclusive lower
+ * boundary).
+ *
+ * TODO Maybe we should use "average" of the two middle distinct
+ * values (at least for even distinct counts), but that would
+ * require being able to do an average (which does not work
+ * for non-arithmetic types).
+ *
+ * TODO Another option is to look for a split that'd give about
+ * 50% tuples (not distinct values) in each partition. That
+ * might work better when there are a few very frequent
+ * values, and many rare ones.
+ */
+ delta = fabs(data->numrows);
+ split_value = values[0].value;
+
+ for (i = 1; i < data->numrows; i++)
+ {
+ if (values[i].value != values[i-1].value)
+ {
+ /* are we closer to splitting the bucket in half? */
+ if (fabs(i - data->numrows/2.0) < delta)
+ {
+ /* let's assume we'll use this value for the split */
+ split_value = values[i].value;
+ delta = fabs(i - data->numrows/2.0);
+ nrows = i;
+ }
+ }
+ }
+
+ Assert(nrows > 0);
+ Assert(nrows < data->numrows);
+
+ /* create the new bucket as a (incomplete) copy of the one being partitioned. */
+ new_bucket = copy_mv_bucket(bucket, numattrs);
+ new_data = (HistogramBuild)new_bucket->build_data;
+
+ /*
+ * Do the actual split of the chosen dimension, using the split value as the
+ * upper bound for the existing bucket, and lower bound for the new one.
+ */
+ bucket->max[dimension] = split_value;
+ new_bucket->min[dimension] = split_value;
+
+ bucket->max_inclusive[dimension] = false;
+ new_bucket->max_inclusive[dimension] = true;
+
+ /*
+ * Redistribute the sample tuples using the 'ScalarItem->tupno'
+ * index. We know 'nrows' rows should remain in the original
+ * bucket and the rest goes to the new one.
+ */
+
+ data->rows = (HeapTuple*)palloc0(nrows * sizeof(HeapTuple));
+ new_data->rows = (HeapTuple*)palloc0((oldnrows - nrows) * sizeof(HeapTuple));
+
+ data->numrows = nrows;
+ new_data->numrows = (oldnrows - nrows);
+
+ /*
+ * The first nrows should go to the first bucket, the rest should
+ * go to the new one. Use the tupno field to get the actual HeapTuple
+ * row from the original array of sample rows.
+ */
+ for (i = 0; i < nrows; i++)
+ memcpy(&data->rows[i], &oldrows[values[i].tupno], sizeof(HeapTuple));
+
+ for (i = nrows; i < oldnrows; i++)
+ memcpy(&new_data->rows[i-nrows], &oldrows[values[i].tupno], sizeof(HeapTuple));
+
+ /* update ndistinct values for the buckets (total and per dimension) */
+ update_bucket_ndistinct(bucket, attrs, stats);
+ update_bucket_ndistinct(new_bucket, attrs, stats);
+
+ /*
+ * TODO We don't need to do this for the dimension we used for split,
+ * because we know how many distinct values went to each partition.
+ */
+ for (i = 0; i < numattrs; i++)
+ {
+ update_dimension_ndistinct(bucket, i, attrs, stats, false);
+ update_dimension_ndistinct(new_bucket, i, attrs, stats, false);
+ }
+
+ pfree(oldrows);
+ pfree(values);
+
+ return new_bucket;
+}
+
+/*
+ * Copy a histogram bucket. The copy does not include the build-time
+ * data, i.e. sampled rows etc.
+ */
+static MVBucket
+copy_mv_bucket(MVBucket bucket, uint32 ndimensions)
+{
+ /* TODO allocate as a single piece (including all the fields) */
+ MVBucket new_bucket = (MVBucket)palloc0(sizeof(MVBucketData));
+ HistogramBuild data = (HistogramBuild)palloc0(sizeof(HistogramBuildData));
+
+ /* Copy only the attributes that will stay the same after the split, and
+ * we'll recompute the rest after the split. */
+
+ /* allocate the per-dimension arrays */
+ new_bucket->nullsonly = (bool*)palloc0(ndimensions * sizeof(bool));
+
+ /* inclusiveness boundaries - lower/upper bounds */
+ new_bucket->min_inclusive = (bool*)palloc0(ndimensions * sizeof(bool));
+ new_bucket->max_inclusive = (bool*)palloc0(ndimensions * sizeof(bool));
+
+ /* lower/upper boundaries */
+ new_bucket->min = (Datum*)palloc0(ndimensions * sizeof(Datum));
+ new_bucket->max = (Datum*)palloc0(ndimensions * sizeof(Datum));
+
+ /* copy data */
+ memcpy(new_bucket->nullsonly, bucket->nullsonly, ndimensions * sizeof(bool));
+
+ memcpy(new_bucket->min_inclusive, bucket->min_inclusive, ndimensions*sizeof(bool));
+ memcpy(new_bucket->min, bucket->min, ndimensions*sizeof(Datum));
+
+ memcpy(new_bucket->max_inclusive, bucket->max_inclusive, ndimensions*sizeof(bool));
+ memcpy(new_bucket->max, bucket->max, ndimensions*sizeof(Datum));
+
+ /* allocate and copy the interesting part of the build data */
+ data->ndistincts = (uint32*)palloc0(ndimensions * sizeof(uint32));
+
+ new_bucket->build_data = data;
+
+ return new_bucket;
+}
+
+/*
+ * Counts the number of distinct values in the bucket. This just copies
+ * the Datum values into a simple array, and sorts them using memcmp-based
+ * comparator. That means it only works for pass-by-value data types
+ * (assuming they don't use collations etc.)
+ *
+ * TODO This might evaluate and store the distinct counts for all
+ * possible attribute combinations. The assumption is this might be
+ * useful for estimating things like GROUP BY cardinalities (e.g.
+ * in cases when some buckets contain a lot of low-frequency
+ * combinations, and other buckets contain few high-frequency ones).
+ *
+ * But it's unclear whether it's worth the price. Computing this
+ * is actually quite cheap, because it may be evaluated at the very
+ * end, when the buckets are rather small (so sorting it in 2^N ways
+ * is not a big deal). Assuming the partitioning algorithm does not
+ * use these values to do the decisions, of course (the current
+ * algorithm does not).
+ *
+ * The overhead with storing, fetching and parsing the data is more
+ * concerning - adding 2^N values per bucket (even if it's just
+ * a 1B or 2B value) would significantly bloat the histogram, and
+ * thus the impact on optimizer. Which is not really desirable.
+ *
+ * TODO This only updates the ndistinct for the sample (or bucket), but
+ * we eventually need an estimate of the total number of distinct
+ * values in the dataset. It's possible to either use the current
+ * 1D approach (i.e., if it's more than 10% of the sample, assume
+ * it's proportional to the number of rows). Or it's possible to
+ * implement the estimator suggested in the article, supposedly
+ * giving 'optimal' estimates (w.r.t. probability of error).
+ */
+static void
+update_bucket_ndistinct(MVBucket bucket, int2vector *attrs, VacAttrStats ** stats)
+{
+ int i, j;
+ int numattrs = attrs->dim1;
+
+ HistogramBuild data = (HistogramBuild)bucket->build_data;
+ int numrows = data->numrows;
+
+ MultiSortSupport mss = multi_sort_init(numattrs);
+
+ /*
+ * We could collect this while walking through all the attributes
+ * above (this way we have to call heap_getattr twice).
+ */
+ SortItem *items = (SortItem*)palloc0(numrows * sizeof(SortItem));
+ Datum *values = (Datum*)palloc0(numrows * sizeof(Datum) * numattrs);
+ bool *isnull = (bool*)palloc0(numrows * sizeof(bool) * numattrs);
+
+ for (i = 0; i < numrows; i++)
+ {
+ items[i].values = &values[i * numattrs];
+ items[i].isnull = &isnull[i * numattrs];
+ }
+
+ /* prepare the sort function for the first dimension */
+ for (i = 0; i < numattrs; i++)
+ multi_sort_add_dimension(mss, i, i, stats);
+
+ /* collect the values */
+ for (i = 0; i < numrows; i++)
+ for (j = 0; j < numattrs; j++)
+ items[i].values[j]
+ = heap_getattr(data->rows[i], attrs->values[j],
+ stats[j]->tupDesc, &items[i].isnull[j]);
+
+ qsort_arg((void *) items, numrows, sizeof(SortItem),
+ multi_sort_compare, mss);
+
+ data->ndistinct = 1;
+
+ for (i = 1; i < numrows; i++)
+ if (multi_sort_compare(&items[i], &items[i-1], mss) != 0)
+ data->ndistinct += 1;
+
+ pfree(items);
+ pfree(values);
+ pfree(isnull);
+}
+
+/*
+ * Count distinct values per bucket dimension.
+ */
+static void
+update_dimension_ndistinct(MVBucket bucket, int dimension, int2vector *attrs,
+ VacAttrStats ** stats, bool update_boundaries)
+{
+ int j;
+ int nvalues = 0;
+ bool isNull;
+ HistogramBuild data = (HistogramBuild)bucket->build_data;
+ Datum * values = (Datum*)palloc0(data->numrows * sizeof(Datum));
+ SortSupportData ssup;
+
+ StdAnalyzeData * mystats = (StdAnalyzeData *) stats[dimension]->extra_data;
+
+ /* we may already know this is a NULL-only dimension */
+ if (bucket->nullsonly[dimension])
+ data->ndistincts[dimension] = 1;
+
+ memset(&ssup, 0, sizeof(ssup));
+ ssup.ssup_cxt = CurrentMemoryContext;
+
+ /* We always use the default collation for statistics */
+ ssup.ssup_collation = DEFAULT_COLLATION_OID;
+ ssup.ssup_nulls_first = false;
+
+ PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);
+
+ for (j = 0; j < data->numrows; j++)
+ {
+ values[nvalues] = heap_getattr(data->rows[j], attrs->values[dimension],
+ stats[dimension]->tupDesc, &isNull);
+
+ /* ignore NULL values */
+ if (! isNull)
+ nvalues++;
+ }
+
+ /* there's always at least 1 distinct value (may be NULL) */
+ data->ndistincts[dimension] = 1;
+
+ /* if there are only NULL values in the column, mark it so and continue
+ * with the next one */
+ if (nvalues == 0)
+ {
+ pfree(values);
+ bucket->nullsonly[dimension] = true;
+ return;
+ }
+
+ /* sort the array (pass-by-value datum */
+ qsort_arg((void *) values, nvalues, sizeof(Datum),
+ compare_scalars_simple, (void *) &ssup);
+
+ /*
+ * Update min/max boundaries to the smallest bounding box. Generally, this
+ * needs to be done only when constructing the initial bucket.
+ */
+ if (update_boundaries)
+ {
+ /* store the min/max values */
+ bucket->min[dimension] = values[0];
+ bucket->min_inclusive[dimension] = true;
+
+ bucket->max[dimension] = values[nvalues-1];
+ bucket->max_inclusive[dimension] = true;
+ }
+
+ /*
+ * Walk through the array and count distinct values by comparing
+ * succeeding values.
+ *
+ * FIXME This only works for pass-by-value types (i.e. not VARCHARs
+ * etc.). Although thanks to the deduplication it might work
+ * even for those types (equal values will get the same item
+ * in the deduplicated array).
+ */
+ for (j = 1; j < nvalues; j++) {
+ if (values[j] != values[j-1])
+ data->ndistincts[dimension] += 1;
+ }
+
+ pfree(values);
+}
+
+/*
+ * A properly built histogram must not contain buckets mixing NULL and
+ * non-NULL values in a single dimension. Each dimension may either be
+ * marked as 'nulls only', and thus containing only NULL values, or
+ * it must not contain any NULL values.
+ *
+ * Therefore, if the sample contains NULL values in any of the columns,
+ * it's necessary to build those NULL-buckets. This is done in an
+ * iterative way using this algorithm, operating on a single bucket:
+ *
+ * (1) Check that all dimensions are well-formed (not mixing NULL
+ * and non-NULL values).
+ *
+ * (2) If all dimensions are well-formed, terminate.
+ *
+ * (3) If the dimension contains only NULL values, but is not
+ * marked as NULL-only, mark it as NULL-only and run the
+ * algorithm again (on this bucket).
+ *
+ * (4) If the dimension mixes NULL and non-NULL values, split the
+ * bucket into two parts - one with NULL values, one with
+ * non-NULL values (replacing the current one). Then run
+ * the algorithm on both buckets.
+ *
+ * This is executed in a recursive manner, but the number of executions
+ * should be quite low - limited by the number of NULL-buckets. Also,
+ * in each branch the number of nested calls is limited by the number
+ * of dimensions (attributes) of the histogram.
+ *
+ * At the end, there should be buckets with no mixed dimensions. The
+ * number of buckets produced by this algorithm is rather limited - with
+ * N dimensions, there may be only 2^N such buckets (each dimension may
+ * be either NULL or non-NULL). So with 8 dimensions (current value of
+ * MVSTATS_MAX_DIMENSIONS) there may be only 256 such buckets.
+ *
+ * After this, a 'regular' bucket-split algorithm shall run, further
+ * optimizing the histogram.
+ */
+static void
+create_null_buckets(MVHistogram histogram, int bucket_idx,
+ int2vector *attrs, VacAttrStats ** stats)
+{
+ int i, j;
+ int null_dim = -1;
+ int null_count = 0;
+ bool null_found = false;
+ MVBucket bucket, null_bucket;
+ int null_idx, curr_idx;
+ HistogramBuild data, null_data;
+
+ /* remember original values from the bucket */
+ int numrows;
+ HeapTuple *oldrows = NULL;
+
+ Assert(bucket_idx < histogram->nbuckets);
+ Assert(histogram->ndimensions == attrs->dim1);
+
+ bucket = histogram->buckets[bucket_idx];
+ data = (HistogramBuild)bucket->build_data;
+
+ numrows = data->numrows;
+ oldrows = data->rows;
+
+ /*
+ * Walk through all rows / dimensions, and stop once we find NULL
+ * in a dimension not yet marked as NULL-only.
+ */
+ for (i = 0; i < data->numrows; i++)
+ {
+ /*
+ * FIXME We don't need to start from the first attribute
+ * here - we can start from the last known dimension.
+ */
+ for (j = 0; j < histogram->ndimensions; j++)
+ {
+ /* Is this a NULL-only dimension? If yes, skip. */
+ if (bucket->nullsonly[j])
+ continue;
+
+ /* found a NULL in that dimension? */
+ if (heap_attisnull(data->rows[i], attrs->values[j]))
+ {
+ null_found = true;
+ null_dim = j;
+ break;
+ }
+ }
+
+ /* terminate if we found attribute with NULL values */
+ if (null_found)
+ break;
+ }
+
+ /* no regular dimension contains NULL values => we're done */
+ if (! null_found)
+ return;
+
+ /* walk through the rows again, count NULL values in 'null_dim' */
+ for (i = 0; i < data->numrows; i++)
+ {
+ if (heap_attisnull(data->rows[i], attrs->values[null_dim]))
+ null_count += 1;
+ }
+
+ Assert(null_count <= data->numrows);
+
+ /*
+ * If (null_count == numrows) the dimension already is NULL-only,
+ * but is not yet marked like that. It's enough to mark it and
+ * repeat the process recursively (until we run out of dimensions).
+ */
+ if (null_count == data->numrows)
+ {
+ bucket->nullsonly[null_dim] = true;
+ create_null_buckets(histogram, bucket_idx, attrs, stats);
+ return;
+ }
+
+ /*
+ * We have to split the bucket into two - one with NULL values in
+ * the dimension, one with non-NULL values. We don't need to sort
+ * the data or anything, but otherwise it's similar to what's done
+ * in partition_bucket().
+ */
+
+ /* create bucket with NULL-only dimension 'dim' */
+ null_bucket = copy_mv_bucket(bucket, histogram->ndimensions);
+ null_data = (HistogramBuild)null_bucket->build_data;
+
+ /* remember the current array info */
+ oldrows = data->rows;
+ numrows = data->numrows;
+
+ /* we'll keep non-NULL values in the current bucket */
+ data->numrows = (numrows - null_count);
+ data->rows
+ = (HeapTuple*)palloc0(data->numrows * sizeof(HeapTuple));
+
+ /* and the NULL values will go to the new one */
+ null_data->numrows = null_count;
+ null_data->rows
+ = (HeapTuple*)palloc0(null_data->numrows * sizeof(HeapTuple));
+
+ /* mark the dimension as NULL-only (in the new bucket) */
+ null_bucket->nullsonly[null_dim] = true;
+
+ /* walk through the sample rows and distribute them accordingly */
+ null_idx = 0;
+ curr_idx = 0;
+ for (i = 0; i < numrows; i++)
+ {
+ if (heap_attisnull(oldrows[i], attrs->values[null_dim]))
+ /* NULL => copy to the new bucket */
+ memcpy(&null_data->rows[null_idx++], &oldrows[i],
+ sizeof(HeapTuple));
+ else
+ memcpy(&data->rows[curr_idx++], &oldrows[i],
+ sizeof(HeapTuple));
+ }
+
+ /* update ndistinct values for the buckets (total and per dimension) */
+ update_bucket_ndistinct(bucket, attrs, stats);
+ update_bucket_ndistinct(null_bucket, attrs, stats);
+
+ /*
+ * TODO We don't need to do this for the dimension we used for split,
+ * because we know how many distinct values went to each
+ * bucket (NULL is not a value, so 0, and the other bucket got
+ * all the ndistinct values).
+ */
+ for (i = 0; i < histogram->ndimensions; i++)
+ {
+ update_dimension_ndistinct(bucket, i, attrs, stats, false);
+ update_dimension_ndistinct(null_bucket, i, attrs, stats, false);
+ }
+
+ pfree(oldrows);
+
+ /* add the NULL bucket to the histogram */
+ histogram->buckets[histogram->nbuckets++] = null_bucket;
+
+ /*
+ * And now run the function recursively on both buckets (the new
+ * one first, because the call may change number of buckets, and
+ * it's used as an index).
+ */
+ create_null_buckets(histogram, (histogram->nbuckets-1), attrs, stats);
+ create_null_buckets(histogram, bucket_idx, attrs, stats);
+
+}
+
+/*
+ * 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);
+}
+
+/*
+ * SRF with details about buckets of a histogram:
+ *
+ * - bucket ID (0...nbuckets)
+ * - min values (string array)
+ * - max values (string array)
+ * - nulls only (boolean array)
+ * - min inclusive flags (boolean array)
+ * - max inclusive flags (boolean array)
+ * - frequency (double precision)
+ *
+ * The input is the OID of the statistics, and there are no rows
+ * returned if the statistics contains no histogram (or if there's no
+ * statistics for the OID).
+ *
+ * The second parameter (type) determines what values will be returned
+ * in the (minvals,maxvals). There are three possible values:
+ *
+ * 0 (actual values)
+ * -----------------
+ * - prints actual values
+ * - using the output function of the data type (as string)
+ * - handy for investigating the histogram
+ *
+ * 1 (distinct index)
+ * ------------------
+ * - prints index of the distinct value (into the serialized array)
+ * - makes it easier to spot neighbor buckets, etc.
+ * - handy for plotting the histogram
+ *
+ * 2 (normalized distinct index)
+ * -----------------------------
+ * - prints index of the distinct value, but normalized into [0,1]
+ * - similar to 1, but shows how 'long' the bucket range is
+ * - handy for plotting the histogram
+ *
+ * When plotting the histogram, be careful as the (1) and (2) options
+ * skew the lengths by distributing the distinct values uniformly. For
+ * data types without a clear meaning of 'distance' (e.g. strings) that
+ * is not a big deal, but for numbers it may be confusing.
+ */
+PG_FUNCTION_INFO_V1(pg_mv_histogram_buckets);
+
+Datum
+pg_mv_histogram_buckets(PG_FUNCTION_ARGS)
+{
+ FuncCallContext *funcctx;
+ int call_cntr;
+ int max_calls;
+ TupleDesc tupdesc;
+ AttInMetadata *attinmeta;
+
+ Oid mvoid = PG_GETARG_OID(0);
+ int otype = PG_GETARG_INT32(1);
+
+ if ((otype < 0) || (otype > 2))
+ elog(ERROR, "invalid output type specified");
+
+ /* stuff done only on the first call of the function */
+ if (SRF_IS_FIRSTCALL())
+ {
+ MemoryContext oldcontext;
+ MVSerializedHistogram histogram;
+
+ /* create a function context for cross-call persistence */
+ funcctx = SRF_FIRSTCALL_INIT();
+
+ /* switch to memory context appropriate for multiple function calls */
+ oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
+
+ histogram = load_mv_histogram(mvoid);
+
+ funcctx->user_fctx = histogram;
+
+ /* total number of tuples to be returned */
+ funcctx->max_calls = 0;
+ if (funcctx->user_fctx != NULL)
+ funcctx->max_calls = histogram->nbuckets;
+
+ /* Build a tuple descriptor for our result type */
+ if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("function returning record called in context "
+ "that cannot accept type record")));
+
+ /*
+ * generate attribute metadata needed later to produce tuples
+ * from raw C strings
+ */
+ attinmeta = TupleDescGetAttInMetadata(tupdesc);
+ funcctx->attinmeta = attinmeta;
+
+ MemoryContextSwitchTo(oldcontext);
+ }
+
+ /* stuff done on every call of the function */
+ funcctx = SRF_PERCALL_SETUP();
+
+ call_cntr = funcctx->call_cntr;
+ max_calls = funcctx->max_calls;
+ attinmeta = funcctx->attinmeta;
+
+ if (call_cntr < max_calls) /* do when there is more left to send */
+ {
+ char **values;
+ HeapTuple tuple;
+ Datum result;
+ int2vector *stakeys;
+ Oid relid;
+ double bucket_size = 1.0;
+
+ char *buff = palloc0(1024);
+ char *format;
+
+ int i;
+
+ Oid *outfuncs;
+ FmgrInfo *fmgrinfo;
+
+ MVSerializedHistogram histogram;
+ MVSerializedBucket bucket;
+
+ histogram = (MVSerializedHistogram)funcctx->user_fctx;
+
+ Assert(call_cntr < histogram->nbuckets);
+
+ bucket = histogram->buckets[call_cntr];
+
+ stakeys = find_mv_attnums(mvoid, &relid);
+
+ /*
+ * Prepare a values array for building the returned tuple.
+ * This should be an array of C strings which will
+ * be processed later by the type input functions.
+ */
+ values = (char **) palloc(9 * sizeof(char *));
+
+ values[0] = (char *) palloc(64 * sizeof(char));
+
+ /* arrays */
+ values[1] = (char *) palloc0(1024 * sizeof(char));
+ values[2] = (char *) palloc0(1024 * sizeof(char));
+ values[3] = (char *) palloc0(1024 * sizeof(char));
+ values[4] = (char *) palloc0(1024 * sizeof(char));
+ values[5] = (char *) palloc0(1024 * sizeof(char));
+
+ values[6] = (char *) palloc(64 * sizeof(char));
+ values[7] = (char *) palloc(64 * sizeof(char));
+ values[8] = (char *) palloc(64 * sizeof(char));
+
+ /* we need to do this only when printing the actual values */
+ outfuncs = (Oid*)palloc0(sizeof(Oid) * histogram->ndimensions);
+ fmgrinfo = (FmgrInfo*)palloc0(sizeof(FmgrInfo) * histogram->ndimensions);
+
+ for (i = 0; i < histogram->ndimensions; i++)
+ {
+ bool isvarlena;
+
+ getTypeOutputInfo(get_atttype(relid, stakeys->values[i]),
+ &outfuncs[i], &isvarlena);
+
+ fmgr_info(outfuncs[i], &fmgrinfo[i]);
+ }
+
+ snprintf(values[0], 64, "%d", call_cntr); /* bucket ID */
+
+ /*
+ * currently we only print array of indexes, but the deduplicated
+ * values should be sorted, so this is actually quite useful
+ *
+ * TODO print the actual min/max values, using the output
+ * function of the attribute type
+ */
+
+ for (i = 0; i < histogram->ndimensions; i++)
+ {
+ bucket_size *= (bucket->max[i] - bucket->min[i]) * 1.0
+ / (histogram->nvalues[i]-1);
+
+ /* print the actual values, i.e. use output function etc. */
+ if (otype == 0)
+ {
+ Datum minval, maxval;
+ Datum minout, maxout;
+
+ format = "%s, %s";
+ if (i == 0)
+ format = "{%s%s";
+ else if (i == histogram->ndimensions-1)
+ format = "%s, %s}";
+
+ minval = histogram->values[i][bucket->min[i]];
+ minout = FunctionCall1(&fmgrinfo[i], minval);
+
+ maxval = histogram->values[i][bucket->max[i]];
+ maxout = FunctionCall1(&fmgrinfo[i], maxval);
+
+ // snprintf(buff, 1024, format, values[1], bucket->min[i]);
+ snprintf(buff, 1024, format, values[1], DatumGetPointer(minout));
+ strncpy(values[1], buff, 1023);
+ buff[0] = '\0';
+
+ // snprintf(buff, 1024, format, values[2], bucket->max[i]);
+ snprintf(buff, 1024, format, values[2], DatumGetPointer(maxout));
+ strncpy(values[2], buff, 1023);
+ buff[0] = '\0';
+ }
+ else if (otype == 1)
+ {
+ format = "%s, %d";
+ if (i == 0)
+ format = "{%s%d";
+ else if (i == histogram->ndimensions-1)
+ format = "%s, %d}";
+
+ snprintf(buff, 1024, format, values[1], bucket->min[i]);
+ strncpy(values[1], buff, 1023);
+ buff[0] = '\0';
+
+ snprintf(buff, 1024, format, values[2], bucket->max[i]);
+ strncpy(values[2], buff, 1023);
+ buff[0] = '\0';
+ }
+ else
+ {
+ format = "%s, %f";
+ if (i == 0)
+ format = "{%s%f";
+ else if (i == histogram->ndimensions-1)
+ format = "%s, %f}";
+
+ snprintf(buff, 1024, format, values[1],
+ bucket->min[i] * 1.0 / (histogram->nvalues[i]-1));
+ strncpy(values[1], buff, 1023);
+ buff[0] = '\0';
+
+ snprintf(buff, 1024, format, values[2],
+ bucket->max[i] * 1.0 / (histogram->nvalues[i]-1));
+ strncpy(values[2], buff, 1023);
+ buff[0] = '\0';
+ }
+
+ format = "%s, %s";
+ if (i == 0)
+ format = "{%s%s";
+ else if (i == histogram->ndimensions-1)
+ format = "%s, %s}";
+
+ snprintf(buff, 1024, format, values[3], bucket->nullsonly[i] ? "t" : "f");
+ strncpy(values[3], buff, 1023);
+ buff[0] = '\0';
+
+ snprintf(buff, 1024, format, values[4], bucket->min_inclusive[i] ? "t" : "f");
+ strncpy(values[4], buff, 1023);
+ buff[0] = '\0';
+
+ snprintf(buff, 1024, format, values[5], bucket->max_inclusive[i] ? "t" : "f");
+ strncpy(values[5], buff, 1023);
+ buff[0] = '\0';
+ }
+
+ snprintf(values[6], 64, "%f", bucket->ntuples); /* frequency */
+ snprintf(values[7], 64, "%f", bucket->ntuples / bucket_size); /* density */
+ snprintf(values[8], 64, "%f", bucket_size); /* bucket_size */
+
+ /* build a tuple */
+ tuple = BuildTupleFromCStrings(attinmeta, values);
+
+ /* make the tuple into a datum */
+ result = HeapTupleGetDatum(tuple);
+
+ /* clean up (this is not really necessary) */
+ pfree(values[0]);
+ pfree(values[1]);
+ pfree(values[2]);
+ pfree(values[3]);
+ pfree(values[4]);
+ pfree(values[5]);
+ pfree(values[6]);
+
+ pfree(values);
+
+ SRF_RETURN_NEXT(funcctx, result);
+ }
+ else /* do when there is no more left */
+ {
+ SRF_RETURN_DONE(funcctx);
+ }
+}
+
+#ifdef DEBUG_MVHIST
+/*
+ * prints debugging info about matched histogram buckets (full/partial)
+ *
+ * XXX Currently works only for INT data type.
+ */
+void
+debug_histogram_matches(MVSerializedHistogram mvhist, char *matches)
+{
+ int i, j;
+
+ float ffull = 0, fpartial = 0;
+ int nfull = 0, npartial = 0;
+
+ for (i = 0; i < mvhist->nbuckets; i++)
+ {
+ MVSerializedBucket bucket = mvhist->buckets[i];
+
+ char ranges[1024];
+
+ if (! matches[i])
+ continue;
+
+ /* increment the counters */
+ nfull += (matches[i] == MVSTATS_MATCH_FULL) ? 1 : 0;
+ npartial += (matches[i] == MVSTATS_MATCH_PARTIAL) ? 1 : 0;
+
+ /* and also update the frequencies */
+ ffull += (matches[i] == MVSTATS_MATCH_FULL) ? bucket->ntuples : 0;
+ fpartial += (matches[i] == MVSTATS_MATCH_PARTIAL) ? bucket->ntuples : 0;
+
+ memset(ranges, 0, sizeof(ranges));
+
+ /* build ranges for all the dimentions */
+ for (j = 0; j < mvhist->ndimensions; j++)
+ {
+ sprintf(ranges, "%s [%d %d]", ranges,
+ DatumGetInt32(mvhist->values[j][bucket->min[j]]),
+ DatumGetInt32(mvhist->values[j][bucket->max[j]]));
+ }
+
+ elog(WARNING, "bucket %d %s => %d [%f]", i, ranges, matches[i], bucket->ntuples);
+ }
+
+ elog(WARNING, "full=%f partial=%f (%f)", ffull, fpartial, (ffull + 0.5 * fpartial));
+}
+#endif
diff --git a/src/bin/psql/describe.c b/src/bin/psql/describe.c
index 6339631..3543239 100644
--- a/src/bin/psql/describe.c
+++ b/src/bin/psql/describe.c
@@ -2109,9 +2109,9 @@ describeOneTableDetails(const char *schemaname,
{
printfPQExpBuffer(&buf,
"SELECT oid, stanamespace::regnamespace AS nsp, staname, stakeys,\n"
- " deps_enabled, mcv_enabled,\n"
- " deps_built, mcv_built,\n"
- " mcv_max_items,\n"
+ " deps_enabled, mcv_enabled, hist_enabled,\n"
+ " deps_built, mcv_built, hist_built,\n"
+ " mcv_max_items, hist_max_buckets,\n"
" (SELECT string_agg(attname::text,', ')\n"
" FROM ((SELECT unnest(stakeys) AS attnum) s\n"
" JOIN pg_attribute a ON (starelid = a.attrelid and a.attnum = s.attnum))) AS attnums\n"
@@ -2154,8 +2154,17 @@ describeOneTableDetails(const char *schemaname,
first = false;
}
+ if (!strcmp(PQgetvalue(result, i, 6), "t"))
+ {
+ if (! first)
+ appendPQExpBuffer(&buf, ", histogram");
+ else
+ appendPQExpBuffer(&buf, "(histogram");
+ first = false;
+ }
+
appendPQExpBuffer(&buf, ") ON (%s)",
- PQgetvalue(result, i, 9));
+ PQgetvalue(result, i, 12));
printTableAddFooter(&cont, buf.data);
}
diff --git a/src/include/catalog/pg_mv_statistic.h b/src/include/catalog/pg_mv_statistic.h
index fd7107d..a5945af 100644
--- a/src/include/catalog/pg_mv_statistic.h
+++ b/src/include/catalog/pg_mv_statistic.h
@@ -38,13 +38,16 @@ CATALOG(pg_mv_statistic,3381)
/* statistics requested to build */
bool deps_enabled; /* analyze dependencies? */
bool mcv_enabled; /* build MCV list? */
+ bool hist_enabled; /* build histogram? */
- /* MCV size */
+ /* histogram / MCV size */
int32 mcv_max_items; /* max MCV items */
+ int32 hist_max_buckets; /* max histogram buckets */
/* statistics that are available (if requested) */
bool deps_built; /* dependencies were built */
bool mcv_built; /* MCV list was built */
+ bool hist_built; /* histogram was built */
/* variable-length fields start here, but we allow direct access to stakeys */
int2vector stakeys; /* array of column keys */
@@ -52,6 +55,7 @@ CATALOG(pg_mv_statistic,3381)
#ifdef CATALOG_VARLEN
bytea stadeps; /* dependencies (serialized) */
bytea stamcv; /* MCV list (serialized) */
+ bytea stahist; /* MV histogram (serialized) */
#endif
} FormData_pg_mv_statistic;
@@ -67,17 +71,21 @@ typedef FormData_pg_mv_statistic *Form_pg_mv_statistic;
* compiler constants for pg_mv_statistic
* ----------------
*/
-#define Natts_pg_mv_statistic 11
+#define Natts_pg_mv_statistic 15
#define Anum_pg_mv_statistic_starelid 1
#define Anum_pg_mv_statistic_staname 2
#define Anum_pg_mv_statistic_stanamespace 3
#define Anum_pg_mv_statistic_deps_enabled 4
#define Anum_pg_mv_statistic_mcv_enabled 5
-#define Anum_pg_mv_statistic_mcv_max_items 6
-#define Anum_pg_mv_statistic_deps_built 7
-#define Anum_pg_mv_statistic_mcv_built 8
-#define Anum_pg_mv_statistic_stakeys 9
-#define Anum_pg_mv_statistic_stadeps 10
-#define Anum_pg_mv_statistic_stamcv 11
+#define Anum_pg_mv_statistic_hist_enabled 6
+#define Anum_pg_mv_statistic_mcv_max_items 7
+#define Anum_pg_mv_statistic_hist_max_buckets 8
+#define Anum_pg_mv_statistic_deps_built 9
+#define Anum_pg_mv_statistic_mcv_built 10
+#define Anum_pg_mv_statistic_hist_built 11
+#define Anum_pg_mv_statistic_stakeys 12
+#define Anum_pg_mv_statistic_stadeps 13
+#define Anum_pg_mv_statistic_stamcv 14
+#define Anum_pg_mv_statistic_stahist 15
#endif /* PG_MV_STATISTIC_H */
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 66b4bcd..7e915bd 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -2674,6 +2674,10 @@ DATA(insert OID = 3376 ( pg_mv_stats_mcvlist_info PGNSP PGUID 12 1 0 0 0 f f f
DESCR("multi-variate statistics: MCV list info");
DATA(insert OID = 3373 ( pg_mv_mcv_items PGNSP PGUID 12 1 1000 0 0 f f f f t t i s 1 0 2249 "26" "{26,23,1009,1000,701}" "{i,o,o,o,o}" "{oid,index,values,nulls,frequency}" _null_ _null_ pg_mv_mcv_items _null_ _null_ _null_ ));
DESCR("details about MCV list items");
+DATA(insert OID = 3375 ( pg_mv_stats_histogram_info PGNSP PGUID 12 1 0 0 0 f f f f t f i s 1 0 25 "17" _null_ _null_ _null_ _null_ _null_ pg_mv_stats_histogram_info _null_ _null_ _null_ ));
+DESCR("multi-variate statistics: histogram info");
+DATA(insert OID = 3374 ( pg_mv_histogram_buckets PGNSP PGUID 12 1 1000 0 0 f f f f t t i s 2 0 2249 "26 23" "{26,23,23,1009,1009,1000,1000,1000,701,701,701}" "{i,i,o,o,o,o,o,o,o,o,o}" "{oid,otype,index,minvals,maxvals,nullsonly,mininclusive,maxinclusive,frequency,density,bucket_size}" _null_ _null_ pg_mv_histogram_buckets _null_ _null_ _null_ ));
+DESCR("details about histogram buckets");
DATA(insert OID = 1928 ( pg_stat_get_numscans PGNSP PGUID 12 1 0 0 0 f f f f t f s r 1 0 20 "26" _null_ _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/nodes/relation.h b/src/include/nodes/relation.h
index 5ae6b3c..46bece6 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -620,10 +620,12 @@ typedef struct MVStatisticInfo
/* enabled statistics */
bool deps_enabled; /* functional dependencies enabled */
bool mcv_enabled; /* MCV list enabled */
+ bool hist_enabled; /* histogram enabled */
/* built/available statistics */
bool deps_built; /* functional dependencies built */
bool mcv_built; /* MCV list built */
+ bool hist_built; /* histogram built */
/* columns in the statistics (attnums) */
int2vector *stakeys; /* attnums of the columns covered */
diff --git a/src/include/utils/mvstats.h b/src/include/utils/mvstats.h
index 4535db7..f05a517 100644
--- a/src/include/utils/mvstats.h
+++ b/src/include/utils/mvstats.h
@@ -92,6 +92,123 @@ typedef MCVListData *MCVList;
#define MVSTAT_MCVLIST_MAX_ITEMS 8192 /* max items in MCV list */
/*
+ * Multivariate histograms
+ */
+typedef struct MVBucketData {
+
+ /* Frequencies of this bucket. */
+ float ntuples; /* frequency of tuples tuples */
+
+ /*
+ * Information about dimensions being NULL-only. Not yet used.
+ */
+ bool *nullsonly;
+
+ /* lower boundaries - values and information about the inequalities */
+ Datum *min;
+ bool *min_inclusive;
+
+ /* upper boundaries - values and information about the inequalities */
+ Datum *max;
+ bool *max_inclusive;
+
+ /* used when building the histogram (not serialized/deserialized) */
+ void *build_data;
+
+} MVBucketData;
+
+typedef MVBucketData *MVBucket;
+
+
+typedef struct MVHistogramData {
+
+ uint32 magic; /* magic constant marker */
+ uint32 type; /* type of histogram (BASIC) */
+ uint32 nbuckets; /* number of buckets (buckets array) */
+ uint32 ndimensions; /* number of dimensions */
+
+ MVBucket *buckets; /* array of buckets */
+
+} MVHistogramData;
+
+typedef MVHistogramData *MVHistogram;
+
+/*
+ * Histogram in a partially serialized form, with deduplicated boundary
+ * values etc.
+ *
+ * TODO add more detailed description here
+ */
+
+typedef struct MVSerializedBucketData {
+
+ /* Frequencies of this bucket. */
+ float ntuples; /* frequency of tuples tuples */
+
+ /*
+ * Information about dimensions being NULL-only. Not yet used.
+ */
+ bool *nullsonly;
+
+ /* lower boundaries - values and information about the inequalities */
+ uint16 *min;
+ bool *min_inclusive;
+
+ /* indexes of upper boundaries - values and information about the
+ * inequalities (exclusive vs. inclusive) */
+ uint16 *max;
+ bool *max_inclusive;
+
+} MVSerializedBucketData;
+
+typedef MVSerializedBucketData *MVSerializedBucket;
+
+typedef struct MVSerializedHistogramData {
+
+ uint32 magic; /* magic constant marker */
+ uint32 type; /* type of histogram (BASIC) */
+ uint32 nbuckets; /* number of buckets (buckets array) */
+ uint32 ndimensions; /* number of dimensions */
+
+ /*
+ * keep this the same with MVHistogramData, because of
+ * deserialization (same offset)
+ */
+ MVSerializedBucket *buckets; /* array of buckets */
+
+ /*
+ * serialized boundary values, one array per dimension, deduplicated
+ * (the min/max indexes point into these arrays)
+ */
+ int *nvalues;
+ Datum **values;
+
+} MVSerializedHistogramData;
+
+typedef MVSerializedHistogramData *MVSerializedHistogram;
+
+
+/* used to flag stats serialized to bytea */
+#define MVSTAT_HIST_MAGIC 0x7F8C5670 /* marks serialized bytea */
+#define MVSTAT_HIST_TYPE_BASIC 1 /* basic histogram type */
+
+/*
+ * Limits used for max_buckets option, i.e. we're always guaranteed
+ * to have space for at least MVSTAT_HIST_MIN_BUCKETS, and we cannot
+ * have more than MVSTAT_HIST_MAX_BUCKETS buckets.
+ *
+ * This is just a boundary for the 'max' threshold - the actual
+ * histogram may use less buckets than MVSTAT_HIST_MAX_BUCKETS.
+ *
+ * TODO The MVSTAT_HIST_MIN_BUCKETS should be related to the number of
+ * attributes (MVSTATS_MAX_DIMENSIONS) because of NULL-buckets.
+ * There should be at least 2^N buckets, otherwise we may be unable
+ * to build the NULL buckets.
+ */
+#define MVSTAT_HIST_MIN_BUCKETS 128 /* min number of buckets */
+#define MVSTAT_HIST_MAX_BUCKETS 16384 /* max number of buckets */
+
+/*
* 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).
@@ -99,20 +216,25 @@ typedef MCVListData *MCVList;
MVDependencies load_mv_dependencies(Oid mvoid);
MCVList load_mv_mcvlist(Oid mvoid);
+MVSerializedHistogram load_mv_histogram(Oid mvoid);
bytea * serialize_mv_dependencies(MVDependencies dependencies);
bytea * serialize_mv_mcvlist(MCVList mcvlist, int2vector *attrs,
VacAttrStats **stats);
+bytea * serialize_mv_histogram(MVHistogram histogram, int2vector *attrs,
+ VacAttrStats **stats);
/* deserialization of stats (serialization is private to analyze) */
MVDependencies deserialize_mv_dependencies(bytea * data);
MCVList deserialize_mv_mcvlist(bytea * data);
+MVSerializedHistogram deserialize_mv_histogram(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);
+int2vector* find_mv_attnums(Oid mvoid, Oid *relid);
int2vector* find_mv_attnums(Oid mvoid, Oid *relid);
@@ -121,6 +243,8 @@ 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);
extern Datum pg_mv_mcvlist_items(PG_FUNCTION_ARGS);
+extern Datum pg_mv_stats_histogram_info(PG_FUNCTION_ARGS);
+extern Datum pg_mv_histogram_buckets(PG_FUNCTION_ARGS);
MVDependencies
build_mv_dependencies(int numrows, HeapTuple *rows, int2vector *attrs,
@@ -130,10 +254,20 @@ MCVList
build_mv_mcvlist(int numrows, HeapTuple *rows, int2vector *attrs,
VacAttrStats **stats, int *numrows_filtered);
+MVHistogram
+build_mv_histogram(int numrows, HeapTuple *rows, int2vector *attrs,
+ VacAttrStats **stats, int numrows_total);
+
void build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
int natts, VacAttrStats **vacattrstats);
-void update_mv_stats(Oid relid, MVDependencies dependencies, MCVList mcvlist,
+void update_mv_stats(Oid relid, MVDependencies dependencies,
+ MCVList mcvlist, MVHistogram histogram,
int2vector *attrs, VacAttrStats **stats);
+#ifdef DEBUG_MVHIST
+extern void debug_histogram_matches(MVSerializedHistogram mvhist, char *matches);
+#endif
+
+
#endif
diff --git a/src/test/regress/expected/mv_histogram.out b/src/test/regress/expected/mv_histogram.out
new file mode 100644
index 0000000..a34edb8
--- /dev/null
+++ b/src/test/regress/expected/mv_histogram.out
@@ -0,0 +1,207 @@
+-- data type passed by value
+CREATE TABLE mv_histogram (
+ a INT,
+ b INT,
+ c INT
+);
+-- unknown column
+CREATE STATISTICS s1 ON mv_histogram (unknown_column) WITH (histogram);
+ERROR: column "unknown_column" referenced in statistics does not exist
+-- single column
+CREATE STATISTICS s1 ON mv_histogram (a) WITH (histogram);
+ERROR: multivariate stats require 2 or more columns
+-- single column, duplicated
+CREATE STATISTICS s1 ON mv_histogram (a, a) WITH (histogram);
+ERROR: duplicate column name in statistics definition
+-- two columns, one duplicated
+CREATE STATISTICS s1 ON mv_histogram (a, a, b) WITH (histogram);
+ERROR: duplicate column name in statistics definition
+-- unknown option
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (unknown_option);
+ERROR: unrecognized STATISTICS option "unknown_option"
+-- missing histogram statistics
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (dependencies, max_buckets=200);
+ERROR: option 'histogram' is required by other options(s)
+-- invalid max_buckets value / too low
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (mcv, max_buckets=10);
+ERROR: minimum number of buckets is 128
+-- invalid max_buckets value / too high
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (mcv, max_buckets=100000);
+ERROR: maximum number of buckets is 16384
+-- correct command
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (histogram);
+-- random data (no functional dependencies)
+INSERT INTO mv_histogram
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+TRUNCATE mv_histogram;
+-- a => b, a => c, b => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+TRUNCATE mv_histogram;
+-- a => b, a => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+TRUNCATE mv_histogram;
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mv_histogram
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX hist_idx ON mv_histogram (a, b);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mv_histogram WHERE a = 10 AND b = 5;
+ QUERY PLAN
+--------------------------------------------
+ Bitmap Heap Scan on mv_histogram
+ Recheck Cond: ((a = 10) AND (b = 5))
+ -> Bitmap Index Scan on hist_idx
+ Index Cond: ((a = 10) AND (b = 5))
+(4 rows)
+
+DROP TABLE mv_histogram;
+-- varlena type (text)
+CREATE TABLE mv_histogram (
+ a TEXT,
+ b TEXT,
+ c TEXT
+);
+CREATE STATISTICS s2 ON mv_histogram (a, b, c) WITH (histogram);
+-- random data (no functional dependencies)
+INSERT INTO mv_histogram
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+TRUNCATE mv_histogram;
+-- a => b, a => c, b => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+TRUNCATE mv_histogram;
+-- a => b, a => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+TRUNCATE mv_histogram;
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mv_histogram
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX hist_idx ON mv_histogram (a, b);
+ANALYZE mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mv_histogram WHERE a = '10' AND b = '5';
+ QUERY PLAN
+------------------------------------------------------------
+ Bitmap Heap Scan on mv_histogram
+ Recheck Cond: ((a = '10'::text) AND (b = '5'::text))
+ -> Bitmap Index Scan on hist_idx
+ Index Cond: ((a = '10'::text) AND (b = '5'::text))
+(4 rows)
+
+TRUNCATE mv_histogram;
+-- check explain (expect bitmap index scan, not plain index scan) with NULLs
+INSERT INTO mv_histogram
+ 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 mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mv_histogram WHERE a IS NULL AND b IS NULL;
+ QUERY PLAN
+---------------------------------------------------
+ Bitmap Heap Scan on mv_histogram
+ Recheck Cond: ((a IS NULL) AND (b IS NULL))
+ -> Bitmap Index Scan on hist_idx
+ Index Cond: ((a IS NULL) AND (b IS NULL))
+(4 rows)
+
+DROP TABLE mv_histogram;
+-- NULL values (mix of int and text columns)
+CREATE TABLE mv_histogram (
+ a INT,
+ b TEXT,
+ c INT,
+ d TEXT
+);
+CREATE STATISTICS s3 ON mv_histogram (a, b, c, d) WITH (histogram);
+INSERT INTO mv_histogram
+ 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 mv_histogram;
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+ hist_enabled | hist_built
+--------------+------------
+ t | t
+(1 row)
+
+DROP TABLE mv_histogram;
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 66071d8..1a1a4ca 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -1375,7 +1375,9 @@ pg_mv_stats| SELECT n.nspname AS schemaname,
length(s.stadeps) AS depsbytes,
pg_mv_stats_dependencies_info(s.stadeps) AS depsinfo,
length(s.stamcv) AS mcvbytes,
- pg_mv_stats_mcvlist_info(s.stamcv) AS mcvinfo
+ pg_mv_stats_mcvlist_info(s.stamcv) AS mcvinfo,
+ length(s.stahist) AS histbytes,
+ pg_mv_stats_histogram_info(s.stahist) AS histinfo
FROM ((pg_mv_statistic s
JOIN pg_class c ON ((c.oid = s.starelid)))
LEFT JOIN pg_namespace n ON ((n.oid = c.relnamespace)));
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 85d94f1..a885235 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -112,4 +112,4 @@ test: event_trigger
test: stats
# run tests of multivariate stats
-test: mv_dependencies mv_mcv
+test: mv_dependencies mv_mcv mv_histogram
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 6584d73..2efdcd7 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -164,3 +164,4 @@ test: event_trigger
test: stats
test: mv_dependencies
test: mv_mcv
+test: mv_histogram
diff --git a/src/test/regress/sql/mv_histogram.sql b/src/test/regress/sql/mv_histogram.sql
new file mode 100644
index 0000000..02f49b4
--- /dev/null
+++ b/src/test/regress/sql/mv_histogram.sql
@@ -0,0 +1,176 @@
+-- data type passed by value
+CREATE TABLE mv_histogram (
+ a INT,
+ b INT,
+ c INT
+);
+
+-- unknown column
+CREATE STATISTICS s1 ON mv_histogram (unknown_column) WITH (histogram);
+
+-- single column
+CREATE STATISTICS s1 ON mv_histogram (a) WITH (histogram);
+
+-- single column, duplicated
+CREATE STATISTICS s1 ON mv_histogram (a, a) WITH (histogram);
+
+-- two columns, one duplicated
+CREATE STATISTICS s1 ON mv_histogram (a, a, b) WITH (histogram);
+
+-- unknown option
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (unknown_option);
+
+-- missing histogram statistics
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (dependencies, max_buckets=200);
+
+-- invalid max_buckets value / too low
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (mcv, max_buckets=10);
+
+-- invalid max_buckets value / too high
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (mcv, max_buckets=100000);
+
+-- correct command
+CREATE STATISTICS s1 ON mv_histogram (a, b, c) WITH (histogram);
+
+-- random data (no functional dependencies)
+INSERT INTO mv_histogram
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+TRUNCATE mv_histogram;
+
+-- a => b, a => c, b => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+TRUNCATE mv_histogram;
+
+-- a => b, a => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+TRUNCATE mv_histogram;
+
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mv_histogram
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX hist_idx ON mv_histogram (a, b);
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mv_histogram WHERE a = 10 AND b = 5;
+
+DROP TABLE mv_histogram;
+
+-- varlena type (text)
+CREATE TABLE mv_histogram (
+ a TEXT,
+ b TEXT,
+ c TEXT
+);
+
+CREATE STATISTICS s2 ON mv_histogram (a, b, c) WITH (histogram);
+
+-- random data (no functional dependencies)
+INSERT INTO mv_histogram
+ SELECT mod(i, 111), mod(i, 123), mod(i, 23) FROM generate_series(1,10000) s(i);
+
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+TRUNCATE mv_histogram;
+
+-- a => b, a => c, b => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/100, i/200 FROM generate_series(1,10000) s(i);
+
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+TRUNCATE mv_histogram;
+
+-- a => b, a => c
+INSERT INTO mv_histogram
+ SELECT i/10, i/150, i/200 FROM generate_series(1,10000) s(i);
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+TRUNCATE mv_histogram;
+
+-- check explain (expect bitmap index scan, not plain index scan)
+INSERT INTO mv_histogram
+ SELECT i/10000, i/20000, i/40000 FROM generate_series(1,1000000) s(i);
+CREATE INDEX hist_idx ON mv_histogram (a, b);
+ANALYZE mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mv_histogram WHERE a = '10' AND b = '5';
+
+TRUNCATE mv_histogram;
+
+-- check explain (expect bitmap index scan, not plain index scan) with NULLs
+INSERT INTO mv_histogram
+ 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 mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+EXPLAIN (COSTS off)
+ SELECT * FROM mv_histogram WHERE a IS NULL AND b IS NULL;
+
+DROP TABLE mv_histogram;
+
+-- NULL values (mix of int and text columns)
+CREATE TABLE mv_histogram (
+ a INT,
+ b TEXT,
+ c INT,
+ d TEXT
+);
+
+CREATE STATISTICS s3 ON mv_histogram (a, b, c, d) WITH (histogram);
+
+INSERT INTO mv_histogram
+ 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 mv_histogram;
+
+SELECT hist_enabled, hist_built
+ FROM pg_mv_statistic WHERE starelid = 'mv_histogram'::regclass;
+
+DROP TABLE mv_histogram;
--
2.1.0