src/backend/executor/nodeMergejoin.c

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