[sqlsmith] Crash in mcv_get_match_bitmap

From 043b7525590278fabacd3c10ef869b1ef2b7358f Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Fri, 12 Jul 2019 22:26:20 +0200
Subject: [PATCH 1/2] Determine operator semantics using btree opclasses

---
 src/backend/statistics/dependencies.c   | 15 +++---
 src/backend/statistics/extended_stats.c | 69 +++++++++++++++++++------
 src/backend/statistics/mcv.c            | 60 ++++++++++++---------
 src/include/statistics/statistics.h     |  1 +
 4 files changed, 99 insertions(+), 46 deletions(-)

diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c
index 66c38ce2bc..2723ca33df 100644
--- a/src/backend/statistics/dependencies.c
+++ b/src/backend/statistics/dependencies.c
@@ -14,6 +14,7 @@
 #include "postgres.h"
 
 #include "access/htup_details.h"
+#include "access/stratnum.h"
 #include "access/sysattr.h"
 #include "catalog/pg_operator.h"
 #include "catalog/pg_statistic_ext.h"
@@ -788,15 +789,13 @@ dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
 		 * If it's not an "=" operator, just ignore the clause, as it's not
 		 * compatible with functional dependencies.
 		 *
-		 * This uses the function for estimating selectivity, not the operator
-		 * directly (a bit awkward, but well ...).
-		 *
-		 * XXX this is pretty dubious; probably it'd be better to check btree
-		 * or hash opclass membership, so as not to be fooled by custom
-		 * selectivity functions, and to be more consistent with decisions
-		 * elsewhere in the planner.
+		 * To decide this, we need to decide the semantics of the operator.
+		 * We do that by matching it to btree opclasses, and checking the
+		 * strategy numbers. When there's no btree opclass, or when there
+		 * are multiple strategy numbers, we consider the semantics to be
+		 * unclear (i.e. not an equality operator).
 		 */
-		if (get_oprrest(expr->opno) != F_EQSEL)
+		if (determine_operator_strategy(expr->opno) != BTEqualStrategyNumber)
 			return false;
 
 		/* OK to proceed with checking "var" */
diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index c56ed48270..2ed28c054f 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -20,6 +20,7 @@
 #include "access/htup_details.h"
 #include "access/table.h"
 #include "access/tuptoaster.h"
+#include "access/stratnum.h"
 #include "catalog/indexing.h"
 #include "catalog/pg_collation.h"
 #include "catalog/pg_statistic_ext.h"
@@ -819,22 +820,14 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
 		 *
 		 * This uses the function for estimating selectivity, not the operator
 		 * directly (a bit awkward, but well ...).
+		 *
+		 * XXX We can't check this against strategies defined in stratnum.h,
+		 * because get_op_btree_interpretation() introduces a new strategy
+		 * number for operator '<>' and we'd miss that. So we simply check
+		 * if the result is (-1) which means strategy is unknown.
 		 */
-		switch (get_oprrest(expr->opno))
-		{
-			case F_EQSEL:
-			case F_NEQSEL:
-			case F_SCALARLTSEL:
-			case F_SCALARLESEL:
-			case F_SCALARGTSEL:
-			case F_SCALARGESEL:
-				/* supported, will continue with inspection of the Var */
-				break;
-
-			default:
-				/* other estimators are considered unknown/unsupported */
-				return false;
-		}
+		if (determine_operator_strategy(expr->opno) == -1)
+			return false;
 
 		/*
 		 * If there are any securityQuals on the RTE from security barrier
@@ -1196,3 +1189,49 @@ statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
 
 	return sel;
 }
+
+/*
+ * determine_operator_strategy
+ *		Determine operator semantics by matching it to btree opclasses.
+ *
+ * We look at all the btree opclasses referencing the supplied operator, and
+ * check if the strategy number is the same in all of them. If yes, we consider
+ * that to be the semantics of the operator (equality, less-than, ...) and
+ * return that strategy number.
+ *
+ * If there are no matching btree opclasses, or when the operator has multiple
+ * strategy numbers in various opclasses, we consider the operator semantics to
+ * be unclear/undefined and return -1.
+ *
+ * Note: This only looks at btree opclasses, so for data types with only a hash
+ * opclass, this always returns (-1). That ultimately means we won't be able
+ * to use extended statistics for them.
+ *
+ * Note: The result strategy number may not be defined in stratnum.h, so you
+ * need to be careful when checking the result. This is because this calls
+ * get_op_btree_interpretation which may introduce new stragies that are not
+ * actually part of btree definition (e.g. '<>')
+ */
+int
+determine_operator_strategy(Oid opno)
+{
+	ListCell   *lc;
+	int			strat;
+	List	   *opinfos;
+	Bitmapset  *strats = NULL;
+
+	opinfos = get_op_btree_interpretation(opno);
+
+	foreach(lc, opinfos)
+	{
+		OpBtreeInterpretation *opinfo = lfirst(lc);
+
+		strats = bms_add_member(strats, opinfo->strategy);
+	}
+
+	/* multiple (or multiple) strategies means unclear semantics */
+	if (!bms_get_singleton_member(strats, &strat))
+		return -1;
+
+	return strat;
+}
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 913a72ff67..1e919c82f9 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1565,9 +1565,6 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 			bool		ok;
 			FmgrInfo	opproc;
 
-			/* get procedure computing operator selectivity */
-			RegProcedure oprrest = get_oprrest(expr->opno);
-
 			fmgr_info(get_opcode(expr->opno), &opproc);
 
 			ok = (NumRelids(clause) == 1) &&
@@ -1583,6 +1580,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 				Const	   *cst;
 				bool		isgt;
 				int			idx;
+				int			strategy;
 
 				/* extract the var and const from the expression */
 				var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
@@ -1600,6 +1598,16 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 				typecache = lookup_type_cache(var->vartype, TYPECACHE_GT_OPR);
 				fmgr_info(get_opcode(typecache->gt_opr), &gtproc);
 
+				/* determine operator semantics from btree opclasses */
+				strategy = determine_operator_strategy(expr->opno);
+
+				/*
+				 * At this point all the expressions must have a meaningful
+				 * btree opclass interpretation (thanks to passing through
+				 * statext_is_compatible_clause, which enforces that).
+				 */
+				Assert(strategy > 0);
+
 				/*
 				 * Walk through the MCV items and evaluate the current clause.
 				 * We can skip items that were already ruled out, and
@@ -1625,27 +1633,12 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 					else if (is_or && (matches[i] == true))
 						continue;
 
-					switch (oprrest)
+					switch (strategy)
 					{
-						case F_EQSEL:
-						case F_NEQSEL:
-
-							/*
-							 * We don't care about isgt in equality, because
-							 * it does not matter whether it's (var op const)
-							 * or (const op var).
-							 */
-							mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																	   DEFAULT_COLLATION_OID,
-																	   cst->constvalue,
-																	   item->values[idx]));
-
-							break;
-
-						case F_SCALARLTSEL: /* column < constant */
-						case F_SCALARLESEL: /* column <= constant */
-						case F_SCALARGTSEL: /* column > constant */
-						case F_SCALARGESEL: /* column >= constant */
+						case BTLessStrategyNumber:         /* column < constant */
+						case BTLessEqualStrategyNumber:    /* column <= constant */
+						case BTGreaterEqualStrategyNumber: /* column > constant */
+						case BTGreaterStrategyNumber:      /* column >= constant */
 
 							/*
 							 * First check whether the constant is below the
@@ -1664,6 +1657,27 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 																		   cst->constvalue));
 
 							break;
+
+						default:
+
+							/*
+							 * This does handle equality and inequality, but we handle
+							 * that as a default case because inequality operator '<>'
+							 * does not actually have a btree opclass strategy, it's
+							 * added by get_op_btree_interpretation.
+							 */
+
+							/*
+							 * We don't care about isgt in equality, because
+							 * it does not matter whether it's (var op const)
+							 * or (const op var).
+							 */
+							mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
+																	   DEFAULT_COLLATION_OID,
+																	   cst->constvalue,
+																	   item->values[idx]));
+
+							break;
 					}
 
 					/*
diff --git a/src/include/statistics/statistics.h b/src/include/statistics/statistics.h
index cb7bc630e9..82e2d5c619 100644
--- a/src/include/statistics/statistics.h
+++ b/src/include/statistics/statistics.h
@@ -118,5 +118,6 @@ extern Selectivity statext_clauselist_selectivity(PlannerInfo *root,
 extern bool has_stats_of_kind(List *stats, char requiredkind);
 extern StatisticExtInfo *choose_best_statistics(List *stats,
 												Bitmapset *attnums, char requiredkind);
+extern int determine_operator_strategy(Oid opno);
 
 #endif							/* STATISTICS_H */
-- 
2.20.1

From 354191c27867d9dc5672f1abad14941e29e3d595 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Sat, 13 Jul 2019 00:12:16 +0200
Subject: [PATCH 2/2] Fix processing of OpExpr in extended statistics

---
 src/backend/statistics/extended_stats.c | 64 ++++++++++++++++++++-----
 src/backend/statistics/mcv.c            | 23 +++------
 src/include/statistics/statistics.h     |  1 +
 3 files changed, 60 insertions(+), 28 deletions(-)

diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index 2ed28c054f..1c7ca07661 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -797,21 +797,13 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
 		RangeTblEntry *rte = root->simple_rte_array[relid];
 		OpExpr	   *expr = (OpExpr *) clause;
 		Var		   *var;
-		bool		varonleft = true;
-		bool		ok;
 
 		/* Only expressions with two arguments are considered compatible. */
 		if (list_length(expr->args) != 2)
 			return false;
 
-		/* see if it actually has the right shape (one Var, one Const) */
-		ok = (NumRelids((Node *) expr) == 1) &&
-			(is_pseudo_constant_clause(lsecond(expr->args)) ||
-			 (varonleft = false,
-			  is_pseudo_constant_clause(linitial(expr->args))));
-
-		/* unsupported structure (two variables or so) */
-		if (!ok)
+		/* Check if the expression the right shape (one Var, one Const) */
+		if (!deconstruct_opexpr(expr, &var, NULL, NULL))
 			return false;
 
 		/*
@@ -843,8 +835,6 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
 			!get_func_leakproof(get_opcode(expr->opno)))
 			return false;
 
-		var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
-
 		return statext_is_compatible_clause_internal(root, (Node *) var,
 													 relid, attnums);
 	}
@@ -1235,3 +1225,53 @@ determine_operator_strategy(Oid opno)
 
 	return strat;
 }
+
+/*
+ * deconstruct_opexpr
+ *		Split expression into Var and Const parts.
+ *
+ * Attempts to match the arguments to either (Var op Const) or (Const op Var),
+ * possibly with a RelabelType on top of the Var node. When successful, returns
+ * true, otherwise returns false.
+ *
+ * Optionally returns pointers to the extracted elements, when passed non-null
+ * pointers (varp, cstp and isgtp).
+ */
+bool
+deconstruct_opexpr(OpExpr *expr, Var **varp, Const **cstp, bool *isgtp)
+{
+	Var	   *var;
+	Const  *cst;
+	bool	isgt;
+
+	/* enforced by statext_is_compatible_clause_internal */
+	Assert(list_length(expr->args) == 2);
+
+	if ((IsA(linitial(expr->args), Var) || IsA(linitial(expr->args), RelabelType)) &&
+		IsA(lsecond(expr->args), Const))
+	{
+		var = linitial(expr->args);
+		cst = lsecond(expr->args);
+		isgt = false;
+	}
+	else if (IsA(linitial(expr->args), Const) &&
+			 (IsA(lsecond(expr->args), Var) || IsA(lsecond(expr->args), RelabelType)))
+	{
+		var = lsecond(expr->args);
+		cst = linitial(expr->args);
+		isgt = true;
+	}
+	else
+		return false;
+
+	if (varp)
+		*varp = var;
+
+	if (cstp)
+		*cstp = cst;
+
+	if (isgtp)
+		*isgtp = isgt;
+
+	return true;
+}
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 1e919c82f9..0d7f6969ee 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1561,32 +1561,23 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 		if (is_opclause(clause))
 		{
 			OpExpr	   *expr = (OpExpr *) clause;
-			bool		varonleft = true;
-			bool		ok;
 			FmgrInfo	opproc;
 
-			fmgr_info(get_opcode(expr->opno), &opproc);
+			/* valid only after deconstruct_opexpr returns true  */
+			Var		   *var;
+			Const	   *cst;
+			bool		isgt;
 
-			ok = (NumRelids(clause) == 1) &&
-				(is_pseudo_constant_clause(lsecond(expr->args)) ||
-				 (varonleft = false,
-				  is_pseudo_constant_clause(linitial(expr->args))));
+			fmgr_info(get_opcode(expr->opno), &opproc);
 
-			if (ok)
+			/* extract the var and const from the expression */
+			if (deconstruct_opexpr(expr, &var, &cst, &isgt))
 			{
 				TypeCacheEntry *typecache;
 				FmgrInfo	gtproc;
-				Var		   *var;
-				Const	   *cst;
-				bool		isgt;
 				int			idx;
 				int			strategy;
 
-				/* extract the var and const from the expression */
-				var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
-				cst = (varonleft) ? lsecond(expr->args) : linitial(expr->args);
-				isgt = (!varonleft);
-
 				/* strip binary-compatible relabeling */
 				if (IsA(var, RelabelType))
 					var = (Var *) ((RelabelType *) var)->arg;
diff --git a/src/include/statistics/statistics.h b/src/include/statistics/statistics.h
index 82e2d5c619..f5120d0663 100644
--- a/src/include/statistics/statistics.h
+++ b/src/include/statistics/statistics.h
@@ -119,5 +119,6 @@ extern bool has_stats_of_kind(List *stats, char requiredkind);
 extern StatisticExtInfo *choose_best_statistics(List *stats,
 												Bitmapset *attnums, char requiredkind);
 extern int determine_operator_strategy(Oid opno);
+extern bool deconstruct_opexpr(OpExpr *expr, Var **varp, Const **cstp, bool *isgtp);
 
 #endif							/* STATISTICS_H */
-- 
2.20.1

From 1586963befe8fe7de473a28515bd7676fa2d0acd Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Sun, 14 Jul 2019 14:19:01 +0200
Subject: [PATCH 1/5] Use proper collations in extended statistics

The extended statistics code was a bit confused about which collation
to use when building the statistics and when computing the estimates.
For building it used a default collation for each data type, while for
estimation it used DEFAULT_COLLATION_OID. That's clearly inconsistent.

Commit 5e0928005 changed how this works for per-column statistics, in
which case we now use collation specified for each column - both for
building the statistics and selectivity estimation. This commit adopts
the same approach for extended statistics.

Note: One issue is that for per-column statistics we store collation
in pg_statistic catalog, but we don't store this in pg_statistic_ext.
So we'd have to either add another column into the catalog (which is
probably the right thing to do) or rely on info from pg_statistic.
But we probably need to add this into pg_statistic_ext, to allow stats
on expressions, or extended statistics with different collations.
---
 src/backend/statistics/mcv.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)

diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 913a72ff67..2e375edcb4 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -348,7 +348,7 @@ build_mss(VacAttrStats **stats, int numattrs)
 			elog(ERROR, "cache lookup failed for ordering operator for type %u",
 				 colstat->attrtypid);
 
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 	}
 
 	return mss;
@@ -668,7 +668,7 @@ statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
 
 		/* sort and deduplicate the data */
 		ssup[dim].ssup_cxt = CurrentMemoryContext;
-		ssup[dim].ssup_collation = DEFAULT_COLLATION_OID;
+		ssup[dim].ssup_collation = stats[dim]->attrcollid;
 		ssup[dim].ssup_nulls_first = false;
 
 		PrepareSortSupportFromOrderingOp(typentry->lt_opr, &ssup[dim]);
@@ -1577,8 +1577,6 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 
 			if (ok)
 			{
-				TypeCacheEntry *typecache;
-				FmgrInfo	gtproc;
 				Var		   *var;
 				Const	   *cst;
 				bool		isgt;
@@ -1596,10 +1594,6 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 				/* match the attribute to a dimension of the statistic */
 				idx = bms_member_index(keys, var->varattno);
 
-				/* get information about the >= procedure */
-				typecache = lookup_type_cache(var->vartype, TYPECACHE_GT_OPR);
-				fmgr_info(get_opcode(typecache->gt_opr), &gtproc);
-
 				/*
 				 * Walk through the MCV items and evaluate the current clause.
 				 * We can skip items that were already ruled out, and
@@ -1636,7 +1630,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 							 * or (const op var).
 							 */
 							mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																	   DEFAULT_COLLATION_OID,
+																	   var->varcollid,
 																	   cst->constvalue,
 																	   item->values[idx]));
 
@@ -1654,12 +1648,12 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 							 */
 							if (isgt)
 								mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																		   DEFAULT_COLLATION_OID,
+																		   var->varcollid,
 																		   cst->constvalue,
 																		   item->values[idx]));
 							else
 								mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																		   DEFAULT_COLLATION_OID,
+																		   var->varcollid,
 																		   item->values[idx],
 																		   cst->constvalue));
 
-- 
2.20.1

From ea6acd6285bf697a3a838c6df163aa4a3466a769 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Sat, 13 Jul 2019 00:12:16 +0200
Subject: [PATCH 2/5] Fix handling of opclauses in extended statistics

We expect opclauses to have exactly one Var and one Const, but the code
was checking the Const by calling is_pseudo_constant_clause() which is
incorrect - we need a proper constant.

Fixed by using plain IsA(x,Const) to check type of the node. We need to
do these checks in two places, so move it into a separate function that
can be called in both places.

Reported by Andreas Seltenreich, based on crash reported by sqlsmith.

Discussion: https://postgr.es/m/8736jdhbhc.fsf%40ansel.ydns.eu
---
 src/backend/statistics/extended_stats.c       | 74 ++++++++++++++++---
 src/backend/statistics/mcv.c                  | 27 ++-----
 .../statistics/extended_stats_internal.h      |  2 +
 3 files changed, 71 insertions(+), 32 deletions(-)

diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index c56ed48270..08032f1b28 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -796,21 +796,13 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
 		RangeTblEntry *rte = root->simple_rte_array[relid];
 		OpExpr	   *expr = (OpExpr *) clause;
 		Var		   *var;
-		bool		varonleft = true;
-		bool		ok;
 
 		/* Only expressions with two arguments are considered compatible. */
 		if (list_length(expr->args) != 2)
 			return false;
 
-		/* see if it actually has the right shape (one Var, one Const) */
-		ok = (NumRelids((Node *) expr) == 1) &&
-			(is_pseudo_constant_clause(lsecond(expr->args)) ||
-			 (varonleft = false,
-			  is_pseudo_constant_clause(linitial(expr->args))));
-
-		/* unsupported structure (two variables or so) */
-		if (!ok)
+		/* Check if the expression the right shape (one Var, one Const) */
+		if (!examine_opclause_expression(expr, &var, NULL, NULL))
 			return false;
 
 		/*
@@ -850,8 +842,6 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
 			!get_func_leakproof(get_opcode(expr->opno)))
 			return false;
 
-		var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
-
 		return statext_is_compatible_clause_internal(root, (Node *) var,
 													 relid, attnums);
 	}
@@ -1196,3 +1186,63 @@ statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
 
 	return sel;
 }
+
+/*
+ * examine_operator_expression
+ *		Split expression into Var and Const parts.
+ *
+ * Attempts to match the arguments to either (Var op Const) or (Const op Var),
+ * possibly with a RelabelType on top of the Var node. When successful, returns
+ * true, otherwise returns false.
+ *
+ * Optionally returns pointers to the extracted elements, when passed non-null
+ * pointers (varp, cstp and isgtp).
+ */
+bool
+examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *isgtp)
+{
+	Var	   *var;
+	Const  *cst;
+	bool	isgt;
+	Node   *leftop,
+		   *rightop;
+
+	/* enforced by statext_is_compatible_clause_internal */
+	Assert(list_length(expr->args) == 2);
+
+	leftop = linitial(expr->args);
+	rightop = lsecond(expr->args);
+
+	/* strip RelabelType from either side of the expression */
+	if (IsA(leftop, RelabelType))
+		leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+	if (IsA(rightop, RelabelType))
+		rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+	if (IsA(leftop, Var) && IsA(rightop, Const))
+	{
+		var = (Var *) leftop;
+		cst = (Const *) rightop;
+		isgt = false;
+	}
+	else if (IsA(leftop, Const) && IsA(rightop, Var))
+	{
+		var = (Var *) rightop;
+		cst = (Const *) leftop;
+		isgt = true;
+	}
+	else
+		return false;
+
+	if (varp)
+		*varp = var;
+
+	if (cstp)
+		*cstp = cst;
+
+	if (isgtp)
+		*isgtp = isgt;
+
+	return true;
+}
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 2e375edcb4..865981bbb4 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1561,36 +1561,23 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 		if (is_opclause(clause))
 		{
 			OpExpr	   *expr = (OpExpr *) clause;
-			bool		varonleft = true;
-			bool		ok;
 			FmgrInfo	opproc;
 
 			/* get procedure computing operator selectivity */
 			RegProcedure oprrest = get_oprrest(expr->opno);
 
-			fmgr_info(get_opcode(expr->opno), &opproc);
+			/* valid only after examine_opclause_expression returns true */
+			Var		   *var;
+			Const	   *cst;
+			bool		isgt;
 
-			ok = (NumRelids(clause) == 1) &&
-				(is_pseudo_constant_clause(lsecond(expr->args)) ||
-				 (varonleft = false,
-				  is_pseudo_constant_clause(linitial(expr->args))));
+			fmgr_info(get_opcode(expr->opno), &opproc);
 
-			if (ok)
+			/* extract the var and const from the expression */
+			if (examine_opclause_expression(expr, &var, &cst, &isgt))
 			{
-				Var		   *var;
-				Const	   *cst;
-				bool		isgt;
 				int			idx;
 
-				/* extract the var and const from the expression */
-				var = (varonleft) ? linitial(expr->args) : lsecond(expr->args);
-				cst = (varonleft) ? lsecond(expr->args) : linitial(expr->args);
-				isgt = (!varonleft);
-
-				/* strip binary-compatible relabeling */
-				if (IsA(var, RelabelType))
-					var = (Var *) ((RelabelType *) var)->arg;
-
 				/* match the attribute to a dimension of the statistic */
 				idx = bms_member_index(keys, var->varattno);
 
diff --git a/src/include/statistics/extended_stats_internal.h b/src/include/statistics/extended_stats_internal.h
index 8fc541993f..c7f01d4edc 100644
--- a/src/include/statistics/extended_stats_internal.h
+++ b/src/include/statistics/extended_stats_internal.h
@@ -97,6 +97,8 @@ extern SortItem *build_sorted_items(int numrows, int *nitems, HeapTuple *rows,
 									TupleDesc tdesc, MultiSortSupport mss,
 									int numattrs, AttrNumber *attnums);
 
+extern bool examine_opclause_expression(OpExpr *expr, Var **varp,
+										Const **cstp, bool *isgtp);
 
 extern Selectivity mcv_clauselist_selectivity(PlannerInfo *root,
 											  StatisticExtInfo *stat,
-- 
2.20.1

From f05c0b05d3760ff5295518dcac049ddd810a611e Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Mon, 15 Jul 2019 02:00:31 +0200
Subject: [PATCH 3/5] Fix handling of NULLs in MCV items and constants

There were two issues in how the extended statistics handled NULL values
in opclauses. Firstly, the code was oblivious to the possibility that
Const may be NULL (constisnull=true) in which case the constvalue is
undefined. We need to treat this as a mismatch, and not call the proc.

Secondly, the MCV item itself may contain NULL values too - the code
already did check that, and updated the match bitmap accordingly, but
failed to ensure we won't call the operator procedure anyway.

This fixes both issues by extending the existing check so that it looks
at constisnull too, and making sure it skips calling the procedure.

Discussion: https://postgr.es/m/8736jdhbhc.fsf%40ansel.ydns.eu
---
 src/backend/statistics/mcv.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 865981bbb4..77daa647e2 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1593,12 +1593,18 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 					MCVItem    *item = &mcvlist->items[i];
 
 					/*
-					 * For AND-lists, we can also mark NULL items as 'no
-					 * match' (and then skip them). For OR-lists this is not
-					 * possible.
+					 * When the MCV item or the Const value is NULL we can treat
+					 * this as a mismatch. We must not call the operator proc
+					 * because of strictness.
 					 */
-					if ((!is_or) && item->isnull[idx])
-						matches[i] = false;
+					if (item->isnull[idx] || cst->constisnull)
+					{
+						/* we only care about AND, because OR can't change */
+						if (!is_or)
+							matches[i] = false;
+
+						continue;
+					}
 
 					/* skip MCV items that were already ruled out */
 					if ((!is_or) && (matches[i] == false))
-- 
2.20.1

From 73619159fc4886dc35ecd933f1f54f695e4d61e5 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Mon, 15 Jul 2019 02:30:50 +0200
Subject: [PATCH 4/5] Refactor / simplify evaluation of MCV bitmap

---
 src/backend/statistics/mcv.c | 145 ++++++++++++++++-------------------
 1 file changed, 65 insertions(+), 80 deletions(-)

diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 77daa647e2..9697f3d101 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1504,6 +1504,37 @@ pg_mcv_list_send(PG_FUNCTION_ARGS)
 	return byteasend(fcinfo);
 }
 
+/*
+ * mcv_result_merge
+ *		Compute new value in result bitmap for AND/OR clauses.
+ *
+ * Compute new value for bitmap item, considering whether it's used for
+ * clauses connected by AND/OR.
+ */
+static bool
+mcv_result_merge(bool value, bool is_or, bool match)
+{
+	return (is_or) ? (value || match) : (value && match);
+}
+
+/*
+ * mcv_result_is_final
+ *		Decide if the current bitmap value may change.
+ *
+ * When processing a list of clauses, the bitmap item may get set to a value
+ * such that additional clauses can't change it. For example, when processing
+ * a list of clauses connected to AND, as soon as the item gets set to 'false'
+ * then it'll remain like that. Similarly clauses connected by OR and 'true'.
+ *
+ * Returns true when the value in the bitmap can't change no matter how the
+ * remaining clauses are evaluated.
+ */
+static bool
+mcv_result_is_final(bool value, bool is_or)
+{
+	return (is_or) ? value : (!value);
+}
+
 /*
  * mcv_get_match_bitmap
  *	Evaluate clauses using the MCV list, and update the match bitmap.
@@ -1589,27 +1620,27 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 				 */
 				for (i = 0; i < mcvlist->nitems; i++)
 				{
-					bool		mismatch = false;
+					bool		match = true;
 					MCVItem    *item = &mcvlist->items[i];
 
 					/*
-					 * When the MCV item or the Const value is NULL we can treat
-					 * this as a mismatch. We must not call the operator proc
-					 * because of strictness.
+					 * Handle NULL constants and NULL values in the MCV item by
+					 * simply considering this to be a mismatch.
+					 *
+					 * We must not call the opproc, because it might be strict.
 					 */
-					if (item->isnull[idx] || cst->constisnull)
+					if (cst->constisnull || item->isnull[idx])
 					{
-						/* we only care about AND, because OR can't change */
-						if (!is_or)
-							matches[i] = false;
-
+						matches[i] = mcv_result_merge(matches[i], is_or, false);
 						continue;
 					}
 
-					/* skip MCV items that were already ruled out */
-					if ((!is_or) && (matches[i] == false))
-						continue;
-					else if (is_or && (matches[i] == true))
+					/*
+					 * Skip MCV items that can't change result in the bitmap.
+					 * Once the value gets false for AND-lists, or true for
+					 * OR-lists, we don't need to look at more clauses.
+					 */
+					if (mcv_result_is_final(matches[i], is_or))
 						continue;
 
 					switch (oprrest)
@@ -1622,10 +1653,10 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 							 * it does not matter whether it's (var op const)
 							 * or (const op var).
 							 */
-							mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																	   var->varcollid,
-																	   cst->constvalue,
-																	   item->values[idx]));
+							match = DatumGetBool(FunctionCall2Coll(&opproc,
+																   var->varcollid,
+																   cst->constvalue,
+																   item->values[idx]));
 
 							break;
 
@@ -1640,39 +1671,21 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 							 * bucket, because there's no overlap).
 							 */
 							if (isgt)
-								mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																		   var->varcollid,
-																		   cst->constvalue,
-																		   item->values[idx]));
+								match = DatumGetBool(FunctionCall2Coll(&opproc,
+																	   var->varcollid,
+																	   cst->constvalue,
+																	   item->values[idx]));
 							else
-								mismatch = !DatumGetBool(FunctionCall2Coll(&opproc,
-																		   var->varcollid,
-																		   item->values[idx],
-																		   cst->constvalue));
+								match = DatumGetBool(FunctionCall2Coll(&opproc,
+																	   var->varcollid,
+																	   item->values[idx],
+																	   cst->constvalue));
 
 							break;
 					}
 
-					/*
-					 * XXX The conditions on matches[i] are not needed, as we
-					 * skip MCV items that can't become true/false, depending
-					 * on the current flag. See beginning of the loop over MCV
-					 * items.
-					 */
-
-					if ((is_or) && (!mismatch))
-					{
-						/* OR - was not a match before, matches now */
-						matches[i] = true;
-						continue;
-					}
-					else if ((!is_or) && mismatch)
-					{
-						/* AND - was a match before, does not match anymore */
-						matches[i] = false;
-						continue;
-					}
-
+					/* update the match bitmap with the result */
+					matches[i] = mcv_result_merge(matches[i], is_or, match);
 				}
 			}
 		}
@@ -1707,10 +1720,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 				}
 
 				/* now, update the match bitmap, depending on OR/AND type */
-				if (is_or)
-					matches[i] = Max(matches[i], match);
-				else
-					matches[i] = Min(matches[i], match);
+				matches[i] = mcv_result_merge(matches[i], is_or, match);
 			}
 		}
 		else if (is_orclause(clause) || is_andclause(clause))
@@ -1737,13 +1747,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 			 * condition when merging the results.
 			 */
 			for (i = 0; i < mcvlist->nitems; i++)
-			{
-				/* Is this OR or AND clause? */
-				if (is_or)
-					matches[i] = Max(matches[i], bool_matches[i]);
-				else
-					matches[i] = Min(matches[i], bool_matches[i]);
-			}
+				matches[i] = mcv_result_merge(matches[i], is_or, bool_matches[i]);
 
 			pfree(bool_matches);
 		}
@@ -1767,25 +1771,11 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 
 			/*
 			 * Merge the bitmap produced by mcv_get_match_bitmap into the
-			 * current one.
+			 * current one. We're handling a NOT clause, so invert the result
+			 * before merging it into the global bitmap.
 			 */
 			for (i = 0; i < mcvlist->nitems; i++)
-			{
-				/*
-				 * When handling a NOT clause, we need to invert the result
-				 * before merging it into the global result.
-				 */
-				if (not_matches[i] == false)
-					not_matches[i] = true;
-				else
-					not_matches[i] = false;
-
-				/* Is this OR or AND clause? */
-				if (is_or)
-					matches[i] = Max(matches[i], not_matches[i]);
-				else
-					matches[i] = Min(matches[i], not_matches[i]);
-			}
+				matches[i] = mcv_result_merge(matches[i], is_or, !not_matches[i]);
 
 			pfree(not_matches);
 		}
@@ -1814,17 +1804,12 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 				if (!item->isnull[idx] && DatumGetBool(item->values[idx]))
 					match = true;
 
-				/* now, update the match bitmap, depending on OR/AND type */
-				if (is_or)
-					matches[i] = Max(matches[i], match);
-				else
-					matches[i] = Min(matches[i], match);
+				/* update the result bitmap */
+				matches[i] = mcv_result_merge(matches[i], is_or, match);
 			}
 		}
 		else
-		{
 			elog(ERROR, "unknown clause type: %d", clause->type);
-		}
 	}
 
 	return matches;
-- 
2.20.1

From 976fdd2f13eaa14e356f0f3a003c6503d907b111 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Thu, 18 Jul 2019 12:28:16 +0200
Subject: [PATCH] Use column collation for extended statistics

The current extended statistics code was a bit confused which collation
to use.  When building the statistics, the collations defined as default
for the data types were used (since commit 5e0928005).  The MCV code was
however using the column collations for MCV serialization, and then
DEFAULT_COLLATION_OID when computing estimates. So overall the code was
using all three possible options, inconsistently.

This uses the column colation everywhere - this makes it consistent with
what 5e0928005 did for regular stats.  We however do not track the
collations in a catalog, because we can derive them from column-level
information.  This may need to change in the future, e.g. after allowing
statistics on expressions.

Discussion: https://postgr.es/m/8736jdhbhc.fsf%40ansel.ydns.eu
Backpatch-to: 12
---
 src/backend/statistics/dependencies.c |  2 +-
 src/backend/statistics/mcv.c          | 10 +++++-----
 src/backend/statistics/mvdistinct.c   |  2 +-
 3 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c
index 66c38ce2bc..585cad2ad9 100644
--- a/src/backend/statistics/dependencies.c
+++ b/src/backend/statistics/dependencies.c
@@ -273,7 +273,7 @@ dependency_degree(int numrows, HeapTuple *rows, int k, AttrNumber *dependency,
 				 colstat->attrtypid);
 
 		/* prepare the sort function for this dimension */
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 	}
 
 	/*
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index e5a4e86c5d..ef66029caa 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -366,7 +366,7 @@ build_mss(VacAttrStats **stats, int numattrs)
 			elog(ERROR, "cache lookup failed for ordering operator for type %u",
 				 colstat->attrtypid);
 
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 	}
 
 	return mss;
@@ -686,7 +686,7 @@ statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
 
 		/* sort and deduplicate the data */
 		ssup[dim].ssup_cxt = CurrentMemoryContext;
-		ssup[dim].ssup_collation = DEFAULT_COLLATION_OID;
+		ssup[dim].ssup_collation = stats[dim]->attrcollid;
 		ssup[dim].ssup_nulls_first = false;
 
 		PrepareSortSupportFromOrderingOp(typentry->lt_opr, &ssup[dim]);
@@ -1640,7 +1640,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 							 * or (const op var).
 							 */
 							match = DatumGetBool(FunctionCall2Coll(&opproc,
-																   DEFAULT_COLLATION_OID,
+																   var->varcollid,
 																   cst->constvalue,
 																   item->values[idx]));
 
@@ -1658,12 +1658,12 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 							 */
 							if (isgt)
 								match = DatumGetBool(FunctionCall2Coll(&opproc,
-																	   DEFAULT_COLLATION_OID,
+																	   var->varcollid,
 																	   cst->constvalue,
 																	   item->values[idx]));
 							else
 								match = DatumGetBool(FunctionCall2Coll(&opproc,
-																	   DEFAULT_COLLATION_OID,
+																	   var->varcollid,
 																	   item->values[idx],
 																	   cst->constvalue));
 
diff --git a/src/backend/statistics/mvdistinct.c b/src/backend/statistics/mvdistinct.c
index 9ebf183d90..228fa2684f 100644
--- a/src/backend/statistics/mvdistinct.c
+++ b/src/backend/statistics/mvdistinct.c
@@ -477,7 +477,7 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows,
 				 colstat->attrtypid);
 
 		/* prepare the sort function for this dimension */
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 
 		/* accumulate all the data for this dimension into the arrays */
 		for (j = 0; j < numrows; j++)
-- 
2.21.0

From 14dc49ad7eefd6e67b751e74ce7253cdc85ca5ad Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Fri, 19 Jul 2019 16:28:28 +0200
Subject: [PATCH 1/2] Rework examine_opclause_expression to use varonleft

The examine_opclause_expression function needs to return information on
which side of the operator we found the Var, but the variable was called
"isgt" which is rather misleading (it assumes the operator is either
less-than or greater-than, but it may be equality or something else).
Other places in the planner use a variable called "varonleft" for this
purpose, so just adopt the same convention here.

The code also assumed we don't care about this flag for equality, as
(Var = Const) and (Const = Var) should be the same thing. But that does
not work for cross-type operators, in which case we need to pass the
parameters to the procedure in the right order. So just use the same
code for all types of expressions.

This means we don't need to care about the selectivity estimation
function anymore, at least not in this code. We should only get the
supported cases here (thanks to statext_is_compatible_clause).

Discussion: https://postgr.es/m/8736jdhbhc.fsf%40ansel.ydns.eu
Backpatch-to: 12
---
 src/backend/statistics/extended_stats.c       | 16 ++---
 src/backend/statistics/mcv.c                  | 62 +++++--------------
 .../statistics/extended_stats_internal.h      |  2 +-
 3 files changed, 26 insertions(+), 54 deletions(-)

diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index d2346cbe02..23c74f7d90 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -1196,15 +1196,15 @@ statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
  * returns true, otherwise returns false.
  *
  * Optionally returns pointers to the extracted Var/Const nodes, when passed
- * non-null pointers (varp, cstp and isgtp). The isgt flag specifies whether
- * the Var node is on the left (false) or right (true) side of the operator.
+ * non-null pointers (varp, cstp and varonleftp). The varonleftp flag specifies
+ * on which side of the operator we found the Var node.
  */
 bool
-examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *isgtp)
+examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *varonleftp)
 {
 	Var	   *var;
 	Const  *cst;
-	bool	isgt;
+	bool	varonleft;
 	Node   *leftop,
 		   *rightop;
 
@@ -1225,13 +1225,13 @@ examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *isgtp)
 	{
 		var = (Var *) leftop;
 		cst = (Const *) rightop;
-		isgt = false;
+		varonleft = true;
 	}
 	else if (IsA(leftop, Const) && IsA(rightop, Var))
 	{
 		var = (Var *) rightop;
 		cst = (Const *) leftop;
-		isgt = true;
+		varonleft = false;
 	}
 	else
 		return false;
@@ -1243,8 +1243,8 @@ examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *isgtp)
 	if (cstp)
 		*cstp = cst;
 
-	if (isgtp)
-		*isgtp = isgt;
+	if (varonleftp)
+		*varonleftp = varonleft;
 
 	return true;
 }
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index e5a4e86c5d..2b685ec67a 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1581,18 +1581,15 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 			OpExpr	   *expr = (OpExpr *) clause;
 			FmgrInfo	opproc;
 
-			/* get procedure computing operator selectivity */
-			RegProcedure oprrest = get_oprrest(expr->opno);
-
 			/* valid only after examine_opclause_expression returns true */
 			Var		   *var;
 			Const	   *cst;
-			bool		isgt;
+			bool		varonleft;
 
 			fmgr_info(get_opcode(expr->opno), &opproc);
 
 			/* extract the var and const from the expression */
-			if (examine_opclause_expression(expr, &var, &cst, &isgt))
+			if (examine_opclause_expression(expr, &var, &cst, &varonleft))
 			{
 				int			idx;
 
@@ -1629,46 +1626,21 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 					if (RESULT_IS_FINAL(matches[i], is_or))
 						continue;
 
-					switch (oprrest)
-					{
-						case F_EQSEL:
-						case F_NEQSEL:
-
-							/*
-							 * We don't care about isgt in equality, because
-							 * it does not matter whether it's (var op const)
-							 * or (const op var).
-							 */
-							match = DatumGetBool(FunctionCall2Coll(&opproc,
-																   DEFAULT_COLLATION_OID,
-																   cst->constvalue,
-																   item->values[idx]));
-
-							break;
-
-						case F_SCALARLTSEL: /* column < constant */
-						case F_SCALARLESEL: /* column <= constant */
-						case F_SCALARGTSEL: /* column > constant */
-						case F_SCALARGESEL: /* column >= constant */
-
-							/*
-							 * First check whether the constant is below the
-							 * lower boundary (in that case we can skip the
-							 * bucket, because there's no overlap).
-							 */
-							if (isgt)
-								match = DatumGetBool(FunctionCall2Coll(&opproc,
-																	   DEFAULT_COLLATION_OID,
-																	   cst->constvalue,
-																	   item->values[idx]));
-							else
-								match = DatumGetBool(FunctionCall2Coll(&opproc,
-																	   DEFAULT_COLLATION_OID,
-																	   item->values[idx],
-																	   cst->constvalue));
-
-							break;
-					}
+					/*
+					 * First check whether the constant is below the lower
+					 * boundary (in that case we can skip the bucket, because
+					 * there's no overlap).
+					 */
+					if (varonleft)
+						match = DatumGetBool(FunctionCall2Coll(&opproc,
+															   DEFAULT_COLLATION_OID,
+															   item->values[idx],
+															   cst->constvalue));
+					else
+						match = DatumGetBool(FunctionCall2Coll(&opproc,
+															   DEFAULT_COLLATION_OID,
+															   cst->constvalue,
+															   item->values[idx]));
 
 					/* update the match bitmap with the result */
 					matches[i] = RESULT_MERGE(matches[i], is_or, match);
diff --git a/src/include/statistics/extended_stats_internal.h b/src/include/statistics/extended_stats_internal.h
index c7f01d4edc..8433c34f6d 100644
--- a/src/include/statistics/extended_stats_internal.h
+++ b/src/include/statistics/extended_stats_internal.h
@@ -98,7 +98,7 @@ extern SortItem *build_sorted_items(int numrows, int *nitems, HeapTuple *rows,
 									int numattrs, AttrNumber *attnums);
 
 extern bool examine_opclause_expression(OpExpr *expr, Var **varp,
-										Const **cstp, bool *isgtp);
+										Const **cstp, bool *varonleftp);
 
 extern Selectivity mcv_clauselist_selectivity(PlannerInfo *root,
 											  StatisticExtInfo *stat,
-- 
2.21.0

From 409b0243f14e91b922a08ab2e1e5fca71284d3e3 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Thu, 18 Jul 2019 12:28:16 +0200
Subject: [PATCH 2/2] Use column collation for extended statistics

The current extended statistics code was a bit confused which collation
to use.  When building the statistics, the collations defined as default
for the data types were used (since commit 5e0928005).  The MCV code was
however using the column collations for MCV serialization, and then
DEFAULT_COLLATION_OID when computing estimates. So overall the code was
using all three possible options, inconsistently.

This uses the column colation everywhere - this makes it consistent with
what 5e0928005 did for regular stats.  We however do not track the
collations in a catalog, because we can derive them from column-level
information.  This may need to change in the future, e.g. after allowing
statistics on expressions.

Discussion: https://postgr.es/m/8736jdhbhc.fsf%40ansel.ydns.eu
Backpatch-to: 12
---
 src/backend/commands/statscmds.c      |  4 ++++
 src/backend/statistics/dependencies.c |  2 +-
 src/backend/statistics/mcv.c          | 15 +++++++++++----
 src/backend/statistics/mvdistinct.c   |  2 +-
 4 files changed, 17 insertions(+), 6 deletions(-)

diff --git a/src/backend/commands/statscmds.c b/src/backend/commands/statscmds.c
index cf406f6f96..34d11c2a98 100644
--- a/src/backend/commands/statscmds.c
+++ b/src/backend/commands/statscmds.c
@@ -485,6 +485,10 @@ RemoveStatisticsById(Oid statsOid)
  *
  * For MCV lists that's not the case, as those statistics store the datums
  * internally. In this case we simply reset the statistics value to NULL.
+ *
+ * Note that "type change" includes collation change, which means we can rely
+ * on the MCV list being consistent with the collation info in pg_attribute
+ * during estimation.
  */
 void
 UpdateStatisticsForTypeChange(Oid statsOid, Oid relationOid, int attnum,
diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c
index 66c38ce2bc..585cad2ad9 100644
--- a/src/backend/statistics/dependencies.c
+++ b/src/backend/statistics/dependencies.c
@@ -273,7 +273,7 @@ dependency_degree(int numrows, HeapTuple *rows, int k, AttrNumber *dependency,
 				 colstat->attrtypid);
 
 		/* prepare the sort function for this dimension */
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 	}
 
 	/*
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 2b685ec67a..cec06f8c44 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -366,7 +366,7 @@ build_mss(VacAttrStats **stats, int numattrs)
 			elog(ERROR, "cache lookup failed for ordering operator for type %u",
 				 colstat->attrtypid);
 
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 	}
 
 	return mss;
@@ -686,7 +686,7 @@ statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
 
 		/* sort and deduplicate the data */
 		ssup[dim].ssup_cxt = CurrentMemoryContext;
-		ssup[dim].ssup_collation = DEFAULT_COLLATION_OID;
+		ssup[dim].ssup_collation = stats[dim]->attrcollid;
 		ssup[dim].ssup_nulls_first = false;
 
 		PrepareSortSupportFromOrderingOp(typentry->lt_opr, &ssup[dim]);
@@ -1630,15 +1630,22 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
 					 * First check whether the constant is below the lower
 					 * boundary (in that case we can skip the bucket, because
 					 * there's no overlap).
+					 *
+					 * We don't store collations used to build the statistics,
+					 * but we can use the collation for the attribute itself,
+					 * as stored in varcollid. We do reset the statistics after
+					 * a type change (including collation change), so this is
+					 * OK. We may need to relax this after allowing extended
+					 * statistics on expressions.
 					 */
 					if (varonleft)
 						match = DatumGetBool(FunctionCall2Coll(&opproc,
-															   DEFAULT_COLLATION_OID,
+															   var->varcollid,
 															   item->values[idx],
 															   cst->constvalue));
 					else
 						match = DatumGetBool(FunctionCall2Coll(&opproc,
-															   DEFAULT_COLLATION_OID,
+															   var->varcollid,
 															   cst->constvalue,
 															   item->values[idx]));
 
diff --git a/src/backend/statistics/mvdistinct.c b/src/backend/statistics/mvdistinct.c
index 536605b83d..f3383c05d9 100644
--- a/src/backend/statistics/mvdistinct.c
+++ b/src/backend/statistics/mvdistinct.c
@@ -477,7 +477,7 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows,
 				 colstat->attrtypid);
 
 		/* prepare the sort function for this dimension */
-		multi_sort_add_dimension(mss, i, type->lt_opr, type->typcollation);
+		multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
 
 		/* accumulate all the data for this dimension into the arrays */
 		for (j = 0; j < numrows; j++)
-- 
2.21.0