diff options
Diffstat (limited to 'src/backend/executor/nodeMergejoin.c')
| -rw-r--r-- | src/backend/executor/nodeMergejoin.c | 1194 |
1 files changed, 1194 insertions, 0 deletions
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c new file mode 100644 index 00000000000..54a3aa28c4e --- /dev/null +++ b/src/backend/executor/nodeMergejoin.c @@ -0,0 +1,1194 @@ +/*------------------------------------------------------------------------- + * + * nodeMergejoin.c-- + * routines supporting merge joins + * + * Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $Header: /cvsroot/pgsql/src/backend/executor/nodeMergejoin.c,v 1.1.1.1 1996/07/09 06:21:27 scrappy 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 satisify 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 + * } - + * + * Currently, 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 + * + * Warning: This code is known to fail for inequality operations + * and is being redesigned. Specifically, = and > work + * but the logic is not correct for <. Since mergejoins + * are no better then nestloops for inequalitys, the planner + * should not plan them anyways. Alternatively, the + * planner could just exchange the inner/outer relations + * if it ever sees a <... -cim 7/1/90 + * + * Update: The executor tuple table has long since alleviated the + * problem described above -cim 4/23/91 + * + */ +#include "executor/executor.h" +#include "executor/nodeMergejoin.h" +#include "utils/lsyscache.h" + +/* ---------------------------------------------------------------- + * MarkInnerTuple and RestoreInnerTuple macros + * + * when we "mark" a tuple, we place a pointer to it + * in the marked tuple slot. now there are two pointers + * to this tuple and we don't want it to be freed until + * next time we mark a tuple, so we move the policy to + * the marked tuple slot and set the inner tuple slot policy + * to false. + * + * But, when we restore the inner tuple, the marked tuple + * retains the policy. Basically once a tuple is marked, it + * should only be freed when we mark another tuple. -cim 9/27/90 + * + * Note: now that we store buffers in the tuple table, + * we have to also increment buffer reference counts + * correctly whenever we propagate an additional pointer + * to a buffer item. Later, when ExecStoreTuple() is + * called again on this slot, the refcnt is decremented + * when the old tuple is replaced. + * ---------------------------------------------------------------- + */ +#define MarkInnerTuple(innerTupleSlot, mergestate) \ +{ \ + bool shouldFree; \ + shouldFree = ExecSetSlotPolicy(innerTupleSlot, false); \ + ExecStoreTuple(innerTupleSlot->val, \ + mergestate->mj_MarkedTupleSlot, \ + innerTupleSlot->ttc_buffer, \ + shouldFree); \ + ExecIncrSlotBufferRefcnt(innerTupleSlot); \ +} + +#define RestoreInnerTuple(innerTupleSlot, markedTupleSlot) \ + ExecStoreTuple(markedTupleSlot->val, \ + innerTupleSlot, \ + markedTupleSlot->ttc_buffer, \ + false); \ + ExecIncrSlotBufferRefcnt(innerTupleSlot) + +/* ---------------------------------------------------------------- + * MJFormOSortopI + * + * 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. + * + * old comments + * The 'qual' must be of the form: + * {(= outerkey1 innerkey1)(= outerkey2 innerkey2) ...} + * The "sortOp outerkey innerkey" is formed by substituting the "=" + * by "sortOp". + * ---------------------------------------------------------------- + */ +static List * +MJFormOSortopI(List *qualList, Oid sortOp) +{ + List *qualCopy; + List *qualcdr; + Expr *qual; + Oper *op; + + /* ---------------- + * 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(DEBUG, "MJFormOSortopI: op not an Oper!"); + return NIL; + } + + /* ---------------- + * change it's opid and since Op nodes now carry around a + * cached pointer to the associated op function, we have + * to make sure we invalidate this. Otherwise you get bizarre + * behavior when someone runs a mergejoin with _exec_repeat_ > 1 + * -cim 4/23/91 + * ---------------- + */ + op->opid = sortOp; + op->op_fcache = NULL; + } + + return qualCopy; +} + +/* ---------------------------------------------------------------- + * MJFormISortopO + * + * This does the same thing as MJFormOSortopI() except that + * it also reverses the expressions in the qualifications. + * For example: ((= expr1 expr2)) produces ((> expr2 expr1)) + * + * old comments + * The 'qual' must be of the form: + * {(= outerkey1 innerkey1) (= outerkey2 innerkey2) ...} + * The 'sortOp innerkey1 outerkey" is formed by substituting the "=" + * by "sortOp" and reversing the positions of the keys. + * ---------------------------------------------------------------- + */ +List * +MJFormISortopO(List *qualList, Oid sortOp) +{ + List *ISortopO; + List *qualcdr; + + /* ---------------- + * first generate OSortopI, a list of the form + * ((op outer inner) (op outer inner) ... ) + * ---------------- + */ + ISortopO = MJFormOSortopI(qualList, sortOp); + + /* ---------------- + * now swap the cadr and caddr of each qual to form ISortopO, + * ((op inner outer) (op inner outer) ... ) + * ---------------- + */ + foreach (qualcdr, ISortopO) { + Expr *qual; + List *inner; + List *outer; + qual = lfirst(qualcdr); + + inner = lfirst(qual->args); + outer = lfirst(lnext(qual->args)); + lfirst(qual->args) = outer; + lfirst(lnext(qual->args)) = inner; + } + + return ISortopO; +} + +/* ---------------------------------------------------------------- + * 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. + * ---------------------------------------------------------------- + */ +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 + * ---------------------------------------------------------------- + */ +void +ExecMergeTupleDumpInner(ExprContext *econtext) +{ + TupleTableSlot *innerSlot; + + printf("==== inner tuple ====\n"); + innerSlot = econtext->ecxt_innertuple; + if (TupIsNull(innerSlot)) + printf("(nil)\n"); + else + debugtup(innerSlot->val, + innerSlot->ttc_tupleDescriptor); +} + +void +ExecMergeTupleDumpOuter(ExprContext *econtext) +{ + TupleTableSlot *outerSlot; + + printf("==== outer tuple ====\n"); + outerSlot = econtext->ecxt_outertuple; + if (TupIsNull(outerSlot)) + printf("(nil)\n"); + else + debugtup(outerSlot->val, + outerSlot->ttc_tupleDescriptor); +} + +void +ExecMergeTupleDumpMarked(ExprContext *econtext, + MergeJoinState *mergestate) +{ + TupleTableSlot *markedSlot; + + printf("==== marked tuple ====\n"); + markedSlot = mergestate->mj_MarkedTupleSlot; + + if (TupIsNull(markedSlot)) + printf("(nil)\n"); + else + debugtup(markedSlot->val, + markedSlot->ttc_tupleDescriptor); +} + +void +ExecMergeTupleDump(ExprContext *econtext, MergeJoinState *mergestate) +{ + printf("******** ExecMergeTupleDump ********\n"); + + ExecMergeTupleDumpInner(econtext); + ExecMergeTupleDumpOuter(econtext); + ExecMergeTupleDumpMarked(econtext, mergestate); + + printf("******** \n"); +} + +/* ---------------------------------------------------------------- + * 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 sort operator used to + * sort the outer and inner relation forming (outerKey sortOp innerKey). + * The sort operator is "<" if the relations are in ascending order + * otherwise, it is ">" if the relations are in descending order. + * The opposite "smaller/greater" clause is formed by reversing the + * outer and inner keys forming (innerKey sortOp outerKey). + * + * (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; + + TupleTableSlot *markedTupleSlot; + + ExprContext *econtext; + + /* ---------------- + * get information from node + * ---------------- + */ + mergestate = node->mergestate; + estate = node->join.state; + direction = estate->es_direction; + innerPlan = innerPlan((Plan *)node); + outerPlan = outerPlan((Plan *)node); + econtext = mergestate->jstate.cs_ExprContext; + mergeclauses = node->mergeclauses; + qual = node->join.qual; + + if (ScanDirectionIsForward(direction)) { + outerSkipQual = mergestate->mj_OSortopI; + innerSkipQual = mergestate->mj_ISortopO; + } else { + outerSkipQual = mergestate->mj_ISortopO; + innerSkipQual = mergestate->mj_OSortopI; + } + + /* ---------------- + * ok, everything is setup.. let's go to work + * ---------------- + */ + if (mergestate->jstate.cs_TupFromTlist) { + TupleTableSlot *result; + ProjectionInfo *projInfo; + bool isDone; + + projInfo = mergestate->jstate.cs_ProjInfo; + result = ExecProject(projInfo, &isDone); + if (!isDone) + return result; + } + for (;;) { + /* ---------------- + * get the current state of the join and do things accordingly. + * Note: The join states are highlighted with 32-* comments for + * improved readability. + * ---------------- + */ + MJ_dump(econtext, mergestate); + + switch (mergestate->mj_JoinState) { + /* ******************************** + * EXEC_MJ_INITIALIZE means that this is the first time + * ExecMergeJoin() has been called and so we have to + * initialize the inner, outer and marked tuples as well + * as various stuff in the expression context. + * ******************************** + */ + case EXEC_MJ_INITIALIZE: + MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE\n"); + /* ---------------- + * Note: at this point, if either of our inner or outer + * tuples are nil, then the join ends immediately because + * we know one of the subplans is empty. + * ---------------- + */ + innerTupleSlot = ExecProcNode(innerPlan, (Plan*)node); + if (TupIsNull(innerTupleSlot)) { + MJ_printf("ExecMergeJoin: **** inner tuple is nil ****\n"); + return NULL; + } + + outerTupleSlot = ExecProcNode(outerPlan, (Plan*)node); + if (TupIsNull(outerTupleSlot)) { + MJ_printf("ExecMergeJoin: **** outer tuple is nil ****\n"); + return NULL; + } + + /* ---------------- + * store the inner and outer tuple in the merge state + * ---------------- + */ + econtext->ecxt_innertuple = innerTupleSlot; + econtext->ecxt_outertuple = outerTupleSlot; + + /* ---------------- + * set the marked tuple to nil + * and initialize its tuple descriptor atttributes. + * -jeff 10 july 1991 + * ---------------- + */ + ExecClearTuple(mergestate->mj_MarkedTupleSlot); + mergestate->mj_MarkedTupleSlot->ttc_tupleDescriptor = + innerTupleSlot->ttc_tupleDescriptor; +/* + mergestate->mj_MarkedTupleSlot->ttc_execTupDescriptor = + innerTupleSlot->ttc_execTupDescriptor; +*/ + /* ---------------- + * initialize merge join state to skip inner tuples. + * ---------------- + */ + mergestate->mj_JoinState = EXEC_MJ_SKIPINNER; + break; + + /* ******************************** + * EXEC_MJ_JOINMARK means we have just found a new + * outer tuple and a possible matching inner tuple. + * This is the case after the INITIALIZE, SKIPOUTER + * or SKIPINNER states. + * ******************************** + */ + case EXEC_MJ_JOINMARK: + MJ_printf("ExecMergeJoin: EXEC_MJ_JOINMARK\n"); + ExecMarkPos(innerPlan); + + innerTupleSlot = econtext->ecxt_innertuple; + MarkInnerTuple(innerTupleSlot, mergestate); + + mergestate->mj_JoinState = EXEC_MJ_JOINTEST; + break; + + /* ******************************** + * EXEC_MJ_JOINTEST means we have two tuples which + * might satisify the merge clause, so we test them. + * + * If they do satisify, then we join them and move + * on to the next inner tuple (EXEC_MJ_JOINTUPLES). + * + * If they do not satisify then advance to next outer tuple. + * ******************************** + */ + case EXEC_MJ_JOINTEST: + MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTEST\n"); + + qualResult = ExecQual((List*)mergeclauses, econtext); + MJ_DEBUG_QUAL(mergeclauses, qualResult); + + if (qualResult) + { + mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES; + } + else + { + mergestate->mj_JoinState = EXEC_MJ_NEXTOUTER; + } + break; + + /* ******************************** + * EXEC_MJ_JOINTUPLES means we have two tuples which + * satisified the merge clause so we join them and then + * proceed to get the next inner tuple (EXEC_NEXT_INNER). + * ******************************** + */ + case EXEC_MJ_JOINTUPLES: + MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n"); + mergestate->mj_JoinState = EXEC_MJ_NEXTINNER; + + qualResult = ExecQual((List*)qual, econtext); + MJ_DEBUG_QUAL(qual, qualResult); + + if (qualResult) { + /* ---------------- + * qualification succeeded. now form the desired + * projection tuple and return the slot containing it. + * ---------------- + */ + ProjectionInfo *projInfo; + TupleTableSlot *result; + bool isDone; + + MJ_printf("ExecMergeJoin: **** returning tuple ****\n"); + + projInfo = mergestate->jstate.cs_ProjInfo; + + result = ExecProject(projInfo, &isDone); + mergestate->jstate.cs_TupFromTlist = !isDone; + return result; + } + break; + + /* ******************************** + * EXEC_MJ_NEXTINNER means advance the inner scan + * to the next tuple. If the tuple is not nil, we then + * proceed to test it against the join qualification. + * ******************************** + */ + case EXEC_MJ_NEXTINNER: + MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n"); + + /* ---------------- + * now we get the next inner tuple, if any + * ---------------- + */ + innerTupleSlot = ExecProcNode(innerPlan, (Plan*)node); + MJ_DEBUG_PROC_NODE(innerTupleSlot); + econtext->ecxt_innertuple = innerTupleSlot; + + if (TupIsNull(innerTupleSlot)) + { + mergestate->mj_JoinState = EXEC_MJ_NEXTOUTER; + } + else + { + mergestate->mj_JoinState = EXEC_MJ_JOINTEST; + } + break; + + /* ******************************** + * EXEC_MJ_NEXTOUTER means + * + * outer inner + * outer tuple - 5 5 - marked tuple + * 5 5 + * 6 6 - inner tuple + * 7 7 + * + * we know we just bumped into + * the first inner tuple > current outer tuple + * so get a new outer tuple and then proceed to test + * it against the marked tuple (EXEC_MJ_TESTOUTER) + * ******************************** + */ + case EXEC_MJ_NEXTOUTER: + MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n"); + + outerTupleSlot = ExecProcNode(outerPlan, (Plan*)node); + MJ_DEBUG_PROC_NODE(outerTupleSlot); + econtext->ecxt_outertuple = outerTupleSlot; + + /* ---------------- + * if the outer tuple is null then we know + * we are done with the join + * ---------------- + */ + if (TupIsNull(outerTupleSlot)) { + MJ_printf("ExecMergeJoin: **** outer tuple is nil ****\n"); + return NULL; + } + + mergestate->mj_JoinState = EXEC_MJ_TESTOUTER; + break; + + /* ******************************** + * EXEC_MJ_TESTOUTER + * If the new outer tuple and the marked tuple satisify + * the merge clause then we know we have duplicates in + * the outer scan so we have to restore the inner scan + * to the marked tuple and proceed to join the new outer + * tuples with the inner tuples (EXEC_MJ_JOINTEST) + * + * This is the case when + * + * outer inner + * 4 5 - marked tuple + * outer tuple - 5 5 + * new outer tuple - 5 5 + * 6 8 - inner tuple + * 7 12 + * + * new outer tuple = marked tuple + * + * If the outer tuple fails the test, then we know we have + * to proceed to skip outer tuples until outer >= inner + * (EXEC_MJ_SKIPOUTER). + * + * This is the case when + * + * outer inner + * 5 5 - marked tuple + * outer tuple - 5 5 + * new outer tuple - 6 8 - inner tuple + * 7 12 + * + * new outer tuple > marked tuple + * + * ******************************** + */ + case EXEC_MJ_TESTOUTER: + MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n"); + + /* ---------------- + * here we compare the outer tuple with the marked inner tuple + * by using the marked tuple in place of the inner tuple. + * ---------------- + */ + innerTupleSlot = econtext->ecxt_innertuple; + markedTupleSlot = mergestate->mj_MarkedTupleSlot; + econtext->ecxt_innertuple = markedTupleSlot; + + qualResult = ExecQual((List*)mergeclauses, econtext); + MJ_DEBUG_QUAL(mergeclauses, qualResult); + + if (qualResult) { + /* ---------------- + * the merge clause matched so now we juggle the slots + * back the way they were and proceed to JOINTEST. + * ---------------- + */ + econtext->ecxt_innertuple = innerTupleSlot; + + RestoreInnerTuple(innerTupleSlot, markedTupleSlot); + + ExecRestrPos(innerPlan); + mergestate->mj_JoinState = EXEC_MJ_JOINTEST; + + } else { + /* ---------------- + * if the inner tuple was nil and the new outer + * tuple didn't match the marked outer tuple then + * we may have the case: + * + * outer inner + * 4 4 - marked tuple + * new outer - 5 4 + * 6 nil - inner tuple + * 7 + * + * which means that all subsequent outer tuples will be + * larger than our inner tuples. + * ---------------- + */ + if (TupIsNull(innerTupleSlot)) { + MJ_printf("ExecMergeJoin: **** wierd case 1 ****\n"); + return NULL; + } + + /* ---------------- + * restore the inner tuple and continue on to + * skip outer tuples. + * ---------------- + */ + econtext->ecxt_innertuple = innerTupleSlot; + mergestate->mj_JoinState = EXEC_MJ_SKIPOUTER; + } + break; + + /* ******************************** + * EXEC_MJ_SKIPOUTER means skip over tuples in the outer plan + * until we find an outer tuple > current inner tuple. + * + * For example: + * + * outer inner + * 5 5 + * 5 5 + * outer tuple - 6 8 - inner tuple + * 7 12 + * 8 14 + * + * we have to advance the outer scan + * until we find the outer 8. + * + * ******************************** + */ + case EXEC_MJ_SKIPOUTER: + MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER\n"); + /* ---------------- + * before we advance, make sure the current tuples + * do not satisify the mergeclauses. If they do, then + * we update the marked tuple and go join them. + * ---------------- + */ + qualResult = ExecQual((List*)mergeclauses, econtext); + MJ_DEBUG_QUAL(mergeclauses, qualResult); + + if (qualResult) { + ExecMarkPos(innerPlan); + innerTupleSlot = econtext->ecxt_innertuple; + + MarkInnerTuple(innerTupleSlot, mergestate); + + mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES; + break; + } + + /* ---------------- + * ok, now test the skip qualification + * ---------------- + */ + compareResult = MergeCompare(mergeclauses, + outerSkipQual, + econtext); + + MJ_DEBUG_MERGE_COMPARE(outerSkipQual, compareResult); + + /* ---------------- + * compareResult is true as long as we should + * continue skipping tuples. + * ---------------- + */ + if (compareResult) { + + outerTupleSlot = ExecProcNode(outerPlan, (Plan*)node); + MJ_DEBUG_PROC_NODE(outerTupleSlot); + econtext->ecxt_outertuple = outerTupleSlot; + + /* ---------------- + * if the outer tuple is null then we know + * we are done with the join + * ---------------- + */ + if (TupIsNull(outerTupleSlot)) { + MJ_printf("ExecMergeJoin: **** outerTuple is nil ****\n"); + return NULL; + } + /* ---------------- + * otherwise test the new tuple against the skip qual. + * (we remain in the EXEC_MJ_SKIPOUTER state) + * ---------------- + */ + break; + } + + /* ---------------- + * now check the inner skip qual to see if we + * should now skip inner tuples... if we fail the + * inner skip qual, then we know we have a new pair + * of matching tuples. + * ---------------- + */ + compareResult = MergeCompare(mergeclauses, + innerSkipQual, + econtext); + + MJ_DEBUG_MERGE_COMPARE(innerSkipQual, compareResult); + + if (compareResult) + { + mergestate->mj_JoinState = EXEC_MJ_SKIPINNER; + } + else + { + mergestate->mj_JoinState = EXEC_MJ_JOINMARK; + } + break; + + /* ******************************** + * EXEC_MJ_SKIPINNER means skip over tuples in the inner plan + * until we find an inner tuple > current outer tuple. + * + * For example: + * + * outer inner + * 5 5 + * 5 5 + * outer tuple - 12 8 - inner tuple + * 14 10 + * 17 12 + * + * we have to advance the inner scan + * until we find the inner 12. + * + * ******************************** + */ + case EXEC_MJ_SKIPINNER: + MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER\n"); + /* ---------------- + * before we advance, make sure the current tuples + * do not satisify the mergeclauses. If they do, then + * we update the marked tuple and go join them. + * ---------------- + */ + qualResult = ExecQual((List*)mergeclauses, econtext); + MJ_DEBUG_QUAL(mergeclauses, qualResult); + + if (qualResult) { + ExecMarkPos(innerPlan); + innerTupleSlot = econtext->ecxt_innertuple; + + MarkInnerTuple(innerTupleSlot, mergestate); + + mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES; + break; + } + + /* ---------------- + * ok, now test the skip qualification + * ---------------- + */ + compareResult = MergeCompare(mergeclauses, + innerSkipQual, + econtext); + + MJ_DEBUG_MERGE_COMPARE(innerSkipQual, compareResult); + + /* ---------------- + * compareResult is true as long as we should + * continue skipping tuples. + * ---------------- + */ + if (compareResult) { + /* ---------------- + * now try and get a new inner tuple + * ---------------- + */ + innerTupleSlot = ExecProcNode(innerPlan, (Plan*)node); + MJ_DEBUG_PROC_NODE(innerTupleSlot); + econtext->ecxt_innertuple = innerTupleSlot; + + /* ---------------- + * if the inner tuple is null then we know + * we have to restore the inner scan + * and advance to the next outer tuple + * ---------------- + */ + if (TupIsNull(innerTupleSlot)) { + /* ---------------- + * this is an interesting case.. all our + * inner tuples are smaller then our outer + * tuples so we never found an inner tuple + * to mark. + * + * outer inner + * outer tuple - 5 4 + * 5 4 + * 6 nil - inner tuple + * 7 + * + * This means the join should end. + * ---------------- + */ + MJ_printf("ExecMergeJoin: **** wierd case 2 ****\n"); + return NULL; + } + + /* ---------------- + * otherwise test the new tuple against the skip qual. + * (we remain in the EXEC_MJ_SKIPINNER state) + * ---------------- + */ + break; + } + + /* ---------------- + * compare finally failed and we have stopped skipping + * inner tuples so now check the outer skip qual + * to see if we should now skip outer tuples... + * ---------------- + */ + compareResult = MergeCompare(mergeclauses, + outerSkipQual, + econtext); + + MJ_DEBUG_MERGE_COMPARE(outerSkipQual, compareResult); + + if (compareResult) + { + mergestate->mj_JoinState = EXEC_MJ_SKIPOUTER; + } + else + { + mergestate->mj_JoinState = EXEC_MJ_JOINMARK; + } + + break; + + /* ******************************** + * if we get here it means our code is fucked up and + * so we just end the join prematurely. + * ******************************** + */ + default: + elog(NOTICE, "ExecMergeJoin: invalid join state. aborting"); + return NULL; + } + } +} + +/* ---------------------------------------------------------------- + * ExecInitMergeJoin + * + * old comments + * Creates the run-time state information for the node and + * sets the relation id to contain relevant decriptors. + * ---------------------------------------------------------------- + */ +bool +ExecInitMergeJoin(MergeJoin *node, EState *estate, Plan *parent) +{ + MergeJoinState *mergestate; + List *joinclauses; + RegProcedure rightsortop; + RegProcedure leftsortop; + RegProcedure sortop; + + List *OSortopI; + List *ISortopO; + + MJ1_printf("ExecInitMergeJoin: %s\n", + "initializing node"); + + /* ---------------- + * assign the node's execution state and + * get the range table and direction from it + * ---------------- + */ + node->join.state = estate; + + /* ---------------- + * create new merge state for node + * ---------------- + */ + mergestate = makeNode(MergeJoinState); + mergestate->mj_OSortopI = NIL; + mergestate->mj_ISortopO = NIL; + mergestate->mj_JoinState = 0; + mergestate->mj_MarkedTupleSlot = NULL; + node->mergestate = mergestate; + + /* ---------------- + * Miscellanious initialization + * + * + assign node's base_id + * + assign debugging hooks and + * + create expression context for node + * ---------------- + */ + ExecAssignNodeBaseInfo(estate, &mergestate->jstate, parent); + ExecAssignExprContext(estate, &mergestate->jstate); + +#define MERGEJOIN_NSLOTS 2 + /* ---------------- + * tuple table initialization + * ---------------- + */ + ExecInitResultTupleSlot(estate, &mergestate->jstate); + ExecInitMarkedTupleSlot(estate, mergestate); + + /* ---------------- + * get merge sort operators. + * + * XXX for now we assume all quals in the joinclauses were + * sorted with the same operator in both the inner and + * outer relations. -cim 11/2/89 + * ---------------- + */ + joinclauses = node->mergeclauses; + + rightsortop = get_opcode(node->mergerightorder[0]); + leftsortop = get_opcode(node->mergeleftorder[0]); + + if (leftsortop != rightsortop) + elog(NOTICE, "ExecInitMergeJoin: %s", + "left and right sortop's are unequal!"); + + sortop = rightsortop; + + /* ---------------- + * form merge skip qualifications + * + * XXX MJform routines need to be extended + * to take a list of sortops.. -cim 11/2/89 + * ---------------- + */ + OSortopI = MJFormOSortopI(joinclauses, sortop); + ISortopO = MJFormISortopO(joinclauses, sortop); + mergestate->mj_OSortopI = OSortopI; + mergestate->mj_ISortopO = ISortopO; + + MJ_printf("\nExecInitMergeJoin: OSortopI is "); + MJ_nodeDisplay(OSortopI); + MJ_printf("\nExecInitMergeJoin: ISortopO is "); + MJ_nodeDisplay(ISortopO); + MJ_printf("\n"); + + /* ---------------- + * initialize join state + * ---------------- + */ + mergestate->mj_JoinState = EXEC_MJ_INITIALIZE; + + /* ---------------- + * initialize subplans + * ---------------- + */ + ExecInitNode(outerPlan((Plan *) node), estate, (Plan *) node); + ExecInitNode(innerPlan((Plan *) node), estate, (Plan *) node); + + /* ---------------- + * initialize tuple type and projection info + * ---------------- + */ + ExecAssignResultTypeFromTL((Plan *) node, &mergestate->jstate); + ExecAssignProjectionInfo((Plan *) node, &mergestate->jstate); + + mergestate->jstate.cs_TupFromTlist = false; + /* ---------------- + * initialization successful + * ---------------- + */ + MJ1_printf("ExecInitMergeJoin: %s\n", + "node initialized"); + + return TRUE; +} + +int +ExecCountSlotsMergeJoin(MergeJoin *node) +{ + return ExecCountSlotsNode(outerPlan((Plan *)node)) + + ExecCountSlotsNode(innerPlan((Plan *)node)) + + MERGEJOIN_NSLOTS; +} + +/* ---------------------------------------------------------------- + * ExecEndMergeJoin + * + * old comments + * frees storage allocated through C routines. + * ---------------------------------------------------------------- + */ +void +ExecEndMergeJoin(MergeJoin *node) +{ + MergeJoinState *mergestate; + + MJ1_printf("ExecEndMergeJoin: %s\n", + "ending node processing"); + + /* ---------------- + * get state information from the node + * ---------------- + */ + mergestate = node->mergestate; + + /* ---------------- + * Free the projection info and the scan attribute info + * + * Note: we don't ExecFreeResultType(mergestate) + * because the rule manager depends on the tupType + * returned by ExecMain(). So for now, this + * is freed at end-transaction time. -cim 6/2/91 + * ---------------- + */ + ExecFreeProjectionInfo(&mergestate->jstate); + + /* ---------------- + * shut down the subplans + * ---------------- + */ + ExecEndNode((Plan*) innerPlan((Plan *) node), (Plan*)node); + ExecEndNode((Plan*) outerPlan((Plan *) node), (Plan*)node); + + /* ---------------- + * clean out the tuple table so that we don't try and + * pfree the marked tuples.. see HACK ALERT at the top of + * this file. + * ---------------- + */ + ExecClearTuple(mergestate->jstate.cs_ResultTupleSlot); + ExecClearTuple(mergestate->mj_MarkedTupleSlot); + + MJ1_printf("ExecEndMergeJoin: %s\n", + "node processing ended"); +} + |