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