Header And Logo

PostgreSQL
| The world's most advanced open source database.

nodeMergejoin.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * nodeMergejoin.c
00004  *    routines supporting merge joins
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/executor/nodeMergejoin.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 /*
00016  * INTERFACE ROUTINES
00017  *      ExecMergeJoin           mergejoin outer and inner relations.
00018  *      ExecInitMergeJoin       creates and initializes run time states
00019  *      ExecEndMergeJoin        cleans up the node.
00020  *
00021  * NOTES
00022  *
00023  *      Merge-join is done by joining the inner and outer tuples satisfying
00024  *      join clauses of the form ((= outerKey innerKey) ...).
00025  *      The join clause list is provided by the query planner and may contain
00026  *      more than one (= outerKey innerKey) clause (for composite sort key).
00027  *
00028  *      However, the query executor needs to know whether an outer
00029  *      tuple is "greater/smaller" than an inner tuple so that it can
00030  *      "synchronize" the two relations. For example, consider the following
00031  *      relations:
00032  *
00033  *              outer: (0 ^1 1 2 5 5 5 6 6 7)   current tuple: 1
00034  *              inner: (1 ^3 5 5 5 5 6)         current tuple: 3
00035  *
00036  *      To continue the merge-join, the executor needs to scan both inner
00037  *      and outer relations till the matching tuples 5. It needs to know
00038  *      that currently inner tuple 3 is "greater" than outer tuple 1 and
00039  *      therefore it should scan the outer relation first to find a
00040  *      matching tuple and so on.
00041  *
00042  *      Therefore, rather than directly executing the merge join clauses,
00043  *      we evaluate the left and right key expressions separately and then
00044  *      compare the columns one at a time (see MJCompare).  The planner
00045  *      passes us enough information about the sort ordering of the inputs
00046  *      to allow us to determine how to make the comparison.  We may use the
00047  *      appropriate btree comparison function, since Postgres' only notion
00048  *      of ordering is specified by btree opfamilies.
00049  *
00050  *
00051  *      Consider the above relations and suppose that the executor has
00052  *      just joined the first outer "5" with the last inner "5". The
00053  *      next step is of course to join the second outer "5" with all
00054  *      the inner "5's". This requires repositioning the inner "cursor"
00055  *      to point at the first inner "5". This is done by "marking" the
00056  *      first inner 5 so we can restore the "cursor" to it before joining
00057  *      with the second outer 5. The access method interface provides
00058  *      routines to mark and restore to a tuple.
00059  *
00060  *
00061  *      Essential operation of the merge join algorithm is as follows:
00062  *
00063  *      Join {
00064  *          get initial outer and inner tuples              INITIALIZE
00065  *          do forever {
00066  *              while (outer != inner) {                    SKIP_TEST
00067  *                  if (outer < inner)
00068  *                      advance outer                       SKIPOUTER_ADVANCE
00069  *                  else
00070  *                      advance inner                       SKIPINNER_ADVANCE
00071  *              }
00072  *              mark inner position                         SKIP_TEST
00073  *              do forever {
00074  *                  while (outer == inner) {
00075  *                      join tuples                         JOINTUPLES
00076  *                      advance inner position              NEXTINNER
00077  *                  }
00078  *                  advance outer position                  NEXTOUTER
00079  *                  if (outer == mark)                      TESTOUTER
00080  *                      restore inner position to mark      TESTOUTER
00081  *                  else
00082  *                      break   // return to top of outer loop
00083  *              }
00084  *          }
00085  *      }
00086  *
00087  *      The merge join operation is coded in the fashion
00088  *      of a state machine.  At each state, we do something and then
00089  *      proceed to another state.  This state is stored in the node's
00090  *      execution state information and is preserved across calls to
00091  *      ExecMergeJoin. -cim 10/31/89
00092  */
00093 #include "postgres.h"
00094 
00095 #include "access/nbtree.h"
00096 #include "executor/execdebug.h"
00097 #include "executor/nodeMergejoin.h"
00098 #include "utils/lsyscache.h"
00099 #include "utils/memutils.h"
00100 
00101 
00102 /*
00103  * States of the ExecMergeJoin state machine
00104  */
00105 #define EXEC_MJ_INITIALIZE_OUTER        1
00106 #define EXEC_MJ_INITIALIZE_INNER        2
00107 #define EXEC_MJ_JOINTUPLES              3
00108 #define EXEC_MJ_NEXTOUTER               4
00109 #define EXEC_MJ_TESTOUTER               5
00110 #define EXEC_MJ_NEXTINNER               6
00111 #define EXEC_MJ_SKIP_TEST               7
00112 #define EXEC_MJ_SKIPOUTER_ADVANCE       8
00113 #define EXEC_MJ_SKIPINNER_ADVANCE       9
00114 #define EXEC_MJ_ENDOUTER                10
00115 #define EXEC_MJ_ENDINNER                11
00116 
00117 /*
00118  * Runtime data for each mergejoin clause
00119  */
00120 typedef struct MergeJoinClauseData
00121 {
00122     /* Executable expression trees */
00123     ExprState  *lexpr;          /* left-hand (outer) input expression */
00124     ExprState  *rexpr;          /* right-hand (inner) input expression */
00125 
00126     /*
00127      * If we have a current left or right input tuple, the values of the
00128      * expressions are loaded into these fields:
00129      */
00130     Datum       ldatum;         /* current left-hand value */
00131     Datum       rdatum;         /* current right-hand value */
00132     bool        lisnull;        /* and their isnull flags */
00133     bool        risnull;
00134 
00135     /*
00136      * Everything we need to know to compare the left and right values is
00137      * stored here.
00138      */
00139     SortSupportData ssup;
00140 }   MergeJoinClauseData;
00141 
00142 /* Result type for MJEvalOuterValues and MJEvalInnerValues */
00143 typedef enum
00144 {
00145     MJEVAL_MATCHABLE,           /* normal, potentially matchable tuple */
00146     MJEVAL_NONMATCHABLE,        /* tuple cannot join because it has a null */
00147     MJEVAL_ENDOFJOIN            /* end of input (physical or effective) */
00148 } MJEvalResult;
00149 
00150 
00151 #define MarkInnerTuple(innerTupleSlot, mergestate) \
00152     ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
00153 
00154 
00155 /*
00156  * MJExamineQuals
00157  *
00158  * This deconstructs the list of mergejoinable expressions, which is given
00159  * to us by the planner in the form of a list of "leftexpr = rightexpr"
00160  * expression trees in the order matching the sort columns of the inputs.
00161  * We build an array of MergeJoinClause structs containing the information
00162  * we will need at runtime.  Each struct essentially tells us how to compare
00163  * the two expressions from the original clause.
00164  *
00165  * In addition to the expressions themselves, the planner passes the btree
00166  * opfamily OID, collation OID, btree strategy number (BTLessStrategyNumber or
00167  * BTGreaterStrategyNumber), and nulls-first flag that identify the intended
00168  * sort ordering for each merge key.  The mergejoinable operator is an
00169  * equality operator in the opfamily, and the two inputs are guaranteed to be
00170  * ordered in either increasing or decreasing (respectively) order according
00171  * to the opfamily and collation, with nulls at the indicated end of the range.
00172  * This allows us to obtain the needed comparison function from the opfamily.
00173  */
00174 static MergeJoinClause
00175 MJExamineQuals(List *mergeclauses,
00176                Oid *mergefamilies,
00177                Oid *mergecollations,
00178                int *mergestrategies,
00179                bool *mergenullsfirst,
00180                PlanState *parent)
00181 {
00182     MergeJoinClause clauses;
00183     int         nClauses = list_length(mergeclauses);
00184     int         iClause;
00185     ListCell   *cl;
00186 
00187     clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
00188 
00189     iClause = 0;
00190     foreach(cl, mergeclauses)
00191     {
00192         OpExpr     *qual = (OpExpr *) lfirst(cl);
00193         MergeJoinClause clause = &clauses[iClause];
00194         Oid         opfamily = mergefamilies[iClause];
00195         Oid         collation = mergecollations[iClause];
00196         StrategyNumber opstrategy = mergestrategies[iClause];
00197         bool        nulls_first = mergenullsfirst[iClause];
00198         int         op_strategy;
00199         Oid         op_lefttype;
00200         Oid         op_righttype;
00201         Oid         sortfunc;
00202 
00203         if (!IsA(qual, OpExpr))
00204             elog(ERROR, "mergejoin clause is not an OpExpr");
00205 
00206         /*
00207          * Prepare the input expressions for execution.
00208          */
00209         clause->lexpr = ExecInitExpr((Expr *) linitial(qual->args), parent);
00210         clause->rexpr = ExecInitExpr((Expr *) lsecond(qual->args), parent);
00211 
00212         /* Set up sort support data */
00213         clause->ssup.ssup_cxt = CurrentMemoryContext;
00214         clause->ssup.ssup_collation = collation;
00215         if (opstrategy == BTLessStrategyNumber)
00216             clause->ssup.ssup_reverse = false;
00217         else if (opstrategy == BTGreaterStrategyNumber)
00218             clause->ssup.ssup_reverse = true;
00219         else    /* planner screwed up */
00220             elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
00221         clause->ssup.ssup_nulls_first = nulls_first;
00222 
00223         /* Extract the operator's declared left/right datatypes */
00224         get_op_opfamily_properties(qual->opno, opfamily, false,
00225                                    &op_strategy,
00226                                    &op_lefttype,
00227                                    &op_righttype);
00228         if (op_strategy != BTEqualStrategyNumber)       /* should not happen */
00229             elog(ERROR, "cannot merge using non-equality operator %u",
00230                  qual->opno);
00231 
00232         /* And get the matching support or comparison function */
00233         sortfunc = get_opfamily_proc(opfamily,
00234                                      op_lefttype,
00235                                      op_righttype,
00236                                      BTSORTSUPPORT_PROC);
00237         if (OidIsValid(sortfunc))
00238         {
00239             /* The sort support function should provide a comparator */
00240             OidFunctionCall1(sortfunc, PointerGetDatum(&clause->ssup));
00241             Assert(clause->ssup.comparator != NULL);
00242         }
00243         else
00244         {
00245             /* opfamily doesn't provide sort support, get comparison func */
00246             sortfunc = get_opfamily_proc(opfamily,
00247                                          op_lefttype,
00248                                          op_righttype,
00249                                          BTORDER_PROC);
00250             if (!OidIsValid(sortfunc))  /* should not happen */
00251                 elog(ERROR, "missing support function %d(%u,%u) in opfamily %u",
00252                      BTORDER_PROC, op_lefttype, op_righttype, opfamily);
00253             /* We'll use a shim to call the old-style btree comparator */
00254             PrepareSortSupportComparisonShim(sortfunc, &clause->ssup);
00255         }
00256 
00257         iClause++;
00258     }
00259 
00260     return clauses;
00261 }
00262 
00263 /*
00264  * MJEvalOuterValues
00265  *
00266  * Compute the values of the mergejoined expressions for the current
00267  * outer tuple.  We also detect whether it's impossible for the current
00268  * outer tuple to match anything --- this is true if it yields a NULL
00269  * input, since we assume mergejoin operators are strict.  If the NULL
00270  * is in the first join column, and that column sorts nulls last, then
00271  * we can further conclude that no following tuple can match anything
00272  * either, since they must all have nulls in the first column.  However,
00273  * that case is only interesting if we're not in FillOuter mode, else
00274  * we have to visit all the tuples anyway.
00275  *
00276  * For the convenience of callers, we also make this routine responsible
00277  * for testing for end-of-input (null outer tuple), and returning
00278  * MJEVAL_ENDOFJOIN when that's seen.  This allows the same code to be used
00279  * for both real end-of-input and the effective end-of-input represented by
00280  * a first-column NULL.
00281  *
00282  * We evaluate the values in OuterEContext, which can be reset each
00283  * time we move to a new tuple.
00284  */
00285 static MJEvalResult
00286 MJEvalOuterValues(MergeJoinState *mergestate)
00287 {
00288     ExprContext *econtext = mergestate->mj_OuterEContext;
00289     MJEvalResult result = MJEVAL_MATCHABLE;
00290     int         i;
00291     MemoryContext oldContext;
00292 
00293     /* Check for end of outer subplan */
00294     if (TupIsNull(mergestate->mj_OuterTupleSlot))
00295         return MJEVAL_ENDOFJOIN;
00296 
00297     ResetExprContext(econtext);
00298 
00299     oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
00300 
00301     econtext->ecxt_outertuple = mergestate->mj_OuterTupleSlot;
00302 
00303     for (i = 0; i < mergestate->mj_NumClauses; i++)
00304     {
00305         MergeJoinClause clause = &mergestate->mj_Clauses[i];
00306 
00307         clause->ldatum = ExecEvalExpr(clause->lexpr, econtext,
00308                                       &clause->lisnull, NULL);
00309         if (clause->lisnull)
00310         {
00311             /* match is impossible; can we end the join early? */
00312             if (i == 0 && !clause->ssup.ssup_nulls_first &&
00313                 !mergestate->mj_FillOuter)
00314                 result = MJEVAL_ENDOFJOIN;
00315             else if (result == MJEVAL_MATCHABLE)
00316                 result = MJEVAL_NONMATCHABLE;
00317         }
00318     }
00319 
00320     MemoryContextSwitchTo(oldContext);
00321 
00322     return result;
00323 }
00324 
00325 /*
00326  * MJEvalInnerValues
00327  *
00328  * Same as above, but for the inner tuple.  Here, we have to be prepared
00329  * to load data from either the true current inner, or the marked inner,
00330  * so caller must tell us which slot to load from.
00331  */
00332 static MJEvalResult
00333 MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
00334 {
00335     ExprContext *econtext = mergestate->mj_InnerEContext;
00336     MJEvalResult result = MJEVAL_MATCHABLE;
00337     int         i;
00338     MemoryContext oldContext;
00339 
00340     /* Check for end of inner subplan */
00341     if (TupIsNull(innerslot))
00342         return MJEVAL_ENDOFJOIN;
00343 
00344     ResetExprContext(econtext);
00345 
00346     oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
00347 
00348     econtext->ecxt_innertuple = innerslot;
00349 
00350     for (i = 0; i < mergestate->mj_NumClauses; i++)
00351     {
00352         MergeJoinClause clause = &mergestate->mj_Clauses[i];
00353 
00354         clause->rdatum = ExecEvalExpr(clause->rexpr, econtext,
00355                                       &clause->risnull, NULL);
00356         if (clause->risnull)
00357         {
00358             /* match is impossible; can we end the join early? */
00359             if (i == 0 && !clause->ssup.ssup_nulls_first &&
00360                 !mergestate->mj_FillInner)
00361                 result = MJEVAL_ENDOFJOIN;
00362             else if (result == MJEVAL_MATCHABLE)
00363                 result = MJEVAL_NONMATCHABLE;
00364         }
00365     }
00366 
00367     MemoryContextSwitchTo(oldContext);
00368 
00369     return result;
00370 }
00371 
00372 /*
00373  * MJCompare
00374  *
00375  * Compare the mergejoinable values of the current two input tuples
00376  * and return 0 if they are equal (ie, the mergejoin equalities all
00377  * succeed), >0 if outer > inner, <0 if outer < inner.
00378  *
00379  * MJEvalOuterValues and MJEvalInnerValues must already have been called
00380  * for the current outer and inner tuples, respectively.
00381  */
00382 static int
00383 MJCompare(MergeJoinState *mergestate)
00384 {
00385     int         result = 0;
00386     bool        nulleqnull = false;
00387     ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
00388     int         i;
00389     MemoryContext oldContext;
00390 
00391     /*
00392      * Call the comparison functions in short-lived context, in case they leak
00393      * memory.
00394      */
00395     ResetExprContext(econtext);
00396 
00397     oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
00398 
00399     for (i = 0; i < mergestate->mj_NumClauses; i++)
00400     {
00401         MergeJoinClause clause = &mergestate->mj_Clauses[i];
00402 
00403         /*
00404          * Special case for NULL-vs-NULL, else use standard comparison.
00405          */
00406         if (clause->lisnull && clause->risnull)
00407         {
00408             nulleqnull = true;  /* NULL "=" NULL */
00409             continue;
00410         }
00411 
00412         result = ApplySortComparator(clause->ldatum, clause->lisnull,
00413                                      clause->rdatum, clause->risnull,
00414                                      &clause->ssup);
00415 
00416         if (result != 0)
00417             break;
00418     }
00419 
00420     /*
00421      * If we had any NULL-vs-NULL inputs, we do not want to report that the
00422      * tuples are equal.  Instead, if result is still 0, change it to +1. This
00423      * will result in advancing the inner side of the join.
00424      *
00425      * Likewise, if there was a constant-false joinqual, do not report
00426      * equality.  We have to check this as part of the mergequals, else the
00427      * rescan logic will do the wrong thing.
00428      */
00429     if (result == 0 &&
00430         (nulleqnull || mergestate->mj_ConstFalseJoin))
00431         result = 1;
00432 
00433     MemoryContextSwitchTo(oldContext);
00434 
00435     return result;
00436 }
00437 
00438 
00439 /*
00440  * Generate a fake join tuple with nulls for the inner tuple,
00441  * and return it if it passes the non-join quals.
00442  */
00443 static TupleTableSlot *
00444 MJFillOuter(MergeJoinState *node)
00445 {
00446     ExprContext *econtext = node->js.ps.ps_ExprContext;
00447     List       *otherqual = node->js.ps.qual;
00448 
00449     ResetExprContext(econtext);
00450 
00451     econtext->ecxt_outertuple = node->mj_OuterTupleSlot;
00452     econtext->ecxt_innertuple = node->mj_NullInnerTupleSlot;
00453 
00454     if (ExecQual(otherqual, econtext, false))
00455     {
00456         /*
00457          * qualification succeeded.  now form the desired projection tuple and
00458          * return the slot containing it.
00459          */
00460         TupleTableSlot *result;
00461         ExprDoneCond isDone;
00462 
00463         MJ_printf("ExecMergeJoin: returning outer fill tuple\n");
00464 
00465         result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
00466 
00467         if (isDone != ExprEndResult)
00468         {
00469             node->js.ps.ps_TupFromTlist =
00470                 (isDone == ExprMultipleResult);
00471             return result;
00472         }
00473     }
00474     else
00475         InstrCountFiltered2(node, 1);
00476 
00477     return NULL;
00478 }
00479 
00480 /*
00481  * Generate a fake join tuple with nulls for the outer tuple,
00482  * and return it if it passes the non-join quals.
00483  */
00484 static TupleTableSlot *
00485 MJFillInner(MergeJoinState *node)
00486 {
00487     ExprContext *econtext = node->js.ps.ps_ExprContext;
00488     List       *otherqual = node->js.ps.qual;
00489 
00490     ResetExprContext(econtext);
00491 
00492     econtext->ecxt_outertuple = node->mj_NullOuterTupleSlot;
00493     econtext->ecxt_innertuple = node->mj_InnerTupleSlot;
00494 
00495     if (ExecQual(otherqual, econtext, false))
00496     {
00497         /*
00498          * qualification succeeded.  now form the desired projection tuple and
00499          * return the slot containing it.
00500          */
00501         TupleTableSlot *result;
00502         ExprDoneCond isDone;
00503 
00504         MJ_printf("ExecMergeJoin: returning inner fill tuple\n");
00505 
00506         result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
00507 
00508         if (isDone != ExprEndResult)
00509         {
00510             node->js.ps.ps_TupFromTlist =
00511                 (isDone == ExprMultipleResult);
00512             return result;
00513         }
00514     }
00515     else
00516         InstrCountFiltered2(node, 1);
00517 
00518     return NULL;
00519 }
00520 
00521 
00522 /*
00523  * Check that a qual condition is constant true or constant false.
00524  * If it is constant false (or null), set *is_const_false to TRUE.
00525  *
00526  * Constant true would normally be represented by a NIL list, but we allow an
00527  * actual bool Const as well.  We do expect that the planner will have thrown
00528  * away any non-constant terms that have been ANDed with a constant false.
00529  */
00530 static bool
00531 check_constant_qual(List *qual, bool *is_const_false)
00532 {
00533     ListCell   *lc;
00534 
00535     foreach(lc, qual)
00536     {
00537         Const      *con = (Const *) lfirst(lc);
00538 
00539         if (!con || !IsA(con, Const))
00540             return false;
00541         if (con->constisnull || !DatumGetBool(con->constvalue))
00542             *is_const_false = true;
00543     }
00544     return true;
00545 }
00546 
00547 
00548 /* ----------------------------------------------------------------
00549  *      ExecMergeTupleDump
00550  *
00551  *      This function is called through the MJ_dump() macro
00552  *      when EXEC_MERGEJOINDEBUG is defined
00553  * ----------------------------------------------------------------
00554  */
00555 #ifdef EXEC_MERGEJOINDEBUG
00556 
00557 static void
00558 ExecMergeTupleDumpOuter(MergeJoinState *mergestate)
00559 {
00560     TupleTableSlot *outerSlot = mergestate->mj_OuterTupleSlot;
00561 
00562     printf("==== outer tuple ====\n");
00563     if (TupIsNull(outerSlot))
00564         printf("(nil)\n");
00565     else
00566         MJ_debugtup(outerSlot);
00567 }
00568 
00569 static void
00570 ExecMergeTupleDumpInner(MergeJoinState *mergestate)
00571 {
00572     TupleTableSlot *innerSlot = mergestate->mj_InnerTupleSlot;
00573 
00574     printf("==== inner tuple ====\n");
00575     if (TupIsNull(innerSlot))
00576         printf("(nil)\n");
00577     else
00578         MJ_debugtup(innerSlot);
00579 }
00580 
00581 static void
00582 ExecMergeTupleDumpMarked(MergeJoinState *mergestate)
00583 {
00584     TupleTableSlot *markedSlot = mergestate->mj_MarkedTupleSlot;
00585 
00586     printf("==== marked tuple ====\n");
00587     if (TupIsNull(markedSlot))
00588         printf("(nil)\n");
00589     else
00590         MJ_debugtup(markedSlot);
00591 }
00592 
00593 static void
00594 ExecMergeTupleDump(MergeJoinState *mergestate)
00595 {
00596     printf("******** ExecMergeTupleDump ********\n");
00597 
00598     ExecMergeTupleDumpOuter(mergestate);
00599     ExecMergeTupleDumpInner(mergestate);
00600     ExecMergeTupleDumpMarked(mergestate);
00601 
00602     printf("******** \n");
00603 }
00604 #endif
00605 
00606 /* ----------------------------------------------------------------
00607  *      ExecMergeJoin
00608  * ----------------------------------------------------------------
00609  */
00610 TupleTableSlot *
00611 ExecMergeJoin(MergeJoinState *node)
00612 {
00613     List       *joinqual;
00614     List       *otherqual;
00615     bool        qualResult;
00616     int         compareResult;
00617     PlanState  *innerPlan;
00618     TupleTableSlot *innerTupleSlot;
00619     PlanState  *outerPlan;
00620     TupleTableSlot *outerTupleSlot;
00621     ExprContext *econtext;
00622     bool        doFillOuter;
00623     bool        doFillInner;
00624 
00625     /*
00626      * get information from node
00627      */
00628     innerPlan = innerPlanState(node);
00629     outerPlan = outerPlanState(node);
00630     econtext = node->js.ps.ps_ExprContext;
00631     joinqual = node->js.joinqual;
00632     otherqual = node->js.ps.qual;
00633     doFillOuter = node->mj_FillOuter;
00634     doFillInner = node->mj_FillInner;
00635 
00636     /*
00637      * Check to see if we're still projecting out tuples from a previous join
00638      * tuple (because there is a function-returning-set in the projection
00639      * expressions).  If so, try to project another one.
00640      */
00641     if (node->js.ps.ps_TupFromTlist)
00642     {
00643         TupleTableSlot *result;
00644         ExprDoneCond isDone;
00645 
00646         result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
00647         if (isDone == ExprMultipleResult)
00648             return result;
00649         /* Done with that source tuple... */
00650         node->js.ps.ps_TupFromTlist = false;
00651     }
00652 
00653     /*
00654      * Reset per-tuple memory context to free any expression evaluation
00655      * storage allocated in the previous tuple cycle.  Note this can't happen
00656      * until we're done projecting out tuples from a join tuple.
00657      */
00658     ResetExprContext(econtext);
00659 
00660     /*
00661      * ok, everything is setup.. let's go to work
00662      */
00663     for (;;)
00664     {
00665         MJ_dump(node);
00666 
00667         /*
00668          * get the current state of the join and do things accordingly.
00669          */
00670         switch (node->mj_JoinState)
00671         {
00672                 /*
00673                  * EXEC_MJ_INITIALIZE_OUTER means that this is the first time
00674                  * ExecMergeJoin() has been called and so we have to fetch the
00675                  * first matchable tuple for both outer and inner subplans. We
00676                  * do the outer side in INITIALIZE_OUTER state, then advance
00677                  * to INITIALIZE_INNER state for the inner subplan.
00678                  */
00679             case EXEC_MJ_INITIALIZE_OUTER:
00680                 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_OUTER\n");
00681 
00682                 outerTupleSlot = ExecProcNode(outerPlan);
00683                 node->mj_OuterTupleSlot = outerTupleSlot;
00684 
00685                 /* Compute join values and check for unmatchability */
00686                 switch (MJEvalOuterValues(node))
00687                 {
00688                     case MJEVAL_MATCHABLE:
00689                         /* OK to go get the first inner tuple */
00690                         node->mj_JoinState = EXEC_MJ_INITIALIZE_INNER;
00691                         break;
00692                     case MJEVAL_NONMATCHABLE:
00693                         /* Stay in same state to fetch next outer tuple */
00694                         if (doFillOuter)
00695                         {
00696                             /*
00697                              * Generate a fake join tuple with nulls for the
00698                              * inner tuple, and return it if it passes the
00699                              * non-join quals.
00700                              */
00701                             TupleTableSlot *result;
00702 
00703                             result = MJFillOuter(node);
00704                             if (result)
00705                                 return result;
00706                         }
00707                         break;
00708                     case MJEVAL_ENDOFJOIN:
00709                         /* No more outer tuples */
00710                         MJ_printf("ExecMergeJoin: nothing in outer subplan\n");
00711                         if (doFillInner)
00712                         {
00713                             /*
00714                              * Need to emit right-join tuples for remaining
00715                              * inner tuples. We set MatchedInner = true to
00716                              * force the ENDOUTER state to advance inner.
00717                              */
00718                             node->mj_JoinState = EXEC_MJ_ENDOUTER;
00719                             node->mj_MatchedInner = true;
00720                             break;
00721                         }
00722                         /* Otherwise we're done. */
00723                         return NULL;
00724                 }
00725                 break;
00726 
00727             case EXEC_MJ_INITIALIZE_INNER:
00728                 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_INNER\n");
00729 
00730                 innerTupleSlot = ExecProcNode(innerPlan);
00731                 node->mj_InnerTupleSlot = innerTupleSlot;
00732 
00733                 /* Compute join values and check for unmatchability */
00734                 switch (MJEvalInnerValues(node, innerTupleSlot))
00735                 {
00736                     case MJEVAL_MATCHABLE:
00737 
00738                         /*
00739                          * OK, we have the initial tuples.  Begin by skipping
00740                          * non-matching tuples.
00741                          */
00742                         node->mj_JoinState = EXEC_MJ_SKIP_TEST;
00743                         break;
00744                     case MJEVAL_NONMATCHABLE:
00745                         /* Mark before advancing, if wanted */
00746                         if (node->mj_ExtraMarks)
00747                             ExecMarkPos(innerPlan);
00748                         /* Stay in same state to fetch next inner tuple */
00749                         if (doFillInner)
00750                         {
00751                             /*
00752                              * Generate a fake join tuple with nulls for the
00753                              * outer tuple, and return it if it passes the
00754                              * non-join quals.
00755                              */
00756                             TupleTableSlot *result;
00757 
00758                             result = MJFillInner(node);
00759                             if (result)
00760                                 return result;
00761                         }
00762                         break;
00763                     case MJEVAL_ENDOFJOIN:
00764                         /* No more inner tuples */
00765                         MJ_printf("ExecMergeJoin: nothing in inner subplan\n");
00766                         if (doFillOuter)
00767                         {
00768                             /*
00769                              * Need to emit left-join tuples for all outer
00770                              * tuples, including the one we just fetched.  We
00771                              * set MatchedOuter = false to force the ENDINNER
00772                              * state to emit first tuple before advancing
00773                              * outer.
00774                              */
00775                             node->mj_JoinState = EXEC_MJ_ENDINNER;
00776                             node->mj_MatchedOuter = false;
00777                             break;
00778                         }
00779                         /* Otherwise we're done. */
00780                         return NULL;
00781                 }
00782                 break;
00783 
00784                 /*
00785                  * EXEC_MJ_JOINTUPLES means we have two tuples which satisfied
00786                  * the merge clause so we join them and then proceed to get
00787                  * the next inner tuple (EXEC_MJ_NEXTINNER).
00788                  */
00789             case EXEC_MJ_JOINTUPLES:
00790                 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n");
00791 
00792                 /*
00793                  * Set the next state machine state.  The right things will
00794                  * happen whether we return this join tuple or just fall
00795                  * through to continue the state machine execution.
00796                  */
00797                 node->mj_JoinState = EXEC_MJ_NEXTINNER;
00798 
00799                 /*
00800                  * Check the extra qual conditions to see if we actually want
00801                  * to return this join tuple.  If not, can proceed with merge.
00802                  * We must distinguish the additional joinquals (which must
00803                  * pass to consider the tuples "matched" for outer-join logic)
00804                  * from the otherquals (which must pass before we actually
00805                  * return the tuple).
00806                  *
00807                  * We don't bother with a ResetExprContext here, on the
00808                  * assumption that we just did one while checking the merge
00809                  * qual.  One per tuple should be sufficient.  We do have to
00810                  * set up the econtext links to the tuples for ExecQual to
00811                  * use.
00812                  */
00813                 outerTupleSlot = node->mj_OuterTupleSlot;
00814                 econtext->ecxt_outertuple = outerTupleSlot;
00815                 innerTupleSlot = node->mj_InnerTupleSlot;
00816                 econtext->ecxt_innertuple = innerTupleSlot;
00817 
00818                 qualResult = (joinqual == NIL ||
00819                               ExecQual(joinqual, econtext, false));
00820                 MJ_DEBUG_QUAL(joinqual, qualResult);
00821 
00822                 if (qualResult)
00823                 {
00824                     node->mj_MatchedOuter = true;
00825                     node->mj_MatchedInner = true;
00826 
00827                     /* In an antijoin, we never return a matched tuple */
00828                     if (node->js.jointype == JOIN_ANTI)
00829                     {
00830                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
00831                         break;
00832                     }
00833 
00834                     /*
00835                      * In a semijoin, we'll consider returning the first
00836                      * match, but after that we're done with this outer tuple.
00837                      */
00838                     if (node->js.jointype == JOIN_SEMI)
00839                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
00840 
00841                     qualResult = (otherqual == NIL ||
00842                                   ExecQual(otherqual, econtext, false));
00843                     MJ_DEBUG_QUAL(otherqual, qualResult);
00844 
00845                     if (qualResult)
00846                     {
00847                         /*
00848                          * qualification succeeded.  now form the desired
00849                          * projection tuple and return the slot containing it.
00850                          */
00851                         TupleTableSlot *result;
00852                         ExprDoneCond isDone;
00853 
00854                         MJ_printf("ExecMergeJoin: returning tuple\n");
00855 
00856                         result = ExecProject(node->js.ps.ps_ProjInfo,
00857                                              &isDone);
00858 
00859                         if (isDone != ExprEndResult)
00860                         {
00861                             node->js.ps.ps_TupFromTlist =
00862                                 (isDone == ExprMultipleResult);
00863                             return result;
00864                         }
00865                     }
00866                     else
00867                         InstrCountFiltered2(node, 1);
00868                 }
00869                 else
00870                     InstrCountFiltered1(node, 1);
00871                 break;
00872 
00873                 /*
00874                  * EXEC_MJ_NEXTINNER means advance the inner scan to the next
00875                  * tuple. If the tuple is not nil, we then proceed to test it
00876                  * against the join qualification.
00877                  *
00878                  * Before advancing, we check to see if we must emit an
00879                  * outer-join fill tuple for this inner tuple.
00880                  */
00881             case EXEC_MJ_NEXTINNER:
00882                 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n");
00883 
00884                 if (doFillInner && !node->mj_MatchedInner)
00885                 {
00886                     /*
00887                      * Generate a fake join tuple with nulls for the outer
00888                      * tuple, and return it if it passes the non-join quals.
00889                      */
00890                     TupleTableSlot *result;
00891 
00892                     node->mj_MatchedInner = true;       /* do it only once */
00893 
00894                     result = MJFillInner(node);
00895                     if (result)
00896                         return result;
00897                 }
00898 
00899                 /*
00900                  * now we get the next inner tuple, if any.  If there's none,
00901                  * advance to next outer tuple (which may be able to join to
00902                  * previously marked tuples).
00903                  *
00904                  * NB: must NOT do "extraMarks" here, since we may need to
00905                  * return to previously marked tuples.
00906                  */
00907                 innerTupleSlot = ExecProcNode(innerPlan);
00908                 node->mj_InnerTupleSlot = innerTupleSlot;
00909                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
00910                 node->mj_MatchedInner = false;
00911 
00912                 /* Compute join values and check for unmatchability */
00913                 switch (MJEvalInnerValues(node, innerTupleSlot))
00914                 {
00915                     case MJEVAL_MATCHABLE:
00916 
00917                         /*
00918                          * Test the new inner tuple to see if it matches
00919                          * outer.
00920                          *
00921                          * If they do match, then we join them and move on to
00922                          * the next inner tuple (EXEC_MJ_JOINTUPLES).
00923                          *
00924                          * If they do not match then advance to next outer
00925                          * tuple.
00926                          */
00927                         compareResult = MJCompare(node);
00928                         MJ_DEBUG_COMPARE(compareResult);
00929 
00930                         if (compareResult == 0)
00931                             node->mj_JoinState = EXEC_MJ_JOINTUPLES;
00932                         else
00933                         {
00934                             Assert(compareResult < 0);
00935                             node->mj_JoinState = EXEC_MJ_NEXTOUTER;
00936                         }
00937                         break;
00938                     case MJEVAL_NONMATCHABLE:
00939 
00940                         /*
00941                          * It contains a NULL and hence can't match any outer
00942                          * tuple, so we can skip the comparison and assume the
00943                          * new tuple is greater than current outer.
00944                          */
00945                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
00946                         break;
00947                     case MJEVAL_ENDOFJOIN:
00948 
00949                         /*
00950                          * No more inner tuples.  However, this might be only
00951                          * effective and not physical end of inner plan, so
00952                          * force mj_InnerTupleSlot to null to make sure we
00953                          * don't fetch more inner tuples.  (We need this hack
00954                          * because we are not transiting to a state where the
00955                          * inner plan is assumed to be exhausted.)
00956                          */
00957                         node->mj_InnerTupleSlot = NULL;
00958                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
00959                         break;
00960                 }
00961                 break;
00962 
00963                 /*-------------------------------------------
00964                  * EXEC_MJ_NEXTOUTER means
00965                  *
00966                  *              outer inner
00967                  * outer tuple -  5     5  - marked tuple
00968                  *                5     5
00969                  *                6     6  - inner tuple
00970                  *                7     7
00971                  *
00972                  * we know we just bumped into the
00973                  * first inner tuple > current outer tuple (or possibly
00974                  * the end of the inner stream)
00975                  * so get a new outer tuple and then
00976                  * proceed to test it against the marked tuple
00977                  * (EXEC_MJ_TESTOUTER)
00978                  *
00979                  * Before advancing, we check to see if we must emit an
00980                  * outer-join fill tuple for this outer tuple.
00981                  *------------------------------------------------
00982                  */
00983             case EXEC_MJ_NEXTOUTER:
00984                 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n");
00985 
00986                 if (doFillOuter && !node->mj_MatchedOuter)
00987                 {
00988                     /*
00989                      * Generate a fake join tuple with nulls for the inner
00990                      * tuple, and return it if it passes the non-join quals.
00991                      */
00992                     TupleTableSlot *result;
00993 
00994                     node->mj_MatchedOuter = true;       /* do it only once */
00995 
00996                     result = MJFillOuter(node);
00997                     if (result)
00998                         return result;
00999                 }
01000 
01001                 /*
01002                  * now we get the next outer tuple, if any
01003                  */
01004                 outerTupleSlot = ExecProcNode(outerPlan);
01005                 node->mj_OuterTupleSlot = outerTupleSlot;
01006                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
01007                 node->mj_MatchedOuter = false;
01008 
01009                 /* Compute join values and check for unmatchability */
01010                 switch (MJEvalOuterValues(node))
01011                 {
01012                     case MJEVAL_MATCHABLE:
01013                         /* Go test the new tuple against the marked tuple */
01014                         node->mj_JoinState = EXEC_MJ_TESTOUTER;
01015                         break;
01016                     case MJEVAL_NONMATCHABLE:
01017                         /* Can't match, so fetch next outer tuple */
01018                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
01019                         break;
01020                     case MJEVAL_ENDOFJOIN:
01021                         /* No more outer tuples */
01022                         MJ_printf("ExecMergeJoin: end of outer subplan\n");
01023                         innerTupleSlot = node->mj_InnerTupleSlot;
01024                         if (doFillInner && !TupIsNull(innerTupleSlot))
01025                         {
01026                             /*
01027                              * Need to emit right-join tuples for remaining
01028                              * inner tuples.
01029                              */
01030                             node->mj_JoinState = EXEC_MJ_ENDOUTER;
01031                             break;
01032                         }
01033                         /* Otherwise we're done. */
01034                         return NULL;
01035                 }
01036                 break;
01037 
01038                 /*--------------------------------------------------------
01039                  * EXEC_MJ_TESTOUTER If the new outer tuple and the marked
01040                  * tuple satisfy the merge clause then we know we have
01041                  * duplicates in the outer scan so we have to restore the
01042                  * inner scan to the marked tuple and proceed to join the
01043                  * new outer tuple with the inner tuples.
01044                  *
01045                  * This is the case when
01046                  *                        outer inner
01047                  *                          4     5  - marked tuple
01048                  *           outer tuple -  5     5
01049                  *       new outer tuple -  5     5
01050                  *                          6     8  - inner tuple
01051                  *                          7    12
01052                  *
01053                  *              new outer tuple == marked tuple
01054                  *
01055                  * If the outer tuple fails the test, then we are done
01056                  * with the marked tuples, and we have to look for a
01057                  * match to the current inner tuple.  So we will
01058                  * proceed to skip outer tuples until outer >= inner
01059                  * (EXEC_MJ_SKIP_TEST).
01060                  *
01061                  *      This is the case when
01062                  *
01063                  *                        outer inner
01064                  *                          5     5  - marked tuple
01065                  *           outer tuple -  5     5
01066                  *       new outer tuple -  6     8  - inner tuple
01067                  *                          7    12
01068                  *
01069                  *              new outer tuple > marked tuple
01070                  *
01071                  *---------------------------------------------------------
01072                  */
01073             case EXEC_MJ_TESTOUTER:
01074                 MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
01075 
01076                 /*
01077                  * Here we must compare the outer tuple with the marked inner
01078                  * tuple.  (We can ignore the result of MJEvalInnerValues,
01079                  * since the marked inner tuple is certainly matchable.)
01080                  */
01081                 innerTupleSlot = node->mj_MarkedTupleSlot;
01082                 (void) MJEvalInnerValues(node, innerTupleSlot);
01083 
01084                 compareResult = MJCompare(node);
01085                 MJ_DEBUG_COMPARE(compareResult);
01086 
01087                 if (compareResult == 0)
01088                 {
01089                     /*
01090                      * the merge clause matched so now we restore the inner
01091                      * scan position to the first mark, and go join that tuple
01092                      * (and any following ones) to the new outer.
01093                      *
01094                      * NOTE: we do not need to worry about the MatchedInner
01095                      * state for the rescanned inner tuples.  We know all of
01096                      * them will match this new outer tuple and therefore
01097                      * won't be emitted as fill tuples.  This works *only*
01098                      * because we require the extra joinquals to be constant
01099                      * when doing a right or full join --- otherwise some of
01100                      * the rescanned tuples might fail the extra joinquals.
01101                      * This obviously won't happen for a constant-true extra
01102                      * joinqual, while the constant-false case is handled by
01103                      * forcing the merge clause to never match, so we never
01104                      * get here.
01105                      */
01106                     ExecRestrPos(innerPlan);
01107 
01108                     /*
01109                      * ExecRestrPos probably should give us back a new Slot,
01110                      * but since it doesn't, use the marked slot.  (The
01111                      * previously returned mj_InnerTupleSlot cannot be assumed
01112                      * to hold the required tuple.)
01113                      */
01114                     node->mj_InnerTupleSlot = innerTupleSlot;
01115                     /* we need not do MJEvalInnerValues again */
01116 
01117                     node->mj_JoinState = EXEC_MJ_JOINTUPLES;
01118                 }
01119                 else
01120                 {
01121                     /* ----------------
01122                      *  if the new outer tuple didn't match the marked inner
01123                      *  tuple then we have a case like:
01124                      *
01125                      *           outer inner
01126                      *             4     4  - marked tuple
01127                      * new outer - 5     4
01128                      *             6     5  - inner tuple
01129                      *             7
01130                      *
01131                      *  which means that all subsequent outer tuples will be
01132                      *  larger than our marked inner tuples.  So we need not
01133                      *  revisit any of the marked tuples but can proceed to
01134                      *  look for a match to the current inner.  If there's
01135                      *  no more inners, no more matches are possible.
01136                      * ----------------
01137                      */
01138                     Assert(compareResult > 0);
01139                     innerTupleSlot = node->mj_InnerTupleSlot;
01140 
01141                     /* reload comparison data for current inner */
01142                     switch (MJEvalInnerValues(node, innerTupleSlot))
01143                     {
01144                         case MJEVAL_MATCHABLE:
01145                             /* proceed to compare it to the current outer */
01146                             node->mj_JoinState = EXEC_MJ_SKIP_TEST;
01147                             break;
01148                         case MJEVAL_NONMATCHABLE:
01149 
01150                             /*
01151                              * current inner can't possibly match any outer;
01152                              * better to advance the inner scan than the
01153                              * outer.
01154                              */
01155                             node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
01156                             break;
01157                         case MJEVAL_ENDOFJOIN:
01158                             /* No more inner tuples */
01159                             if (doFillOuter)
01160                             {
01161                                 /*
01162                                  * Need to emit left-join tuples for remaining
01163                                  * outer tuples.
01164                                  */
01165                                 node->mj_JoinState = EXEC_MJ_ENDINNER;
01166                                 break;
01167                             }
01168                             /* Otherwise we're done. */
01169                             return NULL;
01170                     }
01171                 }
01172                 break;
01173 
01174                 /*----------------------------------------------------------
01175                  * EXEC_MJ_SKIP means compare tuples and if they do not
01176                  * match, skip whichever is lesser.
01177                  *
01178                  * For example:
01179                  *
01180                  *              outer inner
01181                  *                5     5
01182                  *                5     5
01183                  * outer tuple -  6     8  - inner tuple
01184                  *                7    12
01185                  *                8    14
01186                  *
01187                  * we have to advance the outer scan
01188                  * until we find the outer 8.
01189                  *
01190                  * On the other hand:
01191                  *
01192                  *              outer inner
01193                  *                5     5
01194                  *                5     5
01195                  * outer tuple - 12     8  - inner tuple
01196                  *               14    10
01197                  *               17    12
01198                  *
01199                  * we have to advance the inner scan
01200                  * until we find the inner 12.
01201                  *----------------------------------------------------------
01202                  */
01203             case EXEC_MJ_SKIP_TEST:
01204                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIP_TEST\n");
01205 
01206                 /*
01207                  * before we advance, make sure the current tuples do not
01208                  * satisfy the mergeclauses.  If they do, then we update the
01209                  * marked tuple position and go join them.
01210                  */
01211                 compareResult = MJCompare(node);
01212                 MJ_DEBUG_COMPARE(compareResult);
01213 
01214                 if (compareResult == 0)
01215                 {
01216                     ExecMarkPos(innerPlan);
01217 
01218                     MarkInnerTuple(node->mj_InnerTupleSlot, node);
01219 
01220                     node->mj_JoinState = EXEC_MJ_JOINTUPLES;
01221                 }
01222                 else if (compareResult < 0)
01223                     node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
01224                 else
01225                     /* compareResult > 0 */
01226                     node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
01227                 break;
01228 
01229                 /*
01230                  * SKIPOUTER_ADVANCE: advance over an outer tuple that is
01231                  * known not to join to any inner tuple.
01232                  *
01233                  * Before advancing, we check to see if we must emit an
01234                  * outer-join fill tuple for this outer tuple.
01235                  */
01236             case EXEC_MJ_SKIPOUTER_ADVANCE:
01237                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_ADVANCE\n");
01238 
01239                 if (doFillOuter && !node->mj_MatchedOuter)
01240                 {
01241                     /*
01242                      * Generate a fake join tuple with nulls for the inner
01243                      * tuple, and return it if it passes the non-join quals.
01244                      */
01245                     TupleTableSlot *result;
01246 
01247                     node->mj_MatchedOuter = true;       /* do it only once */
01248 
01249                     result = MJFillOuter(node);
01250                     if (result)
01251                         return result;
01252                 }
01253 
01254                 /*
01255                  * now we get the next outer tuple, if any
01256                  */
01257                 outerTupleSlot = ExecProcNode(outerPlan);
01258                 node->mj_OuterTupleSlot = outerTupleSlot;
01259                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
01260                 node->mj_MatchedOuter = false;
01261 
01262                 /* Compute join values and check for unmatchability */
01263                 switch (MJEvalOuterValues(node))
01264                 {
01265                     case MJEVAL_MATCHABLE:
01266                         /* Go test the new tuple against the current inner */
01267                         node->mj_JoinState = EXEC_MJ_SKIP_TEST;
01268                         break;
01269                     case MJEVAL_NONMATCHABLE:
01270                         /* Can't match, so fetch next outer tuple */
01271                         node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
01272                         break;
01273                     case MJEVAL_ENDOFJOIN:
01274                         /* No more outer tuples */
01275                         MJ_printf("ExecMergeJoin: end of outer subplan\n");
01276                         innerTupleSlot = node->mj_InnerTupleSlot;
01277                         if (doFillInner && !TupIsNull(innerTupleSlot))
01278                         {
01279                             /*
01280                              * Need to emit right-join tuples for remaining
01281                              * inner tuples.
01282                              */
01283                             node->mj_JoinState = EXEC_MJ_ENDOUTER;
01284                             break;
01285                         }
01286                         /* Otherwise we're done. */
01287                         return NULL;
01288                 }
01289                 break;
01290 
01291                 /*
01292                  * SKIPINNER_ADVANCE: advance over an inner tuple that is
01293                  * known not to join to any outer tuple.
01294                  *
01295                  * Before advancing, we check to see if we must emit an
01296                  * outer-join fill tuple for this inner tuple.
01297                  */
01298             case EXEC_MJ_SKIPINNER_ADVANCE:
01299                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_ADVANCE\n");
01300 
01301                 if (doFillInner && !node->mj_MatchedInner)
01302                 {
01303                     /*
01304                      * Generate a fake join tuple with nulls for the outer
01305                      * tuple, and return it if it passes the non-join quals.
01306                      */
01307                     TupleTableSlot *result;
01308 
01309                     node->mj_MatchedInner = true;       /* do it only once */
01310 
01311                     result = MJFillInner(node);
01312                     if (result)
01313                         return result;
01314                 }
01315 
01316                 /* Mark before advancing, if wanted */
01317                 if (node->mj_ExtraMarks)
01318                     ExecMarkPos(innerPlan);
01319 
01320                 /*
01321                  * now we get the next inner tuple, if any
01322                  */
01323                 innerTupleSlot = ExecProcNode(innerPlan);
01324                 node->mj_InnerTupleSlot = innerTupleSlot;
01325                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
01326                 node->mj_MatchedInner = false;
01327 
01328                 /* Compute join values and check for unmatchability */
01329                 switch (MJEvalInnerValues(node, innerTupleSlot))
01330                 {
01331                     case MJEVAL_MATCHABLE:
01332                         /* proceed to compare it to the current outer */
01333                         node->mj_JoinState = EXEC_MJ_SKIP_TEST;
01334                         break;
01335                     case MJEVAL_NONMATCHABLE:
01336 
01337                         /*
01338                          * current inner can't possibly match any outer;
01339                          * better to advance the inner scan than the outer.
01340                          */
01341                         node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
01342                         break;
01343                     case MJEVAL_ENDOFJOIN:
01344                         /* No more inner tuples */
01345                         MJ_printf("ExecMergeJoin: end of inner subplan\n");
01346                         outerTupleSlot = node->mj_OuterTupleSlot;
01347                         if (doFillOuter && !TupIsNull(outerTupleSlot))
01348                         {
01349                             /*
01350                              * Need to emit left-join tuples for remaining
01351                              * outer tuples.
01352                              */
01353                             node->mj_JoinState = EXEC_MJ_ENDINNER;
01354                             break;
01355                         }
01356                         /* Otherwise we're done. */
01357                         return NULL;
01358                 }
01359                 break;
01360 
01361                 /*
01362                  * EXEC_MJ_ENDOUTER means we have run out of outer tuples, but
01363                  * are doing a right/full join and therefore must null-fill
01364                  * any remaining unmatched inner tuples.
01365                  */
01366             case EXEC_MJ_ENDOUTER:
01367                 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDOUTER\n");
01368 
01369                 Assert(doFillInner);
01370 
01371                 if (!node->mj_MatchedInner)
01372                 {
01373                     /*
01374                      * Generate a fake join tuple with nulls for the outer
01375                      * tuple, and return it if it passes the non-join quals.
01376                      */
01377                     TupleTableSlot *result;
01378 
01379                     node->mj_MatchedInner = true;       /* do it only once */
01380 
01381                     result = MJFillInner(node);
01382                     if (result)
01383                         return result;
01384                 }
01385 
01386                 /* Mark before advancing, if wanted */
01387                 if (node->mj_ExtraMarks)
01388                     ExecMarkPos(innerPlan);
01389 
01390                 /*
01391                  * now we get the next inner tuple, if any
01392                  */
01393                 innerTupleSlot = ExecProcNode(innerPlan);
01394                 node->mj_InnerTupleSlot = innerTupleSlot;
01395                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
01396                 node->mj_MatchedInner = false;
01397 
01398                 if (TupIsNull(innerTupleSlot))
01399                 {
01400                     MJ_printf("ExecMergeJoin: end of inner subplan\n");
01401                     return NULL;
01402                 }
01403 
01404                 /* Else remain in ENDOUTER state and process next tuple. */
01405                 break;
01406 
01407                 /*
01408                  * EXEC_MJ_ENDINNER means we have run out of inner tuples, but
01409                  * are doing a left/full join and therefore must null- fill
01410                  * any remaining unmatched outer tuples.
01411                  */
01412             case EXEC_MJ_ENDINNER:
01413                 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDINNER\n");
01414 
01415                 Assert(doFillOuter);
01416 
01417                 if (!node->mj_MatchedOuter)
01418                 {
01419                     /*
01420                      * Generate a fake join tuple with nulls for the inner
01421                      * tuple, and return it if it passes the non-join quals.
01422                      */
01423                     TupleTableSlot *result;
01424 
01425                     node->mj_MatchedOuter = true;       /* do it only once */
01426 
01427                     result = MJFillOuter(node);
01428                     if (result)
01429                         return result;
01430                 }
01431 
01432                 /*
01433                  * now we get the next outer tuple, if any
01434                  */
01435                 outerTupleSlot = ExecProcNode(outerPlan);
01436                 node->mj_OuterTupleSlot = outerTupleSlot;
01437                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
01438                 node->mj_MatchedOuter = false;
01439 
01440                 if (TupIsNull(outerTupleSlot))
01441                 {
01442                     MJ_printf("ExecMergeJoin: end of outer subplan\n");
01443                     return NULL;
01444                 }
01445 
01446                 /* Else remain in ENDINNER state and process next tuple. */
01447                 break;
01448 
01449                 /*
01450                  * broken state value?
01451                  */
01452             default:
01453                 elog(ERROR, "unrecognized mergejoin state: %d",
01454                      (int) node->mj_JoinState);
01455         }
01456     }
01457 }
01458 
01459 /* ----------------------------------------------------------------
01460  *      ExecInitMergeJoin
01461  * ----------------------------------------------------------------
01462  */
01463 MergeJoinState *
01464 ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
01465 {
01466     MergeJoinState *mergestate;
01467 
01468     /* check for unsupported flags */
01469     Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
01470 
01471     MJ1_printf("ExecInitMergeJoin: %s\n",
01472                "initializing node");
01473 
01474     /*
01475      * create state structure
01476      */
01477     mergestate = makeNode(MergeJoinState);
01478     mergestate->js.ps.plan = (Plan *) node;
01479     mergestate->js.ps.state = estate;
01480 
01481     /*
01482      * Miscellaneous initialization
01483      *
01484      * create expression context for node
01485      */
01486     ExecAssignExprContext(estate, &mergestate->js.ps);
01487 
01488     /*
01489      * we need two additional econtexts in which we can compute the join
01490      * expressions from the left and right input tuples.  The node's regular
01491      * econtext won't do because it gets reset too often.
01492      */
01493     mergestate->mj_OuterEContext = CreateExprContext(estate);
01494     mergestate->mj_InnerEContext = CreateExprContext(estate);
01495 
01496     /*
01497      * initialize child expressions
01498      */
01499     mergestate->js.ps.targetlist = (List *)
01500         ExecInitExpr((Expr *) node->join.plan.targetlist,
01501                      (PlanState *) mergestate);
01502     mergestate->js.ps.qual = (List *)
01503         ExecInitExpr((Expr *) node->join.plan.qual,
01504                      (PlanState *) mergestate);
01505     mergestate->js.jointype = node->join.jointype;
01506     mergestate->js.joinqual = (List *)
01507         ExecInitExpr((Expr *) node->join.joinqual,
01508                      (PlanState *) mergestate);
01509     mergestate->mj_ConstFalseJoin = false;
01510     /* mergeclauses are handled below */
01511 
01512     /*
01513      * initialize child nodes
01514      *
01515      * inner child must support MARK/RESTORE.
01516      */
01517     outerPlanState(mergestate) = ExecInitNode(outerPlan(node), estate, eflags);
01518     innerPlanState(mergestate) = ExecInitNode(innerPlan(node), estate,
01519                                               eflags | EXEC_FLAG_MARK);
01520 
01521     /*
01522      * For certain types of inner child nodes, it is advantageous to issue
01523      * MARK every time we advance past an inner tuple we will never return to.
01524      * For other types, MARK on a tuple we cannot return to is a waste of
01525      * cycles.  Detect which case applies and set mj_ExtraMarks if we want to
01526      * issue "unnecessary" MARK calls.
01527      *
01528      * Currently, only Material wants the extra MARKs, and it will be helpful
01529      * only if eflags doesn't specify REWIND.
01530      */
01531     if (IsA(innerPlan(node), Material) &&
01532         (eflags & EXEC_FLAG_REWIND) == 0)
01533         mergestate->mj_ExtraMarks = true;
01534     else
01535         mergestate->mj_ExtraMarks = false;
01536 
01537     /*
01538      * tuple table initialization
01539      */
01540     ExecInitResultTupleSlot(estate, &mergestate->js.ps);
01541 
01542     mergestate->mj_MarkedTupleSlot = ExecInitExtraTupleSlot(estate);
01543     ExecSetSlotDescriptor(mergestate->mj_MarkedTupleSlot,
01544                           ExecGetResultType(innerPlanState(mergestate)));
01545 
01546     switch (node->join.jointype)
01547     {
01548         case JOIN_INNER:
01549         case JOIN_SEMI:
01550             mergestate->mj_FillOuter = false;
01551             mergestate->mj_FillInner = false;
01552             break;
01553         case JOIN_LEFT:
01554         case JOIN_ANTI:
01555             mergestate->mj_FillOuter = true;
01556             mergestate->mj_FillInner = false;
01557             mergestate->mj_NullInnerTupleSlot =
01558                 ExecInitNullTupleSlot(estate,
01559                               ExecGetResultType(innerPlanState(mergestate)));
01560             break;
01561         case JOIN_RIGHT:
01562             mergestate->mj_FillOuter = false;
01563             mergestate->mj_FillInner = true;
01564             mergestate->mj_NullOuterTupleSlot =
01565                 ExecInitNullTupleSlot(estate,
01566                               ExecGetResultType(outerPlanState(mergestate)));
01567 
01568             /*
01569              * Can't handle right or full join with non-constant extra
01570              * joinclauses.  This should have been caught by planner.
01571              */
01572             if (!check_constant_qual(node->join.joinqual,
01573                                      &mergestate->mj_ConstFalseJoin))
01574                 ereport(ERROR,
01575                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
01576                          errmsg("RIGHT JOIN is only supported with merge-joinable join conditions")));
01577             break;
01578         case JOIN_FULL:
01579             mergestate->mj_FillOuter = true;
01580             mergestate->mj_FillInner = true;
01581             mergestate->mj_NullOuterTupleSlot =
01582                 ExecInitNullTupleSlot(estate,
01583                               ExecGetResultType(outerPlanState(mergestate)));
01584             mergestate->mj_NullInnerTupleSlot =
01585                 ExecInitNullTupleSlot(estate,
01586                               ExecGetResultType(innerPlanState(mergestate)));
01587 
01588             /*
01589              * Can't handle right or full join with non-constant extra
01590              * joinclauses.  This should have been caught by planner.
01591              */
01592             if (!check_constant_qual(node->join.joinqual,
01593                                      &mergestate->mj_ConstFalseJoin))
01594                 ereport(ERROR,
01595                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
01596                          errmsg("FULL JOIN is only supported with merge-joinable join conditions")));
01597             break;
01598         default:
01599             elog(ERROR, "unrecognized join type: %d",
01600                  (int) node->join.jointype);
01601     }
01602 
01603     /*
01604      * initialize tuple type and projection info
01605      */
01606     ExecAssignResultTypeFromTL(&mergestate->js.ps);
01607     ExecAssignProjectionInfo(&mergestate->js.ps, NULL);
01608 
01609     /*
01610      * preprocess the merge clauses
01611      */
01612     mergestate->mj_NumClauses = list_length(node->mergeclauses);
01613     mergestate->mj_Clauses = MJExamineQuals(node->mergeclauses,
01614                                             node->mergeFamilies,
01615                                             node->mergeCollations,
01616                                             node->mergeStrategies,
01617                                             node->mergeNullsFirst,
01618                                             (PlanState *) mergestate);
01619 
01620     /*
01621      * initialize join state
01622      */
01623     mergestate->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
01624     mergestate->js.ps.ps_TupFromTlist = false;
01625     mergestate->mj_MatchedOuter = false;
01626     mergestate->mj_MatchedInner = false;
01627     mergestate->mj_OuterTupleSlot = NULL;
01628     mergestate->mj_InnerTupleSlot = NULL;
01629 
01630     /*
01631      * initialization successful
01632      */
01633     MJ1_printf("ExecInitMergeJoin: %s\n",
01634                "node initialized");
01635 
01636     return mergestate;
01637 }
01638 
01639 /* ----------------------------------------------------------------
01640  *      ExecEndMergeJoin
01641  *
01642  * old comments
01643  *      frees storage allocated through C routines.
01644  * ----------------------------------------------------------------
01645  */
01646 void
01647 ExecEndMergeJoin(MergeJoinState *node)
01648 {
01649     MJ1_printf("ExecEndMergeJoin: %s\n",
01650                "ending node processing");
01651 
01652     /*
01653      * Free the exprcontext
01654      */
01655     ExecFreeExprContext(&node->js.ps);
01656 
01657     /*
01658      * clean out the tuple table
01659      */
01660     ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
01661     ExecClearTuple(node->mj_MarkedTupleSlot);
01662 
01663     /*
01664      * shut down the subplans
01665      */
01666     ExecEndNode(innerPlanState(node));
01667     ExecEndNode(outerPlanState(node));
01668 
01669     MJ1_printf("ExecEndMergeJoin: %s\n",
01670                "node processing ended");
01671 }
01672 
01673 void
01674 ExecReScanMergeJoin(MergeJoinState *node)
01675 {
01676     ExecClearTuple(node->mj_MarkedTupleSlot);
01677 
01678     node->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
01679     node->js.ps.ps_TupFromTlist = false;
01680     node->mj_MatchedOuter = false;
01681     node->mj_MatchedInner = false;
01682     node->mj_OuterTupleSlot = NULL;
01683     node->mj_InnerTupleSlot = NULL;
01684 
01685     /*
01686      * if chgParam of subnodes is not null then plans will be re-scanned by
01687      * first ExecProcNode.
01688      */
01689     if (node->js.ps.lefttree->chgParam == NULL)
01690         ExecReScan(node->js.ps.lefttree);
01691     if (node->js.ps.righttree->chgParam == NULL)
01692         ExecReScan(node->js.ps.righttree);
01693 
01694 }