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