Revise collation derivation method and expression-tree representation.

All expression nodes now have an explicit output-collation field, unless
they are known to only return a noncollatable data type (such as boolean
or record).  Also, nodes that can invoke collation-aware functions store
a separate field that is the collation value to pass to the function.
This avoids confusion that arises when a function has collatable inputs
and noncollatable output type, or vice versa.

Also, replace the parser's on-the-fly collation assignment method with
a post-pass over the completed expression tree.  This allows us to use
a more complex (and hopefully more nearly spec-compliant) assignment
rule without paying for it in extra storage in every expression node.

Fix assorted bugs in the planner's handling of collations by making
collation one of the defining properties of an EquivalenceClass and
by converting CollateExprs into discardable RelabelType nodes during
expression preprocessing.

15 files changed, 134 insertions, 64 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 657015616cd..c10de537bec 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201103112
+#define CATALOG_VERSION_NO	201103191
 
 #endif
diff --git a/src/include/fmgr.h b/src/include/fmgr.h
index 7539acace82..9e5224d374d 100644
--- a/src/include/fmgr.h
+++ b/src/include/fmgr.h
@@ -40,6 +40,11 @@ typedef Datum (*PGFunction) (FunctionCallInfo fcinfo);
  * before a function can be called through fmgr.  If the same function is
  * to be called multiple times, the lookup need be done only once and the
  * info struct saved for re-use.
+ *
+ * Note that fn_collation and fn_expr really are parse-time-determined
+ * information about the arguments, rather than about the function itself.
+ * But it's convenient to store them here rather than in FunctionCallInfoData,
+ * where they might more logically belong.
  */
 typedef struct FmgrInfo
 {
@@ -50,7 +55,7 @@ typedef struct FmgrInfo
 	bool		fn_strict;		/* function is "strict" (NULL in => NULL out) */
 	bool		fn_retset;		/* function returns a set */
 	unsigned char fn_stats;		/* collect stats if track_functions > this */
-	Oid			fn_collation;	/* collation to use */
+	Oid			fn_collation;	/* collation that function should use */
 	void	   *fn_extra;		/* extra space for use by handler */
 	MemoryContext fn_mcxt;		/* memory context to store fn_extra in */
 	fmNodePtr	fn_expr;		/* expression parse tree for call, or NULL */
@@ -84,15 +89,11 @@ extern void fmgr_info(Oid functionId, FmgrInfo *finfo);
 extern void fmgr_info_cxt(Oid functionId, FmgrInfo *finfo,
 			  MemoryContext mcxt);
 
-/*
- * Initialize the fn_collation field
- */
-extern void fmgr_info_collation(Oid collationId, FmgrInfo *finfo);
-
-/*
- * Initialize the fn_expr field and set the collation based on it
- */
-extern void fmgr_info_expr(fmNodePtr expr, FmgrInfo *finfo);
+/* Macros for setting the fn_collation and fn_expr fields */
+#define fmgr_info_set_collation(collationId, finfo) \
+	((finfo)->fn_collation = (collationId))
+#define fmgr_info_set_expr(expr, finfo) \
+	((finfo)->fn_expr = (expr))
 
 /*
  * Copy an FmgrInfo struct
@@ -147,6 +148,12 @@ extern void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo,
 #define PG_FUNCTION_ARGS	FunctionCallInfo fcinfo
 
 /*
+ * Get collation function should use.
+ */
+#define PG_GET_COLLATION() \
+	(fcinfo->flinfo ? fcinfo->flinfo->fn_collation : InvalidOid)
+
+/*
  * Get number of arguments passed to function.
  */
 #define PG_NARGS() (fcinfo->nargs)
@@ -307,7 +314,6 @@ extern struct varlena *pg_detoast_datum_packed(struct varlena * datum);
 #define PG_RETURN_VARCHAR_P(x) PG_RETURN_POINTER(x)
 #define PG_RETURN_HEAPTUPLEHEADER(x)  PG_RETURN_POINTER(x)
 
-#define PG_GET_COLLATION()		(fcinfo->flinfo ? fcinfo->flinfo->fn_collation : InvalidOid)
 
 /*-------------------------------------------------------------------------
  *		Support for detecting call convention of dynamically-loaded functions
@@ -450,7 +456,7 @@ extern Datum DirectFunctionCall9(PGFunction func, Datum arg1, Datum arg2,
 					Datum arg6, Datum arg7, Datum arg8,
 					Datum arg9);
 
-/* the same but passing a collation */
+/* The same, but passing a collation to use */
 extern Datum DirectFunctionCall1WithCollation(PGFunction func, Oid collation,
 											  Datum arg1);
 extern Datum DirectFunctionCall2WithCollation(PGFunction func, Oid collation,
diff --git a/src/include/nodes/makefuncs.h b/src/include/nodes/makefuncs.h
index 6691b0dc77e..ead7c403cce 100644
--- a/src/include/nodes/makefuncs.h
+++ b/src/include/nodes/makefuncs.h
@@ -62,7 +62,7 @@ extern Expr *makeBoolExpr(BoolExprType boolop, List *args, int location);
 extern Alias *makeAlias(const char *aliasname, List *colnames);
 
 extern RelabelType *makeRelabelType(Expr *arg, Oid rtype, int32 rtypmod,
-				CoercionForm rformat);
+									Oid rcollid, CoercionForm rformat);
 
 extern RangeVar *makeRangeVar(char *schemaname, char *relname, int location);
 
@@ -70,8 +70,8 @@ extern TypeName *makeTypeName(char *typnam);
 extern TypeName *makeTypeNameFromNameList(List *names);
 extern TypeName *makeTypeNameFromOid(Oid typeOid, int32 typmod);
 
-extern FuncExpr *makeFuncExpr(Oid funcid, Oid rettype,
-			 List *args, Oid collid, CoercionForm fformat);
+extern FuncExpr *makeFuncExpr(Oid funcid, Oid rettype, List *args,
+			 Oid funccollid, Oid inputcollid, CoercionForm fformat);
 
 extern DefElem *makeDefElem(char *name, Node *arg);
 extern DefElem *makeDefElemExtended(char *nameSpace, char *name, Node *arg,
diff --git a/src/include/nodes/nodeFuncs.h b/src/include/nodes/nodeFuncs.h
index 32f09f68ad1..591f2a9ca03 100644
--- a/src/include/nodes/nodeFuncs.h
+++ b/src/include/nodes/nodeFuncs.h
@@ -21,17 +21,21 @@
 #define QTW_IGNORE_CTE_SUBQUERIES	0x02		/* subqueries in cteList */
 #define QTW_IGNORE_RC_SUBQUERIES	0x03		/* both of above */
 #define QTW_IGNORE_JOINALIASES		0x04		/* JOIN alias var lists */
-#define QTW_EXAMINE_RTES			0x08		/* examine RTEs */
-#define QTW_DONT_COPY_QUERY			0x10		/* do not copy top Query */
+#define QTW_IGNORE_RANGE_TABLE		0x08		/* skip rangetable entirely */
+#define QTW_EXAMINE_RTES			0x10		/* examine RTEs */
+#define QTW_DONT_COPY_QUERY			0x20		/* do not copy top Query */
 
 
 extern Oid	exprType(Node *expr);
 extern int32 exprTypmod(Node *expr);
-extern Oid	exprCollation(Node *expr);
-extern Oid coercion_expression_result_collation(Oid resulttype, Node *arg);
 extern bool exprIsLengthCoercion(Node *expr, int32 *coercedTypmod);
 extern bool expression_returns_set(Node *clause);
 
+extern Oid	exprCollation(Node *expr);
+extern Oid	exprInputCollation(Node *expr);
+extern void exprSetCollation(Node *expr, Oid collation);
+extern void exprSetInputCollation(Node *expr, Oid inputcollation);
+
 extern int	exprLocation(Node *expr);
 
 extern bool expression_tree_walker(Node *node, bool (*walker) (),
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 8ed819b4dd4..d8bc6b82143 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -137,6 +137,7 @@ typedef enum NodeTag
 	T_NamedArgExpr,
 	T_OpExpr,
 	T_DistinctExpr,
+	T_NullIfExpr,
 	T_ScalarArrayOpExpr,
 	T_BoolExpr,
 	T_SubLink,
@@ -158,7 +159,6 @@ typedef enum NodeTag
 	T_CoalesceExpr,
 	T_MinMaxExpr,
 	T_XmlExpr,
-	T_NullIfExpr,
 	T_NullTest,
 	T_BooleanTest,
 	T_CoerceToDomain,
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 904bd5e9e18..b7e7104f44d 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -787,7 +787,12 @@ typedef struct RangeTblEntry
  *
  * In an ORDER BY item, all fields must be valid.  (The eqop isn't essential
  * here, but it's cheap to get it along with the sortop, and requiring it
- * to be valid eases comparisons to grouping items.)
+ * to be valid eases comparisons to grouping items.)  Note that this isn't
+ * actually enough information to determine an ordering: if the sortop is
+ * collation-sensitive, a collation OID is needed too.  We don't store the
+ * collation in SortGroupClause because it's not available at the time the
+ * parser builds the SortGroupClause; instead, consult the exposed collation
+ * of the referenced targetlist expression to find out what it is.
  *
  * In a grouping item, eqop must be valid.	If the eqop is a btree equality
  * operator, then sortop should be set to a compatible ordering operator.
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 41fd56e1bf1..609f253c077 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -139,7 +139,7 @@ typedef struct Var
 								 * all */
 	Oid			vartype;		/* pg_type OID for the type of this var */
 	int32		vartypmod;		/* pg_attribute typmod value */
-	Oid			varcollid;		/* collation */
+	Oid			varcollid;		/* OID of collation, or InvalidOid if none */
 	Index		varlevelsup;	/* for subquery variables referencing outer
 								 * relations; 0 in a normal var, >0 means N
 								 * levels up */
@@ -156,7 +156,7 @@ typedef struct Const
 	Expr		xpr;
 	Oid			consttype;		/* pg_type OID of the constant's datatype */
 	int32		consttypmod;	/* typmod value, if any */
-	Oid			constcollid;	/* collation */
+	Oid			constcollid;	/* OID of collation, or InvalidOid if none */
 	int			constlen;		/* typlen of the constant's datatype */
 	Datum		constvalue;		/* the constant's value */
 	bool		constisnull;	/* whether the constant is null (if true,
@@ -207,7 +207,7 @@ typedef struct Param
 	int			paramid;		/* numeric ID for parameter */
 	Oid			paramtype;		/* pg_type OID of parameter's datatype */
 	int32		paramtypmod;	/* typmod value, if known */
-	Oid			paramcollation;	/* parameter's collation */
+	Oid			paramcollid;	/* OID of collation, or InvalidOid if none */
 	int			location;		/* token location, or -1 if unknown */
 } Param;
 
@@ -231,12 +231,13 @@ typedef struct Aggref
 	Expr		xpr;
 	Oid			aggfnoid;		/* pg_proc Oid of the aggregate */
 	Oid			aggtype;		/* type Oid of result of the aggregate */
+	Oid			aggcollid;		/* OID of collation of result */
+	Oid			inputcollid;	/* OID of collation that function should use */
 	List	   *args;			/* arguments and sort expressions */
 	List	   *aggorder;		/* ORDER BY (list of SortGroupClause) */
 	List	   *aggdistinct;	/* DISTINCT (list of SortGroupClause) */
 	bool		aggstar;		/* TRUE if argument list was really '*' */
 	Index		agglevelsup;	/* > 0 if agg belongs to outer query */
-	Oid			collid;			/* collation OID to use by function */
 	int			location;		/* token location, or -1 if unknown */
 } Aggref;
 
@@ -248,11 +249,12 @@ typedef struct WindowFunc
 	Expr		xpr;
 	Oid			winfnoid;		/* pg_proc Oid of the function */
 	Oid			wintype;		/* type Oid of result of the window function */
+	Oid			wincollid;		/* OID of collation of result */
+	Oid			inputcollid;	/* OID of collation that function should use */
 	List	   *args;			/* arguments to the window function */
 	Index		winref;			/* index of associated WindowClause */
 	bool		winstar;		/* TRUE if argument list was really '*' */
 	bool		winagg;			/* is function a simple aggregate? */
-	Oid			collid;			/* collation OID to use by function */
 	int			location;		/* token location, or -1 if unknown */
 } WindowFunc;
 
@@ -284,7 +286,7 @@ typedef struct ArrayRef
 	Oid			refarraytype;	/* type of the array proper */
 	Oid			refelemtype;	/* type of the array elements */
 	int32		reftypmod;		/* typmod of the array (and elements too) */
-	Oid			refcollid;		/* collation */
+	Oid			refcollid;		/* OID of collation, or InvalidOid if none */
 	List	   *refupperindexpr;/* expressions that evaluate to upper array
 								 * indexes */
 	List	   *reflowerindexpr;/* expressions that evaluate to lower array
@@ -329,8 +331,9 @@ typedef struct FuncExpr
 	Oid			funcresulttype; /* PG_TYPE OID of result value */
 	bool		funcretset;		/* true if function returns set */
 	CoercionForm funcformat;	/* how to display this function call */
+	Oid			funccollid;		/* OID of collation of result */
+	Oid			inputcollid;	/* OID of collation that function should use */
 	List	   *args;			/* arguments to the function */
-	Oid			collid;			/* collation OID to use by function */
 	int			location;		/* token location, or -1 if unknown */
 } FuncExpr;
 
@@ -373,8 +376,9 @@ typedef struct OpExpr
 	Oid			opfuncid;		/* PG_PROC OID of underlying function */
 	Oid			opresulttype;	/* PG_TYPE OID of result value */
 	bool		opretset;		/* true if operator returns set */
+	Oid			opcollid;		/* OID of collation of result */
+	Oid			inputcollid;	/* OID of collation that operator should use */
 	List	   *args;			/* arguments to the operator (1 or 2) */
-	Oid			collid;			/* collation OID to use by operator */
 	int			location;		/* token location, or -1 if unknown */
 } OpExpr;
 
@@ -391,6 +395,14 @@ typedef struct OpExpr
 typedef OpExpr DistinctExpr;
 
 /*
+ * NullIfExpr - a NULLIF expression
+ *
+ * Like DistinctExpr, this is represented the same as an OpExpr referencing
+ * the "=" operator for x and y.
+ */
+typedef OpExpr NullIfExpr;
+
+/*
  * ScalarArrayOpExpr - expression node for "scalar op ANY/ALL (array)"
  *
  * The operator must yield boolean.  It is applied to the left operand
@@ -398,7 +410,7 @@ typedef OpExpr DistinctExpr;
  * with OR or AND (for ANY or ALL respectively).  The node representation
  * is almost the same as for the underlying operator, but we need a useOr
  * flag to remember whether it's ANY or ALL, and we don't have to store
- * the result type because it must be boolean.
+ * the result type (or the collation) because it must be boolean.
  */
 typedef struct ScalarArrayOpExpr
 {
@@ -406,8 +418,8 @@ typedef struct ScalarArrayOpExpr
 	Oid			opno;			/* PG_OPERATOR OID of the operator */
 	Oid			opfuncid;		/* PG_PROC OID of underlying function */
 	bool		useOr;			/* true for ANY, false for ALL */
+	Oid			inputcollid;	/* OID of collation that operator should use */
 	List	   *args;			/* the scalar and array operands */
-	Oid			collid;			/* collation OID to use by operator */
 	int			location;		/* token location, or -1 if unknown */
 } ScalarArrayOpExpr;
 
@@ -602,7 +614,7 @@ typedef struct FieldSelect
 	Oid			resulttype;		/* type of the field (result type of this
 								 * node) */
 	int32		resulttypmod;	/* output typmod (usually -1) */
-	Oid			resultcollation;/* collation of the field */
+	Oid			resultcollid;	/* OID of collation of the field */
 } FieldSelect;
 
 /* ----------------
@@ -627,7 +639,7 @@ typedef struct FieldStore
 	List	   *newvals;		/* new value(s) for field(s) */
 	List	   *fieldnums;		/* integer list of field attnums */
 	Oid			resulttype;		/* type of result (same as type of arg) */
-	/* Like RowExpr, we deliberately omit a typmod here */
+	/* Like RowExpr, we deliberately omit a typmod and collation here */
 } FieldStore;
 
 /* ----------------
@@ -649,6 +661,7 @@ typedef struct RelabelType
 	Expr	   *arg;			/* input expression */
 	Oid			resulttype;		/* output type of coercion expression */
 	int32		resulttypmod;	/* output typmod (usually -1) */
+	Oid			resultcollid;	/* OID of collation, or InvalidOid if none */
 	CoercionForm relabelformat; /* how to display this node */
 	int			location;		/* token location, or -1 if unknown */
 } RelabelType;
@@ -668,6 +681,7 @@ typedef struct CoerceViaIO
 	Expr	   *arg;			/* input expression */
 	Oid			resulttype;		/* output type of coercion */
 	/* output typmod is not stored, but is presumed -1 */
+	Oid			resultcollid;	/* OID of collation, or InvalidOid if none */
 	CoercionForm coerceformat;	/* how to display this node */
 	int			location;		/* token location, or -1 if unknown */
 } CoerceViaIO;
@@ -691,6 +705,7 @@ typedef struct ArrayCoerceExpr
 	Oid			elemfuncid;		/* OID of element coercion function, or 0 */
 	Oid			resulttype;		/* output type of coercion (an array type) */
 	int32		resulttypmod;	/* output typmod (also element typmod) */
+	Oid			resultcollid;	/* OID of collation, or InvalidOid if none */
 	bool		isExplicit;		/* conversion semantics flag to pass to func */
 	CoercionForm coerceformat;	/* how to display this node */
 	int			location;		/* token location, or -1 if unknown */
@@ -713,13 +728,16 @@ typedef struct ConvertRowtypeExpr
 	Expr		xpr;
 	Expr	   *arg;			/* input expression */
 	Oid			resulttype;		/* output type (always a composite type) */
-	/* result typmod is not stored, but must be -1; see RowExpr comments */
+	/* Like RowExpr, we deliberately omit a typmod and collation here */
 	CoercionForm convertformat; /* how to display this node */
 	int			location;		/* token location, or -1 if unknown */
 } ConvertRowtypeExpr;
 
 /*----------
  * CollateExpr - COLLATE
+ *
+ * The planner replaces CollateExpr with RelabelType during expression
+ * preprocessing, so execution never sees a CollateExpr.
  *----------
  */
 typedef struct CollateExpr
@@ -756,7 +774,7 @@ typedef struct CaseExpr
 {
 	Expr		xpr;
 	Oid			casetype;		/* type of expression result */
-	Oid			casecollation;	/* collation of expression result */
+	Oid			casecollid;		/* OID of collation, or InvalidOid if none */
 	Expr	   *arg;			/* implicit equality comparison argument */
 	List	   *args;			/* the arguments (list of WHEN clauses) */
 	Expr	   *defresult;		/* the default result (ELSE clause) */
@@ -802,6 +820,7 @@ typedef struct ArrayExpr
 {
 	Expr		xpr;
 	Oid			array_typeid;	/* type of expression result */
+	Oid			array_collid;	/* OID of collation, or InvalidOid if none */
 	Oid			element_typeid; /* common type of array elements */
 	List	   *elements;		/* the array elements or sub-arrays */
 	bool		multidims;		/* true if elements are sub-arrays */
@@ -838,6 +857,9 @@ typedef struct RowExpr
 	 * associated with specific RECORD types at runtime, it will differ for
 	 * different backends, and so cannot safely be stored in stored
 	 * parsetrees.	We must assume typmod -1 for a RowExpr node.
+	 *
+	 * We don't need to store a collation either.  The result type is
+	 * necessarily composite, and composite types never have a collation.
 	 */
 	CoercionForm row_format;	/* how to display this node */
 	List	   *colnames;		/* list of String, or NIL */
@@ -875,7 +897,7 @@ typedef struct RowCompareExpr
 	RowCompareType rctype;		/* LT LE GE or GT, never EQ or NE */
 	List	   *opnos;			/* OID list of pairwise comparison ops */
 	List	   *opfamilies;		/* OID list of containing operator families */
-	List	   *collids;		/* OID list of collations for the comparisons */
+	List	   *inputcollids;	/* OID list of collations for comparisons */
 	List	   *largs;			/* the left-hand input arguments */
 	List	   *rargs;			/* the right-hand input arguments */
 } RowCompareExpr;
@@ -887,7 +909,7 @@ typedef struct CoalesceExpr
 {
 	Expr		xpr;
 	Oid			coalescetype;	/* type of expression result */
-	Oid			coalescecollation;	/* collation of expression result */
+	Oid			coalescecollid;	/* OID of collation, or InvalidOid if none */
 	List	   *args;			/* the arguments */
 	int			location;		/* token location, or -1 if unknown */
 } CoalesceExpr;
@@ -905,9 +927,10 @@ typedef struct MinMaxExpr
 {
 	Expr		xpr;
 	Oid			minmaxtype;		/* common type of arguments and result */
+	Oid			minmaxcollid;	/* OID of collation of result */
+	Oid			inputcollid;	/* OID of collation that function should use */
 	MinMaxOp	op;				/* function to execute */
 	List	   *args;			/* the arguments */
-	Oid			collid;			/* collation to use */
 	int			location;		/* token location, or -1 if unknown */
 } MinMaxExpr;
 
@@ -917,6 +940,10 @@ typedef struct MinMaxExpr
  * 'name' carries the "NAME foo" argument (already XML-escaped).
  * 'named_args' and 'arg_names' represent an xml_attribute list.
  * 'args' carries all other arguments.
+ *
+ * Note: result type/typmod/collation are not stored, but can be deduced
+ * from the XmlExprOp.  The type/typmod fields are just used for display
+ * purposes, and are NOT the true result type of the node.
  */
 typedef enum XmlExprOp
 {
@@ -945,19 +972,11 @@ typedef struct XmlExpr
 	List	   *arg_names;		/* parallel list of Value strings */
 	List	   *args;			/* list of expressions */
 	XmlOptionType xmloption;	/* DOCUMENT or CONTENT */
-	Oid			type;			/* target type for XMLSERIALIZE */
+	Oid			type;			/* target type/typmod for XMLSERIALIZE */
 	int32		typmod;
 	int			location;		/* token location, or -1 if unknown */
 } XmlExpr;
 
-/*
- * NullIfExpr - a NULLIF expression
- *
- * Like DistinctExpr, this is represented the same as an OpExpr referencing
- * the "=" operator for x and y.
- */
-typedef OpExpr NullIfExpr;
-
 /* ----------------
  * NullTest
  *
@@ -1018,6 +1037,7 @@ typedef struct CoerceToDomain
 	Expr	   *arg;			/* input expression */
 	Oid			resulttype;		/* domain type ID (result type) */
 	int32		resulttypmod;	/* output typmod (currently always -1) */
+	Oid			resultcollid;	/* OID of collation, or InvalidOid if none */
 	CoercionForm coercionformat;	/* how to display this node */
 	int			location;		/* token location, or -1 if unknown */
 } CoerceToDomain;
@@ -1036,6 +1056,7 @@ typedef struct CoerceToDomainValue
 	Expr		xpr;
 	Oid			typeId;			/* type for substituted value */
 	int32		typeMod;		/* typemod for substituted value */
+	Oid			collation;		/* collation for the substituted value */
 	int			location;		/* token location, or -1 if unknown */
 } CoerceToDomainValue;
 
@@ -1051,7 +1072,7 @@ typedef struct SetToDefault
 	Expr		xpr;
 	Oid			typeId;			/* type for substituted value */
 	int32		typeMod;		/* typemod for substituted value */
-	Oid			collid;			/* collation for the substituted value */
+	Oid			collation;		/* collation for the substituted value */
 	int			location;		/* token location, or -1 if unknown */
 } SetToDefault;
 
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 8bcc4006a1a..7fee3f1464e 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -488,10 +488,13 @@ typedef struct IndexOptInfo
  * require merging two existing EquivalenceClasses.  At the end of the qual
  * distribution process, we have sets of values that are known all transitively
  * equal to each other, where "equal" is according to the rules of the btree
- * operator family(s) shown in ec_opfamilies.  (We restrict an EC to contain
- * only equalities whose operators belong to the same set of opfamilies.  This
- * could probably be relaxed, but for now it's not worth the trouble, since
- * nearly all equality operators belong to only one btree opclass anyway.)
+ * operator family(s) shown in ec_opfamilies, as well as the collation shown
+ * by ec_collation.  (We restrict an EC to contain only equalities whose
+ * operators belong to the same set of opfamilies.  This could probably be
+ * relaxed, but for now it's not worth the trouble, since nearly all equality
+ * operators belong to only one btree opclass anyway.  Similarly, we suppose
+ * that all or none of the input datatypes are collatable, so that a single
+ * collation value is sufficient.)
  *
  * We also use EquivalenceClasses as the base structure for PathKeys, letting
  * us represent knowledge about different sort orderings being equivalent.
@@ -520,6 +523,7 @@ typedef struct EquivalenceClass
 	NodeTag		type;
 
 	List	   *ec_opfamilies;	/* btree operator family OIDs */
+	Oid			ec_collation;	/* collation, if datatypes are collatable */
 	List	   *ec_members;		/* list of EquivalenceMembers */
 	List	   *ec_sources;		/* list of generating RestrictInfos */
 	List	   *ec_derives;		/* list of derived RestrictInfos */
@@ -574,9 +578,10 @@ typedef struct EquivalenceMember
  * represents the primary sort key, the second the first secondary sort key,
  * etc.  The value being sorted is represented by linking to an
  * EquivalenceClass containing that value and including pk_opfamily among its
- * ec_opfamilies.  This is a convenient method because it makes it trivial
- * to detect equivalent and closely-related orderings.	(See optimizer/README
- * for more information.)
+ * ec_opfamilies.  The EquivalenceClass tells which collation to use, too.
+ * This is a convenient method because it makes it trivial to detect
+ * equivalent and closely-related orderings. (See optimizer/README for more
+ * information.)
  *
  * Note: pk_strategy is either BTLessStrategyNumber (for ASC) or
  * BTGreaterStrategyNumber (for DESC).	We assume that all ordering-capable
@@ -589,7 +594,6 @@ typedef struct PathKey
 
 	EquivalenceClass *pk_eclass;	/* the value that is ordered */
 	Oid			pk_opfamily;	/* btree opfamily defining the ordering */
-	Oid			pk_collation;	/* collation */
 	int			pk_strategy;	/* sort direction (ASC or DESC) */
 	bool		pk_nulls_first; /* do NULLs come before normal values? */
 } PathKey;
@@ -1117,7 +1121,7 @@ typedef struct MergeScanSelCache
 {
 	/* Ordering details (cache lookup key) */
 	Oid			opfamily;		/* btree opfamily defining the ordering */
-	Oid			collation;
+	Oid			collation;		/* collation for the ordering */
 	int			strategy;		/* sort direction (ASC or DESC) */
 	bool		nulls_first;	/* do NULLs come before normal values? */
 	/* Results */
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index 945957244c3..7ae236d167c 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -36,7 +36,8 @@ typedef struct
 
 
 extern Expr *make_opclause(Oid opno, Oid opresulttype, bool opretset,
-			  Expr *leftop, Expr *rightop);
+			  Expr *leftop, Expr *rightop,
+			  Oid opcollid, Oid inputcollid);
 extern Node *get_leftop(Expr *clause);
 extern Node *get_rightop(Expr *clause);
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index ef769bf04df..06aed5f3178 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -111,11 +111,14 @@ extern bool have_join_order_restriction(PlannerInfo *root,
  */
 extern bool process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 					bool below_outer_join);
+extern Expr *canonicalize_ec_expression(Expr *expr,
+										Oid req_type, Oid req_collation);
 extern void reconsider_outer_join_clauses(PlannerInfo *root);
 extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 						 Expr *expr,
-						 Oid expr_datatype,
 						 List *opfamilies,
+						 Oid opcintype,
+						 Oid collation,
 						 Index sortref,
 						 bool create_it);
 extern void generate_base_implied_equalities(PlannerInfo *root);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 7e03bc924ed..d48bf39e410 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -98,12 +98,14 @@ extern void distribute_restrictinfo_to_rels(PlannerInfo *root,
 								RestrictInfo *restrictinfo);
 extern void process_implied_equality(PlannerInfo *root,
 						 Oid opno,
+						 Oid collation,
 						 Expr *item1,
 						 Expr *item2,
 						 Relids qualscope,
 						 bool below_outer_join,
 						 bool both_const);
 extern RestrictInfo *build_implied_join_equality(Oid opno,
+							Oid collation,
 							Expr *item1,
 							Expr *item2,
 							Relids qualscope);
diff --git a/src/include/parser/parse_agg.h b/src/include/parser/parse_agg.h
index 76d806dd40e..543d2e7857d 100644
--- a/src/include/parser/parse_agg.h
+++ b/src/include/parser/parse_agg.h
@@ -28,9 +28,9 @@ extern void build_aggregate_fnexprs(Oid *agg_input_types,
 						int agg_num_inputs,
 						Oid agg_state_type,
 						Oid agg_result_type,
+						Oid agg_input_collation,
 						Oid transfn_oid,
 						Oid finalfn_oid,
-						Oid collation,
 						Expr **transfnexpr,
 						Expr **finalfnexpr);
 
diff --git a/src/include/parser/parse_coerce.h b/src/include/parser/parse_coerce.h
index 9f79ad89d41..ceaff2f9a92 100644
--- a/src/include/parser/parse_coerce.h
+++ b/src/include/parser/parse_coerce.h
@@ -87,6 +87,4 @@ extern CoercionPathType find_coercion_pathway(Oid targetTypeId,
 extern CoercionPathType find_typmod_coercion_function(Oid typeId,
 							  Oid *funcid);
 
-extern Oid select_common_collation(ParseState *pstate, List *exprs, bool none_ok);
-
 #endif   /* PARSE_COERCE_H */
diff --git a/src/include/parser/parse_collate.h b/src/include/parser/parse_collate.h
new file mode 100644
index 00000000000..20acb43504f
--- /dev/null
+++ b/src/include/parser/parse_collate.h
@@ -0,0 +1,27 @@
+/*-------------------------------------------------------------------------
+ *
+ * parse_collate.h
+ *	Routines for assigning collation information.
+ *
+ *
+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/parser/parse_collate.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef PARSE_COLLATE_H
+#define PARSE_COLLATE_H
+
+#include "parser/parse_node.h"
+
+extern void assign_query_collations(ParseState *pstate, Query *query);
+
+extern void assign_list_collations(ParseState *pstate, List *exprs);
+
+extern void assign_expr_collations(ParseState *pstate, Node *expr);
+
+extern Oid select_common_collation(ParseState *pstate, List *exprs, bool none_ok);
+
+#endif   /* PARSE_COLLATE_H */
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index a68f7cf5087..0ca79145585 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -146,7 +146,6 @@ extern ArrayRef *transformArraySubscripts(ParseState *pstate,
 						 Oid arrayType,
 						 Oid elementType,
 						 int32 arrayTypMod,
-						 Oid arrayColl,
 						 List *indirection,
 						 Node *assignFrom);
 extern Const *make_const(ParseState *pstate, Value *value, int location);