Provide hashing support for arrays.

The core of this patch is hash_array() and associated typcache
infrastructure, which works just about exactly like the existing support
for array comparison.

In addition I did some work to ensure that the planner won't think that an
array type is hashable unless its element type is hashable, and similarly
for sorting.  This includes adding a datatype parameter to op_hashjoinable
and op_mergejoinable, and adding an explicit "hashable" flag to
SortGroupClause.  The lack of a cross-check on the element type was a
pre-existing bug in mergejoin support --- but it didn't matter so much
before, because if you couldn't sort the element type there wasn't any good
alternative to failing anyhow.  Now that we have the alternative of hashing
the array type, there are cases where we can avoid a failure by being picky
at the planner stage, so it's time to be picky.

The issue of exactly how to combine the per-element hash values to produce
an array hash is still open for discussion, but the rest of this is pretty
solid, so I'll commit it as-is.

3 files changed, 49 insertions, 30 deletions

diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c
index bb2bf04e177..3d84f61e0aa 100644
--- a/src/backend/parser/analyze.c
+++ b/src/backend/parser/analyze.c
@@ -1659,6 +1659,7 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
 				SortGroupClause *grpcl = makeNode(SortGroupClause);
 				Oid			sortop;
 				Oid			eqop;
+				bool		hashable;
 				ParseCallbackState pcbstate;
 
 				setup_parser_errposition_callback(&pcbstate, pstate,
@@ -1667,7 +1668,8 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
 				/* determine the eqop and optional sortop */
 				get_sort_group_operators(rescoltype,
 										 false, true, false,
-										 &sortop, &eqop, NULL);
+										 &sortop, &eqop, NULL,
+										 &hashable);
 
 				cancel_parser_errposition_callback(&pcbstate);
 
@@ -1676,6 +1678,7 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
 				grpcl->eqop = eqop;
 				grpcl->sortop = sortop;
 				grpcl->nulls_first = false;		/* OK with or without sortop */
+				grpcl->hashable = hashable;
 
 				op->groupClauses = lappend(op->groupClauses, grpcl);
 			}
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 5e13fa49345..898c55e98f0 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -1937,6 +1937,7 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 	Oid			restype = exprType((Node *) tle->expr);
 	Oid			sortop;
 	Oid			eqop;
+	bool		hashable;
 	bool		reverse;
 	int			location;
 	ParseCallbackState pcbstate;
@@ -1972,13 +1973,15 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 		case SORTBY_ASC:
 			get_sort_group_operators(restype,
 									 true, true, false,
-									 &sortop, &eqop, NULL);
+									 &sortop, &eqop, NULL,
+									 &hashable);
 			reverse = false;
 			break;
 		case SORTBY_DESC:
 			get_sort_group_operators(restype,
 									 false, true, true,
-									 NULL, &eqop, &sortop);
+									 NULL, &eqop, &sortop,
+									 &hashable);
 			reverse = true;
 			break;
 		case SORTBY_USING:
@@ -2000,11 +2003,17 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 					   errmsg("operator %s is not a valid ordering operator",
 							  strVal(llast(sortby->useOp))),
 						 errhint("Ordering operators must be \"<\" or \">\" members of btree operator families.")));
+
+			/*
+			 * Also see if the equality operator is hashable.
+			 */
+			hashable = op_hashjoinable(eqop, restype);
 			break;
 		default:
 			elog(ERROR, "unrecognized sortby_dir: %d", sortby->sortby_dir);
 			sortop = InvalidOid;	/* keep compiler quiet */
 			eqop = InvalidOid;
+			hashable = false;
 			reverse = false;
 			break;
 	}
@@ -2020,6 +2029,7 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 
 		sortcl->eqop = eqop;
 		sortcl->sortop = sortop;
+		sortcl->hashable = hashable;
 
 		switch (sortby->sortby_nulls)
 		{
@@ -2074,8 +2084,6 @@ addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
 					 bool resolveUnknown)
 {
 	Oid			restype = exprType((Node *) tle->expr);
-	Oid			sortop;
-	Oid			eqop;
 
 	/* if tlist item is an UNKNOWN literal, change it to TEXT */
 	if (restype == UNKNOWNOID && resolveUnknown)
@@ -2092,6 +2100,9 @@ addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
 	if (!targetIsInSortList(tle, InvalidOid, grouplist))
 	{
 		SortGroupClause *grpcl = makeNode(SortGroupClause);
+		Oid			sortop;
+		Oid			eqop;
+		bool		hashable;
 		ParseCallbackState pcbstate;
 
 		setup_parser_errposition_callback(&pcbstate, pstate, location);
@@ -2099,7 +2110,8 @@ addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
 		/* determine the eqop and optional sortop */
 		get_sort_group_operators(restype,
 								 false, true, false,
-								 &sortop, &eqop, NULL);
+								 &sortop, &eqop, NULL,
+								 &hashable);
 
 		cancel_parser_errposition_callback(&pcbstate);
 
@@ -2107,6 +2119,7 @@ addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
 		grpcl->eqop = eqop;
 		grpcl->sortop = sortop;
 		grpcl->nulls_first = false;		/* OK with or without sortop */
+		grpcl->hashable = hashable;
 
 		grouplist = lappend(grouplist, grpcl);
 	}
diff --git a/src/backend/parser/parse_oper.c b/src/backend/parser/parse_oper.c
index 83cc41606cf..8305ca97988 100644
--- a/src/backend/parser/parse_oper.c
+++ b/src/backend/parser/parse_oper.c
@@ -171,6 +171,9 @@ LookupOperNameTypeNames(ParseState *pstate, List *opername,
  * If an operator is missing and the corresponding needXX flag is true,
  * throw a standard error message, else return InvalidOid.
  *
+ * In addition to the operator OIDs themselves, this function can identify
+ * whether the "=" operator is hashable.
+ *
  * Callers can pass NULL pointers for any results they don't care to get.
  *
  * Note: the results are guaranteed to be exact or binary-compatible matches,
@@ -180,30 +183,40 @@ LookupOperNameTypeNames(ParseState *pstate, List *opername,
 void
 get_sort_group_operators(Oid argtype,
 						 bool needLT, bool needEQ, bool needGT,
-						 Oid *ltOpr, Oid *eqOpr, Oid *gtOpr)
+						 Oid *ltOpr, Oid *eqOpr, Oid *gtOpr,
+						 bool *isHashable)
 {
 	TypeCacheEntry *typentry;
+	int			cache_flags;
 	Oid			lt_opr;
 	Oid			eq_opr;
 	Oid			gt_opr;
+	bool		hashable;
 
 	/*
 	 * Look up the operators using the type cache.
 	 *
 	 * Note: the search algorithm used by typcache.c ensures that the results
-	 * are consistent, ie all from the same opclass.
+	 * are consistent, ie all from matching opclasses.
 	 */
-	typentry = lookup_type_cache(argtype,
-					 TYPECACHE_LT_OPR | TYPECACHE_EQ_OPR | TYPECACHE_GT_OPR);
+	if (isHashable != NULL)
+		cache_flags = TYPECACHE_LT_OPR | TYPECACHE_EQ_OPR | TYPECACHE_GT_OPR |
+			TYPECACHE_HASH_PROC;
+	else
+		cache_flags = TYPECACHE_LT_OPR | TYPECACHE_EQ_OPR | TYPECACHE_GT_OPR;
+
+	typentry = lookup_type_cache(argtype, cache_flags);
 	lt_opr = typentry->lt_opr;
 	eq_opr = typentry->eq_opr;
 	gt_opr = typentry->gt_opr;
+	hashable = OidIsValid(typentry->hash_proc);
 
 	/*
 	 * If the datatype is an array, then we can use array_lt and friends ...
-	 * but only if there are suitable operators for the element type.  (This
-	 * check is not in the raw typcache.c code ... should it be?)  Testing all
-	 * three operator IDs here should be redundant, but let's do it anyway.
+	 * but only if there are suitable operators for the element type.
+	 * Likewise, array types are only hashable if the element type is.
+	 * Testing all three operator IDs here should be redundant, but let's do
+	 * it anyway.
 	 */
 	if (lt_opr == ARRAY_LT_OP ||
 		eq_opr == ARRAY_EQ_OP ||
@@ -213,10 +226,7 @@ get_sort_group_operators(Oid argtype,
 
 		if (OidIsValid(elem_type))
 		{
-			typentry = lookup_type_cache(elem_type,
-					 TYPECACHE_LT_OPR | TYPECACHE_EQ_OPR | TYPECACHE_GT_OPR);
-#ifdef NOT_USED
-			/* We should do this ... */
+			typentry = lookup_type_cache(elem_type, cache_flags);
 			if (!OidIsValid(typentry->eq_opr))
 			{
 				/* element type is neither sortable nor hashable */
@@ -228,22 +238,13 @@ get_sort_group_operators(Oid argtype,
 				/* element type is hashable but not sortable */
 				lt_opr = gt_opr = InvalidOid;
 			}
-#else
-
-			/*
-			 * ... but for the moment we have to do this.  This is because
-			 * anyarray has sorting but not hashing support.  So, if the
-			 * element type is only hashable, there is nothing we can do with
-			 * the array type.
-			 */
-			if (!OidIsValid(typentry->lt_opr) ||
-				!OidIsValid(typentry->eq_opr) ||
-				!OidIsValid(typentry->gt_opr))
-				lt_opr = eq_opr = gt_opr = InvalidOid;	/* not sortable */
-#endif
+			hashable = OidIsValid(typentry->hash_proc);
 		}
 		else
+		{
 			lt_opr = eq_opr = gt_opr = InvalidOid;		/* bogus array type? */
+			hashable = false;
+		}
 	}
 
 	/* Report errors if needed */
@@ -267,6 +268,8 @@ get_sort_group_operators(Oid argtype,
 		*eqOpr = eq_opr;
 	if (gtOpr)
 		*gtOpr = gt_opr;
+	if (isHashable)
+		*isHashable = hashable;
 }