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