1
/*-------------------------------------------------------------------------
4
* routines supporting merge joins
6
* Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
7
* Portions Copyright (c) 1994, Regents of the University of California
13
*-------------------------------------------------------------------------
17
* ExecMergeJoin mergejoin outer and inner relations.
18
* ExecInitMergeJoin creates and initializes run time states
19
* ExecEndMergeJoin cleans up the node.
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).
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
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
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.
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.
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.
61
* Essential operation of the merge join algorithm is as follows:
64
* get initial outer and inner tuples INITIALIZE
66
* while (outer != inner) { SKIP_TEST
68
* advance outer SKIPOUTER_ADVANCE
70
* advance inner SKIPINNER_ADVANCE
72
* mark inner position SKIP_TEST
74
* while (outer == inner) {
75
* join tuples JOINTUPLES
76
* advance inner position NEXTINNER
78
* advance outer position NEXTOUTER
79
* if (outer == mark) TESTOUTER
80
* restore inner position to mark TESTOUTER
82
* break // return to top of outer loop
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
95
#include "access/nbtree.h"
96
#include "catalog/pg_amop.h"
97
#include "executor/execdebug.h"
98
#include "executor/execdefs.h"
99
#include "executor/nodeMergejoin.h"
100
#include "miscadmin.h"
101
#include "utils/acl.h"
102
#include "utils/lsyscache.h"
103
#include "utils/memutils.h"
104
#include "utils/syscache.h"
108
* Runtime data for each mergejoin clause
110
typedef struct MergeJoinClauseData
112
/* Executable expression trees */
113
ExprState *lexpr; /* left-hand (outer) input expression */
114
ExprState *rexpr; /* right-hand (inner) input expression */
117
* If we have a current left or right input tuple, the values of the
118
* expressions are loaded into these fields:
120
Datum ldatum; /* current left-hand value */
121
Datum rdatum; /* current right-hand value */
122
bool lisnull; /* and their isnull flags */
126
* The comparison strategy in use, and the lookup info to let us call the
127
* btree comparison support function.
129
bool reverse; /* if true, negate the cmpfn's output */
130
bool nulls_first; /* if true, nulls sort low */
132
} MergeJoinClauseData;
135
#define MarkInnerTuple(innerTupleSlot, mergestate) \
136
ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
142
* This deconstructs the list of mergejoinable expressions, which is given
143
* to us by the planner in the form of a list of "leftexpr = rightexpr"
144
* expression trees in the order matching the sort columns of the inputs.
145
* We build an array of MergeJoinClause structs containing the information
146
* we will need at runtime. Each struct essentially tells us how to compare
147
* the two expressions from the original clause.
149
* In addition to the expressions themselves, the planner passes the btree
150
* opfamily OID, btree strategy number (BTLessStrategyNumber or
151
* BTGreaterStrategyNumber), and nulls-first flag that identify the intended
152
* sort ordering for each merge key. The mergejoinable operator is an
153
* equality operator in this opfamily, and the two inputs are guaranteed to be
154
* ordered in either increasing or decreasing (respectively) order according
155
* to this opfamily, with nulls at the indicated end of the range. This
156
* allows us to obtain the needed comparison function from the opfamily.
158
static MergeJoinClause
159
MJExamineQuals(List *mergeclauses,
161
int *mergestrategies,
162
bool *mergenullsfirst,
165
MergeJoinClause clauses;
166
int nClauses = list_length(mergeclauses);
170
clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
173
foreach(cl, mergeclauses)
175
OpExpr *qual = (OpExpr *) lfirst(cl);
176
MergeJoinClause clause = &clauses[iClause];
177
Oid opfamily = mergefamilies[iClause];
178
StrategyNumber opstrategy = mergestrategies[iClause];
179
bool nulls_first = mergenullsfirst[iClause];
183
RegProcedure cmpproc;
186
if (!IsA(qual, OpExpr))
187
elog(ERROR, "mergejoin clause is not an OpExpr");
190
* Prepare the input expressions for execution.
192
clause->lexpr = ExecInitExpr((Expr *) linitial(qual->args), parent);
193
clause->rexpr = ExecInitExpr((Expr *) lsecond(qual->args), parent);
195
/* Extract the operator's declared left/right datatypes */
196
get_op_opfamily_properties(qual->opno, opfamily,
200
if (op_strategy != BTEqualStrategyNumber) /* should not happen */
201
elog(ERROR, "cannot merge using non-equality operator %u",
204
/* And get the matching support procedure (comparison function) */
205
cmpproc = get_opfamily_proc(opfamily,
209
if (!RegProcedureIsValid(cmpproc)) /* should not happen */
210
elog(ERROR, "missing support function %d(%u,%u) in opfamily %u",
211
BTORDER_PROC, op_lefttype, op_righttype, opfamily);
213
/* Check permission to call cmp function */
214
aclresult = pg_proc_aclcheck(cmpproc, GetUserId(), ACL_EXECUTE);
215
if (aclresult != ACLCHECK_OK)
216
aclcheck_error(aclresult, ACL_KIND_PROC,
217
get_func_name(cmpproc));
219
/* Set up the fmgr lookup information */
220
fmgr_info(cmpproc, &(clause->cmpfinfo));
222
/* Fill the additional comparison-strategy flags */
223
if (opstrategy == BTLessStrategyNumber)
224
clause->reverse = false;
225
else if (opstrategy == BTGreaterStrategyNumber)
226
clause->reverse = true;
227
else /* planner screwed up */
228
elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
230
clause->nulls_first = nulls_first;
241
* Compute the values of the mergejoined expressions for the current
242
* outer tuple. We also detect whether it's impossible for the current
243
* outer tuple to match anything --- this is true if it yields a NULL
244
* input, since we assume mergejoin operators are strict.
246
* We evaluate the values in OuterEContext, which can be reset each
247
* time we move to a new tuple.
250
MJEvalOuterValues(MergeJoinState *mergestate)
252
ExprContext *econtext = mergestate->mj_OuterEContext;
253
bool canmatch = true;
255
MemoryContext oldContext;
257
ResetExprContext(econtext);
259
oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
261
econtext->ecxt_outertuple = mergestate->mj_OuterTupleSlot;
263
for (i = 0; i < mergestate->mj_NumClauses; i++)
265
MergeJoinClause clause = &mergestate->mj_Clauses[i];
267
clause->ldatum = ExecEvalExpr(clause->lexpr, econtext,
268
&clause->lisnull, NULL);
273
MemoryContextSwitchTo(oldContext);
281
* Same as above, but for the inner tuple. Here, we have to be prepared
282
* to load data from either the true current inner, or the marked inner,
283
* so caller must tell us which slot to load from.
286
MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
288
ExprContext *econtext = mergestate->mj_InnerEContext;
289
bool canmatch = true;
291
MemoryContext oldContext;
293
ResetExprContext(econtext);
295
oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
297
econtext->ecxt_innertuple = innerslot;
299
for (i = 0; i < mergestate->mj_NumClauses; i++)
301
MergeJoinClause clause = &mergestate->mj_Clauses[i];
303
clause->rdatum = ExecEvalExpr(clause->rexpr, econtext,
304
&clause->risnull, NULL);
309
MemoryContextSwitchTo(oldContext);
317
* Compare the mergejoinable values of the current two input tuples
318
* and return 0 if they are equal (ie, the mergejoin equalities all
319
* succeed), +1 if outer > inner, -1 if outer < inner.
321
* MJEvalOuterValues and MJEvalInnerValues must already have been called
322
* for the current outer and inner tuples, respectively.
325
MJCompare(MergeJoinState *mergestate)
328
bool nulleqnull = false;
329
ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
331
MemoryContext oldContext;
332
FunctionCallInfoData fcinfo;
335
* Call the comparison functions in short-lived context, in case they leak
338
ResetExprContext(econtext);
340
oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
342
for (i = 0; i < mergestate->mj_NumClauses; i++)
344
MergeJoinClause clause = &mergestate->mj_Clauses[i];
348
* Deal with null inputs.
354
nulleqnull = true; /* NULL "=" NULL */
357
if (clause->nulls_first)
358
result = -1; /* NULL "<" NOT_NULL */
360
result = 1; /* NULL ">" NOT_NULL */
365
if (clause->nulls_first)
366
result = 1; /* NOT_NULL ">" NULL */
368
result = -1; /* NOT_NULL "<" NULL */
373
* OK to call the comparison function.
375
InitFunctionCallInfoData(fcinfo, &(clause->cmpfinfo), 2,
377
fcinfo.arg[0] = clause->ldatum;
378
fcinfo.arg[1] = clause->rdatum;
379
fcinfo.argnull[0] = false;
380
fcinfo.argnull[1] = false;
381
fresult = FunctionCallInvoke(&fcinfo);
384
nulleqnull = true; /* treat like NULL = NULL */
387
result = DatumGetInt32(fresult);
397
* If we had any null comparison results or NULL-vs-NULL inputs, we do not
398
* want to report that the tuples are equal. Instead, if result is still
399
* 0, change it to +1. This will result in advancing the inner side of
402
if (nulleqnull && result == 0)
405
MemoryContextSwitchTo(oldContext);
412
* Generate a fake join tuple with nulls for the inner tuple,
413
* and return it if it passes the non-join quals.
415
static TupleTableSlot *
416
MJFillOuter(MergeJoinState *node)
418
ExprContext *econtext = node->js.ps.ps_ExprContext;
419
List *otherqual = node->js.ps.qual;
421
ResetExprContext(econtext);
423
econtext->ecxt_outertuple = node->mj_OuterTupleSlot;
424
econtext->ecxt_innertuple = node->mj_NullInnerTupleSlot;
426
if (ExecQual(otherqual, econtext, false))
429
* qualification succeeded. now form the desired projection tuple and
430
* return the slot containing it.
432
TupleTableSlot *result;
435
MJ_printf("ExecMergeJoin: returning outer fill tuple\n");
437
result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
439
if (isDone != ExprEndResult)
441
node->js.ps.ps_TupFromTlist =
442
(isDone == ExprMultipleResult);
451
* Generate a fake join tuple with nulls for the outer tuple,
452
* and return it if it passes the non-join quals.
454
static TupleTableSlot *
455
MJFillInner(MergeJoinState *node)
457
ExprContext *econtext = node->js.ps.ps_ExprContext;
458
List *otherqual = node->js.ps.qual;
460
ResetExprContext(econtext);
462
econtext->ecxt_outertuple = node->mj_NullOuterTupleSlot;
463
econtext->ecxt_innertuple = node->mj_InnerTupleSlot;
465
if (ExecQual(otherqual, econtext, false))
468
* qualification succeeded. now form the desired projection tuple and
469
* return the slot containing it.
471
TupleTableSlot *result;
474
MJ_printf("ExecMergeJoin: returning inner fill tuple\n");
476
result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
478
if (isDone != ExprEndResult)
480
node->js.ps.ps_TupFromTlist =
481
(isDone == ExprMultipleResult);
490
/* ----------------------------------------------------------------
493
* This function is called through the MJ_dump() macro
494
* when EXEC_MERGEJOINDEBUG is defined
495
* ----------------------------------------------------------------
497
#ifdef EXEC_MERGEJOINDEBUG
500
ExecMergeTupleDumpOuter(MergeJoinState *mergestate)
502
TupleTableSlot *outerSlot = mergestate->mj_OuterTupleSlot;
504
printf("==== outer tuple ====\n");
505
if (TupIsNull(outerSlot))
508
MJ_debugtup(outerSlot);
512
ExecMergeTupleDumpInner(MergeJoinState *mergestate)
514
TupleTableSlot *innerSlot = mergestate->mj_InnerTupleSlot;
516
printf("==== inner tuple ====\n");
517
if (TupIsNull(innerSlot))
520
MJ_debugtup(innerSlot);
524
ExecMergeTupleDumpMarked(MergeJoinState *mergestate)
526
TupleTableSlot *markedSlot = mergestate->mj_MarkedTupleSlot;
528
printf("==== marked tuple ====\n");
529
if (TupIsNull(markedSlot))
532
MJ_debugtup(markedSlot);
536
ExecMergeTupleDump(MergeJoinState *mergestate)
538
printf("******** ExecMergeTupleDump ********\n");
540
ExecMergeTupleDumpOuter(mergestate);
541
ExecMergeTupleDumpInner(mergestate);
542
ExecMergeTupleDumpMarked(mergestate);
544
printf("******** \n");
548
/* ----------------------------------------------------------------
550
* ----------------------------------------------------------------
553
ExecMergeJoin(MergeJoinState *node)
560
PlanState *innerPlan;
561
TupleTableSlot *innerTupleSlot;
562
PlanState *outerPlan;
563
TupleTableSlot *outerTupleSlot;
564
ExprContext *econtext;
569
* get information from node
571
estate = node->js.ps.state;
572
innerPlan = innerPlanState(node);
573
outerPlan = outerPlanState(node);
574
econtext = node->js.ps.ps_ExprContext;
575
joinqual = node->js.joinqual;
576
otherqual = node->js.ps.qual;
577
doFillOuter = node->mj_FillOuter;
578
doFillInner = node->mj_FillInner;
581
* Check to see if we're still projecting out tuples from a previous join
582
* tuple (because there is a function-returning-set in the projection
583
* expressions). If so, try to project another one.
585
if (node->js.ps.ps_TupFromTlist)
587
TupleTableSlot *result;
590
result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
591
if (isDone == ExprMultipleResult)
593
/* Done with that source tuple... */
594
node->js.ps.ps_TupFromTlist = false;
598
* Reset per-tuple memory context to free any expression evaluation
599
* storage allocated in the previous tuple cycle. Note this can't happen
600
* until we're done projecting out tuples from a join tuple.
602
ResetExprContext(econtext);
605
* ok, everything is setup.. let's go to work
612
* get the current state of the join and do things accordingly.
614
switch (node->mj_JoinState)
617
* EXEC_MJ_INITIALIZE_OUTER means that this is the first time
618
* ExecMergeJoin() has been called and so we have to fetch the
619
* first matchable tuple for both outer and inner subplans. We
620
* do the outer side in INITIALIZE_OUTER state, then advance
621
* to INITIALIZE_INNER state for the inner subplan.
623
case EXEC_MJ_INITIALIZE_OUTER:
624
MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_OUTER\n");
626
outerTupleSlot = ExecProcNode(outerPlan);
627
node->mj_OuterTupleSlot = outerTupleSlot;
628
if (TupIsNull(outerTupleSlot))
630
MJ_printf("ExecMergeJoin: nothing in outer subplan\n");
634
* Need to emit right-join tuples for remaining inner
635
* tuples. We set MatchedInner = true to force the
636
* ENDOUTER state to advance inner.
638
node->mj_JoinState = EXEC_MJ_ENDOUTER;
639
node->mj_MatchedInner = true;
642
/* Otherwise we're done. */
646
/* Compute join values and check for unmatchability */
647
if (MJEvalOuterValues(node))
649
/* OK to go get the first inner tuple */
650
node->mj_JoinState = EXEC_MJ_INITIALIZE_INNER;
654
/* Stay in same state to fetch next outer tuple */
658
* Generate a fake join tuple with nulls for the inner
659
* tuple, and return it if it passes the non-join
662
TupleTableSlot *result;
664
result = MJFillOuter(node);
671
case EXEC_MJ_INITIALIZE_INNER:
672
MJ_printf("ExecMergeJoin: EXEC_MJ_INITIALIZE_INNER\n");
674
innerTupleSlot = ExecProcNode(innerPlan);
675
node->mj_InnerTupleSlot = innerTupleSlot;
676
if (TupIsNull(innerTupleSlot))
678
MJ_printf("ExecMergeJoin: nothing in inner subplan\n");
682
* Need to emit left-join tuples for all outer tuples,
683
* including the one we just fetched. We set
684
* MatchedOuter = false to force the ENDINNER state to
685
* emit first tuple before advancing outer.
687
node->mj_JoinState = EXEC_MJ_ENDINNER;
688
node->mj_MatchedOuter = false;
691
/* Otherwise we're done. */
695
/* Compute join values and check for unmatchability */
696
if (MJEvalInnerValues(node, innerTupleSlot))
699
* OK, we have the initial tuples. Begin by skipping
700
* non-matching tuples.
702
node->mj_JoinState = EXEC_MJ_SKIP_TEST;
706
/* Mark before advancing, if wanted */
707
if (node->mj_ExtraMarks)
708
ExecMarkPos(innerPlan);
709
/* Stay in same state to fetch next inner tuple */
713
* Generate a fake join tuple with nulls for the outer
714
* tuple, and return it if it passes the non-join
717
TupleTableSlot *result;
719
result = MJFillInner(node);
727
* EXEC_MJ_JOINTUPLES means we have two tuples which satisfied
728
* the merge clause so we join them and then proceed to get
729
* the next inner tuple (EXEC_MJ_NEXTINNER).
731
case EXEC_MJ_JOINTUPLES:
732
MJ_printf("ExecMergeJoin: EXEC_MJ_JOINTUPLES\n");
735
* Set the next state machine state. The right things will
736
* happen whether we return this join tuple or just fall
737
* through to continue the state machine execution.
739
node->mj_JoinState = EXEC_MJ_NEXTINNER;
742
* Check the extra qual conditions to see if we actually want
743
* to return this join tuple. If not, can proceed with merge.
744
* We must distinguish the additional joinquals (which must
745
* pass to consider the tuples "matched" for outer-join logic)
746
* from the otherquals (which must pass before we actually
749
* We don't bother with a ResetExprContext here, on the
750
* assumption that we just did one while checking the merge
751
* qual. One per tuple should be sufficient. We do have to
752
* set up the econtext links to the tuples for ExecQual to
755
outerTupleSlot = node->mj_OuterTupleSlot;
756
econtext->ecxt_outertuple = outerTupleSlot;
757
innerTupleSlot = node->mj_InnerTupleSlot;
758
econtext->ecxt_innertuple = innerTupleSlot;
760
qualResult = (joinqual == NIL ||
761
ExecQual(joinqual, econtext, false));
762
MJ_DEBUG_QUAL(joinqual, qualResult);
766
node->mj_MatchedOuter = true;
767
node->mj_MatchedInner = true;
769
/* In an antijoin, we never return a matched tuple */
770
if (node->js.jointype == JOIN_ANTI)
772
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
777
* In a semijoin, we'll consider returning the first match,
778
* but after that we're done with this outer tuple.
780
if (node->js.jointype == JOIN_SEMI)
781
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
783
qualResult = (otherqual == NIL ||
784
ExecQual(otherqual, econtext, false));
785
MJ_DEBUG_QUAL(otherqual, qualResult);
790
* qualification succeeded. now form the desired
791
* projection tuple and return the slot containing it.
793
TupleTableSlot *result;
796
MJ_printf("ExecMergeJoin: returning tuple\n");
798
result = ExecProject(node->js.ps.ps_ProjInfo,
801
if (isDone != ExprEndResult)
803
node->js.ps.ps_TupFromTlist =
804
(isDone == ExprMultipleResult);
812
* EXEC_MJ_NEXTINNER means advance the inner scan to the next
813
* tuple. If the tuple is not nil, we then proceed to test it
814
* against the join qualification.
816
* Before advancing, we check to see if we must emit an
817
* outer-join fill tuple for this inner tuple.
819
case EXEC_MJ_NEXTINNER:
820
MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTINNER\n");
822
if (doFillInner && !node->mj_MatchedInner)
825
* Generate a fake join tuple with nulls for the outer
826
* tuple, and return it if it passes the non-join quals.
828
TupleTableSlot *result;
830
node->mj_MatchedInner = true; /* do it only once */
832
result = MJFillInner(node);
838
* now we get the next inner tuple, if any. If there's none,
839
* advance to next outer tuple (which may be able to join to
840
* previously marked tuples).
842
* NB: must NOT do "extraMarks" here, since we may need to
843
* return to previously marked tuples.
845
innerTupleSlot = ExecProcNode(innerPlan);
846
node->mj_InnerTupleSlot = innerTupleSlot;
847
MJ_DEBUG_PROC_NODE(innerTupleSlot);
848
node->mj_MatchedInner = false;
850
if (TupIsNull(innerTupleSlot))
852
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
857
* Load up the new inner tuple's comparison values. If we see
858
* that it contains a NULL and hence can't match any outer
859
* tuple, we can skip the comparison and assume the new tuple
860
* is greater than current outer.
862
if (!MJEvalInnerValues(node, innerTupleSlot))
864
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
869
* Test the new inner tuple to see if it matches outer.
871
* If they do match, then we join them and move on to the next
872
* inner tuple (EXEC_MJ_JOINTUPLES).
874
* If they do not match then advance to next outer tuple.
876
compareResult = MJCompare(node);
877
MJ_DEBUG_COMPARE(compareResult);
879
if (compareResult == 0)
880
node->mj_JoinState = EXEC_MJ_JOINTUPLES;
883
Assert(compareResult < 0);
884
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
888
/*-------------------------------------------
889
* EXEC_MJ_NEXTOUTER means
892
* outer tuple - 5 5 - marked tuple
897
* we know we just bumped into the
898
* first inner tuple > current outer tuple (or possibly
899
* the end of the inner stream)
900
* so get a new outer tuple and then
901
* proceed to test it against the marked tuple
902
* (EXEC_MJ_TESTOUTER)
904
* Before advancing, we check to see if we must emit an
905
* outer-join fill tuple for this outer tuple.
906
*------------------------------------------------
908
case EXEC_MJ_NEXTOUTER:
909
MJ_printf("ExecMergeJoin: EXEC_MJ_NEXTOUTER\n");
911
if (doFillOuter && !node->mj_MatchedOuter)
914
* Generate a fake join tuple with nulls for the inner
915
* tuple, and return it if it passes the non-join quals.
917
TupleTableSlot *result;
919
node->mj_MatchedOuter = true; /* do it only once */
921
result = MJFillOuter(node);
927
* now we get the next outer tuple, if any
929
outerTupleSlot = ExecProcNode(outerPlan);
930
node->mj_OuterTupleSlot = outerTupleSlot;
931
MJ_DEBUG_PROC_NODE(outerTupleSlot);
932
node->mj_MatchedOuter = false;
935
* if the outer tuple is null then we are done with the join,
936
* unless we have inner tuples we need to null-fill.
938
if (TupIsNull(outerTupleSlot))
940
MJ_printf("ExecMergeJoin: end of outer subplan\n");
941
innerTupleSlot = node->mj_InnerTupleSlot;
942
if (doFillInner && !TupIsNull(innerTupleSlot))
945
* Need to emit right-join tuples for remaining inner
948
node->mj_JoinState = EXEC_MJ_ENDOUTER;
951
/* Otherwise we're done. */
955
/* Compute join values and check for unmatchability */
956
if (MJEvalOuterValues(node))
958
/* Go test the new tuple against the marked tuple */
959
node->mj_JoinState = EXEC_MJ_TESTOUTER;
963
/* Can't match, so fetch next outer tuple */
964
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
968
/*--------------------------------------------------------
969
* EXEC_MJ_TESTOUTER If the new outer tuple and the marked
970
* tuple satisfy the merge clause then we know we have
971
* duplicates in the outer scan so we have to restore the
972
* inner scan to the marked tuple and proceed to join the
973
* new outer tuple with the inner tuples.
975
* This is the case when
979
* new outer tuple - 5 5
983
* new outer tuple == marked tuple
985
* If the outer tuple fails the test, then we are done
986
* with the marked tuples, and we have to look for a
987
* match to the current inner tuple. So we will
988
* proceed to skip outer tuples until outer >= inner
989
* (EXEC_MJ_SKIP_TEST).
991
* This is the case when
996
* new outer tuple - 6 8 - inner tuple
999
* new outer tuple > marked tuple
1001
*---------------------------------------------------------
1003
case EXEC_MJ_TESTOUTER:
1004
MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
1007
* Here we must compare the outer tuple with the marked inner
1008
* tuple. (We can ignore the result of MJEvalInnerValues,
1009
* since the marked inner tuple is certainly matchable.)
1011
innerTupleSlot = node->mj_MarkedTupleSlot;
1012
(void) MJEvalInnerValues(node, innerTupleSlot);
1014
compareResult = MJCompare(node);
1015
MJ_DEBUG_COMPARE(compareResult);
1017
if (compareResult == 0)
1020
* the merge clause matched so now we restore the inner
1021
* scan position to the first mark, and go join that tuple
1022
* (and any following ones) to the new outer.
1024
* NOTE: we do not need to worry about the MatchedInner
1025
* state for the rescanned inner tuples. We know all of
1026
* them will match this new outer tuple and therefore
1027
* won't be emitted as fill tuples. This works *only*
1028
* because we require the extra joinquals to be nil when
1029
* doing a right or full join --- otherwise some of the
1030
* rescanned tuples might fail the extra joinquals.
1032
ExecRestrPos(innerPlan);
1035
* ExecRestrPos probably should give us back a new Slot,
1036
* but since it doesn't, use the marked slot. (The
1037
* previously returned mj_InnerTupleSlot cannot be assumed
1038
* to hold the required tuple.)
1040
node->mj_InnerTupleSlot = innerTupleSlot;
1041
/* we need not do MJEvalInnerValues again */
1043
node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1048
* if the new outer tuple didn't match the marked inner
1049
* tuple then we have a case like:
1052
* 4 4 - marked tuple
1057
* which means that all subsequent outer tuples will be
1058
* larger than our marked inner tuples. So we need not
1059
* revisit any of the marked tuples but can proceed to
1060
* look for a match to the current inner. If there's
1061
* no more inners, we are done.
1064
Assert(compareResult > 0);
1065
innerTupleSlot = node->mj_InnerTupleSlot;
1066
if (TupIsNull(innerTupleSlot))
1071
* Need to emit left-join tuples for remaining
1074
node->mj_JoinState = EXEC_MJ_ENDINNER;
1077
/* Otherwise we're done. */
1081
/* reload comparison data for current inner */
1082
if (MJEvalInnerValues(node, innerTupleSlot))
1084
/* proceed to compare it to the current outer */
1085
node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1090
* current inner can't possibly match any outer;
1091
* better to advance the inner scan than the outer.
1093
node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1098
/*----------------------------------------------------------
1099
* EXEC_MJ_SKIP means compare tuples and if they do not
1100
* match, skip whichever is lesser.
1107
* outer tuple - 6 8 - inner tuple
1111
* we have to advance the outer scan
1112
* until we find the outer 8.
1114
* On the other hand:
1119
* outer tuple - 12 8 - inner tuple
1123
* we have to advance the inner scan
1124
* until we find the inner 12.
1125
*----------------------------------------------------------
1127
case EXEC_MJ_SKIP_TEST:
1128
MJ_printf("ExecMergeJoin: EXEC_MJ_SKIP_TEST\n");
1131
* before we advance, make sure the current tuples do not
1132
* satisfy the mergeclauses. If they do, then we update the
1133
* marked tuple position and go join them.
1135
compareResult = MJCompare(node);
1136
MJ_DEBUG_COMPARE(compareResult);
1138
if (compareResult == 0)
1140
ExecMarkPos(innerPlan);
1142
MarkInnerTuple(node->mj_InnerTupleSlot, node);
1144
node->mj_JoinState = EXEC_MJ_JOINTUPLES;
1146
else if (compareResult < 0)
1147
node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
1149
/* compareResult > 0 */
1150
node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1154
* SKIPOUTER_ADVANCE: advance over an outer tuple that is
1155
* known not to join to any inner tuple.
1157
* Before advancing, we check to see if we must emit an
1158
* outer-join fill tuple for this outer tuple.
1160
case EXEC_MJ_SKIPOUTER_ADVANCE:
1161
MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPOUTER_ADVANCE\n");
1163
if (doFillOuter && !node->mj_MatchedOuter)
1166
* Generate a fake join tuple with nulls for the inner
1167
* tuple, and return it if it passes the non-join quals.
1169
TupleTableSlot *result;
1171
node->mj_MatchedOuter = true; /* do it only once */
1173
result = MJFillOuter(node);
1179
* now we get the next outer tuple, if any
1181
outerTupleSlot = ExecProcNode(outerPlan);
1182
node->mj_OuterTupleSlot = outerTupleSlot;
1183
MJ_DEBUG_PROC_NODE(outerTupleSlot);
1184
node->mj_MatchedOuter = false;
1187
* if the outer tuple is null then we are done with the join,
1188
* unless we have inner tuples we need to null-fill.
1190
if (TupIsNull(outerTupleSlot))
1192
MJ_printf("ExecMergeJoin: end of outer subplan\n");
1193
innerTupleSlot = node->mj_InnerTupleSlot;
1194
if (doFillInner && !TupIsNull(innerTupleSlot))
1197
* Need to emit right-join tuples for remaining inner
1200
node->mj_JoinState = EXEC_MJ_ENDOUTER;
1203
/* Otherwise we're done. */
1207
/* Compute join values and check for unmatchability */
1208
if (MJEvalOuterValues(node))
1210
/* Go test the new tuple against the current inner */
1211
node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1215
/* Can't match, so fetch next outer tuple */
1216
node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
1221
* SKIPINNER_ADVANCE: advance over an inner tuple that is
1222
* known not to join to any outer tuple.
1224
* Before advancing, we check to see if we must emit an
1225
* outer-join fill tuple for this inner tuple.
1227
case EXEC_MJ_SKIPINNER_ADVANCE:
1228
MJ_printf("ExecMergeJoin: EXEC_MJ_SKIPINNER_ADVANCE\n");
1230
if (doFillInner && !node->mj_MatchedInner)
1233
* Generate a fake join tuple with nulls for the outer
1234
* tuple, and return it if it passes the non-join quals.
1236
TupleTableSlot *result;
1238
node->mj_MatchedInner = true; /* do it only once */
1240
result = MJFillInner(node);
1245
/* Mark before advancing, if wanted */
1246
if (node->mj_ExtraMarks)
1247
ExecMarkPos(innerPlan);
1250
* now we get the next inner tuple, if any
1252
innerTupleSlot = ExecProcNode(innerPlan);
1253
node->mj_InnerTupleSlot = innerTupleSlot;
1254
MJ_DEBUG_PROC_NODE(innerTupleSlot);
1255
node->mj_MatchedInner = false;
1258
* if the inner tuple is null then we are done with the join,
1259
* unless we have outer tuples we need to null-fill.
1261
if (TupIsNull(innerTupleSlot))
1263
MJ_printf("ExecMergeJoin: end of inner subplan\n");
1264
outerTupleSlot = node->mj_OuterTupleSlot;
1265
if (doFillOuter && !TupIsNull(outerTupleSlot))
1268
* Need to emit left-join tuples for remaining outer
1271
node->mj_JoinState = EXEC_MJ_ENDINNER;
1274
/* Otherwise we're done. */
1278
/* Compute join values and check for unmatchability */
1279
if (MJEvalInnerValues(node, innerTupleSlot))
1281
/* proceed to compare it to the current outer */
1282
node->mj_JoinState = EXEC_MJ_SKIP_TEST;
1287
* current inner can't possibly match any outer; better to
1288
* advance the inner scan than the outer.
1290
node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
1295
* EXEC_MJ_ENDOUTER means we have run out of outer tuples, but
1296
* are doing a right/full join and therefore must null-fill
1297
* any remaing unmatched inner tuples.
1299
case EXEC_MJ_ENDOUTER:
1300
MJ_printf("ExecMergeJoin: EXEC_MJ_ENDOUTER\n");
1302
Assert(doFillInner);
1304
if (!node->mj_MatchedInner)
1307
* Generate a fake join tuple with nulls for the outer
1308
* tuple, and return it if it passes the non-join quals.
1310
TupleTableSlot *result;
1312
node->mj_MatchedInner = true; /* do it only once */
1314
result = MJFillInner(node);
1319
/* Mark before advancing, if wanted */
1320
if (node->mj_ExtraMarks)
1321
ExecMarkPos(innerPlan);
1324
* now we get the next inner tuple, if any
1326
innerTupleSlot = ExecProcNode(innerPlan);
1327
node->mj_InnerTupleSlot = innerTupleSlot;
1328
MJ_DEBUG_PROC_NODE(innerTupleSlot);
1329
node->mj_MatchedInner = false;
1331
if (TupIsNull(innerTupleSlot))
1333
MJ_printf("ExecMergeJoin: end of inner subplan\n");
1337
/* Else remain in ENDOUTER state and process next tuple. */
1341
* EXEC_MJ_ENDINNER means we have run out of inner tuples, but
1342
* are doing a left/full join and therefore must null- fill
1343
* any remaing unmatched outer tuples.
1345
case EXEC_MJ_ENDINNER:
1346
MJ_printf("ExecMergeJoin: EXEC_MJ_ENDINNER\n");
1348
Assert(doFillOuter);
1350
if (!node->mj_MatchedOuter)
1353
* Generate a fake join tuple with nulls for the inner
1354
* tuple, and return it if it passes the non-join quals.
1356
TupleTableSlot *result;
1358
node->mj_MatchedOuter = true; /* do it only once */
1360
result = MJFillOuter(node);
1366
* now we get the next outer tuple, if any
1368
outerTupleSlot = ExecProcNode(outerPlan);
1369
node->mj_OuterTupleSlot = outerTupleSlot;
1370
MJ_DEBUG_PROC_NODE(outerTupleSlot);
1371
node->mj_MatchedOuter = false;
1373
if (TupIsNull(outerTupleSlot))
1375
MJ_printf("ExecMergeJoin: end of outer subplan\n");
1379
/* Else remain in ENDINNER state and process next tuple. */
1383
* broken state value?
1386
elog(ERROR, "unrecognized mergejoin state: %d",
1387
(int) node->mj_JoinState);
1392
/* ----------------------------------------------------------------
1394
* ----------------------------------------------------------------
1397
ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
1399
MergeJoinState *mergestate;
1401
/* check for unsupported flags */
1402
Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
1404
MJ1_printf("ExecInitMergeJoin: %s\n",
1405
"initializing node");
1408
* create state structure
1410
mergestate = makeNode(MergeJoinState);
1411
mergestate->js.ps.plan = (Plan *) node;
1412
mergestate->js.ps.state = estate;
1415
* Miscellaneous initialization
1417
* create expression context for node
1419
ExecAssignExprContext(estate, &mergestate->js.ps);
1422
* we need two additional econtexts in which we can compute the join
1423
* expressions from the left and right input tuples. The node's regular
1424
* econtext won't do because it gets reset too often.
1426
mergestate->mj_OuterEContext = CreateExprContext(estate);
1427
mergestate->mj_InnerEContext = CreateExprContext(estate);
1430
* initialize child expressions
1432
mergestate->js.ps.targetlist = (List *)
1433
ExecInitExpr((Expr *) node->join.plan.targetlist,
1434
(PlanState *) mergestate);
1435
mergestate->js.ps.qual = (List *)
1436
ExecInitExpr((Expr *) node->join.plan.qual,
1437
(PlanState *) mergestate);
1438
mergestate->js.jointype = node->join.jointype;
1439
mergestate->js.joinqual = (List *)
1440
ExecInitExpr((Expr *) node->join.joinqual,
1441
(PlanState *) mergestate);
1442
/* mergeclauses are handled below */
1445
* initialize child nodes
1447
* inner child must support MARK/RESTORE.
1449
outerPlanState(mergestate) = ExecInitNode(outerPlan(node), estate, eflags);
1450
innerPlanState(mergestate) = ExecInitNode(innerPlan(node), estate,
1451
eflags | EXEC_FLAG_MARK);
1454
* For certain types of inner child nodes, it is advantageous to issue
1455
* MARK every time we advance past an inner tuple we will never return to.
1456
* For other types, MARK on a tuple we cannot return to is a waste of
1457
* cycles. Detect which case applies and set mj_ExtraMarks if we want to
1458
* issue "unnecessary" MARK calls.
1460
* Currently, only Material wants the extra MARKs, and it will be helpful
1461
* only if eflags doesn't specify REWIND.
1463
if (IsA(innerPlan(node), Material) &&
1464
(eflags & EXEC_FLAG_REWIND) == 0)
1465
mergestate->mj_ExtraMarks = true;
1467
mergestate->mj_ExtraMarks = false;
1469
#define MERGEJOIN_NSLOTS 4
1472
* tuple table initialization
1474
ExecInitResultTupleSlot(estate, &mergestate->js.ps);
1476
mergestate->mj_MarkedTupleSlot = ExecInitExtraTupleSlot(estate);
1477
ExecSetSlotDescriptor(mergestate->mj_MarkedTupleSlot,
1478
ExecGetResultType(innerPlanState(mergestate)));
1480
switch (node->join.jointype)
1484
mergestate->mj_FillOuter = false;
1485
mergestate->mj_FillInner = false;
1489
mergestate->mj_FillOuter = true;
1490
mergestate->mj_FillInner = false;
1491
mergestate->mj_NullInnerTupleSlot =
1492
ExecInitNullTupleSlot(estate,
1493
ExecGetResultType(innerPlanState(mergestate)));
1496
mergestate->mj_FillOuter = false;
1497
mergestate->mj_FillInner = true;
1498
mergestate->mj_NullOuterTupleSlot =
1499
ExecInitNullTupleSlot(estate,
1500
ExecGetResultType(outerPlanState(mergestate)));
1503
* Can't handle right or full join with non-nil extra joinclauses.
1504
* This should have been caught by planner.
1506
if (node->join.joinqual != NIL)
1508
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1509
errmsg("RIGHT JOIN is only supported with merge-joinable join conditions")));
1512
mergestate->mj_FillOuter = true;
1513
mergestate->mj_FillInner = true;
1514
mergestate->mj_NullOuterTupleSlot =
1515
ExecInitNullTupleSlot(estate,
1516
ExecGetResultType(outerPlanState(mergestate)));
1517
mergestate->mj_NullInnerTupleSlot =
1518
ExecInitNullTupleSlot(estate,
1519
ExecGetResultType(innerPlanState(mergestate)));
1522
* Can't handle right or full join with non-nil extra joinclauses.
1524
if (node->join.joinqual != NIL)
1526
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1527
errmsg("FULL JOIN is only supported with merge-joinable join conditions")));
1530
elog(ERROR, "unrecognized join type: %d",
1531
(int) node->join.jointype);
1535
* initialize tuple type and projection info
1537
ExecAssignResultTypeFromTL(&mergestate->js.ps);
1538
ExecAssignProjectionInfo(&mergestate->js.ps, NULL);
1541
* preprocess the merge clauses
1543
mergestate->mj_NumClauses = list_length(node->mergeclauses);
1544
mergestate->mj_Clauses = MJExamineQuals(node->mergeclauses,
1545
node->mergeFamilies,
1546
node->mergeStrategies,
1547
node->mergeNullsFirst,
1548
(PlanState *) mergestate);
1551
* initialize join state
1553
mergestate->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1554
mergestate->js.ps.ps_TupFromTlist = false;
1555
mergestate->mj_MatchedOuter = false;
1556
mergestate->mj_MatchedInner = false;
1557
mergestate->mj_OuterTupleSlot = NULL;
1558
mergestate->mj_InnerTupleSlot = NULL;
1561
* initialization successful
1563
MJ1_printf("ExecInitMergeJoin: %s\n",
1564
"node initialized");
1570
ExecCountSlotsMergeJoin(MergeJoin *node)
1572
return ExecCountSlotsNode(outerPlan((Plan *) node)) +
1573
ExecCountSlotsNode(innerPlan((Plan *) node)) +
1577
/* ----------------------------------------------------------------
1581
* frees storage allocated through C routines.
1582
* ----------------------------------------------------------------
1585
ExecEndMergeJoin(MergeJoinState *node)
1587
MJ1_printf("ExecEndMergeJoin: %s\n",
1588
"ending node processing");
1591
* Free the exprcontext
1593
ExecFreeExprContext(&node->js.ps);
1596
* clean out the tuple table
1598
ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
1599
ExecClearTuple(node->mj_MarkedTupleSlot);
1602
* shut down the subplans
1604
ExecEndNode(innerPlanState(node));
1605
ExecEndNode(outerPlanState(node));
1607
MJ1_printf("ExecEndMergeJoin: %s\n",
1608
"node processing ended");
1612
ExecReScanMergeJoin(MergeJoinState *node, ExprContext *exprCtxt)
1614
ExecClearTuple(node->mj_MarkedTupleSlot);
1616
node->mj_JoinState = EXEC_MJ_INITIALIZE_OUTER;
1617
node->js.ps.ps_TupFromTlist = false;
1618
node->mj_MatchedOuter = false;
1619
node->mj_MatchedInner = false;
1620
node->mj_OuterTupleSlot = NULL;
1621
node->mj_InnerTupleSlot = NULL;
1624
* if chgParam of subnodes is not null then plans will be re-scanned by
1625
* first ExecProcNode.
1627
if (((PlanState *) node)->lefttree->chgParam == NULL)
1628
ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
1629
if (((PlanState *) node)->righttree->chgParam == NULL)
1630
ExecReScan(((PlanState *) node)->righttree, exprCtxt);
added
removed
src/backend/executor/nodeMergejoin.c
