0006-multi-statistics-estimation.patch

From dec65426b12adcceb6303692b07bb4f5c3e564e2 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Fri, 6 Feb 2015 01:42:38 +0100
Subject: [PATCH 6/9] multi-statistics estimation

The general idea is that a probability (which is what selectivity is)
can be split into a product of conditional probabilities like this:

    P(A & B & C) = P(A & B) * P(C|A & B)

If we assume that C and B are independent, the last part may be
simplified like this

    P(A & B & C) = P(A & B) * P(C|A)

we only need probabilities on [A,B] and [C,A] to compute the original
probability.

The implementation works in the other direction, though. We know what
probability P(A & B & C) we need to compute, and also what statistics
are available.

So we search for a combinations of statistics, covering the clauses in
an optimal way (most clauses covered, most dependencies exploited).

There are two possible approaches - exhaustive and greedy. The
exhaustive one walks through all permutations of stats using dynamic
programming, so it's guaranteed to find the optimal solution, but it
soon gets very slow as it's roughly O(N!). The dynamic programming may
improve that a bit, but it's still far too expensive for large numbers
of statistics (on a single table).

The greedy algorithm is very simple - in every step choose the best
solution. That may not guarantee the best solution globally (but maybe
it does?), but it only needs N steps to find the solution, so it's very
fast (processing the selected stats is usually way more expensive).

There's a GUC for selecting the search algorithm

    mvstat_search = {'greedy', 'exhaustive'}

The default value is 'greedy' as that's much safer (with respect to
runtime). See choose_mv_statistics().

Once we have found a sequence of statistics, we apply them to the
clauses using the conditional probabilities. We process the selected
stats one by one, and for each we select the estimated clauses and
conditions. See clauselist_selectivity() for more details.

Limitations
-----------

It's still true that each clause at a given level has to be covered by
a single MV statistics. So with this query

    WHERE (clause1) AND (clause2) AND (clause3 OR clause4)

each parenthesized clause has to be covered by a single multivariate
statistics.

Clauses not covered by a single statistics at this level will be passed
to clause_selectivity() but this will treat them as a collection of
simpler clauses (connected by AND or OR), and the clauses from the
previous level will be used as conditions.

So using the same example, the last clause will be passed to
clause_selectivity() with 'clause1' and 'clause2' as conditions, and it
will be processed using multivariate stats if possible.

The other limitation is that all the expressions have to be
mv-compatible, i.e. there can't be a mix of expressions. If this is
violated, the clause may be passed to the next level (just like with
list of clauses not covered by a single statistics), which splits that
into clauses handled by multivariate stats and clauses handler by
regular statistics.

rework clauselist_selectivity_or to handle OR-clauses correctly

We might invent a completely new set of functions here, resembling
clauselist_selectivity but adapting the ideas to OR-clauses.

But luckily we know that each OR-clause

    (a OR b OR c)

may be rewritten as an equivalent AND-clause using negation:

    NOT ((NOT a) AND (NOT b) AND (NOT c))

And that's something we can pass to clauselist_selectivity.
---
 contrib/file_fdw/file_fdw.c            |    3 +-
 contrib/postgres_fdw/postgres_fdw.c    |    6 +-
 src/backend/optimizer/path/clausesel.c | 1990 ++++++++++++++++++++++++++------
 src/backend/optimizer/path/costsize.c  |   23 +-
 src/backend/optimizer/util/orclauses.c |    4 +-
 src/backend/utils/adt/selfuncs.c       |   17 +-
 src/backend/utils/misc/guc.c           |   20 +
 src/backend/utils/mvstats/README.stats |  166 +++
 src/include/optimizer/cost.h           |    6 +-
 src/include/utils/mvstats.h            |    8 +
 10 files changed, 1887 insertions(+), 356 deletions(-)

diff --git a/contrib/file_fdw/file_fdw.c b/contrib/file_fdw/file_fdw.c
index dc035d7..8f11b7a 100644
--- a/contrib/file_fdw/file_fdw.c
+++ b/contrib/file_fdw/file_fdw.c
@@ -969,7 +969,8 @@ estimate_size(PlannerInfo *root, RelOptInfo *baserel,
 							   baserel->baserestrictinfo,
 							   0,
 							   JOIN_INNER,
-							   NULL);
+							   NULL,
+							   NIL);
 
 	nrows = clamp_row_est(nrows);
 
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index d79e4cc..2f4af21 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -498,7 +498,8 @@ postgresGetForeignRelSize(PlannerInfo *root,
 													 fpinfo->local_conds,
 													 baserel->relid,
 													 JOIN_INNER,
-													 NULL);
+													 NULL,
+													 NIL);
 
 	cost_qual_eval(&fpinfo->local_conds_cost, fpinfo->local_conds, root);
 
@@ -2149,7 +2150,8 @@ estimate_path_cost_size(PlannerInfo *root,
 										   local_param_join_conds,
 										   foreignrel->relid,
 										   JOIN_INNER,
-										   NULL);
+										   NULL,
+										   NIL);
 		local_sel *= fpinfo->local_conds_sel;
 
 		rows = clamp_row_est(rows * local_sel);
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 0de2418..c1b8999 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -29,6 +29,8 @@
 #include "utils/selfuncs.h"
 #include "utils/typcache.h"
 
+#include "miscadmin.h"
+
 
 /*
  * Data structure for accumulating info about possible range-query
@@ -44,6 +46,13 @@ typedef struct RangeQueryClause
 	Selectivity hibound;		/* Selectivity of a var < something clause */
 } RangeQueryClause;
 
+static Selectivity clauselist_selectivity_or(PlannerInfo *root,
+											 List *clauses,
+											 int varRelid,
+											 JoinType jointype,
+											 SpecialJoinInfo *sjinfo,
+											 List *conditions);
+
 static void addRangeClause(RangeQueryClause **rqlist, Node *clause,
 			   bool varonleft, bool isLTsel, Selectivity s2);
 
@@ -60,23 +69,25 @@ static int count_mv_attnums(List *clauses, Index relid, int type);
 
 static int count_varnos(List *clauses, Index *relid);
 
+static List *clauses_matching_statistic(List **clauses, MVStatisticInfo *statistic,
+						   Index relid, int types, bool remove);
+
 static List *clauselist_apply_dependencies(PlannerInfo *root, List *clauses,
 									Index relid, List *stats);
 
-static MVStatisticInfo *choose_mv_statistics(List *mvstats, Bitmapset *attnums);
-
-static List *clauselist_mv_split(PlannerInfo *root, Index relid,
-								 List *clauses, List **mvclauses,
-								 MVStatisticInfo *mvstats, int types);
-
 static Selectivity clauselist_mv_selectivity(PlannerInfo *root,
-									List *clauses, MVStatisticInfo *mvstats);
+									MVStatisticInfo *mvstats, List *clauses,
+									List *conditions, bool is_or);
 
 static Selectivity clauselist_mv_selectivity_mcvlist(PlannerInfo *root,
-									List *clauses, MVStatisticInfo *mvstats,
-									bool *fullmatch, Selectivity *lowsel);
+									MVStatisticInfo *mvstats,
+									List *clauses, List *conditions,
+									bool is_or, bool *fullmatch,
+									Selectivity *lowsel);
 static Selectivity clauselist_mv_selectivity_histogram(PlannerInfo *root,
-									List *clauses, MVStatisticInfo *mvstats);
+									MVStatisticInfo *mvstats,
+									List *clauses, List *conditions,
+									bool is_or);
 
 static int update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
 									int2vector *stakeys, MCVList mcvlist,
@@ -90,10 +101,33 @@ static int update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
 									int nmatches, char * matches,
 									bool is_or);
 
+/*
+ * Describes a combination of multiple statistics to cover attributes
+ * referenced by the clauses. The array 'stats' (with nstats elements)
+ * lists attributes (in the order as they are applied), and number of
+ * clause attributes covered by this solution.
+ *
+ * choose_mv_statistics_exhaustive() uses this to track both the current
+ * and the best solutions, while walking through the state of possible
+ * combination.
+ */
+typedef struct mv_solution_t {
+	int		nclauses;		/* number of clauses covered */
+	int		nconditions;	/* number of conditions covered */
+	int		nstats;			/* number of stats applied */
+	int	   *stats;			/* stats (in the apply order) */
+} mv_solution_t;
+
+static List *choose_mv_statistics(PlannerInfo *root, Index relid,
+							List *mvstats, List *clauses, List *conditions);
+
 static bool has_stats(List *stats, int type);
 
 static List * find_stats(PlannerInfo *root, Index relid);
 
+static bool stats_type_matches(MVStatisticInfo *stat, int type);
+
+int mvstat_search_type = MVSTAT_SEARCH_GREEDY;
 
 /* used for merging bitmaps - AND (min), OR (max) */
 #define MAX(x, y) (((x) > (y)) ? (x) : (y))
@@ -168,14 +202,15 @@ clauselist_selectivity(PlannerInfo *root,
 					   List *clauses,
 					   int varRelid,
 					   JoinType jointype,
-					   SpecialJoinInfo *sjinfo)
+					   SpecialJoinInfo *sjinfo,
+					   List *conditions)
 {
 	Selectivity s1 = 1.0;
 	RangeQueryClause *rqlist = NULL;
 	ListCell   *l;
 
 	/* processing mv stats */
-	Oid			relid = InvalidOid;
+	Index		relid = InvalidOid;
 
 	/* list of multivariate stats on the relation */
 	List	   *stats = NIL;
@@ -191,12 +226,13 @@ clauselist_selectivity(PlannerInfo *root,
 		stats = find_stats(root, relid);
 
 	/*
-	 * If there's exactly one clause, then no use in trying to match up pairs,
-	 * so just go directly to clause_selectivity().
+	 * If there's exactly one clause, then no use in trying to match up
+	 * pairs, or matching multivariate statistics, so just go directly
+	 * to clause_selectivity().
 	 */
 	if (list_length(clauses) == 1)
 		return clause_selectivity(root, (Node *) linitial(clauses),
-								  varRelid, jointype, sjinfo);
+								  varRelid, jointype, sjinfo, conditions);
 
 	/*
 	 * Apply functional dependencies, but first check that there are some stats
@@ -228,31 +264,96 @@ clauselist_selectivity(PlannerInfo *root,
 		(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 | MV_CLAUSE_TYPE_HIST);
+		ListCell *s;
+
+		/*
+		 * Copy the conditions we got from the upper part of the expression tree
+		 * so that we can add local conditions to it (we need to keep the
+		 * original list intact, for sibling expressions - other expressions
+		 * at the same level).
+		 */
+		List *conditions_local = list_copy(conditions);
 
-		/* and search for the statistic covering the most attributes */
-		MVStatisticInfo *mvstat = choose_mv_statistics(stats, mvattnums);
+		/* find the best combination of statistics */
+		List *solution = choose_mv_statistics(root, relid, stats,
+											  clauses, conditions);
 
-		if (mvstat != NULL)	/* we have a matching stats */
+		/*
+		 * We have a good solution, which is merely a list of statistics that
+		 * we need to apply. We'll apply the statistics one by one (in the order
+		 * as they appear in the list), and for each statistic we'll
+		 *
+		 * (1) find clauses compatible with the statistic (and remove them
+		 *     from the list)
+		 *
+		 * (2) find local conditions compatible with the statistic
+		 *
+		 * (3) do the estimation P(clauses | conditions)
+		 *
+		 * (4) append the estimated clauses to local conditions
+		 *
+		 * continuously modify 
+		 */
+		foreach (s, solution)
 		{
-			/* clauses compatible with multi-variate stats */
-			List	*mvclauses = NIL;
+			MVStatisticInfo *mvstat = (MVStatisticInfo *)lfirst(s);
 
-			/* split the clauselist into regular and mv-clauses */
-			clauses = clauselist_mv_split(root, relid, clauses, &mvclauses,
-										  mvstat, MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST);
+			/* clauses compatible with the statistic we're applying right now */
+			List	*stat_clauses = NIL;
+			List	*stat_conditions = NIL;
 
-			/* we've chosen the histogram to match the clauses */
-			Assert(mvclauses != NIL);
+			/*
+			 * Find clauses and conditions matching the statistic - the clauses
+			 * need to be removed from the list, while conditions should remain
+			 * there (so that we can apply them repeatedly).
+			 */
+			stat_clauses
+				= clauses_matching_statistic(&clauses, mvstat, relid,
+											 MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST,
+											 true);
+
+			stat_conditions
+				= clauses_matching_statistic(&conditions_local, mvstat, relid,
+											 MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST,
+											 false);
+
+			/*
+			 * If we got no clauses to estimate, we've done something wrong,
+			 * either during the optimization, detecting compatible clause, or
+			 * somewhere else.
+			 *
+			 * Also, we need at least two attributes in clauses and conditions.
+			 */
+			Assert(stat_clauses != NIL);
+			Assert(count_mv_attnums(list_union(stat_clauses, stat_conditions),
+								relid, MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST) >= 2);
 
 			/* compute the multivariate stats */
-			s1 *= clauselist_mv_selectivity(root, mvclauses, mvstat);
+			s1 *= clauselist_mv_selectivity(root, mvstat,
+											stat_clauses, stat_conditions,
+											false); /* AND */
+
+			/*
+			 * Add the new clauses to the local conditions, so that we can use
+			 * them for the subsequent statistics. We only add the clauses,
+			 * because the conditions are already there (or should be).
+			 */
+			conditions_local = list_concat(conditions_local, stat_clauses);
 		}
+
+		/* from now on, work only with the 'local' list of conditions */
+		conditions = conditions_local;
 	}
 
 	/*
+	 * If there's exactly one clause, then no use in trying to match up
+	 * pairs, so just go directly to clause_selectivity().
+	 */
+	if (list_length(clauses) == 1)
+		return s1 * clause_selectivity(root, (Node *) linitial(clauses),
+									   varRelid, jointype, sjinfo, conditions);
+
+	/*
 	 * Initial scan over clauses.  Anything that doesn't look like a potential
 	 * rangequery clause gets multiplied into s1 and forgotten. Anything that
 	 * does gets inserted into an rqlist entry.
@@ -264,7 +365,8 @@ clauselist_selectivity(PlannerInfo *root,
 		Selectivity s2;
 
 		/* Always compute the selectivity using clause_selectivity */
-		s2 = clause_selectivity(root, clause, varRelid, jointype, sjinfo);
+		s2 = clause_selectivity(root, clause, varRelid, jointype, sjinfo,
+								conditions);
 
 		/*
 		 * Check for being passed a RestrictInfo.
@@ -423,6 +525,55 @@ clauselist_selectivity(PlannerInfo *root,
 }
 
 /*
+ * Similar to clauselist_selectivity(), but for OR-clauses. We can't simply use
+ * the same multi-statistic estimation logic for AND-clauses, at least not
+ * directly, because there are a few key differences:
+ *
+ *   - functional dependencies don't really apply to OR-clauses
+ *
+ *   - clauselist_selectivity() is based on decomposing the selectivity into
+ *     a sequence of conditional probabilities (selectivities), but that can
+ *     be done only for AND-clauses
+ *
+ * We might invent a similar infrastructure for optimizing OR-clauses, doing
+ * something similar to what clause_selectivity does for AND-clauses, but
+ * luckily we know that each disjunctive normal form (aka OR-clause)
+ *
+ *     (a OR b OR c)
+ *
+ * may be rewritten as an equivalent conjunctive normal form (aka AND-clause)
+ * by using negation:
+ *
+ *     NOT ((NOT a) AND (NOT b) AND (NOT c))
+ *
+ * And that's something we can pass to clauselist_selectivity and let it do
+ * all the heavy lifting.
+ */
+static Selectivity
+clauselist_selectivity_or(PlannerInfo *root,
+					   List *clauses,
+					   int varRelid,
+					   JoinType jointype,
+					   SpecialJoinInfo *sjinfo,
+					   List *conditions)
+{
+	List	   *args = NIL;
+	ListCell   *l;
+	Expr	   *expr;
+
+	/* build arguments for the AND-clause by negating args of the OR-clause */
+	foreach (l, clauses)
+		args = lappend(args, makeBoolExpr(NOT_EXPR, list_make1(lfirst(l)), -1));
+
+	/* and then the actual OR-clause on the negated args */
+	expr = makeBoolExpr(AND_EXPR, args, -1);
+
+	/* instead of constructing NOT expression, just do (1.0 - s) */
+	return 1.0 - clauselist_selectivity(root, list_make1(expr), varRelid,
+										jointype, sjinfo, conditions);
+}
+
+/*
  * addRangeClause --- add a new range clause for clauselist_selectivity
  *
  * Here is where we try to match up pairs of range-query clauses
@@ -629,7 +780,8 @@ clause_selectivity(PlannerInfo *root,
 				   Node *clause,
 				   int varRelid,
 				   JoinType jointype,
-				   SpecialJoinInfo *sjinfo)
+				   SpecialJoinInfo *sjinfo,
+				   List *conditions)
 {
 	Selectivity s1 = 0.5;		/* default for any unhandled clause type */
 	RestrictInfo *rinfo = NULL;
@@ -749,7 +901,8 @@ clause_selectivity(PlannerInfo *root,
 								  (Node *) get_notclausearg((Expr *) clause),
 									  varRelid,
 									  jointype,
-									  sjinfo);
+									  sjinfo,
+									  conditions);
 	}
 	else if (and_clause(clause))
 	{
@@ -758,29 +911,18 @@ clause_selectivity(PlannerInfo *root,
 									((BoolExpr *) clause)->args,
 									varRelid,
 									jointype,
-									sjinfo);
+									sjinfo,
+									conditions);
 	}
 	else if (or_clause(clause))
 	{
-		/*
-		 * Selectivities for an OR clause are computed as s1+s2 - s1*s2 to
-		 * account for the probable overlap of selected tuple sets.
-		 *
-		 * XXX is this too conservative?
-		 */
-		ListCell   *arg;
-
-		s1 = 0.0;
-		foreach(arg, ((BoolExpr *) clause)->args)
-		{
-			Selectivity s2 = clause_selectivity(root,
-												(Node *) lfirst(arg),
-												varRelid,
-												jointype,
-												sjinfo);
-
-			s1 = s1 + s2 - s1 * s2;
-		}
+		/* just call to clauselist_selectivity_or() */
+		s1 = clauselist_selectivity_or(root,
+									((BoolExpr *) clause)->args,
+									varRelid,
+									jointype,
+									sjinfo,
+									conditions);
 	}
 	else if (is_opclause(clause) || IsA(clause, DistinctExpr))
 	{
@@ -870,7 +1012,8 @@ clause_selectivity(PlannerInfo *root,
 								(Node *) ((RelabelType *) clause)->arg,
 								varRelid,
 								jointype,
-								sjinfo);
+								sjinfo,
+								conditions);
 	}
 	else if (IsA(clause, CoerceToDomain))
 	{
@@ -879,7 +1022,8 @@ clause_selectivity(PlannerInfo *root,
 								(Node *) ((CoerceToDomain *) clause)->arg,
 								varRelid,
 								jointype,
-								sjinfo);
+								sjinfo,
+								conditions);
 	}
 	else
 	{
@@ -943,15 +1087,16 @@ clause_selectivity(PlannerInfo *root,
  *          in the MCV list, then the selectivity is below the lowest frequency
  *          found in the MCV list,
  *
- * TODO When applying the clauses to the histogram/MCV list, we can do
- *      that from the most selective clauses first, because that'll
- *      eliminate the buckets/items sooner (so we'll be able to skip
- *      them without inspection, which is more expensive). But this
- *      requires really knowing the per-clause selectivities in advance,
- *      and that's not what we do now.
+ * TODO When applying the clauses to the histogram/MCV list, we can do that from
+ *      the most selective clauses first, because that'll eliminate the
+ *      buckets/items sooner (so we'll be able to skip them without inspection,
+ *      which is more expensive). But this requires really knowing the
+ *      per-clause selectivities in advance, and that's not what we do now.
+ *
  */
 static Selectivity
-clauselist_mv_selectivity(PlannerInfo *root, List *clauses, MVStatisticInfo *mvstats)
+clauselist_mv_selectivity(PlannerInfo *root, MVStatisticInfo *mvstats,
+						  List *clauses, List *conditions, bool is_or)
 {
 	bool fullmatch = false;
 	Selectivity s1 = 0.0, s2 = 0.0;
@@ -969,7 +1114,8 @@ clauselist_mv_selectivity(PlannerInfo *root, List *clauses, MVStatisticInfo *mvs
 	 */
 
 	/* Evaluate the MCV first. */
-	s1 = clauselist_mv_selectivity_mcvlist(root, clauses, mvstats,
+	s1 = clauselist_mv_selectivity_mcvlist(root, mvstats,
+										   clauses, conditions, is_or,
 										   &fullmatch, &mcv_low);
 
 	/*
@@ -982,7 +1128,8 @@ clauselist_mv_selectivity(PlannerInfo *root, List *clauses, MVStatisticInfo *mvs
 	/* TODO if (fullmatch) without matching MCV item, use the mcv_low
 	 *      selectivity as upper bound */
 
-	s2 = clauselist_mv_selectivity_histogram(root, clauses, mvstats);
+	s2 = clauselist_mv_selectivity_histogram(root, mvstats,
+											 clauses, conditions, is_or);
 
 	/* TODO clamp to <= 1.0 (or more strictly, when possible) */
 	return s1 + s2;
@@ -1016,260 +1163,1325 @@ get_varattnos(Node * node, Index relid)
 								 k + FirstLowInvalidHeapAttributeNumber);
 	}
 
-	bms_free(varattnos);
+	bms_free(varattnos);
+
+	return result;
+}
+
+/*
+ * Collect attributes from mv-compatible clauses.
+ */
+static Bitmapset *
+collect_mv_attnums(List *clauses, Index relid, int types)
+{
+	Bitmapset  *attnums = NULL;
+	ListCell   *l;
+
+	/*
+	 * Walk through the clauses and identify the ones we can estimate
+	 * using multivariate stats, and remember the relid/columns. We'll
+	 * then cross-check if we have suitable stats, and only if needed
+	 * we'll split the clauses into multivariate and regular lists.
+	 *
+	 * For now we're only interested in RestrictInfo nodes with nested
+	 * OpExpr, using either a range or equality.
+	 */
+	foreach (l, clauses)
+	{
+		Node	   *clause = (Node *) lfirst(l);
+
+		/* ignore the result here - we only need the attnums */
+		clause_is_mv_compatible(clause, relid, &attnums, types);
+	}
+
+	/*
+	 * If there are not at least two attributes referenced by the clause(s),
+	 * we can throw everything out (as we'll revert to simple stats).
+	 */
+	if (bms_num_members(attnums) <= 1)
+	{
+		bms_free(attnums);
+		attnums = NULL;
+	}
+
+	return attnums;
+}
+
+/*
+ * Count the number of attributes in clauses compatible with multivariate stats.
+ */
+static int
+count_mv_attnums(List *clauses, Index relid, int type)
+{
+	int c;
+	Bitmapset *attnums = collect_mv_attnums(clauses, relid, type);
+
+	c = bms_num_members(attnums);
+
+	bms_free(attnums);
+
+	return c;
+}
+
+/*
+ * Count varnos referenced in the clauses, and if there's a single varno then
+ * return the index in 'relid'.
+ */
+static int
+count_varnos(List *clauses, Index *relid)
+{
+	int cnt;
+	Bitmapset *varnos = NULL;
+
+	varnos = pull_varnos((Node *) clauses);
+	cnt = bms_num_members(varnos);
+
+	/* if there's a single varno in the clauses, remember it */
+	if (bms_num_members(varnos) == 1)
+		*relid = bms_singleton_member(varnos);
+
+	bms_free(varnos);
+
+	return cnt;
+}
+
+static List *
+clauses_matching_statistic(List **clauses, MVStatisticInfo *statistic,
+						   Index relid, int types, bool remove)
+{
+	int i;
+	Bitmapset  *stat_attnums = NULL;
+	List	   *matching_clauses = NIL;
+	ListCell   *lc;
+
+	/* build attnum bitmapset for this statistics */
+	for (i = 0; i < statistic->stakeys->dim1; i++)
+		stat_attnums = bms_add_member(stat_attnums,
+									  statistic->stakeys->values[i]);
+
+	/*
+	 * We can't use foreach here, because we may need to remove some of the
+	 * clauses if (remove=true).
+	 */
+	lc = list_head(*clauses);
+	while (lc)
+	{
+		Node *clause = (Node*)lfirst(lc);
+		Bitmapset *attnums = NULL;
+
+		/* must advance lc before list_delete possibly pfree's it */
+		lc = lnext(lc);
+
+		/*
+		 * skip clauses that are not compatible with stats (just leave them
+		 * in the original list)
+		 *
+		 * XXX Perhaps this should check what stats are actually available in
+		 *     the statistics (not a big deal now, because MCV and histograms
+		 *     handle the same types of conditions).
+		 */
+		if (! clause_is_mv_compatible(clause, relid, &attnums, types))
+		{
+			bms_free(attnums);
+			continue;
+		}
+
+		/* if the clause is covered by the statistic, add it to the list */
+		if (bms_is_subset(attnums, stat_attnums))
+		{
+			matching_clauses = lappend(matching_clauses, clause);
+
+			/* if remove=true, remove the matching item from the main list */
+			if (remove)
+				*clauses = list_delete_ptr(*clauses, clause);
+		}
+
+		bms_free(attnums);
+	}
+
+	bms_free(stat_attnums);
+
+	return matching_clauses;
+}
+
+/*
+ * Selects the best combination of multivariate statistics, in an exhaustive
+ * way, where 'best' means:
+ *
+ * (a) covering the most attributes (referenced by clauses)
+ * (b) using the least number of multivariate stats
+ * (c) using the most conditions to exploit dependency
+ *
+ * Don't call this directly but through choose_mv_statistics(), which does some
+ * additional tricks to minimize the runtime.
+ *
+ *
+ * Algorithm
+ * ---------
+ * The algorithm is a recursive implementation of backtracking, with maximum
+ * depth equal to the number of multi-variate statistics available on the table.
+ * It actually explores all valid combinations of stats.
+ * 
+ * Whenever it considers adding the next statistics, the clauses it matches are
+ * divided into 'conditions' (clauses already matched by at least one previous
+ * statistics) and clauses that are estimated.
+ *
+ * Then several checks are performed:
+ *
+ *  (a) The statistics covers at least 2 columns, referenced in the estimated
+ *      clauses (otherwise multi-variate stats are useless).
+ *
+ *  (b) The statistics covers at least 1 new column, i.e. column not refefenced
+ *      by the already used stats (and the new column has to be referenced by
+ *      the clauses, of couse). Otherwise the statistics would not add any new
+ *      information.
+ *
+ * There are some other sanity checks (e.g. stats must not be used twice etc.).
+ *
+ *
+ * Weaknesses
+ * ----------
+ * The current implemetation uses a rather simple optimality criteria, so it may
+ * not do the best choice when
+ *
+ * (a) There may be multiple solutions with the same number of covered
+ *     attributes and number of statistics (e.g. the same solution but with
+ *     statistics in a different order). It's unclear which solution in the best
+ *     one - in a sense all of them are equal.
+ *
+ * TODO It might be possible to compute estimate for each of those solutions,
+ *      and then combine them to get the final estimate (e.g. by using average
+ *      or median).
+ *
+ * (b) Does not consider that some types of stats are a better match for some
+ *     types of clauses (e.g. MCV list is generally a better match for equality
+ *     conditions than a histogram).
+ *
+ *     But maybe this is pointless - generally, each column is either a label
+ *     (it's not important whether because of the data type or how it's used),
+ *     or a value with ordering that makes sense. So either a MCV list is more
+ *     appropriate (labels) or a histogram (values with orderings).
+ *
+ *     Now sure what to do with statistics on columns mixing both types of data
+ *     (some columns would work best with MCVs, some with histograms). Maybe we
+ *     could invent a new type of statistics combining MCV list and histogram
+ *     (keeping a small histogram for each MCV item, and a separate histogram
+ *     for values not on the MCV list).
+ *
+ * TODO The algorithm should probably count number of Vars (not just attnums)
+ *      when computing the 'score' of each solution. Computing the ratio of
+ *      (num of all vars) / (num of condition vars) as a measure of how well
+ *      the solution uses conditions might be useful.
+ */
+static void
+choose_mv_statistics_exhaustive(PlannerInfo *root, int step,
+					int nmvstats, MVStatisticInfo *mvstats, Bitmapset ** stats_attnums,
+					int nclauses, Node ** clauses, Bitmapset ** clauses_attnums,
+					int nconditions, Node ** conditions, Bitmapset ** conditions_attnums,
+					bool *cover_map, bool *condition_map, int *ruled_out,
+					mv_solution_t *current, mv_solution_t **best)
+{
+	int i, j;
+
+	Assert(best != NULL);
+	Assert((step == 0 && current == NULL) || (step > 0 && current != NULL));
+
+	/* this may run for a long sime, so let's make it interruptible */
+	CHECK_FOR_INTERRUPTS();
+
+	if (current == NULL)
+	{
+		current = (mv_solution_t*)palloc0(sizeof(mv_solution_t));
+		current->stats = (int*)palloc0(sizeof(int)*nmvstats);
+		current->nstats = 0;
+		current->nclauses = 0;
+		current->nconditions = 0;
+	}
+
+	/*
+	 * Now try to apply each statistics, matching at least two attributes,
+	 * unless it's already used in one of the previous steps.
+	 */
+	for (i = 0; i < nmvstats; i++)
+	{
+		int c;
+
+		int ncovered_clauses = 0;		/* number of covered clauses */
+		int ncovered_conditions = 0;	/* number of covered conditions */
+		int nattnums = 0;		/* number of covered attributes */
+
+		Bitmapset  *all_attnums = NULL;
+		Bitmapset  *new_attnums = NULL;
+
+		/* skip statistics that were already used or eliminated */
+		if (ruled_out[i] != -1)
+			continue;
+
+		/*
+		 * See if we have clauses covered by this statistics, but not
+		 * yet covered by any of the preceding onces.
+		 */
+		for (c = 0; c < nclauses; c++)
+		{
+			bool covered = false;
+			Bitmapset *clause_attnums = clauses_attnums[c];
+			Bitmapset *tmp = NULL;
+
+			/*
+			 * If this clause is not covered by this stats, we can't
+			 * use the stats to estimate that at all.
+			 */
+			if (! cover_map[i * nclauses + c])
+				continue;
+
+			/*
+			 * Now we know we'll use this clause - either as a condition
+			 * or as a new clause (the estimated one). So let's add the
+			 * attributes to the attnums from all the clauses usable with
+			 * this statistics.
+			 */
+			tmp = bms_union(all_attnums, clause_attnums);
+
+			/* free the old bitmap */
+			bms_free(all_attnums);
+			all_attnums = tmp;
+
+			/* let's see if it's covered by any of the previous stats */
+			for (j = 0; j < step; j++)
+			{
+				/* already covered by the previous stats */
+				if (cover_map[current->stats[j] * nclauses + c])
+					covered = true;
+
+				if (covered)
+					break;
+			}
+
+			/* if already covered, continue with the next clause */
+			if (covered)
+			{
+				ncovered_conditions += 1;
+				continue;
+			}
+
+			/*
+			 * OK, this clause is covered by this statistics (and not by
+			 * any of the previous ones)
+			 */
+			ncovered_clauses += 1;
+
+			/* add the attnums into attnums from 'new clauses' */
+			// new_attnums = bms_union(new_attnums, clause_attnums);
+		}
+
+		/* can't have more new clauses than original clauses */
+		Assert(nclauses >= ncovered_clauses);
+		Assert(ncovered_clauses >= 0);	/* mostly paranoia */
+
+		nattnums = bms_num_members(all_attnums);
+
+		/* free all the bitmapsets - we don't need them anymore */
+		bms_free(all_attnums);
+		bms_free(new_attnums);
+
+		all_attnums = NULL;
+		new_attnums = NULL;
+
+		/*
+		 * See if we have clauses covered by this statistics, but not
+		 * yet covered by any of the preceding onces.
+		 */
+		for (c = 0; c < nconditions; c++)
+		{
+			Bitmapset *clause_attnums = conditions_attnums[c];
+			Bitmapset *tmp = NULL;
+
+			/*
+			 * If this clause is not covered by this stats, we can't
+			 * use the stats to estimate that at all.
+			 */
+			if (! condition_map[i * nconditions + c])
+				continue;
+
+			/* count this as a condition */
+			ncovered_conditions += 1;
+
+			/*
+			 * Now we know we'll use this clause - either as a condition
+			 * or as a new clause (the estimated one). So let's add the
+			 * attributes to the attnums from all the clauses usable with
+			 * this statistics.
+			 */
+			tmp = bms_union(all_attnums, clause_attnums);
+
+			/* free the old bitmap */
+			bms_free(all_attnums);
+			all_attnums = tmp;
+		}
+
+		/*
+		 * Let's mark the statistics as 'ruled out' - either we'll use
+		 * it (and proceed to the next step), or it's incompatible.
+		 */
+		ruled_out[i] = step;
+
+		/*
+		 * There are no clauses usable with this statistics (not already
+		 * covered by aome of the previous stats).
+		 *
+		 * Similarly, if the clauses only use a single attribute, we
+		 * can't really use that.
+		 */
+		if ((ncovered_clauses == 0) || (nattnums < 2))
+			continue;
+
+		/*
+		 * TODO Not sure if it's possible to add a clause referencing
+		 *      only attributes already covered by previous stats?
+		 *      Introducing only some new dependency, not a new
+		 *      attribute. Couldn't come up with an example, though.
+		 *      Might be worth adding some assert.
+		 */
+
+		/*
+		 * got a suitable statistics - let's update the current solution,
+		 * maybe use it as the best solution
+		 */
+		current->nclauses += ncovered_clauses;
+		current->nconditions += ncovered_conditions;
+		current->nstats += 1;
+		current->stats[step] = i;
+
+		/*
+		 * We can never cover more clauses, or use more stats that we
+		 * actually have at the beginning.
+		 */
+		Assert(nclauses >= current->nclauses);
+		Assert(nmvstats >= current->nstats);
+		Assert(step < nmvstats);
+
+		if (*best == NULL)
+		{
+			*best = (mv_solution_t*)palloc0(sizeof(mv_solution_t));
+			(*best)->stats = (int*)palloc0(sizeof(int)*nmvstats);
+			(*best)->nstats = 0;
+			(*best)->nclauses = 0;
+			(*best)->nconditions = 0;
+		}
+
+		/* see if it's better than the current 'best' solution */
+		if ((current->nclauses > (*best)->nclauses) ||
+			((current->nclauses == (*best)->nclauses) &&
+			((current->nstats > (*best)->nstats))))
+		{
+			(*best)->nstats = current->nstats;
+			(*best)->nclauses = current->nclauses;
+			(*best)->nconditions = current->nconditions;
+			memcpy((*best)->stats, current->stats, nmvstats * sizeof(int));
+		}
+
+		/*
+		 * The recursion only makes sense if we haven't covered all the
+		 * attributes (then adding stats is not really possible).
+		 */
+		if ((step + 1) < nmvstats)
+			choose_mv_statistics_exhaustive(root, step+1,
+									nmvstats, mvstats, stats_attnums,
+									nclauses, clauses, clauses_attnums,
+									nconditions, conditions, conditions_attnums,
+									cover_map, condition_map, ruled_out,
+									current, best);
+
+		/* reset the last step */
+		current->nclauses -= ncovered_clauses;
+		current->nconditions -= ncovered_conditions;
+		current->nstats -= 1;
+		current->stats[step] = 0;
+
+		/* mark the statistics as usable again */
+		ruled_out[i] = -1;
+
+		Assert(current->nclauses >= 0);
+		Assert(current->nstats >= 0);
+	}
+
+	/* reset all statistics as 'incompatible' in this step */
+	for (i = 0; i < nmvstats; i++)
+		if (ruled_out[i] == step)
+			ruled_out[i] = -1;
+
+}
+
+/*
+ * Greedy search for a multivariate solution - a sequence of statistics covering
+ * the clauses. This chooses the "best" statistics at each step, so the
+ * resulting solution may not be the best solution globally, but this produces
+ * the solution in only N steps (where N is the number of statistics), while
+ * the exhaustive approach may have to walk through ~N! combinations (although
+ * some of those are terminated early).
+ *
+ * See the comments at choose_mv_statistics_exhaustive() as this does the same
+ * thing (but in a different way).
+ *
+ * Don't call this directly, but through choose_mv_statistics().
+ *
+ * TODO There are probably other metrics we might use - e.g. using number of
+ *      columns (num_cond_columns / num_cov_columns), which might work better
+ *      with a mix of simple and complex clauses.
+ *
+ * TODO Also the choice at the very first step should be handled in a special
+ *      way, because there will be 0 conditions at that moment, so there needs
+ *      to be some other criteria - e.g. using the simplest (or most complex?)
+ *      clause might be a good idea.
+ *
+ * TODO We might also select multiple stats using different criteria, and branch
+ *      the search. This is however tricky, because if we choose k statistics at
+ *      each step, we get k^N branches to walk through (with N steps). That's
+ *      not really good with large number of stats (yet better than exhaustive
+ *      search).
+ */
+static void
+choose_mv_statistics_greedy(PlannerInfo *root, int step,
+					int nmvstats, MVStatisticInfo *mvstats, Bitmapset ** stats_attnums,
+					int nclauses, Node ** clauses, Bitmapset ** clauses_attnums,
+					int nconditions, Node ** conditions, Bitmapset ** conditions_attnums,
+					bool *cover_map, bool *condition_map, int *ruled_out,
+					mv_solution_t *current, mv_solution_t **best)
+{
+	int i, j;
+	int best_stat = -1;
+	double gain, max_gain = -1.0;
+
+	/*
+	 * Bitmap tracking which clauses are already covered (by the previous
+	 * statistics) and may thus serve only as a condition in this step.
+	 */
+	bool *covered_clauses = (bool*)palloc0(nclauses);
+
+	/*
+	 * Number of clauses and columns covered by each statistics - this
+	 * includes both conditions and clauses covered by the statistics for
+	 * the first time. The number of columns may count some columns
+	 * repeatedly - if a column is shared by multiple clauses, it will
+	 * be counted once for each clause (covered by the statistics).
+	 * So with two clauses [(a=1 OR b=2),(a<2 OR c>1)] the column "a"
+	 * will be counted twice (if both clauses are covered).
+	 *
+	 * The values for reduded statistics (that can't be applied) are
+	 * not computed, because that'd be pointless.
+	 */
+	int	*num_cov_clauses	= (int*)palloc0(sizeof(int) * nmvstats);
+	int	*num_cov_columns	= (int*)palloc0(sizeof(int) * nmvstats);
+
+	/*
+	 * Same as above, but this only includes clauses that are already
+	 * covered by the previous stats (and the current one).
+	 */
+	int	*num_cond_clauses	= (int*)palloc0(sizeof(int) * nmvstats);
+	int	*num_cond_columns	= (int*)palloc0(sizeof(int) * nmvstats);
+
+	/*
+	 * Number of attributes for each clause.
+	 *
+	 * TODO Might be computed in choose_mv_statistics() and then passed
+	 *      here, but then the function would not have the same signature
+	 *      as _exhaustive().
+	 */
+	int *attnum_counts = (int*)palloc0(sizeof(int) * nclauses);
+	int *attnum_cond_counts = (int*)palloc0(sizeof(int) * nconditions);
+
+	CHECK_FOR_INTERRUPTS();
+
+	Assert(best != NULL);
+	Assert((step == 0 && current == NULL) || (step > 0 && current != NULL));
+
+	/* compute attributes (columns) for each clause */
+	for (i = 0; i < nclauses; i++)
+		attnum_counts[i] = bms_num_members(clauses_attnums[i]);
+
+	/* compute attributes (columns) for each condition */
+	for (i = 0; i < nconditions; i++)
+		attnum_cond_counts[i] = bms_num_members(conditions_attnums[i]);
+
+	/* see which clauses are already covered at this point (by previous stats) */
+	for (i = 0; i < step; i++)
+		for (j = 0; j < nclauses; j++)
+			covered_clauses[j] |= (cover_map[current->stats[i] * nclauses + j]);
+
+	/* which remaining statistics covers most clauses / uses most conditions? */
+	for (i = 0; i < nmvstats; i++)
+	{
+		Bitmapset *attnums_covered = NULL;
+		Bitmapset *attnums_conditions = NULL;
+
+		/* skip stats that are already ruled out (either used or inapplicable) */
+		if (ruled_out[i] != -1)
+			continue;
+
+		/* count covered clauses and conditions (for the statistics) */
+		for (j = 0; j < nclauses; j++)
+		{
+			if (cover_map[i * nclauses + j])
+			{
+				Bitmapset *attnums_new
+					= bms_union(attnums_covered, clauses_attnums[j]);
+
+				/* get rid of the old bitmap and keep the unified result */
+				bms_free(attnums_covered);
+				attnums_covered = attnums_new;
+
+				num_cov_clauses[i] += 1;
+				num_cov_columns[i] += attnum_counts[j];
+
+				/* is the clause already covered (i.e. a condition)? */
+				if (covered_clauses[j])
+				{
+					num_cond_clauses[i] += 1;
+					num_cond_columns[i] += attnum_counts[j];
+					attnums_new = bms_union(attnums_conditions,
+											clauses_attnums[j]);
+
+					bms_free(attnums_conditions);
+					attnums_conditions = attnums_new;
+				}
+			}
+		}
+
+		/* if all covered clauses are covered by prev stats (thus conditions) */
+		if (num_cov_clauses[i] == num_cond_clauses[i])
+			ruled_out[i] = step;
+
+		/* same if there are no new attributes */
+		else if (bms_num_members(attnums_conditions) == bms_num_members(attnums_covered))
+			ruled_out[i] = step;
+
+		bms_free(attnums_covered);
+		bms_free(attnums_conditions);
+
+		/* if the statistics is inapplicable, try the next one */
+		if (ruled_out[i] != -1)
+			continue;
+
+		/* now let's walk through conditions and count the covered */
+		for (j = 0; j < nconditions; j++)
+		{
+			if (condition_map[i * nconditions + j])
+			{
+				num_cond_clauses[i] += 1;
+				num_cond_columns[i] += attnum_cond_counts[j];
+			}
+		}
+
+		/* otherwise see if this improves the interesting metrics */
+		gain = num_cond_columns[i] / (double)num_cov_columns[i];
+
+		if (gain > max_gain)
+		{
+			max_gain = gain;
+			best_stat = i;
+		}
+	}
+
+	/*
+	 * Have we found a suitable statistics? Add it to the solution and
+	 * try next step.
+	 */
+	if (best_stat != -1)
+	{
+		/* mark the statistics, so that we skip it in next steps */
+		ruled_out[best_stat] = step;
+
+		/* allocate current solution if necessary */
+		if (current == NULL)
+		{
+			current = (mv_solution_t*)palloc0(sizeof(mv_solution_t));
+			current->stats = (int*)palloc0(sizeof(int)*nmvstats);
+			current->nstats = 0;
+			current->nclauses = 0;
+			current->nconditions = 0;
+		}
+
+		current->nclauses += num_cov_clauses[best_stat];
+		current->nconditions += num_cond_clauses[best_stat];
+		current->stats[step] = best_stat;
+		current->nstats++;
+
+		if (*best == NULL)
+		{
+			(*best) = (mv_solution_t*)palloc0(sizeof(mv_solution_t));
+			(*best)->nstats = current->nstats;
+			(*best)->nclauses = current->nclauses;
+			(*best)->nconditions = current->nconditions;
+
+			(*best)->stats = (int*)palloc0(sizeof(int)*nmvstats);
+			memcpy((*best)->stats, current->stats, nmvstats * sizeof(int));
+		}
+		else
+		{
+			/* see if this is a better solution */
+			double current_gain = (double)current->nconditions / current->nclauses;
+			double best_gain    = (double)(*best)->nconditions / (*best)->nclauses;
+
+			if ((current_gain > best_gain) ||
+				((current_gain == best_gain) && (current->nstats < (*best)->nstats)))
+			{
+				(*best)->nstats = current->nstats;
+				(*best)->nclauses = current->nclauses;
+				(*best)->nconditions = current->nconditions;
+				memcpy((*best)->stats, current->stats, nmvstats * sizeof(int));
+			}
+		}
+
+		/*
+		 * The recursion only makes sense if we haven't covered all the
+		 * attributes (then adding stats is not really possible).
+		*/
+		if ((step + 1) < nmvstats)
+			choose_mv_statistics_greedy(root, step+1,
+									nmvstats, mvstats, stats_attnums,
+									nclauses, clauses, clauses_attnums,
+									nconditions, conditions, conditions_attnums,
+									cover_map, condition_map, ruled_out,
+									current, best);
+
+		/* reset the last step */
+		current->nclauses -= num_cov_clauses[best_stat];
+		current->nconditions -= num_cond_clauses[best_stat];
+		current->nstats -= 1;
+		current->stats[step] = 0;
+
+		/* mark the statistics as usable again */
+		ruled_out[best_stat] = -1;
+	}
+
+	/* reset all statistics eliminated in this step */
+	for (i = 0; i < nmvstats; i++)
+		if (ruled_out[i] == step)
+			ruled_out[i] = -1;
+
+	/* free everything allocated in this step */
+	pfree(covered_clauses);
+	pfree(attnum_counts);
+	pfree(num_cov_clauses);
+	pfree(num_cov_columns);
+	pfree(num_cond_clauses);
+	pfree(num_cond_columns);
+}
+
+/*
+ * Remove clauses not covered by any of the available statistics
+ *
+ * This helps us to reduce the amount of work done in choose_mv_statistics()
+ * by not having to deal with clauses that can't possibly be useful.
+ */
+static List *
+filter_clauses(PlannerInfo *root, Index relid, int type,
+			   List *stats, List *clauses, Bitmapset **attnums)
+{
+	ListCell   *c;
+	ListCell   *s;
+
+	/* results (list of compatible clauses, attnums) */
+	List	   *rclauses = NIL;
+
+	foreach (c, clauses)
+	{
+		Node *clause = (Node*)lfirst(c);
+		Bitmapset *clause_attnums = NULL;
+
+		/*
+		 * We do assume that thanks to previous checks, we should not run into
+		 * clauses that are incompatible with multivariate stats here. We also
+		 * need to collect the attnums for the clause.
+		 *
+		 * XXX Maybe turn this into an assert?
+		 */
+		if (! clause_is_mv_compatible(clause, relid, &clause_attnums, type))
+				elog(ERROR, "should not get non-mv-compatible cluase");
+
+		/* Is there a multivariate statistics covering the clause? */
+		foreach (s, stats)
+		{
+			int k, matches = 0;
+			MVStatisticInfo	*stat = (MVStatisticInfo *)lfirst(s);
+
+			/* skip statistics not matching the required type */
+			if (! stats_type_matches(stat, type))
+				continue;
+
+			/*
+			 * see if all clause attributes are covered by the statistic
+			 *
+			 * We'll do that in the opposite direction, i.e. we'll see how many
+			 * attributes of the statistic are referenced in the clause, and then
+			 * compare the counts.
+			 */
+			for (k = 0; k < stat->stakeys->dim1; k++)
+				if (bms_is_member(stat->stakeys->values[k], clause_attnums))
+					matches += 1;
+
+			/*
+			 * If the number of matches is equal to attributes referenced by the
+			 * clause, then the clause is covered by the statistic.
+			 */
+			if (bms_num_members(clause_attnums) == matches)
+			{
+				*attnums = bms_union(*attnums, clause_attnums);
+				rclauses = lappend(rclauses, clause);
+				break;
+			}
+		}
+
+		bms_free(clause_attnums);
+	}
+
+	/* we can't have more compatible conditions than source conditions */
+	Assert(list_length(clauses) >= list_length(rclauses));
+
+	return rclauses;
+}
+
+/*
+ * Remove statistics not covering any new clauses
+ *
+ * Statistics not covering any new clauses (conditions don't count) are not
+ * really useful, so let's ignore them. Also, we need the statistics to
+ * reference at least two different attributes (both in conditions and clauses
+ * combined), and at least one of them in the clauses alone.
+ *
+ * This check might be made more strict by checking against individual clauses,
+ * because by using the bitmapsets of all attnums we may actually use attnums
+ * from clauses that are not covered by the statistics. For example, we may
+ * have a condition
+ *
+ *    (a=1 AND b=2)
+ *
+ * and a new clause
+ *
+ *    (c=1 AND d=1)
+ *
+ * With only bitmapsets, statistics on [b,c] will pass through this (assuming
+ * there are some statistics covering both clases).
+ *
+ * Parameters:
+ *
+ *     stats       - list of statistics to filter
+ *     new_attnums - attnums referenced in new clauses
+ *     all_attnums - attnums referenced by contidions and new clauses combined
+ *
+ * Returns filtered list of statistics.
+ *
+ * TODO Do the more strict check, i.e. walk through individual clauses and
+ *      conditions and only use those covered by the statistics.
+ */
+static List *
+filter_stats(List *stats, Bitmapset *new_attnums, Bitmapset *all_attnums)
+{
+	ListCell   *s;
+	List	   *stats_filtered = NIL;
+
+	foreach (s, stats)
+	{
+		int k;
+		int matches_new = 0,
+			matches_all = 0;
+
+		MVStatisticInfo	*stat = (MVStatisticInfo *)lfirst(s);
+
+		/* see how many attributes the statistics covers */
+		for (k = 0; k < stat->stakeys->dim1; k++)
+		{
+			/* attributes from new clauses */
+			if (bms_is_member(stat->stakeys->values[k], new_attnums))
+				matches_new += 1;
+
+			/* attributes from onditions */
+			if (bms_is_member(stat->stakeys->values[k], all_attnums))
+				matches_all += 1;
+		}
+
+		/* check we have enough attributes for this statistics */
+		if ((matches_new >= 1) && (matches_all >= 2))
+			stats_filtered = lappend(stats_filtered, stat);
+	}
+
+	/* we can't have more useful stats than we had originally */
+	Assert(list_length(stats) >= list_length(stats_filtered));
+
+	return stats_filtered;
+}
+
+static MVStatisticInfo *
+make_stats_array(List *stats, int *nmvstats)
+{
+	int i;
+	ListCell   *l;
+
+	MVStatisticInfo *mvstats = NULL;
+	*nmvstats = list_length(stats);
+
+	mvstats
+		= (MVStatisticInfo*)palloc0((*nmvstats) * sizeof(MVStatisticInfo));
+
+	i = 0;
+	foreach (l, stats)
+	{
+		MVStatisticInfo	*stat = (MVStatisticInfo *)lfirst(l);
+		memcpy(&mvstats[i++], stat, sizeof(MVStatisticInfo));
+	}
+
+	return mvstats;
+}
+
+static Bitmapset **
+make_stats_attnums(MVStatisticInfo *mvstats, int nmvstats)
+{
+	int			i, j;
+	Bitmapset **stats_attnums = NULL;
+
+	Assert(nmvstats > 0);
 
-	return result;
+	/* build bitmaps of attnums for the stats (easier to compare) */
+	stats_attnums = (Bitmapset **)palloc0(nmvstats * sizeof(Bitmapset*));
+
+	for (i = 0; i < nmvstats; i++)
+		for (j = 0; j < mvstats[i].stakeys->dim1; j++)
+			stats_attnums[i]
+				= bms_add_member(stats_attnums[i],
+								 mvstats[i].stakeys->values[j]);
+
+	return stats_attnums;
 }
 
+
 /*
- * Collect attributes from mv-compatible clauses.
+ * Remove redundant statistics
+ *
+ * If there are multiple statistics covering the same set of columns (counting
+ * only those referenced by clauses and conditions), we can apply one of those
+ * anyway and further reduce the size of the optimization problem.
+ *
+ * Thus when redundant stats are detected, we keep the smaller one (the one with
+ * fewer columns), based on the assumption that it's more accurate and also
+ * faster to process. That may be untrue for two reasons - first, the accuracy
+ * really depends on number of buckets/MCV items, not the number of columns.
+ * Second, some types of statistics may work better for certain types of clauses
+ * (e.g. MCV lists for equality conditions) etc.
  */
-static Bitmapset *
-collect_mv_attnums(List *clauses, Index relid, int types)
+static List*
+filter_redundant_stats(List *stats, List *clauses, List *conditions)
 {
-	Bitmapset  *attnums = NULL;
-	ListCell   *l;
+	int i, j, nmvstats;
+
+	MVStatisticInfo	   *mvstats;
+	bool			   *redundant;
+	Bitmapset		  **stats_attnums;
+	Bitmapset		   *varattnos;
+	Index				relid;
+
+	Assert(list_length(stats) > 0);
+	Assert(list_length(clauses) > 0);
 
 	/*
-	 * Walk through the clauses and identify the ones we can estimate using
-	 * multivariate stats, and remember the relid/columns. We'll then
-	 * cross-check if we have suitable stats, and only if needed we'll split
-	 * the clauses into multivariate and regular lists.
+	 * We'll convert the list of statistics into an array now, because
+	 * the reduction of redundant statistics is easier to do that way
+	 * (we can mark previous stats as redundant, etc.).
+	 */
+	mvstats = make_stats_array(stats, &nmvstats);
+	stats_attnums = make_stats_attnums(mvstats, nmvstats);
+
+	/* by default, none of the stats is redundant (so palloc0) */
+	redundant = palloc0(nmvstats * sizeof(bool));
+
+	/*
+	 * We only expect a single relid here, and also we should get the
+	 * same relid from clauses and conditions (but we get it from
+	 * clauses, because those are certainly non-empty).
+	 */
+	relid = bms_singleton_member(pull_varnos((Node*)clauses));
+
+	/*
+	 * Get the varattnos from both conditions and clauses.
+	 *
+	 * This skips system attributes, although that should be impossible
+	 * thanks to previous filtering out of incompatible clauses.
 	 *
-	 * For now we're only interested in RestrictInfo nodes with nested OpExpr,
-	 * using either a range or equality.
+	 * XXX Is that really true?
 	 */
-	foreach (l, clauses)
+	varattnos = bms_union(get_varattnos((Node*)clauses, relid),
+						  get_varattnos((Node*)conditions, relid));
+
+	for (i = 1; i < nmvstats; i++)
 	{
-		Node	   *clause = (Node *) lfirst(l);
+		/* intersect with current statistics */
+		Bitmapset *curr = bms_intersect(stats_attnums[i], varattnos);
 
-		/* ignore the result here - we only need the attnums */
-		clause_is_mv_compatible(clause, relid, &attnums, types);
+		/* walk through 'previous' stats and check redundancy */
+		for (j = 0; j < i; j++)
+		{
+			/* intersect with current statistics */
+			Bitmapset *prev;
+
+			/* skip stats already identified as redundant */
+			if (redundant[j])
+				continue;
+
+			prev = bms_intersect(stats_attnums[j], varattnos);
+
+			switch (bms_subset_compare(curr, prev))
+			{
+				case BMS_EQUAL:
+					/*
+					 * Use the smaller one (hopefully more accurate).
+					 * If both have the same size, use the first one.
+					 */
+					if (mvstats[i].stakeys->dim1 >= mvstats[j].stakeys->dim1)
+						redundant[i] = TRUE;
+					else
+						redundant[j] = TRUE;
+
+					break;
+
+				case BMS_SUBSET1: /* curr is subset of prev */
+					redundant[i] = TRUE;
+					break;
+
+				case BMS_SUBSET2: /* prev is subset of curr */
+					redundant[j] = TRUE;
+					break;
+
+				case BMS_DIFFERENT:
+					/* do nothing - keep both stats */
+					break;
+			}
+
+			bms_free(prev);
+		}
+
+		bms_free(curr);
 	}
 
-	/*
-	 * If there are not at least two attributes referenced by the clause(s),
-	 * we can throw everything out (as we'll revert to simple stats).
-	 */
-	if (bms_num_members(attnums) <= 1)
+	/* can't reduce all statistics (at least one has to remain) */
+	Assert(nmvstats > 0);
+
+	/* now, let's remove the reduced statistics from the arrays */
+	list_free(stats);
+	stats = NIL;
+
+	for (i = 0; i < nmvstats; i++)
 	{
-		if (attnums != NULL)
-			pfree(attnums);
-		attnums = NULL;
+		MVStatisticInfo *info;
+
+		pfree(stats_attnums[i]);
+
+		if (redundant[i])
+			continue;
+
+		info = makeNode(MVStatisticInfo);
+		memcpy(info, &mvstats[i], sizeof(MVStatisticInfo));
+
+		stats = lappend(stats, info);
 	}
 
-	return attnums;
+	pfree(mvstats);
+	pfree(stats_attnums);
+	pfree(redundant);
+
+	return stats;
 }
 
-/*
- * Count the number of attributes in clauses compatible with multivariate stats.
- */
-static int
-count_mv_attnums(List *clauses, Index relid, int type)
+static Node**
+make_clauses_array(List *clauses, int *nclauses)
 {
-	int c;
-	Bitmapset *attnums = collect_mv_attnums(clauses, relid, type);
+	int i;
+	ListCell *l;
 
-	c = bms_num_members(attnums);
+	Node** clauses_array;
 
-	bms_free(attnums);
+	*nclauses = list_length(clauses);
+	clauses_array = (Node **)palloc0((*nclauses) * sizeof(Node *));
 
-	return c;
+	i = 0;
+	foreach (l, clauses)
+		clauses_array[i++] = (Node *)lfirst(l);
+
+	*nclauses = i;
+
+	return clauses_array;
 }
 
-/*
- * Count varnos referenced in the clauses, and if there's a single varno then
- * return the index in 'relid'.
- */
-static int
-count_varnos(List *clauses, Index *relid)
+static Bitmapset **
+make_clauses_attnums(PlannerInfo *root, Index relid,
+					 int type, Node **clauses, int nclauses)
 {
-	int cnt;
-	Bitmapset *varnos = NULL;
+	int			i;
+	Bitmapset **clauses_attnums
+		= (Bitmapset **)palloc0(nclauses * sizeof(Bitmapset *));
 
-	varnos = pull_varnos((Node *) clauses);
-	cnt = bms_num_members(varnos);
+	for (i = 0; i < nclauses; i++)
+	{
+		Bitmapset * attnums = NULL;
 
-	/* if there's a single varno in the clauses, remember it */
-	if (bms_num_members(varnos) == 1)
-		*relid = bms_singleton_member(varnos);
+		if (! clause_is_mv_compatible(clauses[i], relid, &attnums, type))
+			elog(ERROR, "should not get non-mv-compatible clause");
 
-	bms_free(varnos);
+		clauses_attnums[i] = attnums;
+	}
 
-	return cnt;
+	return clauses_attnums;
 }
- 
+
+static bool*
+make_cover_map(Bitmapset **stats_attnums, int nmvstats,
+			   Bitmapset **clauses_attnums, int nclauses)
+{
+	int		i, j;
+	bool   *cover_map	= (bool*)palloc0(nclauses * nmvstats);
+
+	for (i = 0; i < nmvstats; i++)
+		for (j = 0; j < nclauses; j++)
+			cover_map[i * nclauses + j]
+				= bms_is_subset(clauses_attnums[j], stats_attnums[i]);
+
+	return cover_map;
+}
+
 /*
- * We're looking for statistics matching at least 2 attributes, referenced in
- * clauses compatible with multivariate statistics. The current selection
- * criteria is very simple - we choose the statistics referencing the most
- * attributes.
- *
- * If there are multiple statistics referencing the same number of columns
- * (from the clauses), the one with less source columns (as listed in the
- * ADD STATISTICS when creating the statistics) wins. Else the first one wins.
- *
- * This is a very simple criteria, and has several weaknesses:
- *
- * (a) does not consider the accuracy of the statistics
- *
- *     If there are two histograms built on the same set of columns, but one
- *     has 100 buckets and the other one has 1000 buckets (thus likely
- *     providing better estimates), this is not currently considered.
- *
- * (b) does not consider the type of statistics
- *
- *     If there are three statistics - one containing just a MCV list, another
- *     one with just a histogram and a third one with both, we treat them equally.
+ * Chooses the combination of statistics, optimal for estimation of a particular
+ * clause list.
  *
- * (c) does not consider the number of clauses
+ * This only handles a 'preparation' shared by the exhaustive and greedy
+ * implementations (see the previous methods), mostly trying to reduce the size
+ * of the problem (eliminate clauses/statistics that can't be really used in
+ * the solution).
  *
- *     As explained, only the number of referenced attributes counts, so if
- *     there are multiple clauses on a single attribute, this still counts as
- *     a single attribute.
+ * It also precomputes bitmaps for attributes covered by clauses and statistics,
+ * so that we don't need to do that over and over in the actual optimizations
+ * (as it's both CPU and memory intensive).
  *
- * (d) does not consider type of condition
  *
- *     Some clauses may work better with some statistics - for example equality
- *     clauses probably work better with MCV lists than with histograms. But
- *     IS [NOT] NULL conditions may often work better with histograms (thanks
- *     to NULL-buckets).
+ * TODO Another way to make the optimization problems smaller might be splitting
+ *      the statistics into several disjoint subsets, i.e. if we can split the
+ *      graph of statistics (after the elimination) into multiple components
+ *      (so that stats in different components share no attributes), we can do
+ *      the optimization for each component separately.
  *
- * So for example with five WHERE conditions
- *
- *     WHERE (a = 1) AND (b = 1) AND (c = 1) AND (d = 1) AND (e = 1)
- *
- * and statistics on (a,b), (a,b,e) and (a,b,c,d), the last one will be selected
- * as it references the most columns.
- *
- * Once we have selected the multivariate statistics, we split the list of
- * clauses into two parts - conditions that are compatible with the selected
- * stats, and conditions are estimated using simple statistics.
- *
- * From the example above, conditions
- *
- *     (a = 1) AND (b = 1) AND (c = 1) AND (d = 1)
- *
- * will be estimated using the multivariate statistics (a,b,c,d) while the last
- * condition (e = 1) will get estimated using the regular ones.
- *
- * There are various alternative selection criteria (e.g. counting conditions
- * instead of just referenced attributes), but eventually the best option should
- * be to combine multiple statistics. But that's much harder to do correctly.
- *
- * TODO Select multiple statistics and combine them when computing the estimate.
- *
- * TODO This will probably have to consider compatibility of clauses, because
- *      'dependencies' will probably work only with equality clauses.
+ * TODO If we could compute what is a "perfect solution" maybe we could
+ *      terminate the search after reaching ~90% of it? Say, if we knew that we
+ *      can cover 10 clauses and reuse 8 dependencies, maybe covering 9 clauses
+ *      and 7 dependencies would be OK?
  */
-static MVStatisticInfo *
-choose_mv_statistics(List *stats, Bitmapset *attnums)
+static List*
+choose_mv_statistics(PlannerInfo *root, Index relid, List *stats,
+					 List *clauses, List *conditions)
 {
 	int i;
-	ListCell   *lc;
+	mv_solution_t *best = NULL;
+	List *result = NIL;
+
+	int nmvstats;
+	MVStatisticInfo *mvstats;
+
+	/* we only work with MCV lists and histograms here */
+	int type = (MV_CLAUSE_TYPE_MCV | MV_CLAUSE_TYPE_HIST);
+
+	bool   *clause_cover_map = NULL,
+		   *condition_cover_map = NULL;
+	int	   *ruled_out = NULL;
+
+	/* build bitmapsets for all stats and clauses */
+	Bitmapset **stats_attnums;
+	Bitmapset **clauses_attnums;
+	Bitmapset **conditions_attnums;
 
-	MVStatisticInfo *choice = NULL;
+	int nclauses, nconditions;
+	Node ** clauses_array;
+	Node ** conditions_array;
 
-	int current_matches = 1;						/* goal #1: maximize */
-	int current_dims = (MVSTATS_MAX_DIMENSIONS+1);	/* goal #2: minimize */
+	/* copy lists, so that we can free them during elimination easily */
+	clauses = list_copy(clauses);
+	conditions = list_copy(conditions);
+	stats = list_copy(stats);
 
 	/*
-	 * Walk through the statistics (simple array with nmvstats elements) and for
-	 * each one count the referenced attributes (encoded in the 'attnums' bitmap).
+	 * Reduce the optimization problem size as much as possible.
+	 *
+	 * Eliminate clauses and conditions not covered by any statistics,
+	 * or statistics not matching at least two attributes (one of them
+	 * has to be in a regular clause).
+	 *
+	 * It's possible that removing a statistics in one iteration
+	 * eliminates clause in the next one, so we'll repeat this until we
+	 * eliminate no clauses/stats in that iteration.
+	 *
+	 * This can only happen after eliminating a statistics - clauses are
+	 * eliminated first, so statistics always reflect that.
 	 */
-	foreach (lc, stats)
+	while (true)
 	{
-		MVStatisticInfo *info = (MVStatisticInfo *)lfirst(lc);
-
-		/* columns matching this statistics */
-		int matches = 0;
+		List	   *tmp;
 
-		int2vector * attrs = info->stakeys;
-		int	numattrs = attrs->dim1;
+		Bitmapset *compatible_attnums = NULL;
+		Bitmapset *condition_attnums  = NULL;
+		Bitmapset *all_attnums = NULL;
 
-		/* skip dependencies-only stats */
-		if (! (info->mcv_built || info->hist_built))
-			continue;
+		/*
+		 * Clauses
+		 *
+		 * Walk through clauses and keep only those covered by at least
+		 * one of the statistics we still have. We'll also keep info
+		 * about attnums in clauses (without conditions) so that we can
+		 * ignore stats covering just conditions (which is pointless).
+		 */
+		tmp = filter_clauses(root, relid, type,
+							 stats, clauses, &compatible_attnums);
 
-		/* count columns covered by the histogram */
-		for (i = 0; i < numattrs; i++)
-			if (bms_is_member(attrs->values[i], attnums))
-				matches++;
+		/* discard the original list */
+		list_free(clauses);
+		clauses = tmp;
 
 		/*
-		 * Use this statistics when it improves the number of matches or
-		 * when it matches the same number of attributes but is smaller.
+		 * Conditions
+		 *
+		 * Walk through clauses and keep only those covered by at least
+		 * one of the statistics we still have. Also, collect bitmap of
+		 * attributes so that we can make sure we add at least one new
+		 * attribute (by comparing with clauses).
 		 */
-		if ((matches > current_matches) ||
-			((matches == current_matches) && (current_dims > numattrs)))
+		if (conditions != NIL)
 		{
-			choice = info;
-			current_matches = matches;
-			current_dims = numattrs;
+			tmp = filter_clauses(root, relid, type,
+								 stats, conditions, &condition_attnums);
+
+			/* discard the original list */
+			list_free(conditions);
+			conditions = tmp;
 		}
-	}
 
-	return choice;
-}
+		/* get a union of attnums (from conditions and new clauses) */
+		all_attnums = bms_union(compatible_attnums, condition_attnums);
+
+		/*
+		 * Statisitics
+		 *
+		 * Walk through statistics and only keep those covering at least
+		 * one new attribute (excluding conditions) and at two attributes
+		 * in both clauses and conditions.
+		 */
+		tmp = filter_stats(stats, compatible_attnums, all_attnums);
 
+		/* if we've not eliminated anything, terminate */
+		if (list_length(stats) == list_length(tmp))
+			break;
 
-/*
- * This splits the clauses list into two parts - one containing clauses that
- * will be evaluated using the chosen statistics, and the remaining clauses
- * (either non-mvcompatible, or not related to the histogram).
- */
-static List *
-clauselist_mv_split(PlannerInfo *root, Index relid,
-					List *clauses, List **mvclauses,
-					MVStatisticInfo *mvstats, int types)
-{
-	int i;
-	ListCell *l;
-	List	 *non_mvclauses = NIL;
+		/* work only with filtered statistics from now */
+		list_free(stats);
+		stats = tmp;
+	}
 
-	/* FIXME is there a better way to get info on int2vector? */
-	int2vector * attrs = mvstats->stakeys;
-	int	numattrs = mvstats->stakeys->dim1;
+	/* only do the optimization if we have clauses/statistics */
+	if ((list_length(stats) == 0) || (list_length(clauses) == 0))
+		return NULL;
 
-	Bitmapset *mvattnums = NULL;
+	/* remove redundant stats (stats covered by another stats) */
+	stats = filter_redundant_stats(stats, clauses, conditions);
 
-	/* build bitmap of attributes, so we can do bms_is_subset later */
-	for (i = 0; i < numattrs; i++)
-		mvattnums = bms_add_member(mvattnums, attrs->values[i]);
+	/*
+	 * TODO We should sort the stats to make the order deterministic,
+	 *      otherwise we may get different estimates on different
+	 *      executions - if there are multiple "equally good" solutions,
+	 *      we'll keep the first solution we see.
+	 *
+	 *      Sorting by OID probably is not the right solution though,
+	 *      because we'd like it to be somehow reproducible,
+	 *      irrespectedly of the order of ADD STATISTICS commands.
+	 *      So maybe statkeys?
+	 */
+	mvstats = make_stats_array(stats, &nmvstats);
+	stats_attnums = make_stats_attnums(mvstats, nmvstats);
 
-	/* erase the list of mv-compatible clauses */
-	*mvclauses = NIL;
+	/* collect clauses an bitmap of attnums */
+	clauses_array = make_clauses_array(clauses, &nclauses);
+	clauses_attnums = make_clauses_attnums(root, relid, type,
+										   clauses_array, nclauses);
 
-	foreach (l, clauses)
-	{
-		bool		match = false;	/* by default not mv-compatible */
-		Bitmapset	*attnums = NULL;
-		Node	   *clause = (Node *) lfirst(l);
+	/* collect conditions and bitmap of attnums */
+	conditions_array = make_clauses_array(conditions, &nconditions);
+	conditions_attnums = make_clauses_attnums(root, relid, type,
+											  conditions_array, nconditions);
 
-		if (clause_is_mv_compatible(clause, relid, &attnums, types))
+	/*
+	 * Build bitmaps with info about which clauses/conditions are
+	 * covered by each statistics (so that we don't need to call the
+	 * bms_is_subset over and over again).
+	 */
+	clause_cover_map = make_cover_map(stats_attnums, nmvstats,
+									  clauses_attnums, nclauses);
+
+	condition_cover_map	= make_cover_map(stats_attnums, nmvstats,
+										 conditions_attnums, nconditions);
+
+	ruled_out =  (int*)palloc0(nmvstats * sizeof(int));
+
+	/* no stats are ruled out by default */
+	for (i = 0; i < nmvstats; i++)
+		ruled_out[i] = -1;
+
+	/* do the optimization itself */
+	if (mvstat_search_type == MVSTAT_SEARCH_EXHAUSTIVE)
+		choose_mv_statistics_exhaustive(root, 0,
+									   nmvstats, mvstats, stats_attnums,
+									   nclauses, clauses_array, clauses_attnums,
+									   nconditions, conditions_array, conditions_attnums,
+									   clause_cover_map, condition_cover_map,
+									   ruled_out, NULL, &best);
+	else
+		choose_mv_statistics_greedy(root, 0,
+									   nmvstats, mvstats, stats_attnums,
+									   nclauses, clauses_array, clauses_attnums,
+									   nconditions, conditions_array, conditions_attnums,
+									   clause_cover_map, condition_cover_map,
+									   ruled_out, NULL, &best);
+
+	/* create a list of statistics from the array */
+	if (best != NULL)
+	{
+		for (i = 0; i < best->nstats; i++)
 		{
-			/* are all the attributes part of the selected stats? */
-			if (bms_is_subset(attnums, mvattnums))
-				match = true;
+			MVStatisticInfo *info = makeNode(MVStatisticInfo);
+			memcpy(info, &mvstats[best->stats[i]], sizeof(MVStatisticInfo));
+			result = lappend(result, info);
 		}
 
-		/*
-		 * The clause matches the selected stats, so put it to the list of
-		 * mv-compatible clauses. Otherwise, keep it in the list of 'regular'
-		 * clauses (that may be selected later).
-		 */
-		if (match)
-			*mvclauses = lappend(*mvclauses, clause);
-		else
-			non_mvclauses = lappend(non_mvclauses, clause);
+		pfree(best);
 	}
 
-	/*
-	 * Perform regular estimation using the clauses incompatible with the chosen
-	 * histogram (or MV stats in general).
-	 */
-	return non_mvclauses;
+	/* cleanup (maybe leave it up to the memory context?) */
+	for (i = 0; i < nmvstats; i++)
+		bms_free(stats_attnums[i]);
+
+	for (i = 0; i < nclauses; i++)
+		bms_free(clauses_attnums[i]);
+
+	for (i = 0; i < nconditions; i++)
+		bms_free(conditions_attnums[i]);
+
+	pfree(stats_attnums);
+	pfree(clauses_attnums);
+	pfree(conditions_attnums);
 
+	pfree(clauses_array);
+	pfree(conditions_array);
+	pfree(clause_cover_map);
+	pfree(condition_cover_map);
+	pfree(ruled_out);
+	pfree(mvstats);
+
+	list_free(clauses);
+	list_free(conditions);
+	list_free(stats);
+
+	return result;
 }
 
 typedef struct
@@ -1474,6 +2686,7 @@ clause_is_mv_compatible(Node *clause, Index relid, Bitmapset **attnums, int type
 	return true;
 }
 
+
 /*
  * collect attnums from functional dependencies
  *
@@ -2022,6 +3235,24 @@ clauselist_apply_dependencies(PlannerInfo *root, List *clauses,
  * Check that there are stats with at least one of the requested types.
  */
 static bool
+stats_type_matches(MVStatisticInfo *stat, int type)
+{
+	if ((type & MV_CLAUSE_TYPE_FDEP) && stat->deps_built)
+		return true;
+
+	if ((type & MV_CLAUSE_TYPE_MCV) && stat->mcv_built)
+		return true;
+
+	if ((type & MV_CLAUSE_TYPE_HIST) && stat->hist_built)
+		return true;
+
+	return false;
+}
+
+/*
+ * Check that there are stats with at least one of the requested types.
+ */
+static bool
 has_stats(List *stats, int type)
 {
 	ListCell   *s;
@@ -2030,13 +3261,8 @@ has_stats(List *stats, int type)
 	{
 		MVStatisticInfo	*stat = (MVStatisticInfo *)lfirst(s);
 
-		if ((type & MV_CLAUSE_TYPE_FDEP) && stat->deps_built)
-			return true;
-
-		if ((type & MV_CLAUSE_TYPE_MCV) && stat->mcv_built)
-			return true;
-
-		if ((type & MV_CLAUSE_TYPE_HIST) && stat->hist_built)
+		/* terminate if we've found at least one matching statistics */
+		if (stats_type_matches(stat, type))
 			return true;
 	}
 
@@ -2087,22 +3313,26 @@ find_stats(PlannerInfo *root, Index relid)
  *      as the clauses are processed (and skip items that are 'match').
  */
 static Selectivity
-clauselist_mv_selectivity_mcvlist(PlannerInfo *root, List *clauses,
-								  MVStatisticInfo *mvstats, bool *fullmatch,
-								  Selectivity *lowsel)
+clauselist_mv_selectivity_mcvlist(PlannerInfo *root, MVStatisticInfo *mvstats,
+								  List *clauses, List *conditions, bool is_or,
+								  bool *fullmatch, Selectivity *lowsel)
 {
 	int i;
 	Selectivity s = 0.0;
+	Selectivity t = 0.0;
 	Selectivity u = 0.0;
 
 	MCVList mcvlist = NULL;
+
 	int	nmatches = 0;
+	int	nconditions = 0;
 
 	/* match/mismatch bitmap for each MCV item */
 	char * matches = NULL;
+	char * condition_matches = NULL;
 
 	Assert(clauses != NIL);
-	Assert(list_length(clauses) >= 2);
+	Assert(list_length(clauses) >= 1);
 
 	/* there's no MCV list built yet */
 	if (! mvstats->mcv_built)
@@ -2113,32 +3343,85 @@ clauselist_mv_selectivity_mcvlist(PlannerInfo *root, List *clauses,
 	Assert(mcvlist != NULL);
 	Assert(mcvlist->nitems > 0);
 
-	/* by default all the MCV items match the clauses fully */
-	matches = palloc0(sizeof(char) * mcvlist->nitems);
-	memset(matches, MVSTATS_MATCH_FULL, sizeof(char)*mcvlist->nitems);
-
 	/* number of matching MCV items */
 	nmatches = mcvlist->nitems;
+	nconditions = mcvlist->nitems;
+
+	/*
+	 * Bitmap of bucket matches (mismatch, partial, full).
+	 *
+	 * For AND clauses all buckets match (and we'll eliminate them).
+	 * For OR  clauses no  buckets match (and we'll add them).
+	 *
+	 * We only need to do the memset for AND clauses (for OR clauses
+	 * it's already set correctly by the palloc0).
+	 */
+	matches = palloc0(sizeof(char) * nmatches);
+
+	if (! is_or) /* AND-clause */
+		memset(matches, MVSTATS_MATCH_FULL, sizeof(char)*nmatches);
 
+	/* Conditions are treated as AND clause, so match by default. */
+	condition_matches = palloc0(sizeof(char) * nconditions);
+	memset(condition_matches, MVSTATS_MATCH_FULL, sizeof(char)*nconditions);
+
+	/*
+	 * build the match bitmap for the conditions (conditions are always
+	 * connected by AND)
+	 */
+	if (conditions != NIL)
+		nconditions = update_match_bitmap_mcvlist(root, conditions,
+									   mvstats->stakeys, mcvlist,
+									   nconditions, condition_matches,
+									   lowsel, fullmatch, false);
+
+	/*
+	 * build the match bitmap for the estimated clauses
+	 *
+	 * TODO This evaluates the clauses for all MCV items, even those
+	 *      ruled out by the conditions. The final result should be the
+	 *      same, but it might be faster.
+	 */
 	nmatches = update_match_bitmap_mcvlist(root, clauses,
 										   mvstats->stakeys, mcvlist,
-										   nmatches, matches,
-										   lowsel, fullmatch, false);
+										   ((is_or) ? 0 : nmatches), matches,
+										   lowsel, fullmatch, is_or);
 
 	/* sum frequencies for all the matching MCV items */
 	for (i = 0; i < mcvlist->nitems; i++)
 	{
-		/* used to 'scale' for MCV lists not covering all tuples */
+		/*
+		 * Find out what part of the data is covered by the MCV list,
+		 * so that we can 'scale' the selectivity properly (e.g. when
+		 * only 50% of the sample items got into the MCV, and the rest
+		 * is either in a histogram, or not covered by stats).
+		 *
+		 * TODO This might be handled by keeping a global "frequency"
+		 *      for the whole list, which might save us a bit of time
+		 *      spent on accessing the not-matching part of the MCV list.
+		 *      Although it's likely in a cache, so it's very fast.
+		 */
 		u += mcvlist->items[i]->frequency;
 
+		/* skit MCV items not matching the conditions */
+		if (condition_matches[i] == MVSTATS_MATCH_NONE)
+			continue;
+
 		if (matches[i] != MVSTATS_MATCH_NONE)
 			s += mcvlist->items[i]->frequency;
+
+		t += mcvlist->items[i]->frequency;
 	}
 
 	pfree(matches);
+	pfree(condition_matches);
 	pfree(mcvlist);
 
-	return s*u;
+	/* no condition matches */
+	if (t == 0.0)
+		return (Selectivity)0.0;
+
+	return (s / t) * u;
 }
 
 /*
@@ -2369,64 +3652,57 @@ update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
 				}
 			}
 		}
-		else if (or_clause(clause) || and_clause(clause))
+		else if (or_clause(clause) || and_clause(clause) || not_clause(clause))
 		{
 			/* AND/OR clause, with all clauses compatible with the selected MV stat */
 
 			int			i;
-			BoolExpr   *orclause  = ((BoolExpr*)clause);
-			List	   *orclauses = orclause->args;
+			List	   *tmp_clauses = ((BoolExpr*)clause)->args;
 
 			/* match/mismatch bitmap for each MCV item */
-			int	or_nmatches = 0;
-			char * or_matches = NULL;
+			int	tmp_nmatches = 0;
+			char * tmp_matches = NULL;
 
-			Assert(orclauses != NIL);
-			Assert(list_length(orclauses) >= 2);
+			Assert(tmp_clauses != NIL);
+			Assert((list_length(tmp_clauses) >= 2) || (not_clause(clause) && (list_length(tmp_clauses)==1)));
 
 			/* number of matching MCV items */
-			or_nmatches = mcvlist->nitems;
+			tmp_nmatches = (or_clause(clause)) ? 0 : mcvlist->nitems;
 
 			/* by default none of the MCV items matches the clauses */
-			or_matches = palloc0(sizeof(char) * or_nmatches);
+			tmp_matches = palloc0(sizeof(char) * mcvlist->nitems);
 
-			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);
-			}
+			/* AND (and NOT) clauses assume everything matches, initially */
+			if (! or_clause(clause))
+				memset(tmp_matches, MVSTATS_MATCH_FULL, sizeof(char)*mcvlist->nitems);
 
 			/* build the match bitmap for the OR-clauses */
-			or_nmatches = update_match_bitmap_mcvlist(root, orclauses,
+			tmp_nmatches = update_match_bitmap_mcvlist(root, tmp_clauses,
 									   stakeys, mcvlist,
-									   or_nmatches, or_matches,
+									   tmp_nmatches, tmp_matches,
 									   lowsel, fullmatch, or_clause(clause));
 
 			/* merge the bitmap into the existing one*/
 			for (i = 0; i < mcvlist->nitems; i++)
 			{
+				/* if this is a NOT clause, we need to invert the results first */
+				if (not_clause(clause))
+					tmp_matches[i] = (MVSTATS_MATCH_FULL - tmp_matches[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);
+				UPDATE_RESULT(matches[i], tmp_matches[i], is_or);
 			}
 
-			pfree(or_matches);
+			pfree(tmp_matches);
 
 		}
 		else
-		{
 			elog(ERROR, "unknown clause type: %d", clause->type);
-		}
 	}
 
 	/*
@@ -2484,15 +3760,18 @@ update_match_bitmap_mcvlist(PlannerInfo *root, List *clauses,
  *      this is not uncommon, but for histograms it's not that clear.
  */
 static Selectivity
-clauselist_mv_selectivity_histogram(PlannerInfo *root, List *clauses,
-									MVStatisticInfo *mvstats)
+clauselist_mv_selectivity_histogram(PlannerInfo *root, MVStatisticInfo *mvstats,
+									List *clauses, List *conditions, bool is_or)
 {
 	int i;
 	Selectivity s = 0.0;
+	Selectivity t = 0.0;
 	Selectivity u = 0.0;
 
 	int		nmatches = 0;
+	int		nconditions = 0;
 	char   *matches = NULL;
+	char   *condition_matches = NULL;
 
 	MVSerializedHistogram mvhist = NULL;
 
@@ -2505,25 +3784,55 @@ clauselist_mv_selectivity_histogram(PlannerInfo *root, List *clauses,
 
 	Assert (mvhist != NULL);
 	Assert (clauses != NIL);
-	Assert (list_length(clauses) >= 2);
+	Assert (list_length(clauses) >= 1);
+
+	nmatches = mvhist->nbuckets;
+	nconditions = mvhist->nbuckets;
 
 	/*
-	 * Bitmap of bucket matches (mismatch, partial, full). by default
-	 * all buckets fully match (and we'll eliminate them).
+	 * Bitmap of bucket matches (mismatch, partial, full).
+	 *
+	 * For AND clauses all buckets match (and we'll eliminate them).
+	 * For OR  clauses no  buckets match (and we'll add them).
+	 *
+	 * We only need to do the memset for AND clauses (for OR clauses
+	 * it's already set correctly by the palloc0).
 	 */
-	matches = palloc0(sizeof(char) * mvhist->nbuckets);
-	memset(matches,  MVSTATS_MATCH_FULL, sizeof(char)*mvhist->nbuckets);
+	matches = palloc0(sizeof(char) * nmatches);
 
-	nmatches = mvhist->nbuckets;
+	if (! is_or) /* AND-clause */
+		memset(matches, MVSTATS_MATCH_FULL, sizeof(char)*nmatches);
+
+	/* Conditions are treated as AND clause, so match by default. */
+	condition_matches = palloc0(sizeof(char)*nconditions);
+	memset(condition_matches, MVSTATS_MATCH_FULL, sizeof(char)*nconditions);
+
+	/*
+	 * build the match bitmap for the conditions (conditions are always
+	 * connected by AND)
+	 */
+	if (conditions != NIL)
+		update_match_bitmap_histogram(root, conditions,
+								  mvstats->stakeys, mvhist,
+								  nconditions, condition_matches, false);
 
-	/* build the match bitmap */
+	/*
+	 * build the match bitmap for the estimated clauses
+	 *
+	 * TODO This evaluates the clauses for all buckets, even those
+	 *      ruled out by the conditions. The final result should be
+	 *      the same, but it might be faster.
+	 */
 	update_match_bitmap_histogram(root, clauses,
 								  mvstats->stakeys, mvhist,
-								  nmatches, matches, false);
+								  ((is_or) ? 0 : nmatches), matches,
+								  is_or);
 
 	/* now, walk through the buckets and sum the selectivities */
 	for (i = 0; i < mvhist->nbuckets; i++)
 	{
+		float coeff = 1.0;
+
 		/*
 		 * Find out what part of the data is covered by the histogram,
 		 * so that we can 'scale' the selectivity properly (e.g. when
@@ -2537,10 +3846,23 @@ clauselist_mv_selectivity_histogram(PlannerInfo *root, List *clauses,
 		 */
 		u += mvhist->buckets[i]->ntuples;
 
+		/* skip buckets not matching the conditions */
+		if (condition_matches[i] == MVSTATS_MATCH_NONE)
+			continue;
+		else if (condition_matches[i] == MVSTATS_MATCH_PARTIAL)
+			coeff = 0.5;
+
+		t += coeff * mvhist->buckets[i]->ntuples;
+
 		if (matches[i] == MVSTATS_MATCH_FULL)
-			s += mvhist->buckets[i]->ntuples;
+			s += coeff * mvhist->buckets[i]->ntuples;
 		else if (matches[i] == MVSTATS_MATCH_PARTIAL)
-			s += 0.5 * mvhist->buckets[i]->ntuples;
+			/*
+			 * TODO If both conditions and clauses match partially, this
+			 *      will use 0.25 match - not sure if that's the right
+			 *      thing solution, but seems about right.
+			 */
+			s += coeff * 0.5 * mvhist->buckets[i]->ntuples;
 	}
 
 #ifdef DEBUG_MVHIST
@@ -2549,9 +3871,14 @@ clauselist_mv_selectivity_histogram(PlannerInfo *root, List *clauses,
 
 	/* release the allocated bitmap and deserialized histogram */
 	pfree(matches);
+	pfree(condition_matches);
 	pfree(mvhist);
 
-	return s * u;
+	/* no condition matches */
+	if (t == 0.0)
+		return (Selectivity)0.0;
+
+	return (s / t) * u;
 }
 
 /* cached result of bucket boundary comparison for a single dimension */
@@ -2699,7 +4026,7 @@ update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
 {
 	int i;
 	ListCell * l;
-
+ 
 	/*
 	 * Used for caching function calls, only once per deduplicated value.
 	 *
@@ -2742,7 +4069,7 @@ update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
 
 			FmgrInfo	opproc;			/* operator */
 			fmgr_info(get_opcode(expr->opno), &opproc);
-
+ 
 			/* reset the cache (per clause) */
 			memset(callcache, 0, mvhist->nbuckets);
 
@@ -2902,64 +4229,57 @@ update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
 					UPDATE_RESULT(matches[i], MVSTATS_MATCH_NONE, is_or);
 			}
 		}
-		else if (or_clause(clause) || and_clause(clause))
+		else if (or_clause(clause) || and_clause(clause) || not_clause(clause))
 		{
 			/* AND/OR clause, with all clauses compatible with the selected MV stat */
 
 			int			i;
-			BoolExpr   *orclause  = ((BoolExpr*)clause);
-			List	   *orclauses = orclause->args;
+			List	   *tmp_clauses = ((BoolExpr*)clause)->args;
 
 			/* match/mismatch bitmap for each bucket */
-			int	or_nmatches = 0;
-			char * or_matches = NULL;
+			int	tmp_nmatches = 0;
+			char * tmp_matches = NULL;
 
-			Assert(orclauses != NIL);
-			Assert(list_length(orclauses) >= 2);
+			Assert(tmp_clauses != NIL);
+			Assert((list_length(tmp_clauses) >= 2) || (not_clause(clause) && (list_length(tmp_clauses)==1)));
 
 			/* number of matching buckets */
-			or_nmatches = mvhist->nbuckets;
+			tmp_nmatches = (or_clause(clause)) ? 0 : mvhist->nbuckets;
 
-			/* by default none of the buckets matches the clauses */
-			or_matches = palloc0(sizeof(char) * or_nmatches);
+			/* by default none of the buckets matches the clauses (OR clause) */
+			tmp_matches = palloc0(sizeof(char) * mvhist->nbuckets);
 
-			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);
-			}
+			/* but AND (and NOT) clauses assume everything matches, initially */
+			if (! or_clause(clause))
+				memset(tmp_matches, MVSTATS_MATCH_FULL, sizeof(char)*mvhist->nbuckets);
 
 			/* build the match bitmap for the OR-clauses */
-			or_nmatches = update_match_bitmap_histogram(root, orclauses,
+			tmp_nmatches = update_match_bitmap_histogram(root, tmp_clauses,
 										stakeys, mvhist,
-										or_nmatches, or_matches, or_clause(clause));
+										tmp_nmatches, tmp_matches, or_clause(clause));
 
 			/* merge the bitmap into the existing one*/
 			for (i = 0; i < mvhist->nbuckets; i++)
 			{
+				/* if this is a NOT clause, we need to invert the results first */
+				if (not_clause(clause))
+					tmp_matches[i] = (MVSTATS_MATCH_FULL - tmp_matches[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);
+				UPDATE_RESULT(matches[i], tmp_matches[i], is_or);
 			}
 
-			pfree(or_matches);
-
+			pfree(tmp_matches);
 		}
 		else
 			elog(ERROR, "unknown clause type: %d", clause->type);
 	}
 
-	/* free the call cache */
 	pfree(callcache);
 
 	return nmatches;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 5fc2f9c..7384cb8 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3520,7 +3520,8 @@ compute_semi_anti_join_factors(PlannerInfo *root,
 									joinquals,
 									0,
 									jointype,
-									sjinfo);
+									sjinfo,
+									NIL);
 
 	/*
 	 * Also get the normal inner-join selectivity of the join clauses.
@@ -3543,7 +3544,8 @@ compute_semi_anti_join_factors(PlannerInfo *root,
 									joinquals,
 									0,
 									JOIN_INNER,
-									&norm_sjinfo);
+									&norm_sjinfo,
+									NIL);
 
 	/* Avoid leaking a lot of ListCells */
 	if (jointype == JOIN_ANTI)
@@ -3710,7 +3712,7 @@ approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
 		Node	   *qual = (Node *) lfirst(l);
 
 		/* Note that clause_selectivity will be able to cache its result */
-		selec *= clause_selectivity(root, qual, 0, JOIN_INNER, &sjinfo);
+		selec *= clause_selectivity(root, qual, 0, JOIN_INNER, &sjinfo, NIL);
 	}
 
 	/* Apply it to the input relation sizes */
@@ -3746,7 +3748,8 @@ set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel)
 							   rel->baserestrictinfo,
 							   0,
 							   JOIN_INNER,
-							   NULL);
+							   NULL,
+							   NIL);
 
 	rel->rows = clamp_row_est(nrows);
 
@@ -3783,7 +3786,8 @@ get_parameterized_baserel_size(PlannerInfo *root, RelOptInfo *rel,
 							   allclauses,
 							   rel->relid,		/* do not use 0! */
 							   JOIN_INNER,
-							   NULL);
+							   NULL,
+							   NIL);
 	nrows = clamp_row_est(nrows);
 	/* For safety, make sure result is not more than the base estimate */
 	if (nrows > rel->rows)
@@ -3921,12 +3925,14 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 										joinquals,
 										0,
 										jointype,
-										sjinfo);
+										sjinfo,
+										NIL);
 		pselec = clauselist_selectivity(root,
 										pushedquals,
 										0,
 										jointype,
-										sjinfo);
+										sjinfo,
+										NIL);
 
 		/* Avoid leaking a lot of ListCells */
 		list_free(joinquals);
@@ -3938,7 +3944,8 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 										restrictlist,
 										0,
 										jointype,
-										sjinfo);
+										sjinfo,
+										NIL);
 		pselec = 0.0;			/* not used, keep compiler quiet */
 	}
 
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index ea831f5..6299e75 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -280,7 +280,7 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
 	 * saving work later.)
 	 */
 	or_selec = clause_selectivity(root, (Node *) or_rinfo,
-								  0, JOIN_INNER, NULL);
+								  0, JOIN_INNER, NULL, NIL);
 
 	/*
 	 * The clause is only worth adding to the query if it rejects a useful
@@ -342,7 +342,7 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
 
 		/* Compute inner-join size */
 		orig_selec = clause_selectivity(root, (Node *) join_or_rinfo,
-										0, JOIN_INNER, &sjinfo);
+										0, JOIN_INNER, &sjinfo, NIL);
 
 		/* And hack cached selectivity so join size remains the same */
 		join_or_rinfo->norm_selec = orig_selec / or_selec;
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 46c95b0..7d0a3a1 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -1627,13 +1627,15 @@ booltestsel(PlannerInfo *root, BoolTestType booltesttype, Node *arg,
 			case IS_NOT_FALSE:
 				selec = (double) clause_selectivity(root, arg,
 													varRelid,
-													jointype, sjinfo);
+													jointype, sjinfo,
+													NIL);
 				break;
 			case IS_FALSE:
 			case IS_NOT_TRUE:
 				selec = 1.0 - (double) clause_selectivity(root, arg,
 														  varRelid,
-														  jointype, sjinfo);
+														  jointype, sjinfo,
+														  NIL);
 				break;
 			default:
 				elog(ERROR, "unrecognized booltesttype: %d",
@@ -6259,7 +6261,8 @@ genericcostestimate(PlannerInfo *root,
 	indexSelectivity = clauselist_selectivity(root, selectivityQuals,
 											  index->rel->relid,
 											  JOIN_INNER,
-											  NULL);
+											  NULL,
+											  NIL);
 
 	/*
 	 * If caller didn't give us an estimate, estimate the number of index
@@ -6579,7 +6582,8 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 		btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
 												  index->rel->relid,
 												  JOIN_INNER,
-												  NULL);
+												  NULL,
+												  NIL);
 		numIndexTuples = btreeSelectivity * index->rel->tuples;
 
 		/*
@@ -7330,7 +7334,8 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	*indexSelectivity = clauselist_selectivity(root, selectivityQuals,
 											   index->rel->relid,
 											   JOIN_INNER,
-											   NULL);
+											   NULL,
+											   NIL);
 
 	/* fetch estimated page cost for tablespace containing index */
 	get_tablespace_page_costs(index->reltablespace,
@@ -7560,7 +7565,7 @@ brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	*indexSelectivity =
 		clauselist_selectivity(root, indexQuals,
 							   path->indexinfo->rel->relid,
-							   JOIN_INNER, NULL);
+							   JOIN_INNER, NULL, NIL);
 	*indexCorrelation = 1;
 
 	/*
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index ea5a09a..27a8de5 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -75,6 +75,7 @@
 #include "utils/bytea.h"
 #include "utils/guc_tables.h"
 #include "utils/memutils.h"
+#include "utils/mvstats.h"
 #include "utils/pg_locale.h"
 #include "utils/plancache.h"
 #include "utils/portal.h"
@@ -393,6 +394,15 @@ static const struct config_enum_entry force_parallel_mode_options[] = {
 };
 
 /*
+ * Search algorithm for multivariate stats.
+ */
+static const struct config_enum_entry mvstat_search_options[] = {
+	{"greedy", MVSTAT_SEARCH_GREEDY, false},
+	{"exhaustive", MVSTAT_SEARCH_EXHAUSTIVE, false},
+	{NULL, 0, false}
+};
+
+/*
  * Options for enum values stored in other modules
  */
 extern const struct config_enum_entry wal_level_options[];
@@ -3707,6 +3717,16 @@ static struct config_enum ConfigureNamesEnum[] =
 		NULL, NULL, NULL
 	},
 
+	{
+		{"mvstat_search", PGC_USERSET, QUERY_TUNING_OTHER,
+			gettext_noop("Sets the algorithm used for combining multivariate stats."),
+			NULL
+		},
+		&mvstat_search_type,
+		MVSTAT_SEARCH_GREEDY, mvstat_search_options,
+		NULL, NULL, NULL
+	},
+
 	/* End-of-list marker */
 	{
 		{NULL, 0, 0, NULL, NULL}, NULL, 0, NULL, NULL, NULL, NULL
diff --git a/src/backend/utils/mvstats/README.stats b/src/backend/utils/mvstats/README.stats
index 3e4f4d1..d404914 100644
--- a/src/backend/utils/mvstats/README.stats
+++ b/src/backend/utils/mvstats/README.stats
@@ -90,6 +90,137 @@ even attempting to do the more expensive estimation.
 Whenever we find there are no suitable stats, we skip the expensive steps.
 
 
+Combining multiple statistics
+-----------------------------
+
+When estimating selectivity of a list of clauses, there may exist no statistics
+covering all of them. If there are multiple statistics, each covering some
+subset of the attributes, the optimizer needs to figure out which of those
+statistics to apply.
+
+When the statistics do not overlap, the solution is trivial - we can simply
+split the groups of conditions by the matching statistics, and then multiply the
+selectivities. For example assume multivariate statistics on (b,c) and (d,e),
+and a condition like this:
+
+    (a=1) AND (b=2) AND (c=3) AND (d=4) AND (e=5)
+
+Then (a=1) is not covered by any of the statistics, so will be estimated using
+the regular per-column statistics. The two conditions ((b=2) AND (c=3)) will be
+estimated using the (b,c) statistics, and ((d=4) AND (e=5)) will be estimated
+using (d,e) statistics. And the resulting selectivities will be estimated.
+
+Now, what if the statistics overlap? For example assume the same condition as
+above, but let's say we have statistics on (a,b,c) and (a,c,d,e). What then?
+
+As selectivity is just a probability that the condition holds for a random row,
+we can write the selectivity like this:
+
+    P(a=1 & b=2 & c=3 & d=4 & e=5)
+
+and we can rewrite it using conditional probability like this
+
+    P(a=1 & b=2 & c=3) * P(d=4 & e=5 | a=1 & b=2 & c=3)
+
+Notice that the first part already matches to (a,b,c) statistics. If we assume
+that columns that are not referenced by the same statistics are independent, we
+may rewrite the second half like this
+
+    P(d=4 & e=5 | a=1 & b=2 & c=3) = P(d=4 & e=5 | a=1 & c=3)
+
+which corresponds to the statistics on (a,c,d,e).
+
+If there are multiple statistics defined on a table, it's not difficult to come
+up with examples when there are multiple ways to combine them to cover a list of
+clauses. We need a way to find the best combination of statistics.
+
+This is the purpose of choose_mv_statistics(). It searches through the possible
+combinations of statistics, and searches such combination that
+
+    (a) covers the most clauses of the list
+
+    (b) reuses the maximum number of clauses as conditions
+        (in conditional probabilities)
+
+While (a) criteria seems natural, the (b) may seem a bit awkward at first. The
+idea is that conditions in a way of transfering information about dependencies
+between statistics.
+
+There are two alternative implementations of choose_mv_statistics() - greedy
+and exhaustive. Exhaustive actually searches through all possible combinations
+of statistics, and for larger numbers of statistics may get quite expensive
+(as it, unsurprisingly, has exponential cost). Greedy terminates in less than
+K steps (when K is the number of clauses), and in each step chooses the best
+next statistics. I've been unable to come up with an example where those two
+approaches would produce different combinations.
+
+It's possible to choose the optimization using mvstat_search_type, with either
+'greedy' or 'exhaustive' values (default is 'greedy').
+
+    SET mvstat_search_type = 'exhaustive';
+
+Note: This is meant mostly for experimentation. I do expect we'll choose one of
+the algorithms and remove the GUC before commit.
+
+
+Limitations of combining statistics
+-----------------------------------
+
+As described in the section 'Combining multiple statistics', the current appoach
+is based on transfering information between statistics by means of conditional
+probabilities. This is a relatively cheap and efficient approach, but it is
+based on two assumptions:
+
+    (1) The overlap between the statistics needs to be sufficiently large, i.e.
+        there needs to be enough columns shared by the statistics to transfer
+        information about dependencies between the remaining columns.
+
+    (2) The query needs to include sufficient clauses on the shared columns.
+
+How a violation of those assumptions may be a problem can be illustrated by
+a simple example. Assume a table with three columns (a,b,c) containing exactly
+the same values, and statistics on (a,b) and (b,c):
+
+    CREATE TABLE test AS SELECT i, i, i
+                           FROM generate_series(1,1000);
+
+    CREATE STATISTICS s1 ON test (a,b) WITH (mcv);
+    CREATE STATISTICS s2 ON test (b,c) WITH (mcv);
+
+    ANALYZE test;
+
+First, let's estimate this query:
+
+    SELECT * FROM test WHERE (a < 10) AND (c < 10);
+
+Clearly, there are no conditions on 'b' (which is the only column shared by the
+two statistics), so we'll end up with an estimate based on assumption of
+independence:
+
+    P(a < 10) * P(c < 10) = 0.01 * 0.01 = 0.0001
+
+Which is a significant under-estimate, as the proper selectivity is 0.01.
+
+But let's estimate another query:
+
+    SELECT * FROM test WHERE (a < 10) AND (b < 500) AND (c < 10);
+
+In this case, the estimate may be computed for example like this:
+
+    P[(a < 10) & (b < 500) & (c < 10)]
+      = P[(a < 10) & (b < 500)] * P[(c < 10) | (a < 10) & (b < 500)]
+      = P[(a < 10) & (b < 500)] * P[(c < 10) | (b < 500)]
+
+The trouble is the probability P(c < 10 | b < 500) evaluates to 0.02, because
+we have assumed (a) and (c) are independent because there is no statistic
+containing both these columns, and the condition on (b) does not transfer
+sufficient amount of information between the two statistics.
+
+Currently, the only solution is to build statistics on all three columns, but
+see the 'combining statistics using convolution' section for ideas on how to
+improve this.
+
+
 Further (possibly crazy) ideas
 ------------------------------
 
@@ -111,3 +242,38 @@ But of course, this may result in expensive estimation (CPU-wise).
 
 So we might add a GUC to choose between a simple (single statistics) and thus
 multi-statistic estimation, possibly table-level parameter (ALTER TABLE ...).
+
+
+Combining stats using convolution
+---------------------------------
+
+While the current approach for combining statistics is based on conditional
+probabilities, and thus only works when the query includes conditions on the
+overlapping parts of the statistics. But there may be other ways to combine
+statistics, relaxing this requirement.
+
+Let's assume two histograms H1 and H2 - then combining them might work about
+like this:
+
+
+    for (buckets of H1, satisfying local conditions)
+    {
+        for (buckets of H2, overlapping with H1 bucket)
+        {
+            mark H2 bucket as 'valid'
+        }
+    }
+
+    s1 = s2 = 0.0
+    for (buckets of H2 marked as valid)
+    {
+        s1 += frequency
+
+        if (bucket satistifes local conditions)
+             s2 += frequency
+    }
+
+    s = (s2 / s1) /* final selectivity estimate */
+
+However this may quickly get non-trivial, e.g. when combining two statistics
+of different types (histogram vs. MCV).
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 78c7cae..a5ac088 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -191,11 +191,13 @@ extern Selectivity clauselist_selectivity(PlannerInfo *root,
 					   List *clauses,
 					   int varRelid,
 					   JoinType jointype,
-					   SpecialJoinInfo *sjinfo);
+					   SpecialJoinInfo *sjinfo,
+					   List *conditions);
 extern Selectivity clause_selectivity(PlannerInfo *root,
 				   Node *clause,
 				   int varRelid,
 				   JoinType jointype,
-				   SpecialJoinInfo *sjinfo);
+				   SpecialJoinInfo *sjinfo,
+				   List *conditions);
 
 #endif   /* COST_H */
diff --git a/src/include/utils/mvstats.h b/src/include/utils/mvstats.h
index f05a517..35b2f8e 100644
--- a/src/include/utils/mvstats.h
+++ b/src/include/utils/mvstats.h
@@ -17,6 +17,14 @@
 #include "fmgr.h"
 #include "commands/vacuum.h"
 
+typedef enum MVStatSearchType
+{
+	MVSTAT_SEARCH_EXHAUSTIVE,		/* exhaustive search */
+	MVSTAT_SEARCH_GREEDY			/* greedy search */
+}	MVStatSearchType;
+
+extern int mvstat_search_type;
+
 /*
  * Degree of how much MCV item / histogram bucket matches a clause.
  * This is then considered when computing the selectivity.
-- 
2.1.0