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.

12 files changed, 37 insertions, 14 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index b858d3ee009..0c1abdbe898 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201010241
+#define CATALOG_VERSION_NO	201010301
 
 #endif
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index d5cf859539d..a9e70a2d6a7 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -561,6 +561,8 @@ DATA(insert (	2235   1033 1033 1	974 405 ));
 DATA(insert (	2969   2950 2950 1 2972 405 ));
 /* numeric_ops */
 DATA(insert (	1998   1700 1700 1 1752 405 ));
+/* array_ops */
+DATA(insert (	627    2277 2277 1 1070	405 ));
 
 
 /*
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index 3b549178afd..f7a0fbe07f8 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -130,6 +130,7 @@ DATA(insert (	3522   3500 3500 1 3514 ));
 DATA(insert (	427   1042 1042 1 1080 ));
 DATA(insert (	431   18 18 1 454 ));
 DATA(insert (	435   1082 1082 1 450 ));
+DATA(insert (	627   2277 2277 1 626 ));
 DATA(insert (	1971   700 700 1 451 ));
 DATA(insert (	1971   701 701 1 452 ));
 DATA(insert (	1975   869 869 1 422 ));
diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h
index 2921f382ddf..7236ce60c27 100644
--- a/src/include/catalog/pg_opclass.h
+++ b/src/include/catalog/pg_opclass.h
@@ -92,6 +92,7 @@ typedef FormData_pg_opclass *Form_pg_opclass;
 
 DATA(insert (	403		abstime_ops			PGNSP PGUID  421  702 t 0 ));
 DATA(insert (	403		array_ops			PGNSP PGUID  397 2277 t 0 ));
+DATA(insert (	405		array_ops			PGNSP PGUID  627 2277 t 0 ));
 DATA(insert (	403		bit_ops				PGNSP PGUID  423 1560 t 0 ));
 DATA(insert (	403		bool_ops			PGNSP PGUID  424   16 t 0 ));
 DATA(insert (	403		bpchar_ops			PGNSP PGUID  426 1042 t 0 ));
diff --git a/src/include/catalog/pg_operator.h b/src/include/catalog/pg_operator.h
index 468d3295ff8..b9405f90772 100644
--- a/src/include/catalog/pg_operator.h
+++ b/src/include/catalog/pg_operator.h
@@ -439,7 +439,7 @@ DATA(insert OID = 1060 ( ">"	   PGNSP PGUID b f f 1042 1042	 16 1058 1059 bpchar
 DATA(insert OID = 1061 ( ">="	   PGNSP PGUID b f f 1042 1042	 16 1059 1058 bpcharge scalargtsel scalargtjoinsel ));
 
 /* generic array comparison operators */
-DATA(insert OID = 1070 (  "="	   PGNSP PGUID b t f 2277 2277 16 1070 1071 array_eq eqsel eqjoinsel ));
+DATA(insert OID = 1070 (  "="	   PGNSP PGUID b t t 2277 2277 16 1070 1071 array_eq eqsel eqjoinsel ));
 #define ARRAY_EQ_OP 1070
 DATA(insert OID = 1071 (  "<>"	   PGNSP PGUID b f f 2277 2277 16 1071 1070 array_ne neqsel neqjoinsel ));
 DATA(insert OID = 1072 (  "<"	   PGNSP PGUID b f f 2277 2277 16 1073 1075 array_lt scalarltsel scalarltjoinsel ));
diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h
index 82157cfe18d..252d3b9dbe7 100644
--- a/src/include/catalog/pg_opfamily.h
+++ b/src/include/catalog/pg_opfamily.h
@@ -60,6 +60,7 @@ typedef FormData_pg_opfamily *Form_pg_opfamily;
 
 DATA(insert OID =  421 (	403		abstime_ops		PGNSP PGUID ));
 DATA(insert OID =  397 (	403		array_ops		PGNSP PGUID ));
+DATA(insert OID =  627 (	405		array_ops		PGNSP PGUID ));
 DATA(insert OID =  423 (	403		bit_ops			PGNSP PGUID ));
 DATA(insert OID =  424 (	403		bool_ops		PGNSP PGUID ));
 #define BOOL_BTREE_FAM_OID 424
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 61c6b27d1dd..12c640c3d00 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -907,6 +907,9 @@ DESCR("convert float8 to int8");
 
 /* OIDS 600 - 699 */
 
+DATA(insert OID = 626 (  hash_array		   PGNSP PGUID 12 1 0 0 f f f t f i 1 0 23 "2277" _null_ _null_ _null_ _null_ hash_array _null_ _null_ _null_ ));
+DESCR("hash");
+
 DATA(insert OID = 652 (  float4			   PGNSP PGUID 12 1 0 0 f f f t f i 1 0 700 "20" _null_ _null_ _null_ _null_ i8tof _null_ _null_ _null_ ));
 DESCR("convert int8 to float4");
 DATA(insert OID = 653 (  int8			   PGNSP PGUID 12 1 0 0 f f f t f i 1 0 20 "700" _null_ _null_ _null_ _null_	ftoi8 _null_ _null_ _null_ ));
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 3cac54b9470..a320be4d899 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -757,6 +757,8 @@ typedef struct RangeTblEntry
  *		or InvalidOid if not available.
  * nulls_first means about what you'd expect.  If sortop is InvalidOid
  *		then nulls_first is meaningless and should be set to false.
+ * hashable is TRUE if eqop is hashable (note this condition also depends
+ *		on the datatype of the input expression).
  *
  * 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
@@ -773,6 +775,11 @@ typedef struct RangeTblEntry
  * and nulls_first to false.  A grouping item of this kind can only be
  * implemented by hashing, and of course it'll never match an ORDER BY item.
  *
+ * The hashable flag is provided since we generally have the requisite
+ * information readily available when the SortGroupClause is constructed,
+ * and it's relatively expensive to get it again later.  Note there is no
+ * need for a "sortable" flag since OidIsValid(sortop) serves the purpose.
+ *
  * A query might have both ORDER BY and DISTINCT (or DISTINCT ON) clauses.
  * In SELECT DISTINCT, the distinctClause list is as long or longer than the
  * sortClause list, while in SELECT DISTINCT ON it's typically shorter.
@@ -789,6 +796,7 @@ typedef struct SortGroupClause
 	Oid			eqop;			/* the equality operator ('=' op) */
 	Oid			sortop;			/* the ordering operator ('<' op), or 0 */
 	bool		nulls_first;	/* do NULLs come before normal values? */
+	bool		hashable;		/* can eqop be implemented by hashing? */
 } SortGroupClause;
 
 /*
diff --git a/src/include/parser/parse_oper.h b/src/include/parser/parse_oper.h
index 03bc9598f54..4ef1d0c9776 100644
--- a/src/include/parser/parse_oper.h
+++ b/src/include/parser/parse_oper.h
@@ -48,7 +48,8 @@ extern Operator compatible_oper(ParseState *pstate, List *op,
 /* Routines for identifying "<", "=", ">" operators for a type */
 extern 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);
 
 /* Convenience routines for common calls on the above */
 extern Oid	compatible_oper_opid(List *op, Oid arg1, Oid arg2, bool noError);
diff --git a/src/include/utils/array.h b/src/include/utils/array.h
index bce28bb26d9..dba9c3d741f 100644
--- a/src/include/utils/array.h
+++ b/src/include/utils/array.h
@@ -192,6 +192,7 @@ extern Datum array_gt(PG_FUNCTION_ARGS);
 extern Datum array_le(PG_FUNCTION_ARGS);
 extern Datum array_ge(PG_FUNCTION_ARGS);
 extern Datum btarraycmp(PG_FUNCTION_ARGS);
+extern Datum hash_array(PG_FUNCTION_ARGS);
 extern Datum arrayoverlap(PG_FUNCTION_ARGS);
 extern Datum arraycontains(PG_FUNCTION_ARGS);
 extern Datum arraycontained(PG_FUNCTION_ARGS);
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index 02c0219fa0e..b6104d7deca 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -67,8 +67,8 @@ extern Oid	get_opclass_input_type(Oid opclass);
 extern RegProcedure get_opcode(Oid opno);
 extern char *get_opname(Oid opno);
 extern void op_input_types(Oid opno, Oid *lefttype, Oid *righttype);
-extern bool op_mergejoinable(Oid opno);
-extern bool op_hashjoinable(Oid opno);
+extern bool op_mergejoinable(Oid opno, Oid inputtype);
+extern bool op_hashjoinable(Oid opno, Oid inputtype);
 extern bool op_strict(Oid opno);
 extern char op_volatile(Oid opno);
 extern Oid	get_commutator(Oid opno);
diff --git a/src/include/utils/typcache.h b/src/include/utils/typcache.h
index 28b66718b33..313f7815918 100644
--- a/src/include/utils/typcache.h
+++ b/src/include/utils/typcache.h
@@ -49,16 +49,18 @@ typedef struct TypeCacheEntry
 	Oid			lt_opr;			/* the less-than operator */
 	Oid			gt_opr;			/* the greater-than operator */
 	Oid			cmp_proc;		/* the btree comparison function */
+	Oid			hash_proc;		/* the hash calculation function */
 
 	/*
-	 * Pre-set-up fmgr call info for the equality operator and the btree
-	 * comparison function.  These are kept in the type cache to avoid
-	 * problems with memory leaks in repeated calls to array_eq and array_cmp.
-	 * There is not currently a need to maintain call info for the lt_opr or
-	 * gt_opr.
+	 * Pre-set-up fmgr call info for the equality operator, the btree
+	 * comparison function, and the hash calculation function.  These are kept
+	 * in the type cache to avoid problems with memory leaks in repeated calls
+	 * to array_eq, array_cmp, hash_array.  There is not currently a need to
+	 * maintain call info for the lt_opr or gt_opr.
 	 */
 	FmgrInfo	eq_opr_finfo;
 	FmgrInfo	cmp_proc_finfo;
+	FmgrInfo	hash_proc_finfo;
 
 	/*
 	 * Tuple descriptor if it's a composite type (row type).  NULL if not
@@ -79,10 +81,13 @@ typedef struct TypeCacheEntry
 #define TYPECACHE_LT_OPR			0x0002
 #define TYPECACHE_GT_OPR			0x0004
 #define TYPECACHE_CMP_PROC			0x0008
-#define TYPECACHE_EQ_OPR_FINFO		0x0010
-#define TYPECACHE_CMP_PROC_FINFO	0x0020
-#define TYPECACHE_TUPDESC			0x0040
-#define TYPECACHE_BTREE_OPFAMILY	0x0080
+#define TYPECACHE_HASH_PROC			0x0010
+#define TYPECACHE_EQ_OPR_FINFO		0x0020
+#define TYPECACHE_CMP_PROC_FINFO	0x0040
+#define TYPECACHE_HASH_PROC_FINFO	0x0080
+#define TYPECACHE_TUPDESC			0x0100
+#define TYPECACHE_BTREE_OPFAMILY	0x0200
+#define TYPECACHE_HASH_OPFAMILY		0x0400
 
 extern TypeCacheEntry *lookup_type_cache(Oid type_id, int flags);