3 files changed, 236 insertions, 21 deletions

diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index 43a2a6b596a..1b7bec5a317 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -3449,6 +3449,117 @@ array_cmp(FunctionCallInfo fcinfo)
 
 
 /*-----------------------------------------------------------------------------
+ * array hashing
+ *		Hash the elements and combine the results.
+ *----------------------------------------------------------------------------
+ */
+
+Datum
+hash_array(PG_FUNCTION_ARGS)
+{
+	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
+	int			ndims = ARR_NDIM(array);
+	int		   *dims = ARR_DIMS(array);
+	Oid			element_type = ARR_ELEMTYPE(array);
+	uint32		result = 0;
+	int			nitems;
+	TypeCacheEntry *typentry;
+	int			typlen;
+	bool		typbyval;
+	char		typalign;
+	char	   *ptr;
+	bits8	   *bitmap;
+	int			bitmask;
+	int			i;
+	FunctionCallInfoData locfcinfo;
+
+	/*
+	 * We arrange to look up the hash function only once per series of calls,
+	 * assuming the element type doesn't change underneath us.  The typcache
+	 * is used so that we have no memory leakage when being used as an index
+	 * support function.
+	 */
+	typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+	if (typentry == NULL ||
+		typentry->type_id != element_type)
+	{
+		typentry = lookup_type_cache(element_type,
+									 TYPECACHE_HASH_PROC_FINFO);
+		if (!OidIsValid(typentry->hash_proc_finfo.fn_oid))
+			ereport(ERROR,
+					(errcode(ERRCODE_UNDEFINED_FUNCTION),
+					 errmsg("could not identify a hash function for type %s",
+							format_type_be(element_type))));
+		fcinfo->flinfo->fn_extra = (void *) typentry;
+	}
+	typlen = typentry->typlen;
+	typbyval = typentry->typbyval;
+	typalign = typentry->typalign;
+
+	/*
+	 * apply the hash function to each array element.
+	 */
+	InitFunctionCallInfoData(locfcinfo, &typentry->hash_proc_finfo, 1,
+							 NULL, NULL);
+
+	/* Loop over source data */
+	nitems = ArrayGetNItems(ndims, dims);
+	ptr = ARR_DATA_PTR(array);
+	bitmap = ARR_NULLBITMAP(array);
+	bitmask = 1;
+
+	for (i = 0; i < nitems; i++)
+	{
+		uint32		elthash;
+
+		/* Get element, checking for NULL */
+		if (bitmap && (*bitmap & bitmask) == 0)
+		{
+			/* Treat nulls as having hashvalue 0 */
+			elthash = 0;
+		}
+		else
+		{
+			Datum		elt;
+
+			elt = fetch_att(ptr, typbyval, typlen);
+			ptr = att_addlength_pointer(ptr, typlen, ptr);
+			ptr = (char *) att_align_nominal(ptr, typalign);
+
+			/* Apply the hash function */
+			locfcinfo.arg[0] = elt;
+			locfcinfo.argnull[0] = false;
+			locfcinfo.isnull = false;
+			elthash = DatumGetUInt32(FunctionCallInvoke(&locfcinfo));
+		}
+
+		/* advance bitmap pointer if any */
+		if (bitmap)
+		{
+			bitmask <<= 1;
+			if (bitmask == 0x100)
+			{
+				bitmap++;
+				bitmask = 1;
+			}
+		}
+
+		/*
+		 * Combine hash values of successive elements by rotating the previous
+		 * value left 1 bit, then XOR'ing in the new element's hash value.
+		 */
+		result = (result << 1) | (result >> 31);
+		result ^= elthash;
+	}
+
+	/* Avoid leaking memory when handed toasted input. */
+	PG_FREE_IF_COPY(array, 0);
+
+	PG_RETURN_UINT32(result);
+}
+
+
+/*-----------------------------------------------------------------------------
  * array overlap/containment comparisons
  *		These use the same methods of comparing array elements as array_eq.
  *		We consider only the elements of the arrays, ignoring dimensionality.
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 740e8c4ab42..df765e9d5e3 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -34,6 +34,7 @@
 #include "utils/datum.h"
 #include "utils/lsyscache.h"
 #include "utils/syscache.h"
+#include "utils/typcache.h"
 
 /* Hook for plugins to get control in get_attavgwidth() */
 get_attavgwidth_hook_type get_attavgwidth_hook = NULL;
@@ -1054,20 +1055,47 @@ op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
  * will fail to find any mergejoin plans unless there are suitable btree
  * opfamily entries for this operator and associated sortops.  The pg_operator
  * flag is just a hint to tell the planner whether to bother looking.)
+ *
+ * In some cases (currently only array_eq), mergejoinability depends on the
+ * specific input data type the operator is invoked for, so that must be
+ * passed as well.  We currently assume that only one input's type is needed
+ * to check this --- by convention, pass the left input's data type.
  */
 bool
-op_mergejoinable(Oid opno)
+op_mergejoinable(Oid opno, Oid inputtype)
 {
 	HeapTuple	tp;
 	bool		result = false;
 
-	tp = SearchSysCache1(OPEROID, ObjectIdGetDatum(opno));
-	if (HeapTupleIsValid(tp))
+	if (opno == ARRAY_EQ_OP)
 	{
-		Form_pg_operator optup = (Form_pg_operator) GETSTRUCT(tp);
+		/*
+		 * For array_eq, can sort if element type has a default btree opclass.
+		 * We could use GetDefaultOpClass, but that's fairly expensive and not
+		 * cached, so let's use the typcache instead.
+		 */
+		Oid			elem_type = get_base_element_type(inputtype);
 
-		result = optup->oprcanmerge;
-		ReleaseSysCache(tp);
+		if (OidIsValid(elem_type))
+		{
+			TypeCacheEntry *typentry;
+
+			typentry = lookup_type_cache(elem_type, TYPECACHE_BTREE_OPFAMILY);
+			if (OidIsValid(typentry->btree_opf))
+				result = true;
+		}
+	}
+	else
+	{
+		/* For all other operators, rely on pg_operator.oprcanmerge */
+		tp = SearchSysCache1(OPEROID, ObjectIdGetDatum(opno));
+		if (HeapTupleIsValid(tp))
+		{
+			Form_pg_operator optup = (Form_pg_operator) GETSTRUCT(tp);
+
+			result = optup->oprcanmerge;
+			ReleaseSysCache(tp);
+		}
 	}
 	return result;
 }
@@ -1077,20 +1105,43 @@ op_mergejoinable(Oid opno)
  *
  * Returns true if the operator is hashjoinable.  (There must be a suitable
  * hash opfamily entry for this operator if it is so marked.)
+ *
+ * In some cases (currently only array_eq), hashjoinability depends on the
+ * specific input data type the operator is invoked for, so that must be
+ * passed as well.  We currently assume that only one input's type is needed
+ * to check this --- by convention, pass the left input's data type.
  */
 bool
-op_hashjoinable(Oid opno)
+op_hashjoinable(Oid opno, Oid inputtype)
 {
 	HeapTuple	tp;
 	bool		result = false;
 
-	tp = SearchSysCache1(OPEROID, ObjectIdGetDatum(opno));
-	if (HeapTupleIsValid(tp))
+	if (opno == ARRAY_EQ_OP)
 	{
-		Form_pg_operator optup = (Form_pg_operator) GETSTRUCT(tp);
+		/* For array_eq, can hash if element type has a default hash opclass */
+		Oid			elem_type = get_base_element_type(inputtype);
 
-		result = optup->oprcanhash;
-		ReleaseSysCache(tp);
+		if (OidIsValid(elem_type))
+		{
+			TypeCacheEntry *typentry;
+
+			typentry = lookup_type_cache(elem_type, TYPECACHE_HASH_OPFAMILY);
+			if (OidIsValid(typentry->hash_opf))
+				result = true;
+		}
+	}
+	else
+	{
+		/* For all other operators, rely on pg_operator.oprcanhash */
+		tp = SearchSysCache1(OPEROID, ObjectIdGetDatum(opno));
+		if (HeapTupleIsValid(tp))
+		{
+			Form_pg_operator optup = (Form_pg_operator) GETSTRUCT(tp);
+
+			result = optup->oprcanhash;
+			ReleaseSysCache(tp);
+		}
 	}
 	return result;
 }
diff --git a/src/backend/utils/cache/typcache.c b/src/backend/utils/cache/typcache.c
index bc4abc451a6..c2537e1de7a 100644
--- a/src/backend/utils/cache/typcache.c
+++ b/src/backend/utils/cache/typcache.c
@@ -10,10 +10,10 @@
  * be used for grouping and sorting the type (GROUP BY, ORDER BY ASC/DESC).
  *
  * Several seemingly-odd choices have been made to support use of the type
- * cache by the generic array comparison routines array_eq() and array_cmp().
- * Because those routines are used as index support operations, they cannot
- * leak memory.  To allow them to execute efficiently, all information that
- * either of them would like to re-use across calls is made available in the
+ * cache by the generic array handling routines array_eq(), array_cmp(),
+ * and hash_array().  Because those routines are used as index support
+ * operations, they cannot leak memory.  To allow them to execute efficiently,
+ * all information that they would like to re-use across calls is kept in the
  * type cache.
  *
  * Once created, a type cache entry lives as long as the backend does, so
@@ -193,7 +193,9 @@ lookup_type_cache(Oid type_id, int flags)
 		ReleaseSysCache(tp);
 	}
 
-	/* If we haven't already found the opclass, try to do so */
+	/*
+	 * If we haven't already found the opclasses, try to do so
+	 */
 	if ((flags & (TYPECACHE_EQ_OPR | TYPECACHE_LT_OPR | TYPECACHE_GT_OPR |
 				  TYPECACHE_CMP_PROC |
 				  TYPECACHE_EQ_OPR_FINFO | TYPECACHE_CMP_PROC_FINFO |
@@ -208,7 +210,7 @@ lookup_type_cache(Oid type_id, int flags)
 			typentry->btree_opf = get_opclass_family(opclass);
 			typentry->btree_opintype = get_opclass_input_type(opclass);
 		}
-		/* Only care about hash opclass if no btree opclass... */
+		/* If no btree opclass, we force lookup of the hash opclass */
 		if (typentry->btree_opf == InvalidOid)
 		{
 			if (typentry->hash_opf == InvalidOid)
@@ -224,12 +226,30 @@ lookup_type_cache(Oid type_id, int flags)
 		else
 		{
 			/*
-			 * If we find a btree opclass where previously we only found a
-			 * hash opclass, forget the hash equality operator so we can use
-			 * the btree operator instead.
+			 * In case we find a btree opclass where previously we only found
+			 * a hash opclass, reset eq_opr and derived information so that
+			 * we can fetch the btree equality operator instead of the hash
+			 * equality operator.  (They're probably the same operator, but
+			 * we don't assume that here.)
 			 */
 			typentry->eq_opr = InvalidOid;
 			typentry->eq_opr_finfo.fn_oid = InvalidOid;
+			typentry->hash_proc = InvalidOid;
+			typentry->hash_proc_finfo.fn_oid = InvalidOid;
+		}
+	}
+
+	if ((flags & (TYPECACHE_HASH_PROC | TYPECACHE_HASH_PROC_FINFO |
+				  TYPECACHE_HASH_OPFAMILY)) &&
+		typentry->hash_opf == InvalidOid)
+	{
+		Oid			opclass;
+
+		opclass = GetDefaultOpClass(type_id, HASH_AM_OID);
+		if (OidIsValid(opclass))
+		{
+			typentry->hash_opf = get_opclass_family(opclass);
+			typentry->hash_opintype = get_opclass_input_type(opclass);
 		}
 	}
 
@@ -248,6 +268,14 @@ lookup_type_cache(Oid type_id, int flags)
 												   typentry->hash_opintype,
 												   typentry->hash_opintype,
 												   HTEqualStrategyNumber);
+
+		/*
+		 * Reset info about hash function whenever we pick up new info about
+		 * equality operator.  This is so we can ensure that the hash function
+		 * matches the operator.
+		 */
+		typentry->hash_proc = InvalidOid;
+		typentry->hash_proc_finfo.fn_oid = InvalidOid;
 	}
 	if ((flags & TYPECACHE_LT_OPR) && typentry->lt_opr == InvalidOid)
 	{
@@ -274,6 +302,24 @@ lookup_type_cache(Oid type_id, int flags)
 												   typentry->btree_opintype,
 												   BTORDER_PROC);
 	}
+	if ((flags & (TYPECACHE_HASH_PROC | TYPECACHE_HASH_PROC_FINFO)) &&
+		typentry->hash_proc == InvalidOid)
+	{
+		/*
+		 * We insist that the eq_opr, if one has been determined, match the
+		 * hash opclass; else report there is no hash function.
+		 */
+		if (typentry->hash_opf != InvalidOid &&
+			(!OidIsValid(typentry->eq_opr) ||
+			 typentry->eq_opr == get_opfamily_member(typentry->hash_opf,
+													 typentry->hash_opintype,
+													 typentry->hash_opintype,
+													 HTEqualStrategyNumber)))
+			typentry->hash_proc = get_opfamily_proc(typentry->hash_opf,
+													typentry->hash_opintype,
+													typentry->hash_opintype,
+													HASHPROC);
+	}
 
 	/*
 	 * Set up fmgr lookup info as requested
@@ -300,6 +346,13 @@ lookup_type_cache(Oid type_id, int flags)
 		fmgr_info_cxt(typentry->cmp_proc, &typentry->cmp_proc_finfo,
 					  CacheMemoryContext);
 	}
+	if ((flags & TYPECACHE_HASH_PROC_FINFO) &&
+		typentry->hash_proc_finfo.fn_oid == InvalidOid &&
+		typentry->hash_proc != InvalidOid)
+	{
+		fmgr_info_cxt(typentry->hash_proc, &typentry->hash_proc_finfo,
+					  CacheMemoryContext);
+	}
 
 	/*
 	 * If it's a composite type (row type), get tupdesc if requested