granicus.if.org Git - postgresql/blob - src/backend/executor/nodeMergejoin.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeMergejoin.c
   4  *        routines supporting merge joins
   5  *
   6  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/executor/nodeMergejoin.c,v 1.63 2003/11/29 19:51:48 pgsql Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 /*
  16  * INTERFACE ROUTINES
  17  *              ExecMergeJoin                   mergejoin outer and inner relations.
  18  *              ExecInitMergeJoin               creates and initializes run time states
  19  *              ExecEndMergeJoin                cleans up the node.
  20  *
  21  * NOTES
  22  *              Essential operation of the merge join algorithm is as follows:
  23  *
  24  *              Join {                                                                                             -
  25  *                      get initial outer and inner tuples                              INITIALIZE
  26  *                      Skip Inner                                                                              SKIPINNER
  27  *                      mark inner position                                                             JOINMARK
  28  *                      do forever {                                                                       -
  29  *                              while (outer == inner) {                                        JOINTEST
  30  *                                      join tuples                                                             JOINTUPLES
  31  *                                      advance inner position                                  NEXTINNER
  32  *                              }                                                                                          -
  33  *                              advance outer position                                          NEXTOUTER
  34  *                              if (outer == mark) {                                            TESTOUTER
  35  *                                      restore inner position to mark                  TESTOUTER
  36  *                                      continue                                                                   -
  37  *                              } else {                                                                           -
  38  *                                      Skip Outer                                                              SKIPOUTER
  39  *                                      mark inner position                                             JOINMARK
  40  *                              }                                                                                          -
  41  *                      }                                                                                                  -
  42  *              }                                                                                                          -
  43  *
  44  *              Skip Outer {                                                                            SKIPOUTER_BEGIN
  45  *                      if (inner == outer) Join Tuples                                 JOINTUPLES
  46  *                      while (outer < inner)                                                   SKIPOUTER_TEST
  47  *                              advance outer                                                           SKIPOUTER_ADVANCE
  48  *                      if (outer > inner)                                                              SKIPOUTER_TEST
  49  *                              Skip Inner                                                                      SKIPINNER
  50  *              }                                                                                                          -
  51  *
  52  *              Skip Inner {                                                                            SKIPINNER_BEGIN
  53  *                      if (inner == outer) Join Tuples                                 JOINTUPLES
  54  *                      while (outer > inner)                                                   SKIPINNER_TEST
  55  *                              advance inner                                                           SKIPINNER_ADVANCE
  56  *                      if (outer < inner)                                                              SKIPINNER_TEST
  57  *                              Skip Outer                                                                      SKIPOUTER
  58  *              }                                                                                                          -
  59  *
  60  *              The merge join operation is coded in the fashion
  61  *              of a state machine.  At each state, we do something and then
  62  *              proceed to another state.  This state is stored in the node's
  63  *              execution state information and is preserved across calls to
  64  *              ExecMergeJoin. -cim 10/31/89
  65  *
  66  */
  67 #include "postgres.h"
  68
  69 #include "access/heapam.h"
  70 #include "access/printtup.h"
  71 #include "catalog/pg_operator.h"
  72 #include "executor/execdebug.h"
  73 #include "executor/execdefs.h"
  74 #include "executor/nodeMergejoin.h"
  75 #include "utils/lsyscache.h"
  76 #include "utils/syscache.h"
  77
  78
  79 static bool MergeCompare(List *eqQual, List *compareQual, ExprContext *econtext);
  80
  81 #define MarkInnerTuple(innerTupleSlot, mergestate) \
  82 ( \
  83         ExecStoreTuple(heap_copytuple((innerTupleSlot)->val), \
  84                                    (mergestate)->mj_MarkedTupleSlot, \
  85                                    InvalidBuffer, \
  86                                    true) \
  87 )
  88
  89
  90 /* ----------------------------------------------------------------
  91  *              MJFormSkipQuals
  92  *
  93  *              This takes the mergeclause which is a qualification of the
  94  *              form ((= expr expr) (= expr expr) ...) and forms new lists
  95  *              of the forms ((< expr expr) (< expr expr) ...) and
  96  *              ((> expr expr) (> expr expr) ...).      These lists will be used
  97  *              by ExecMergeJoin() to determine if we should skip tuples.
  98  *              (We expect there to be suitable operators because the "=" operators
  99  *              were marked mergejoinable; however, there might be a different
 100  *              one needed in each qual clause.)
 101  * ----------------------------------------------------------------
 102  */
 103 static void
 104 MJFormSkipQuals(List *qualList, List **ltQuals, List **gtQuals,
 105                                 PlanState *parent)
 106 {
 107         List       *ltexprs,
 108                            *gtexprs,
 109                            *ltcdr,
 110                            *gtcdr;
 111
 112         /*
 113          * Make modifiable copies of the qualList.
 114          */
 115         ltexprs = (List *) copyObject((Node *) qualList);
 116         gtexprs = (List *) copyObject((Node *) qualList);
 117
 118         /*
 119          * Scan both lists in parallel, so that we can update the operators
 120          * with the minimum number of syscache searches.
 121          */
 122         ltcdr = ltexprs;
 123         foreach(gtcdr, gtexprs)
 124         {
 125                 OpExpr     *ltop = (OpExpr *) lfirst(ltcdr);
 126                 OpExpr     *gtop = (OpExpr *) lfirst(gtcdr);
 127
 128                 /*
 129                  * The two ops should be identical, so use either one for lookup.
 130                  */
 131                 if (!IsA(ltop, OpExpr))
 132                         elog(ERROR, "mergejoin clause is not an OpExpr");
 133
 134                 /*
 135                  * Lookup the operators, and replace the data in the copied
 136                  * operator nodes.
 137                  */
 138                 op_mergejoin_crossops(ltop->opno,
 139                                                           &ltop->opno,
 140                                                           &gtop->opno,
 141                                                           &ltop->opfuncid,
 142                                                           &gtop->opfuncid);
 143
 144                 ltcdr = lnext(ltcdr);
 145         }
 146
 147         /*
 148          * Prepare both lists for execution.
 149          */
 150         *ltQuals = (List *) ExecInitExpr((Expr *) ltexprs, parent);
 151         *gtQuals = (List *) ExecInitExpr((Expr *) gtexprs, parent);
 152 }
 153
 154 /* ----------------------------------------------------------------
 155  *              MergeCompare
 156  *
 157  *              Compare the keys according to 'compareQual' which is of the
 158  *              form: { (key1a > key2a) (key1b > key2b) ... }.
 159  *
 160  *              (actually, it could also be of the form (key1a < key2a)...)
 161  *
 162  *              This is different from calling ExecQual because ExecQual returns
 163  *              true only if ALL the comparison clauses are satisfied.
 164  *              However, there is an order of significance among the keys with
 165  *              the first keys being most significant. Therefore, the clauses
 166  *              are evaluated in order and the 'compareQual' is satisfied
 167  *              if (key1i > key2i) is true and (key1j = key2j) for 0 < j < i.
 168  *              We use the original mergeclause items to detect equality.
 169  * ----------------------------------------------------------------
 170  */
 171 static bool
 172 MergeCompare(List *eqQual, List *compareQual, ExprContext *econtext)
 173 {
 174         bool            result;
 175         MemoryContext oldContext;
 176         List       *clause;
 177         List       *eqclause;
 178
 179         /*
 180          * Do expression eval in short-lived context.
 181          */
 182         oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 183
 184         /*
 185          * for each pair of clauses, test them until our compare conditions
 186          * are satisfied. if we reach the end of the list, none of our key
 187          * greater-than conditions were satisfied so we return false.
 188          */
 189         result = false;                         /* assume 'false' result */
 190
 191         eqclause = eqQual;
 192         foreach(clause, compareQual)
 193         {
 194                 Datum           const_value;
 195                 bool            isNull;
 196
 197                 /*
 198                  * first test if our compare clause is satisfied. if so then
 199                  * return true.
 200                  *
 201                  * A NULL result is considered false.
 202                  */
 203                 const_value = ExecEvalExpr((ExprState *) lfirst(clause),
 204                                                                    econtext,
 205                                                                    &isNull,
 206                                                                    NULL);
 207
 208                 if (DatumGetBool(const_value) && !isNull)
 209                 {
 210                         result = true;
 211                         break;
 212                 }
 213
 214                 /*-----------
 215                  * ok, the compare clause failed so we test if the keys are
 216                  * equal... if key1 != key2, we return false. otherwise
 217                  * key1 = key2 so we move on to the next pair of keys.
 218                  *-----------
 219                  */
 220                 const_value = ExecEvalExpr((ExprState *) lfirst(eqclause),
 221                                                                    econtext,
 222                                                                    &isNull,
 223                                                                    NULL);
 224
 225                 if (!DatumGetBool(const_value) || isNull)
 226                         break;                          /* return false */
 227
 228                 eqclause = lnext(eqclause);
 229         }
 230
 231         MemoryContextSwitchTo(oldContext);
 232
 233         return result;
 234 }
 235
 236 /* ----------------------------------------------------------------
 237  *              ExecMergeTupleDump
 238  *
 239  *              This function is called through the MJ_dump() macro
 240  *              when EXEC_MERGEJOINDEBUG is defined
 241  * ----------------------------------------------------------------
 242  */
 243 #ifdef EXEC_MERGEJOINDEBUG
 244
 245 static void
 246 ExecMergeTupleDumpOuter(MergeJoinState *mergestate)
 247 {
 248         TupleTableSlot *outerSlot = mergestate->mj_OuterTupleSlot;
 249
 250         printf("==== outer tuple ====\n");
 251         if (TupIsNull(outerSlot))
 252                 printf("(nil)\n");
 253         else
 254                 MJ_debugtup(outerSlot->val,
 255                                         outerSlot->ttc_tupleDescriptor);
 256 }
 257
 258 static void
 259 ExecMergeTupleDumpInner(MergeJoinState *mergestate)
 260 {
 261         TupleTableSlot *innerSlot = mergestate->mj_InnerTupleSlot;
 262
 263         printf("==== inner tuple ====\n");
 264         if (TupIsNull(innerSlot))
 265                 printf("(nil)\n");
 266         else
 267                 MJ_debugtup(innerSlot->val,
 268                                         innerSlot->ttc_tupleDescriptor);
 269 }
 270
 271 static void
 272 ExecMergeTupleDumpMarked(MergeJoinState *mergestate)
 273 {
 274         TupleTableSlot *markedSlot = mergestate->mj_MarkedTupleSlot;
 275
 276         printf("==== marked tuple ====\n");
 277         if (TupIsNull(markedSlot))
 278                 printf("(nil)\n");
 279         else
 280                 MJ_debugtup(markedSlot->val,
 281                                         markedSlot->ttc_tupleDescriptor);
 282 }
 283
 284 static void
 285 ExecMergeTupleDump(MergeJoinState *mergestate)
 286 {
 287         printf("******** ExecMergeTupleDump ********\n");
 288
 289         ExecMergeTupleDumpOuter(mergestate);
 290         ExecMergeTupleDumpInner(mergestate);
 291         ExecMergeTupleDumpMarked(mergestate);
 292
 293         printf("******** \n");
 294 }
 295 #endif
 296
 297 /* ----------------------------------------------------------------
 298  *              ExecMergeJoin
 299  *
 300  * old comments
 301  *              Details of the merge-join routines:
 302  *
 303  *              (1) ">" and "<" operators
 304  *
 305  *              Merge-join is done by joining the inner and outer tuples satisfying
 306  *              the join clauses of the form ((= outerKey innerKey) ...).
 307  *              The join clauses is provided by the query planner and may contain
 308  *              more than one (= outerKey innerKey) clauses (for composite key).
 309  *
 310  *              However, the query executor needs to know whether an outer
 311  *              tuple is "greater/smaller" than an inner tuple so that it can
 312  *              "synchronize" the two relations. For e.g., consider the following
 313  *              relations:
 314  *
 315  *                              outer: (0 ^1 1 2 5 5 5 6 6 7)   current tuple: 1
 316  *                              inner: (1 ^3 5 5 5 5 6)                 current tuple: 3
 317  *
 318  *              To continue the merge-join, the executor needs to scan both inner
 319  *              and outer relations till the matching tuples 5. It needs to know
 320  *              that currently inner tuple 3 is "greater" than outer tuple 1 and
 321  *              therefore it should scan the outer relation first to find a
 322  *              matching tuple and so on.
 323  *
 324  *              Therefore, when initializing the merge-join node, the executor
 325  *              creates the "greater/smaller" clause by substituting the "="
 326  *              operator in the join clauses with the corresponding ">" operator.
 327  *              The opposite "smaller/greater" clause is formed by substituting "<".
 328  *
 329  *              Note: prior to v6.5, the relational clauses were formed using the
 330  *              sort op used to sort the inner relation, which of course would fail
 331  *              if the outer and inner keys were of different data types.
 332  *              In the current code, we instead assume that operators named "<" and ">"
 333  *              will do the right thing.  This should be true since the mergejoin "="
 334  *              operator's pg_operator entry will have told the planner to sort by
 335  *              "<" for each of the left and right sides.
 336  *
 337  *              (2) repositioning inner "cursor"
 338  *
 339  *              Consider the above relations and suppose that the executor has
 340  *              just joined the first outer "5" with the last inner "5". The
 341  *              next step is of course to join the second outer "5" with all
 342  *              the inner "5's". This requires repositioning the inner "cursor"
 343  *              to point at the first inner "5". This is done by "marking" the
 344  *              first inner 5 and restore the "cursor" to it before joining
 345  *              with the second outer 5. The access method interface provides
 346  *              routines to mark and restore to a tuple.
 347  * ----------------------------------------------------------------
 348  */
 349 TupleTableSlot *
 350 ExecMergeJoin(MergeJoinState *node)
 351 {
 352         EState     *estate;
 353         ScanDirection direction;
 354         List       *innerSkipQual;
 355         List       *outerSkipQual;
 356         List       *mergeclauses;
 357         List       *joinqual;
 358         List       *otherqual;
 359         bool            qualResult;
 360         bool            compareResult;
 361         PlanState  *innerPlan;
 362         TupleTableSlot *innerTupleSlot;
 363         PlanState  *outerPlan;
 364         TupleTableSlot *outerTupleSlot;
 365         ExprContext *econtext;
 366         bool            doFillOuter;
 367         bool            doFillInner;
 368
 369         /*
 370          * get information from node
 371          */
 372         estate = node->js.ps.state;
 373         direction = estate->es_direction;
 374         innerPlan = innerPlanState(node);
 375         outerPlan = outerPlanState(node);
 376         econtext = node->js.ps.ps_ExprContext;
 377         mergeclauses = node->mergeclauses;
 378         joinqual = node->js.joinqual;
 379         otherqual = node->js.ps.qual;
 380
 381         switch (node->js.jointype)
 382         {
 383                 case JOIN_INNER:
 384                 case JOIN_IN:
 385                         doFillOuter = false;
 386                         doFillInner = false;
 387                         break;
 388                 case JOIN_LEFT:
 389                         doFillOuter = true;
 390                         doFillInner = false;
 391                         break;
 392                 case JOIN_FULL:
 393                         doFillOuter = true;
 394                         doFillInner = true;
 395                         break;
 396                 case JOIN_RIGHT:
 397                         doFillOuter = false;
 398                         doFillInner = true;
 399                         break;
 400                 default:
 401                         elog(ERROR, "unrecognized join type: %d",
 402                                  (int) node->js.jointype);
 403                         doFillOuter = false;    /* keep compiler quiet */
 404                         doFillInner = false;
 405                         break;
 406         }
 407
 408         if (ScanDirectionIsForward(direction))
 409         {
 410                 outerSkipQual = node->mj_OuterSkipQual;
 411                 innerSkipQual = node->mj_InnerSkipQual;
 412         }
 413         else
 414         {
 415                 outerSkipQual = node->mj_InnerSkipQual;
 416                 innerSkipQual = node->mj_OuterSkipQual;
 417         }
 418
 419         /*
 420          * Check to see if we're still projecting out tuples from a previous
 421          * join tuple (because there is a function-returning-set in the
 422          * projection expressions).  If so, try to project another one.
 423          */
 424         if (node->js.ps.ps_TupFromTlist)
 425         {
 426                 TupleTableSlot *result;
 427                 ExprDoneCond isDone;
 428
 429                 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
 430                 if (isDone == ExprMultipleResult)
 431                         return result;
 432                 /* Done with that source tuple... */
 433                 node->js.ps.ps_TupFromTlist = false;
 434         }
 435
 436         /*
 437          * Reset per-tuple memory context to free any expression evaluation
 438          * storage allocated in the previous tuple cycle.  Note this can't
 439          * happen until we're done projecting out tuples from a join tuple.
 440          */
 441         ResetExprContext(econtext);
 442
 443         /*
 444          * ok, everything is setup.. let's go to work
 445          */
 446         for (;;)
 447         {
 448                 /*
 449                  * get the current state of the join and do things accordingly.
 450                  * Note: The join states are highlighted with 32-* comments for
 451                  * improved readability.
 452                  */
 453                 MJ_dump(node);
 454
 455                 switch (node->mj_JoinState)
 456                 {
 457                                 /*
 458                                  * EXEC_MJ_INITIALIZE means that this is the first time
 459                                  * ExecMergeJoin() has been called and so we have to fetch
 460                                  * the first tuple for both outer and inner subplans. If
 461                                  * we fail to get a tuple here, then that subplan is
 462                                  * empty, and we either end the join or go to one of the
 463                                  * fill-remaining-tuples states.
 464                                  */
 465                         case EXEC_MJ_INITIALIZE:
 466                                 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE\n");
 467
 468                                 outerTupleSlot = ExecProcNode(outerPlan);
 469                                 node->mj_OuterTupleSlot = outerTupleSlot;
 470                                 if (TupIsNull(outerTupleSlot))
 471                                 {
 472                                         MJ_printf("ExecMergeJoin: outer subplan is empty\n");
 473                                         if (doFillInner)
 474                                         {
 475                                                 /*
 476                                                  * Need to emit right-join tuples for remaining
 477                                                  * inner tuples.  We set MatchedInner = true to
 478                                                  * force the ENDOUTER state to advance inner.
 479                                                  */
 480                                                 node->mj_JoinState = EXEC_MJ_ENDOUTER;
 481                                                 node->mj_MatchedInner = true;
 482                                                 break;
 483                                         }
 484                                         /* Otherwise we're done. */
 485                                         return NULL;
 486                                 }
 487
 488                                 innerTupleSlot = ExecProcNode(innerPlan);
 489                                 node->mj_InnerTupleSlot = innerTupleSlot;
 490                                 if (TupIsNull(innerTupleSlot))
 491                                 {
 492                                         MJ_printf("ExecMergeJoin: inner subplan is empty\n");
 493                                         if (doFillOuter)
 494                                         {
 495                                                 /*
 496                                                  * Need to emit left-join tuples for all outer
 497                                                  * tuples, including the one we just fetched.  We
 498                                                  * set MatchedOuter = false to force the ENDINNER
 499                                                  * state to emit this tuple before advancing
 500                                                  * outer.
 501                                                  */
 502                                                 node->mj_JoinState = EXEC_MJ_ENDINNER;
 503                                                 node->mj_MatchedOuter = false;
 504                                                 break;
 505                                         }
 506                                         /* Otherwise we're done. */
 507                                         return NULL;
 508                                 }
 509
 510                                 /*
 511                                  * OK, we have the initial tuples.      Begin by skipping
 512                                  * unmatched inner tuples.
 513                                  */
 514                                 node->mj_JoinState = EXEC_MJ_SKIPINNER_BEGIN;
 515                                 break;
 516
 517                                 /*
 518                                  * EXEC_MJ_JOINMARK means we have just found a new outer
 519                                  * tuple and a possible matching inner tuple. This is the
 520                                  * case after the INITIALIZE, SKIPOUTER or SKIPINNER
 521                                  * states.
 522                                  */
 523                         case EXEC_MJ_JOINMARK:
 524                                 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINMARK\n");
 525
 526                                 ExecMarkPos(innerPlan);
 527
 528                                 MarkInnerTuple(node->mj_InnerTupleSlot, node);
 529
 530                                 node->mj_JoinState = EXEC_MJ_JOINTEST;
 531                                 break;
 532
 533                                 /*
 534                                  * EXEC_MJ_JOINTEST means we have two tuples which might
 535                                  * satisfy the merge clause, so we test them.
 536                                  *
 537                                  * If they do satisfy, then we join them and move on to the
 538                                  * next inner tuple (EXEC_MJ_JOINTUPLES).
 539                                  *
 540                                  * If they do not satisfy then advance to next outer tuple.
 541                                  */
 542                         case EXEC_MJ_JOINTEST:
 543                                 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTEST\n");
 544
 545                                 ResetExprContext(econtext);
 546
 547                                 outerTupleSlot = node->mj_OuterTupleSlot;
 548                                 econtext->ecxt_outertuple = outerTupleSlot;
 549                                 innerTupleSlot = node->mj_InnerTupleSlot;
 550                                 econtext->ecxt_innertuple = innerTupleSlot;
 551
 552                                 qualResult = ExecQual(mergeclauses, econtext, false);
 553                                 MJ_DEBUG_QUAL(mergeclauses, qualResult);
 554
 555                                 if (qualResult)
 556                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
 557                                 else
 558                                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 559                                 break;
 560
 561                                 /*
 562                                  * EXEC_MJ_JOINTUPLES means we have two tuples which
 563                                  * satisfied the merge clause so we join them and then
 564                                  * proceed to get the next inner tuple (EXEC_NEXT_INNER).
 565                                  */
 566                         case EXEC_MJ_JOINTUPLES:
 567                                 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n");
 568
 569                                 node->mj_JoinState = EXEC_MJ_NEXTINNER;
 570
 571                                 /*
 572                                  * Check the extra qual conditions to see if we actually
 573                                  * want to return this join tuple.      If not, can proceed
 574                                  * with merge.  We must distinguish the additional
 575                                  * joinquals (which must pass to consider the tuples
 576                                  * "matched" for outer-join logic) from the otherquals
 577                                  * (which must pass before we actually return the tuple).
 578                                  *
 579                                  * We don't bother with a ResetExprContext here, on the
 580                                  * assumption that we just did one before checking the
 581                                  * merge qual.  One per tuple should be sufficient.  Also,
 582                                  * the econtext's tuple pointers were set up before
 583                                  * checking the merge qual, so we needn't do it again.
 584                                  */
 585                                 if (node->js.jointype == JOIN_IN &&
 586                                         node->mj_MatchedOuter)
 587                                         qualResult = false;
 588                                 else
 589                                 {
 590                                         qualResult = (joinqual == NIL ||
 591                                                                   ExecQual(joinqual, econtext, false));
 592                                         MJ_DEBUG_QUAL(joinqual, qualResult);
 593                                 }
 594
 595                                 if (qualResult)
 596                                 {
 597                                         node->mj_MatchedOuter = true;
 598                                         node->mj_MatchedInner = true;
 599
 600                                         qualResult = (otherqual == NIL ||
 601                                                                   ExecQual(otherqual, econtext, false));
 602                                         MJ_DEBUG_QUAL(otherqual, qualResult);
 603
 604                                         if (qualResult)
 605                                         {
 606                                                 /*
 607                                                  * qualification succeeded.  now form the desired
 608                                                  * projection tuple and return the slot containing
 609                                                  * it.
 610                                                  */
 611                                                 TupleTableSlot *result;
 612                                                 ExprDoneCond isDone;
 613
 614                                                 MJ_printf("ExecMergeJoin: returning tuple\n");
 615
 616                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
 617                                                                                          &isDone);
 618
 619                                                 if (isDone != ExprEndResult)
 620                                                 {
 621                                                         node->js.ps.ps_TupFromTlist =
 622                                                                 (isDone == ExprMultipleResult);
 623                                                         return result;
 624                                                 }
 625                                         }
 626                                 }
 627                                 break;
 628
 629                                 /*
 630                                  * EXEC_MJ_NEXTINNER means advance the inner scan to the
 631                                  * next tuple. If the tuple is not nil, we then proceed to
 632                                  * test it against the join qualification.
 633                                  *
 634                                  * Before advancing, we check to see if we must emit an
 635                                  * outer-join fill tuple for this inner tuple.
 636                                  */
 637                         case EXEC_MJ_NEXTINNER:
 638                                 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n");
 639
 640                                 if (doFillInner && !node->mj_MatchedInner)
 641                                 {
 642                                         /*
 643                                          * Generate a fake join tuple with nulls for the outer
 644                                          * tuple, and return it if it passes the non-join
 645                                          * quals.
 646                                          */
 647                                         node->mj_MatchedInner = true;           /* do it only once */
 648
 649                                         ResetExprContext(econtext);
 650
 651                                         outerTupleSlot = node->mj_NullOuterTupleSlot;
 652                                         econtext->ecxt_outertuple = outerTupleSlot;
 653                                         innerTupleSlot = node->mj_InnerTupleSlot;
 654                                         econtext->ecxt_innertuple = innerTupleSlot;
 655
 656                                         if (ExecQual(otherqual, econtext, false))
 657                                         {
 658                                                 /*
 659                                                  * qualification succeeded.  now form the desired
 660                                                  * projection tuple and return the slot containing
 661                                                  * it.
 662                                                  */
 663                                                 TupleTableSlot *result;
 664                                                 ExprDoneCond isDone;
 665
 666                                                 MJ_printf("ExecMergeJoin: returning fill tuple\n");
 667
 668                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
 669                                                                                          &isDone);
 670
 671                                                 if (isDone != ExprEndResult)
 672                                                 {
 673                                                         node->js.ps.ps_TupFromTlist =
 674                                                                 (isDone == ExprMultipleResult);
 675                                                         return result;
 676                                                 }
 677                                         }
 678                                 }
 679
 680                                 /*
 681                                  * now we get the next inner tuple, if any
 682                                  */
 683                                 innerTupleSlot = ExecProcNode(innerPlan);
 684                                 node->mj_InnerTupleSlot = innerTupleSlot;
 685                                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
 686                                 node->mj_MatchedInner = false;
 687
 688                                 if (TupIsNull(innerTupleSlot))
 689                                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 690                                 else
 691                                         node->mj_JoinState = EXEC_MJ_JOINTEST;
 692                                 break;
 693
 694                                 /*-------------------------------------------
 695                                  * EXEC_MJ_NEXTOUTER means
 696                                  *
 697                                  *                              outer inner
 698                                  * outer tuple -  5             5  - marked tuple
 699                                  *                                5             5
 700                                  *                                6             6  - inner tuple
 701                                  *                                7             7
 702                                  *
 703                                  * we know we just bumped into the
 704                                  * first inner tuple > current outer tuple
 705                                  * so get a new outer tuple and then
 706                                  * proceed to test it against the marked tuple
 707                                  * (EXEC_MJ_TESTOUTER)
 708                                  *
 709                                  * Before advancing, we check to see if we must emit an
 710                                  * outer-join fill tuple for this outer tuple.
 711                                  *------------------------------------------------
 712                                  */
 713                         case EXEC_MJ_NEXTOUTER:
 714                                 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n");
 715
 716                                 if (doFillOuter && !node->mj_MatchedOuter)
 717                                 {
 718                                         /*
 719                                          * Generate a fake join tuple with nulls for the inner
 720                                          * tuple, and return it if it passes the non-join
 721                                          * quals.
 722                                          */
 723                                         node->mj_MatchedOuter = true;           /* do it only once */
 724
 725                                         ResetExprContext(econtext);
 726
 727                                         outerTupleSlot = node->mj_OuterTupleSlot;
 728                                         econtext->ecxt_outertuple = outerTupleSlot;
 729                                         innerTupleSlot = node->mj_NullInnerTupleSlot;
 730                                         econtext->ecxt_innertuple = innerTupleSlot;
 731
 732                                         if (ExecQual(otherqual, econtext, false))
 733                                         {
 734                                                 /*
 735                                                  * qualification succeeded.  now form the desired
 736                                                  * projection tuple and return the slot containing
 737                                                  * it.
 738                                                  */
 739                                                 TupleTableSlot *result;
 740                                                 ExprDoneCond isDone;
 741
 742                                                 MJ_printf("ExecMergeJoin: returning fill tuple\n");
 743
 744                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
 745                                                                                          &isDone);
 746
 747                                                 if (isDone != ExprEndResult)
 748                                                 {
 749                                                         node->js.ps.ps_TupFromTlist =
 750                                                                 (isDone == ExprMultipleResult);
 751                                                         return result;
 752                                                 }
 753                                         }
 754                                 }
 755
 756                                 /*
 757                                  * now we get the next outer tuple, if any
 758                                  */
 759                                 outerTupleSlot = ExecProcNode(outerPlan);
 760                                 node->mj_OuterTupleSlot = outerTupleSlot;
 761                                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
 762                                 node->mj_MatchedOuter = false;
 763
 764                                 /*
 765                                  * if the outer tuple is null then we are done with the
 766                                  * join, unless we have inner tuples we need to null-fill.
 767                                  */
 768                                 if (TupIsNull(outerTupleSlot))
 769                                 {
 770                                         MJ_printf("ExecMergeJoin: end of outer subplan\n");
 771                                         innerTupleSlot = node->mj_InnerTupleSlot;
 772                                         if (doFillInner && !TupIsNull(innerTupleSlot))
 773                                         {
 774                                                 /*
 775                                                  * Need to emit right-join tuples for remaining
 776                                                  * inner tuples.
 777                                                  */
 778                                                 node->mj_JoinState = EXEC_MJ_ENDOUTER;
 779                                                 break;
 780                                         }
 781                                         /* Otherwise we're done. */
 782                                         return NULL;
 783                                 }
 784
 785                                 node->mj_JoinState = EXEC_MJ_TESTOUTER;
 786                                 break;
 787
 788                                 /*--------------------------------------------------------
 789                                  * EXEC_MJ_TESTOUTER If the new outer tuple and the marked
 790                                  * tuple satisfy the merge clause then we know we have
 791                                  * duplicates in the outer scan so we have to restore the
 792                                  * inner scan to the marked tuple and proceed to join the
 793                                  * new outer tuples with the inner tuples (EXEC_MJ_JOINTEST)
 794                                  *
 795                                  * This is the case when
 796                                  *                                                outer inner
 797                                  *                                                      4         5  - marked tuple
 798                                  *                       outer tuple -  5         5
 799                                  *               new outer tuple -      5         5
 800                                  *                                                      6         8  - inner tuple
 801                                  *                                                      7        12
 802                                  *
 803                                  *                              new outer tuple = marked tuple
 804                                  *
 805                                  *              If the outer tuple fails the test, then we know we have
 806                                  *              to proceed to skip outer tuples until outer >= inner
 807                                  *              (EXEC_MJ_SKIPOUTER).
 808                                  *
 809                                  *              This is the case when
 810                                  *
 811                                  *                                                outer inner
 812                                  *                                                      5         5  - marked tuple
 813                                  *                       outer tuple -  5         5
 814                                  *               new outer tuple -      6         8  - inner tuple
 815                                  *                                                      7        12
 816                                  *
 817                                  *
 818                                  *               new outer tuple > marked tuple
 819                                  *
 820                                  *---------------------------------------------------------
 821                                  */
 822                         case EXEC_MJ_TESTOUTER:
 823                                 MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
 824
 825                                 /*
 826                                  * here we compare the outer tuple with the marked inner
 827                                  * tuple
 828                                  */
 829                                 ResetExprContext(econtext);
 830
 831                                 outerTupleSlot = node->mj_OuterTupleSlot;
 832                                 econtext->ecxt_outertuple = outerTupleSlot;
 833                                 innerTupleSlot = node->mj_MarkedTupleSlot;
 834                                 econtext->ecxt_innertuple = innerTupleSlot;
 835
 836                                 qualResult = ExecQual(mergeclauses, econtext, false);
 837                                 MJ_DEBUG_QUAL(mergeclauses, qualResult);
 838
 839                                 if (qualResult)
 840                                 {
 841                                         /*
 842                                          * the merge clause matched so now we restore the
 843                                          * inner scan position to the first mark, and loop
 844                                          * back to JOINTEST.  Actually, since we know the
 845                                          * mergeclause matches, we can skip JOINTEST and go
 846                                          * straight to JOINTUPLES.
 847                                          *
 848                                          * NOTE: we do not need to worry about the MatchedInner
 849                                          * state for the rescanned inner tuples.  We know all
 850                                          * of them will match this new outer tuple and
 851                                          * therefore won't be emitted as fill tuples.  This
 852                                          * works *only* because we require the extra joinquals
 853                                          * to be nil when doing a right or full join ---
 854                                          * otherwise some of the rescanned tuples might fail
 855                                          * the extra joinquals.
 856                                          */
 857                                         ExecRestrPos(innerPlan);
 858                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
 859                                 }
 860                                 else
 861                                 {
 862                                         /* ----------------
 863                                          *      if the inner tuple was nil and the new outer
 864                                          *      tuple didn't match the marked outer tuple then
 865                                          *      we have the case:
 866                                          *
 867                                          *                       outer inner
 868                                          *                         4     4      - marked tuple
 869                                          * new outer - 5         4
 870                                          *                         6    nil - inner tuple
 871                                          *                         7
 872                                          *
 873                                          *      which means that all subsequent outer tuples will be
 874                                          *      larger than our marked inner tuples.  So we're done.
 875                                          * ----------------
 876                                          */
 877                                         innerTupleSlot = node->mj_InnerTupleSlot;
 878                                         if (TupIsNull(innerTupleSlot))
 879                                         {
 880                                                 if (doFillOuter)
 881                                                 {
 882                                                         /*
 883                                                          * Need to emit left-join tuples for remaining
 884                                                          * outer tuples.
 885                                                          */
 886                                                         node->mj_JoinState = EXEC_MJ_ENDINNER;
 887                                                         break;
 888                                                 }
 889                                                 /* Otherwise we're done. */
 890                                                 return NULL;
 891                                         }
 892
 893                                         /* continue on to skip outer tuples */
 894                                         node->mj_JoinState = EXEC_MJ_SKIPOUTER_BEGIN;
 895                                 }
 896                                 break;
 897
 898                                 /*----------------------------------------------------------
 899                                  * EXEC_MJ_SKIPOUTER means skip over tuples in the outer plan
 900                                  * until we find an outer tuple >= current inner tuple.
 901                                  *
 902                                  * For example:
 903                                  *
 904                                  *                              outer inner
 905                                  *                                5             5
 906                                  *                                5             5
 907                                  * outer tuple -  6             8  - inner tuple
 908                                  *                                7    12
 909                                  *                                8    14
 910                                  *
 911                                  * we have to advance the outer scan
 912                                  * until we find the outer 8.
 913                                  *
 914                                  * To avoid redundant tests, we divide this into three
 915                                  * sub-states: BEGIN, TEST, ADVANCE.
 916                                  *----------------------------------------------------------
 917                                  */
 918                         case EXEC_MJ_SKIPOUTER_BEGIN:
 919                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_BEGIN\n");
 920
 921                                 /*
 922                                  * before we advance, make sure the current tuples do not
 923                                  * satisfy the mergeclauses.  If they do, then we update
 924                                  * the marked tuple and go join them.
 925                                  */
 926                                 ResetExprContext(econtext);
 927
 928                                 outerTupleSlot = node->mj_OuterTupleSlot;
 929                                 econtext->ecxt_outertuple = outerTupleSlot;
 930                                 innerTupleSlot = node->mj_InnerTupleSlot;
 931                                 econtext->ecxt_innertuple = innerTupleSlot;
 932
 933                                 qualResult = ExecQual(mergeclauses, econtext, false);
 934                                 MJ_DEBUG_QUAL(mergeclauses, qualResult);
 935
 936                                 if (qualResult)
 937                                 {
 938                                         ExecMarkPos(innerPlan);
 939
 940                                         MarkInnerTuple(innerTupleSlot, node);
 941
 942                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
 943                                         break;
 944                                 }
 945
 946                                 node->mj_JoinState = EXEC_MJ_SKIPOUTER_TEST;
 947                                 break;
 948
 949                         case EXEC_MJ_SKIPOUTER_TEST:
 950                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_TEST\n");
 951
 952                                 /*
 953                                  * ok, now test the skip qualification
 954                                  */
 955                                 outerTupleSlot = node->mj_OuterTupleSlot;
 956                                 econtext->ecxt_outertuple = outerTupleSlot;
 957                                 innerTupleSlot = node->mj_InnerTupleSlot;
 958                                 econtext->ecxt_innertuple = innerTupleSlot;
 959
 960                                 compareResult = MergeCompare(mergeclauses,
 961                                                                                          outerSkipQual,
 962                                                                                          econtext);
 963
 964                                 MJ_DEBUG_MERGE_COMPARE(outerSkipQual, compareResult);
 965
 966                                 /*
 967                                  * compareResult is true as long as we should continue
 968                                  * skipping outer tuples.
 969                                  */
 970                                 if (compareResult)
 971                                 {
 972                                         node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
 973                                         break;
 974                                 }
 975
 976                                 /*
 977                                  * now check the inner skip qual to see if we should now
 978                                  * skip inner tuples... if we fail the inner skip qual,
 979                                  * then we know we have a new pair of matching tuples.
 980                                  */
 981                                 compareResult = MergeCompare(mergeclauses,
 982                                                                                          innerSkipQual,
 983                                                                                          econtext);
 984
 985                                 MJ_DEBUG_MERGE_COMPARE(innerSkipQual, compareResult);
 986
 987                                 if (compareResult)
 988                                         node->mj_JoinState = EXEC_MJ_SKIPINNER_BEGIN;
 989                                 else
 990                                         node->mj_JoinState = EXEC_MJ_JOINMARK;
 991                                 break;
 992
 993                                 /*
 994                                  * Before advancing, we check to see if we must emit an
 995                                  * outer-join fill tuple for this outer tuple.
 996                                  */
 997                         case EXEC_MJ_SKIPOUTER_ADVANCE:
 998                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_ADVANCE\n");
 999
1000                                 if (doFillOuter && !node->mj_MatchedOuter)
1001                                 {
1002                                         /*
1003                                          * Generate a fake join tuple with nulls for the inner
1004                                          * tuple, and return it if it passes the non-join
1005                                          * quals.
1006                                          */
1007                                         node->mj_MatchedOuter = true;           /* do it only once */
1008
1009                                         ResetExprContext(econtext);
1010
1011                                         outerTupleSlot = node->mj_OuterTupleSlot;
1012                                         econtext->ecxt_outertuple = outerTupleSlot;
1013                                         innerTupleSlot = node->mj_NullInnerTupleSlot;
1014                                         econtext->ecxt_innertuple = innerTupleSlot;
1015
1016                                         if (ExecQual(otherqual, econtext, false))
1017                                         {
1018                                                 /*
1019                                                  * qualification succeeded.  now form the desired
1020                                                  * projection tuple and return the slot containing
1021                                                  * it.
1022                                                  */
1023                                                 TupleTableSlot *result;
1024                                                 ExprDoneCond isDone;
1025
1026                                                 MJ_printf("ExecMergeJoin: returning fill tuple\n");
1027
1028                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
1029                                                                                          &isDone);
1030
1031                                                 if (isDone != ExprEndResult)
1032                                                 {
1033                                                         node->js.ps.ps_TupFromTlist =
1034                                                                 (isDone == ExprMultipleResult);
1035                                                         return result;
1036                                                 }
1037                                         }
1038                                 }
1039
1040                                 /*
1041                                  * now we get the next outer tuple, if any
1042                                  */
1043                                 outerTupleSlot = ExecProcNode(outerPlan);
1044                                 node->mj_OuterTupleSlot = outerTupleSlot;
1045                                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1046                                 node->mj_MatchedOuter = false;
1047
1048                                 /*
1049                                  * if the outer tuple is null then we are done with the
1050                                  * join, unless we have inner tuples we need to null-fill.
1051                                  */
1052                                 if (TupIsNull(outerTupleSlot))
1053                                 {
1054                                         MJ_printf("ExecMergeJoin: end of outer subplan\n");
1055                                         innerTupleSlot = node->mj_InnerTupleSlot;
1056                                         if (doFillInner && !TupIsNull(innerTupleSlot))
1057                                         {
1058                                                 /*
1059                                                  * Need to emit right-join tuples for remaining
1060                                                  * inner tuples.
1061                                                  */
1062                                                 node->mj_JoinState = EXEC_MJ_ENDOUTER;
1063                                                 break;
1064                                         }
1065                                         /* Otherwise we're done. */
1066                                         return NULL;
1067                                 }
1068
1069                                 /*
1070                                  * otherwise test the new tuple against the skip qual.
1071                                  */
1072                                 node->mj_JoinState = EXEC_MJ_SKIPOUTER_TEST;
1073                                 break;
1074
1075                                 /*-----------------------------------------------------------
1076                                  * EXEC_MJ_SKIPINNER means skip over tuples in the inner plan
1077                                  * until we find an inner tuple >= current outer tuple.
1078                                  *
1079                                  * For example:
1080                                  *
1081                                  *                              outer inner
1082                                  *                                5             5
1083                                  *                                5             5
1084                                  * outer tuple - 12             8  - inner tuple
1085                                  *                               14    10
1086                                  *                               17    12
1087                                  *
1088                                  * we have to advance the inner scan
1089                                  * until we find the inner 12.
1090                                  *
1091                                  * To avoid redundant tests, we divide this into three
1092                                  * sub-states: BEGIN, TEST, ADVANCE.
1093                                  *-------------------------------------------------------
1094                                  */
1095                         case EXEC_MJ_SKIPINNER_BEGIN:
1096                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_BEGIN\n");
1097
1098                                 /*
1099                                  * before we advance, make sure the current tuples do not
1100                                  * satisfy the mergeclauses.  If they do, then we update
1101                                  * the marked tuple and go join them.
1102                                  */
1103                                 ResetExprContext(econtext);
1104
1105                                 outerTupleSlot = node->mj_OuterTupleSlot;
1106                                 econtext->ecxt_outertuple = outerTupleSlot;
1107                                 innerTupleSlot = node->mj_InnerTupleSlot;
1108                                 econtext->ecxt_innertuple = innerTupleSlot;
1109
1110                                 qualResult = ExecQual(mergeclauses, econtext, false);
1111                                 MJ_DEBUG_QUAL(mergeclauses, qualResult);
1112
1113                                 if (qualResult)
1114                                 {
1115                                         ExecMarkPos(innerPlan);
1116
1117                                         MarkInnerTuple(innerTupleSlot, node);
1118
1119                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1120                                         break;
1121                                 }
1122
1123                                 node->mj_JoinState = EXEC_MJ_SKIPINNER_TEST;
1124                                 break;
1125
1126                         case EXEC_MJ_SKIPINNER_TEST:
1127                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_TEST\n");
1128
1129                                 /*
1130                                  * ok, now test the skip qualification
1131                                  */
1132                                 outerTupleSlot = node->mj_OuterTupleSlot;
1133                                 econtext->ecxt_outertuple = outerTupleSlot;
1134                                 innerTupleSlot = node->mj_InnerTupleSlot;
1135                                 econtext->ecxt_innertuple = innerTupleSlot;
1136
1137                                 compareResult = MergeCompare(mergeclauses,
1138                                                                                          innerSkipQual,
1139                                                                                          econtext);
1140
1141                                 MJ_DEBUG_MERGE_COMPARE(innerSkipQual, compareResult);
1142
1143                                 /*
1144                                  * compareResult is true as long as we should continue
1145                                  * skipping inner tuples.
1146                                  */
1147                                 if (compareResult)
1148                                 {
1149                                         node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1150                                         break;
1151                                 }
1152
1153                                 /*
1154                                  * now check the outer skip qual to see if we should now
1155                                  * skip outer tuples... if we fail the outer skip qual,
1156                                  * then we know we have a new pair of matching tuples.
1157                                  */
1158                                 compareResult = MergeCompare(mergeclauses,
1159                                                                                          outerSkipQual,
1160                                                                                          econtext);
1161
1162                                 MJ_DEBUG_MERGE_COMPARE(outerSkipQual, compareResult);
1163
1164                                 if (compareResult)
1165                                         node->mj_JoinState = EXEC_MJ_SKIPOUTER_BEGIN;
1166                                 else
1167                                         node->mj_JoinState = EXEC_MJ_JOINMARK;
1168                                 break;
1169
1170                                 /*
1171                                  * Before advancing, we check to see if we must emit an
1172                                  * outer-join fill tuple for this inner tuple.
1173                                  */
1174                         case EXEC_MJ_SKIPINNER_ADVANCE:
1175                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_ADVANCE\n");
1176
1177                                 if (doFillInner && !node->mj_MatchedInner)
1178                                 {
1179                                         /*
1180                                          * Generate a fake join tuple with nulls for the outer
1181                                          * tuple, and return it if it passes the non-join
1182                                          * quals.
1183                                          */
1184                                         node->mj_MatchedInner = true;           /* do it only once */
1185
1186                                         ResetExprContext(econtext);
1187
1188                                         outerTupleSlot = node->mj_NullOuterTupleSlot;
1189                                         econtext->ecxt_outertuple = outerTupleSlot;
1190                                         innerTupleSlot = node->mj_InnerTupleSlot;
1191                                         econtext->ecxt_innertuple = innerTupleSlot;
1192
1193                                         if (ExecQual(otherqual, econtext, false))
1194                                         {
1195                                                 /*
1196                                                  * qualification succeeded.  now form the desired
1197                                                  * projection tuple and return the slot containing
1198                                                  * it.
1199                                                  */
1200                                                 TupleTableSlot *result;
1201                                                 ExprDoneCond isDone;
1202
1203                                                 MJ_printf("ExecMergeJoin: returning fill tuple\n");
1204
1205                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
1206                                                                                          &isDone);
1207
1208                                                 if (isDone != ExprEndResult)
1209                                                 {
1210                                                         node->js.ps.ps_TupFromTlist =
1211                                                                 (isDone == ExprMultipleResult);
1212                                                         return result;
1213                                                 }
1214                                         }
1215                                 }
1216
1217                                 /*
1218                                  * now we get the next inner tuple, if any
1219                                  */
1220                                 innerTupleSlot = ExecProcNode(innerPlan);
1221                                 node->mj_InnerTupleSlot = innerTupleSlot;
1222                                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1223                                 node->mj_MatchedInner = false;
1224
1225                                 /*
1226                                  * if the inner tuple is null then we are done with the
1227                                  * join, unless we have outer tuples we need to null-fill.
1228                                  */
1229                                 if (TupIsNull(innerTupleSlot))
1230                                 {
1231                                         MJ_printf("ExecMergeJoin: end of inner subplan\n");
1232                                         outerTupleSlot = node->mj_OuterTupleSlot;
1233                                         if (doFillOuter && !TupIsNull(outerTupleSlot))
1234                                         {
1235                                                 /*
1236                                                  * Need to emit left-join tuples for remaining
1237                                                  * outer tuples.
1238                                                  */
1239                                                 node->mj_JoinState = EXEC_MJ_ENDINNER;
1240                                                 break;
1241                                         }
1242                                         /* Otherwise we're done. */
1243                                         return NULL;
1244                                 }
1245
1246                                 /*
1247                                  * otherwise test the new tuple against the skip qual.
1248                                  */
1249                                 node->mj_JoinState = EXEC_MJ_SKIPINNER_TEST;
1250                                 break;
1251
1252                                 /*
1253                                  * EXEC_MJ_ENDOUTER means we have run out of outer tuples,
1254                                  * but are doing a right/full join and therefore must
1255                                  * null- fill any remaing unmatched inner tuples.
1256                                  */
1257                         case EXEC_MJ_ENDOUTER:
1258                                 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDOUTER\n");
1259
1260                                 Assert(doFillInner);
1261
1262                                 if (!node->mj_MatchedInner)
1263                                 {
1264                                         /*
1265                                          * Generate a fake join tuple with nulls for the outer
1266                                          * tuple, and return it if it passes the non-join
1267                                          * quals.
1268                                          */
1269                                         node->mj_MatchedInner = true;           /* do it only once */
1270
1271                                         ResetExprContext(econtext);
1272
1273                                         outerTupleSlot = node->mj_NullOuterTupleSlot;
1274                                         econtext->ecxt_outertuple = outerTupleSlot;
1275                                         innerTupleSlot = node->mj_InnerTupleSlot;
1276                                         econtext->ecxt_innertuple = innerTupleSlot;
1277
1278                                         if (ExecQual(otherqual, econtext, false))
1279                                         {
1280                                                 /*
1281                                                  * qualification succeeded.  now form the desired
1282                                                  * projection tuple and return the slot containing
1283                                                  * it.
1284                                                  */
1285                                                 TupleTableSlot *result;
1286                                                 ExprDoneCond isDone;
1287
1288                                                 MJ_printf("ExecMergeJoin: returning fill tuple\n");
1289
1290                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
1291                                                                                          &isDone);
1292
1293                                                 if (isDone != ExprEndResult)
1294                                                 {
1295                                                         node->js.ps.ps_TupFromTlist =
1296                                                                 (isDone == ExprMultipleResult);
1297                                                         return result;
1298                                                 }
1299                                         }
1300                                 }
1301
1302                                 /*
1303                                  * now we get the next inner tuple, if any
1304                                  */
1305                                 innerTupleSlot = ExecProcNode(innerPlan);
1306                                 node->mj_InnerTupleSlot = innerTupleSlot;
1307                                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1308                                 node->mj_MatchedInner = false;
1309
1310                                 if (TupIsNull(innerTupleSlot))
1311                                 {
1312                                         MJ_printf("ExecMergeJoin: end of inner subplan\n");
1313                                         return NULL;
1314                                 }
1315
1316                                 /* Else remain in ENDOUTER state and process next tuple. */
1317                                 break;
1318
1319                                 /*
1320                                  * EXEC_MJ_ENDINNER means we have run out of inner tuples,
1321                                  * but are doing a left/full join and therefore must null-
1322                                  * fill any remaing unmatched outer tuples.
1323                                  */
1324                         case EXEC_MJ_ENDINNER:
1325                                 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDINNER\n");
1326
1327                                 Assert(doFillOuter);
1328
1329                                 if (!node->mj_MatchedOuter)
1330                                 {
1331                                         /*
1332                                          * Generate a fake join tuple with nulls for the inner
1333                                          * tuple, and return it if it passes the non-join
1334                                          * quals.
1335                                          */
1336                                         node->mj_MatchedOuter = true;           /* do it only once */
1337
1338                                         ResetExprContext(econtext);
1339
1340                                         outerTupleSlot = node->mj_OuterTupleSlot;
1341                                         econtext->ecxt_outertuple = outerTupleSlot;
1342                                         innerTupleSlot = node->mj_NullInnerTupleSlot;
1343                                         econtext->ecxt_innertuple = innerTupleSlot;
1344
1345                                         if (ExecQual(otherqual, econtext, false))
1346                                         {
1347                                                 /*
1348                                                  * qualification succeeded.  now form the desired
1349                                                  * projection tuple and return the slot containing
1350                                                  * it.
1351                                                  */
1352                                                 TupleTableSlot *result;
1353                                                 ExprDoneCond isDone;
1354
1355                                                 MJ_printf("ExecMergeJoin: returning fill tuple\n");
1356
1357                                                 result = ExecProject(node->js.ps.ps_ProjInfo,
1358                                                                                          &isDone);
1359
1360                                                 if (isDone != ExprEndResult)
1361                                                 {
1362                                                         node->js.ps.ps_TupFromTlist =
1363                                                                 (isDone == ExprMultipleResult);
1364                                                         return result;
1365                                                 }
1366                                         }
1367                                 }
1368
1369                                 /*
1370                                  * now we get the next outer tuple, if any
1371                                  */
1372                                 outerTupleSlot = ExecProcNode(outerPlan);
1373                                 node->mj_OuterTupleSlot = outerTupleSlot;
1374                                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1375                                 node->mj_MatchedOuter = false;
1376
1377                                 if (TupIsNull(outerTupleSlot))
1378                                 {
1379                                         MJ_printf("ExecMergeJoin: end of outer subplan\n");
1380                                         return NULL;
1381                                 }
1382
1383                                 /* Else remain in ENDINNER state and process next tuple. */
1384                                 break;
1385
1386                                 /*
1387                                  * broken state value?
1388                                  */
1389                         default:
1390                                 elog(ERROR, "unrecognized mergejoin state: %d",
1391                                          (int) node->mj_JoinState);
1392                 }
1393         }
1394 }
1395
1396 /* ----------------------------------------------------------------
1397  *              ExecInitMergeJoin
1398  * ----------------------------------------------------------------
1399  */
1400 MergeJoinState *
1401 ExecInitMergeJoin(MergeJoin *node, EState *estate)
1402 {
1403         MergeJoinState *mergestate;
1404
1405         MJ1_printf("ExecInitMergeJoin: %s\n",
1406                            "initializing node");
1407
1408         /*
1409          * create state structure
1410          */
1411         mergestate = makeNode(MergeJoinState);
1412         mergestate->js.ps.plan = (Plan *) node;
1413         mergestate->js.ps.state = estate;
1414
1415         /*
1416          * Miscellaneous initialization
1417          *
1418          * create expression context for node
1419          */
1420         ExecAssignExprContext(estate, &mergestate->js.ps);
1421
1422         /*
1423          * initialize child expressions
1424          */
1425         mergestate->js.ps.targetlist = (List *)
1426                 ExecInitExpr((Expr *) node->join.plan.targetlist,
1427                                          (PlanState *) mergestate);
1428         mergestate->js.ps.qual = (List *)
1429                 ExecInitExpr((Expr *) node->join.plan.qual,
1430                                          (PlanState *) mergestate);
1431         mergestate->js.jointype = node->join.jointype;
1432         mergestate->js.joinqual = (List *)
1433                 ExecInitExpr((Expr *) node->join.joinqual,
1434                                          (PlanState *) mergestate);
1435         mergestate->mergeclauses = (List *)
1436                 ExecInitExpr((Expr *) node->mergeclauses,
1437                                          (PlanState *) mergestate);
1438
1439         /*
1440          * initialize child nodes
1441          */
1442         outerPlanState(mergestate) = ExecInitNode(outerPlan(node), estate);
1443         innerPlanState(mergestate) = ExecInitNode(innerPlan(node), estate);
1444
1445 #define MERGEJOIN_NSLOTS 4
1446
1447         /*
1448          * tuple table initialization
1449          */
1450         ExecInitResultTupleSlot(estate, &mergestate->js.ps);
1451
1452         mergestate->mj_MarkedTupleSlot = ExecInitExtraTupleSlot(estate);
1453         ExecSetSlotDescriptor(mergestate->mj_MarkedTupleSlot,
1454                                                   ExecGetResultType(innerPlanState(mergestate)),
1455                                                   false);
1456
1457         switch (node->join.jointype)
1458         {
1459                 case JOIN_INNER:
1460                 case JOIN_IN:
1461                         break;
1462                 case JOIN_LEFT:
1463                         mergestate->mj_NullInnerTupleSlot =
1464                                 ExecInitNullTupleSlot(estate,
1465                                                   ExecGetResultType(innerPlanState(mergestate)));
1466                         break;
1467                 case JOIN_RIGHT:
1468                         mergestate->mj_NullOuterTupleSlot =
1469                                 ExecInitNullTupleSlot(estate,
1470                                                   ExecGetResultType(outerPlanState(mergestate)));
1471
1472                         /*
1473                          * Can't handle right or full join with non-nil extra
1474                          * joinclauses.  This should have been caught by planner.
1475                          */
1476                         if (node->join.joinqual != NIL)
1477                                 ereport(ERROR,
1478                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1479                                                  errmsg("RIGHT JOIN is only supported with merge-joinable join conditions")));
1480                         break;
1481                 case JOIN_FULL:
1482                         mergestate->mj_NullOuterTupleSlot =
1483                                 ExecInitNullTupleSlot(estate,
1484                                                   ExecGetResultType(outerPlanState(mergestate)));
1485                         mergestate->mj_NullInnerTupleSlot =
1486                                 ExecInitNullTupleSlot(estate,
1487                                                   ExecGetResultType(innerPlanState(mergestate)));
1488
1489                         /*
1490                          * Can't handle right or full join with non-nil extra
1491                          * joinclauses.
1492                          */
1493                         if (node->join.joinqual != NIL)
1494                                 ereport(ERROR,
1495                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1496                                                  errmsg("FULL JOIN is only supported with merge-joinable join conditions")));
1497                         break;
1498                 default:
1499                         elog(ERROR, "unrecognized join type: %d",
1500                                  (int) node->join.jointype);
1501         }
1502
1503         /*
1504          * initialize tuple type and projection info
1505          */
1506         ExecAssignResultTypeFromTL(&mergestate->js.ps);
1507         ExecAssignProjectionInfo(&mergestate->js.ps);
1508
1509         /*
1510          * form merge skip qualifications
1511          */
1512         MJFormSkipQuals(node->mergeclauses,
1513                                         &mergestate->mj_OuterSkipQual,
1514                                         &mergestate->mj_InnerSkipQual,
1515                                         (PlanState *) mergestate);
1516
1517         MJ_printf("\nExecInitMergeJoin: OuterSkipQual is ");
1518         MJ_nodeDisplay(mergestate->mj_OuterSkipQual);
1519         MJ_printf("\nExecInitMergeJoin: InnerSkipQual is ");
1520         MJ_nodeDisplay(mergestate->mj_InnerSkipQual);
1521         MJ_printf("\n");
1522
1523         /*
1524          * initialize join state
1525          */
1526         mergestate->mj_JoinState = EXEC_MJ_INITIALIZE;
1527         mergestate->js.ps.ps_TupFromTlist = false;
1528         mergestate->mj_MatchedOuter = false;
1529         mergestate->mj_MatchedInner = false;
1530         mergestate->mj_OuterTupleSlot = NULL;
1531         mergestate->mj_InnerTupleSlot = NULL;
1532
1533         /*
1534          * initialization successful
1535          */
1536         MJ1_printf("ExecInitMergeJoin: %s\n",
1537                            "node initialized");
1538
1539         return mergestate;
1540 }
1541
1542 int
1543 ExecCountSlotsMergeJoin(MergeJoin *node)
1544 {
1545         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
1546                 ExecCountSlotsNode(innerPlan((Plan *) node)) +
1547                 MERGEJOIN_NSLOTS;
1548 }
1549
1550 /* ----------------------------------------------------------------
1551  *              ExecEndMergeJoin
1552  *
1553  * old comments
1554  *              frees storage allocated through C routines.
1555  * ----------------------------------------------------------------
1556  */
1557 void
1558 ExecEndMergeJoin(MergeJoinState *node)
1559 {
1560         MJ1_printf("ExecEndMergeJoin: %s\n",
1561                            "ending node processing");
1562
1563         /*
1564          * Free the exprcontext
1565          */
1566         ExecFreeExprContext(&node->js.ps);
1567
1568         /*
1569          * clean out the tuple table
1570          */
1571         ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
1572         ExecClearTuple(node->mj_MarkedTupleSlot);
1573
1574         /*
1575          * shut down the subplans
1576          */
1577         ExecEndNode(innerPlanState(node));
1578         ExecEndNode(outerPlanState(node));
1579
1580         MJ1_printf("ExecEndMergeJoin: %s\n",
1581                            "node processing ended");
1582 }
1583
1584 void
1585 ExecReScanMergeJoin(MergeJoinState *node, ExprContext *exprCtxt)
1586 {
1587         ExecClearTuple(node->mj_MarkedTupleSlot);
1588
1589         node->mj_JoinState = EXEC_MJ_INITIALIZE;
1590         node->js.ps.ps_TupFromTlist = false;
1591         node->mj_MatchedOuter = false;
1592         node->mj_MatchedInner = false;
1593         node->mj_OuterTupleSlot = NULL;
1594         node->mj_InnerTupleSlot = NULL;
1595
1596         /*
1597          * if chgParam of subnodes is not null then plans will be re-scanned
1598          * by first ExecProcNode.
1599          */
1600         if (((PlanState *) node)->lefttree->chgParam == NULL)
1601                 ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
1602         if (((PlanState *) node)->righttree->chgParam == NULL)
1603                 ExecReScan(((PlanState *) node)->righttree, exprCtxt);
1604
1605 }