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