Here is a new version of the patch, rebased to 749c7c41 and with some
cosmetic changes.
--
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 d77c2a70e4..19bc90aa32 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..8eb5c8fd1d 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,50 @@ 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:
+ Assert(false);
+ }
/*
* sortsupport routine must know if abbreviation optimization is
@@ -265,8 +288,6 @@ MJExamineQuals(List *mergeclauses,
iClause++;
}
-
- return clauses;
}
/*
@@ -378,6 +399,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 +417,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 +437,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,12 +448,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;
+ }
}
/*
@@ -435,9 +494,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 +662,7 @@ ExecMergeJoin(PlanState *pstate)
ExprState *joinqual;
ExprState *otherqual;
bool qualResult;
- int compareResult;
+ MJCompareResult compareResult;
PlanState *innerPlan;
TupleTableSlot *innerTupleSlot;
PlanState *outerPlan;
@@ -891,11 +950,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 +1107,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 +1165,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 +1241,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 +1250,15 @@ 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 +1656,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 45a04b0b27..8a8cb64702 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 379d92a2b0..9e588f0149 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 b35acb7bdc..be8449a5d6 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))
@@ -2695,6 +2717,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,
@@ -2704,15 +2729,19 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
* 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 9a3f606df0..d39fd3b867 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;
@@ -1696,7 +1696,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;
@@ -1814,7 +1814,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;
/*
@@ -2042,7 +2042,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 511c734980..c11c692da4 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;
@@ -460,6 +461,99 @@ 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().
@@ -495,6 +589,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.
@@ -573,6 +678,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().
*/
@@ -896,7 +1009,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)
{
@@ -1881,7 +1995,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..8123394e49 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,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 987c20ac9f..e476798e00 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 ebae0cd8ce..2a39818cf8 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 e103f5ef16..3bf8c0e6bf 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
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 35c28a6143..ae527152e4 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1624,6 +1624,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: */
@@ -1634,6 +1636,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 9bae3c6ab9..aee1647a97 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1789,7 +1789,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 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
