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