1 /*-------------------------------------------------------------------------
4 * routines supporting merge joins
6 * Copyright (c) 1994, Regents of the University of California
10 * $Header: /cvsroot/pgsql/src/backend/executor/nodeMergejoin.c,v 1.32 1999/11/22 17:56:03 momjian Exp $
12 *-------------------------------------------------------------------------
16 * ExecMergeJoin mergejoin outer and inner relations.
17 * ExecInitMergeJoin creates and initializes run time states
18 * ExecEndMergeJoin cleand up the node.
21 * Essential operation of the merge join algorithm is as follows:
22 * (** indicates the tuples satisfy the merge clause).
25 * get initial outer and inner tuples INITIALIZE
26 * Skip Inner SKIPINNER
27 * mark inner position JOINMARK
29 * while (outer == inner) { JOINTEST
30 * join tuples JOINTUPLES
31 * advance inner position NEXTINNER
33 * advance outer position NEXTOUTER
34 * if (outer == mark) { TESTOUTER
35 * restore inner position to mark TESTOUTER
38 * Skip Outer SKIPOUTER
39 * mark inner position JOINMARK
44 * Skip Outer { SKIPOUTER
45 * if (inner == outer) Join Tuples JOINTUPLES
46 * while (outer < inner) SKIPOUTER
47 * advance outer SKIPOUTER
48 * if (outer > inner) SKIPOUTER
49 * Skip Inner SKIPINNER
52 * Skip Inner { SKIPINNER
53 * if (inner == outer) Join Tuples JOINTUPLES
54 * while (outer > inner) SKIPINNER
55 * advance inner SKIPINNER
56 * if (outer < inner) SKIPINNER
57 * Skip Outer SKIPOUTER
60 * The merge join operation is coded in the fashion
61 * of a state machine. At each state, we do something and then
62 * proceed to another state. This state is stored in the node's
63 * execution state information and is preserved across calls to
64 * ExecMergeJoin. -cim 10/31/89
69 #include "access/heapam.h"
70 #include "catalog/pg_operator.h"
71 #include "executor/execdebug.h"
72 #include "executor/execdefs.h"
73 #include "executor/executor.h"
74 #include "executor/nodeMergejoin.h"
75 #include "utils/lsyscache.h"
76 #include "utils/syscache.h"
79 static bool MergeCompare(List *eqQual, List *compareQual, ExprContext *econtext);
81 #define MarkInnerTuple(innerTupleSlot, mergestate) \
83 ExecStoreTuple(heap_copytuple((innerTupleSlot)->val), \
84 (mergestate)->mj_MarkedTupleSlot, \
90 /* ----------------------------------------------------------------
93 * This takes the mergeclause which is a qualification of the
94 * form ((= expr expr) (= expr expr) ...) and forms a new
95 * qualification like ((> expr expr) (> expr expr) ...) which
96 * is used by ExecMergeJoin() in order to determine if we should
97 * skip tuples. The replacement operators are named either ">"
98 * or "<" according to the replaceopname parameter, and have the
99 * same operand data types as the "=" operators they replace.
100 * (We expect there to be such operators because the "=" operators
101 * were marked mergejoinable; however, there might be a different
102 * one needed in each qual clause.)
103 * ----------------------------------------------------------------
106 MJFormSkipQual(List *qualList, char *replaceopname)
113 Form_pg_operator opform;
118 * qualList is a list: ((op .. ..) ...)
119 * first we make a copy of it. copyObject() makes a deep copy
120 * so let's use it instead of the old fashoned lispCopy()...
123 qualCopy = (List *) copyObject((Node *) qualList);
125 foreach(qualcdr, qualCopy)
128 * first get the current (op .. ..) list
131 qual = lfirst(qualcdr);
137 op = (Oper *) qual->oper;
139 elog(ERROR, "MJFormSkipQual: op not an Oper!");
142 * Get the declared left and right operand types of the operator.
143 * Note we do *not* use the actual operand types, since those might
144 * be different in scenarios with binary-compatible data types.
145 * There should be "<" and ">" operators matching a mergejoinable
146 * "=" operator's declared operand types, but we might not find them
147 * if we search with the actual operand types.
150 optup = get_operator_tuple(op->opno);
151 if (!HeapTupleIsValid(optup)) /* shouldn't happen */
152 elog(ERROR, "MJFormSkipQual: operator %u not found", op->opno);
153 opform = (Form_pg_operator) GETSTRUCT(optup);
154 oprleft = opform->oprleft;
155 oprright = opform->oprright;
158 * Now look up the matching "<" or ">" operator. If there isn't one,
159 * whoever marked the "=" operator mergejoinable was a loser.
162 optup = SearchSysCacheTuple(OPERNAME,
163 PointerGetDatum(replaceopname),
164 ObjectIdGetDatum(oprleft),
165 ObjectIdGetDatum(oprright),
167 if (!HeapTupleIsValid(optup))
169 "MJFormSkipQual: mergejoin operator %u has no matching %s op",
170 op->opno, replaceopname);
171 opform = (Form_pg_operator) GETSTRUCT(optup);
174 * And replace the data in the copied operator node.
177 op->opno = optup->t_data->t_oid;
178 op->opid = opform->oprcode;
179 op->op_fcache = NULL;
185 /* ----------------------------------------------------------------
188 * Compare the keys according to 'compareQual' which is of the
189 * form: {(key1a > key2a)(key1b > key2b) ...}.
191 * (actually, it could also be the form (key1a < key2a)..)
193 * This is different from calling ExecQual because ExecQual returns
194 * true only if ALL the comparisions clauses are satisfied.
195 * However, there is an order of significance among the keys with
196 * the first keys being most significant. Therefore, the clauses
197 * are evaluated in order and the 'compareQual' is satisfied
198 * if (key1i > key2i) is true and (key1j = key2j) for 0 < j < i.
199 * We use the original mergeclause items to detect equality.
200 * ----------------------------------------------------------------
203 MergeCompare(List *eqQual, List *compareQual, ExprContext *econtext)
212 * if we have no compare qualification, return nil
215 if (compareQual == NIL)
219 * for each pair of clauses, test them until
220 * our compare conditions are satisified
224 foreach(clause, compareQual)
227 * first test if our compare clause is satisified.
228 * if so then return true. ignore isDone, don't iterate in
232 const_value = (Datum)
233 ExecEvalExpr((Node *) lfirst(clause), econtext, &isNull, &isDone);
235 if (DatumGetInt32(const_value) != 0)
239 * ok, the compare clause failed so we test if the keys
240 * are equal... if key1 != key2, we return false.
241 * otherwise key1 = key2 so we move on to the next pair of keys.
243 * ignore isDone, don't iterate in quals.
246 const_value = ExecEvalExpr((Node *) lfirst(eqclause),
251 if (DatumGetInt32(const_value) == 0)
253 eqclause = lnext(eqclause);
257 * if we get here then it means none of our key greater-than
258 * conditions were satisified so we return false.
264 /* ----------------------------------------------------------------
267 * This function is called through the MJ_dump() macro
268 * when EXEC_MERGEJOINDEBUG is defined
269 * ----------------------------------------------------------------
271 #ifdef EXEC_MERGEJOINDEBUG
273 ExecMergeTupleDumpInner(ExprContext *econtext);
276 ExecMergeTupleDumpInner(ExprContext *econtext)
278 TupleTableSlot *innerSlot;
280 printf("==== inner tuple ====\n");
281 innerSlot = econtext->ecxt_innertuple;
282 if (TupIsNull(innerSlot))
285 MJ_debugtup(innerSlot->val,
286 innerSlot->ttc_tupleDescriptor);
290 ExecMergeTupleDumpOuter(ExprContext *econtext);
293 ExecMergeTupleDumpOuter(ExprContext *econtext)
295 TupleTableSlot *outerSlot;
297 printf("==== outer tuple ====\n");
298 outerSlot = econtext->ecxt_outertuple;
299 if (TupIsNull(outerSlot))
302 MJ_debugtup(outerSlot->val,
303 outerSlot->ttc_tupleDescriptor);
306 void ExecMergeTupleDumpMarked(ExprContext *econtext,
307 MergeJoinState *mergestate);
310 ExecMergeTupleDumpMarked(ExprContext *econtext,
311 MergeJoinState *mergestate)
313 TupleTableSlot *markedSlot;
315 printf("==== marked tuple ====\n");
316 markedSlot = mergestate->mj_MarkedTupleSlot;
318 if (TupIsNull(markedSlot))
321 MJ_debugtup(markedSlot->val,
322 markedSlot->ttc_tupleDescriptor);
326 ExecMergeTupleDump(ExprContext *econtext, MergeJoinState *mergestate);
329 ExecMergeTupleDump(ExprContext *econtext, MergeJoinState *mergestate)
331 printf("******** ExecMergeTupleDump ********\n");
333 ExecMergeTupleDumpInner(econtext);
334 ExecMergeTupleDumpOuter(econtext);
335 ExecMergeTupleDumpMarked(econtext, mergestate);
337 printf("******** \n");
342 /* ----------------------------------------------------------------
346 * Details of the merge-join routines:
348 * (1) ">" and "<" operators
350 * Merge-join is done by joining the inner and outer tuples satisfying
351 * the join clauses of the form ((= outerKey innerKey) ...).
352 * The join clauses is provided by the query planner and may contain
353 * more than one (= outerKey innerKey) clauses (for composite key).
355 * However, the query executor needs to know whether an outer
356 * tuple is "greater/smaller" than an inner tuple so that it can
357 * "synchronize" the two relations. For e.g., consider the following
360 * outer: (0 ^1 1 2 5 5 5 6 6 7) current tuple: 1
361 * inner: (1 ^3 5 5 5 5 6) current tuple: 3
363 * To continue the merge-join, the executor needs to scan both inner
364 * and outer relations till the matching tuples 5. It needs to know
365 * that currently inner tuple 3 is "greater" than outer tuple 1 and
366 * therefore it should scan the outer relation first to find a
367 * matching tuple and so on.
369 * Therefore, when initializing the merge-join node, the executor
370 * creates the "greater/smaller" clause by substituting the "="
371 * operator in the join clauses with the corresponding ">" operator.
372 * The opposite "smaller/greater" clause is formed by substituting "<".
374 * Note: prior to v6.5, the relational clauses were formed using the
375 * sort op used to sort the inner relation, which of course would fail
376 * if the outer and inner keys were of different data types.
377 * In the current code, we instead assume that operators named "<" and ">"
378 * will do the right thing. This should be true since the mergejoin "="
379 * operator's pg_operator entry will have told the planner to sort by
380 * "<" for each of the left and right sides.
382 * (2) repositioning inner "cursor"
384 * Consider the above relations and suppose that the executor has
385 * just joined the first outer "5" with the last inner "5". The
386 * next step is of course to join the second outer "5" with all
387 * the inner "5's". This requires repositioning the inner "cursor"
388 * to point at the first inner "5". This is done by "marking" the
389 * first inner 5 and restore the "cursor" to it before joining
390 * with the second outer 5. The access method interface provides
391 * routines to mark and restore to a tuple.
392 * ----------------------------------------------------------------
395 ExecMergeJoin(MergeJoin *node)
398 MergeJoinState *mergestate;
399 ScanDirection direction;
408 TupleTableSlot *innerTupleSlot;
411 TupleTableSlot *outerTupleSlot;
413 ExprContext *econtext;
415 #ifdef ENABLE_OUTER_JOINS
418 * These should be set from the expression context! - thomas
421 static bool isLeftJoin = true;
422 static bool isRightJoin = false;
427 * get information from node
430 mergestate = node->mergestate;
431 estate = node->join.state;
432 direction = estate->es_direction;
433 innerPlan = innerPlan((Plan *) node);
434 outerPlan = outerPlan((Plan *) node);
435 econtext = mergestate->jstate.cs_ExprContext;
436 mergeclauses = node->mergeclauses;
437 qual = node->join.qual;
439 if (ScanDirectionIsForward(direction))
441 outerSkipQual = mergestate->mj_OuterSkipQual;
442 innerSkipQual = mergestate->mj_InnerSkipQual;
446 outerSkipQual = mergestate->mj_InnerSkipQual;
447 innerSkipQual = mergestate->mj_OuterSkipQual;
451 * ok, everything is setup.. let's go to work
454 if (mergestate->jstate.cs_TupFromTlist)
456 TupleTableSlot *result;
457 ProjectionInfo *projInfo;
460 projInfo = mergestate->jstate.cs_ProjInfo;
461 result = ExecProject(projInfo, &isDone);
468 * get the current state of the join and do things accordingly.
469 * Note: The join states are highlighted with 32-* comments for
470 * improved readability.
473 MJ_dump(econtext, mergestate);
475 switch (mergestate->mj_JoinState)
479 * EXEC_MJ_INITIALIZE means that this is the first time
480 * ExecMergeJoin() has been called and so we have to
481 * initialize the inner, outer and marked tuples as well
482 * as various stuff in the expression context.
484 case EXEC_MJ_INITIALIZE:
485 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE\n");
488 * Note: at this point, if either of our inner or outer
489 * tuples are nil, then the join ends immediately because
490 * we know one of the subplans is empty.
492 innerTupleSlot = ExecProcNode(innerPlan, (Plan *) node);
493 if (TupIsNull(innerTupleSlot))
495 MJ_printf("ExecMergeJoin: **** inner tuple is nil ****\n");
499 outerTupleSlot = ExecProcNode(outerPlan, (Plan *) node);
500 if (TupIsNull(outerTupleSlot))
502 MJ_printf("ExecMergeJoin: **** outer tuple is nil ****\n");
507 * store the inner and outer tuple in the merge state
510 econtext->ecxt_innertuple = innerTupleSlot;
511 econtext->ecxt_outertuple = outerTupleSlot;
513 mergestate->mj_MarkedTupleSlot->ttc_tupleDescriptor =
514 innerTupleSlot->ttc_tupleDescriptor;
517 * initialize merge join state to skip inner tuples.
520 mergestate->mj_JoinState = EXEC_MJ_SKIPINNER;
524 * EXEC_MJ_JOINMARK means we have just found a new outer
525 * tuple and a possible matching inner tuple. This is the
526 * case after the INITIALIZE, SKIPOUTER or SKIPINNER
529 case EXEC_MJ_JOINMARK:
530 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINMARK\n");
531 ExecMarkPos(innerPlan);
533 MarkInnerTuple(econtext->ecxt_innertuple, mergestate);
535 mergestate->mj_JoinState = EXEC_MJ_JOINTEST;
539 * EXEC_MJ_JOINTEST means we have two tuples which might
540 * satisfy the merge clause, so we test them.
542 * If they do satisfy, then we join them and move on to the
543 * next inner tuple (EXEC_MJ_JOINTUPLES).
545 * If they do not satisfy then advance to next outer tuple.
547 case EXEC_MJ_JOINTEST:
548 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTEST\n");
550 qualResult = ExecQual((List *) mergeclauses, econtext);
551 MJ_DEBUG_QUAL(mergeclauses, qualResult);
554 mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES;
556 mergestate->mj_JoinState = EXEC_MJ_NEXTOUTER;
560 * EXEC_MJ_JOINTUPLES means we have two tuples which
561 * satisified the merge clause so we join them and then
562 * proceed to get the next inner tuple (EXEC_NEXT_INNER).
564 case EXEC_MJ_JOINTUPLES:
565 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n");
566 mergestate->mj_JoinState = EXEC_MJ_NEXTINNER;
568 qualResult = ExecQual((List *) qual, econtext);
569 MJ_DEBUG_QUAL(qual, qualResult);
574 * qualification succeeded. now form the desired
575 * projection tuple and return the slot containing it.
578 ProjectionInfo *projInfo;
579 TupleTableSlot *result;
582 MJ_printf("ExecMergeJoin: **** returning tuple ****\n");
584 projInfo = mergestate->jstate.cs_ProjInfo;
586 result = ExecProject(projInfo, &isDone);
587 mergestate->jstate.cs_TupFromTlist = !isDone;
593 * EXEC_MJ_NEXTINNER means advance the inner scan to the
594 * next tuple. If the tuple is not nil, we then proceed to
595 * test it against the join qualification.
597 case EXEC_MJ_NEXTINNER:
598 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n");
601 * now we get the next inner tuple, if any
604 innerTupleSlot = ExecProcNode(innerPlan, (Plan *) node);
605 MJ_DEBUG_PROC_NODE(innerTupleSlot);
606 econtext->ecxt_innertuple = innerTupleSlot;
608 if (TupIsNull(innerTupleSlot))
609 mergestate->mj_JoinState = EXEC_MJ_NEXTOUTER;
611 mergestate->mj_JoinState = EXEC_MJ_JOINTEST;
614 /*-------------------------------------------
615 * EXEC_MJ_NEXTOUTER means
618 * outer tuple - 5 5 - marked tuple
623 * we know we just bumped into the
624 * first inner tuple > current outer tuple
625 * so get a new outer tuple and then
626 * proceed to test it against the marked tuple
627 * (EXEC_MJ_TESTOUTER)
628 *------------------------------------------------
630 case EXEC_MJ_NEXTOUTER:
631 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n");
633 outerTupleSlot = ExecProcNode(outerPlan, (Plan *) node);
634 MJ_DEBUG_PROC_NODE(outerTupleSlot);
635 econtext->ecxt_outertuple = outerTupleSlot;
638 * if the outer tuple is null then we know
639 * we are done with the join
642 if (TupIsNull(outerTupleSlot))
644 MJ_printf("ExecMergeJoin: **** outer tuple is nil ****\n");
648 mergestate->mj_JoinState = EXEC_MJ_TESTOUTER;
651 /*--------------------------------------------------------
652 * EXEC_MJ_TESTOUTER If the new outer tuple and the marked
653 * tuple satisfy the merge clause then we know we have
654 * duplicates in the outer scan so we have to restore the
655 * inner scan to the marked tuple and proceed to join the
656 * new outer tuples with the inner tuples (EXEC_MJ_JOINTEST)
658 * This is the case when
662 * new outer tuple - 5 5
666 * new outer tuple = marked tuple
668 * If the outer tuple fails the test, then we know we have
669 * to proceed to skip outer tuples until outer >= inner
670 * (EXEC_MJ_SKIPOUTER).
672 * This is the case when
677 * new outer tuple - 6 8 - inner tuple
681 * new outer tuple > marked tuple
683 *---------------------------------------------------------
685 case EXEC_MJ_TESTOUTER:
686 MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
689 * here we compare the outer tuple with the marked inner tuple
690 * by using the marked tuple in place of the inner tuple.
693 innerTupleSlot = econtext->ecxt_innertuple;
694 econtext->ecxt_innertuple = mergestate->mj_MarkedTupleSlot;
696 qualResult = ExecQual((List *) mergeclauses, econtext);
697 MJ_DEBUG_QUAL(mergeclauses, qualResult);
703 * the merge clause matched so now we juggle the slots
704 * back the way they were and proceed to JOINTEST.
706 * I can't understand why we have to go to JOINTEST and
707 * compare outer tuple with the same inner one again
708 * -> go to JOINTUPLES... - vadim 02/27/98
711 ExecRestrPos(innerPlan);
713 mergestate->mj_JoinState = EXEC_MJ_JOINTEST;
715 mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES;
720 econtext->ecxt_innertuple = innerTupleSlot;
722 * if the inner tuple was nil and the new outer
723 * tuple didn't match the marked outer tuple then
724 * we may have the case:
729 * 6 nil - inner tuple
732 * which means that all subsequent outer tuples will be
733 * larger than our inner tuples.
736 if (TupIsNull(innerTupleSlot))
738 #ifdef ENABLE_OUTER_JOINS
741 /* continue on to null fill outer tuples */
742 mergestate->mj_JoinState = EXEC_MJ_FILLOUTER;
746 MJ_printf("ExecMergeJoin: **** weird case 1 ****\n");
750 /* continue on to skip outer tuples */
751 mergestate->mj_JoinState = EXEC_MJ_SKIPOUTER;
755 /*----------------------------------------------------------
756 * EXEC_MJ_SKIPOUTER means skip over tuples in the outer plan
757 * until we find an outer tuple > current inner tuple.
764 * outer tuple - 6 8 - inner tuple
768 * we have to advance the outer scan
769 * until we find the outer 8.
770 *----------------------------------------------------------
772 case EXEC_MJ_SKIPOUTER:
773 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER\n");
775 * before we advance, make sure the current tuples
776 * do not satisfy the mergeclauses. If they do, then
777 * we update the marked tuple and go join them.
780 qualResult = ExecQual((List *) mergeclauses, econtext);
781 MJ_DEBUG_QUAL(mergeclauses, qualResult);
785 ExecMarkPos(innerPlan);
787 MarkInnerTuple(econtext->ecxt_innertuple, mergestate);
789 mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES;
794 * ok, now test the skip qualification
797 compareResult = MergeCompare(mergeclauses,
801 MJ_DEBUG_MERGE_COMPARE(outerSkipQual, compareResult);
804 * compareResult is true as long as we should
805 * continue skipping tuples.
810 #ifdef ENABLE_OUTER_JOINS
812 * if this is a left or full outer join, then fill
817 mergestate->mj_JoinState = EXEC_MJ_FILLOUTER;
822 outerTupleSlot = ExecProcNode(outerPlan, (Plan *) node);
823 MJ_DEBUG_PROC_NODE(outerTupleSlot);
824 econtext->ecxt_outertuple = outerTupleSlot;
827 * if the outer tuple is null then we know
828 * we are done with the join
831 if (TupIsNull(outerTupleSlot))
833 MJ_printf("ExecMergeJoin: **** outerTuple is nil ****\n");
837 * otherwise test the new tuple against the skip qual.
838 * (we remain in the EXEC_MJ_SKIPOUTER state)
845 * now check the inner skip qual to see if we
846 * should now skip inner tuples... if we fail the
847 * inner skip qual, then we know we have a new pair
848 * of matching tuples.
851 compareResult = MergeCompare(mergeclauses,
855 MJ_DEBUG_MERGE_COMPARE(innerSkipQual, compareResult);
858 mergestate->mj_JoinState = EXEC_MJ_SKIPINNER;
860 mergestate->mj_JoinState = EXEC_MJ_JOINMARK;
863 /*-----------------------------------------------------------
864 * EXEC_MJ_SKIPINNER means skip over tuples in the inner plan
865 * until we find an inner tuple > current outer tuple.
872 * outer tuple - 12 8 - inner tuple
876 * we have to advance the inner scan
877 * until we find the inner 12.
879 *-------------------------------------------------------
881 case EXEC_MJ_SKIPINNER:
882 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER\n");
884 * before we advance, make sure the current tuples
885 * do not satisfy the mergeclauses. If they do, then
886 * we update the marked tuple and go join them.
889 qualResult = ExecQual((List *) mergeclauses, econtext);
890 MJ_DEBUG_QUAL(mergeclauses, qualResult);
894 ExecMarkPos(innerPlan);
896 MarkInnerTuple(econtext->ecxt_innertuple, mergestate);
898 mergestate->mj_JoinState = EXEC_MJ_JOINTUPLES;
903 * ok, now test the skip qualification
906 compareResult = MergeCompare(mergeclauses,
910 MJ_DEBUG_MERGE_COMPARE(innerSkipQual, compareResult);
913 * compareResult is true as long as we should
914 * continue skipping tuples.
919 #ifdef ENABLE_OUTER_JOINS
921 * if this is a right or full outer join, then fill
926 mergestate->mj_JoinState = EXEC_MJ_FILLINNER;
932 * now try and get a new inner tuple
935 innerTupleSlot = ExecProcNode(innerPlan, (Plan *) node);
936 MJ_DEBUG_PROC_NODE(innerTupleSlot);
937 econtext->ecxt_innertuple = innerTupleSlot;
940 * if the inner tuple is null then we know
941 * we have to restore the inner scan
942 * and advance to the next outer tuple
945 if (TupIsNull(innerTupleSlot))
948 * this is an interesting case.. all our
949 * inner tuples are smaller then our outer
950 * tuples so we never found an inner tuple
956 * 6 nil - inner tuple
959 * This means the join should end.
962 MJ_printf("ExecMergeJoin: **** weird case 2 ****\n");
967 * otherwise test the new tuple against the skip qual.
968 * (we remain in the EXEC_MJ_SKIPINNER state)
975 * compare finally failed and we have stopped skipping
976 * inner tuples so now check the outer skip qual
977 * to see if we should now skip outer tuples...
980 compareResult = MergeCompare(mergeclauses,
984 MJ_DEBUG_MERGE_COMPARE(outerSkipQual, compareResult);
987 mergestate->mj_JoinState = EXEC_MJ_SKIPOUTER;
989 mergestate->mj_JoinState = EXEC_MJ_JOINMARK;
993 #ifdef ENABLE_OUTER_JOINS
996 * EXEC_MJ_FILLINNER means we have an unmatched inner
997 * tuple which must be null-expanded into the projection
998 * tuple. get the next inner tuple and reset markers
999 * (EXEC_MJ_JOINMARK).
1001 case EXEC_MJ_FILLINNER:
1002 MJ_printf("ExecMergeJoin: EXEC_MJ_FILLINNER\n");
1003 mergestate->mj_JoinState = EXEC_MJ_JOINMARK;
1006 * project the inner tuple into the result
1009 MJ_printf("ExecMergeJoin: project inner tuple into the result (not yet implemented)\n");
1012 * now skip this inner tuple
1015 innerTupleSlot = ExecProcNode(innerPlan, (Plan *) node);
1016 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1017 econtext->ecxt_innertuple = innerTupleSlot;
1020 * if the inner tuple is null then we know
1021 * we have to restore the inner scan
1022 * and advance to the next outer tuple
1025 if (TupIsNull(innerTupleSlot))
1027 if (isLeftJoin && !TupIsNull(outerTupleSlot))
1029 mergestate->mj_JoinState = EXEC_MJ_FILLOUTER;
1030 MJ_printf("ExecMergeJoin: try to complete outer fill\n");
1034 MJ_printf("ExecMergeJoin: **** weird case 2 ****\n");
1039 * otherwise test the new tuple against the skip qual.
1040 * (we move to the EXEC_MJ_JOINMARK state)
1046 * EXEC_MJ_FILLOUTER means we have an unmatched outer
1047 * tuple which must be null-expanded into the projection
1048 * tuple. get the next outer tuple and reset markers
1049 * (EXEC_MJ_JOINMARK).
1051 case EXEC_MJ_FILLOUTER:
1052 MJ_printf("ExecMergeJoin: EXEC_MJ_FILLOUTER\n");
1053 mergestate->mj_JoinState = EXEC_MJ_JOINMARK;
1056 * project the outer tuple into the result
1059 MJ_printf("ExecMergeJoin: project outer tuple into the result (not yet implemented)\n");
1062 * now skip this outer tuple
1065 outerTupleSlot = ExecProcNode(outerPlan, (Plan *) node);
1066 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1067 econtext->ecxt_outertuple = outerTupleSlot;
1070 * if the outer tuple is null then we know
1071 * we are done with the left half of the join
1074 if (TupIsNull(outerTupleSlot))
1076 if (isRightJoin && !TupIsNull(innerTupleSlot))
1078 mergestate->mj_JoinState = EXEC_MJ_FILLINNER;
1079 MJ_printf("ExecMergeJoin: try to complete inner fill\n");
1083 MJ_printf("ExecMergeJoin: **** outerTuple is nil ****\n");
1088 * otherwise test the new tuple against the skip qual.
1089 * (we move to the EXEC_MJ_JOINMARK state)
1096 * if we get here it means our code is fouled up and so we
1097 * just end the join prematurely.
1100 elog(NOTICE, "ExecMergeJoin: invalid join state. aborting");
1106 /* ----------------------------------------------------------------
1110 * Creates the run-time state information for the node and
1111 * sets the relation id to contain relevant decriptors.
1112 * ----------------------------------------------------------------
1115 ExecInitMergeJoin(MergeJoin *node, EState *estate, Plan *parent)
1117 MergeJoinState *mergestate;
1119 TupleTableSlot *mjSlot;
1121 MJ1_printf("ExecInitMergeJoin: %s\n",
1122 "initializing node");
1125 * assign the node's execution state and
1126 * get the range table and direction from it
1129 node->join.state = estate;
1132 * create new merge state for node
1135 mergestate = makeNode(MergeJoinState);
1136 mergestate->mj_OuterSkipQual = NIL;
1137 mergestate->mj_InnerSkipQual = NIL;
1138 mergestate->mj_JoinState = 0;
1139 mergestate->mj_MarkedTupleSlot = NULL;
1140 node->mergestate = mergestate;
1143 * Miscellaneous initialization
1145 * + assign node's base_id
1146 * + assign debugging hooks and
1147 * + create expression context for node
1150 ExecAssignNodeBaseInfo(estate, &mergestate->jstate, parent);
1151 ExecAssignExprContext(estate, &mergestate->jstate);
1153 #define MERGEJOIN_NSLOTS 2
1155 * tuple table initialization
1157 * XXX why aren't we getting a tuple table slot in the normal way?
1160 ExecInitResultTupleSlot(estate, &mergestate->jstate);
1161 mjSlot = makeNode(TupleTableSlot);
1163 mjSlot->ttc_shouldFree = true;
1164 mjSlot->ttc_descIsNew = true;
1165 mjSlot->ttc_tupleDescriptor = NULL;
1166 mjSlot->ttc_buffer = InvalidBuffer;
1167 mjSlot->ttc_whichplan = -1;
1168 mergestate->mj_MarkedTupleSlot = mjSlot;
1171 * form merge skip qualifications
1174 joinclauses = node->mergeclauses;
1175 mergestate->mj_OuterSkipQual = MJFormSkipQual(joinclauses, "<");
1176 mergestate->mj_InnerSkipQual = MJFormSkipQual(joinclauses, ">");
1178 MJ_printf("\nExecInitMergeJoin: OuterSkipQual is ");
1179 MJ_nodeDisplay(mergestate->mj_OuterSkipQual);
1180 MJ_printf("\nExecInitMergeJoin: InnerSkipQual is ");
1181 MJ_nodeDisplay(mergestate->mj_InnerSkipQual);
1185 * initialize join state
1188 mergestate->mj_JoinState = EXEC_MJ_INITIALIZE;
1191 * initialize subplans
1194 ExecInitNode(outerPlan((Plan *) node), estate, (Plan *) node);
1195 ExecInitNode(innerPlan((Plan *) node), estate, (Plan *) node);
1198 * initialize tuple type and projection info
1201 ExecAssignResultTypeFromTL((Plan *) node, &mergestate->jstate);
1202 ExecAssignProjectionInfo((Plan *) node, &mergestate->jstate);
1204 mergestate->jstate.cs_TupFromTlist = false;
1206 * initialization successful
1209 MJ1_printf("ExecInitMergeJoin: %s\n",
1210 "node initialized");
1216 ExecCountSlotsMergeJoin(MergeJoin *node)
1218 return ExecCountSlotsNode(outerPlan((Plan *) node)) +
1219 ExecCountSlotsNode(innerPlan((Plan *) node)) +
1223 /* ----------------------------------------------------------------
1227 * frees storage allocated through C routines.
1228 * ----------------------------------------------------------------
1231 ExecEndMergeJoin(MergeJoin *node)
1233 MergeJoinState *mergestate;
1235 MJ1_printf("ExecEndMergeJoin: %s\n",
1236 "ending node processing");
1239 * get state information from the node
1242 mergestate = node->mergestate;
1245 * Free the projection info and the scan attribute info
1247 * Note: we don't ExecFreeResultType(mergestate)
1248 * because the rule manager depends on the tupType
1249 * returned by ExecMain(). So for now, this
1250 * is freed at end-transaction time. -cim 6/2/91
1253 ExecFreeProjectionInfo(&mergestate->jstate);
1256 * shut down the subplans
1259 ExecEndNode((Plan *) innerPlan((Plan *) node), (Plan *) node);
1260 ExecEndNode((Plan *) outerPlan((Plan *) node), (Plan *) node);
1263 * clean out the tuple table so that we don't try and
1264 * pfree the marked tuples.. see HACK ALERT at the top of
1268 ExecClearTuple(mergestate->jstate.cs_ResultTupleSlot);
1269 ExecClearTuple(mergestate->mj_MarkedTupleSlot);
1270 pfree(mergestate->mj_MarkedTupleSlot);
1271 mergestate->mj_MarkedTupleSlot = NULL;
1273 MJ1_printf("ExecEndMergeJoin: %s\n",
1274 "node processing ended");
1278 ExecReScanMergeJoin(MergeJoin *node, ExprContext *exprCtxt, Plan *parent)
1280 MergeJoinState *mergestate = node->mergestate;
1281 TupleTableSlot *mjSlot = mergestate->mj_MarkedTupleSlot;
1283 ExecClearTuple(mjSlot);
1284 mjSlot->ttc_tupleDescriptor = NULL;
1285 mjSlot->ttc_descIsNew = true;
1286 mjSlot->ttc_whichplan = -1;
1288 mergestate->mj_JoinState = EXEC_MJ_INITIALIZE;
1291 * if chgParam of subnodes is not null then plans will be re-scanned
1292 * by first ExecProcNode.
1294 if (((Plan *) node)->lefttree->chgParam == NULL)
1295 ExecReScan(((Plan *) node)->lefttree, exprCtxt, (Plan *) node);
1296 if (((Plan *) node)->righttree->chgParam == NULL)
1297 ExecReScan(((Plan *) node)->righttree, exprCtxt, (Plan *) node);