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