0007-multivariate-ndistinct-coefficients.patch

From e42a2efeb060692d0a1ebe23f28c654130b26dcd 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/9] multivariate ndistinct coefficients

---
 doc/src/sgml/ref/create_statistics.sgml    |   9 ++
 src/backend/catalog/system_views.sql       |   3 +-
 src/backend/commands/analyze.c             |   2 +-
 src/backend/commands/statscmds.c           |  11 +-
 src/backend/optimizer/path/clausesel.c     |   4 +
 src/backend/optimizer/util/plancat.c       |   4 +-
 src/backend/utils/adt/selfuncs.c           |  93 +++++++++++++++-
 src/backend/utils/mvstats/Makefile         |   2 +-
 src/backend/utils/mvstats/README.ndistinct |  83 ++++++++++++++
 src/backend/utils/mvstats/README.stats     |   2 +
 src/backend/utils/mvstats/common.c         |  23 +++-
 src/backend/utils/mvstats/mvdist.c         | 171 +++++++++++++++++++++++++++++
 src/include/catalog/pg_mv_statistic.h      |  26 +++--
 src/include/nodes/relation.h               |   2 +
 src/include/utils/mvstats.h                |   9 +-
 src/test/regress/expected/rules.out        |   3 +-
 16 files changed, 424 insertions(+), 23 deletions(-)
 create mode 100644 src/backend/utils/mvstats/README.ndistinct
 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/catalog/system_views.sql b/src/backend/catalog/system_views.sql
index 6afdee0..a550141 100644
--- a/src/backend/catalog/system_views.sql
+++ b/src/backend/catalog/system_views.sql
@@ -169,7 +169,8 @@ CREATE VIEW pg_mv_stats AS
         length(S.stamcv) AS mcvbytes,
         pg_mv_stats_mcvlist_info(S.stamcv) AS mcvinfo,
         length(S.stahist) AS histbytes,
-        pg_mv_stats_histogram_info(S.stahist) AS histinfo
+        pg_mv_stats_histogram_info(S.stahist) AS histinfo,
+        standcoeff AS ndcoeff
     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/analyze.c b/src/backend/commands/analyze.c
index cbaa4e1..0f6db77 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -582,7 +582,7 @@ do_analyze_rel(Relation onerel, int options, VacuumParams *params,
 		}
 
 		/* Build multivariate stats (if there are any). */
-		build_mv_stats(onerel, numrows, rows, attr_cnt, vacattrstats);
+		build_mv_stats(onerel, totalrows, numrows, rows, attr_cnt, vacattrstats);
 	}
 
 	/*
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 c1b8999..2540da9 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(Node *clause, Index relid, Bitmapset **attnums,
 							 int type);
@@ -3246,6 +3247,9 @@ stats_type_matches(MVStatisticInfo *stat, 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 d46aed2..bd2c306 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 || mvstat->hist_built)
+			if (mvstat->deps_built || mvstat->mcv_built || mvstat->hist_built || mvstat->ndist_built)
 			{
 				info = makeNode(MVStatisticInfo);
 
@@ -427,11 +427,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/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 7d0a3a1..a84dd2b 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -132,6 +132,7 @@
 #include "utils/fmgroids.h"
 #include "utils/index_selfuncs.h"
 #include "utils/lsyscache.h"
+#include "utils/mvstats.h"
 #include "utils/nabstime.h"
 #include "utils/pg_locale.h"
 #include "utils/rel.h"
@@ -206,6 +207,7 @@ static Const *string_to_const(const char *str, Oid datatype);
 static Const *string_to_bytea_const(const char *str, size_t str_len);
 static List *add_predicate_to_quals(IndexOptInfo *index, List *indexQuals);
 
+static Oid find_ndistinct_coeff(PlannerInfo *root, RelOptInfo *rel, List *varinfos);
 
 /*
  *		eqsel			- Selectivity of "=" for any data types.
@@ -3422,12 +3424,26 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 			 * don't know by how much.  We should never clamp to less than the
 			 * largest ndistinct value for any of the Vars, though, since
 			 * there will surely be at least that many groups.
+			 *
+			 * However we don't need to do this if we have ndistinct stats on
+			 * the columns - in that case we can simply use the coefficient
+			 * to get the (probably way more accurate) estimate.
+			 *
+			 * XXX Probably needs refactoring (don't like to mix with clamp
+			 *     and coeff at the same time).
 			 */
 			double		clamp = rel->tuples;
+			double		coeff = 1.0;
 
 			if (relvarcount > 1)
 			{
-				clamp *= 0.1;
+				Oid oid = find_ndistinct_coeff(root, rel, varinfos);
+
+				if (oid != InvalidOid)
+					coeff = load_mv_ndistinct(oid);
+				else
+					clamp *= 0.1;
+
 				if (clamp < relmaxndistinct)
 				{
 					clamp = relmaxndistinct;
@@ -3436,6 +3452,13 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 						clamp = rel->tuples;
 				}
 			}
+
+			/*
+			 * Apply ndistinct coefficient from multivar stats (we must do this
+			 * before clamping the estimate in any way.
+			 */
+			reldistinct /= coeff;
+
 			if (reldistinct > clamp)
 				reldistinct = clamp;
 
@@ -7582,3 +7605,71 @@ brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 
 	/* XXX what about pages_per_range? */
 }
+
+/*
+ * Find applicable ndistinct statistics and compute the coefficient to
+ * correct the estimate (simply a product of per-column ndistincts).
+ *
+ * Currently we only look for a perfect match, i.e. a single ndistinct
+ * estimate exactly matching all the columns of the statistics.
+ */
+static Oid
+find_ndistinct_coeff(PlannerInfo *root, RelOptInfo *rel, List *varinfos)
+{
+	ListCell *lc;
+	Bitmapset *attnums = NULL;
+	VariableStatData vardata;
+
+	foreach(lc, varinfos)
+	{
+		GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc);
+
+		if (varinfo->rel != rel)
+			continue;
+
+		/* FIXME handle expressions in general only */
+
+		/*
+		 * examine the variable (or expression) so that we know which
+		 * attribute we're dealing with - we need this for matching the
+		 * ndistinct coefficient
+		 *
+		 * FIXME probably might remember this from estimate_num_groups
+		 */
+		examine_variable(root, varinfo->var, 0, &vardata);
+
+		if (HeapTupleIsValid(vardata.statsTuple))
+		{
+			Form_pg_statistic stats
+				= (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
+
+			attnums = bms_add_member(attnums, stats->staattnum);
+
+			ReleaseVariableStats(vardata);
+		}
+	}
+
+	/* look for a matching ndistinct statistics */
+	foreach (lc, rel->mvstatlist)
+	{
+		int i;
+		MVStatisticInfo *info = (MVStatisticInfo *)lfirst(lc);
+
+		/* skip statistics without ndistinct coefficient built */
+		if (!info->ndist_built)
+			continue;
+
+		/* only exact matches for now (same set of columns) */
+		if (bms_num_members(attnums) != info->stakeys->dim1)
+			continue;
+
+		/* check that the columns match */
+		for (i = 0; i < info->stakeys->dim1; i++)
+			if (bms_is_member(info->stakeys->values[i], attnums))
+				continue;
+
+		return info->mvoid;
+	}
+
+	return InvalidOid;
+}
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/README.ndistinct b/src/backend/utils/mvstats/README.ndistinct
new file mode 100644
index 0000000..32d1624
--- /dev/null
+++ b/src/backend/utils/mvstats/README.ndistinct
@@ -0,0 +1,83 @@
+ndistinct coefficients
+======================
+
+Estimating number of distinct groups in a combination of columns is tricky,
+and the estimation error is often significant. By ndistinct coefficient we
+mean a ratio
+
+    q = ndistinct(a) * ndistinct(b) / ndistinct(a,b)
+
+where 'a' and 'b' are columns, ndistinct(a) is (an estimate of) a number of
+distinct values in column 'a'. And ndistinct(a,b) is the same thing for the
+pair of columns.
+
+The meaning of the coefficient may be illustrated by answering the following
+question: Given a combination of columns (a,b), how many distinct values of 'b'
+matches a chosen value of 'a' on average?
+
+Let's assume we know ndistinct(a) and ndistinct(a,b). Then the answer to the
+question clearly is
+
+    ndistinct(a,b) / ndistinct(a)
+
+and by using 'q' we may rewrite this as
+
+    ndistinct(b) / q
+
+so 'q' may be considered as a correction factor of the ndistinct estimate given
+a condition on one of the columns.
+
+This may be generalized to a combination of 'n' columns
+
+    [ndistinct(c1) * ... * ndistinct(cn)] / ndistinct(c1, ..., cn)
+
+and the meaning is very similar, except that we need to use conditions on (n-1)
+of the columns.
+
+
+Selectivity estimation
+----------------------
+
+As explained in the previous paragraph, ndistinct coefficients may be used to
+estimate cardinality of a column, given some apriori knowledge. Let's assume
+we need to estimate selectivity of a condition
+
+    (a=1) AND (b=2)
+
+which we can expand like this
+
+    P(a=1 & b=2) = P(a=1) * P(b=2 | a=1)
+
+Let's also assume that the distribution of 'b' is uniform, i.e. that
+
+    P(a=1) = 1/ndistinct(a)
+    P(b=2) = 1/ndistinct(b)
+    P(a=1 & b=2) = 1/ndistinct(a,b)
+
+    P(b=2 | a=1) = ndistinct(a) / ndistinct(a,b)
+
+which may be rewritten like
+
+    P(b=2 | a=1)
+        = ndistinct(a,b) / ndistinct(a)
+        = (1/ndistinct(b)) * [(ndistinct(a) * ndistinct(b)) / ndistinct(a,b)]
+        = (1/ndistinct(b)) * q
+
+and therefore
+
+    P(a=1 & b=2) = (1/ndistinct(a)) * (1/ndistinct(b)) * q
+
+This also illustrates 'q' as a correction coefficient.
+
+It also explains why we store the coefficient and not simply ndistinct(a,b).
+This way we can simply estimate individual clauses and then simply correct
+the estimate by multiplying the result with 'q' - we don't have to mess with
+ndistinct estimates at all.
+
+Naturally, as the coefficient is derives from ndistinct(a,b), it may be also
+used to estimate GROUP BY clauses on the combination of columns, replacing the
+existing heuristics in estimate_num_groups().
+
+Note: Currently only the GROUP BY estimation is implemented. It's a bit unclear
+how to implement the clause estimation when there are other statistics (esp.
+MCV lists and/or functional dependencies) available.
diff --git a/src/backend/utils/mvstats/README.stats b/src/backend/utils/mvstats/README.stats
index d404914..6d4b09b 100644
--- a/src/backend/utils/mvstats/README.stats
+++ b/src/backend/utils/mvstats/README.stats
@@ -20,6 +20,8 @@ Currently we only have two kinds of multivariate statistics
 
     (c) multivariate histograms (README.histogram)
 
+    (d) ndistinct coefficients
+
 
 Compatible clause types
 -----------------------
diff --git a/src/backend/utils/mvstats/common.c b/src/backend/utils/mvstats/common.c
index ffb76f4..2be980d 100644
--- a/src/backend/utils/mvstats/common.c
+++ b/src/backend/utils/mvstats/common.c
@@ -32,7 +32,8 @@ static List* list_mv_stats(Oid relid);
  * and serializes them back into the catalog (as bytea values).
  */
 void
-build_mv_stats(Relation onerel, int numrows, HeapTuple *rows,
+build_mv_stats(Relation onerel, double totalrows,
+			   int numrows, HeapTuple *rows,
 			   int natts, VacAttrStats **vacattrstats)
 {
 	ListCell *lc;
@@ -53,6 +54,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 +94,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(totalrows, numrows, rows, attrs, stats);
+
 		/* build the MCV list */
 		if (stat->mcv_enabled)
 			mcvlist = build_mv_mcvlist(numrows, rows, attrs, stats, &numrows_filtered);
@@ -101,7 +106,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 +188,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 +259,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 +299,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..59b8358
--- /dev/null
+++ b/src/backend/utils/mvstats/mvdist.c
@@ -0,0 +1,171 @@
+/*-------------------------------------------------------------------------
+ *
+ * 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 <math.h>
+
+#include "common.h"
+#include "utils/lsyscache.h"
+
+static double estimate_ndistinct(double totalrows, int numrows, int d, int f1);
+
+/*
+ * Compute ndistinct coefficient for the combination of attributes. This
+ * computes the ndistinct estimate using the same estimator used in analyze.c
+ * and then computes the coefficient.
+ */
+double
+build_mv_ndistinct(double totalrows, int numrows, HeapTuple *rows,
+				   int2vector *attrs, VacAttrStats **stats)
+{
+	int i, j;
+	int f1, cnt, d;
+	int nmultiple, summultiple;
+	int numattrs = attrs->dim1;
+	MultiSortSupport mss = multi_sort_init(numattrs);
+	double ndistcoeff;
+
+	/*
+	 * 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 */
+
+	f1 = 0;
+	cnt = 1;
+	d = 1;
+	for (i = 1; i < numrows; i++)
+	{
+		if (multi_sort_compare(&items[i], &items[i-1], mss) != 0)
+		{
+			if (cnt == 1)
+				f1 += 1;
+			else
+			{
+				nmultiple += 1;
+				summultiple += cnt;
+			}
+
+			d++;
+			cnt = 0;
+		}
+
+		cnt += 1;
+	}
+
+	if (cnt == 1)
+		f1 += 1;
+	else
+	{
+		nmultiple += 1;
+		summultiple += cnt;
+	}
+
+	ndistcoeff = 1 / estimate_ndistinct(totalrows, numrows, d, f1);
+
+	/*
+	 * now count distinct values for each attribute and incrementally
+	 * compute ndistinct(a,b) / (ndistinct(a) * ndistinct(b))
+	 *
+	 * FIXME Probably need to handle cases when one of the ndistinct
+	 *       estimates is negative, and also check that the combined
+	 *       ndistinct is greater than any of those partial values.
+	 */
+	for (i = 0; i < numattrs; i++)
+		ndistcoeff *= stats[i]->stadistinct;
+
+	return ndistcoeff;
+}
+
+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);
+}
+
+/* The Duj1 estimator (already used in analyze.c). */
+static double
+estimate_ndistinct(double totalrows, int numrows, int d, int f1)
+{
+	double	numer,
+			denom,
+			ndistinct;
+
+	numer = (double) numrows *(double) d;
+
+	denom = (double) (numrows - f1) +
+			(double) f1 * (double) numrows / totalrows;
+
+	ndistinct = numer / denom;
+
+	/* Clamp to sane range in case of roundoff error */
+	if (ndistinct < (double) d)
+		ndistinct = (double) d;
+
+	if (ndistinct > totalrows)
+		ndistinct = totalrows;
+
+	return floor(ndistinct + 0.5);
+}
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 46bece6..a2fafd2 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -621,11 +621,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..fb2c5d8 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,17 @@ 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,
+double
+build_mv_ndistinct(double totalrows, int numrows, HeapTuple *rows,
+				   int2vector *attrs, VacAttrStats **stats);
+
+void build_mv_stats(Relation onerel, double totalrows,
+					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
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 1a1a4ca..0ad935e 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -1377,7 +1377,8 @@ pg_mv_stats| SELECT n.nspname AS schemaname,
     length(s.stamcv) AS mcvbytes,
     pg_mv_stats_mcvlist_info(s.stamcv) AS mcvinfo,
     length(s.stahist) AS histbytes,
-    pg_mv_stats_histogram_info(s.stahist) AS histinfo
+    pg_mv_stats_histogram_info(s.stahist) AS histinfo,
+    s.standcoeff AS ndcoeff
    FROM ((pg_mv_statistic s
      JOIN pg_class c ON ((c.oid = s.starelid)))
      LEFT JOIN pg_namespace n ON ((n.oid = c.relnamespace)));
-- 
2.1.0