Upgrade planner and executor to allow multiple hash keys for a hash join,

instead of only one.  This should speed up planning (only one hash path
to consider for a given pair of relations) as well as allow more effective
hashing, when there are multiple hashable joinclauses.

14 files changed, 182 insertions, 133 deletions

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 57faf0622cb..c2c3ab66644 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/executor/nodeHash.c,v 1.67 2002/11/06 22:31:23 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/executor/nodeHash.c,v 1.68 2002/11/30 00:08:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -45,7 +45,7 @@ ExecHash(Hash *node)
 	EState	   *estate;
 	HashState  *hashstate;
 	Plan	   *outerNode;
-	Node	   *hashkey;
+	List	   *hashkeys;
 	HashJoinTable hashtable;
 	TupleTableSlot *slot;
 	ExprContext *econtext;
@@ -79,7 +79,7 @@ ExecHash(Hash *node)
 	/*
 	 * set expression context
 	 */
-	hashkey = node->hashkey;
+	hashkeys = node->hashkeys;
 	econtext = hashstate->cstate.cs_ExprContext;
 
 	/*
@@ -91,7 +91,7 @@ ExecHash(Hash *node)
 		if (TupIsNull(slot))
 			break;
 		econtext->ecxt_innertuple = slot;
-		ExecHashTableInsert(hashtable, econtext, hashkey);
+		ExecHashTableInsert(hashtable, econtext, hashkeys);
 		ExecClearTuple(slot);
 	}
 
@@ -212,7 +212,9 @@ ExecHashTableCreate(Hash *node)
 	int			totalbuckets;
 	int			nbuckets;
 	int			nbatch;
+	int			nkeys;
 	int			i;
+	List	   *hk;
 	MemoryContext oldcxt;
 
 	/*
@@ -248,11 +250,19 @@ ExecHashTableCreate(Hash *node)
 	hashtable->outerBatchSize = NULL;
 
 	/*
-	 * Get info about the datatype of the hash key.
+	 * Get info about the datatypes of the hash keys.
 	 */
-	get_typlenbyval(exprType(node->hashkey),
-					&hashtable->typLen,
-					&hashtable->typByVal);
+	nkeys = length(node->hashkeys);
+	hashtable->typLens = (int16 *) palloc(nkeys * sizeof(int16));
+	hashtable->typByVals = (bool *) palloc(nkeys * sizeof(bool));
+	i = 0;
+	foreach(hk, node->hashkeys)
+	{
+		get_typlenbyval(exprType(lfirst(hk)),
+						&hashtable->typLens[i],
+						&hashtable->typByVals[i]);
+		i++;
+	}
 
 	/*
 	 * Create temporary memory contexts in which to keep the hashtable
@@ -465,9 +475,9 @@ ExecHashTableDestroy(HashJoinTable hashtable)
 void
 ExecHashTableInsert(HashJoinTable hashtable,
 					ExprContext *econtext,
-					Node *hashkey)
+					List *hashkeys)
 {
-	int			bucketno = ExecHashGetBucket(hashtable, econtext, hashkey);
+	int			bucketno = ExecHashGetBucket(hashtable, econtext, hashkeys);
 	TupleTableSlot *slot = econtext->ecxt_innertuple;
 	HeapTuple	heapTuple = slot->val;
 
@@ -522,44 +532,55 @@ ExecHashTableInsert(HashJoinTable hashtable,
 int
 ExecHashGetBucket(HashJoinTable hashtable,
 				  ExprContext *econtext,
-				  Node *hashkey)
+				  List *hashkeys)
 {
+	uint32		hashkey = 0;
 	int			bucketno;
-	Datum		keyval;
-	bool		isNull;
+	List	   *hk;
+	int			i = 0;
 	MemoryContext oldContext;
 
 	/*
 	 * We reset the eval context each time to reclaim any memory leaked in
-	 * the hashkey expression or ComputeHashFunc itself.
+	 * the hashkey expressions or ComputeHashFunc itself.
 	 */
 	ResetExprContext(econtext);
 
 	oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 
-	/*
-	 * Get the join attribute value of the tuple
-	 */
-	keyval = ExecEvalExpr(hashkey, econtext, &isNull, NULL);
-
-	/*
-	 * Compute the hash function
-	 */
-	if (isNull)
-		bucketno = 0;
-	else
+	foreach(hk, hashkeys)
 	{
-		bucketno = ComputeHashFunc(keyval,
-								   (int) hashtable->typLen,
-								   hashtable->typByVal)
-			% (uint32) hashtable->totalbuckets;
+		Datum		keyval;
+		bool		isNull;
+
+		/* rotate hashkey left 1 bit at each step */
+		hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+
+		/*
+		 * Get the join attribute value of the tuple
+		 */
+		keyval = ExecEvalExpr(lfirst(hk), econtext, &isNull, NULL);
+
+		/*
+		 * Compute the hash function
+		 */
+		if (!isNull)			/* treat nulls as having hash key 0 */
+		{
+			hashkey ^= ComputeHashFunc(keyval,
+									   (int) hashtable->typLens[i],
+									   hashtable->typByVals[i]);
+		}
+
+		i++;
 	}
 
+	bucketno = hashkey % (uint32) hashtable->totalbuckets;
+
 #ifdef HJDEBUG
 	if (bucketno >= hashtable->nbuckets)
-		printf("hash(%ld) = %d SAVED\n", (long) keyval, bucketno);
+		printf("hash(%u) = %d SAVED\n", hashkey, bucketno);
 	else
-		printf("hash(%ld) = %d\n", (long) keyval, bucketno);
+		printf("hash(%u) = %d\n", hashkey, bucketno);
 #endif
 
 	MemoryContextSwitchTo(oldContext);
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index f1484c4a054..8f0e700ac35 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/executor/nodeHashjoin.c,v 1.41 2002/09/02 02:47:02 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/executor/nodeHashjoin.c,v 1.42 2002/11/30 00:08:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -48,12 +48,11 @@ ExecHashJoin(HashJoin *node)
 	Plan	   *outerNode;
 	Hash	   *hashNode;
 	List	   *hjclauses;
-	Expr	   *clause;
+	List	   *outerkeys;
 	List	   *joinqual;
 	List	   *otherqual;
 	ScanDirection dir;
 	TupleTableSlot *inntuple;
-	Node	   *outerVar;
 	ExprContext *econtext;
 	ExprDoneCond isDone;
 	HashJoinTable hashtable;
@@ -68,7 +67,6 @@ ExecHashJoin(HashJoin *node)
 	 */
 	hjstate = node->hashjoinstate;
 	hjclauses = node->hashclauses;
-	clause = lfirst(hjclauses);
 	estate = node->join.plan.state;
 	joinqual = node->join.joinqual;
 	otherqual = node->join.plan.qual;
@@ -81,6 +79,7 @@ ExecHashJoin(HashJoin *node)
 	 * get information from HashJoin state
 	 */
 	hashtable = hjstate->hj_HashTable;
+	outerkeys = hjstate->hj_OuterHashKeys;
 	econtext = hjstate->jstate.cs_ExprContext;
 
 	/*
@@ -119,7 +118,6 @@ ExecHashJoin(HashJoin *node)
 			 */
 			hashtable = ExecHashTableCreate(hashNode);
 			hjstate->hj_HashTable = hashtable;
-			hjstate->hj_InnerHashKey = hashNode->hashkey;
 
 			/*
 			 * execute the Hash node, to build the hash table
@@ -143,7 +141,6 @@ ExecHashJoin(HashJoin *node)
 	 * Now get an outer tuple and probe into the hash table for matches
 	 */
 	outerTupleSlot = hjstate->jstate.cs_OuterTupleSlot;
-	outerVar = (Node *) get_leftop(clause);
 
 	for (;;)
 	{
@@ -175,7 +172,7 @@ ExecHashJoin(HashJoin *node)
 			 * for this tuple from the hash table
 			 */
 			hjstate->hj_CurBucketNo = ExecHashGetBucket(hashtable, econtext,
-														outerVar);
+														outerkeys);
 			hjstate->hj_CurTuple = NULL;
 
 			/*
@@ -308,6 +305,7 @@ ExecInitHashJoin(HashJoin *node, EState *estate, Plan *parent)
 	HashJoinState *hjstate;
 	Plan	   *outerNode;
 	Hash	   *hashNode;
+	List	   *hcl;
 
 	/*
 	 * assign the node's execution state
@@ -391,7 +389,18 @@ ExecInitHashJoin(HashJoin *node, EState *estate, Plan *parent)
 	hjstate->hj_HashTable = (HashJoinTable) NULL;
 	hjstate->hj_CurBucketNo = 0;
 	hjstate->hj_CurTuple = (HashJoinTuple) NULL;
-	hjstate->hj_InnerHashKey = (Node *) NULL;
+
+	/*
+	 * The planner already made a list of the inner hashkeys for us,
+	 * but we also need a list of the outer hashkeys.
+	 */
+	hjstate->hj_InnerHashKeys = hashNode->hashkeys;
+	hjstate->hj_OuterHashKeys = NIL;
+	foreach(hcl, node->hashclauses)
+	{
+		hjstate->hj_OuterHashKeys = lappend(hjstate->hj_OuterHashKeys,
+											get_leftop(lfirst(hcl)));
+	}
 
 	hjstate->jstate.cs_OuterTupleSlot = NULL;
 	hjstate->jstate.cs_TupFromTlist = false;
@@ -555,7 +564,7 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
 	BufFile    *innerFile;
 	TupleTableSlot *slot;
 	ExprContext *econtext;
-	Node	   *innerhashkey;
+	List	   *innerhashkeys;
 
 	if (newbatch > 1)
 	{
@@ -603,7 +612,7 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
 	ExecHashTableReset(hashtable, innerBatchSize[newbatch - 1]);
 
 	econtext = hjstate->jstate.cs_ExprContext;
-	innerhashkey = hjstate->hj_InnerHashKey;
+	innerhashkeys = hjstate->hj_InnerHashKeys;
 
 	while ((slot = ExecHashJoinGetSavedTuple(hjstate,
 											 innerFile,
@@ -611,7 +620,7 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
 		   && !TupIsNull(slot))
 	{
 		econtext->ecxt_innertuple = slot;
-		ExecHashTableInsert(hashtable, econtext, innerhashkey);
+		ExecHashTableInsert(hashtable, econtext, innerhashkeys);
 	}
 
 	/*
@@ -694,7 +703,6 @@ ExecReScanHashJoin(HashJoin *node, ExprContext *exprCtxt, Plan *parent)
 
 	hjstate->hj_CurBucketNo = 0;
 	hjstate->hj_CurTuple = (HashJoinTuple) NULL;
-	hjstate->hj_InnerHashKey = (Node *) NULL;
 
 	hjstate->jstate.cs_OuterTupleSlot = (TupleTableSlot *) NULL;
 	hjstate->jstate.cs_TupFromTlist = false;
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index a678d6326b1..7798913cde5 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -15,7 +15,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.223 2002/11/25 21:29:36 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.224 2002/11/30 00:08:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -429,7 +429,6 @@ _copyHashJoin(HashJoin *from)
 	 * copy remainder of node
 	 */
 	COPY_NODE_FIELD(hashclauses);
-	COPY_SCALAR_FIELD(hashjoinop);
 
 	/* subPlan list must point to subplans in the new subtree, not the old */
 	FIX_SUBPLAN_LINKS(join.plan.subPlan, hashclauses);
@@ -593,9 +592,9 @@ _copyHash(Hash *from)
 	/*
 	 * copy remainder of node
 	 */
-	COPY_NODE_FIELD(hashkey);
+	COPY_NODE_FIELD(hashkeys);
 
-	/* XXX could the hashkey contain subplans?  Not at present... */
+	/* XXX could the hashkeys contain subplans?  Not at present... */
 
 	return newnode;
 }
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 11572a4ebad..528148f02f0 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.183 2002/11/25 21:29:36 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.184 2002/11/30 00:08:16 tgl Exp $
  *
  * NOTES
  *	  Every node type that can appear in stored rules' parsetrees *must*
@@ -538,7 +538,6 @@ _outHashJoin(StringInfo str, HashJoin *node)
 	_outJoinPlanInfo(str, (Join *) node);
 
 	WRITE_NODE_FIELD(hashclauses);
-	WRITE_OID_FIELD(hashjoinop);
 }
 
 static void
@@ -634,7 +633,7 @@ _outHash(StringInfo str, Hash *node)
 
 	_outPlanInfo(str, (Plan *) node);
 
-	WRITE_NODE_FIELD(hashkey);
+	WRITE_NODE_FIELD(hashkeys);
 }
 
 static void
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 6cf8b2af4b5..fbdeea414c2 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -42,7 +42,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.91 2002/11/21 00:42:19 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.92 2002/11/30 00:08:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -819,7 +819,7 @@ cost_mergejoin(Path *path, Query *root,
  * 'outer_path' is the path for the outer relation
  * 'inner_path' is the path for the inner relation
  * 'restrictlist' are the RestrictInfo nodes to be applied at the join
- * 'hashclauses' is a list of the hash join clause (always a 1-element list)
+ * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
  *		(this should be a subset of the restrictlist)
  */
 void
@@ -838,10 +838,8 @@ cost_hashjoin(Path *path, Query *root,
 	double		innerbytes = relation_byte_size(inner_path->parent->rows,
 											  inner_path->parent->width);
 	long		hashtablebytes = SortMem * 1024L;
-	RestrictInfo *restrictinfo;
-	Var		   *left,
-			   *right;
 	Selectivity innerbucketsize;
+	List	   *hcl;
 
 	if (!enable_hashjoin)
 		startup_cost += disable_cost;
@@ -856,43 +854,57 @@ cost_hashjoin(Path *path, Query *root,
 	run_cost += cpu_operator_cost * outer_path->parent->rows;
 
 	/*
-	 * Determine bucketsize fraction for inner relation.  First we have to
-	 * figure out which side of the hashjoin clause is the inner side.
+	 * Determine bucketsize fraction for inner relation.  We use the
+	 * smallest bucketsize estimated for any individual hashclause;
+	 * this is undoubtedly conservative.
 	 */
-	Assert(length(hashclauses) == 1);
-	Assert(IsA(lfirst(hashclauses), RestrictInfo));
-	restrictinfo = (RestrictInfo *) lfirst(hashclauses);
-	/* these must be OK, since check_hashjoinable accepted the clause */
-	left = get_leftop(restrictinfo->clause);
-	right = get_rightop(restrictinfo->clause);
-
-	/*
-	 * Since we tend to visit the same clauses over and over when planning
-	 * a large query, we cache the bucketsize estimate in the RestrictInfo
-	 * node to avoid repeated lookups of statistics.
-	 */
-	if (VARISRELMEMBER(right->varno, inner_path->parent))
+	innerbucketsize = 1.0;
+	foreach(hcl, hashclauses)
 	{
-		/* righthand side is inner */
-		innerbucketsize = restrictinfo->right_bucketsize;
-		if (innerbucketsize < 0)
+		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(hcl);
+		Var		   *left,
+				   *right;
+		Selectivity thisbucketsize;
+
+		Assert(IsA(restrictinfo, RestrictInfo));
+		/* these must be OK, since check_hashjoinable accepted the clause */
+		left = get_leftop(restrictinfo->clause);
+		right = get_rightop(restrictinfo->clause);
+
+		/*
+		 * First we have to figure out which side of the hashjoin clause is the
+		 * inner side.
+		 *
+		 * Since we tend to visit the same clauses over and over when planning
+		 * a large query, we cache the bucketsize estimate in the RestrictInfo
+		 * node to avoid repeated lookups of statistics.
+		 */
+		if (VARISRELMEMBER(right->varno, inner_path->parent))
 		{
-			/* not cached yet */
-			innerbucketsize = estimate_hash_bucketsize(root, right);
-			restrictinfo->right_bucketsize = innerbucketsize;
+			/* righthand side is inner */
+			thisbucketsize = restrictinfo->right_bucketsize;
+			if (thisbucketsize < 0)
+			{
+				/* not cached yet */
+				thisbucketsize = estimate_hash_bucketsize(root, right);
+				restrictinfo->right_bucketsize = thisbucketsize;
+			}
 		}
-	}
-	else
-	{
-		Assert(VARISRELMEMBER(left->varno, inner_path->parent));
-		/* lefthand side is inner */
-		innerbucketsize = restrictinfo->left_bucketsize;
-		if (innerbucketsize < 0)
+		else
 		{
-			/* not cached yet */
-			innerbucketsize = estimate_hash_bucketsize(root, left);
-			restrictinfo->left_bucketsize = innerbucketsize;
+			Assert(VARISRELMEMBER(left->varno, inner_path->parent));
+			/* lefthand side is inner */
+			thisbucketsize = restrictinfo->left_bucketsize;
+			if (thisbucketsize < 0)
+			{
+				/* not cached yet */
+				thisbucketsize = estimate_hash_bucketsize(root, left);
+				restrictinfo->left_bucketsize = thisbucketsize;
+			}
 		}
+
+		if (innerbucketsize > thisbucketsize)
+			innerbucketsize = thisbucketsize;
 	}
 
 	/*
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index ac5d4a72d45..6069a34d879 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.72 2002/11/24 21:52:14 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.73 2002/11/30 00:08:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -701,7 +701,7 @@ match_unsorted_inner(Query *root,
 /*
  * hash_inner_and_outer
  *	  Create hashjoin join paths by explicitly hashing both the outer and
- *	  inner join relations of each available hash clause.
+ *	  inner keys of each available hash clause.
  *
  * 'joinrel' is the join relation
  * 'outerrel' is the outer join relation
@@ -719,6 +719,7 @@ hash_inner_and_outer(Query *root,
 					 JoinType jointype)
 {
 	bool		isouterjoin;
+	List	   *hashclauses;
 	List	   *i;
 
 	/*
@@ -737,20 +738,18 @@ hash_inner_and_outer(Query *root,
 	}
 
 	/*
+	 * We need to build only one hashpath for any given pair of outer and
+	 * inner relations; all of the hashable clauses will be used as keys.
+	 *
 	 * Scan the join's restrictinfo list to find hashjoinable clauses that
-	 * are usable with this pair of sub-relations.	Since we currently
-	 * accept only var-op-var clauses as hashjoinable, we need only check
-	 * the membership of the vars to determine whether a particular clause
-	 * can be used with this pair of sub-relations.  This code would need
-	 * to be upgraded if we wanted to allow more-complex expressions in
-	 * hash joins.
+	 * are usable with this pair of sub-relations.
 	 */
+	hashclauses = NIL;
 	foreach(i, restrictlist)
 	{
 		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
 		Var		   *left,
 				   *right;
-		List	   *hashclauses;
 
 		if (restrictinfo->hashjoinoperator == InvalidOid)
 			continue;			/* not hashjoinable */
@@ -768,6 +767,12 @@ hash_inner_and_outer(Query *root,
 
 		/*
 		 * Check if clause is usable with these input rels.
+		 *
+		 * Since we currently accept only var-op-var clauses as hashjoinable,
+		 * we need only check the membership of the vars to determine whether
+		 * a particular clause can be used with this pair of sub-relations.
+		 * This code would need to be upgraded if we wanted to allow
+		 * more-complex expressions in hash joins.
 		 */
 		if (VARISRELMEMBER(left->varno, outerrel) &&
 			VARISRELMEMBER(right->varno, innerrel))
@@ -782,9 +787,12 @@ hash_inner_and_outer(Query *root,
 		else
 			continue;			/* no good for these input relations */
 
-		/* always a one-element list of hash clauses */
-		hashclauses = makeList1(restrictinfo);
+		hashclauses = lappend(hashclauses, restrictinfo);
+	}
 
+	/* If we found any usable hashclauses, make a path */
+	if (hashclauses)
+	{
 		/*
 		 * We consider both the cheapest-total-cost and
 		 * cheapest-startup-cost outer paths.  There's no need to consider
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index b393252542f..d43e3271fbf 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.124 2002/11/21 00:42:19 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.125 2002/11/30 00:08:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -91,7 +91,7 @@ static HashJoin *make_hashjoin(List *tlist,
 			  List *hashclauses,
 			  Plan *lefttree, Plan *righttree,
 			  JoinType jointype);
-static Hash *make_hash(List *tlist, Node *hashkey, Plan *lefttree);
+static Hash *make_hash(List *tlist, List *hashkeys, Plan *lefttree);
 static MergeJoin *make_mergejoin(List *tlist,
 			   List *joinclauses, List *otherclauses,
 			   List *mergeclauses,
@@ -910,14 +910,9 @@ create_hashjoin_plan(Query *root,
 	List	   *hashclauses;
 	HashJoin   *join_plan;
 	Hash	   *hash_plan;
-	Node	   *innerhashkey;
+	List	   *innerhashkeys;
+	List	   *hcl;
 
-	/*
-	 * NOTE: there will always be exactly one hashclause in the list
-	 * best_path->path_hashclauses (cf. hash_inner_and_outer()). We
-	 * represent it as a list anyway, for convenience with routines that
-	 * want to work on lists of clauses.
-	 */
 	hashclauses = get_actual_clauses(best_path->path_hashclauses);
 
 	/*
@@ -950,13 +945,20 @@ create_hashjoin_plan(Query *root,
 											   inner_tlist,
 											   (Index) 0));
 
-	/* Now the righthand op of the sole hashclause is the inner hash key. */
-	innerhashkey = (Node *) get_rightop(lfirst(hashclauses));
+	/*
+	 * Extract the inner hash keys (right-hand operands of the hashclauses)
+	 * to put in the Hash node.
+	 */
+	innerhashkeys = NIL;
+	foreach(hcl, hashclauses)
+	{
+		innerhashkeys = lappend(innerhashkeys, get_rightop(lfirst(hcl)));
+	}
 
 	/*
 	 * Build the hash node and hash join node.
 	 */
-	hash_plan = make_hash(inner_tlist, innerhashkey, inner_plan);
+	hash_plan = make_hash(inner_tlist, innerhashkeys, inner_plan);
 	join_plan = make_hashjoin(tlist,
 							  joinclauses,
 							  otherclauses,
@@ -1511,7 +1513,7 @@ make_hashjoin(List *tlist,
 }
 
 static Hash *
-make_hash(List *tlist, Node *hashkey, Plan *lefttree)
+make_hash(List *tlist, List *hashkeys, Plan *lefttree)
 {
 	Hash	   *node = makeNode(Hash);
 	Plan	   *plan = &node->plan;
@@ -1528,7 +1530,7 @@ make_hash(List *tlist, Node *hashkey, Plan *lefttree)
 	plan->qual = NULL;
 	plan->lefttree = lefttree;
 	plan->righttree = NULL;
-	node->hashkey = hashkey;
+	node->hashkeys = hashkeys;
 
 	return node;
 }
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 5b171fb819a..61476a65604 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.56 2002/11/26 03:01:58 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.57 2002/11/30 00:08:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -677,7 +677,7 @@ SS_finalize_plan(Plan *plan, List *rtable)
 			break;
 
 		case T_Hash:
-			finalize_primnode(((Hash *) plan)->hashkey,
+			finalize_primnode((Node *) ((Hash *) plan)->hashkeys,
 							  &results);
 			break;
 
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index e99435a6edf..98227355605 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.80 2002/11/24 21:52:14 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.81 2002/11/30 00:08:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -616,7 +616,7 @@ create_mergejoin_path(Query *root,
  * 'outer_path' is the cheapest outer path
  * 'inner_path' is the cheapest inner path
  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
- * 'hashclauses' is a list of the hash join clause (always a 1-element list)
+ * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
  *		(this should be a subset of the restrict_clauses list)
  */
 HashPath *
diff --git a/src/include/executor/hashjoin.h b/src/include/executor/hashjoin.h
index 1869feae08b..a2d5f633fcd 100644
--- a/src/include/executor/hashjoin.h
+++ b/src/include/executor/hashjoin.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: hashjoin.h,v 1.26 2002/06/20 20:29:49 momjian Exp $
+ * $Id: hashjoin.h,v 1.27 2002/11/30 00:08:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -69,12 +69,13 @@ typedef struct HashTableData
 								 * file */
 
 	/*
-	 * Info about the datatype being hashed.  We assume that the inner and
-	 * outer sides of the hash are the same type, or at least
-	 * binary-compatible types.
+	 * Info about the datatypes being hashed.  We assume that the inner and
+	 * outer sides of each hashclause are the same type, or at least
+	 * binary-compatible types.  Each of these fields points to an array
+	 * of the same length as the number of hash keys.
 	 */
-	int16		typLen;
-	bool		typByVal;
+	int16	   *typLens;
+	bool	   *typByVals;
 
 	/*
 	 * During 1st scan of inner relation, we get tuples from executor. If
diff --git a/src/include/executor/nodeHash.h b/src/include/executor/nodeHash.h
index 8bea51e8af0..654906cd3c2 100644
--- a/src/include/executor/nodeHash.h
+++ b/src/include/executor/nodeHash.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nodeHash.h,v 1.25 2002/11/06 22:31:24 tgl Exp $
+ * $Id: nodeHash.h,v 1.26 2002/11/30 00:08:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -24,10 +24,10 @@ extern HashJoinTable ExecHashTableCreate(Hash *node);
 extern void ExecHashTableDestroy(HashJoinTable hashtable);
 extern void ExecHashTableInsert(HashJoinTable hashtable,
 					ExprContext *econtext,
-					Node *hashkey);
+					List *hashkeys);
 extern int ExecHashGetBucket(HashJoinTable hashtable,
 				  ExprContext *econtext,
-				  Node *hashkey);
+				  List *hashkeys);
 extern HeapTuple ExecScanHashBucket(HashJoinState *hjstate, List *hjclauses,
 				   ExprContext *econtext);
 extern void ExecHashTableReset(HashJoinTable hashtable, long ntuples);
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 6ee39b98182..544510746d6 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execnodes.h,v 1.80 2002/11/25 21:29:42 tgl Exp $
+ * $Id: execnodes.h,v 1.81 2002/11/30 00:08:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -618,7 +618,8 @@ typedef struct MergeJoinState
  *								tuple, or NULL if starting search
  *								(CurBucketNo and CurTuple are meaningless
  *								 unless OuterTupleSlot is nonempty!)
- *		hj_InnerHashKey			the inner hash key in the hashjoin condition
+ *		hj_OuterHashKeys		the outer hash keys in the hashjoin condition
+ *		hj_InnerHashKeys		the inner hash keys in the hashjoin condition
  *		hj_OuterTupleSlot		tuple slot for outer tuples
  *		hj_HashTupleSlot		tuple slot for hashed tuples
  *		hj_NullInnerTupleSlot	prepared null tuple for left outer joins
@@ -633,7 +634,8 @@ typedef struct HashJoinState
 	HashJoinTable hj_HashTable;
 	int			hj_CurBucketNo;
 	HashJoinTuple hj_CurTuple;
-	Node	   *hj_InnerHashKey;
+	List	   *hj_OuterHashKeys;
+	List	   *hj_InnerHashKeys;
 	TupleTableSlot *hj_OuterTupleSlot;
 	TupleTableSlot *hj_HashTupleSlot;
 	TupleTableSlot *hj_NullInnerTupleSlot;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 0cf9d0bac91..6a6ac415f9f 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: plannodes.h,v 1.60 2002/11/06 22:31:24 tgl Exp $
+ * $Id: plannodes.h,v 1.61 2002/11/30 00:08:22 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -318,7 +318,6 @@ typedef struct HashJoin
 {
 	Join		join;
 	List	   *hashclauses;
-	Oid			hashjoinop;
 	HashJoinState *hashjoinstate;
 } HashJoin;
 
@@ -443,7 +442,7 @@ typedef struct Limit
 typedef struct Hash
 {
 	Plan		plan;
-	Node	   *hashkey;
+	List	   *hashkeys;
 	HashState  *hashstate;
 } Hash;
 
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a3f0e36c766..4c06224ecce 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.70 2002/11/27 20:52:04 tgl Exp $
+ * $Id: relation.h,v 1.71 2002/11/30 00:08:22 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -464,8 +464,6 @@ typedef struct MergePath
  * A hashjoin path has these fields.
  *
  * The remarks above for mergeclauses apply for hashclauses as well.
- * (But note that path_hashclauses will always be a one-element list,
- * since we only hash on one hashable clause.)
  *
  * Hashjoin does not care what order its inputs appear in, so we have
  * no need for sortkeys.