Hi Ashutosh,
Thanks for the review.
*Jeff*, I'm copying you because this is relevant to our discussion about
what to do with mergeopfamilies when adding new merge join types.
You have renamed RestrictInfo member mergeopfamilies as
equivopfamilies. I don't think that's a good name; it doesn't convey
that these are opfamilies containing merge operators. The changes in
check_mergejoinable() suggest that an operator may act as equality
operator in few operator families and comparison operator in others.
That looks odd. Actually an operator family contains operators other
than equality operators, so you may want to retain this member and add
a new member to specify whether the clause is an equality clause or
not.
For mergeopfamilies, I'm not sure what is the best thing to do. I'll try
to explain my understanding of the situation, please correct me if I'm
wrong.
Before the patch, mergeopfamilies was used for two things: creating
equivalence classes and performing merge joins.
For equivalence classes: we look at the restriction clauses, and if they
have mergeopfamilies set, it means that these clause are based on an
equality operator, and the left and right variables must be equal. To
record this fact, we create an equivalence class. The variables might be
equal for one equality operator and not equal for another, so we record
the particular operator families to which our equality operator belongs.
For merge join: we look at the join clauses, and if they have
mergeopfamilies set, it means that these clauses are based on an
equality operator, and we can try performing this particular join as
merge join. These opfamilies are also used beforehand to create the
equivalence classes for left and right variables. The equivalence
classes are used to match the join clauses to pathkeys describing the
ordering of join inputs.
So, if we want to start doing merge joins for operators other than
equality, we still need to record their opfamilies, but only use them
for the second case and not the first. I chose to put these opfamilies
to different variables, and
name the one used for equivalence classes 'equivopfamilies' and the one
used for merge joins 'mergeopfamilies'. The equality operators are used
for both cases, so we put their opfamilies into both of these variables.
I agree this might look confusing. Indeed, we could keep a single
variable for opfamilies, and add separate flags that show how they can
be used, be that for equivalence classes, merge joins, range joins or
some combination of them. This is similar to what Jeff did in his range
merge join patch [1]. I will think more about this and try to produce an
updated patch.
In mergejoinscansel() you have just removed Assert(op_strategy ==
BTEqualStrategyNumber); Probably this function is written considering
on equality operators. But now that we are using this for all other
operators, we will need more changes to this function. That may be the
reason why INNER join in your earlier example doesn't choose right
costing.
I changed mergejoinscansel() slightly to reflect the fact that the inner
relation is scanned from the beginning if we have an inequality merge
clause.
The comment change in final_cost_mergejoin() needs more work. n1, n2,
n3 are number of rows on inner side with values 1, 2, 3 resp. So n1 +
n2 + n3 + ... = size of inner relation is correct. In that context I
am not able to understand your change
+ * If the merge clauses contain inequality, (n1 + n2 + ...) ~=
+ * (size of inner relation)^2.
I extended the comment in final_cost_mergejoin(). Not sure if that
approximation makes any sense, but this is the best I could think of.
Style problems are fixed.
Attached please find the new version of the patch that addresses all the
review comments except mergeopfamilies.
The current commitfest is ending, but I'd like to continue working on
this patch, so I am moving it to the next one.
[1]
https://www.postgresql.org/message-id/flat/CAMp0ubfwAFFW3O_NgKqpRPmm56M4weTEXjprb2gP_NrDaEC4Eg%40mail.gmail.com#camp0ubfwaffw3o_ngkqprpmm56m4wetexjprb2gp_nrdaec...@mail.gmail.com
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 32dc4e6301..2958a9e53d 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -722,19 +722,19 @@ get_useful_ecs_for_relation(PlannerInfo *root, RelOptInfo *rel)
{
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
- /* Consider only mergejoinable clauses */
- if (restrictinfo->mergeopfamilies == NIL)
+ /* Consider only mergejoinable equality clauses */
+ if (restrictinfo->equivopfamilies == NIL)
continue;
/* Make sure we've got canonical ECs. */
- update_mergeclause_eclasses(root, restrictinfo);
+ update_equivclause_eclasses(root, restrictinfo);
/*
- * restrictinfo->mergeopfamilies != NIL is sufficient to guarantee
+ * restrictinfo->equivopfamilies != NIL is sufficient to guarantee
* that left_ec and right_ec will be initialized, per comments in
* distribute_qual_to_rels.
*
- * We want to identify which side of this merge-joinable clause
+ * We want to identify which side of this merge-joinable equality clause
* contains columns from the relation produced by this RelOptInfo. We
* test for overlap, not containment, because there could be extra
* relations on either side. For example, suppose we've got something
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 925b4cf553..73e6a4ca74 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -172,31 +172,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;
@@ -207,28 +208,55 @@ 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);
+
+ /*
+ * Determine whether we accept lesser and/or equal tuples of the inner
+ * relation.
+ */
+ switch (join_op_strategy)
+ {
+ case BTEqualStrategyNumber:
+ parent->mj_UseEqual[iClause] = true;
+ break;
+
+ case BTLessEqualStrategyNumber:
+ parent->mj_UseEqual[iClause] = true;
+ /* fall through */
+
+ case BTLessStrategyNumber:
+ parent->mj_UseLesser[iClause] = true;
+ break;
+
+ case BTGreaterEqualStrategyNumber:
+ parent->mj_UseEqual[iClause] = true;
+ /* fall through */
+
+ case BTGreaterStrategyNumber:
+ parent->mj_UseLesser[iClause] = true;
+ break;
+
+ default:
+ elog(ERROR, "unsupported join strategy %d", join_op_strategy);
+ }
/*
* sortsupport routine must know if abbreviation optimization is
@@ -265,8 +293,6 @@ MJExamineQuals(List *mergeclauses,
iClause++;
}
-
- return clauses;
}
/*
@@ -378,6 +404,14 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
return result;
}
+/* Tuple comparison result */
+typedef enum
+{
+ MJCR_NextInner = 1,
+ MJCR_NextOuter = -1,
+ MJCR_Join = 0
+} MJCompareResult;
+
/*
* MJCompare
*
@@ -388,10 +422,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;
@@ -408,6 +442,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.
@@ -418,11 +453,28 @@ 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;
}
@@ -435,9 +487,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);
@@ -603,7 +655,7 @@ ExecMergeJoin(PlanState *pstate)
ExprState *joinqual;
ExprState *otherqual;
bool qualResult;
- int compareResult;
+ MJCompareResult compareResult;
PlanState *innerPlan;
TupleTableSlot *innerTupleSlot;
PlanState *outerPlan;
@@ -891,11 +943,11 @@ ExecMergeJoin(PlanState *pstate)
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;
@@ -1048,7 +1100,7 @@ ExecMergeJoin(PlanState *pstate)
compareResult = MJCompare(node);
MJ_DEBUG_COMPARE(compareResult);
- if (compareResult == 0)
+ if (compareResult == MJCR_Join)
{
/*
* the merge clause matched so now we restore the inner
@@ -1106,7 +1158,7 @@ ExecMergeJoin(PlanState *pstate)
* 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 */
@@ -1182,7 +1234,7 @@ ExecMergeJoin(PlanState *pstate)
compareResult = MJCompare(node);
MJ_DEBUG_COMPARE(compareResult);
- if (compareResult == 0)
+ if (compareResult == MJCR_Join)
{
if (!node->mj_SkipMarkRestore)
ExecMarkPos(innerPlan);
@@ -1191,11 +1243,13 @@ ExecMergeJoin(PlanState *pstate)
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;
/*
@@ -1593,12 +1647,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 72041693df..8384eb7d74 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -2173,6 +2173,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 5ce3c7c599..26408de719 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2458,6 +2458,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 051a8544b0..992a6c824a 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2569,6 +2569,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.
*
@@ -2620,6 +2641,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))
@@ -2701,18 +2723,25 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
* when we should not. Can we do better without expensive selectivity
* computations?
*
+ * Also, if merge clauses contain inequality, n_i matches all m_k where i <= k.
+ * From that we derive: rescanned tuples = (m1 - 1) * n1 + (m2 - 1) * (n1 + n2)
+ * + ... = m1 * n1 + m2 * (n1 + n2) + ... - n1 - (n1 + n2) - ...
+ * In the limit case of n_i = 1, n1 + (n1 + n2) + ... = sum(n_i) ^ 2 / 2.
+ * Therefore, rescanned tuples = size of join - (inner_rows) ^ 2 / 2.
+ *
* The whole issue is moot if we are working from a unique-ified outer
* input, or if we know we don't need to mark/restore at all.
*/
- if (IsA(outer_path, UniquePath) ||path->skip_mark_restore)
+ if (have_inequality)
+ rescannedtuples = mergejointuples - inner_path_rows * inner_path_rows / 2.;
+ else if (IsA(outer_path, UniquePath) ||path->skip_mark_restore)
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 7997f50c18..256391effd 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;
@@ -1697,7 +1697,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;
@@ -1815,7 +1815,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;
/*
@@ -2043,7 +2043,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 f35380391a..334ceb45c9 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2979,10 +2979,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 */
/*
@@ -3045,7 +3045,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 43833ea9c9..6453c492e4 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -22,6 +22,7 @@
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.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;
@@ -461,6 +462,93 @@ 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 */
+ Assert(list_length(mergeclauses) == 1);
+ 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().
@@ -496,6 +584,13 @@ 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.
@@ -574,6 +669,14 @@ 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().
*/
@@ -897,7 +1000,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)
{
@@ -1882,7 +1986,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 9d83a5ca62..7060ae2533 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, "missing operator %d(%u,%u) in opfamily %u",
BTEqualStrategyNumber, opcintype, opcintype, 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,15 @@ 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 +1321,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 +1437,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 987c20ac9f..296f794864 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,19 @@ 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 39b52aecc5..97d96d5c84 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 23e5526a8e..9c13dbf368 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2893,7 +2893,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
@@ -3076,18 +3075,39 @@ mergejoinscansel(PlannerInfo *root, Node *clause,
if (selec != DEFAULT_INEQ_SEL)
*rightstart = selec;
- /*
- * Only one of the two "start" fractions can really be more than zero;
- * believe the larger estimate and reset the other one to exactly 0.0. If
- * we get exactly equal estimates (as can easily happen with self-joins),
- * believe neither.
- */
- if (*leftstart < *rightstart)
+ if (op_strategy == BTLessStrategyNumber
+ || op_strategy == BTLessEqualStrategyNumber)
+ {
+ /*
+ * If the left variable must be less than right, its first tuple
+ * will already produce the first join pair.
+ */
*leftstart = 0.0;
- else if (*leftstart > *rightstart)
+ }
+ else if (op_strategy == BTGreaterStrategyNumber
+ || op_strategy == BTGreaterEqualStrategyNumber)
+ {
+ /*
+ * Similarly for the right variable and greater operator.
+ */
*rightstart = 0.0;
+ }
else
- *leftstart = *rightstart = 0.0;
+ {
+ Assert(op_strategy == BTEqualStrategyNumber);
+ /*
+ * Only one of the two "start" fractions can really be more than zero;
+ * believe the larger estimate and reset the other one to exactly 0.0. If
+ * we get exactly equal estimates (as can easily happen with self-joins),
+ * believe neither.
+ */
+ if (*leftstart < *rightstart)
+ *leftstart = 0.0;
+ else if (*leftstart > *rightstart)
+ *rightstart = 0.0;
+ else
+ *leftstart = *rightstart = 0.0;
+ }
/*
* If the sort order is nulls-first, we're going to have to skip over any
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 82763f8013..39eca875c9 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
@@ -1179,11 +1218,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
@@ -1192,7 +1231,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;
@@ -1249,7 +1288,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 3272c4b315..77c4a29cbf 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1627,6 +1627,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: */
@@ -1637,6 +1639,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_SkipMarkRestore;
bool mj_ExtraMarks;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 3ccc9d1b03..42f885cf53 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1789,7 +1789,9 @@ 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 4e06b2e299..e202782640 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -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 07208b56ce..b40daae39f 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -74,6 +74,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);
@@ -100,7 +101,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 9f4c88dab4..452023e538 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)
@@ -5365,6 +5494,7 @@ rollback;
--
-- test planner's ability to mark joins as unique
--
+set enable_mergejoin to 0;
create table j1 (id int primary key);
create table j2 (id int primary key);
create table j3 (id int);
@@ -5634,6 +5764,7 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
set enable_nestloop to 0;
set enable_hashjoin to 0;
set enable_sort to 0;
+set enable_mergejoin to 1;
-- create an index that will be preferred over the PK to perform the join
create index j1_id1_idx on j1 (id1) where id1 % 1000 = 1;
explain (costs off) select * from j1 j1
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 835d67551c..2f0eec296e 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
@@ -1765,6 +1776,8 @@ rollback;
-- test planner's ability to mark joins as unique
--
+set enable_mergejoin to 0;
+
create table j1 (id int primary key);
create table j2 (id int primary key);
create table j3 (id int);
@@ -1865,6 +1878,7 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
set enable_nestloop to 0;
set enable_hashjoin to 0;
set enable_sort to 0;
+set enable_mergejoin to 1;
-- create an index that will be preferred over the PK to perform the join
create index j1_id1_idx on j1 (id1) where id1 % 1000 = 1;
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
