1 /*-------------------------------------------------------------------------
4 * routines supporting merge joins
6 * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/executor/nodeMergejoin.c,v 1.84 2007/01/05 22:19:28 momjian Exp $
13 *-------------------------------------------------------------------------
17 * ExecMergeJoin mergejoin outer and inner relations.
18 * ExecInitMergeJoin creates and initializes run time states
19 * ExecEndMergeJoin cleans up the node.
23 * Merge-join is done by joining the inner and outer tuples satisfying
24 * join clauses of the form ((= outerKey innerKey) ...).
25 * The join clause list is provided by the query planner and may contain
26 * more than one (= outerKey innerKey) clause (for composite sort key).
28 * However, the query executor needs to know whether an outer
29 * tuple is "greater/smaller" than an inner tuple so that it can
30 * "synchronize" the two relations. For example, consider the following
33 * outer: (0 ^1 1 2 5 5 5 6 6 7) current tuple: 1
34 * inner: (1 ^3 5 5 5 5 6) current tuple: 3
36 * To continue the merge-join, the executor needs to scan both inner
37 * and outer relations till the matching tuples 5. It needs to know
38 * that currently inner tuple 3 is "greater" than outer tuple 1 and
39 * therefore it should scan the outer relation first to find a
40 * matching tuple and so on.
42 * Therefore, when initializing the merge-join node, we look up the
43 * associated sort operators. We assume the planner has seen to it
44 * that the inputs are correctly sorted by these operators. Rather
45 * than directly executing the merge join clauses, we evaluate the
46 * left and right key expressions separately and then compare the
47 * columns one at a time (see MJCompare).
50 * Consider the above relations and suppose that the executor has
51 * just joined the first outer "5" with the last inner "5". The
52 * next step is of course to join the second outer "5" with all
53 * the inner "5's". This requires repositioning the inner "cursor"
54 * to point at the first inner "5". This is done by "marking" the
55 * first inner 5 so we can restore the "cursor" to it before joining
56 * with the second outer 5. The access method interface provides
57 * routines to mark and restore to a tuple.
60 * Essential operation of the merge join algorithm is as follows:
63 * get initial outer and inner tuples INITIALIZE
65 * while (outer != inner) { SKIP_TEST
67 * advance outer SKIPOUTER_ADVANCE
69 * advance inner SKIPINNER_ADVANCE
71 * mark inner position SKIP_TEST
73 * while (outer == inner) {
74 * join tuples JOINTUPLES
75 * advance inner position NEXTINNER
77 * advance outer position NEXTOUTER
78 * if (outer == mark) TESTOUTER
79 * restore inner position to mark TESTOUTER
81 * break // return to top of outer loop
86 * The merge join operation is coded in the fashion
87 * of a state machine. At each state, we do something and then
88 * proceed to another state. This state is stored in the node's
89 * execution state information and is preserved across calls to
90 * ExecMergeJoin. -cim 10/31/89
94 #include "access/nbtree.h"
95 #include "catalog/pg_amop.h"
96 #include "executor/execdebug.h"
97 #include "executor/execdefs.h"
98 #include "executor/nodeMergejoin.h"
99 #include "miscadmin.h"
100 #include "utils/acl.h"
101 #include "utils/lsyscache.h"
102 #include "utils/memutils.h"
103 #include "utils/syscache.h"
107 * Comparison strategies supported by MJCompare
109 * XXX eventually should extend MJCompare to support descending-order sorts.
110 * There are some tricky issues however about being sure we are on the same
111 * page as the underlying sort or index as to which end NULLs sort to.
115 MERGEFUNC_CMP, /* -1 / 0 / 1 three-way comparator */
116 MERGEFUNC_REV_CMP /* same, reversing the sense of the result */
119 /* Runtime data for each mergejoin clause */
120 typedef struct MergeJoinClauseData
122 /* Executable expression trees */
123 ExprState *lexpr; /* left-hand (outer) input expression */
124 ExprState *rexpr; /* right-hand (inner) input expression */
127 * If we have a current left or right input tuple, the values of the
128 * expressions are loaded into these fields:
130 Datum ldatum; /* current left-hand value */
131 Datum rdatum; /* current right-hand value */
132 bool lisnull; /* and their isnull flags */
136 * The comparison strategy in use, and the lookup info to let us call the
137 * btree comparison support function.
139 MergeFunctionKind cmpstrategy;
141 } MergeJoinClauseData;
144 #define MarkInnerTuple(innerTupleSlot, mergestate) \
145 ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
151 * This deconstructs the list of mergejoinable expressions, which is given
152 * to us by the planner in the form of a list of "leftexpr = rightexpr"
153 * expression trees in the order matching the sort columns of the inputs.
154 * We build an array of MergeJoinClause structs containing the information
155 * we will need at runtime. Each struct essentially tells us how to compare
156 * the two expressions from the original clause.
158 * In addition to the expressions themselves, the planner passes the btree
159 * opfamily OID and btree strategy number (BTLessStrategyNumber or
160 * BTGreaterStrategyNumber) that identify the intended merge semantics for
161 * each merge key. The mergejoinable operator is an equality operator in
162 * this opfamily, and the two inputs are guaranteed to be ordered in either
163 * increasing or decreasing (respectively) order according to this opfamily.
164 * This allows us to obtain the needed comparison functions from the opfamily.
166 static MergeJoinClause
167 MJExamineQuals(List *mergeclauses, List *mergefamilies, List *mergestrategies,
170 MergeJoinClause clauses;
171 int nClauses = list_length(mergeclauses);
177 clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
180 cf = list_head(mergefamilies);
181 cs = list_head(mergestrategies);
182 foreach(cl, mergeclauses)
184 OpExpr *qual = (OpExpr *) lfirst(cl);
185 MergeJoinClause clause = &clauses[iClause];
187 StrategyNumber opstrategy;
192 RegProcedure cmpproc;
195 opfamily = lfirst_oid(cf);
197 opstrategy = lfirst_int(cs);
200 /* Later we'll support both ascending and descending sort... */
201 Assert(opstrategy == BTLessStrategyNumber);
202 clause->cmpstrategy = MERGEFUNC_CMP;
204 if (!IsA(qual, OpExpr))
205 elog(ERROR, "mergejoin clause is not an OpExpr");
208 * Prepare the input expressions for execution.
210 clause->lexpr = ExecInitExpr((Expr *) linitial(qual->args), parent);
211 clause->rexpr = ExecInitExpr((Expr *) lsecond(qual->args), parent);
213 /* Extract the operator's declared left/right datatypes */
214 get_op_opfamily_properties(qual->opno, opfamily,
219 Assert(op_strategy == BTEqualStrategyNumber);
222 /* And get the matching support procedure (comparison function) */
223 cmpproc = get_opfamily_proc(opfamily,
227 Assert(RegProcedureIsValid(cmpproc));
229 /* Check permission to call cmp function */
230 aclresult = pg_proc_aclcheck(cmpproc, GetUserId(), ACL_EXECUTE);
231 if (aclresult != ACLCHECK_OK)
232 aclcheck_error(aclresult, ACL_KIND_PROC,
233 get_func_name(cmpproc));
235 /* Set up the fmgr lookup information */
236 fmgr_info(cmpproc, &(clause->cmpfinfo));
247 * Compute the values of the mergejoined expressions for the current
248 * outer tuple. We also detect whether it's impossible for the current
249 * outer tuple to match anything --- this is true if it yields a NULL
250 * input, since we assume mergejoin operators are strict.
252 * We evaluate the values in OuterEContext, which can be reset each
253 * time we move to a new tuple.
256 MJEvalOuterValues(MergeJoinState *mergestate)
258 ExprContext *econtext = mergestate->mj_OuterEContext;
259 bool canmatch = true;
261 MemoryContext oldContext;
263 ResetExprContext(econtext);
265 oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
267 econtext->ecxt_outertuple = mergestate->mj_OuterTupleSlot;
269 for (i = 0; i < mergestate->mj_NumClauses; i++)
271 MergeJoinClause clause = &mergestate->mj_Clauses[i];
273 clause->ldatum = ExecEvalExpr(clause->lexpr, econtext,
274 &clause->lisnull, NULL);
279 MemoryContextSwitchTo(oldContext);
287 * Same as above, but for the inner tuple. Here, we have to be prepared
288 * to load data from either the true current inner, or the marked inner,
289 * so caller must tell us which slot to load from.
292 MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
294 ExprContext *econtext = mergestate->mj_InnerEContext;
295 bool canmatch = true;
297 MemoryContext oldContext;
299 ResetExprContext(econtext);
301 oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
303 econtext->ecxt_innertuple = innerslot;
305 for (i = 0; i < mergestate->mj_NumClauses; i++)
307 MergeJoinClause clause = &mergestate->mj_Clauses[i];
309 clause->rdatum = ExecEvalExpr(clause->rexpr, econtext,
310 &clause->risnull, NULL);
315 MemoryContextSwitchTo(oldContext);
323 * Compare the mergejoinable values of the current two input tuples
324 * and return 0 if they are equal (ie, the mergejoin equalities all
325 * succeed), +1 if outer > inner, -1 if outer < inner.
327 * MJEvalOuterValues and MJEvalInnerValues must already have been called
328 * for the current outer and inner tuples, respectively.
331 MJCompare(MergeJoinState *mergestate)
334 bool nulleqnull = false;
335 ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
337 MemoryContext oldContext;
338 FunctionCallInfoData fcinfo;
341 * Call the comparison functions in short-lived context, in case they leak
344 ResetExprContext(econtext);
346 oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
348 for (i = 0; i < mergestate->mj_NumClauses; i++)
350 MergeJoinClause clause = &mergestate->mj_Clauses[i];
354 * Deal with null inputs. We treat NULL as sorting after non-NULL.
363 /* NULL > non-NULL */
369 /* non-NULL < NULL */
374 InitFunctionCallInfoData(fcinfo, &(clause->cmpfinfo), 2,
376 fcinfo.arg[0] = clause->ldatum;
377 fcinfo.arg[1] = clause->rdatum;
378 fcinfo.argnull[0] = false;
379 fcinfo.argnull[1] = false;
380 fresult = FunctionCallInvoke(&fcinfo);
386 if (DatumGetInt32(fresult) == 0)
391 if (clause->cmpstrategy == MERGEFUNC_CMP)
393 if (DatumGetInt32(fresult) < 0)
408 /* reverse the sort order */
409 if (DatumGetInt32(fresult) > 0)
425 * If we had any null comparison results or NULL-vs-NULL inputs, we do not
426 * want to report that the tuples are equal. Instead, if result is still
427 * 0, change it to +1. This will result in advancing the inner side of
430 if (nulleqnull && result == 0)
433 MemoryContextSwitchTo(oldContext);
440 * Generate a fake join tuple with nulls for the inner tuple,
441 * and return it if it passes the non-join quals.
443 static TupleTableSlot *
444 MJFillOuter(MergeJoinState *node)
446 ExprContext *econtext = node->js.ps.ps_ExprContext;
447 List *otherqual = node->js.ps.qual;
449 ResetExprContext(econtext);
451 econtext->ecxt_outertuple = node->mj_OuterTupleSlot;
452 econtext->ecxt_innertuple = node->mj_NullInnerTupleSlot;
454 if (ExecQual(otherqual, econtext, false))
457 * qualification succeeded. now form the desired projection tuple and
458 * return the slot containing it.
460 TupleTableSlot *result;
463 MJ_printf("ExecMergeJoin: returning outer fill tuple\n");
465 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
467 if (isDone != ExprEndResult)
469 node->js.ps.ps_TupFromTlist =
470 (isDone == ExprMultipleResult);
479 * Generate a fake join tuple with nulls for the outer tuple,
480 * and return it if it passes the non-join quals.
482 static TupleTableSlot *
483 MJFillInner(MergeJoinState *node)
485 ExprContext *econtext = node->js.ps.ps_ExprContext;
486 List *otherqual = node->js.ps.qual;
488 ResetExprContext(econtext);
490 econtext->ecxt_outertuple = node->mj_NullOuterTupleSlot;
491 econtext->ecxt_innertuple = node->mj_InnerTupleSlot;
493 if (ExecQual(otherqual, econtext, false))
496 * qualification succeeded. now form the desired projection tuple and
497 * return the slot containing it.
499 TupleTableSlot *result;
502 MJ_printf("ExecMergeJoin: returning inner fill tuple\n");
504 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
506 if (isDone != ExprEndResult)
508 node->js.ps.ps_TupFromTlist =
509 (isDone == ExprMultipleResult);
518 /* ----------------------------------------------------------------
521 * This function is called through the MJ_dump() macro
522 * when EXEC_MERGEJOINDEBUG is defined
523 * ----------------------------------------------------------------
525 #ifdef EXEC_MERGEJOINDEBUG
528 ExecMergeTupleDumpOuter(MergeJoinState *mergestate)
530 TupleTableSlot *outerSlot = mergestate->mj_OuterTupleSlot;
532 printf("==== outer tuple ====\n");
533 if (TupIsNull(outerSlot))
536 MJ_debugtup(outerSlot);
540 ExecMergeTupleDumpInner(MergeJoinState *mergestate)
542 TupleTableSlot *innerSlot = mergestate->mj_InnerTupleSlot;
544 printf("==== inner tuple ====\n");
545 if (TupIsNull(innerSlot))
548 MJ_debugtup(innerSlot);
552 ExecMergeTupleDumpMarked(MergeJoinState *mergestate)
554 TupleTableSlot *markedSlot = mergestate->mj_MarkedTupleSlot;
556 printf("==== marked tuple ====\n");
557 if (TupIsNull(markedSlot))
560 MJ_debugtup(markedSlot);
564 ExecMergeTupleDump(MergeJoinState *mergestate)
566 printf("******** ExecMergeTupleDump ********\n");
568 ExecMergeTupleDumpOuter(mergestate);
569 ExecMergeTupleDumpInner(mergestate);
570 ExecMergeTupleDumpMarked(mergestate);
572 printf("******** \n");
576 /* ----------------------------------------------------------------
578 * ----------------------------------------------------------------
581 ExecMergeJoin(MergeJoinState *node)
588 PlanState *innerPlan;
589 TupleTableSlot *innerTupleSlot;
590 PlanState *outerPlan;
591 TupleTableSlot *outerTupleSlot;
592 ExprContext *econtext;
597 * get information from node
599 estate = node->js.ps.state;
600 innerPlan = innerPlanState(node);
601 outerPlan = outerPlanState(node);
602 econtext = node->js.ps.ps_ExprContext;
603 joinqual = node->js.joinqual;
604 otherqual = node->js.ps.qual;
605 doFillOuter = node->mj_FillOuter;
606 doFillInner = node->mj_FillInner;
609 * Check to see if we're still projecting out tuples from a previous join
610 * tuple (because there is a function-returning-set in the projection
611 * expressions). If so, try to project another one.
613 if (node->js.ps.ps_TupFromTlist)
615 TupleTableSlot *result;
618 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
619 if (isDone == ExprMultipleResult)
621 /* Done with that source tuple... */
622 node->js.ps.ps_TupFromTlist = false;
626 * Reset per-tuple memory context to free any expression evaluation
627 * storage allocated in the previous tuple cycle. Note this can't happen
628 * until we're done projecting out tuples from a join tuple.
630 ResetExprContext(econtext);
633 * ok, everything is setup.. let's go to work
640 * get the current state of the join and do things accordingly.
642 switch (node->mj_JoinState)
645 * EXEC_MJ_INITIALIZE_OUTER means that this is the first time
646 * ExecMergeJoin() has been called and so we have to fetch the
647 * first matchable tuple for both outer and inner subplans. We
648 * do the outer side in INITIALIZE_OUTER state, then advance
649 * to INITIALIZE_INNER state for the inner subplan.
651 case EXEC_MJ_INITIALIZE_OUTER:
652 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_OUTER\n");
654 outerTupleSlot = ExecProcNode(outerPlan);
655 node->mj_OuterTupleSlot = outerTupleSlot;
656 if (TupIsNull(outerTupleSlot))
658 MJ_printf("ExecMergeJoin: nothing in outer subplan\n");
662 * Need to emit right-join tuples for remaining inner
663 * tuples. We set MatchedInner = true to force the
664 * ENDOUTER state to advance inner.
666 node->mj_JoinState = EXEC_MJ_ENDOUTER;
667 node->mj_MatchedInner = true;
670 /* Otherwise we're done. */
674 /* Compute join values and check for unmatchability */
675 if (MJEvalOuterValues(node))
677 /* OK to go get the first inner tuple */
678 node->mj_JoinState = EXEC_MJ_INITIALIZE_INNER;
682 /* Stay in same state to fetch next outer tuple */
686 * Generate a fake join tuple with nulls for the inner
687 * tuple, and return it if it passes the non-join
690 TupleTableSlot *result;
692 result = MJFillOuter(node);
699 case EXEC_MJ_INITIALIZE_INNER:
700 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_INNER\n");
702 innerTupleSlot = ExecProcNode(innerPlan);
703 node->mj_InnerTupleSlot = innerTupleSlot;
704 if (TupIsNull(innerTupleSlot))
706 MJ_printf("ExecMergeJoin: nothing in inner subplan\n");
710 * Need to emit left-join tuples for all outer tuples,
711 * including the one we just fetched. We set
712 * MatchedOuter = false to force the ENDINNER state to
713 * emit first tuple before advancing outer.
715 node->mj_JoinState = EXEC_MJ_ENDINNER;
716 node->mj_MatchedOuter = false;
719 /* Otherwise we're done. */
723 /* Compute join values and check for unmatchability */
724 if (MJEvalInnerValues(node, innerTupleSlot))
727 * OK, we have the initial tuples. Begin by skipping
728 * non-matching tuples.
730 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
734 /* Stay in same state to fetch next inner tuple */
738 * Generate a fake join tuple with nulls for the outer
739 * tuple, and return it if it passes the non-join
742 TupleTableSlot *result;
744 result = MJFillInner(node);
752 * EXEC_MJ_JOINTUPLES means we have two tuples which satisfied
753 * the merge clause so we join them and then proceed to get
754 * the next inner tuple (EXEC_MJ_NEXTINNER).
756 case EXEC_MJ_JOINTUPLES:
757 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n");
760 * Set the next state machine state. The right things will
761 * happen whether we return this join tuple or just fall
762 * through to continue the state machine execution.
764 node->mj_JoinState = EXEC_MJ_NEXTINNER;
767 * Check the extra qual conditions to see if we actually want
768 * to return this join tuple. If not, can proceed with merge.
769 * We must distinguish the additional joinquals (which must
770 * pass to consider the tuples "matched" for outer-join logic)
771 * from the otherquals (which must pass before we actually
774 * We don't bother with a ResetExprContext here, on the
775 * assumption that we just did one while checking the merge
776 * qual. One per tuple should be sufficient. We do have to
777 * set up the econtext links to the tuples for ExecQual to
780 outerTupleSlot = node->mj_OuterTupleSlot;
781 econtext->ecxt_outertuple = outerTupleSlot;
782 innerTupleSlot = node->mj_InnerTupleSlot;
783 econtext->ecxt_innertuple = innerTupleSlot;
785 if (node->js.jointype == JOIN_IN &&
786 node->mj_MatchedOuter)
790 qualResult = (joinqual == NIL ||
791 ExecQual(joinqual, econtext, false));
792 MJ_DEBUG_QUAL(joinqual, qualResult);
797 node->mj_MatchedOuter = true;
798 node->mj_MatchedInner = true;
800 qualResult = (otherqual == NIL ||
801 ExecQual(otherqual, econtext, false));
802 MJ_DEBUG_QUAL(otherqual, qualResult);
807 * qualification succeeded. now form the desired
808 * projection tuple and return the slot containing it.
810 TupleTableSlot *result;
813 MJ_printf("ExecMergeJoin: returning tuple\n");
815 result = ExecProject(node->js.ps.ps_ProjInfo,
818 if (isDone != ExprEndResult)
820 node->js.ps.ps_TupFromTlist =
821 (isDone == ExprMultipleResult);
829 * EXEC_MJ_NEXTINNER means advance the inner scan to the next
830 * tuple. If the tuple is not nil, we then proceed to test it
831 * against the join qualification.
833 * Before advancing, we check to see if we must emit an
834 * outer-join fill tuple for this inner tuple.
836 case EXEC_MJ_NEXTINNER:
837 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n");
839 if (doFillInner && !node->mj_MatchedInner)
842 * Generate a fake join tuple with nulls for the outer
843 * tuple, and return it if it passes the non-join quals.
845 TupleTableSlot *result;
847 node->mj_MatchedInner = true; /* do it only once */
849 result = MJFillInner(node);
855 * now we get the next inner tuple, if any. If there's none,
856 * advance to next outer tuple (which may be able to join to
857 * previously marked tuples).
859 innerTupleSlot = ExecProcNode(innerPlan);
860 node->mj_InnerTupleSlot = innerTupleSlot;
861 MJ_DEBUG_PROC_NODE(innerTupleSlot);
862 node->mj_MatchedInner = false;
864 if (TupIsNull(innerTupleSlot))
866 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
871 * Load up the new inner tuple's comparison values. If we see
872 * that it contains a NULL and hence can't match any outer
873 * tuple, we can skip the comparison and assume the new tuple
874 * is greater than current outer.
876 if (!MJEvalInnerValues(node, innerTupleSlot))
878 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
883 * Test the new inner tuple to see if it matches outer.
885 * If they do match, then we join them and move on to the next
886 * inner tuple (EXEC_MJ_JOINTUPLES).
888 * If they do not match then advance to next outer tuple.
890 compareResult = MJCompare(node);
891 MJ_DEBUG_COMPARE(compareResult);
893 if (compareResult == 0)
894 node->mj_JoinState = EXEC_MJ_JOINTUPLES;
897 Assert(compareResult < 0);
898 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
902 /*-------------------------------------------
903 * EXEC_MJ_NEXTOUTER means
906 * outer tuple - 5 5 - marked tuple
911 * we know we just bumped into the
912 * first inner tuple > current outer tuple (or possibly
913 * the end of the inner stream)
914 * so get a new outer tuple and then
915 * proceed to test it against the marked tuple
916 * (EXEC_MJ_TESTOUTER)
918 * Before advancing, we check to see if we must emit an
919 * outer-join fill tuple for this outer tuple.
920 *------------------------------------------------
922 case EXEC_MJ_NEXTOUTER:
923 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n");
925 if (doFillOuter && !node->mj_MatchedOuter)
928 * Generate a fake join tuple with nulls for the inner
929 * tuple, and return it if it passes the non-join quals.
931 TupleTableSlot *result;
933 node->mj_MatchedOuter = true; /* do it only once */
935 result = MJFillOuter(node);
941 * now we get the next outer tuple, if any
943 outerTupleSlot = ExecProcNode(outerPlan);
944 node->mj_OuterTupleSlot = outerTupleSlot;
945 MJ_DEBUG_PROC_NODE(outerTupleSlot);
946 node->mj_MatchedOuter = false;
949 * if the outer tuple is null then we are done with the join,
950 * unless we have inner tuples we need to null-fill.
952 if (TupIsNull(outerTupleSlot))
954 MJ_printf("ExecMergeJoin: end of outer subplan\n");
955 innerTupleSlot = node->mj_InnerTupleSlot;
956 if (doFillInner && !TupIsNull(innerTupleSlot))
959 * Need to emit right-join tuples for remaining inner
962 node->mj_JoinState = EXEC_MJ_ENDOUTER;
965 /* Otherwise we're done. */
969 /* Compute join values and check for unmatchability */
970 if (MJEvalOuterValues(node))
972 /* Go test the new tuple against the marked tuple */
973 node->mj_JoinState = EXEC_MJ_TESTOUTER;
977 /* Can't match, so fetch next outer tuple */
978 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
982 /*--------------------------------------------------------
983 * EXEC_MJ_TESTOUTER If the new outer tuple and the marked
984 * tuple satisfy the merge clause then we know we have
985 * duplicates in the outer scan so we have to restore the
986 * inner scan to the marked tuple and proceed to join the
987 * new outer tuple with the inner tuples.
989 * This is the case when
993 * new outer tuple - 5 5
997 * new outer tuple == marked tuple
999 * If the outer tuple fails the test, then we are done
1000 * with the marked tuples, and we have to look for a
1001 * match to the current inner tuple. So we will
1002 * proceed to skip outer tuples until outer >= inner
1003 * (EXEC_MJ_SKIP_TEST).
1005 * This is the case when
1008 * 5 5 - marked tuple
1010 * new outer tuple - 6 8 - inner tuple
1013 * new outer tuple > marked tuple
1015 *---------------------------------------------------------
1017 case EXEC_MJ_TESTOUTER:
1018 MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
1021 * Here we must compare the outer tuple with the marked inner
1022 * tuple. (We can ignore the result of MJEvalInnerValues,
1023 * since the marked inner tuple is certainly matchable.)
1025 innerTupleSlot = node->mj_MarkedTupleSlot;
1026 (void) MJEvalInnerValues(node, innerTupleSlot);
1028 compareResult = MJCompare(node);
1029 MJ_DEBUG_COMPARE(compareResult);
1031 if (compareResult == 0)
1034 * the merge clause matched so now we restore the inner
1035 * scan position to the first mark, and go join that tuple
1036 * (and any following ones) to the new outer.
1038 * NOTE: we do not need to worry about the MatchedInner
1039 * state for the rescanned inner tuples. We know all of
1040 * them will match this new outer tuple and therefore
1041 * won't be emitted as fill tuples. This works *only*
1042 * because we require the extra joinquals to be nil when
1043 * doing a right or full join --- otherwise some of the
1044 * rescanned tuples might fail the extra joinquals.
1046 ExecRestrPos(innerPlan);
1049 * ExecRestrPos probably should give us back a new Slot,
1050 * but since it doesn't, use the marked slot. (The
1051 * previously returned mj_InnerTupleSlot cannot be assumed
1052 * to hold the required tuple.)
1054 node->mj_InnerTupleSlot = innerTupleSlot;
1055 /* we need not do MJEvalInnerValues again */
1057 node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1062 * if the new outer tuple didn't match the marked inner
1063 * tuple then we have a case like:
1066 * 4 4 - marked tuple
1071 * which means that all subsequent outer tuples will be
1072 * larger than our marked inner tuples. So we need not
1073 * revisit any of the marked tuples but can proceed to
1074 * look for a match to the current inner. If there's
1075 * no more inners, we are done.
1078 Assert(compareResult > 0);
1079 innerTupleSlot = node->mj_InnerTupleSlot;
1080 if (TupIsNull(innerTupleSlot))
1085 * Need to emit left-join tuples for remaining
1088 node->mj_JoinState = EXEC_MJ_ENDINNER;
1091 /* Otherwise we're done. */
1095 /* reload comparison data for current inner */
1096 if (MJEvalInnerValues(node, innerTupleSlot))
1098 /* proceed to compare it to the current outer */
1099 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1104 * current inner can't possibly match any outer;
1105 * better to advance the inner scan than the outer.
1107 node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1112 /*----------------------------------------------------------
1113 * EXEC_MJ_SKIP means compare tuples and if they do not
1114 * match, skip whichever is lesser.
1121 * outer tuple - 6 8 - inner tuple
1125 * we have to advance the outer scan
1126 * until we find the outer 8.
1128 * On the other hand:
1133 * outer tuple - 12 8 - inner tuple
1137 * we have to advance the inner scan
1138 * until we find the inner 12.
1139 *----------------------------------------------------------
1141 case EXEC_MJ_SKIP_TEST:
1142 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIP_TEST\n");
1145 * before we advance, make sure the current tuples do not
1146 * satisfy the mergeclauses. If they do, then we update the
1147 * marked tuple position and go join them.
1149 compareResult = MJCompare(node);
1150 MJ_DEBUG_COMPARE(compareResult);
1152 if (compareResult == 0)
1154 ExecMarkPos(innerPlan);
1156 MarkInnerTuple(node->mj_InnerTupleSlot, node);
1158 node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1160 else if (compareResult < 0)
1161 node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
1163 /* compareResult > 0 */
1164 node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1168 * Before advancing, we check to see if we must emit an
1169 * outer-join fill tuple for this outer tuple.
1171 case EXEC_MJ_SKIPOUTER_ADVANCE:
1172 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_ADVANCE\n");
1174 if (doFillOuter && !node->mj_MatchedOuter)
1177 * Generate a fake join tuple with nulls for the inner
1178 * tuple, and return it if it passes the non-join quals.
1180 TupleTableSlot *result;
1182 node->mj_MatchedOuter = true; /* do it only once */
1184 result = MJFillOuter(node);
1190 * now we get the next outer tuple, if any
1192 outerTupleSlot = ExecProcNode(outerPlan);
1193 node->mj_OuterTupleSlot = outerTupleSlot;
1194 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1195 node->mj_MatchedOuter = false;
1198 * if the outer tuple is null then we are done with the join,
1199 * unless we have inner tuples we need to null-fill.
1201 if (TupIsNull(outerTupleSlot))
1203 MJ_printf("ExecMergeJoin: end of outer subplan\n");
1204 innerTupleSlot = node->mj_InnerTupleSlot;
1205 if (doFillInner && !TupIsNull(innerTupleSlot))
1208 * Need to emit right-join tuples for remaining inner
1211 node->mj_JoinState = EXEC_MJ_ENDOUTER;
1214 /* Otherwise we're done. */
1218 /* Compute join values and check for unmatchability */
1219 if (MJEvalOuterValues(node))
1221 /* Go test the new tuple against the current inner */
1222 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1226 /* Can't match, so fetch next outer tuple */
1227 node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
1232 * Before advancing, we check to see if we must emit an
1233 * outer-join fill tuple for this inner tuple.
1235 case EXEC_MJ_SKIPINNER_ADVANCE:
1236 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_ADVANCE\n");
1238 if (doFillInner && !node->mj_MatchedInner)
1241 * Generate a fake join tuple with nulls for the outer
1242 * tuple, and return it if it passes the non-join quals.
1244 TupleTableSlot *result;
1246 node->mj_MatchedInner = true; /* do it only once */
1248 result = MJFillInner(node);
1254 * now we get the next inner tuple, if any
1256 innerTupleSlot = ExecProcNode(innerPlan);
1257 node->mj_InnerTupleSlot = innerTupleSlot;
1258 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1259 node->mj_MatchedInner = false;
1262 * if the inner tuple is null then we are done with the join,
1263 * unless we have outer tuples we need to null-fill.
1265 if (TupIsNull(innerTupleSlot))
1267 MJ_printf("ExecMergeJoin: end of inner subplan\n");
1268 outerTupleSlot = node->mj_OuterTupleSlot;
1269 if (doFillOuter && !TupIsNull(outerTupleSlot))
1272 * Need to emit left-join tuples for remaining outer
1275 node->mj_JoinState = EXEC_MJ_ENDINNER;
1278 /* Otherwise we're done. */
1282 /* Compute join values and check for unmatchability */
1283 if (MJEvalInnerValues(node, innerTupleSlot))
1285 /* proceed to compare it to the current outer */
1286 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1291 * current inner can't possibly match any outer; better to
1292 * advance the inner scan than the outer.
1294 node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1299 * EXEC_MJ_ENDOUTER means we have run out of outer tuples, but
1300 * are doing a right/full join and therefore must null-fill
1301 * any remaing unmatched inner tuples.
1303 case EXEC_MJ_ENDOUTER:
1304 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDOUTER\n");
1306 Assert(doFillInner);
1308 if (!node->mj_MatchedInner)
1311 * Generate a fake join tuple with nulls for the outer
1312 * tuple, and return it if it passes the non-join quals.
1314 TupleTableSlot *result;
1316 node->mj_MatchedInner = true; /* do it only once */
1318 result = MJFillInner(node);
1324 * now we get the next inner tuple, if any
1326 innerTupleSlot = ExecProcNode(innerPlan);
1327 node->mj_InnerTupleSlot = innerTupleSlot;
1328 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1329 node->mj_MatchedInner = false;
1331 if (TupIsNull(innerTupleSlot))
1333 MJ_printf("ExecMergeJoin: end of inner subplan\n");
1337 /* Else remain in ENDOUTER state and process next tuple. */
1341 * EXEC_MJ_ENDINNER means we have run out of inner tuples, but
1342 * are doing a left/full join and therefore must null- fill
1343 * any remaing unmatched outer tuples.
1345 case EXEC_MJ_ENDINNER:
1346 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDINNER\n");
1348 Assert(doFillOuter);
1350 if (!node->mj_MatchedOuter)
1353 * Generate a fake join tuple with nulls for the inner
1354 * tuple, and return it if it passes the non-join quals.
1356 TupleTableSlot *result;
1358 node->mj_MatchedOuter = true; /* do it only once */
1360 result = MJFillOuter(node);
1366 * now we get the next outer tuple, if any
1368 outerTupleSlot = ExecProcNode(outerPlan);
1369 node->mj_OuterTupleSlot = outerTupleSlot;
1370 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1371 node->mj_MatchedOuter = false;
1373 if (TupIsNull(outerTupleSlot))
1375 MJ_printf("ExecMergeJoin: end of outer subplan\n");
1379 /* Else remain in ENDINNER state and process next tuple. */
1383 * broken state value?
1386 elog(ERROR, "unrecognized mergejoin state: %d",
1387 (int) node->mj_JoinState);
1392 /* ----------------------------------------------------------------
1394 * ----------------------------------------------------------------
1397 ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
1399 MergeJoinState *mergestate;
1401 /* check for unsupported flags */
1402 Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
1404 MJ1_printf("ExecInitMergeJoin: %s\n",
1405 "initializing node");
1408 * create state structure
1410 mergestate = makeNode(MergeJoinState);
1411 mergestate->js.ps.plan = (Plan *) node;
1412 mergestate->js.ps.state = estate;
1415 * Miscellaneous initialization
1417 * create expression context for node
1419 ExecAssignExprContext(estate, &mergestate->js.ps);
1422 * we need two additional econtexts in which we can compute the join
1423 * expressions from the left and right input tuples. The node's regular
1424 * econtext won't do because it gets reset too often.
1426 mergestate->mj_OuterEContext = CreateExprContext(estate);
1427 mergestate->mj_InnerEContext = CreateExprContext(estate);
1430 * initialize child expressions
1432 mergestate->js.ps.targetlist = (List *)
1433 ExecInitExpr((Expr *) node->join.plan.targetlist,
1434 (PlanState *) mergestate);
1435 mergestate->js.ps.qual = (List *)
1436 ExecInitExpr((Expr *) node->join.plan.qual,
1437 (PlanState *) mergestate);
1438 mergestate->js.jointype = node->join.jointype;
1439 mergestate->js.joinqual = (List *)
1440 ExecInitExpr((Expr *) node->join.joinqual,
1441 (PlanState *) mergestate);
1442 /* mergeclauses are handled below */
1445 * initialize child nodes
1447 * inner child must support MARK/RESTORE.
1449 outerPlanState(mergestate) = ExecInitNode(outerPlan(node), estate, eflags);
1450 innerPlanState(mergestate) = ExecInitNode(innerPlan(node), estate,
1451 eflags | EXEC_FLAG_MARK);
1453 #define MERGEJOIN_NSLOTS 4
1456 * tuple table initialization
1458 ExecInitResultTupleSlot(estate, &mergestate->js.ps);
1460 mergestate->mj_MarkedTupleSlot = ExecInitExtraTupleSlot(estate);
1461 ExecSetSlotDescriptor(mergestate->mj_MarkedTupleSlot,
1462 ExecGetResultType(innerPlanState(mergestate)));
1464 switch (node->join.jointype)
1468 mergestate->mj_FillOuter = false;
1469 mergestate->mj_FillInner = false;
1472 mergestate->mj_FillOuter = true;
1473 mergestate->mj_FillInner = false;
1474 mergestate->mj_NullInnerTupleSlot =
1475 ExecInitNullTupleSlot(estate,
1476 ExecGetResultType(innerPlanState(mergestate)));
1479 mergestate->mj_FillOuter = false;
1480 mergestate->mj_FillInner = true;
1481 mergestate->mj_NullOuterTupleSlot =
1482 ExecInitNullTupleSlot(estate,
1483 ExecGetResultType(outerPlanState(mergestate)));
1486 * Can't handle right or full join with non-nil extra joinclauses.
1487 * This should have been caught by planner.
1489 if (node->join.joinqual != NIL)
1491 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1492 errmsg("RIGHT JOIN is only supported with merge-joinable join conditions")));
1495 mergestate->mj_FillOuter = true;
1496 mergestate->mj_FillInner = true;
1497 mergestate->mj_NullOuterTupleSlot =
1498 ExecInitNullTupleSlot(estate,
1499 ExecGetResultType(outerPlanState(mergestate)));
1500 mergestate->mj_NullInnerTupleSlot =
1501 ExecInitNullTupleSlot(estate,
1502 ExecGetResultType(innerPlanState(mergestate)));
1505 * Can't handle right or full join with non-nil extra joinclauses.
1507 if (node->join.joinqual != NIL)
1509 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1510 errmsg("FULL JOIN is only supported with merge-joinable join conditions")));
1513 elog(ERROR, "unrecognized join type: %d",
1514 (int) node->join.jointype);
1518 * initialize tuple type and projection info
1520 ExecAssignResultTypeFromTL(&mergestate->js.ps);
1521 ExecAssignProjectionInfo(&mergestate->js.ps);
1524 * preprocess the merge clauses
1526 mergestate->mj_NumClauses = list_length(node->mergeclauses);
1527 mergestate->mj_Clauses = MJExamineQuals(node->mergeclauses,
1528 node->mergefamilies,
1529 node->mergestrategies,
1530 (PlanState *) mergestate);
1533 * initialize join state
1535 mergestate->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1536 mergestate->js.ps.ps_TupFromTlist = false;
1537 mergestate->mj_MatchedOuter = false;
1538 mergestate->mj_MatchedInner = false;
1539 mergestate->mj_OuterTupleSlot = NULL;
1540 mergestate->mj_InnerTupleSlot = NULL;
1543 * initialization successful
1545 MJ1_printf("ExecInitMergeJoin: %s\n",
1546 "node initialized");
1552 ExecCountSlotsMergeJoin(MergeJoin *node)
1554 return ExecCountSlotsNode(outerPlan((Plan *) node)) +
1555 ExecCountSlotsNode(innerPlan((Plan *) node)) +
1559 /* ----------------------------------------------------------------
1563 * frees storage allocated through C routines.
1564 * ----------------------------------------------------------------
1567 ExecEndMergeJoin(MergeJoinState *node)
1569 MJ1_printf("ExecEndMergeJoin: %s\n",
1570 "ending node processing");
1573 * Free the exprcontext
1575 ExecFreeExprContext(&node->js.ps);
1578 * clean out the tuple table
1580 ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
1581 ExecClearTuple(node->mj_MarkedTupleSlot);
1584 * shut down the subplans
1586 ExecEndNode(innerPlanState(node));
1587 ExecEndNode(outerPlanState(node));
1589 MJ1_printf("ExecEndMergeJoin: %s\n",
1590 "node processing ended");
1594 ExecReScanMergeJoin(MergeJoinState *node, ExprContext *exprCtxt)
1596 ExecClearTuple(node->mj_MarkedTupleSlot);
1598 node->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1599 node->js.ps.ps_TupFromTlist = false;
1600 node->mj_MatchedOuter = false;
1601 node->mj_MatchedInner = false;
1602 node->mj_OuterTupleSlot = NULL;
1603 node->mj_InnerTupleSlot = NULL;
1606 * if chgParam of subnodes is not null then plans will be re-scanned by
1607 * first ExecProcNode.
1609 if (((PlanState *) node)->lefttree->chgParam == NULL)
1610 ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
1611 if (((PlanState *) node)->righttree->chgParam == NULL)
1612 ExecReScan(((PlanState *) node)->righttree, exprCtxt);