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