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