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-2019, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/executor/nodeMergejoin.c
  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  *
  23  *              Merge-join is done by joining the inner and outer tuples satisfying
  24  *              join clauses of the form ((= outerKey innerKey) ...).
  25  *              The join clause list is provided by the query planner and may contain
  26  *              more than one (= outerKey innerKey) clause (for composite sort key).
  27  *
  28  *              However, the query executor needs to know whether an outer
  29  *              tuple is "greater/smaller" than an inner tuple so that it can
  30  *              "synchronize" the two relations. For example, consider the following
  31  *              relations:
  32  *
  33  *                              outer: (0 ^1 1 2 5 5 5 6 6 7)   current tuple: 1
  34  *                              inner: (1 ^3 5 5 5 5 6)                 current tuple: 3
  35  *
  36  *              To continue the merge-join, the executor needs to scan both inner
  37  *              and outer relations till the matching tuples 5. It needs to know
  38  *              that currently inner tuple 3 is "greater" than outer tuple 1 and
  39  *              therefore it should scan the outer relation first to find a
  40  *              matching tuple and so on.
  41  *
  42  *              Therefore, rather than directly executing the merge join clauses,
  43  *              we evaluate the left and right key expressions separately and then
  44  *              compare the columns one at a time (see MJCompare).  The planner
  45  *              passes us enough information about the sort ordering of the inputs
  46  *              to allow us to determine how to make the comparison.  We may use the
  47  *              appropriate btree comparison function, since Postgres' only notion
  48  *              of ordering is specified by btree opfamilies.
  49  *
  50  *
  51  *              Consider the above relations and suppose that the executor has
  52  *              just joined the first outer "5" with the last inner "5". The
  53  *              next step is of course to join the second outer "5" with all
  54  *              the inner "5's". This requires repositioning the inner "cursor"
  55  *              to point at the first inner "5". This is done by "marking" the
  56  *              first inner 5 so we can restore the "cursor" to it before joining
  57  *              with the second outer 5. The access method interface provides
  58  *              routines to mark and restore to a tuple.
  59  *
  60  *
  61  *              Essential operation of the merge join algorithm is as follows:
  62  *
  63  *              Join {
  64  *                      get initial outer and inner tuples                              INITIALIZE
  65  *                      do forever {
  66  *                              while (outer != inner) {                                        SKIP_TEST
  67  *                                      if (outer < inner)
  68  *                                              advance outer                                           SKIPOUTER_ADVANCE
  69  *                                      else
  70  *                                              advance inner                                           SKIPINNER_ADVANCE
  71  *                              }
  72  *                              mark inner position                                                     SKIP_TEST
  73  *                              do forever {
  74  *                                      while (outer == inner) {
  75  *                                              join tuples                                                     JOINTUPLES
  76  *                                              advance inner position                          NEXTINNER
  77  *                                      }
  78  *                                      advance outer position                                  NEXTOUTER
  79  *                                      if (outer == mark)                                              TESTOUTER
  80  *                                              restore inner position to mark          TESTOUTER
  81  *                                      else
  82  *                                              break   // return to top of outer loop
  83  *                              }
  84  *                      }
  85  *              }
  86  *
  87  *              The merge join operation is coded in the fashion
  88  *              of a state machine.  At each state, we do something and then
  89  *              proceed to another state.  This state is stored in the node's
  90  *              execution state information and is preserved across calls to
  91  *              ExecMergeJoin. -cim 10/31/89
  92  */
  93 #include "postgres.h"
  94
  95 #include "access/nbtree.h"
  96 #include "executor/execdebug.h"
  97 #include "executor/nodeMergejoin.h"
  98 #include "miscadmin.h"
  99 #include "utils/lsyscache.h"
 100 #include "utils/memutils.h"
 101
 102
 103 /*
 104  * States of the ExecMergeJoin state machine
 105  */
 106 #define EXEC_MJ_INITIALIZE_OUTER                1
 107 #define EXEC_MJ_INITIALIZE_INNER                2
 108 #define EXEC_MJ_JOINTUPLES                              3
 109 #define EXEC_MJ_NEXTOUTER                               4
 110 #define EXEC_MJ_TESTOUTER                               5
 111 #define EXEC_MJ_NEXTINNER                               6
 112 #define EXEC_MJ_SKIP_TEST                               7
 113 #define EXEC_MJ_SKIPOUTER_ADVANCE               8
 114 #define EXEC_MJ_SKIPINNER_ADVANCE               9
 115 #define EXEC_MJ_ENDOUTER                                10
 116 #define EXEC_MJ_ENDINNER                                11
 117
 118 /*
 119  * Runtime data for each mergejoin clause
 120  */
 121 typedef struct MergeJoinClauseData
 122 {
 123         /* Executable expression trees */
 124         ExprState  *lexpr;                      /* left-hand (outer) input expression */
 125         ExprState  *rexpr;                      /* right-hand (inner) input expression */
 126
 127         /*
 128          * If we have a current left or right input tuple, the values of the
 129          * expressions are loaded into these fields:
 130          */
 131         Datum           ldatum;                 /* current left-hand value */
 132         Datum           rdatum;                 /* current right-hand value */
 133         bool            lisnull;                /* and their isnull flags */
 134         bool            risnull;
 135
 136         /*
 137          * Everything we need to know to compare the left and right values is
 138          * stored here.
 139          */
 140         SortSupportData ssup;
 141 }                       MergeJoinClauseData;
 142
 143 /* Result type for MJEvalOuterValues and MJEvalInnerValues */
 144 typedef enum
 145 {
 146         MJEVAL_MATCHABLE,                       /* normal, potentially matchable tuple */
 147         MJEVAL_NONMATCHABLE,            /* tuple cannot join because it has a null */
 148         MJEVAL_ENDOFJOIN                        /* end of input (physical or effective) */
 149 } MJEvalResult;
 150
 151
 152 #define MarkInnerTuple(innerTupleSlot, mergestate) \
 153         ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
 154
 155
 156 /*
 157  * MJExamineQuals
 158  *
 159  * This deconstructs the list of mergejoinable expressions, which is given
 160  * to us by the planner in the form of a list of "leftexpr = rightexpr"
 161  * expression trees in the order matching the sort columns of the inputs.
 162  * We build an array of MergeJoinClause structs containing the information
 163  * we will need at runtime.  Each struct essentially tells us how to compare
 164  * the two expressions from the original clause.
 165  *
 166  * In addition to the expressions themselves, the planner passes the btree
 167  * opfamily OID, collation OID, btree strategy number (BTLessStrategyNumber or
 168  * BTGreaterStrategyNumber), and nulls-first flag that identify the intended
 169  * sort ordering for each merge key.  The mergejoinable operator is an
 170  * equality operator in the opfamily, and the two inputs are guaranteed to be
 171  * ordered in either increasing or decreasing (respectively) order according
 172  * to the opfamily and collation, with nulls at the indicated end of the range.
 173  * This allows us to obtain the needed comparison function from the opfamily.
 174  */
 175 static MergeJoinClause
 176 MJExamineQuals(List *mergeclauses,
 177                            Oid *mergefamilies,
 178                            Oid *mergecollations,
 179                            int *mergestrategies,
 180                            bool *mergenullsfirst,
 181                            PlanState *parent)
 182 {
 183         MergeJoinClause clauses;
 184         int                     nClauses = list_length(mergeclauses);
 185         int                     iClause;
 186         ListCell   *cl;
 187
 188         clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
 189
 190         iClause = 0;
 191         foreach(cl, mergeclauses)
 192         {
 193                 OpExpr     *qual = (OpExpr *) lfirst(cl);
 194                 MergeJoinClause clause = &clauses[iClause];
 195                 Oid                     opfamily = mergefamilies[iClause];
 196                 Oid                     collation = mergecollations[iClause];
 197                 StrategyNumber opstrategy = mergestrategies[iClause];
 198                 bool            nulls_first = mergenullsfirst[iClause];
 199                 int                     op_strategy;
 200                 Oid                     op_lefttype;
 201                 Oid                     op_righttype;
 202                 Oid                     sortfunc;
 203
 204                 if (!IsA(qual, OpExpr))
 205                         elog(ERROR, "mergejoin clause is not an OpExpr");
 206
 207                 /*
 208                  * Prepare the input expressions for execution.
 209                  */
 210                 clause->lexpr = ExecInitExpr((Expr *) linitial(qual->args), parent);
 211                 clause->rexpr = ExecInitExpr((Expr *) lsecond(qual->args), parent);
 212
 213                 /* Set up sort support data */
 214                 clause->ssup.ssup_cxt = CurrentMemoryContext;
 215                 clause->ssup.ssup_collation = collation;
 216                 if (opstrategy == BTLessStrategyNumber)
 217                         clause->ssup.ssup_reverse = false;
 218                 else if (opstrategy == BTGreaterStrategyNumber)
 219                         clause->ssup.ssup_reverse = true;
 220                 else                                    /* planner screwed up */
 221                         elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
 222                 clause->ssup.ssup_nulls_first = nulls_first;
 223
 224                 /* Extract the operator's declared left/right datatypes */
 225                 get_op_opfamily_properties(qual->opno, opfamily, false,
 226                                                                    &op_strategy,
 227                                                                    &op_lefttype,
 228                                                                    &op_righttype);
 229                 if (op_strategy != BTEqualStrategyNumber)       /* should not happen */
 230                         elog(ERROR, "cannot merge using non-equality operator %u",
 231                                  qual->opno);
 232
 233                 /*
 234                  * sortsupport routine must know if abbreviation optimization is
 235                  * applicable in principle.  It is never applicable for merge joins
 236                  * because there is no convenient opportunity to convert to
 237                  * alternative representation.
 238                  */
 239                 clause->ssup.abbreviate = false;
 240
 241                 /* And get the matching support or comparison function */
 242                 Assert(clause->ssup.comparator == NULL);
 243                 sortfunc = get_opfamily_proc(opfamily,
 244                                                                          op_lefttype,
 245                                                                          op_righttype,
 246                                                                          BTSORTSUPPORT_PROC);
 247                 if (OidIsValid(sortfunc))
 248                 {
 249                         /* The sort support function can provide a comparator */
 250                         OidFunctionCall1(sortfunc, PointerGetDatum(&clause->ssup));
 251                 }
 252                 if (clause->ssup.comparator == NULL)
 253                 {
 254                         /* support not available, get comparison func */
 255                         sortfunc = get_opfamily_proc(opfamily,
 256                                                                                  op_lefttype,
 257                                                                                  op_righttype,
 258                                                                                  BTORDER_PROC);
 259                         if (!OidIsValid(sortfunc))      /* should not happen */
 260                                 elog(ERROR, "missing support function %d(%u,%u) in opfamily %u",
 261                                          BTORDER_PROC, op_lefttype, op_righttype, opfamily);
 262                         /* We'll use a shim to call the old-style btree comparator */
 263                         PrepareSortSupportComparisonShim(sortfunc, &clause->ssup);
 264                 }
 265
 266                 iClause++;
 267         }
 268
 269         return clauses;
 270 }
 271
 272 /*
 273  * MJEvalOuterValues
 274  *
 275  * Compute the values of the mergejoined expressions for the current
 276  * outer tuple.  We also detect whether it's impossible for the current
 277  * outer tuple to match anything --- this is true if it yields a NULL
 278  * input, since we assume mergejoin operators are strict.  If the NULL
 279  * is in the first join column, and that column sorts nulls last, then
 280  * we can further conclude that no following tuple can match anything
 281  * either, since they must all have nulls in the first column.  However,
 282  * that case is only interesting if we're not in FillOuter mode, else
 283  * we have to visit all the tuples anyway.
 284  *
 285  * For the convenience of callers, we also make this routine responsible
 286  * for testing for end-of-input (null outer tuple), and returning
 287  * MJEVAL_ENDOFJOIN when that's seen.  This allows the same code to be used
 288  * for both real end-of-input and the effective end-of-input represented by
 289  * a first-column NULL.
 290  *
 291  * We evaluate the values in OuterEContext, which can be reset each
 292  * time we move to a new tuple.
 293  */
 294 static MJEvalResult
 295 MJEvalOuterValues(MergeJoinState *mergestate)
 296 {
 297         ExprContext *econtext = mergestate->mj_OuterEContext;
 298         MJEvalResult result = MJEVAL_MATCHABLE;
 299         int                     i;
 300         MemoryContext oldContext;
 301
 302         /* Check for end of outer subplan */
 303         if (TupIsNull(mergestate->mj_OuterTupleSlot))
 304                 return MJEVAL_ENDOFJOIN;
 305
 306         ResetExprContext(econtext);
 307
 308         oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 309
 310         econtext->ecxt_outertuple = mergestate->mj_OuterTupleSlot;
 311
 312         for (i = 0; i < mergestate->mj_NumClauses; i++)
 313         {
 314                 MergeJoinClause clause = &mergestate->mj_Clauses[i];
 315
 316                 clause->ldatum = ExecEvalExpr(clause->lexpr, econtext,
 317                                                                           &clause->lisnull);
 318                 if (clause->lisnull)
 319                 {
 320                         /* match is impossible; can we end the join early? */
 321                         if (i == 0 && !clause->ssup.ssup_nulls_first &&
 322                                 !mergestate->mj_FillOuter)
 323                                 result = MJEVAL_ENDOFJOIN;
 324                         else if (result == MJEVAL_MATCHABLE)
 325                                 result = MJEVAL_NONMATCHABLE;
 326                 }
 327         }
 328
 329         MemoryContextSwitchTo(oldContext);
 330
 331         return result;
 332 }
 333
 334 /*
 335  * MJEvalInnerValues
 336  *
 337  * Same as above, but for the inner tuple.  Here, we have to be prepared
 338  * to load data from either the true current inner, or the marked inner,
 339  * so caller must tell us which slot to load from.
 340  */
 341 static MJEvalResult
 342 MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
 343 {
 344         ExprContext *econtext = mergestate->mj_InnerEContext;
 345         MJEvalResult result = MJEVAL_MATCHABLE;
 346         int                     i;
 347         MemoryContext oldContext;
 348
 349         /* Check for end of inner subplan */
 350         if (TupIsNull(innerslot))
 351                 return MJEVAL_ENDOFJOIN;
 352
 353         ResetExprContext(econtext);
 354
 355         oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 356
 357         econtext->ecxt_innertuple = innerslot;
 358
 359         for (i = 0; i < mergestate->mj_NumClauses; i++)
 360         {
 361                 MergeJoinClause clause = &mergestate->mj_Clauses[i];
 362
 363                 clause->rdatum = ExecEvalExpr(clause->rexpr, econtext,
 364                                                                           &clause->risnull);
 365                 if (clause->risnull)
 366                 {
 367                         /* match is impossible; can we end the join early? */
 368                         if (i == 0 && !clause->ssup.ssup_nulls_first &&
 369                                 !mergestate->mj_FillInner)
 370                                 result = MJEVAL_ENDOFJOIN;
 371                         else if (result == MJEVAL_MATCHABLE)
 372                                 result = MJEVAL_NONMATCHABLE;
 373                 }
 374         }
 375
 376         MemoryContextSwitchTo(oldContext);
 377
 378         return result;
 379 }
 380
 381 /*
 382  * MJCompare
 383  *
 384  * Compare the mergejoinable values of the current two input tuples
 385  * and return 0 if they are equal (ie, the mergejoin equalities all
 386  * succeed), >0 if outer > inner, <0 if outer < inner.
 387  *
 388  * MJEvalOuterValues and MJEvalInnerValues must already have been called
 389  * for the current outer and inner tuples, respectively.
 390  */
 391 static int
 392 MJCompare(MergeJoinState *mergestate)
 393 {
 394         int                     result = 0;
 395         bool            nulleqnull = false;
 396         ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
 397         int                     i;
 398         MemoryContext oldContext;
 399
 400         /*
 401          * Call the comparison functions in short-lived context, in case they leak
 402          * memory.
 403          */
 404         ResetExprContext(econtext);
 405
 406         oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 407
 408         for (i = 0; i < mergestate->mj_NumClauses; i++)
 409         {
 410                 MergeJoinClause clause = &mergestate->mj_Clauses[i];
 411
 412                 /*
 413                  * Special case for NULL-vs-NULL, else use standard comparison.
 414                  */
 415                 if (clause->lisnull && clause->risnull)
 416                 {
 417                         nulleqnull = true;      /* NULL "=" NULL */
 418                         continue;
 419                 }
 420
 421                 result = ApplySortComparator(clause->ldatum, clause->lisnull,
 422                                                                          clause->rdatum, clause->risnull,
 423                                                                          &clause->ssup);
 424
 425                 if (result != 0)
 426                         break;
 427         }
 428
 429         /*
 430          * If we had any NULL-vs-NULL inputs, we do not want to report that the
 431          * tuples are equal.  Instead, if result is still 0, change it to +1. This
 432          * will result in advancing the inner side of the join.
 433          *
 434          * Likewise, if there was a constant-false joinqual, do not report
 435          * equality.  We have to check this as part of the mergequals, else the
 436          * rescan logic will do the wrong thing.
 437          */
 438         if (result == 0 &&
 439                 (nulleqnull || mergestate->mj_ConstFalseJoin))
 440                 result = 1;
 441
 442         MemoryContextSwitchTo(oldContext);
 443
 444         return result;
 445 }
 446
 447
 448 /*
 449  * Generate a fake join tuple with nulls for the inner tuple,
 450  * and return it if it passes the non-join quals.
 451  */
 452 static TupleTableSlot *
 453 MJFillOuter(MergeJoinState *node)
 454 {
 455         ExprContext *econtext = node->js.ps.ps_ExprContext;
 456         ExprState  *otherqual = node->js.ps.qual;
 457
 458         ResetExprContext(econtext);
 459
 460         econtext->ecxt_outertuple = node->mj_OuterTupleSlot;
 461         econtext->ecxt_innertuple = node->mj_NullInnerTupleSlot;
 462
 463         if (ExecQual(otherqual, econtext))
 464         {
 465                 /*
 466                  * qualification succeeded.  now form the desired projection tuple and
 467                  * return the slot containing it.
 468                  */
 469                 MJ_printf("ExecMergeJoin: returning outer fill tuple\n");
 470
 471                 return ExecProject(node->js.ps.ps_ProjInfo);
 472         }
 473         else
 474                 InstrCountFiltered2(node, 1);
 475
 476         return NULL;
 477 }
 478
 479 /*
 480  * Generate a fake join tuple with nulls for the outer tuple,
 481  * and return it if it passes the non-join quals.
 482  */
 483 static TupleTableSlot *
 484 MJFillInner(MergeJoinState *node)
 485 {
 486         ExprContext *econtext = node->js.ps.ps_ExprContext;
 487         ExprState  *otherqual = node->js.ps.qual;
 488
 489         ResetExprContext(econtext);
 490
 491         econtext->ecxt_outertuple = node->mj_NullOuterTupleSlot;
 492         econtext->ecxt_innertuple = node->mj_InnerTupleSlot;
 493
 494         if (ExecQual(otherqual, econtext))
 495         {
 496                 /*
 497                  * qualification succeeded.  now form the desired projection tuple and
 498                  * return the slot containing it.
 499                  */
 500                 MJ_printf("ExecMergeJoin: returning inner fill tuple\n");
 501
 502                 return ExecProject(node->js.ps.ps_ProjInfo);
 503         }
 504         else
 505                 InstrCountFiltered2(node, 1);
 506
 507         return NULL;
 508 }
 509
 510
 511 /*
 512  * Check that a qual condition is constant true or constant false.
 513  * If it is constant false (or null), set *is_const_false to true.
 514  *
 515  * Constant true would normally be represented by a NIL list, but we allow an
 516  * actual bool Const as well.  We do expect that the planner will have thrown
 517  * away any non-constant terms that have been ANDed with a constant false.
 518  */
 519 static bool
 520 check_constant_qual(List *qual, bool *is_const_false)
 521 {
 522         ListCell   *lc;
 523
 524         foreach(lc, qual)
 525         {
 526                 Const      *con = (Const *) lfirst(lc);
 527
 528                 if (!con || !IsA(con, Const))
 529                         return false;
 530                 if (con->constisnull || !DatumGetBool(con->constvalue))
 531                         *is_const_false = true;
 532         }
 533         return true;
 534 }
 535
 536
 537 /* ----------------------------------------------------------------
 538  *              ExecMergeTupleDump
 539  *
 540  *              This function is called through the MJ_dump() macro
 541  *              when EXEC_MERGEJOINDEBUG is defined
 542  * ----------------------------------------------------------------
 543  */
 544 #ifdef EXEC_MERGEJOINDEBUG
 545
 546 static void
 547 ExecMergeTupleDumpOuter(MergeJoinState *mergestate)
 548 {
 549         TupleTableSlot *outerSlot = mergestate->mj_OuterTupleSlot;
 550
 551         printf("==== outer tuple ====\n");
 552         if (TupIsNull(outerSlot))
 553                 printf("(nil)\n");
 554         else
 555                 MJ_debugtup(outerSlot);
 556 }
 557
 558 static void
 559 ExecMergeTupleDumpInner(MergeJoinState *mergestate)
 560 {
 561         TupleTableSlot *innerSlot = mergestate->mj_InnerTupleSlot;
 562
 563         printf("==== inner tuple ====\n");
 564         if (TupIsNull(innerSlot))
 565                 printf("(nil)\n");
 566         else
 567                 MJ_debugtup(innerSlot);
 568 }
 569
 570 static void
 571 ExecMergeTupleDumpMarked(MergeJoinState *mergestate)
 572 {
 573         TupleTableSlot *markedSlot = mergestate->mj_MarkedTupleSlot;
 574
 575         printf("==== marked tuple ====\n");
 576         if (TupIsNull(markedSlot))
 577                 printf("(nil)\n");
 578         else
 579                 MJ_debugtup(markedSlot);
 580 }
 581
 582 static void
 583 ExecMergeTupleDump(MergeJoinState *mergestate)
 584 {
 585         printf("******** ExecMergeTupleDump ********\n");
 586
 587         ExecMergeTupleDumpOuter(mergestate);
 588         ExecMergeTupleDumpInner(mergestate);
 589         ExecMergeTupleDumpMarked(mergestate);
 590
 591         printf("********\n");
 592 }
 593 #endif
 594
 595 /* ----------------------------------------------------------------
 596  *              ExecMergeJoin
 597  * ----------------------------------------------------------------
 598  */
 599 static TupleTableSlot *
 600 ExecMergeJoin(PlanState *pstate)
 601 {
 602         MergeJoinState *node = castNode(MergeJoinState, pstate);
 603         ExprState  *joinqual;
 604         ExprState  *otherqual;
 605         bool            qualResult;
 606         int                     compareResult;
 607         PlanState  *innerPlan;
 608         TupleTableSlot *innerTupleSlot;
 609         PlanState  *outerPlan;
 610         TupleTableSlot *outerTupleSlot;
 611         ExprContext *econtext;
 612         bool            doFillOuter;
 613         bool            doFillInner;
 614
 615         CHECK_FOR_INTERRUPTS();
 616
 617         /*
 618          * get information from node
 619          */
 620         innerPlan = innerPlanState(node);
 621         outerPlan = outerPlanState(node);
 622         econtext = node->js.ps.ps_ExprContext;
 623         joinqual = node->js.joinqual;
 624         otherqual = node->js.ps.qual;
 625         doFillOuter = node->mj_FillOuter;
 626         doFillInner = node->mj_FillInner;
 627
 628         /*
 629          * Reset per-tuple memory context to free any expression evaluation
 630          * storage allocated in the previous tuple cycle.
 631          */
 632         ResetExprContext(econtext);
 633
 634         /*
 635          * ok, everything is setup.. let's go to work
 636          */
 637         for (;;)
 638         {
 639                 MJ_dump(node);
 640
 641                 /*
 642                  * get the current state of the join and do things accordingly.
 643                  */
 644                 switch (node->mj_JoinState)
 645                 {
 646                                 /*
 647                                  * EXEC_MJ_INITIALIZE_OUTER means that this is the first time
 648                                  * ExecMergeJoin() has been called and so we have to fetch the
 649                                  * first matchable tuple for both outer and inner subplans. We
 650                                  * do the outer side in INITIALIZE_OUTER state, then advance
 651                                  * to INITIALIZE_INNER state for the inner subplan.
 652                                  */
 653                         case EXEC_MJ_INITIALIZE_OUTER:
 654                                 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_OUTER\n");
 655
 656                                 outerTupleSlot = ExecProcNode(outerPlan);
 657                                 node->mj_OuterTupleSlot = outerTupleSlot;
 658
 659                                 /* Compute join values and check for unmatchability */
 660                                 switch (MJEvalOuterValues(node))
 661                                 {
 662                                         case MJEVAL_MATCHABLE:
 663                                                 /* OK to go get the first inner tuple */
 664                                                 node->mj_JoinState = EXEC_MJ_INITIALIZE_INNER;
 665                                                 break;
 666                                         case MJEVAL_NONMATCHABLE:
 667                                                 /* Stay in same state to fetch next outer tuple */
 668                                                 if (doFillOuter)
 669                                                 {
 670                                                         /*
 671                                                          * Generate a fake join tuple with nulls for the
 672                                                          * inner tuple, and return it if it passes the
 673                                                          * non-join quals.
 674                                                          */
 675                                                         TupleTableSlot *result;
 676
 677                                                         result = MJFillOuter(node);
 678                                                         if (result)
 679                                                                 return result;
 680                                                 }
 681                                                 break;
 682                                         case MJEVAL_ENDOFJOIN:
 683                                                 /* No more outer tuples */
 684                                                 MJ_printf("ExecMergeJoin: nothing in outer subplan\n");
 685                                                 if (doFillInner)
 686                                                 {
 687                                                         /*
 688                                                          * Need to emit right-join tuples for remaining
 689                                                          * inner tuples. We set MatchedInner = true to
 690                                                          * force the ENDOUTER state to advance inner.
 691                                                          */
 692                                                         node->mj_JoinState = EXEC_MJ_ENDOUTER;
 693                                                         node->mj_MatchedInner = true;
 694                                                         break;
 695                                                 }
 696                                                 /* Otherwise we're done. */
 697                                                 return NULL;
 698                                 }
 699                                 break;
 700
 701                         case EXEC_MJ_INITIALIZE_INNER:
 702                                 MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_INNER\n");
 703
 704                                 innerTupleSlot = ExecProcNode(innerPlan);
 705                                 node->mj_InnerTupleSlot = innerTupleSlot;
 706
 707                                 /* Compute join values and check for unmatchability */
 708                                 switch (MJEvalInnerValues(node, innerTupleSlot))
 709                                 {
 710                                         case MJEVAL_MATCHABLE:
 711
 712                                                 /*
 713                                                  * OK, we have the initial tuples.  Begin by skipping
 714                                                  * non-matching tuples.
 715                                                  */
 716                                                 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
 717                                                 break;
 718                                         case MJEVAL_NONMATCHABLE:
 719                                                 /* Mark before advancing, if wanted */
 720                                                 if (node->mj_ExtraMarks)
 721                                                         ExecMarkPos(innerPlan);
 722                                                 /* Stay in same state to fetch next inner tuple */
 723                                                 if (doFillInner)
 724                                                 {
 725                                                         /*
 726                                                          * Generate a fake join tuple with nulls for the
 727                                                          * outer tuple, and return it if it passes the
 728                                                          * non-join quals.
 729                                                          */
 730                                                         TupleTableSlot *result;
 731
 732                                                         result = MJFillInner(node);
 733                                                         if (result)
 734                                                                 return result;
 735                                                 }
 736                                                 break;
 737                                         case MJEVAL_ENDOFJOIN:
 738                                                 /* No more inner tuples */
 739                                                 MJ_printf("ExecMergeJoin: nothing in inner subplan\n");
 740                                                 if (doFillOuter)
 741                                                 {
 742                                                         /*
 743                                                          * Need to emit left-join tuples for all outer
 744                                                          * tuples, including the one we just fetched.  We
 745                                                          * set MatchedOuter = false to force the ENDINNER
 746                                                          * state to emit first tuple before advancing
 747                                                          * outer.
 748                                                          */
 749                                                         node->mj_JoinState = EXEC_MJ_ENDINNER;
 750                                                         node->mj_MatchedOuter = false;
 751                                                         break;
 752                                                 }
 753                                                 /* Otherwise we're done. */
 754                                                 return NULL;
 755                                 }
 756                                 break;
 757
 758                                 /*
 759                                  * EXEC_MJ_JOINTUPLES means we have two tuples which satisfied
 760                                  * the merge clause so we join them and then proceed to get
 761                                  * the next inner tuple (EXEC_MJ_NEXTINNER).
 762                                  */
 763                         case EXEC_MJ_JOINTUPLES:
 764                                 MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n");
 765
 766                                 /*
 767                                  * Set the next state machine state.  The right things will
 768                                  * happen whether we return this join tuple or just fall
 769                                  * through to continue the state machine execution.
 770                                  */
 771                                 node->mj_JoinState = EXEC_MJ_NEXTINNER;
 772
 773                                 /*
 774                                  * Check the extra qual conditions to see if we actually want
 775                                  * to return this join tuple.  If not, can proceed with merge.
 776                                  * We must distinguish the additional joinquals (which must
 777                                  * pass to consider the tuples "matched" for outer-join logic)
 778                                  * from the otherquals (which must pass before we actually
 779                                  * return the tuple).
 780                                  *
 781                                  * We don't bother with a ResetExprContext here, on the
 782                                  * assumption that we just did one while checking the merge
 783                                  * qual.  One per tuple should be sufficient.  We do have to
 784                                  * set up the econtext links to the tuples for ExecQual to
 785                                  * use.
 786                                  */
 787                                 outerTupleSlot = node->mj_OuterTupleSlot;
 788                                 econtext->ecxt_outertuple = outerTupleSlot;
 789                                 innerTupleSlot = node->mj_InnerTupleSlot;
 790                                 econtext->ecxt_innertuple = innerTupleSlot;
 791
 792                                 qualResult = (joinqual == NULL ||
 793                                                           ExecQual(joinqual, econtext));
 794                                 MJ_DEBUG_QUAL(joinqual, qualResult);
 795
 796                                 if (qualResult)
 797                                 {
 798                                         node->mj_MatchedOuter = true;
 799                                         node->mj_MatchedInner = true;
 800
 801                                         /* In an antijoin, we never return a matched tuple */
 802                                         if (node->js.jointype == JOIN_ANTI)
 803                                         {
 804                                                 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 805                                                 break;
 806                                         }
 807
 808                                         /*
 809                                          * If we only need to join to the first matching inner
 810                                          * tuple, then consider returning this one, but after that
 811                                          * continue with next outer tuple.
 812                                          */
 813                                         if (node->js.single_match)
 814                                                 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 815
 816                                         qualResult = (otherqual == NULL ||
 817                                                                   ExecQual(otherqual, econtext));
 818                                         MJ_DEBUG_QUAL(otherqual, qualResult);
 819
 820                                         if (qualResult)
 821                                         {
 822                                                 /*
 823                                                  * qualification succeeded.  now form the desired
 824                                                  * projection tuple and return the slot containing it.
 825                                                  */
 826                                                 MJ_printf("ExecMergeJoin: returning tuple\n");
 827
 828                                                 return ExecProject(node->js.ps.ps_ProjInfo);
 829                                         }
 830                                         else
 831                                                 InstrCountFiltered2(node, 1);
 832                                 }
 833                                 else
 834                                         InstrCountFiltered1(node, 1);
 835                                 break;
 836
 837                                 /*
 838                                  * EXEC_MJ_NEXTINNER means advance the inner scan to the next
 839                                  * tuple. If the tuple is not nil, we then proceed to test it
 840                                  * against the join qualification.
 841                                  *
 842                                  * Before advancing, we check to see if we must emit an
 843                                  * outer-join fill tuple for this inner tuple.
 844                                  */
 845                         case EXEC_MJ_NEXTINNER:
 846                                 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n");
 847
 848                                 if (doFillInner && !node->mj_MatchedInner)
 849                                 {
 850                                         /*
 851                                          * Generate a fake join tuple with nulls for the outer
 852                                          * tuple, and return it if it passes the non-join quals.
 853                                          */
 854                                         TupleTableSlot *result;
 855
 856                                         node->mj_MatchedInner = true;   /* do it only once */
 857
 858                                         result = MJFillInner(node);
 859                                         if (result)
 860                                                 return result;
 861                                 }
 862
 863                                 /*
 864                                  * now we get the next inner tuple, if any.  If there's none,
 865                                  * advance to next outer tuple (which may be able to join to
 866                                  * previously marked tuples).
 867                                  *
 868                                  * NB: must NOT do "extraMarks" here, since we may need to
 869                                  * return to previously marked tuples.
 870                                  */
 871                                 innerTupleSlot = ExecProcNode(innerPlan);
 872                                 node->mj_InnerTupleSlot = innerTupleSlot;
 873                                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
 874                                 node->mj_MatchedInner = false;
 875
 876                                 /* Compute join values and check for unmatchability */
 877                                 switch (MJEvalInnerValues(node, innerTupleSlot))
 878                                 {
 879                                         case MJEVAL_MATCHABLE:
 880
 881                                                 /*
 882                                                  * Test the new inner tuple to see if it matches
 883                                                  * outer.
 884                                                  *
 885                                                  * If they do match, then we join them and move on to
 886                                                  * the next inner tuple (EXEC_MJ_JOINTUPLES).
 887                                                  *
 888                                                  * If they do not match then advance to next outer
 889                                                  * tuple.
 890                                                  */
 891                                                 compareResult = MJCompare(node);
 892                                                 MJ_DEBUG_COMPARE(compareResult);
 893
 894                                                 if (compareResult == 0)
 895                                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
 896                                                 else
 897                                                 {
 898                                                         Assert(compareResult < 0);
 899                                                         node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 900                                                 }
 901                                                 break;
 902                                         case MJEVAL_NONMATCHABLE:
 903
 904                                                 /*
 905                                                  * It contains a NULL and hence can't match any outer
 906                                                  * tuple, so we can skip the comparison and assume the
 907                                                  * new tuple is greater than current outer.
 908                                                  */
 909                                                 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 910                                                 break;
 911                                         case MJEVAL_ENDOFJOIN:
 912
 913                                                 /*
 914                                                  * No more inner tuples.  However, this might be only
 915                                                  * effective and not physical end of inner plan, so
 916                                                  * force mj_InnerTupleSlot to null to make sure we
 917                                                  * don't fetch more inner tuples.  (We need this hack
 918                                                  * because we are not transiting to a state where the
 919                                                  * inner plan is assumed to be exhausted.)
 920                                                  */
 921                                                 node->mj_InnerTupleSlot = NULL;
 922                                                 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 923                                                 break;
 924                                 }
 925                                 break;
 926
 927                                 /*-------------------------------------------
 928                                  * EXEC_MJ_NEXTOUTER means
 929                                  *
 930                                  *                              outer inner
 931                                  * outer tuple -  5             5  - marked tuple
 932                                  *                                5             5
 933                                  *                                6             6  - inner tuple
 934                                  *                                7             7
 935                                  *
 936                                  * we know we just bumped into the
 937                                  * first inner tuple > current outer tuple (or possibly
 938                                  * the end of the inner stream)
 939                                  * so get a new outer tuple and then
 940                                  * proceed to test it against the marked tuple
 941                                  * (EXEC_MJ_TESTOUTER)
 942                                  *
 943                                  * Before advancing, we check to see if we must emit an
 944                                  * outer-join fill tuple for this outer tuple.
 945                                  *------------------------------------------------
 946                                  */
 947                         case EXEC_MJ_NEXTOUTER:
 948                                 MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n");
 949
 950                                 if (doFillOuter && !node->mj_MatchedOuter)
 951                                 {
 952                                         /*
 953                                          * Generate a fake join tuple with nulls for the inner
 954                                          * tuple, and return it if it passes the non-join quals.
 955                                          */
 956                                         TupleTableSlot *result;
 957
 958                                         node->mj_MatchedOuter = true;   /* do it only once */
 959
 960                                         result = MJFillOuter(node);
 961                                         if (result)
 962                                                 return result;
 963                                 }
 964
 965                                 /*
 966                                  * now we get the next outer tuple, if any
 967                                  */
 968                                 outerTupleSlot = ExecProcNode(outerPlan);
 969                                 node->mj_OuterTupleSlot = outerTupleSlot;
 970                                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
 971                                 node->mj_MatchedOuter = false;
 972
 973                                 /* Compute join values and check for unmatchability */
 974                                 switch (MJEvalOuterValues(node))
 975                                 {
 976                                         case MJEVAL_MATCHABLE:
 977                                                 /* Go test the new tuple against the marked tuple */
 978                                                 node->mj_JoinState = EXEC_MJ_TESTOUTER;
 979                                                 break;
 980                                         case MJEVAL_NONMATCHABLE:
 981                                                 /* Can't match, so fetch next outer tuple */
 982                                                 node->mj_JoinState = EXEC_MJ_NEXTOUTER;
 983                                                 break;
 984                                         case MJEVAL_ENDOFJOIN:
 985                                                 /* No more outer tuples */
 986                                                 MJ_printf("ExecMergeJoin: end of outer subplan\n");
 987                                                 innerTupleSlot = node->mj_InnerTupleSlot;
 988                                                 if (doFillInner && !TupIsNull(innerTupleSlot))
 989                                                 {
 990                                                         /*
 991                                                          * Need to emit right-join tuples for remaining
 992                                                          * inner tuples.
 993                                                          */
 994                                                         node->mj_JoinState = EXEC_MJ_ENDOUTER;
 995                                                         break;
 996                                                 }
 997                                                 /* Otherwise we're done. */
 998                                                 return NULL;
 999                                 }
1000                                 break;
1001
1002                                 /*--------------------------------------------------------
1003                                  * EXEC_MJ_TESTOUTER If the new outer tuple and the marked
1004                                  * tuple satisfy the merge clause then we know we have
1005                                  * duplicates in the outer scan so we have to restore the
1006                                  * inner scan to the marked tuple and proceed to join the
1007                                  * new outer tuple with the inner tuples.
1008                                  *
1009                                  * This is the case when
1010                                  *                                                outer inner
1011                                  *                                                      4         5  - marked tuple
1012                                  *                       outer tuple -  5         5
1013                                  *               new outer tuple -      5         5
1014                                  *                                                      6         8  - inner tuple
1015                                  *                                                      7        12
1016                                  *
1017                                  *                              new outer tuple == marked tuple
1018                                  *
1019                                  * If the outer tuple fails the test, then we are done
1020                                  * with the marked tuples, and we have to look for a
1021                                  * match to the current inner tuple.  So we will
1022                                  * proceed to skip outer tuples until outer >= inner
1023                                  * (EXEC_MJ_SKIP_TEST).
1024                                  *
1025                                  *              This is the case when
1026                                  *
1027                                  *                                                outer inner
1028                                  *                                                      5         5  - marked tuple
1029                                  *                       outer tuple -  5         5
1030                                  *               new outer tuple -      6         8  - inner tuple
1031                                  *                                                      7        12
1032                                  *
1033                                  *                              new outer tuple > marked tuple
1034                                  *
1035                                  *---------------------------------------------------------
1036                                  */
1037                         case EXEC_MJ_TESTOUTER:
1038                                 MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
1039
1040                                 /*
1041                                  * Here we must compare the outer tuple with the marked inner
1042                                  * tuple.  (We can ignore the result of MJEvalInnerValues,
1043                                  * since the marked inner tuple is certainly matchable.)
1044                                  */
1045                                 innerTupleSlot = node->mj_MarkedTupleSlot;
1046                                 (void) MJEvalInnerValues(node, innerTupleSlot);
1047
1048                                 compareResult = MJCompare(node);
1049                                 MJ_DEBUG_COMPARE(compareResult);
1050
1051                                 if (compareResult == 0)
1052                                 {
1053                                         /*
1054                                          * the merge clause matched so now we restore the inner
1055                                          * scan position to the first mark, and go join that tuple
1056                                          * (and any following ones) to the new outer.
1057                                          *
1058                                          * If we were able to determine mark and restore are not
1059                                          * needed, then we don't have to back up; the current
1060                                          * inner is already the first possible match.
1061                                          *
1062                                          * NOTE: we do not need to worry about the MatchedInner
1063                                          * state for the rescanned inner tuples.  We know all of
1064                                          * them will match this new outer tuple and therefore
1065                                          * won't be emitted as fill tuples.  This works *only*
1066                                          * because we require the extra joinquals to be constant
1067                                          * when doing a right or full join --- otherwise some of
1068                                          * the rescanned tuples might fail the extra joinquals.
1069                                          * This obviously won't happen for a constant-true extra
1070                                          * joinqual, while the constant-false case is handled by
1071                                          * forcing the merge clause to never match, so we never
1072                                          * get here.
1073                                          */
1074                                         if (!node->mj_SkipMarkRestore)
1075                                         {
1076                                                 ExecRestrPos(innerPlan);
1077
1078                                                 /*
1079                                                  * ExecRestrPos probably should give us back a new
1080                                                  * Slot, but since it doesn't, use the marked slot.
1081                                                  * (The previously returned mj_InnerTupleSlot cannot
1082                                                  * be assumed to hold the required tuple.)
1083                                                  */
1084                                                 node->mj_InnerTupleSlot = innerTupleSlot;
1085                                                 /* we need not do MJEvalInnerValues again */
1086                                         }
1087
1088                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1089                                 }
1090                                 else
1091                                 {
1092                                         /* ----------------
1093                                          *      if the new outer tuple didn't match the marked inner
1094                                          *      tuple then we have a case like:
1095                                          *
1096                                          *                       outer inner
1097                                          *                         4     4      - marked tuple
1098                                          * new outer - 5         4
1099                                          *                         6     5      - inner tuple
1100                                          *                         7
1101                                          *
1102                                          *      which means that all subsequent outer tuples will be
1103                                          *      larger than our marked inner tuples.  So we need not
1104                                          *      revisit any of the marked tuples but can proceed to
1105                                          *      look for a match to the current inner.  If there's
1106                                          *      no more inners, no more matches are possible.
1107                                          * ----------------
1108                                          */
1109                                         Assert(compareResult > 0);
1110                                         innerTupleSlot = node->mj_InnerTupleSlot;
1111
1112                                         /* reload comparison data for current inner */
1113                                         switch (MJEvalInnerValues(node, innerTupleSlot))
1114                                         {
1115                                                 case MJEVAL_MATCHABLE:
1116                                                         /* proceed to compare it to the current outer */
1117                                                         node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1118                                                         break;
1119                                                 case MJEVAL_NONMATCHABLE:
1120
1121                                                         /*
1122                                                          * current inner can't possibly match any outer;
1123                                                          * better to advance the inner scan than the
1124                                                          * outer.
1125                                                          */
1126                                                         node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1127                                                         break;
1128                                                 case MJEVAL_ENDOFJOIN:
1129                                                         /* No more inner tuples */
1130                                                         if (doFillOuter)
1131                                                         {
1132                                                                 /*
1133                                                                  * Need to emit left-join tuples for remaining
1134                                                                  * outer tuples.
1135                                                                  */
1136                                                                 node->mj_JoinState = EXEC_MJ_ENDINNER;
1137                                                                 break;
1138                                                         }
1139                                                         /* Otherwise we're done. */
1140                                                         return NULL;
1141                                         }
1142                                 }
1143                                 break;
1144
1145                                 /*----------------------------------------------------------
1146                                  * EXEC_MJ_SKIP means compare tuples and if they do not
1147                                  * match, skip whichever is lesser.
1148                                  *
1149                                  * For example:
1150                                  *
1151                                  *                              outer inner
1152                                  *                                5             5
1153                                  *                                5             5
1154                                  * outer tuple -  6             8  - inner tuple
1155                                  *                                7    12
1156                                  *                                8    14
1157                                  *
1158                                  * we have to advance the outer scan
1159                                  * until we find the outer 8.
1160                                  *
1161                                  * On the other hand:
1162                                  *
1163                                  *                              outer inner
1164                                  *                                5             5
1165                                  *                                5             5
1166                                  * outer tuple - 12             8  - inner tuple
1167                                  *                               14    10
1168                                  *                               17    12
1169                                  *
1170                                  * we have to advance the inner scan
1171                                  * until we find the inner 12.
1172                                  *----------------------------------------------------------
1173                                  */
1174                         case EXEC_MJ_SKIP_TEST:
1175                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIP_TEST\n");
1176
1177                                 /*
1178                                  * before we advance, make sure the current tuples do not
1179                                  * satisfy the mergeclauses.  If they do, then we update the
1180                                  * marked tuple position and go join them.
1181                                  */
1182                                 compareResult = MJCompare(node);
1183                                 MJ_DEBUG_COMPARE(compareResult);
1184
1185                                 if (compareResult == 0)
1186                                 {
1187                                         if (!node->mj_SkipMarkRestore)
1188                                                 ExecMarkPos(innerPlan);
1189
1190                                         MarkInnerTuple(node->mj_InnerTupleSlot, node);
1191
1192                                         node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1193                                 }
1194                                 else if (compareResult < 0)
1195                                         node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
1196                                 else
1197                                         /* compareResult > 0 */
1198                                         node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1199                                 break;
1200
1201                                 /*
1202                                  * SKIPOUTER_ADVANCE: advance over an outer tuple that is
1203                                  * known not to join to any inner tuple.
1204                                  *
1205                                  * Before advancing, we check to see if we must emit an
1206                                  * outer-join fill tuple for this outer tuple.
1207                                  */
1208                         case EXEC_MJ_SKIPOUTER_ADVANCE:
1209                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_ADVANCE\n");
1210
1211                                 if (doFillOuter && !node->mj_MatchedOuter)
1212                                 {
1213                                         /*
1214                                          * Generate a fake join tuple with nulls for the inner
1215                                          * tuple, and return it if it passes the non-join quals.
1216                                          */
1217                                         TupleTableSlot *result;
1218
1219                                         node->mj_MatchedOuter = true;   /* do it only once */
1220
1221                                         result = MJFillOuter(node);
1222                                         if (result)
1223                                                 return result;
1224                                 }
1225
1226                                 /*
1227                                  * now we get the next outer tuple, if any
1228                                  */
1229                                 outerTupleSlot = ExecProcNode(outerPlan);
1230                                 node->mj_OuterTupleSlot = outerTupleSlot;
1231                                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1232                                 node->mj_MatchedOuter = false;
1233
1234                                 /* Compute join values and check for unmatchability */
1235                                 switch (MJEvalOuterValues(node))
1236                                 {
1237                                         case MJEVAL_MATCHABLE:
1238                                                 /* Go test the new tuple against the current inner */
1239                                                 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1240                                                 break;
1241                                         case MJEVAL_NONMATCHABLE:
1242                                                 /* Can't match, so fetch next outer tuple */
1243                                                 node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
1244                                                 break;
1245                                         case MJEVAL_ENDOFJOIN:
1246                                                 /* No more outer tuples */
1247                                                 MJ_printf("ExecMergeJoin: end of outer subplan\n");
1248                                                 innerTupleSlot = node->mj_InnerTupleSlot;
1249                                                 if (doFillInner && !TupIsNull(innerTupleSlot))
1250                                                 {
1251                                                         /*
1252                                                          * Need to emit right-join tuples for remaining
1253                                                          * inner tuples.
1254                                                          */
1255                                                         node->mj_JoinState = EXEC_MJ_ENDOUTER;
1256                                                         break;
1257                                                 }
1258                                                 /* Otherwise we're done. */
1259                                                 return NULL;
1260                                 }
1261                                 break;
1262
1263                                 /*
1264                                  * SKIPINNER_ADVANCE: advance over an inner tuple that is
1265                                  * known not to join to any outer tuple.
1266                                  *
1267                                  * Before advancing, we check to see if we must emit an
1268                                  * outer-join fill tuple for this inner tuple.
1269                                  */
1270                         case EXEC_MJ_SKIPINNER_ADVANCE:
1271                                 MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_ADVANCE\n");
1272
1273                                 if (doFillInner && !node->mj_MatchedInner)
1274                                 {
1275                                         /*
1276                                          * Generate a fake join tuple with nulls for the outer
1277                                          * tuple, and return it if it passes the non-join quals.
1278                                          */
1279                                         TupleTableSlot *result;
1280
1281                                         node->mj_MatchedInner = true;   /* do it only once */
1282
1283                                         result = MJFillInner(node);
1284                                         if (result)
1285                                                 return result;
1286                                 }
1287
1288                                 /* Mark before advancing, if wanted */
1289                                 if (node->mj_ExtraMarks)
1290                                         ExecMarkPos(innerPlan);
1291
1292                                 /*
1293                                  * now we get the next inner tuple, if any
1294                                  */
1295                                 innerTupleSlot = ExecProcNode(innerPlan);
1296                                 node->mj_InnerTupleSlot = innerTupleSlot;
1297                                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1298                                 node->mj_MatchedInner = false;
1299
1300                                 /* Compute join values and check for unmatchability */
1301                                 switch (MJEvalInnerValues(node, innerTupleSlot))
1302                                 {
1303                                         case MJEVAL_MATCHABLE:
1304                                                 /* proceed to compare it to the current outer */
1305                                                 node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1306                                                 break;
1307                                         case MJEVAL_NONMATCHABLE:
1308
1309                                                 /*
1310                                                  * current inner can't possibly match any outer;
1311                                                  * better to advance the inner scan than the outer.
1312                                                  */
1313                                                 node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1314                                                 break;
1315                                         case MJEVAL_ENDOFJOIN:
1316                                                 /* No more inner tuples */
1317                                                 MJ_printf("ExecMergeJoin: end of inner subplan\n");
1318                                                 outerTupleSlot = node->mj_OuterTupleSlot;
1319                                                 if (doFillOuter && !TupIsNull(outerTupleSlot))
1320                                                 {
1321                                                         /*
1322                                                          * Need to emit left-join tuples for remaining
1323                                                          * outer tuples.
1324                                                          */
1325                                                         node->mj_JoinState = EXEC_MJ_ENDINNER;
1326                                                         break;
1327                                                 }
1328                                                 /* Otherwise we're done. */
1329                                                 return NULL;
1330                                 }
1331                                 break;
1332
1333                                 /*
1334                                  * EXEC_MJ_ENDOUTER means we have run out of outer tuples, but
1335                                  * are doing a right/full join and therefore must null-fill
1336                                  * any remaining unmatched inner tuples.
1337                                  */
1338                         case EXEC_MJ_ENDOUTER:
1339                                 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDOUTER\n");
1340
1341                                 Assert(doFillInner);
1342
1343                                 if (!node->mj_MatchedInner)
1344                                 {
1345                                         /*
1346                                          * Generate a fake join tuple with nulls for the outer
1347                                          * tuple, and return it if it passes the non-join quals.
1348                                          */
1349                                         TupleTableSlot *result;
1350
1351                                         node->mj_MatchedInner = true;   /* do it only once */
1352
1353                                         result = MJFillInner(node);
1354                                         if (result)
1355                                                 return result;
1356                                 }
1357
1358                                 /* Mark before advancing, if wanted */
1359                                 if (node->mj_ExtraMarks)
1360                                         ExecMarkPos(innerPlan);
1361
1362                                 /*
1363                                  * now we get the next inner tuple, if any
1364                                  */
1365                                 innerTupleSlot = ExecProcNode(innerPlan);
1366                                 node->mj_InnerTupleSlot = innerTupleSlot;
1367                                 MJ_DEBUG_PROC_NODE(innerTupleSlot);
1368                                 node->mj_MatchedInner = false;
1369
1370                                 if (TupIsNull(innerTupleSlot))
1371                                 {
1372                                         MJ_printf("ExecMergeJoin: end of inner subplan\n");
1373                                         return NULL;
1374                                 }
1375
1376                                 /* Else remain in ENDOUTER state and process next tuple. */
1377                                 break;
1378
1379                                 /*
1380                                  * EXEC_MJ_ENDINNER means we have run out of inner tuples, but
1381                                  * are doing a left/full join and therefore must null- fill
1382                                  * any remaining unmatched outer tuples.
1383                                  */
1384                         case EXEC_MJ_ENDINNER:
1385                                 MJ_printf("ExecMergeJoin: EXEC_MJ_ENDINNER\n");
1386
1387                                 Assert(doFillOuter);
1388
1389                                 if (!node->mj_MatchedOuter)
1390                                 {
1391                                         /*
1392                                          * Generate a fake join tuple with nulls for the inner
1393                                          * tuple, and return it if it passes the non-join quals.
1394                                          */
1395                                         TupleTableSlot *result;
1396
1397                                         node->mj_MatchedOuter = true;   /* do it only once */
1398
1399                                         result = MJFillOuter(node);
1400                                         if (result)
1401                                                 return result;
1402                                 }
1403
1404                                 /*
1405                                  * now we get the next outer tuple, if any
1406                                  */
1407                                 outerTupleSlot = ExecProcNode(outerPlan);
1408                                 node->mj_OuterTupleSlot = outerTupleSlot;
1409                                 MJ_DEBUG_PROC_NODE(outerTupleSlot);
1410                                 node->mj_MatchedOuter = false;
1411
1412                                 if (TupIsNull(outerTupleSlot))
1413                                 {
1414                                         MJ_printf("ExecMergeJoin: end of outer subplan\n");
1415                                         return NULL;
1416                                 }
1417
1418                                 /* Else remain in ENDINNER state and process next tuple. */
1419                                 break;
1420
1421                                 /*
1422                                  * broken state value?
1423                                  */
1424                         default:
1425                                 elog(ERROR, "unrecognized mergejoin state: %d",
1426                                          (int) node->mj_JoinState);
1427                 }
1428         }
1429 }
1430
1431 /* ----------------------------------------------------------------
1432  *              ExecInitMergeJoin
1433  * ----------------------------------------------------------------
1434  */
1435 MergeJoinState *
1436 ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
1437 {
1438         MergeJoinState *mergestate;
1439         TupleDesc       outerDesc,
1440                                 innerDesc;
1441         const TupleTableSlotOps *innerOps;
1442
1443         /* check for unsupported flags */
1444         Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
1445
1446         MJ1_printf("ExecInitMergeJoin: %s\n",
1447                            "initializing node");
1448
1449         /*
1450          * create state structure
1451          */
1452         mergestate = makeNode(MergeJoinState);
1453         mergestate->js.ps.plan = (Plan *) node;
1454         mergestate->js.ps.state = estate;
1455         mergestate->js.ps.ExecProcNode = ExecMergeJoin;
1456         mergestate->js.jointype = node->join.jointype;
1457         mergestate->mj_ConstFalseJoin = false;
1458
1459         /*
1460          * Miscellaneous initialization
1461          *
1462          * create expression context for node
1463          */
1464         ExecAssignExprContext(estate, &mergestate->js.ps);
1465
1466         /*
1467          * we need two additional econtexts in which we can compute the join
1468          * expressions from the left and right input tuples.  The node's regular
1469          * econtext won't do because it gets reset too often.
1470          */
1471         mergestate->mj_OuterEContext = CreateExprContext(estate);
1472         mergestate->mj_InnerEContext = CreateExprContext(estate);
1473
1474         /*
1475          * initialize child nodes
1476          *
1477          * inner child must support MARK/RESTORE, unless we have detected that we
1478          * don't need that.  Note that skip_mark_restore must never be set if
1479          * there are non-mergeclause joinquals, since the logic wouldn't work.
1480          */
1481         Assert(node->join.joinqual == NIL || !node->skip_mark_restore);
1482         mergestate->mj_SkipMarkRestore = node->skip_mark_restore;
1483
1484         outerPlanState(mergestate) = ExecInitNode(outerPlan(node), estate, eflags);
1485         outerDesc = ExecGetResultType(outerPlanState(mergestate));
1486         innerPlanState(mergestate) = ExecInitNode(innerPlan(node), estate,
1487                                                                                           mergestate->mj_SkipMarkRestore ?
1488                                                                                           eflags :
1489                                                                                           (eflags | EXEC_FLAG_MARK));
1490         innerDesc = ExecGetResultType(innerPlanState(mergestate));
1491
1492         /*
1493          * For certain types of inner child nodes, it is advantageous to issue
1494          * MARK every time we advance past an inner tuple we will never return to.
1495          * For other types, MARK on a tuple we cannot return to is a waste of
1496          * cycles.  Detect which case applies and set mj_ExtraMarks if we want to
1497          * issue "unnecessary" MARK calls.
1498          *
1499          * Currently, only Material wants the extra MARKs, and it will be helpful
1500          * only if eflags doesn't specify REWIND.
1501          *
1502          * Note that for IndexScan and IndexOnlyScan, it is *necessary* that we
1503          * not set mj_ExtraMarks; otherwise we might attempt to set a mark before
1504          * the first inner tuple, which they do not support.
1505          */
1506         if (IsA(innerPlan(node), Material) &&
1507                 (eflags & EXEC_FLAG_REWIND) == 0 &&
1508                 !mergestate->mj_SkipMarkRestore)
1509                 mergestate->mj_ExtraMarks = true;
1510         else
1511                 mergestate->mj_ExtraMarks = false;
1512
1513         /*
1514          * Initialize result slot, type and projection.
1515          */
1516         ExecInitResultTupleSlotTL(&mergestate->js.ps, &TTSOpsVirtual);
1517         ExecAssignProjectionInfo(&mergestate->js.ps, NULL);
1518
1519         /*
1520          * tuple table initialization
1521          */
1522         innerOps = ExecGetResultSlotOps(innerPlanState(mergestate), NULL);
1523         mergestate->mj_MarkedTupleSlot = ExecInitExtraTupleSlot(estate, innerDesc,
1524                                                                                                                         innerOps);
1525
1526         /*
1527          * initialize child expressions
1528          */
1529         mergestate->js.ps.qual =
1530                 ExecInitQual(node->join.plan.qual, (PlanState *) mergestate);
1531         mergestate->js.joinqual =
1532                 ExecInitQual(node->join.joinqual, (PlanState *) mergestate);
1533         /* mergeclauses are handled below */
1534
1535         /*
1536          * detect whether we need only consider the first matching inner tuple
1537          */
1538         mergestate->js.single_match = (node->join.inner_unique ||
1539                                                                    node->join.jointype == JOIN_SEMI);
1540
1541         /* set up null tuples for outer joins, if needed */
1542         switch (node->join.jointype)
1543         {
1544                 case JOIN_INNER:
1545                 case JOIN_SEMI:
1546                         mergestate->mj_FillOuter = false;
1547                         mergestate->mj_FillInner = false;
1548                         break;
1549                 case JOIN_LEFT:
1550                 case JOIN_ANTI:
1551                         mergestate->mj_FillOuter = true;
1552                         mergestate->mj_FillInner = false;
1553                         mergestate->mj_NullInnerTupleSlot =
1554                                 ExecInitNullTupleSlot(estate, innerDesc, &TTSOpsVirtual);
1555                         break;
1556                 case JOIN_RIGHT:
1557                         mergestate->mj_FillOuter = false;
1558                         mergestate->mj_FillInner = true;
1559                         mergestate->mj_NullOuterTupleSlot =
1560                                 ExecInitNullTupleSlot(estate, outerDesc, &TTSOpsVirtual);
1561
1562                         /*
1563                          * Can't handle right or full join with non-constant extra
1564                          * joinclauses.  This should have been caught by planner.
1565                          */
1566                         if (!check_constant_qual(node->join.joinqual,
1567                                                                          &mergestate->mj_ConstFalseJoin))
1568                                 ereport(ERROR,
1569                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1570                                                  errmsg("RIGHT JOIN is only supported with merge-joinable join conditions")));
1571                         break;
1572                 case JOIN_FULL:
1573                         mergestate->mj_FillOuter = true;
1574                         mergestate->mj_FillInner = true;
1575                         mergestate->mj_NullOuterTupleSlot =
1576                                 ExecInitNullTupleSlot(estate, outerDesc, &TTSOpsVirtual);
1577                         mergestate->mj_NullInnerTupleSlot =
1578                                 ExecInitNullTupleSlot(estate, innerDesc, &TTSOpsVirtual);
1579
1580                         /*
1581                          * Can't handle right or full join with non-constant extra
1582                          * joinclauses.  This should have been caught by planner.
1583                          */
1584                         if (!check_constant_qual(node->join.joinqual,
1585                                                                          &mergestate->mj_ConstFalseJoin))
1586                                 ereport(ERROR,
1587                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1588                                                  errmsg("FULL JOIN is only supported with merge-joinable join conditions")));
1589                         break;
1590                 default:
1591                         elog(ERROR, "unrecognized join type: %d",
1592                                  (int) node->join.jointype);
1593         }
1594
1595         /*
1596          * preprocess the merge clauses
1597          */
1598         mergestate->mj_NumClauses = list_length(node->mergeclauses);
1599         mergestate->mj_Clauses = MJExamineQuals(node->mergeclauses,
1600                                                                                         node->mergeFamilies,
1601                                                                                         node->mergeCollations,
1602                                                                                         node->mergeStrategies,
1603                                                                                         node->mergeNullsFirst,
1604                                                                                         (PlanState *) mergestate);
1605
1606         /*
1607          * initialize join state
1608          */
1609         mergestate->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1610         mergestate->mj_MatchedOuter = false;
1611         mergestate->mj_MatchedInner = false;
1612         mergestate->mj_OuterTupleSlot = NULL;
1613         mergestate->mj_InnerTupleSlot = NULL;
1614
1615         /*
1616          * initialization successful
1617          */
1618         MJ1_printf("ExecInitMergeJoin: %s\n",
1619                            "node initialized");
1620
1621         return mergestate;
1622 }
1623
1624 /* ----------------------------------------------------------------
1625  *              ExecEndMergeJoin
1626  *
1627  * old comments
1628  *              frees storage allocated through C routines.
1629  * ----------------------------------------------------------------
1630  */
1631 void
1632 ExecEndMergeJoin(MergeJoinState *node)
1633 {
1634         MJ1_printf("ExecEndMergeJoin: %s\n",
1635                            "ending node processing");
1636
1637         /*
1638          * Free the exprcontext
1639          */
1640         ExecFreeExprContext(&node->js.ps);
1641
1642         /*
1643          * clean out the tuple table
1644          */
1645         ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
1646         ExecClearTuple(node->mj_MarkedTupleSlot);
1647
1648         /*
1649          * shut down the subplans
1650          */
1651         ExecEndNode(innerPlanState(node));
1652         ExecEndNode(outerPlanState(node));
1653
1654         MJ1_printf("ExecEndMergeJoin: %s\n",
1655                            "node processing ended");
1656 }
1657
1658 void
1659 ExecReScanMergeJoin(MergeJoinState *node)
1660 {
1661         ExecClearTuple(node->mj_MarkedTupleSlot);
1662
1663         node->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1664         node->mj_MatchedOuter = false;
1665         node->mj_MatchedInner = false;
1666         node->mj_OuterTupleSlot = NULL;
1667         node->mj_InnerTupleSlot = NULL;
1668
1669         /*
1670          * if chgParam of subnodes is not null then plans will be re-scanned by
1671          * first ExecProcNode.
1672          */
1673         if (node->js.ps.lefttree->chgParam == NULL)
1674                 ExecReScan(node->js.ps.lefttree);
1675         if (node->js.ps.righttree->chgParam == NULL)
1676                 ExecReScan(node->js.ps.righttree);
1677
1678 }