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