Collations with nondeterministic comparison

This adds a flag "deterministic" to collations.  If that is false,
such a collation disables various optimizations that assume that
strings are equal only if they are byte-wise equal.  That then allows
use cases such as case-insensitive or accent-insensitive comparisons
or handling of strings with different Unicode normal forms.

This functionality is only supported with the ICU provider.  At least
glibc doesn't appear to have any locales that work in a
nondeterministic way, so it's not worth supporting this for the libc
provider.

The term "deterministic comparison" in this context is from Unicode
Technical Standard #10
(https://unicode.org/reports/tr10/#Deterministic_Comparison).

This patch makes changes in three areas:

- CREATE COLLATION DDL changes and system catalog changes to support
  this new flag.

- Many executor nodes and auxiliary code are extended to track
  collations.  Previously, this code would just throw away collation
  information, because the eventually-called user-defined functions
  didn't use it since they only cared about equality, which didn't
  need collation information.

- String data type functions that do equality comparisons and hashing
  are changed to take the (non-)deterministic flag into account.  For
  comparison, this just means skipping various shortcuts and tie
  breakers that use byte-wise comparison.  For hashing, we first need
  to convert the input string to a canonical "sort key" using the ICU
  analogue of strxfrm().

Reviewed-by: Daniel Verite <daniel@manitou-mail.org>
Reviewed-by: Peter Geoghegan <pg@bowt.ie>
Discussion: https://www.postgresql.org/message-id/flat/1ccc668f-4cbc-0bef-af67-450b47cdfee7@2ndquadrant.com

13 files changed, 57 insertions, 16 deletions

diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 7cbf9d3bc1c..0fb31f5c3d3 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3317,6 +3317,7 @@ ExecBuildGroupingEqual(TupleDesc ldesc, TupleDesc rdesc,
 					   int numCols,
 					   const AttrNumber *keyColIdx,
 					   const Oid *eqfunctions,
+					   const Oid *collations,
 					   PlanState *parent)
 {
 	ExprState  *state = makeNode(ExprState);
@@ -3377,6 +3378,7 @@ ExecBuildGroupingEqual(TupleDesc ldesc, TupleDesc rdesc,
 		Form_pg_attribute latt = TupleDescAttr(ldesc, attno - 1);
 		Form_pg_attribute ratt = TupleDescAttr(rdesc, attno - 1);
 		Oid			foid = eqfunctions[natt];
+		Oid			collid = collations[natt];
 		FmgrInfo   *finfo;
 		FunctionCallInfo fcinfo;
 		AclResult	aclresult;
@@ -3394,7 +3396,7 @@ ExecBuildGroupingEqual(TupleDesc ldesc, TupleDesc rdesc,
 		fmgr_info(foid, finfo);
 		fmgr_info_set_expr(NULL, finfo);
 		InitFunctionCallInfoData(*fcinfo, finfo, 2,
-								 InvalidOid, NULL, NULL);
+								 collid, NULL, NULL);
 
 		/* left arg */
 		scratch.opcode = EEOP_INNER_VAR;
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 417e971ec88..14ee8db3f98 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -60,6 +60,7 @@ execTuplesMatchPrepare(TupleDesc desc,
 					   int numCols,
 					   const AttrNumber *keyColIdx,
 					   const Oid *eqOperators,
+					   const Oid *collations,
 					   PlanState *parent)
 {
 	Oid		   *eqFunctions = (Oid *) palloc(numCols * sizeof(Oid));
@@ -75,7 +76,7 @@ execTuplesMatchPrepare(TupleDesc desc,
 
 	/* build actual expression */
 	expr = ExecBuildGroupingEqual(desc, desc, NULL, NULL,
-								  numCols, keyColIdx, eqFunctions,
+								  numCols, keyColIdx, eqFunctions, collations,
 								  parent);
 
 	return expr;
@@ -155,6 +156,7 @@ BuildTupleHashTableExt(PlanState *parent,
 					   int numCols, AttrNumber *keyColIdx,
 					   const Oid *eqfuncoids,
 					   FmgrInfo *hashfunctions,
+					   Oid *collations,
 					   long nbuckets, Size additionalsize,
 					   MemoryContext metacxt,
 					   MemoryContext tablecxt,
@@ -177,6 +179,7 @@ BuildTupleHashTableExt(PlanState *parent,
 	hashtable->numCols = numCols;
 	hashtable->keyColIdx = keyColIdx;
 	hashtable->tab_hash_funcs = hashfunctions;
+	hashtable->tab_collations = collations;
 	hashtable->tablecxt = tablecxt;
 	hashtable->tempcxt = tempcxt;
 	hashtable->entrysize = entrysize;
@@ -212,7 +215,7 @@ BuildTupleHashTableExt(PlanState *parent,
 	hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
 													&TTSOpsMinimalTuple, &TTSOpsMinimalTuple,
 													numCols,
-													keyColIdx, eqfuncoids,
+													keyColIdx, eqfuncoids, collations,
 													NULL);
 
 	/*
@@ -240,6 +243,7 @@ BuildTupleHashTable(PlanState *parent,
 					int numCols, AttrNumber *keyColIdx,
 					const Oid *eqfuncoids,
 					FmgrInfo *hashfunctions,
+					Oid *collations,
 					long nbuckets, Size additionalsize,
 					MemoryContext tablecxt,
 					MemoryContext tempcxt,
@@ -250,6 +254,7 @@ BuildTupleHashTable(PlanState *parent,
 								  numCols, keyColIdx,
 								  eqfuncoids,
 								  hashfunctions,
+								  collations,
 								  nbuckets, additionalsize,
 								  tablecxt,
 								  tablecxt,
@@ -421,8 +426,9 @@ TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple)
 		{
 			uint32		hkey;
 
-			hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i],
-												attr));
+			hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
+													hashtable->tab_collations[i],
+													attr));
 			hashkey ^= hkey;
 		}
 	}
diff --git a/src/backend/executor/execPartition.c b/src/backend/executor/execPartition.c
index 37e96a6013b..cfad8a38f0f 100644
--- a/src/backend/executor/execPartition.c
+++ b/src/backend/executor/execPartition.c
@@ -1246,6 +1246,7 @@ get_partition_for_tuple(PartitionDispatch pd, Datum *values, bool *isnull)
 				greatest_modulus = get_hash_partition_greatest_modulus(boundinfo);
 				rowHash = compute_partition_hash_value(key->partnatts,
 													   key->partsupfunc,
+													   key->partcollation,
 													   values, isnull);
 
 				part_index = boundinfo->indexes[rowHash % greatest_modulus];
diff --git a/src/backend/executor/execReplication.c b/src/backend/executor/execReplication.c
index 95dfc4987de..c539bb5a3f6 100644
--- a/src/backend/executor/execReplication.c
+++ b/src/backend/executor/execReplication.c
@@ -96,6 +96,8 @@ build_replindex_scan_key(ScanKey skey, Relation rel, Relation idxrel,
 					regop,
 					searchslot->tts_values[mainattno - 1]);
 
+		skey[attoff].sk_collation = idxrel->rd_indcollation[attoff];
+
 		/* Check for null value. */
 		if (searchslot->tts_isnull[mainattno - 1])
 		{
@@ -262,7 +264,8 @@ tuples_equal(TupleTableSlot *slot1, TupleTableSlot *slot2)
 					 errmsg("could not identify an equality operator for type %s",
 							format_type_be(att->atttypid))));
 
-		if (!DatumGetBool(FunctionCall2(&typentry->eq_opr_finfo,
+		if (!DatumGetBool(FunctionCall2Coll(&typentry->eq_opr_finfo,
+											att->attcollation,
 										slot1->tts_values[attrnum],
 										slot2->tts_values[attrnum])))
 			return false;
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index bae7989a422..47161afbd42 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -746,15 +746,14 @@ process_ordered_aggregate_single(AggState *aggstate,
 
 		/*
 		 * If DISTINCT mode, and not distinct from prior, skip it.
-		 *
-		 * Note: we assume equality functions don't care about collation.
 		 */
 		if (isDistinct &&
 			haveOldVal &&
 			((oldIsNull && *isNull) ||
 			 (!oldIsNull && !*isNull &&
 			  oldAbbrevVal == newAbbrevVal &&
-			  DatumGetBool(FunctionCall2(&pertrans->equalfnOne,
+			  DatumGetBool(FunctionCall2Coll(&pertrans->equalfnOne,
+											 pertrans->aggCollation,
 										 oldVal, *newVal)))))
 		{
 			/* equal to prior, so forget this one */
@@ -1287,6 +1286,7 @@ build_hash_table(AggState *aggstate)
 														perhash->hashGrpColIdxHash,
 														perhash->eqfuncoids,
 														perhash->hashfunctions,
+														perhash->aggnode->grpCollations,
 														perhash->aggnode->numGroups,
 														additionalsize,
 														aggstate->ss.ps.state->es_query_cxt,
@@ -2381,6 +2381,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 											   length,
 											   aggnode->grpColIdx,
 											   aggnode->grpOperators,
+											   aggnode->grpCollations,
 											   (PlanState *) aggstate);
 				}
 
@@ -2392,6 +2393,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 											   aggnode->numCols,
 											   aggnode->grpColIdx,
 											   aggnode->grpOperators,
+											   aggnode->grpCollations,
 											   (PlanState *) aggstate);
 				}
 			}
@@ -3155,6 +3157,7 @@ build_pertrans_for_aggref(AggStatePerTrans pertrans,
 									   numDistinctCols,
 									   pertrans->sortColIdx,
 									   ops,
+									   pertrans->sortCollations,
 									   &aggstate->ss.ps);
 		pfree(ops);
 	}
diff --git a/src/backend/executor/nodeGroup.c b/src/backend/executor/nodeGroup.c
index 655084d7b56..05f1d33150f 100644
--- a/src/backend/executor/nodeGroup.c
+++ b/src/backend/executor/nodeGroup.c
@@ -212,6 +212,7 @@ ExecInitGroup(Group *node, EState *estate, int eflags)
 							   node->numCols,
 							   node->grpColIdx,
 							   node->grpOperators,
+							   node->grpCollations,
 							   &grpstate->ss.ps);
 
 	return grpstate;
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 856daf6a7f3..64eec91f8b8 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -425,7 +425,7 @@ ExecEndHash(HashState *node)
  * ----------------------------------------------------------------
  */
 HashJoinTable
-ExecHashTableCreate(HashState *state, List *hashOperators, bool keepNulls)
+ExecHashTableCreate(HashState *state, List *hashOperators, List *hashCollations, bool keepNulls)
 {
 	Hash	   *node;
 	HashJoinTable hashtable;
@@ -439,6 +439,7 @@ ExecHashTableCreate(HashState *state, List *hashOperators, bool keepNulls)
 	int			nkeys;
 	int			i;
 	ListCell   *ho;
+	ListCell   *hc;
 	MemoryContext oldcxt;
 
 	/*
@@ -541,8 +542,9 @@ ExecHashTableCreate(HashState *state, List *hashOperators, bool keepNulls)
 	hashtable->inner_hashfunctions =
 		(FmgrInfo *) palloc(nkeys * sizeof(FmgrInfo));
 	hashtable->hashStrict = (bool *) palloc(nkeys * sizeof(bool));
+	hashtable->collations = (Oid *) palloc(nkeys * sizeof(Oid));
 	i = 0;
-	foreach(ho, hashOperators)
+	forboth(ho, hashOperators, hc, hashCollations)
 	{
 		Oid			hashop = lfirst_oid(ho);
 		Oid			left_hashfn;
@@ -554,6 +556,7 @@ ExecHashTableCreate(HashState *state, List *hashOperators, bool keepNulls)
 		fmgr_info(left_hashfn, &hashtable->outer_hashfunctions[i]);
 		fmgr_info(right_hashfn, &hashtable->inner_hashfunctions[i]);
 		hashtable->hashStrict[i] = op_strict(hashop);
+		hashtable->collations[i] = lfirst_oid(hc);
 		i++;
 	}
 
@@ -1847,7 +1850,7 @@ ExecHashGetHashValue(HashJoinTable hashtable,
 			/* Compute the hash function */
 			uint32		hkey;
 
-			hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i], keyval));
+			hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i], hashtable->collations[i], keyval));
 			hashkey ^= hkey;
 		}
 
@@ -2303,8 +2306,9 @@ ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node, int mcvsToUse)
 			uint32		hashvalue;
 			int			bucket;
 
-			hashvalue = DatumGetUInt32(FunctionCall1(&hashfunctions[0],
-													 sslot.values[i]));
+			hashvalue = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[0],
+														 hashtable->collations[0],
+														 sslot.values[i]));
 
 			/*
 			 * While we have not hit a hole in the hashtable and have not hit
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index 20987088640..aa43296e26c 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -278,6 +278,7 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
 				 */
 				hashtable = ExecHashTableCreate(hashNode,
 												node->hj_HashOperators,
+												node->hj_Collations,
 												HJ_FILL_INNER(node));
 				node->hj_HashTable = hashtable;
 
@@ -603,6 +604,7 @@ ExecInitHashJoin(HashJoin *node, EState *estate, int eflags)
 	List	   *rclauses;
 	List	   *rhclauses;
 	List	   *hoperators;
+	List	   *hcollations;
 	TupleDesc	outerDesc,
 				innerDesc;
 	ListCell   *l;
@@ -738,6 +740,7 @@ ExecInitHashJoin(HashJoin *node, EState *estate, int eflags)
 	rclauses = NIL;
 	rhclauses = NIL;
 	hoperators = NIL;
+	hcollations = NIL;
 	foreach(l, node->hashclauses)
 	{
 		OpExpr	   *hclause = lfirst_node(OpExpr, l);
@@ -749,10 +752,12 @@ ExecInitHashJoin(HashJoin *node, EState *estate, int eflags)
 		rhclauses = lappend(rhclauses, ExecInitExpr(lsecond(hclause->args),
 												   innerPlanState(hjstate)));
 		hoperators = lappend_oid(hoperators, hclause->opno);
+		hcollations = lappend_oid(hcollations, hclause->inputcollid);
 	}
 	hjstate->hj_OuterHashKeys = lclauses;
 	hjstate->hj_InnerHashKeys = rclauses;
 	hjstate->hj_HashOperators = hoperators;
+	hjstate->hj_Collations = hcollations;
 	/* child Hash node needs to evaluate inner hash keys, too */
 	((HashState *) innerPlanState(hjstate))->hashkeys = rhclauses;
 
diff --git a/src/backend/executor/nodeRecursiveunion.c b/src/backend/executor/nodeRecursiveunion.c
index 9b74ed3208c..9c5eed7def3 100644
--- a/src/backend/executor/nodeRecursiveunion.c
+++ b/src/backend/executor/nodeRecursiveunion.c
@@ -43,6 +43,7 @@ build_hash_table(RecursiveUnionState *rustate)
 												node->dupColIdx,
 												rustate->eqfuncoids,
 												rustate->hashfunctions,
+												node->dupCollations,
 												node->numGroups,
 												0,
 												rustate->ps.state->es_query_cxt,
diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c
index 26aeaee0838..044246aa09f 100644
--- a/src/backend/executor/nodeSetOp.c
+++ b/src/backend/executor/nodeSetOp.c
@@ -132,6 +132,7 @@ build_hash_table(SetOpState *setopstate)
 												   node->dupColIdx,
 												   setopstate->eqfuncoids,
 												   setopstate->hashfunctions,
+												   node->dupCollations,
 												   node->numGroups,
 												   0,
 												   setopstate->ps.state->es_query_cxt,
@@ -554,6 +555,7 @@ ExecInitSetOp(SetOp *node, EState *estate, int eflags)
 								   node->numCols,
 								   node->dupColIdx,
 								   node->dupOperators,
+								   node->dupCollations,
 								   &setopstate->ps);
 
 	if (node->strategy == SETOP_HASHED)
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index d7d076758c3..749b4eced34 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -514,6 +514,7 @@ buildSubPlanHash(SubPlanState *node, ExprContext *econtext)
 												 node->keyColIdx,
 												 node->tab_eq_funcoids,
 												 node->tab_hash_funcs,
+												 node->tab_collations,
 												 nbuckets,
 												 0,
 												 node->planstate->state->es_query_cxt,
@@ -541,6 +542,7 @@ buildSubPlanHash(SubPlanState *node, ExprContext *econtext)
 													 node->keyColIdx,
 													 node->tab_eq_funcoids,
 													 node->tab_hash_funcs,
+													 node->tab_collations,
 													 nbuckets,
 													 0,
 													 node->planstate->state->es_query_cxt,
@@ -642,6 +644,7 @@ execTuplesUnequal(TupleTableSlot *slot1,
 				  int numCols,
 				  AttrNumber *matchColIdx,
 				  FmgrInfo *eqfunctions,
+				  const Oid *collations,
 				  MemoryContext evalContext)
 {
 	MemoryContext oldContext;
@@ -679,8 +682,8 @@ execTuplesUnequal(TupleTableSlot *slot1,
 			continue;			/* can't prove anything here */
 
 		/* Apply the type-specific equality function */
-
-		if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
+		if (!DatumGetBool(FunctionCall2Coll(&eqfunctions[i],
+											collations[i],
 										attr1, attr2)))
 		{
 			result = true;		/* they are unequal */
@@ -722,6 +725,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot,
 		if (!execTuplesUnequal(slot, hashtable->tableslot,
 							   numCols, keyColIdx,
 							   eqfunctions,
+							   hashtable->tab_collations,
 							   hashtable->tempcxt))
 		{
 			TermTupleHashIterator(&hashiter);
@@ -817,6 +821,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
 	sstate->tab_eq_funcoids = NULL;
 	sstate->tab_hash_funcs = NULL;
 	sstate->tab_eq_funcs = NULL;
+	sstate->tab_collations = NULL;
 	sstate->lhs_hash_funcs = NULL;
 	sstate->cur_eq_funcs = NULL;
 
@@ -915,6 +920,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
 		sstate->tab_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
 		sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 		sstate->tab_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
+		sstate->tab_collations = (Oid *) palloc(ncols * sizeof(Oid));
 		sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 		sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 		i = 1;
@@ -965,6 +971,9 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
 			fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
 			fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
 
+			/* Set collation */
+			sstate->tab_collations[i - 1] = opexpr->inputcollid;
+
 			i++;
 		}
 
@@ -1001,6 +1010,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
 													 ncols,
 													 sstate->keyColIdx,
 													 sstate->tab_eq_funcoids,
+													 sstate->tab_collations,
 													 parent);
 
 	}
diff --git a/src/backend/executor/nodeUnique.c b/src/backend/executor/nodeUnique.c
index ad7039937d0..c553f150b8d 100644
--- a/src/backend/executor/nodeUnique.c
+++ b/src/backend/executor/nodeUnique.c
@@ -152,6 +152,7 @@ ExecInitUnique(Unique *node, EState *estate, int eflags)
 							   node->numCols,
 							   node->uniqColIdx,
 							   node->uniqOperators,
+							   node->uniqCollations,
 							   &uniquestate->ps);
 
 	return uniquestate;
diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 157ac042b82..b090828c01e 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -2370,6 +2370,7 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 								   node->partNumCols,
 								   node->partColIdx,
 								   node->partOperators,
+								   node->partCollations,
 								   &winstate->ss.ps);
 
 	if (node->ordNumCols > 0)
@@ -2378,6 +2379,7 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 								   node->ordNumCols,
 								   node->ordColIdx,
 								   node->ordOperators,
+								   node->ordCollations,
 								   &winstate->ss.ps);
 
 	/*