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