Hi hackers,
As you know, at this time Postgres cannot perform a full join on a
comparison clause. For example, if we have two tables with numeric
columns and run a query like 'select * from t1 full join t2 on t1.a >
t2.a', we get an error: "FULL JOIN is only supported with merge-joinable
or hash-joinable join conditions". Such queries are legitimate SQL and
sometimes arise when porting applications from different DBMS, so it
would be good to support them in Postgres. They can be rewritten as
union of right and left joins, but it requires manual work and runs
somewhat slower (see the benchmark at the end of the letter). This
proof-of-concept patch explores the possibility of performing such
queries as merge joins.
Consider the following example where outer and inner relations are in
ascending order, and we are asked to return outer tuples that are
greater than inner.
outer > inner
outer tuple - 6 4 - marked tuple
7 5
8 6 - inner tuple
8 7
The main difference from normal merge join is that we do not need to
advance the marked tuple. This behavior can be implemented with some
simple changes to the function that compares inner and outer tuples.
However, for the join clause 'outer < inner' we would have to advance
the marked tuple, which would require adding a new state to the merge
join executor node. We do not do this. Instead, at the path creation
stage, we make sure that the particular combination of sorting order and
join clause allows us to perform merge join the simple way.
The optimizer requires some other changes to support these joins.
Currently, it uses the same clauses to generate equivalence classes and
to perform merge joins. This patch has to separate these two uses.
Clauses that correspond to a btree equality operator are used to
construct equivalence classes; the operator families for these clauses
are recorded in the 'equivopfamilies' field of RestrictInfo struct.
Clauses that correspond to btree equality or comparison are used to
perform merge joins, and have their operator families recorded in the
'mergeopfamilies'.
The optimizer also has to check whether the particular join clause list
can be used for merge join, and ensure that it is compatible with
inner/outer path ordering. These checks are performed by
'can_sort_for_mergejoin()' and 'outer_sort_suitable_for_mergejoin()'.
There is an important unsolved problem in this patch. When generating
index paths for base relations, the optimizer tries to use only one scan
direction to limit the number of paths. This direction might not be
suitable for a given join clause, and the input path will have to be
sorted. We could generate paths for both directions, but this was
specifically removed for optimization (SHA 834ddc62 by Tom Lane,
10/27/2007 09:45 AM).
For inner joins one would expect the merge join to be slower than the
nested loop, because it has more complex code paths, and indeed this can
be seen on simple benchmarks (see the end of the letter). Costs should
be revised further to reflect this difference.
I would be glad to hear your opinion on this approach.
Some benchmarks:
===== Full join vs union of left and right joins
========================================
test1=# explain analyze select * from t4 right join t1 on t4.a < t1.a
union all select * from t4 left join t1 on t4.a < t1.a where t1.a is null;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
Append (cost=809.69..70703.19 rows=3340000 width=8) (actual
time=8.336..1195.534 rows=5007546 loops=1)
-> Merge Left Join (cost=809.69..34230.49 rows=3333333 width=8)
(actual time=8.335..920.442 rows=5007537 loops=1)
Merge Cond: (t1.a > t4.a)
-> Index Only Scan using idx_t1_a on t1 (cost=0.28..35.27
rows=1000 width=4) (actual time=0.027..0.395 rows=1001 loops=1)
Heap Fetches: 97
-> Sort (cost=809.39..834.39 rows=10000 width=4) (actual
time=8.300..356.821 rows=5007538 loops=1)
Sort Key: t4.a
Sort Method: quicksort Memory: 931kB
-> Seq Scan on t4 (cost=0.00..145.00 rows=10000
width=4) (actual time=0.019..2.533 rows=10000 loops=1)
-> Nested Loop Anti Join (cost=0.28..3072.71 rows=6667 width=8)
(actual time=4.685..35.421 rows=9 loops=1)
-> Seq Scan on t4 t4_1 (cost=0.00..145.00 rows=10000
width=4) (actual time=0.010..0.656 rows=10000 loops=1)
-> Index Only Scan using idx_t1_a on t1 t1_1 (cost=0.28..6.10
rows=333 width=4) (actual time=0.003..0.003 rows=1 loops=10000)
Index Cond: (a > t4_1.a)
Heap Fetches: 971
Planning time: 1.414 ms
Execution time: 1324.985 ms
(16 rows)
test1=# explain analyze select * from t4 full join t1 on t4.a < t1.a;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Merge Full Join (cost=809.66..34230.49 rows=3333333 width=8) (actual
time=8.351..914.590 rows=5007546 loops=1)
Merge Cond: (t1.a > t4.a)
-> Index Only Scan using idx_t1_a on t1 (cost=0.28..35.27
rows=1000 width=4) (actual time=0.035..0.368 rows=1001 loops=1)
Heap Fetches: 97
-> Sort (cost=809.39..834.39 rows=10000 width=4) (actual
time=8.309..347.851 rows=5007546 loops=1)
Sort Key: t4.a
Sort Method: quicksort Memory: 931kB
-> Seq Scan on t4 (cost=0.00..145.00 rows=10000 width=4)
(actual time=0.020..2.563 rows=10000 loops=1)
Planning time: 1.083 ms
Execution time: 1044.869 ms
(10 rows)
=== Merge vs nested loop ===========================================
test1=# explain analyze select * from t5 join t1 on t5.a <= t1.a;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.28..944713.00 rows=33333333 width=8) (actual
time=0.055..8718.840 rows=50014145 loops=1)
-> Seq Scan on t5 (cost=0.00..1443.00 rows=100000 width=4) (actual
time=0.019..6.428 rows=100000 loops=1)
-> Index Only Scan using idx_t1_a on t1 (cost=0.28..6.10 rows=333
width=4) (actual time=0.003..0.050 rows=500 loops=100000)
Index Cond: (a >= t5.a)
Heap Fetches: 9147995
Planning time: 2.209 ms
Execution time: 9942.176 ms
(7 rows)
test1=# set enable_mergejoin TO on;
SET
test1=# explain analyze select * from t5 join t1 on t5.a <= t1.a;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Merge Join (cost=9748.54..343618.88 rows=33333333 width=8) (actual
time=35.491..9281.482 rows=50014145 loops=1)
Merge Cond: (t1.a >= t5.a)
-> Index Only Scan using idx_t1_a on t1 (cost=0.28..35.27
rows=1000 width=4) (actual time=0.027..0.769 rows=1001 loops=1)
Heap Fetches: 97
-> Sort (cost=9747.82..9997.82 rows=100000 width=4) (actual
time=35.458..3906.652 rows=50014145 loops=1)
Sort Key: t5.a
Sort Method: quicksort Memory: 8541kB
-> Seq Scan on t5 (cost=0.00..1443.00 rows=100000 width=4)
(actual time=0.013..8.570 rows=100000 loops=1)
Planning time: 2.368 ms
Execution time: 10530.356 ms
(10 rows)
--
Alexander Kuzmenkov
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 62784af..db9de5b 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -171,31 +171,32 @@ typedef enum
* to the opfamily and collation, with nulls at the indicated end of the range.
* This allows us to obtain the needed comparison function from the opfamily.
*/
-static MergeJoinClause
+static void
MJExamineQuals(List *mergeclauses,
Oid *mergefamilies,
Oid *mergecollations,
int *mergestrategies,
bool *mergenullsfirst,
- PlanState *parent)
+ MergeJoinState *parent)
{
- MergeJoinClause clauses;
int nClauses = list_length(mergeclauses);
int iClause;
ListCell *cl;
- clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
+ parent->mj_Clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
+ parent->mj_UseEqual = (bool *) palloc0(nClauses * sizeof(bool));
+ parent->mj_UseLesser = (bool *) palloc0(nClauses * sizeof(bool));
iClause = 0;
foreach(cl, mergeclauses)
{
OpExpr *qual = (OpExpr *) lfirst(cl);
- MergeJoinClause clause = &clauses[iClause];
+ MergeJoinClause clause = &parent->mj_Clauses[iClause];
Oid opfamily = mergefamilies[iClause];
Oid collation = mergecollations[iClause];
- StrategyNumber opstrategy = mergestrategies[iClause];
+ StrategyNumber sort_op_strategy = mergestrategies[iClause];
bool nulls_first = mergenullsfirst[iClause];
- int op_strategy;
+ int join_op_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid sortfunc;
@@ -206,28 +207,46 @@ MJExamineQuals(List *mergeclauses,
/*
* Prepare the input expressions for execution.
*/
- clause->lexpr = ExecInitExpr((Expr *) linitial(qual->args), parent);
- clause->rexpr = ExecInitExpr((Expr *) lsecond(qual->args), parent);
+ clause->lexpr = ExecInitExpr((Expr *) linitial(qual->args), (PlanState *) parent);
+ clause->rexpr = ExecInitExpr((Expr *) lsecond(qual->args), (PlanState *) parent);
/* Set up sort support data */
clause->ssup.ssup_cxt = CurrentMemoryContext;
clause->ssup.ssup_collation = collation;
- if (opstrategy == BTLessStrategyNumber)
+ if (sort_op_strategy == BTLessStrategyNumber)
clause->ssup.ssup_reverse = false;
- else if (opstrategy == BTGreaterStrategyNumber)
+ else if (sort_op_strategy == BTGreaterStrategyNumber)
clause->ssup.ssup_reverse = true;
else /* planner screwed up */
- elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
+ elog(ERROR, "unsupported mergejoin strategy %d", sort_op_strategy);
clause->ssup.ssup_nulls_first = nulls_first;
/* Extract the operator's declared left/right datatypes */
get_op_opfamily_properties(qual->opno, opfamily, false,
- &op_strategy,
+ &join_op_strategy,
&op_lefttype,
&op_righttype);
- if (op_strategy != BTEqualStrategyNumber) /* should not happen */
- elog(ERROR, "cannot merge using non-equality operator %u",
- qual->opno);
+
+ switch (join_op_strategy)
+ {
+ case BTEqualStrategyNumber:
+ parent->mj_UseEqual[iClause] = true;
+ break;
+ case BTLessEqualStrategyNumber:
+ parent->mj_UseEqual[iClause] = true;
+ /* fall through to 'less' strategy */
+ case BTLessStrategyNumber:
+ parent->mj_UseLesser[iClause] = true;
+ break;
+ case BTGreaterEqualStrategyNumber:
+ parent->mj_UseEqual[iClause] = true;
+ /* fall through to 'greater' strategy */
+ case BTGreaterStrategyNumber:
+ parent->mj_UseLesser[iClause] = true;
+ break;
+ default:
+ Assert(false);
+ }
/*
* sortsupport routine must know if abbreviation optimization is
@@ -264,8 +283,6 @@ MJExamineQuals(List *mergeclauses,
iClause++;
}
-
- return clauses;
}
/*
@@ -377,6 +394,14 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
return result;
}
+/* Tuple comparison result */
+typedef enum
+{
+ MJCR_NextInner = 1,
+ MJCR_NextOuter = -1,
+ MJCR_Join = 0
+} MJCompareResult;
+
/*
* MJCompare
*
@@ -387,10 +412,10 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
* MJEvalOuterValues and MJEvalInnerValues must already have been called
* for the current outer and inner tuples, respectively.
*/
-static int
+static MJCompareResult
MJCompare(MergeJoinState *mergestate)
{
- int result = 0;
+ MJCompareResult result = MJCR_Join;
bool nulleqnull = false;
ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
int i;
@@ -407,6 +432,7 @@ MJCompare(MergeJoinState *mergestate)
for (i = 0; i < mergestate->mj_NumClauses; i++)
{
MergeJoinClause clause = &mergestate->mj_Clauses[i];
+ int sort_result;
/*
* Special case for NULL-vs-NULL, else use standard comparison.
@@ -417,12 +443,41 @@ MJCompare(MergeJoinState *mergestate)
continue;
}
- result = ApplySortComparator(clause->ldatum, clause->lisnull,
- clause->rdatum, clause->risnull,
- &clause->ssup);
+ sort_result = ApplySortComparator(clause->ldatum, clause->lisnull,
+ clause->rdatum, clause->risnull,
+ &clause->ssup);
- if (result != 0)
+ if (sort_result < 0)
+ {
+ result = MJCR_NextOuter;
+ }
+ else if (sort_result == 0)
+ {
+ if (mergestate->mj_UseEqual[i])
+ {
+ result = MJCR_Join;
+ }
+ else
+ {
+ result = MJCR_NextOuter;
+ }
+ }
+ else /*sort_result > 0 */
+ {
+ if (mergestate->mj_UseLesser[i])
+ {
+ result = MJCR_Join;
+ }
+ else
+ {
+ result = MJCR_NextInner;
+ }
+ }
+
+ if (result != MJCR_Join)
+ {
break;
+ }
}
/*
@@ -434,9 +489,9 @@ MJCompare(MergeJoinState *mergestate)
* equality. We have to check this as part of the mergequals, else the
* rescan logic will do the wrong thing.
*/
- if (result == 0 &&
+ if (result == MJCR_Join &&
(nulleqnull || mergestate->mj_ConstFalseJoin))
- result = 1;
+ result = MJCR_NextInner;
MemoryContextSwitchTo(oldContext);
@@ -601,7 +656,7 @@ ExecMergeJoin(MergeJoinState *node)
ExprState *joinqual;
ExprState *otherqual;
bool qualResult;
- int compareResult;
+ MJCompareResult compareResult;
PlanState *innerPlan;
TupleTableSlot *innerTupleSlot;
PlanState *outerPlan;
@@ -886,11 +941,11 @@ ExecMergeJoin(MergeJoinState *node)
compareResult = MJCompare(node);
MJ_DEBUG_COMPARE(compareResult);
- if (compareResult == 0)
+ if (compareResult == MJCR_Join)
node->mj_JoinState = EXEC_MJ_JOINTUPLES;
else
{
- Assert(compareResult < 0);
+ Assert(compareResult == MJCR_NextOuter);
node->mj_JoinState = EXEC_MJ_NEXTOUTER;
}
break;
@@ -1043,7 +1098,7 @@ ExecMergeJoin(MergeJoinState *node)
compareResult = MJCompare(node);
MJ_DEBUG_COMPARE(compareResult);
- if (compareResult == 0)
+ if (compareResult == MJCR_Join)
{
/*
* the merge clause matched so now we restore the inner
@@ -1094,7 +1149,7 @@ ExecMergeJoin(MergeJoinState *node)
* no more inners, no more matches are possible.
* ----------------
*/
- Assert(compareResult > 0);
+ Assert(compareResult == MJCR_NextInner);
innerTupleSlot = node->mj_InnerTupleSlot;
/* reload comparison data for current inner */
@@ -1170,7 +1225,7 @@ ExecMergeJoin(MergeJoinState *node)
compareResult = MJCompare(node);
MJ_DEBUG_COMPARE(compareResult);
- if (compareResult == 0)
+ if (compareResult == MJCR_Join)
{
ExecMarkPos(innerPlan);
@@ -1178,11 +1233,15 @@ ExecMergeJoin(MergeJoinState *node)
node->mj_JoinState = EXEC_MJ_JOINTUPLES;
}
- else if (compareResult < 0)
+ else if (compareResult == MJCR_NextOuter)
+ {
node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
+ }
else
- /* compareResult > 0 */
+ {
+ Assert(compareResult == MJCR_NextInner);
node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE;
+ }
break;
/*
@@ -1564,12 +1623,12 @@ ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
* preprocess the merge clauses
*/
mergestate->mj_NumClauses = list_length(node->mergeclauses);
- mergestate->mj_Clauses = MJExamineQuals(node->mergeclauses,
- node->mergeFamilies,
- node->mergeCollations,
- node->mergeStrategies,
- node->mergeNullsFirst,
- (PlanState *) mergestate);
+ MJExamineQuals(node->mergeclauses,
+ node->mergeFamilies,
+ node->mergeCollations,
+ node->mergeStrategies,
+ node->mergeNullsFirst,
+ mergestate);
/*
* initialize join state
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 1c88d60..a77fc6b 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -2135,6 +2135,7 @@ _copyRestrictInfo(const RestrictInfo *from)
COPY_SCALAR_FIELD(eval_cost);
COPY_SCALAR_FIELD(norm_selec);
COPY_SCALAR_FIELD(outer_selec);
+ COPY_NODE_FIELD(equivopfamilies);
COPY_NODE_FIELD(mergeopfamilies);
/* EquivalenceClasses are never copied, so shallow-copy the pointers */
COPY_SCALAR_FIELD(left_ec);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bbb63a4..cc42ee6 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2412,6 +2412,7 @@ _outRestrictInfo(StringInfo str, const RestrictInfo *node)
/* don't write parent_ec, leads to infinite recursion in plan tree dump */
WRITE_FLOAT_FIELD(norm_selec, "%.4f");
WRITE_FLOAT_FIELD(outer_selec, "%.4f");
+ WRITE_NODE_FIELD(equivopfamilies);
WRITE_NODE_FIELD(mergeopfamilies);
/* don't write left_ec, leads to infinite recursion in plan tree dump */
/* don't write right_ec, leads to infinite recursion in plan tree dump */
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 92de2b7..26e377e 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2522,6 +2522,27 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
}
/*
+ * Check whether there is an inequality clause in the list
+ */
+static bool
+have_inequality_mergeclause(List *mergeclauses)
+{
+ ListCell *lc;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(lc));
+
+ if (rinfo->equivopfamilies == NIL)
+ {
+ Assert(rinfo->mergeopfamilies != NIL);
+ return true;
+ }
+ }
+ return false;
+}
+
+/*
* final_cost_mergejoin
* Final estimate of the cost and result size of a mergejoin path.
*
@@ -2566,6 +2587,7 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
double mergejointuples,
rescannedtuples;
double rescanratio;
+ bool have_inequality = have_inequality_mergeclause(mergeclauses);
/* Protect some assumptions below that rowcounts aren't zero or NaN */
if (inner_path_rows <= 0 || isnan(inner_path_rows))
@@ -2626,6 +2648,9 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
* n1 + m2 * n2 + ... - (n1 + n2 + ...) = size of join - size of inner
* relation
*
+ * If the merge clauses contain inequality, (n1 + n2 + ...) ~=
+ * (size of inner relation)^2.
+ *
* This equation works correctly for outer tuples having no inner match
* (nk = 0), but not for inner tuples having no outer match (mk = 0); we
* are effectively subtracting those from the number of rescanned tuples,
@@ -2635,15 +2660,19 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
* The whole issue is moot if we are working from a unique-ified outer
* input.
*/
- if (IsA(outer_path, UniquePath))
+ if (have_inequality)
+ {
+ rescannedtuples = mergejointuples - inner_path_rows * inner_path_rows / 2.;
+ }
+ else if (IsA(outer_path, UniquePath))
rescannedtuples = 0;
else
{
rescannedtuples = mergejointuples - inner_path_rows;
- /* Must clamp because of possible underestimate */
- if (rescannedtuples < 0)
- rescannedtuples = 0;
}
+ /* Must clamp because of possible underestimate */
+ if (rescannedtuples < 0)
+ rescannedtuples = 0;
/* We'll inflate various costs this much to account for rescanning */
rescanratio = 1.0 + (rescannedtuples / inner_path_rows);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index a329dd1..4367e1d 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -194,7 +194,7 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
*/
op_input_types(opno, &item1_type, &item2_type);
- opfamilies = restrictinfo->mergeopfamilies;
+ opfamilies = restrictinfo->equivopfamilies;
/*
* Sweep through the existing EquivalenceClasses looking for matches to
@@ -235,7 +235,7 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
/*
* A "match" requires matching sets of btree opfamilies. Use of
* equal() for this test has implications discussed in the comments
- * for get_mergejoin_opfamilies().
+ * for get_equiv_opfamilies().
*/
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
@@ -1695,7 +1695,7 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
/* It has to match the outer-join clause as to semantics, too */
if (collation != cur_ec->ec_collation)
continue;
- if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
+ if (!equal(rinfo->equivopfamilies, cur_ec->ec_opfamilies))
continue;
/* Does it contain a match to outervar? */
match = false;
@@ -1813,7 +1813,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
/* It has to match the outer-join clause as to semantics, too */
if (collation != cur_ec->ec_collation)
continue;
- if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
+ if (!equal(rinfo->equivopfamilies, cur_ec->ec_opfamilies))
continue;
/*
@@ -2041,7 +2041,7 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
* to test for member matches first.
*/
if (opfamilies == NIL) /* compute if we didn't already */
- opfamilies = get_mergejoin_opfamilies(eqop);
+ opfamilies = get_equiv_opfamilies(eqop);
if (equal(opfamilies, ec->ec_opfamilies))
return ec;
/* Otherwise, done with this EC, move on to the next */
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a5d19f9..32535fa 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2975,10 +2975,10 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/*
* Note: can_join won't be set for a restriction clause, but
- * mergeopfamilies will be if it has a mergejoinable operator and
+ * equivopfamilies will be if it has a mergejoinable operator and
* doesn't contain volatile functions.
*/
- if (restrictinfo->mergeopfamilies == NIL)
+ if (restrictinfo->equivopfamilies == NIL)
continue; /* not mergejoinable */
/*
@@ -3041,7 +3041,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
* equality behavior for this index. We check this first
* since it's probably cheaper than match_index_to_operand().
*/
- if (!list_member_oid(rinfo->mergeopfamilies, ind->opfamily[c]))
+ if (!list_member_oid(rinfo->equivopfamilies, ind->opfamily[c]))
continue;
/*
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index de7044d..d2ebcf2 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -21,6 +21,7 @@
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+#include "utils/lsyscache.h"
/* Hook for plugins to get control in add_paths_to_joinrel() */
set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
@@ -420,6 +421,98 @@ try_partial_nestloop_path(PlannerInfo *root,
}
/*
+ * Check that we have at most one non-equality merge join clause.
+ * Otherwise, it may not be possible to create a sort order for
+ * mergejoin that maps all the qualifying tuples to a contiguous interval.
+ * For the list consisting of one non-equality clause and multiple equality clauses
+ * we could first sort by all equalities and then by non-equality,
+ * but we don't do this for now.
+ */
+static bool
+can_sort_for_mergejoin(List *mergeclauses)
+{
+ ListCell *lc;
+ int non_equality_clauses = 0;
+ int all_clauses = 0;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(lc));
+
+ all_clauses++;
+ if (rinfo->equivopfamilies == NIL)
+ {
+ Assert(rinfo->mergeopfamilies != NIL);
+ non_equality_clauses++;
+ }
+ if (all_clauses > 1 && non_equality_clauses > 0)
+ {
+ return false;
+ }
+ }
+ return true;
+}
+
+/*
+ * Check whether the given sort order of the outer path is suitable to perform
+ * a merge join. A merge join executor can only choose inner values that are
+ * "lesser" or "equal" according to the sort order. Assumes that we
+ * have at most one non-equality clause.
+ */
+static bool
+outer_sort_suitable_for_mergejoin(List *mergeclauses, List *outerkeys)
+{
+ if (mergeclauses == NIL)
+ {
+ return true;
+ }
+
+ RestrictInfo *rinfo = castNode(RestrictInfo, linitial(mergeclauses));
+ PathKey *key = castNode(PathKey, linitial(outerkeys));
+ Oid orig_opno;
+ Oid opno;
+ int strategy;
+ Oid lefttype;
+ Oid righttype;
+
+ if (rinfo->equivopfamilies != NIL)
+ {
+ /*
+ * Equality clauses do not care about sort order, and do not coexist
+ * with inequality clauses, so we can accept any order now.
+ */
+ return true;
+ }
+
+ /* We have a single inequality clause */
+ orig_opno = ((OpExpr *) rinfo->clause)->opno;
+ opno = rinfo->outer_is_left ? orig_opno : get_commutator(orig_opno);
+ get_op_opfamily_properties(opno, key->pk_opfamily,
+ false /* ordering op */ , &strategy, &lefttype,
+ &righttype);
+ switch (strategy)
+ {
+ case BTLessEqualStrategyNumber:
+ case BTLessStrategyNumber:
+ if (key->pk_strategy == BTLessStrategyNumber)
+ {
+ return false;
+ }
+ break;
+ case BTGreaterEqualStrategyNumber:
+ case BTGreaterStrategyNumber:
+ if (key->pk_strategy == BTGreaterStrategyNumber)
+ {
+ return false;
+ }
+ break;
+ default:
+ elog(ERROR, "unknown merge join clause strategy %d\n", strategy);
+ }
+ return true;
+}
+
+/*
* try_mergejoin_path
* Consider a merge join path; if it appears useful, push it into
* the joinrel's pathlist via add_path().
@@ -455,6 +548,17 @@ try_mergejoin_path(PlannerInfo *root,
return;
}
+ if (!can_sort_for_mergejoin(mergeclauses))
+ {
+ return;
+ }
+
+ if (!outer_sort_suitable_for_mergejoin(mergeclauses, outersortkeys != NIL
+ ? outersortkeys : outer_path->pathkeys))
+ {
+ return;
+ }
+
/*
* Check to see if proposed path is still parameterized, and reject if the
* parameterization wouldn't be sensible.
@@ -533,6 +637,18 @@ try_partial_mergejoin_path(PlannerInfo *root,
{
JoinCostWorkspace workspace;
+ if (!can_sort_for_mergejoin(mergeclauses))
+ {
+ return;
+ }
+
+ if (!outer_sort_suitable_for_mergejoin(mergeclauses, outersortkeys != NIL
+ ? outersortkeys : outer_path->pathkeys))
+ {
+ return;
+ }
+
+
/*
* See comments in try_partial_hashjoin_path().
*/
@@ -860,7 +976,8 @@ sort_inner_and_outer(PlannerInfo *root,
*/
all_pathkeys = select_outer_pathkeys_for_merge(root,
extra->mergeclause_list,
- joinrel);
+ joinrel,
+ jointype);
foreach(l, all_pathkeys)
{
@@ -1845,7 +1962,7 @@ select_mergejoin_clauses(PlannerInfo *root,
* mergejoin is not really all that big a deal, and so it's not clear
* that improving this is important.
*/
- update_mergeclause_eclasses(root, restrictinfo);
+ update_equivclause_eclasses(root, restrictinfo);
if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 2c26906..0f14bdf 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -199,7 +199,7 @@ make_pathkey_from_sortinfo(PlannerInfo *root,
if (!OidIsValid(equality_op)) /* shouldn't happen */
elog(ERROR, "could not find equality operator for opfamily %u",
opfamily);
- opfamilies = get_mergejoin_opfamilies(equality_op);
+ opfamilies = get_equiv_opfamilies(equality_op);
if (!opfamilies) /* certainly should find some */
elog(ERROR, "could not find opfamilies for equality operator %u",
equality_op);
@@ -897,7 +897,7 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
****************************************************************************/
/*
- * initialize_mergeclause_eclasses
+ * initialize_equivclause_eclasses
* Set the EquivalenceClass links in a mergeclause restrictinfo.
*
* RestrictInfo contains fields in which we may cache pointers to
@@ -912,18 +912,21 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
*
* Note this is called before EC merging is complete, so the links won't
* necessarily point to canonical ECs. Before they are actually used for
- * anything, update_mergeclause_eclasses must be called to ensure that
+ * anything, update_equivclause_eclasses must be called to ensure that
* they've been updated to point to canonical ECs.
*/
void
-initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
+initialize_equivclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
{
Expr *clause = restrictinfo->clause;
Oid lefttype,
righttype;
+ List *opfamilies = restrictinfo->mergeopfamilies
+ ? restrictinfo->mergeopfamilies
+ : restrictinfo->equivopfamilies;
/* Should be a mergeclause ... */
- Assert(restrictinfo->mergeopfamilies != NIL);
+ Assert(opfamilies != NIL);
/* ... with links not yet set */
Assert(restrictinfo->left_ec == NULL);
Assert(restrictinfo->right_ec == NULL);
@@ -936,7 +939,7 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
get_eclass_for_sort_expr(root,
(Expr *) get_leftop(clause),
restrictinfo->nullable_relids,
- restrictinfo->mergeopfamilies,
+ opfamilies,
lefttype,
((OpExpr *) clause)->inputcollid,
0,
@@ -946,7 +949,7 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
get_eclass_for_sort_expr(root,
(Expr *) get_rightop(clause),
restrictinfo->nullable_relids,
- restrictinfo->mergeopfamilies,
+ opfamilies,
righttype,
((OpExpr *) clause)->inputcollid,
0,
@@ -955,17 +958,17 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
}
/*
- * update_mergeclause_eclasses
+ * update_equivclause_eclasses
* Make the cached EquivalenceClass links valid in a mergeclause
* restrictinfo.
*
* These pointers should have been set by process_equivalence or
- * initialize_mergeclause_eclasses, but they might have been set to
+ * initialize_equivclause_eclasses, but they might have been set to
* non-canonical ECs that got merged later. Chase up to the canonical
* merged parent if so.
*/
void
-update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
+update_equivclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
{
/* Should be a merge clause ... */
Assert(restrictinfo->mergeopfamilies != NIL);
@@ -1013,7 +1016,7 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
- update_mergeclause_eclasses(root, rinfo);
+ update_equivclause_eclasses(root, rinfo);
}
foreach(i, pathkeys)
@@ -1119,7 +1122,8 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *
select_outer_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
- RelOptInfo *joinrel)
+ RelOptInfo *joinrel,
+ JoinType jointype)
{
List *pathkeys = NIL;
int nClauses = list_length(mergeclauses);
@@ -1149,7 +1153,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
ListCell *lc2;
/* get the outer eclass */
- update_mergeclause_eclasses(root, rinfo);
+ update_equivclause_eclasses(root, rinfo);
if (rinfo->outer_is_left)
oeclass = rinfo->left_ec;
@@ -1186,8 +1190,14 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
* Find out if we have all the ECs mentioned in query_pathkeys; if so we
* can generate a sort order that's also useful for final output. There is
* no percentage in a partial match, though, so we have to have 'em all.
+ *
+ * Full joins on an inequality clause are performed as merge joins and
+ * require a particular combination of merge clause, sort order, and
+ * which relation is outer and which is inner. populate_joinrel_with_paths()
+ * tries both relations as outer, so we should use the same sort order for them.
*/
- if (root->query_pathkeys)
+
+ if (root->query_pathkeys && jointype != JOIN_FULL)
{
foreach(lc, root->query_pathkeys)
{
@@ -1310,7 +1320,7 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
EquivalenceClass *ieclass;
PathKey *pathkey;
- update_mergeclause_eclasses(root, rinfo);
+ update_equivclause_eclasses(root, rinfo);
if (rinfo->outer_is_left)
{
@@ -1426,7 +1436,7 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
if (restrictinfo->mergeopfamilies == NIL)
continue;
- update_mergeclause_eclasses(root, restrictinfo);
+ update_equivclause_eclasses(root, restrictinfo);
if (pathkey->pk_eclass == restrictinfo->left_ec ||
pathkey->pk_eclass == restrictinfo->right_ec)
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 53aefbd..86ee22c 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -1531,8 +1531,8 @@ compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause)
if (all_btree)
{
/* oprcanmerge is considered a hint... */
- if (!op_mergejoinable(opno, opinputtype) ||
- get_mergejoin_opfamilies(opno) == NIL)
+ if (!op_mergejoinable_equality(opno, opinputtype) ||
+ get_equiv_opfamilies(opno) == NIL)
all_btree = false;
}
if (all_hash)
@@ -1936,9 +1936,9 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
* fields of a mergejoinable clause, so that all possibly mergejoinable
* expressions have representations in EquivalenceClasses. If
* process_equivalence is successful, it will take care of that;
- * otherwise, we have to call initialize_mergeclause_eclasses to do it.
+ * otherwise, we have to call initialize_equivclause_eclasses to do it.
*/
- if (restrictinfo->mergeopfamilies)
+ if (restrictinfo->equivopfamilies)
{
if (maybe_equivalence)
{
@@ -1946,13 +1946,13 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
process_equivalence(root, restrictinfo, below_outer_join))
return;
/* EC rejected it, so set left_ec/right_ec the hard way ... */
- initialize_mergeclause_eclasses(root, restrictinfo);
+ initialize_equivclause_eclasses(root, restrictinfo);
/* ... and fall through to distribute_restrictinfo_to_rels */
}
else if (maybe_outer_join && restrictinfo->can_join)
{
/* we need to set up left_ec/right_ec the hard way */
- initialize_mergeclause_eclasses(root, restrictinfo);
+ initialize_equivclause_eclasses(root, restrictinfo);
/* now see if it should go to any outer-join lists */
if (bms_is_subset(restrictinfo->left_relids,
outerjoin_nonnullable) &&
@@ -1986,7 +1986,21 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
else
{
/* we still need to set up left_ec/right_ec */
- initialize_mergeclause_eclasses(root, restrictinfo);
+ initialize_equivclause_eclasses(root, restrictinfo);
+ }
+ }
+ else if (restrictinfo->mergeopfamilies)
+ {
+ /* Not an equivalence clause, but maybe still mergejoinable? */
+ initialize_equivclause_eclasses(root, restrictinfo);
+
+ if (maybe_outer_join
+ && jointype == JOIN_FULL
+ && restrictinfo->can_join)
+ {
+ root->full_join_clauses = lappend(root->full_join_clauses,
+ restrictinfo);
+ return;
}
}
@@ -2347,7 +2361,7 @@ process_implied_equality(PlannerInfo *root,
* responsibility to make sure that the Relids parameters are fresh copies
* not shared with other uses.
*
- * Note: we do not do initialize_mergeclause_eclasses() here. It is
+ * Note: we do not do initialize_equivclause_eclasses() here. It is
* caller's responsibility that left_ec/right_ec be set as necessary.
*/
RestrictInfo *
@@ -2594,14 +2608,21 @@ check_mergejoinable(RestrictInfo *restrictinfo)
opno = ((OpExpr *) clause)->opno;
leftarg = linitial(((OpExpr *) clause)->args);
- if (op_mergejoinable(opno, exprType(leftarg)) &&
- !contain_volatile_functions((Node *) clause))
- restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
+ if (!contain_volatile_functions((Node *) clause))
+ {
+ if (op_mergejoinable_equality(opno, exprType(leftarg)))
+ {
+ restrictinfo->equivopfamilies = get_equiv_opfamilies(opno);
+ }
+ restrictinfo->mergeopfamilies = list_concat(
+ list_copy(restrictinfo->equivopfamilies),
+ get_mergejoin_opfamilies(opno));
+ }
/*
- * Note: op_mergejoinable is just a hint; if we fail to find the operator
- * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
- * is not treated as mergejoinable.
+ * Note: op_mergejoinable_equality is just a hint; if we fail to find the
+ * operator in any btree opfamilies, equivopfamilies remains NIL and so
+ * the clause is not treated as mergejoinable.
*/
}
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index 6f79f96..72d4a12 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -185,6 +185,7 @@ make_restrictinfo_internal(Expr *clause,
restrictinfo->norm_selec = -1;
restrictinfo->outer_selec = -1;
+ restrictinfo->equivopfamilies = NIL;
restrictinfo->mergeopfamilies = NIL;
restrictinfo->left_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 5c382a2..0dad9aa 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2901,7 +2901,6 @@ mergejoinscansel(PlannerInfo *root, Node *clause,
&op_strategy,
&op_lefttype,
&op_righttype);
- Assert(op_strategy == BTEqualStrategyNumber);
/*
* Look up the various operators we need. If we don't find them all, it
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index b891f38..01714ae 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -341,7 +341,7 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type)
}
/*
- * get_mergejoin_opfamilies
+ * get_equiv_opfamilies
* Given a putatively mergejoinable operator, return a list of the OIDs
* of the btree opfamilies in which it represents equality.
*
@@ -360,7 +360,7 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type)
* or cycles here to guarantee the ordering in that case.
*/
List *
-get_mergejoin_opfamilies(Oid opno)
+get_equiv_opfamilies(Oid opno)
{
List *result = NIL;
CatCList *catlist;
@@ -388,6 +388,45 @@ get_mergejoin_opfamilies(Oid opno)
return result;
}
+
+/*
+ * Given an operator, returns a list of operator families in which it represents
+ * btree comparison.
+ * Also see the comment for get_equiv_opfamilies().
+ */
+List *
+get_mergejoin_opfamilies(Oid opno)
+{
+ List *result = NIL;
+ CatCList *catlist;
+ int i;
+
+ /*
+ * Search pg_amop to see if the target operator is registered as the "<"
+ * or ">" operator of any btree opfamily.
+ */
+ catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno));
+
+ for (i = 0; i < catlist->n_members; i++)
+ {
+ HeapTuple tuple = &catlist->members[i]->tuple;
+ Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
+
+ if (aform->amopmethod == BTREE_AM_OID
+ && (aform->amopstrategy == BTLessStrategyNumber
+ || aform->amopstrategy == BTLessEqualStrategyNumber
+ || aform->amopstrategy == BTGreaterStrategyNumber
+ || aform->amopstrategy == BTGreaterEqualStrategyNumber))
+ {
+ result = lappend_oid(result, aform->amopfamily);
+ }
+ }
+
+ ReleaseSysCacheList(catlist);
+
+ return result;
+}
+
/*
* get_compatible_hash_operators
* Get the OID(s) of hash equality operator(s) compatible with the given
@@ -1147,11 +1186,11 @@ op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
}
/*
- * op_mergejoinable
+ * op_mergejoinable_equality
*
- * Returns true if the operator is potentially mergejoinable. (The planner
- * will fail to find any mergejoin plans unless there are suitable btree
- * opfamily entries for this operator and associated sortops. The pg_operator
+ * Returns true if the operator is a potentially mergejoinable equality operator.
+ * (The planner will fail to find any mergejoin plans unless there are suitable
+ * btree opfamily entries for this operator and associated sortops. The pg_operator
* flag is just a hint to tell the planner whether to bother looking.)
*
* In some cases (currently only array_eq and record_eq), mergejoinability
@@ -1160,7 +1199,7 @@ op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
* is needed to check this --- by convention, pass the left input's data type.
*/
bool
-op_mergejoinable(Oid opno, Oid inputtype)
+op_mergejoinable_equality(Oid opno, Oid inputtype)
{
bool result = false;
HeapTuple tp;
@@ -1217,7 +1256,7 @@ op_hashjoinable(Oid opno, Oid inputtype)
HeapTuple tp;
TypeCacheEntry *typentry;
- /* As in op_mergejoinable, let the typcache handle the hard cases */
+ /* As in op_mergejoinable_equality, let the typcache handle the hard cases */
/* Eventually we'll need a similar case for record_eq ... */
if (opno == ARRAY_EQ_OP)
{
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 11a6850..3bf4a35 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1553,6 +1553,8 @@ typedef struct NestLoopState
* NullInnerTupleSlot prepared null tuple for left outer joins
* OuterEContext workspace for computing outer tuple's join values
* InnerEContext workspace for computing inner tuple's join values
+ * UseLesser join lesser values
+ * UseEqual join equal values
* ----------------
*/
/* private in nodeMergejoin.c: */
@@ -1563,6 +1565,8 @@ typedef struct MergeJoinState
JoinState js; /* its first field is NodeTag */
int mj_NumClauses;
MergeJoinClause mj_Clauses; /* array of length mj_NumClauses */
+ bool *mj_UseLesser;
+ bool *mj_UseEqual;
int mj_JoinState;
bool mj_ExtraMarks;
bool mj_ConstFalseJoin;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 8930edf..9c4a424 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1741,7 +1741,8 @@ typedef struct RestrictInfo
* not yet set */
/* valid if clause is mergejoinable, else NIL */
- List *mergeopfamilies; /* opfamilies containing clause operator */
+ List *equivopfamilies; /* opfamilies containing equality operator */
+ List *mergeopfamilies; /* opfamilies containing comparison operator */
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 25fe78c..bd38d3d 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -57,7 +57,7 @@ extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel);
extern int compute_parallel_worker(RelOptInfo *rel, double heap_pages,
double index_pages);
extern void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
- Path *bitmapqual);
+ Path *bitmapqual);
#ifdef OPTIMIZER_DEBUG
extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel);
@@ -206,9 +206,9 @@ extern List *build_join_pathkeys(PlannerInfo *root,
extern List *make_pathkeys_for_sortclauses(PlannerInfo *root,
List *sortclauses,
List *tlist);
-extern void initialize_mergeclause_eclasses(PlannerInfo *root,
+extern void initialize_equivclause_eclasses(PlannerInfo *root,
RestrictInfo *restrictinfo);
-extern void update_mergeclause_eclasses(PlannerInfo *root,
+extern void update_equivclause_eclasses(PlannerInfo *root,
RestrictInfo *restrictinfo);
extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
@@ -216,7 +216,8 @@ extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *restrictinfos);
extern List *select_outer_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
- RelOptInfo *joinrel);
+ RelOptInfo *joinrel,
+ JoinType jointype);
extern List *make_inner_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
List *outer_pathkeys);
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index b6d1fca..8f6a800 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -52,6 +52,7 @@ extern bool get_ordering_op_properties(Oid opno,
Oid *opfamily, Oid *opcintype, int16 *strategy);
extern Oid get_equality_op_for_ordering_op(Oid opno, bool *reverse);
extern Oid get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type);
+extern List *get_equiv_opfamilies(Oid opno);
extern List *get_mergejoin_opfamilies(Oid opno);
extern bool get_compatible_hash_operators(Oid opno,
Oid *lhs_opno, Oid *rhs_opno);
@@ -77,7 +78,7 @@ extern RegProcedure get_opcode(Oid opno);
extern char *get_opname(Oid opno);
extern Oid get_op_rettype(Oid opno);
extern void op_input_types(Oid opno, Oid *lefttype, Oid *righttype);
-extern bool op_mergejoinable(Oid opno, Oid inputtype);
+extern bool op_mergejoinable_equality(Oid opno, Oid inputtype);
extern bool op_hashjoinable(Oid opno, Oid inputtype);
extern bool op_strict(Oid opno);
extern char op_volatile(Oid opno);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 4992048..3d306d8 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -1700,18 +1700,19 @@ SELECT '' AS "xxx", *
-- Non-equi-joins
--
SELECT '' AS "xxx", *
- FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k);
+ FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k)
+ ORDER BY J1_TBL.i;
xxx | i | j | t | i | k
-----+---+---+-------+---+---
- | 1 | 4 | one | 2 | 2
- | 2 | 3 | two | 2 | 2
+ | 0 | | zero | | 0
| 0 | | zero | 2 | 2
+ | 0 | | zero | 2 | 4
| 1 | 4 | one | 2 | 4
+ | 1 | 4 | one | 2 | 2
+ | 2 | 3 | two | 2 | 2
| 2 | 3 | two | 2 | 4
| 3 | 2 | three | 2 | 4
| 4 | 1 | four | 2 | 4
- | 0 | | zero | 2 | 4
- | 0 | | zero | | 0
(9 rows)
--
@@ -1845,6 +1846,126 @@ SELECT '' AS "xxx", *
| 1 | 4 | one | -1
(1 row)
+-- Full merge join
+explain (costs off) select * from J1_TBL full join J2_TBL on J1_TBL.i <= J2_TBL.k order by J1_TBL.i;
+ QUERY PLAN
+--------------------------------------------
+ Sort
+ Sort Key: j1_tbl.i
+ -> Merge Full Join
+ Merge Cond: (j2_tbl.k >= j1_tbl.i)
+ -> Sort
+ Sort Key: j2_tbl.k
+ -> Seq Scan on j2_tbl
+ -> Sort
+ Sort Key: j1_tbl.i
+ -> Seq Scan on j1_tbl
+(10 rows)
+
+explain (costs off) select * from J1_TBL full join J2_TBL on J1_TBL.i <= J2_TBL.k order by J2_TBL.k desc;
+ QUERY PLAN
+--------------------------------------------
+ Sort
+ Sort Key: j2_tbl.k DESC
+ -> Merge Full Join
+ Merge Cond: (j2_tbl.k >= j1_tbl.i)
+ -> Sort
+ Sort Key: j2_tbl.k
+ -> Seq Scan on j2_tbl
+ -> Sort
+ Sort Key: j1_tbl.i
+ -> Seq Scan on j1_tbl
+(10 rows)
+
+select * from J1_TBL full join J2_TBL on J1_TBL.i <= J2_TBL.k order by J1_TBL.i;
+ i | j | t | i | k
+---+---+-------+---+----
+ 0 | | zero | | 0
+ 0 | | zero | 2 | 2
+ 0 | | zero | 2 | 4
+ 1 | 4 | one | 2 | 2
+ 1 | 4 | one | 2 | 4
+ 2 | 3 | two | 2 | 2
+ 2 | 3 | two | 2 | 4
+ 3 | 2 | three | 2 | 4
+ 4 | 1 | four | 2 | 4
+ 5 | 0 | five | |
+ 6 | 6 | six | |
+ 7 | 7 | seven | |
+ 8 | 8 | eight | |
+ | 0 | zero | |
+ | | | 5 | -5
+ | | | 3 | -3
+ | | | 1 | -1
+ | | | 0 |
+ | | | |
+ | | null | |
+ | | | 5 | -5
+(21 rows)
+
+select * from J1_TBL full join J2_TBL on J1_TBL.i > J2_TBL.k order by J1_TBL.i;
+ i | j | t | i | k
+---+---+-------+---+----
+ 0 | | zero | 5 | -5
+ 0 | | zero | 5 | -5
+ 0 | | zero | 3 | -3
+ 0 | | zero | 1 | -1
+ 1 | 4 | one | 5 | -5
+ 1 | 4 | one | 5 | -5
+ 1 | 4 | one | 3 | -3
+ 1 | 4 | one | 1 | -1
+ 1 | 4 | one | | 0
+ 2 | 3 | two | 5 | -5
+ 2 | 3 | two | 5 | -5
+ 2 | 3 | two | 3 | -3
+ 2 | 3 | two | 1 | -1
+ 2 | 3 | two | | 0
+ 3 | 2 | three | 5 | -5
+ 3 | 2 | three | 5 | -5
+ 3 | 2 | three | 3 | -3
+ 3 | 2 | three | 1 | -1
+ 3 | 2 | three | | 0
+ 3 | 2 | three | 2 | 2
+ 4 | 1 | four | 5 | -5
+ 4 | 1 | four | 5 | -5
+ 4 | 1 | four | 3 | -3
+ 4 | 1 | four | 1 | -1
+ 4 | 1 | four | | 0
+ 4 | 1 | four | 2 | 2
+ 5 | 0 | five | 5 | -5
+ 5 | 0 | five | 5 | -5
+ 5 | 0 | five | 3 | -3
+ 5 | 0 | five | 1 | -1
+ 5 | 0 | five | | 0
+ 5 | 0 | five | 2 | 2
+ 5 | 0 | five | 2 | 4
+ 6 | 6 | six | 5 | -5
+ 6 | 6 | six | 5 | -5
+ 6 | 6 | six | 3 | -3
+ 6 | 6 | six | 1 | -1
+ 6 | 6 | six | | 0
+ 6 | 6 | six | 2 | 2
+ 6 | 6 | six | 2 | 4
+ 7 | 7 | seven | 5 | -5
+ 7 | 7 | seven | 5 | -5
+ 7 | 7 | seven | 3 | -3
+ 7 | 7 | seven | 1 | -1
+ 7 | 7 | seven | | 0
+ 7 | 7 | seven | 2 | 2
+ 7 | 7 | seven | 2 | 4
+ 8 | 8 | eight | 5 | -5
+ 8 | 8 | eight | 5 | -5
+ 8 | 8 | eight | 3 | -3
+ 8 | 8 | eight | 1 | -1
+ 8 | 8 | eight | | 0
+ 8 | 8 | eight | 2 | 2
+ 8 | 8 | eight | 2 | 4
+ | | null | |
+ | 0 | zero | |
+ | | | 0 |
+ | | | |
+(58 rows)
+
--
-- More complicated constructs
--
@@ -5094,43 +5215,51 @@ select c.*,a.*,ss1.q1,ss2.q1,ss3.* from
lateral (select q1, coalesce(ss1.x,q2) as y from int8_tbl d) ss2
) on c.q2 = ss2.q1,
lateral (select * from int4_tbl i where ss2.y > f1) ss3;
- QUERY PLAN
----------------------------------------------------------------------------------------------------------
- Nested Loop
+ QUERY PLAN
+---------------------------------------------------------------------------------------------------------------
+ Merge Join
Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, i.f1
- Join Filter: ((COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)) > i.f1)
- -> Hash Right Join
+ Merge Cond: ((COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)) > i.f1)
+ -> Sort
Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
- Hash Cond: (d.q1 = c.q2)
- -> Nested Loop
- Output: a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
- -> Hash Right Join
- Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
- Hash Cond: (b.q1 = a.q2)
- -> Nested Loop
- Output: b.q1, COALESCE(b.q2, (b2.f1)::bigint)
- Join Filter: (b.q1 < b2.f1)
- -> Seq Scan on public.int8_tbl b
- Output: b.q1, b.q2
- -> Materialize
- Output: b2.f1
- -> Seq Scan on public.int4_tbl b2
- Output: b2.f1
- -> Hash
- Output: a.q1, a.q2
+ Sort Key: (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
+ -> Hash Right Join
+ Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
+ Hash Cond: (d.q1 = c.q2)
+ -> Nested Loop
+ Output: a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
+ -> Hash Left Join
+ Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
+ Hash Cond: (a.q2 = b.q1)
-> Seq Scan on public.int8_tbl a
Output: a.q1, a.q2
- -> Seq Scan on public.int8_tbl d
- Output: d.q1, COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)
- -> Hash
- Output: c.q1, c.q2
- -> Seq Scan on public.int8_tbl c
+ -> Hash
+ Output: b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
+ -> Merge Join
+ Output: b.q1, COALESCE(b.q2, (b2.f1)::bigint)
+ Merge Cond: (b2.f1 > b.q1)
+ -> Sort
+ Output: b2.f1
+ Sort Key: b2.f1
+ -> Seq Scan on public.int4_tbl b2
+ Output: b2.f1
+ -> Sort
+ Output: b.q1, b.q2
+ Sort Key: b.q1
+ -> Seq Scan on public.int8_tbl b
+ Output: b.q1, b.q2
+ -> Seq Scan on public.int8_tbl d
+ Output: d.q1, COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)
+ -> Hash
Output: c.q1, c.q2
- -> Materialize
+ -> Seq Scan on public.int8_tbl c
+ Output: c.q1, c.q2
+ -> Sort
Output: i.f1
+ Sort Key: i.f1
-> Seq Scan on public.int4_tbl i
Output: i.f1
-(34 rows)
+(42 rows)
-- check processing of postponed quals (bug #9041)
explain (verbose, costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index cca1a53..9aee651 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -157,7 +157,8 @@ SELECT '' AS "xxx", *
--
SELECT '' AS "xxx", *
- FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k);
+ FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k)
+ ORDER BY J1_TBL.i;
--
@@ -193,6 +194,16 @@ SELECT '' AS "xxx", *
SELECT '' AS "xxx", *
FROM J1_TBL LEFT JOIN J2_TBL USING (i) WHERE (i = 1);
+-- Full merge join
+
+explain (costs off) select * from J1_TBL full join J2_TBL on J1_TBL.i <= J2_TBL.k order by J1_TBL.i;
+
+explain (costs off) select * from J1_TBL full join J2_TBL on J1_TBL.i <= J2_TBL.k order by J2_TBL.k desc;
+
+select * from J1_TBL full join J2_TBL on J1_TBL.i <= J2_TBL.k order by J1_TBL.i;
+
+select * from J1_TBL full join J2_TBL on J1_TBL.i > J2_TBL.k order by J1_TBL.i;
+
--
-- More complicated constructs
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
