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