nodemergejoin.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * nodeMergejoin.c
 *	  routines supporting merge joins
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/executor/nodeMergejoin.c,v 1.27 1999/05/25 16:08:45 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
/*
 * INTERFACE ROUTINES
 *		ExecMergeJoin			mergejoin outer and inner relations.
 *		ExecInitMergeJoin		creates and initializes run time states
 *		ExecEndMergeJoin		cleand up the node.
 *
 * NOTES
 *		Essential operation of the merge join algorithm is as follows:
 *		(** indicates the tuples satisfy the merge clause).
 *
 *		Join {												   -
 *			get initial outer and inner tuples				INITIALIZE
 *			Skip Inner										SKIPINNER
 *			mark inner position								JOINMARK
 *			do forever {									   -
 *				while (outer == inner) {					JOINTEST
 *					join tuples								JOINTUPLES
 *					advance inner position					NEXTINNER
 *				}											   -
 *				advance outer position						NEXTOUTER
 *				if (outer == mark) {						TESTOUTER
 *					restore inner position to mark			TESTOUTER
 *					continue								   -
 *				} else {									   -
 *					Skip Outer								SKIPOUTER
 *					mark inner position						JOINMARK
 *				}											   -
 *			}												   -
 *		}													   -
 *
 *		Skip Outer {										SKIPOUTER
 *			if (inner == outer) Join Tuples					JOINTUPLES
 *			while (outer < inner)							SKIPOUTER
 *				advance outer								SKIPOUTER
 *			if (outer > inner)								SKIPOUTER
 *				Skip Inner									SKIPINNER
 *		}													   -
 *
 *		Skip Inner {										SKIPINNER
 *			if (inner == outer) Join Tuples					JOINTUPLES
 *			while (outer > inner)							SKIPINNER
 *				advance inner								SKIPINNER
 *			if (outer < inner)								SKIPINNER
 *				Skip Outer									SKIPOUTER
 *		}													   -
 *
 *		The merge join operation is coded in the fashion
 *		of a state machine.  At each state, we do something and then
 *		proceed to another state.  This state is stored in the node's
 *		execution state information and is preserved across calls to
 *		ExecMergeJoin. -cim 10/31/89
 *
 */
#include "postgres.h"

#include "access/heapam.h"
#include "catalog/pg_operator.h"
#include "executor/executor.h"
#include "executor/execdefs.h"
#include "executor/nodeMergejoin.h"
#include "executor/execdebug.h"
#include "utils/lsyscache.h"
#include "utils/psort.h"


static bool MergeCompare(List *eqQual, List *compareQual, ExprContext *econtext);

#define MarkInnerTuple(innerTupleSlot, mergestate) \
( \
	ExecStoreTuple(heap_copytuple((innerTupleSlot)->val), \
				   (mergestate)->mj_MarkedTupleSlot, \
				   InvalidBuffer, \
				   true) \
)


/* ----------------------------------------------------------------
 *		MJFormSkipQual
 *
 *		This takes the mergeclause which is a qualification of the
 *		form ((= expr expr) (= expr expr) ...) and forms a new
 *		qualification like ((> expr expr) (> expr expr) ...) which
 *		is used by ExecMergeJoin() in order to determine if we should
 *		skip tuples.  The replacement operators are named either ">"
 *		or "<" according to the replaceopname parameter, and have the
 *		same operand data types as the "=" operators they replace.
 *		(We expect there to be such operators because the "=" operators
 *		were marked mergejoinable; however, there might be a different
 *		one needed in each qual clause.)
 * ----------------------------------------------------------------
 */
static List *
MJFormSkipQual(List *qualList, char *replaceopname)
{
	List	   *qualCopy;
	List	   *qualcdr;
	Expr	   *qual;
	Oper	   *op;
	HeapTuple	optup;
	Form_pg_operator opform;
	Oid			oprleft,
				oprright;

	/* ----------------
	 *	qualList is a list: ((op .. ..) ...)
	 *	first we make a copy of it.  copyObject() makes a deep copy
	 *	so let's use it instead of the old fashoned lispCopy()...
	 * ----------------
	 */
	qualCopy = (List *) copyObject((Node *) qualList);

	foreach(qualcdr, qualCopy)
	{
		/* ----------------
		 *	 first get the current (op .. ..) list
		 * ----------------
		 */
		qual = lfirst(qualcdr);

		/* ----------------
		 *	 now get at the op
		 * ----------------
		 */
		op = (Oper *) qual->oper;
		if (!IsA(op, Oper))
			elog(ERROR, "MJFormSkipQual: op not an Oper!");

		/* ----------------
		 *	 Get the declared left and right operand types of the operator.
		 *	 Note we do *not* use the actual operand types, since those might
		 *	 be different in scenarios with binary-compatible data types.
		 *	 There should be "<" and ">" operators matching a mergejoinable
		 *	 "=" operator's declared operand types, but we might not find them
		 *	 if we search with the actual operand types.
		 * ----------------
		 */
		optup = get_operator_tuple(op->opno);
		if (!HeapTupleIsValid(optup))	/* shouldn't happen */
			elog(ERROR, "MJFormSkipQual: operator %u not found", op->opno);
		opform = (Form_pg_operator) GETSTRUCT(optup);
		oprleft = opform->oprleft;
		oprright = opform->oprright;

		/* ----------------
		 *	 Now look up the matching "<" or ">" operator.	If there isn't one,
		 *	 whoever marked the "=" operator mergejoinable was a loser.
		 * ----------------
		 */
		optup = SearchSysCacheTuple(OPRNAME,
									PointerGetDatum(replaceopname),
									ObjectIdGetDatum(oprleft),
									ObjectIdGetDatum(oprright),
									CharGetDatum('b'));
		if (!HeapTupleIsValid(optup))
			elog(ERROR,
			"MJFormSkipQual: mergejoin operator %u has no matching %s op",
				 op->opno, replaceopname);
		opform = (Form_pg_operator) GETSTRUCT(optup);

		/* ----------------
		 *	 And replace the data in the copied operator node.
		 * ----------------
		 */
		op->opno = optup->t_data->t_oid;
		op->opid = opform->oprcode;
		op->op_fcache = NULL;
	}

	return qualCopy;
}

/* ----------------------------------------------------------------
 *		MergeCompare
 *
 *		Compare the keys according to 'compareQual' which is of the
 *		form: {(key1a > key2a)(key1b > key2b) ...}.
 *
 *		(actually, it could also be the form (key1a < key2a)..)
 *
 *		This is different from calling ExecQual because ExecQual returns
 *		true only if ALL the comparisions clauses are satisfied.
 *		However, there is an order of significance among the keys with
 *		the first keys being most significant. Therefore, the clauses
 *		are evaluated in order and the 'compareQual' is satisfied
 *		if (key1i > key2i) is true and (key1j = key2j) for 0 < j < i.
 *		We use the original mergeclause items to detect equality.
 * ----------------------------------------------------------------
 */
static bool
MergeCompare(List *eqQual, List *compareQual, ExprContext *econtext)
{
	List	   *clause;
	List	   *eqclause;
	Datum		const_value;
	bool		isNull;
	bool		isDone;

	/* ----------------
	 *	if we have no compare qualification, return nil
	 * ----------------
	 */
	if (compareQual == NIL)
		return false;

	/* ----------------
	 *	for each pair of clauses, test them until
	 *	our compare conditions are satisified
	 * ----------------
	 */
	eqclause = eqQual;
	foreach(clause, compareQual)
	{
		/* ----------------
		 *	 first test if our compare clause is satisified.
		 *	 if so then return true. ignore isDone, don't iterate in
		 *	 quals.
		 * ----------------
		 */
		const_value = (Datum)
			ExecEvalExpr((Node *) lfirst(clause), econtext, &isNull, &isDone);

		if (DatumGetInt32(const_value) != 0)
			return true;

		/* ----------------
		 *	 ok, the compare clause failed so we test if the keys
		 *	 are equal... if key1 != key2, we return false.
		 *	 otherwise key1 = key2 so we move on to the next pair of keys.
		 *
		 *	 ignore isDone, don't iterate in quals.
		 * ----------------
		 */
		const_value = ExecEvalExpr((Node *) lfirst(eqclause),
								   econtext,
								   &isNull,
								   &isDone);

		if (DatumGetInt32(const_value) == 0)
			return false;
		eqclause = lnext(eqclause);
	}

	/* ----------------
	 *	if we get here then it means none of our key greater-than
	 *	conditions were satisified so we return false.
	 * ----------------
	 */
	return false;
}

/* ----------------------------------------------------------------
 *		ExecMergeTupleDump
 *
 *		This function is called through the MJ_dump() macro
 *		when EXEC_MERGEJOINDEBUG is defined
 * ----------------------------------------------------------------
 */
#ifdef EXEC_MERGEJOINDEBUG
void
			ExecMergeTupleDumpInner(ExprContext *econtext);

void
ExecMergeTupleDumpInner(ExprContext *econtext)
{
	TupleTableSlot *innerSlot;

	printf("==== inner tuple ====\n");
	innerSlot = econtext->ecxt_innertuple;
	if (TupIsNull(innerSlot))
		printf("(nil)\n");
	else
		MJ_debugtup(innerSlot->val,
					innerSlot->ttc_tupleDescriptor);
}

void
			ExecMergeTupleDumpOuter(ExprContext *econtext);

void
ExecMergeTupleDumpOuter(ExprContext *econtext)
{
	TupleTableSlot *outerSlot;

	printf("==== outer tuple ====\n");
	outerSlot = econtext->ecxt_outertuple;
	if (TupIsNull(outerSlot))
		printf("(nil)\n");
	else
		MJ_debugtup(outerSlot->val,
					outerSlot->ttc_tupleDescriptor);
}

void ExecMergeTupleDumpMarked(ExprContext *econtext,
						 MergeJoinState *mergestate);

void
ExecMergeTupleDumpMarked(ExprContext *econtext,
						 MergeJoinState *mergestate)
{
	TupleTableSlot *markedSlot;

	printf("==== marked tuple ====\n");
	markedSlot = mergestate->mj_MarkedTupleSlot;

	if (TupIsNull(markedSlot))
		printf("(nil)\n");
	else
		MJ_debugtup(markedSlot->val,
					markedSlot->ttc_tupleDescriptor);
}

void
			ExecMergeTupleDump(ExprContext *econtext, MergeJoinState *mergestate);

void
ExecMergeTupleDump(ExprContext *econtext, MergeJoinState *mergestate)
{
	printf("******** ExecMergeTupleDump ********\n");

	ExecMergeTupleDumpInner(econtext);
	ExecMergeTupleDumpOuter(econtext);
	ExecMergeTupleDumpMarked(econtext, mergestate);

	printf("******** \n");
}

#endif

/* ----------------------------------------------------------------
 *		ExecMergeJoin
 *
 * old comments
 *		Details of the merge-join routines:
 *
 *		(1) ">" and "<" operators
 *
 *		Merge-join is done by joining the inner and outer tuples satisfying
 *		the join clauses of the form ((= outerKey innerKey) ...).
 *		The join clauses is provided by the query planner and may contain
 *		more than one (= outerKey innerKey) clauses (for composite key).
 *
 *		However, the query executor needs to know whether an outer
 *		tuple is "greater/smaller" than an inner tuple so that it can
 *		"synchronize" the two relations. For e.g., consider the following
 *		relations:
 *
 *				outer: (0 ^1 1 2 5 5 5 6 6 7)	current tuple: 1
 *				inner: (1 ^3 5 5 5 5 6)			current tuple: 3
 *
 *		To continue the merge-join, the executor needs to scan both inner
 *		and outer relations till the matching tuples 5. It needs to know
 *		that currently inner tuple 3 is "greater" than outer tuple 1 and
 *		therefore it should scan the outer relation first to find a
 *		matching tuple and so on.
 *
 *		Therefore, when initializing the merge-join node, the executor
 *		creates the "greater/smaller" clause by substituting the "="
 *		operator in the join clauses with the corresponding ">" operator.
 *		The opposite "smaller/greater" clause is formed by substituting "<".
 *
 *		Note: prior to v6.5, the relational clauses were formed using the
 *		sort op used to sort the inner relation, which of course would fail
 *		if the outer and inner keys were of different data types.
 *		In the current code, we instead assume that operators named "<" and ">"
 *		will do the right thing.  This should be true since the mergejoin "="
 *		operator's pg_operator entry will have told the planner to sort by
 *		"<" for each of the left and right sides.
 *
 *		(2) repositioning inner "cursor"
 *
 *		Consider the above relations and suppose that the executor has
 *		just joined the first outer "5" with the last inner "5". The
 *		next step is of course to join the second outer "5" with all
 *		the inner "5's". This requires repositioning the inner "cursor"
 *		to point at the first inner "5". This is done by "marking" the
 *		first inner 5 and restore the "cursor" to it before joining
 *		with the second outer 5. The access method interface provides
 *		routines to mark and restore to a tuple.
 * ----------------------------------------------------------------
 */
TupleTableSlot *
ExecMergeJoin(MergeJoin *node)
{
	EState	   *estate;
	MergeJoinState *mergestate;
	ScanDirection direction;
	List	   *innerSkipQual;
	List	   *outerSkipQual;
	List	   *mergeclauses;
	List	   *qual;
	bool		qualResult;
	bool		compareResult;

	Plan	   *innerPlan;
	TupleTableSlot *innerTupleSlot;

	Plan	   *outerPlan;
	TupleTableSlot *outerTupleSlot;

	ExprContext *econtext;

#ifdef ENABLE_OUTER_JOINS

	/*
	 * These should be set from the expression context! - thomas
	 * 1999-02-20
	 */
	static bool isLeftJoin = true;
	static bool isRightJoin = false;

#endif

	/* ----------------
	 *	get information from node
	 * ----------------
	 */
	mergestate = node->mergestate;
	estate = node->join.state;
	direction = estate->es_direction;
	innerPlan = innerPlan((Plan *) node);