PostgreSQL Source Code: src/backend/executor/nodeMergejoin.c Source File

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

AltStyle によって変換されたページ (->オリジナル) /