From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
To: Ashutosh Bapat <ashutosh.bapat@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Jeff Davis <pgsql@j-davis.com>
Subject: Re: PoC: full merge join on comparison clause
Date: Mon, 30 Oct 2017 15:25:50 +0300
Message-ID: <715cb811-4538-9967-a2e3-ca85f2711d80@postgrespro.ru> (raw)
In-Reply-To: <CAFjFpRfP0Q_+j_9oZ5Jsi7SwQyrx+BgVfvE=zUeZHuinPPsVdw@mail.gmail.com>
References: <b31e1a2d-5ed2-cbca-649e-136f1a7c4c31@postgrespro.ru>
<f3369c3d-7313-bf1d-97ac-6c275305599a@postgrespro.ru>
<CAFjFpRc0FGBqnB+DEB-6K08DA4KuEUFK1tKM8MNURf3z0qkf-Q@mail.gmail.com>
<22906fd3-6f56-2473-9897-21a9532e6da3@postgrespro.ru>
<CAFjFpRcDvOjc02S398ZHKnpYoKk38rnWdzTwPKdq0xc8gsHfcg@mail.gmail.com>
<0e0a0cb9-f51e-f8a6-3829-50c3e38e33f9@postgrespro.ru>
<CAFjFpRfP0Q_+j_9oZ5Jsi7SwQyrx+BgVfvE=zUeZHuinPPsVdw@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
Hi,
I am attaching the updated patch, rebased to 820c03.
On 09.10.2017 13:47, Ashutosh Bapat wrote:
> Hi Alexander,
> Commit c7a9fa399 has added another test on mergeopfamilies. I think
> your patch will need to take care of that test.
>
> On Wed, Oct 4, 2017 at 6:38 PM, Alexander Kuzmenkov
> <a.kuzmenkov@postgrespro.ru> wrote:
>> As discussed earlier, I changed the way we work with mergeopfamilies. I use
>> the "is_equality" flag to indicate whether the clause is an equality one,
>> and fill mergeopfamilies for both equality and inequality operators.
>> The updated patch is attached (rebased to 20b6552242).
>>
>>
>> --
>> Alexander Kuzmenkov
>> Postgres Professional: http://www.postgrespro.com
>> The Russian Postgres Company
>>
>
>
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:full-merge-join-v5.patch (text/x-patch, 46.0K) downloaddiff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.cindex 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.cindex c1a83ca909..9ac3e68616 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -2175,6 +2175,7 @@ _copyRestrictInfo(const RestrictInfo *from)
COPY_SCALAR_FIELD(norm_selec);
COPY_SCALAR_FIELD(outer_selec);
COPY_NODE_FIELD(mergeopfamilies);
+ COPY_SCALAR_FIELD(is_equality);
/* EquivalenceClasses are never copied, so shallow-copy the pointers */
COPY_SCALAR_FIELD(left_ec);
COPY_SCALAR_FIELD(right_ec);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.cindex 43d62062bc..e40e31855d 100644--- a/src/backend/nodes/outfuncs.c+++ b/src/backend/nodes/outfuncs.c@@ -2465,6 +2465,7 @@ _outRestrictInfo(StringInfo str, const RestrictInfo *node)
WRITE_FLOAT_FIELD(norm_selec, "%.4f");
WRITE_FLOAT_FIELD(outer_selec, "%.4f");
WRITE_NODE_FIELD(mergeopfamilies);
+ WRITE_BOOL_FIELD(is_equality);
/* 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 */
WRITE_NODE_FIELD(left_em);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex ce32b8a4b9..e1ab33431c 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -2570,6 +2570,24 @@ 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));+ Assert(rinfo->mergeopfamilies != NIL);+ if (!rinfo->is_equality)+ return true;+ }+ return false;+}++/*
* final_cost_mergejoin
* Final estimate of the cost and result size of a mergejoin path.
*
@@ -2621,6 +2639,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))
@@ -2702,18 +2721,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.cindex a225414c97..f6cb80baf9 100644--- a/src/backend/optimizer/path/equivclass.c+++ b/src/backend/optimizer/path/equivclass.c@@ -233,6 +233,7 @@ process_equivalence(PlannerInfo *root,
op_input_types(opno, &item1_type, &item2_type);
opfamilies = restrictinfo->mergeopfamilies;
+ Assert(restrictinfo->is_equality);
/*
* Sweep through the existing EquivalenceClasses looking for matches to
@@ -273,7 +274,7 @@ process_equivalence(PlannerInfo *root,
/*
* 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;
@@ -2081,7 +2082,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.cindex f35380391a..d76749edb1 100644--- a/src/backend/optimizer/path/indxpath.c+++ b/src/backend/optimizer/path/indxpath.c@@ -2982,7 +2982,8 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
* mergeopfamilies will be if it has a mergejoinable operator and
* doesn't contain volatile functions.
*/
- if (restrictinfo->mergeopfamilies == NIL)+ if (restrictinfo->mergeopfamilies == NIL+ || !restrictinfo->is_equality)
continue; /* not mergejoinable */
/*
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.cindex 310262d87c..90cdee236d 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;
@@ -547,6 +548,92 @@ 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));++ Assert(rinfo->mergeopfamilies != NIL);+ all_clauses++;+ if (!rinfo->is_equality)+ 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->is_equality)+ {+ /*+ * Equality clauses do not care about sort order, and do not coexist+ * with inequality clauses, so we can accept any order now.+ */+ Assert(rinfo->mergeopfamilies != NIL);+ 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().
@@ -582,6 +669,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.
@@ -660,6 +754,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().
*/
@@ -983,7 +1085,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)
{
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.cindex 2b868c52de..a01c02d86a 100644--- a/src/backend/optimizer/path/joinrels.c+++ b/src/backend/optimizer/path/joinrels.c@@ -1463,7 +1463,7 @@ have_partkey_equi_join(RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype,
continue;
/* Skip clauses which are not equality conditions. */
- if (!rinfo->mergeopfamilies)+ if (!rinfo->is_equality)
continue;
opexpr = (OpExpr *) rinfo->clause;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.cindex 9d83a5ca62..1920e6b5a0 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);
@@ -1119,7 +1119,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);
@@ -1186,8 +1187,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)
{
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.cindex 511603b581..ee7ce21780 100644--- a/src/backend/optimizer/plan/analyzejoins.c+++ b/src/backend/optimizer/plan/analyzejoins.c@@ -1084,11 +1084,9 @@ is_innerrel_unique_for(PlannerInfo *root,
ListCell *lc;
/*
- * Search for mergejoinable clauses that constrain the inner rel against- * the outer rel. If an operator is mergejoinable then it behaves like- * equality for some btree opclass, so it's what we want. The- * mergejoinability test also eliminates clauses containing volatile- * functions, which we couldn't depend on.+ * Search for mergejoinable equality clauses that constrain the inner+ * rel against the outer rel. The mergejoinability test also eliminates+ * clauses containing volatile functions, which we couldn't depend on.
*/
foreach(lc, restrictlist)
{
@@ -1101,9 +1099,9 @@ is_innerrel_unique_for(PlannerInfo *root,
if (restrictinfo->is_pushed_down && IS_OUTER_JOIN(jointype))
continue;
- /* Ignore if it's not a mergejoinable clause */+ /* Ignore if it's not a mergejoinable equality clause */
if (!restrictinfo->can_join ||
- restrictinfo->mergeopfamilies == NIL)+ !restrictinfo->is_equality)
continue; /* not mergejoinable */
/*
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.cindex 974eb58d83..5b41eddf7a 100644--- a/src/backend/optimizer/plan/initsplan.c+++ b/src/backend/optimizer/plan/initsplan.c@@ -1552,8 +1552,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)
@@ -1959,15 +1959,17 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
* process_equivalence is successful, it will take care of that;
* otherwise, we have to call initialize_mergeclause_eclasses to do it.
*/
- if (restrictinfo->mergeopfamilies)+ if (restrictinfo->is_equality)
{
+ Assert(restrictinfo->mergeopfamilies != NIL);+
if (maybe_equivalence)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, &restrictinfo, below_outer_join))
return;
/* EC rejected it, so set left_ec/right_ec the hard way ... */
- if (restrictinfo->mergeopfamilies) /* EC might have changed this */+ if (restrictinfo->is_equality) /* EC might have changed this */
initialize_mergeclause_eclasses(root, restrictinfo);
/* ... and fall through to distribute_restrictinfo_to_rels */
}
@@ -2011,6 +2013,20 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
initialize_mergeclause_eclasses(root, restrictinfo);
}
}
+ else if (restrictinfo->mergeopfamilies)+ {+ /* Not an equivalence clause, but maybe still mergejoinable? */+ initialize_mergeclause_eclasses(root, restrictinfo);++ if (maybe_outer_join+ && jointype == JOIN_FULL+ && restrictinfo->can_join)+ {+ root->full_join_clauses = lappend(root->full_join_clauses,+ restrictinfo);+ return;+ }+ }
/* No EC special case applies, so push it into the clause lists */
distribute_restrictinfo_to_rels(root, restrictinfo);
@@ -2616,9 +2632,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->mergeopfamilies = get_equiv_opfamilies(opno);+ restrictinfo->is_equality = true;+ }+ else+ {+ restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);+ restrictinfo->is_equality = false;+ }+ }
/*
* Note: op_mergejoinable is just a hint; if we fail to find the operator
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.cindex 39b52aecc5..648d707a5b 100644--- a/src/backend/optimizer/util/restrictinfo.c+++ b/src/backend/optimizer/util/restrictinfo.c@@ -186,6 +186,7 @@ make_restrictinfo_internal(Expr *clause,
restrictinfo->outer_selec = -1;
restrictinfo->mergeopfamilies = NIL;
+ restrictinfo->is_equality = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.cindex 7361e9d43c..bb7ad8475b 100644--- a/src/backend/utils/adt/selfuncs.c+++ b/src/backend/utils/adt/selfuncs.c@@ -2984,7 +2984,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
@@ -3167,18 +3166,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.cindex 48961e31aa..b090f2ddcf 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.hindex 52d3532580..f790b7a272 100644--- a/src/include/nodes/execnodes.h+++ b/src/include/nodes/execnodes.h@@ -1630,6 +1630,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: */
@@ -1640,6 +1642,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.hindex e085cefb7b..f8e95b7193 100644--- a/src/include/nodes/relation.h+++ b/src/include/nodes/relation.h@@ -1877,7 +1877,9 @@ typedef struct RestrictInfo
* not yet set */
/* valid if clause is mergejoinable, else NIL */
- List *mergeopfamilies; /* opfamilies containing clause operator */+ List *mergeopfamilies; /* opfamilies containing mergejoinable+ * operator */ + bool is_equality; /* is this an equality clause? */
/* 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.hindex ea886b6501..90654e4b66 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -222,7 +222,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.hindex 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.outindex f47449b1c4..afa247ed86 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
--
@@ -5106,43 +5227,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)
@@ -5430,6 +5559,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);
@@ -5699,6 +5829,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/expected/partition_join.out b/src/test/regress/expected/partition_join.outindex adf6aedfa6..45a9161d9a 100644--- a/src/test/regress/expected/partition_join.out+++ b/src/test/regress/expected/partition_join.out@@ -4,6 +4,8 @@
--
-- Enable partition-wise join, which by default is disabled.
SET enable_partition_wise_join to true;
+-- Disable merge joins to get predictable plans+SET enable_mergejoin TO off;
--
-- partitioned by a single column
--
@@ -869,6 +871,7 @@ SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (
-- test merge joins
SET enable_hashjoin TO off;
SET enable_nestloop TO off;
+SET enable_mergejoin TO on;
EXPLAIN (COSTS OFF)
SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (SELECT (t1.a + t1.b)/2 FROM prt1_e t1 WHERE t1.c = 0)) AND t1.b = 0 ORDER BY t1.a;
QUERY PLAN
@@ -1052,6 +1055,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
RESET enable_hashjoin;
RESET enable_nestloop;
+SET enable_mergejoin TO off;
--
-- partitioned by multiple columns
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sqlindex d847d53653..897a03d813 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
@@ -1793,6 +1804,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);
@@ -1893,6 +1906,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;
diff --git a/src/test/regress/sql/partition_join.sql b/src/test/regress/sql/partition_join.sqlindex 25abf2dc13..e4a4cdbe41 100644--- a/src/test/regress/sql/partition_join.sql+++ b/src/test/regress/sql/partition_join.sql@@ -6,6 +6,9 @@
-- Enable partition-wise join, which by default is disabled.
SET enable_partition_wise_join to true;
+-- Disable merge joins to get predictable plans+SET enable_mergejoin TO off;+
--
-- partitioned by a single column
--
@@ -146,6 +149,7 @@ SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (
-- test merge joins
SET enable_hashjoin TO off;
SET enable_nestloop TO off;
+SET enable_mergejoin TO on;
EXPLAIN (COSTS OFF)
SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (SELECT (t1.a + t1.b)/2 FROM prt1_e t1 WHERE t1.c = 0)) AND t1.b = 0 ORDER BY t1.a;
@@ -162,6 +166,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
RESET enable_hashjoin;
RESET enable_nestloop;
+SET enable_mergejoin TO off;
--
-- partitioned by multiple columns
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: a.kuzmenkov@postgrespro.ru, ashutosh.bapat@enterprisedb.com, pgsql@j-davis.com
Subject: Re: PoC: full merge join on comparison clause
In-Reply-To: <715cb811-4538-9967-a2e3-ca85f2711d80@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox