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.

1 files changed, 8 insertions, 0 deletions

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;
 
 /*