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