1/*-------------------------------------------------------------------------
2 *
3 * nodeMergejoin.c
4 * routines supporting merge joins
5 *
6 * Portions Copyright (c) 1996-2019, 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 */
121typedef 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 */
144typedef 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 */
175static MergeJoinClause
176MJExamineQuals(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 */
294static MJEvalResult
295MJEvalOuterValues(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 */
341static MJEvalResult
342MJEvalInnerValues(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 */
391static int
392MJCompare(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 */
452static TupleTableSlot *
453MJFillOuter(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 */
483static TupleTableSlot *
484MJFillInner(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 */
519static bool
520check_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
546static void
547ExecMergeTupleDumpOuter(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
558static void
559ExecMergeTupleDumpInner(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
570static void
571ExecMergeTupleDumpMarked(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
582static void
583ExecMergeTupleDump(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 */
599static TupleTableSlot *
600ExecMergeJoin(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 */
1435MergeJoinState *
1436ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
1437{
1438 MergeJoinState *mergestate;
1439 TupleDesc outerDesc,
1440 innerDesc;
1441 const TupleTableSlotOps *innerOps;
1442
1443 /* check for unsupported flags */
1444 Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
1445
1446 MJ1_printf("ExecInitMergeJoin: %s\n",
1447 "initializing node");
1448
1449 /*
1450 * create state structure
1451 */
1452 mergestate = makeNode(MergeJoinState);
1453 mergestate->js.ps.plan = (Plan *) node;
1454 mergestate->js.ps.state = estate;
1455 mergestate->js.ps.ExecProcNode = ExecMergeJoin;
1456 mergestate->js.jointype = node->join.jointype;
1457 mergestate->mj_ConstFalseJoin = false;
1458
1459 /*
1460 * Miscellaneous initialization
1461 *
1462 * create expression context for node
1463 */
1464 ExecAssignExprContext(estate, &mergestate->js.ps);
1465
1466 /*
1467 * we need two additional econtexts in which we can compute the join
1468 * expressions from the left and right input tuples. The node's regular
1469 * econtext won't do because it gets reset too often.
1470 */
1471 mergestate->mj_OuterEContext = CreateExprContext(estate);
1472 mergestate->mj_InnerEContext = CreateExprContext(estate);
1473
1474 /*
1475 * initialize child nodes
1476 *
1477 * inner child must support MARK/RESTORE, unless we have detected that we
1478 * don't need that. Note that skip_mark_restore must never be set if
1479 * there are non-mergeclause joinquals, since the logic wouldn't work.
1480 */
1481 Assert(node->join.joinqual == NIL || !node->skip_mark_restore);
1482 mergestate->mj_SkipMarkRestore = node->skip_mark_restore;
1483
1484 outerPlanState(mergestate) = ExecInitNode(outerPlan(node), estate, eflags);
1485 outerDesc = ExecGetResultType(outerPlanState(mergestate));
1486 innerPlanState(mergestate) = ExecInitNode(innerPlan(node), estate,
1487 mergestate->mj_SkipMarkRestore ?
1488 eflags :
1489 (eflags | EXEC_FLAG_MARK));
1490 innerDesc = ExecGetResultType(innerPlanState(mergestate));
1491
1492 /*
1493 * For certain types of inner child nodes, it is advantageous to issue
1494 * MARK every time we advance past an inner tuple we will never return to.
1495 * For other types, MARK on a tuple we cannot return to is a waste of
1496 * cycles. Detect which case applies and set mj_ExtraMarks if we want to
1497 * issue "unnecessary" MARK calls.
1498 *
1499 * Currently, only Material wants the extra MARKs, and it will be helpful
1500 * only if eflags doesn't specify REWIND.
1501 *
1502 * Note that for IndexScan and IndexOnlyScan, it is *necessary* that we
1503 * not set mj_ExtraMarks; otherwise we might attempt to set a mark before
1504 * the first inner tuple, which they do not support.
1505 */
1506 if (IsA(innerPlan(node), Material) &&
1507 (eflags & EXEC_FLAG_REWIND) == 0 &&
1508 !mergestate->mj_SkipMarkRestore)
1509 mergestate->mj_ExtraMarks = true;
1510 else
1511 mergestate->mj_ExtraMarks = false;
1512
1513 /*
1514 * Initialize result slot, type and projection.
1515 */
1516 ExecInitResultTupleSlotTL(&mergestate->js.ps, &TTSOpsVirtual);
1517 ExecAssignProjectionInfo(&mergestate->js.ps, NULL);
1518
1519 /*
1520 * tuple table initialization
1521 */
1522 innerOps = ExecGetResultSlotOps(innerPlanState(mergestate), NULL);
1523 mergestate->mj_MarkedTupleSlot = ExecInitExtraTupleSlot(estate, innerDesc,
1524 innerOps);
1525
1526 /*
1527 * initialize child expressions
1528 */
1529 mergestate->js.ps.qual =
1530 ExecInitQual(node->join.plan.qual, (PlanState *) mergestate);
1531 mergestate->js.joinqual =
1532 ExecInitQual(node->join.joinqual, (PlanState *) mergestate);
1533 /* mergeclauses are handled below */
1534
1535 /*
1536 * detect whether we need only consider the first matching inner tuple
1537 */
1538 mergestate->js.single_match = (node->join.inner_unique ||
1539 node->join.jointype == JOIN_SEMI);
1540
1541 /* set up null tuples for outer joins, if needed */
1542 switch (node->join.jointype)
1543 {
1544 case JOIN_INNER:
1545 case JOIN_SEMI:
1546 mergestate->mj_FillOuter = false;
1547 mergestate->mj_FillInner = false;
1548 break;
1549 case JOIN_LEFT:
1550 case JOIN_ANTI:
1551 mergestate->mj_FillOuter = true;
1552 mergestate->mj_FillInner = false;
1553 mergestate->mj_NullInnerTupleSlot =
1554 ExecInitNullTupleSlot(estate, innerDesc, &TTSOpsVirtual);
1555 break;
1556 case JOIN_RIGHT:
1557 mergestate->mj_FillOuter = false;
1558 mergestate->mj_FillInner = true;
1559 mergestate->mj_NullOuterTupleSlot =
1560 ExecInitNullTupleSlot(estate, outerDesc, &TTSOpsVirtual);
1561
1562 /*
1563 * Can't handle right or full join with non-constant extra
1564 * joinclauses. This should have been caught by planner.
1565 */
1566 if (!check_constant_qual(node->join.joinqual,
1567 &mergestate->mj_ConstFalseJoin))
1568 ereport(ERROR,
1569 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1570 errmsg("RIGHT JOIN is only supported with merge-joinable join conditions")));
1571 break;
1572 case JOIN_FULL:
1573 mergestate->mj_FillOuter = true;
1574 mergestate->mj_FillInner = true;
1575 mergestate->mj_NullOuterTupleSlot =
1576 ExecInitNullTupleSlot(estate, outerDesc, &TTSOpsVirtual);
1577 mergestate->mj_NullInnerTupleSlot =
1578 ExecInitNullTupleSlot(estate, innerDesc, &TTSOpsVirtual);
1579
1580 /*
1581 * Can't handle right or full join with non-constant extra
1582 * joinclauses. This should have been caught by planner.
1583 */
1584 if (!check_constant_qual(node->join.joinqual,
1585 &mergestate->mj_ConstFalseJoin))
1586 ereport(ERROR,
1587 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1588 errmsg("FULL JOIN is only supported with merge-joinable join conditions")));
1589 break;
1590 default:
1591 elog(ERROR, "unrecognized join type: %d",
1592 (int) node->join.jointype);
1593 }
1594
1595 /*
1596 * preprocess the merge clauses
1597 */
1598 mergestate->mj_NumClauses = list_length(node->mergeclauses);
1599 mergestate->mj_Clauses = MJExamineQuals(node->mergeclauses,
1600 node->mergeFamilies,
1601 node->mergeCollations,
1602 node->mergeStrategies,
1603 node->mergeNullsFirst,
1604 (PlanState *) mergestate);
1605
1606 /*
1607 * initialize join state
1608 */
1609 mergestate->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1610 mergestate->mj_MatchedOuter = false;
1611 mergestate->mj_MatchedInner = false;
1612 mergestate->mj_OuterTupleSlot = NULL;
1613 mergestate->mj_InnerTupleSlot = NULL;
1614
1615 /*
1616 * initialization successful
1617 */
1618 MJ1_printf("ExecInitMergeJoin: %s\n",
1619 "node initialized");
1620
1621 return mergestate;
1622}
1623
1624/* ----------------------------------------------------------------
1625 * ExecEndMergeJoin
1626 *
1627 * old comments
1628 * frees storage allocated through C routines.
1629 * ----------------------------------------------------------------
1630 */
1631void
1632ExecEndMergeJoin(MergeJoinState *node)
1633{
1634 MJ1_printf("ExecEndMergeJoin: %s\n",
1635 "ending node processing");
1636
1637 /*
1638 * Free the exprcontext
1639 */
1640 ExecFreeExprContext(&node->js.ps);
1641
1642 /*
1643 * clean out the tuple table
1644 */
1645 ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
1646 ExecClearTuple(node->mj_MarkedTupleSlot);
1647
1648 /*
1649 * shut down the subplans
1650 */
1651 ExecEndNode(innerPlanState(node));
1652 ExecEndNode(outerPlanState(node));
1653
1654 MJ1_printf("ExecEndMergeJoin: %s\n",
1655 "node processing ended");
1656}
1657
1658void
1659ExecReScanMergeJoin(MergeJoinState *node)
1660{
1661 ExecClearTuple(node->mj_MarkedTupleSlot);
1662
1663 node->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1664 node->mj_MatchedOuter = false;
1665 node->mj_MatchedInner = false;
1666 node->mj_OuterTupleSlot = NULL;
1667 node->mj_InnerTupleSlot = NULL;
1668
1669 /*
1670 * if chgParam of subnodes is not null then plans will be re-scanned by
1671 * first ExecProcNode.
1672 */
1673 if (node->js.ps.lefttree->chgParam == NULL)
1674 ExecReScan(node->js.ps.lefttree);
1675 if (node->js.ps.righttree->chgParam == NULL)
1676 ExecReScan(node->js.ps.righttree);
1677
1678}
1679