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