src/backend/executor/nodeMergejoin.c

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