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