nodehashjoin.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * nodeHashjoin.c
 *	  Routines to handle hash join nodes
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/executor/nodeHashjoin.c,v 1.22 1999/05/25 22:41:01 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <sys/types.h>
#include <string.h>

#include "postgres.h"

#include "executor/execdebug.h"
#include "executor/executor.h"
#include "executor/nodeHash.h"
#include "executor/nodeHashjoin.h"
#include "optimizer/clauses.h"	/* for get_leftop */

static TupleTableSlot *ExecHashJoinOuterGetTuple(Plan *node, Plan *parent,
						  HashJoinState *hjstate);
static TupleTableSlot *ExecHashJoinGetSavedTuple(HashJoinState *hjstate,
						  BufFile *file,
						  TupleTableSlot *tupleSlot);
static int	ExecHashJoinGetBatch(int bucketno, HashJoinTable hashtable);
static int	ExecHashJoinNewBatch(HashJoinState *hjstate);


/* ----------------------------------------------------------------
 *		ExecHashJoin
 *
 *		This function implements the Hybrid Hashjoin algorithm.
 *		recursive partitioning remains to be added.
 *		Note: the relation we build hash table on is the inner
 *			  the other one is outer.
 * ----------------------------------------------------------------
 */
TupleTableSlot *				/* return: a tuple or NULL */
ExecHashJoin(HashJoin *node)
{
	HashJoinState *hjstate;
	EState	   *estate;
	Plan	   *outerNode;
	Hash	   *hashNode;
	List	   *hjclauses;
	Expr	   *clause;
	List	   *qual;
	ScanDirection dir;
	TupleTableSlot *inntuple;
	Var		   *outerVar;
	ExprContext *econtext;
	HashJoinTable hashtable;
	HeapTuple	curtuple;
	bool		qualResult;
	TupleTableSlot *outerTupleSlot;
	TupleTableSlot *innerTupleSlot;
	Var		   *innerhashkey;
	int			i;
	bool		hashPhaseDone;

	/* ----------------
	 *	get information from HashJoin node
	 * ----------------
	 */
	hjstate = node->hashjoinstate;
	hjclauses = node->hashclauses;
	clause = lfirst(hjclauses);
	estate = node->join.state;
	qual = node->join.qual;
	hashNode = (Hash *) innerPlan(node);
	outerNode = outerPlan(node);
	hashPhaseDone = node->hashdone;

	dir = estate->es_direction;

	/* -----------------
	 * get information from HashJoin state
	 * -----------------
	 */
	hashtable = hjstate->hj_HashTable;

	/* --------------------
	 * initialize expression context
	 * --------------------
	 */
	econtext = hjstate->jstate.cs_ExprContext;

	if (hjstate->jstate.cs_TupFromTlist)
	{
		TupleTableSlot *result;
		bool		isDone;

		result = ExecProject(hjstate->jstate.cs_ProjInfo, &isDone);
		if (!isDone)
			return result;
	}

	/* ----------------
	 *	if this is the first call, build the hash table for inner relation
	 * ----------------
	 */
	if (!hashPhaseDone)
	{							/* if the hash phase not completed */
		if (hashtable == NULL)
		{						/* if the hash table has not been created */
			/* ----------------
			 * create the hash table
			 * ----------------
			 */
			hashtable = ExecHashTableCreate(hashNode);
			hjstate->hj_HashTable = hashtable;
			innerhashkey = hashNode->hashkey;
			hjstate->hj_InnerHashKey = innerhashkey;

			/* ----------------
			 * execute the Hash node, to build the hash table
			 * ----------------
			 */
			hashNode->hashstate->hashtable = hashtable;
			innerTupleSlot = ExecProcNode((Plan *) hashNode, (Plan *) node);
		}
		node->hashdone = true;
		/* ----------------
		 * Open temp files for outer batches, if needed.
		 * Note that file buffers are palloc'd in regular executor context.
		 * ----------------
		 */
		for (i = 0; i < hashtable->nbatch; i++)
		{
			File		tfile = OpenTemporaryFile();

			Assert(tfile >= 0);
			hashtable->outerBatchFile[i] = BufFileCreate(tfile);
		}
	}
	else if (hashtable == NULL)
		return NULL;

	/* ----------------
	 *	Now get an outer tuple and probe into the hash table for matches
	 * ----------------
	 */
	outerTupleSlot = hjstate->jstate.cs_OuterTupleSlot;
	outerVar = get_leftop(clause);

	for (;;)
	{

		/*
		 * if the current outer tuple is nil, get a new one
		 */
		if (TupIsNull(outerTupleSlot))
		{
			outerTupleSlot = ExecHashJoinOuterGetTuple(outerNode,
													   (Plan *) node,
													   hjstate);
			if (TupIsNull(outerTupleSlot))
			{

				/*
				 * when the last batch runs out, clean up and exit
				 */
				ExecHashTableDestroy(hashtable);
				hjstate->hj_HashTable = NULL;
				return NULL;
			}

			/*
			 * now we have an outer tuple, find the corresponding bucket
			 * for this tuple from the hash table
			 */
			econtext->ecxt_outertuple = outerTupleSlot;
			hjstate->hj_CurBucketNo = ExecHashGetBucket(hashtable, econtext,
														outerVar);
			hjstate->hj_CurTuple = NULL;

			/* ----------------
			 *	Now we've got an outer tuple and the corresponding hash bucket,
			 *	but this tuple may not belong to the current batch.
			 *	This need only be checked in the first pass.
			 * ----------------
			 */
			if (hashtable->curbatch == 0)
			{
				int			batch = ExecHashJoinGetBatch(hjstate->hj_CurBucketNo,
														 hashtable);

				if (batch > 0)
				{

					/*
					 * Need to postpone this outer tuple to a later batch.
					 * Save it in the corresponding outer-batch file.
					 */
					int			batchno = batch - 1;

					hashtable->outerBatchSize[batchno]++;
					ExecHashJoinSaveTuple(outerTupleSlot->val,
									 hashtable->outerBatchFile[batchno]);
					ExecClearTuple(outerTupleSlot);
					continue;	/* loop around for a new outer tuple */
				}
			}
		}

		/*
		 * OK, scan the selected hash bucket for matches
		 */
		for (;;)
		{
			curtuple = ExecScanHashBucket(hjstate,
										  hjclauses,
										  econtext);
			if (curtuple == NULL)
				break;			/* out of matches */

			/*
			 * we've got a match, but still need to test qpqual
			 */
			inntuple = ExecStoreTuple(curtuple,
									  hjstate->hj_HashTupleSlot,
									  InvalidBuffer,
									  false);	/* don't pfree this tuple */
			econtext->ecxt_innertuple = inntuple;
			qualResult = ExecQual(qual, econtext);
			/* ----------------
			 * if we pass the qual, then save state for next call and
			 * have ExecProject form the projection, store it
			 * in the tuple table, and return the slot.
			 * ----------------
			 */
			if (qualResult)
			{
				ProjectionInfo *projInfo;
				TupleTableSlot *result;
				bool		isDone;

				hjstate->jstate.cs_OuterTupleSlot = outerTupleSlot;
				projInfo = hjstate->jstate.cs_ProjInfo;
				result = ExecProject(projInfo, &isDone);
				hjstate->jstate.cs_TupFromTlist = !isDone;
				return result;
			}
		}

		/* ----------------
		 *	 Now the current outer tuple has run out of matches,
		 *	 so we free it and loop around to get a new outer tuple.
		 * ----------------
		 */
		ExecClearTuple(outerTupleSlot);
	}
}

/* ----------------------------------------------------------------
 *		ExecInitHashJoin
 *
 *		Init routine for HashJoin node.
 * ----------------------------------------------------------------
 */
bool							/* return: initialization status */
ExecInitHashJoin(HashJoin *node, EState *estate, Plan *parent)
{
	HashJoinState *hjstate;
	Plan	   *outerNode;
	Hash	   *hashNode;

	/* ----------------
	 *	assign the node's execution state
	 * ----------------
	 */
	node->join.state = estate;

	/* ----------------
	 * create state structure
	 * ----------------
	 */
	hjstate = makeNode(HashJoinState);

	node->hashjoinstate = hjstate;

	/* ----------------
	 *	Miscellaneous initialization
	 *
	 *		 +	assign node's base_id
	 *		 +	assign debugging hooks and
	 *		 +	create expression context for node
	 * ----------------
	 */
	ExecAssignNodeBaseInfo(estate, &hjstate->jstate, parent);
	ExecAssignExprContext(estate, &hjstate->jstate);

#define HASHJOIN_NSLOTS 2
	/* ----------------
	 *	tuple table initialization
	 * ----------------
	 */
	ExecInitResultTupleSlot(estate, &hjstate->jstate);
	ExecInitOuterTupleSlot(estate, hjstate);

	/* ----------------
	 * initializes child nodes
	 * ----------------
	 */
	outerNode = outerPlan((Plan *) node);
	hashNode = (Hash *) innerPlan((Plan *) node);

	ExecInitNode(outerNode, estate, (Plan *) node);
	ExecInitNode((Plan *) hashNode, estate, (Plan *) node);

	/* ----------------
	 *	now for some voodoo.  our temporary tuple slot
	 *	is actually the result tuple slot of the Hash node
	 *	(which is our inner plan).	we do this because Hash
	 *	nodes don't return tuples via ExecProcNode() -- instead
	 *	the hash join node uses ExecScanHashBucket() to get
	 *	at the contents of the hash table.	-cim 6/9/91
	 * ----------------
	 */
	{
		HashState  *hashstate = hashNode->hashstate;
		TupleTableSlot *slot = hashstate->cstate.cs_ResultTupleSlot;

		hjstate->hj_HashTupleSlot = slot;
	}
	hjstate->hj_OuterTupleSlot->ttc_tupleDescriptor = ExecGetTupType(outerNode);

/*
	hjstate->hj_OuterTupleSlot->ttc_execTupDescriptor = ExecGetExecTupDesc(outerNode);
*/

	/* ----------------
	 *	initialize tuple type and projection info