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