0007-initial-version-of-ndistinct-conefficient-statistics.patch

From f750038f659d74ff88be575b1c5c92ad0f745f1d Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Wed, 23 Dec 2015 02:07:58 +0100
Subject: [PATCH 7/7] initial version of ndistinct conefficient statistics

---
 doc/src/sgml/ref/create_statistics.sgml |   9 ++
 src/backend/commands/statscmds.c        |  11 ++-
 src/backend/optimizer/path/clausesel.c  |   7 ++
 src/backend/optimizer/util/plancat.c    |   4 +-
 src/backend/utils/mvstats/Makefile      |   2 +-
 src/backend/utils/mvstats/common.c      |  20 ++++-
 src/backend/utils/mvstats/mvdist.c      | 147 ++++++++++++++++++++++++++++++++
 src/include/catalog/pg_mv_statistic.h   |  26 +++---
 src/include/nodes/relation.h            |   2 +
 src/include/utils/mvstats.h             |   6 ++
 10 files changed, 217 insertions(+), 17 deletions(-)
 create mode 100644 src/backend/utils/mvstats/mvdist.c

diff --git a/doc/src/sgml/ref/create_statistics.sgml b/doc/src/sgml/ref/create_statistics.sgml
index fd3382e..80360a6 100644
--- a/doc/src/sgml/ref/create_statistics.sgml
+++ b/doc/src/sgml/ref/create_statistics.sgml
@@ -168,6 +168,15 @@ CREATE STATISTICS [ IF NOT EXISTS ] <replaceable class="PARAMETER">statistics_na
     </listitem>
    </varlistentry>
 
+   <varlistentry>
+    <term><literal>ndistinct</> (<type>boolean</>)</term>
+    <listitem>
+     <para>
+      Enables ndistinct coefficients for the statistics.
+     </para>
+    </listitem>
+   </varlistentry>
+
    </variablelist>
 
   </refsect2>
diff --git a/src/backend/commands/statscmds.c b/src/backend/commands/statscmds.c
index b974655..6ea0e13 100644
--- a/src/backend/commands/statscmds.c
+++ b/src/backend/commands/statscmds.c
@@ -138,7 +138,8 @@ CreateStatistics(CreateStatsStmt *stmt)
 	/* by default build nothing */
 	bool 	build_dependencies = false,
 			build_mcv = false,
-			build_histogram = false;
+			build_histogram = false,
+			build_ndistinct = false;
 
 	int32 	max_buckets = -1,
 			max_mcv_items = -1;
@@ -221,6 +222,8 @@ CreateStatistics(CreateStatsStmt *stmt)
 
 		if (strcmp(opt->defname, "dependencies") == 0)
 			build_dependencies = defGetBoolean(opt);
+		else if (strcmp(opt->defname, "ndistinct") == 0)
+			build_ndistinct = defGetBoolean(opt);
 		else if (strcmp(opt->defname, "mcv") == 0)
 			build_mcv = defGetBoolean(opt);
 		else if (strcmp(opt->defname, "max_mcv_items") == 0)
@@ -275,10 +278,10 @@ CreateStatistics(CreateStatsStmt *stmt)
 	}
 
 	/* check that at least some statistics were requested */
-	if (! (build_dependencies || build_mcv || build_histogram))
+	if (! (build_dependencies || build_mcv || build_histogram || build_ndistinct))
 		ereport(ERROR,
 				(errcode(ERRCODE_SYNTAX_ERROR),
-				 errmsg("no statistics type (dependencies, mcv, histogram) was requested")));
+				 errmsg("no statistics type (dependencies, mcv, histogram, ndistinct) was requested")));
 
 	/* now do some checking of the options */
 	if (require_mcv && (! build_mcv))
@@ -311,6 +314,7 @@ 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_ndist_enabled-1] = BoolGetDatum(build_ndistinct);
 
 	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);
@@ -318,6 +322,7 @@ CreateStatistics(CreateStatsStmt *stmt)
 	nulls[Anum_pg_mv_statistic_stadeps  -1] = true;
 	nulls[Anum_pg_mv_statistic_stamcv   -1] = true;
 	nulls[Anum_pg_mv_statistic_stahist  -1] = true;
+	nulls[Anum_pg_mv_statistic_standist -1] = true;
 
 	/* insert the tuple into pg_mv_statistic */
 	mvstatrel = heap_open(MvStatisticRelationId, RowExclusiveLock);
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 3d4d136..720ff87 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -59,6 +59,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
+#define		MV_CLAUSE_TYPE_NDIST	0x08
 
 static bool clause_is_mv_compatible(PlannerInfo *root, Node *clause, Oid varRelid,
 							 Index *relid, Bitmapset **attnums, SpecialJoinInfo *sjinfo,
@@ -377,6 +378,9 @@ clauselist_selectivity(PlannerInfo *root,
 													stats, sjinfo);
 	}
 
+	if (has_stats(stats, MV_CLAUSE_TYPE_NDIST))
+		elog(WARNING, "has ndistinct coefficient stats");
+
 	/*
 	 * Check that there are statistics with MCV list or histogram.
 	 * If not, we don't need to waste time with the optimization.
@@ -2931,6 +2935,9 @@ has_stats(List *stats, int type)
 
 		if ((type & MV_CLAUSE_TYPE_HIST) && stat->hist_built)
 			return true;
+
+		if ((type & MV_CLAUSE_TYPE_NDIST) && stat->ndist_built)
+			return true;
 	}
 
 	return false;
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 963d26e..a319246 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -410,7 +410,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 || mvstat->hist_built)
+			if (mvstat->deps_built || mvstat->mcv_built || mvstat->hist_built || mvstat->ndist_built)
 			{
 				info = makeNode(MVStatisticInfo);
 
@@ -421,11 +421,13 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 				info->deps_enabled = mvstat->deps_enabled;
 				info->mcv_enabled  = mvstat->mcv_enabled;
 				info->hist_enabled = mvstat->hist_enabled;
+				info->ndist_enabled = mvstat->ndist_enabled;
 
 				/* built/available statistics */
 				info->deps_built = mvstat->deps_built;
 				info->mcv_built  = mvstat->mcv_built;
 				info->hist_built = mvstat->hist_built;
+				info->ndist_built = mvstat->ndist_built;
 
 				/* stakeys */
 				adatum = SysCacheGetAttr(MVSTATOID, htup,
diff --git a/src/backend/utils/mvstats/Makefile b/src/backend/utils/mvstats/Makefile
index 9dbb3b6..d4b88e9 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 histogram.o mcv.o
+OBJS = common.o dependencies.o histogram.o mcv.o mvdist.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/utils/mvstats/common.c b/src/backend/utils/mvstats/common.c
index ffb76f4..c42ca8f 100644
--- a/src/backend/utils/mvstats/common.c
+++ b/src/backend/utils/mvstats/common.c
@@ -53,6 +53,7 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
 		MVDependencies	deps  = NULL;
 		MCVList		mcvlist   = NULL;
 		MVHistogram	histogram = NULL;
+		double		ndist	  = -1;
 		int numrows_filtered  = numrows;
 
 		VacAttrStats  **stats  = NULL;
@@ -92,6 +93,9 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
 		if (stat->deps_enabled)
 			deps = build_mv_dependencies(numrows, rows, attrs, stats);
 
+		if (stat->ndist_enabled)
+			ndist = build_mv_ndistinct(numrows, rows, attrs, stats);
+
 		/* build the MCV list */
 		if (stat->mcv_enabled)
 			mcvlist = build_mv_mcvlist(numrows, rows, attrs, stats, &numrows_filtered);
@@ -101,7 +105,7 @@ build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
 			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, histogram, attrs, stats);
+		update_mv_stats(stat->mvoid, deps, mcvlist, histogram, ndist, attrs, stats);
 	}
 }
 
@@ -183,6 +187,8 @@ list_mv_stats(Oid relid)
 		info->mcv_built = stats->mcv_built;
 		info->hist_enabled = stats->hist_enabled;
 		info->hist_built = stats->hist_built;
+		info->ndist_enabled = stats->ndist_enabled;
+		info->ndist_built = stats->ndist_built;
 
 		result = lappend(result, info);
 	}
@@ -252,7 +258,7 @@ find_mv_attnums(Oid mvoid, Oid *relid)
 void
 update_mv_stats(Oid mvoid,
 				MVDependencies dependencies, MCVList mcvlist, MVHistogram histogram,
-				int2vector *attrs, VacAttrStats **stats)
+				double ndistcoeff, int2vector *attrs, VacAttrStats **stats)
 {
 	HeapTuple	stup,
 				oldtup;
@@ -292,26 +298,36 @@ update_mv_stats(Oid mvoid,
 			= PointerGetDatum(data);
 	}
 
+	if (ndistcoeff > 1.0)
+	{
+		nulls[Anum_pg_mv_statistic_standist -1] = false;
+		values[Anum_pg_mv_statistic_standist-1] = Float8GetDatum(ndistcoeff);
+	}
+
 	/* 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;
+	replaces[Anum_pg_mv_statistic_standist-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_ndist_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_ndist_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_ndist_built-1] = BoolGetDatum(ndistcoeff > 1.0);
 	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/mvdist.c b/src/backend/utils/mvstats/mvdist.c
new file mode 100644
index 0000000..6df7411
--- /dev/null
+++ b/src/backend/utils/mvstats/mvdist.c
@@ -0,0 +1,147 @@
+/*-------------------------------------------------------------------------
+ *
+ * mvdist.c
+ *	  POSTGRES multivariate distinct coefficients
+ *
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/utils/mvstats/mvdist.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "common.h"
+#include "utils/lsyscache.h"
+
+/*
+ * 
+ */
+double
+build_mv_ndistinct(int numrows, HeapTuple *rows, int2vector *attrs,
+				   VacAttrStats **stats)
+{
+	int i, j;
+	int numattrs = attrs->dim1;
+	MultiSortSupport mss = multi_sort_init(numattrs);
+	int ndistinct;
+	double result;
+
+	/*
+	 * It's possible to sort the sample rows directly, but this seemed
+	 * somehow simpler / less error prone. Another option would be to
+	 * allocate the arrays for each SortItem separately, but that'd be
+	 * significant overhead (not just CPU, but especially memory bloat).
+	 */
+	SortItem * items = (SortItem*)palloc0(numrows * sizeof(SortItem));
+
+	Datum *values = (Datum*)palloc0(sizeof(Datum) * numrows * numattrs);
+	bool  *isnull = (bool*)palloc0(sizeof(bool) * numrows * numattrs);
+
+	for (i = 0; i < numrows; i++)
+	{
+		items[i].values = &values[i * numattrs];
+		items[i].isnull = &isnull[i * numattrs];
+	}
+
+	Assert(numattrs >= 2);
+
+	for (i = 0; i < numattrs; i++)
+	{
+		/* prepare the sort function for the first dimension */
+		multi_sort_add_dimension(mss, i, i, stats);
+
+		/* accumulate all the data into the array and sort it */
+		for (j = 0; j < numrows; j++)
+		{
+			items[j].values[i]
+				= heap_getattr(rows[j], attrs->values[i],
+							   stats[i]->tupDesc, &items[j].isnull[i]);
+		}
+	}
+
+	qsort_arg((void *) items, numrows, sizeof(SortItem),
+			  multi_sort_compare, mss);
+
+	/* count number of distinct combinations */
+
+	ndistinct = 1;
+	for (i = 1; i < numrows; i++)
+	{
+		if (multi_sort_compare(&items[i], &items[i-1], mss) != 0)
+			ndistinct++;
+	}
+
+	result = 1 / (double)ndistinct;
+
+	/*
+	 * now count distinct values for each attribute and incrementally
+	 * compute ndistinct(a,b) / (ndistinct(a) * ndistinct(b))
+	 */
+	for (i = 0; i < numattrs; i++)
+	{
+		SortSupportData ssup;
+		StdAnalyzeData *tmp = (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(tmp->ltopr, &ssup);
+
+		memset(values, 0, sizeof(Datum) * numrows);
+
+		/* accumulate all the data into the array and sort it */
+		for (j = 0; j < numrows; j++)
+		{
+			bool isnull;
+			values[j] = heap_getattr(rows[j], attrs->values[i],
+									 stats[i]->tupDesc, &isnull);
+		}
+
+		qsort_arg((void *)values, numrows, sizeof(Datum),
+				  compare_scalars_simple, &ssup);
+
+		ndistinct = 1;
+		for (j = 1; j < numrows; j++)
+		{
+			if (compare_scalars_simple(&values[j], &values[j-1], &ssup) != 0)
+				ndistinct++;
+		}
+
+		result *= ndistinct;
+	}
+
+	return result;
+}
+
+double
+load_mv_ndistinct(Oid mvoid)
+{
+	bool		isnull = false;
+	Datum		deps;
+
+	/* Prepare to scan pg_mv_statistic for entries having indrelid = this rel. */
+	HeapTuple	htup = SearchSysCache1(MVSTATOID, ObjectIdGetDatum(mvoid));
+
+#ifdef USE_ASSERT_CHECKING
+	Form_pg_mv_statistic	mvstat = (Form_pg_mv_statistic) GETSTRUCT(htup);
+	Assert(mvstat->ndist_enabled && mvstat->ndist_built);
+#endif
+
+	deps = SysCacheGetAttr(MVSTATOID, htup,
+						   Anum_pg_mv_statistic_standist, &isnull);
+
+	Assert(!isnull);
+
+	ReleaseSysCache(htup);
+
+	return DatumGetFloat8(deps);
+}
diff --git a/src/include/catalog/pg_mv_statistic.h b/src/include/catalog/pg_mv_statistic.h
index a5945af..ee353da 100644
--- a/src/include/catalog/pg_mv_statistic.h
+++ b/src/include/catalog/pg_mv_statistic.h
@@ -39,6 +39,7 @@ CATALOG(pg_mv_statistic,3381)
 	bool		deps_enabled;		/* analyze dependencies? */
 	bool		mcv_enabled;		/* build MCV list? */
 	bool		hist_enabled;		/* build histogram? */
+	bool		ndist_enabled;		/* build ndist coefficient? */
 
 	/* histogram / MCV size */
 	int32		mcv_max_items;		/* max MCV items */
@@ -48,6 +49,7 @@ CATALOG(pg_mv_statistic,3381)
 	bool		deps_built;			/* dependencies were built */
 	bool		mcv_built;			/* MCV list was built */
 	bool		hist_built;			/* histogram was built */
+	bool		ndist_built;		/* ndistinct coeff built */
 
 	/* variable-length fields start here, but we allow direct access to stakeys */
 	int2vector	stakeys;			/* array of column keys */
@@ -56,6 +58,7 @@ CATALOG(pg_mv_statistic,3381)
 	bytea		stadeps;			/* dependencies (serialized) */
 	bytea		stamcv;				/* MCV list (serialized) */
 	bytea		stahist;			/* MV histogram (serialized) */
+	float8		standcoeff;			/* ndistinct coeff (serialized) */
 #endif
 
 } FormData_pg_mv_statistic;
@@ -71,21 +74,24 @@ typedef FormData_pg_mv_statistic *Form_pg_mv_statistic;
  *		compiler constants for pg_mv_statistic
  * ----------------
  */
-#define Natts_pg_mv_statistic					15
+#define Natts_pg_mv_statistic					18
 #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_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
+#define Anum_pg_mv_statistic_ndist_enabled		7
+#define Anum_pg_mv_statistic_mcv_max_items		8
+#define Anum_pg_mv_statistic_hist_max_buckets	9
+#define Anum_pg_mv_statistic_deps_built			10
+#define Anum_pg_mv_statistic_mcv_built			11
+#define Anum_pg_mv_statistic_hist_built			12
+#define Anum_pg_mv_statistic_ndist_built		13
+#define Anum_pg_mv_statistic_stakeys			14
+#define Anum_pg_mv_statistic_stadeps			15
+#define Anum_pg_mv_statistic_stamcv				16
+#define Anum_pg_mv_statistic_stahist			17
+#define Anum_pg_mv_statistic_standist			18
 
 #endif   /* PG_MV_STATISTIC_H */
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 1298c42..97d74e9 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -594,11 +594,13 @@ typedef struct MVStatisticInfo
 	bool		deps_enabled;	/* functional dependencies enabled */
 	bool		mcv_enabled;	/* MCV list enabled */
 	bool		hist_enabled;	/* histogram enabled */
+	bool		ndist_enabled;	/* ndistinct coefficient enabled */
 
 	/* built/available statistics */
 	bool		deps_built;		/* functional dependencies built */
 	bool		mcv_built;		/* MCV list built */
 	bool		hist_built;		/* histogram built */
+	bool		ndist_built;	/* ndistinct coefficient 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 35b2f8e..a154cd9 100644
--- a/src/include/utils/mvstats.h
+++ b/src/include/utils/mvstats.h
@@ -225,6 +225,7 @@ typedef MVSerializedHistogramData *MVSerializedHistogram;
 MVDependencies load_mv_dependencies(Oid mvoid);
 MCVList        load_mv_mcvlist(Oid mvoid);
 MVSerializedHistogram    load_mv_histogram(Oid mvoid);
+double		   load_mv_ndistinct(Oid mvoid);
 
 bytea * serialize_mv_dependencies(MVDependencies dependencies);
 bytea * serialize_mv_mcvlist(MCVList mcvlist, int2vector *attrs,
@@ -266,11 +267,16 @@ MVHistogram
 build_mv_histogram(int numrows, HeapTuple *rows, int2vector *attrs,
 				   VacAttrStats **stats, int numrows_total);
 
+double
+build_mv_ndistinct(int numrows, HeapTuple *rows, int2vector *attrs,
+				   VacAttrStats **stats);
+
 void build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
 					int natts, VacAttrStats **vacattrstats);
 
 void update_mv_stats(Oid relid, MVDependencies dependencies,
 					 MCVList mcvlist, MVHistogram histogram,
+					 double ndistcoeff,
 					 int2vector *attrs, VacAttrStats **stats);
 
 #ifdef DEBUG_MVHIST
-- 
2.1.0