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.

2 files changed, 72 insertions, 43 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;