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