Here are some updates on this patch.
I split it into two parts. The preparatory part contains some mechanical
changes to prepare for the main part. Most importantly, a new field is
added, `RestrictInfo.is_mj_equality`. It is a marker of mergejoinable
equality clauses, and `RestrictInfo.mergeopfamilies` is a more general
marker of clauses that are mergejoinable but not necessarily equality.
The usages are changed accordingly.
The main part consists of executor and planner changes required to
support inequality merge joins.
The executor changes are as described in the original post.
The planner part has changed significantly since the last version. It
used to apply some shady hacks to ensure we have the required sort
orders of inner and outer paths. Now I think I found a reasonable way to
generate the pathkeys we need. When we sort outer relation in
`sort_inner_and_outer()`, the pathkeys are generated by
`select_outer_pathkeys_for_merge()`. When we use the pathkeys we already
have for the outer relation in `match_unsorted_outer()`, mergeclauses
are selected by `find_mergeclauses_for_pathkeys()`. I changed these
functions to select the right pathkey direction for merge clauses, and
also ensure that we only have a single inequality merge clause and it is
the last one. Also, to use the index paths, I changed
`pathkeys_useful_for_merging()` to keep both pathkey directions for
inequality merge clauses.
Some basic joins work, but I couldn't properly test all the corner cases
with different orderings, because they depend on a bug in vanilla merge
joins [1].
To sum up, the preparatory and executor changes are stable, and the
planner part is WIP.
1.
https://www.postgresql.org/message-id/flat/5dad9160-4632-0e47-e120-8e2082000...@postgrespro.ru
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index f50205ec8a..861327b928 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -166,8 +166,8 @@ typedef enum
* In addition to the expressions themselves, the planner passes the btree
* opfamily OID, collation OID, btree strategy number (BTLessStrategyNumber or
* BTGreaterStrategyNumber), and nulls-first flag that identify the intended
- * sort ordering for each merge key. The mergejoinable operator is an
- * equality operator in the opfamily, and the two inputs are guaranteed to be
+ * sort ordering for each merge key. The mergejoinable operator is a
+ * comparison operator in the opfamily, and the two inputs are guaranteed to be
* ordered in either increasing or decreasing (respectively) order according
* 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.
@@ -200,6 +200,9 @@ MJExamineQuals(List *mergeclauses,
Oid op_righttype;
Oid sortfunc;
+ if (parent->mj_Ineq_Present)
+ elog(ERROR, "inequality mergejoin clause must be the last one");
+
if (!IsA(qual, OpExpr))
elog(ERROR, "mergejoin clause is not an OpExpr");
@@ -225,9 +228,40 @@ MJExamineQuals(List *mergeclauses,
&join_strategy,
&op_lefttype,
&op_righttype);
- if (join_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.
+ */
+ if (join_strategy != BTEqualStrategyNumber)
+ {
+ parent->mj_Ineq_Present = true;
+ switch (join_strategy)
+ {
+ case BTLessEqualStrategyNumber:
+ parent->mj_Ineq_JoinEqual = true;
+ /* fall through */
+ case BTLessStrategyNumber:
+ parent->mj_Ineq_JoinLesser = true;
+ if (sort_strategy != BTGreaterStrategyNumber)
+ elog(ERROR, "join strategy %d is not compatible with sort strategy %d",
+ join_strategy, sort_strategy);
+ break;
+
+ case BTGreaterEqualStrategyNumber:
+ parent->mj_Ineq_JoinEqual = true;
+ /* fall through */
+ case BTGreaterStrategyNumber:
+ parent->mj_Ineq_JoinLesser = true;
+ if (sort_strategy != BTLessStrategyNumber)
+ elog(ERROR, "join strategy %d is not compatible with sort strategy %d",
+ join_strategy, sort_strategy);
+ break;
+
+ default:
+ elog(ERROR, "unsupported join strategy %d", join_strategy);
+ }
+ }
/*
* sortsupport routine must know if abbreviation optimization is
@@ -415,6 +449,19 @@ MJCompare(MergeJoinState *mergestate)
{
MergeJoinClause clause = &mergestate->mj_Clauses[i];
int sort_result;
+ bool join_equal = true;
+ bool join_lesser = false;
+
+ if (mergestate->mj_Ineq_Present && i == mergestate->mj_NumClauses - 1)
+ {
+ /*
+ * If the last merge clause is an inequality, check whether
+ * we have to join the inner tuples that are less than outer
+ * and/or equal to outer.
+ */
+ join_equal = mergestate->mj_Ineq_JoinEqual;
+ join_lesser = mergestate->mj_Ineq_JoinLesser;
+ }
/*
* Special case for NULL-vs-NULL, else use standard comparison.
@@ -429,8 +476,22 @@ MJCompare(MergeJoinState *mergestate)
clause->rdatum, clause->risnull,
&clause->ssup);
- result = sort_result == 0 ? MJCR_Join
- : sort_result < 0 ? MJCR_NextOuter : MJCR_NextInner;
+ if (sort_result < 0)
+ result = MJCR_NextOuter;
+ else if (sort_result == 0)
+ {
+ if (join_equal)
+ result = MJCR_Join;
+ else
+ result = MJCR_NextOuter;
+ }
+ else /* sort_result > 0 */
+ {
+ if (join_lesser)
+ result = MJCR_Join;
+ else
+ result = MJCR_NextInner;
+ }
if (result != MJCR_Join)
break;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d8db0b29e1..9d3f177622 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2797,6 +2797,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_mj_equality)
+ return true;
+ }
+ return false;
+}
+
+/*
* final_cost_mergejoin
* Final estimate of the cost and result size of a mergejoin path.
*
@@ -2848,6 +2866,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))
@@ -2929,18 +2948,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/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 396ee2747a..17cdf0cbe2 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;
@@ -890,6 +891,7 @@ sort_inner_and_outer(PlannerInfo *root,
Path *cheapest_safe_inner = NULL;
List *all_pathkeys;
ListCell *l;
+ bool have_inequality;
/*
* We only consider the cheapest-total-cost input paths, since we are
@@ -990,7 +992,7 @@ sort_inner_and_outer(PlannerInfo *root,
*/
all_pathkeys = select_outer_pathkeys_for_merge(root,
extra->mergeclause_list,
- joinrel);
+ joinrel, &have_inequality);
foreach(l, all_pathkeys)
{
@@ -1002,9 +1004,15 @@ sort_inner_and_outer(PlannerInfo *root,
/* Make a pathkey list with this guy first */
if (l != list_head(all_pathkeys))
+ {
+ if (have_inequality && l == list_tail(all_pathkeys))
+ /* Inequality merge clause must be the last, we can't move it */
+ break;
+
outerkeys = lcons(front_pathkey,
list_delete_ptr(list_copy(all_pathkeys),
front_pathkey));
+ }
else
outerkeys = all_pathkeys; /* no work at first one... */
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index c067f70970..54b464a78d 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -981,6 +981,44 @@ update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
}
/*
+ * Determine the sort order required by an inequality merge clause.
+ */
+static int
+get_merge_sort_strategy(RestrictInfo *rinfo)
+{
+ Oid opfamily = linitial_oid(rinfo->mergeopfamilies);
+ Oid opno;
+ int join_strategy;
+ Oid lefttype;
+ Oid righttype;
+ bool sort_ascending;
+
+ Assert(IsA(rinfo->clause, OpExpr));
+ opno = ((OpExpr *) rinfo->clause)->opno;
+ get_op_opfamily_properties(opno, opfamily,
+ false /* ordering_op */ , &join_strategy,
+ &lefttype, &righttype);
+ switch (join_strategy)
+ {
+ case BTLessEqualStrategyNumber:
+ case BTLessStrategyNumber:
+ sort_ascending = false;
+ break;
+ case BTGreaterEqualStrategyNumber:
+ case BTGreaterStrategyNumber:
+ sort_ascending = true;
+ break;
+ default:
+ elog(ERROR, "unknown merge join clause strategy %d\n", join_strategy);
+ }
+
+ if (!rinfo->outer_is_left)
+ sort_ascending = !sort_ascending;
+
+ return sort_ascending ? BTLessStrategyNumber : BTGreaterStrategyNumber;
+}
+
+/*
* find_mergeclauses_for_pathkeys
* This routine attempts to find a set of mergeclauses that can be
* used with a specified ordering for one of the input relations.
@@ -1021,6 +1059,7 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
PathKey *pathkey = (PathKey *) lfirst(i);
EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
List *matched_restrictinfos = NIL;
+ RestrictInfo *matched_inequality = NULL;
ListCell *j;
/*----------
@@ -1057,6 +1096,9 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
* make_inner_pathkeys_for_merge() has to delete duplicates when
* it constructs the canonical pathkeys list, and we also have to
* deal with the case in create_mergejoin_plan().
+ *
+ * If we found an inequality merge clause, we must put it after all
+ * the equality clauses.
*----------
*/
foreach(j, restrictinfos)
@@ -1070,29 +1112,64 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
else
clause_ec = rinfo->outer_is_left ?
rinfo->right_ec : rinfo->left_ec;
- if (clause_ec == pathkey_ec)
+
+ if (clause_ec != pathkey_ec)
+ continue;
+
+ if (rinfo->is_mj_equality)
matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
+ else
+ {
+ int strategy = get_merge_sort_strategy(rinfo);
+ if (pathkey->pk_strategy != strategy)
+ continue; /* pathkey direction does not match mergeclause */
+ if (matched_inequality)
+ break; /* can't have more than one inequality mergeclause */
+ matched_inequality = rinfo;
+ }
}
+ /*
+ * If we did find usable mergeclause(s) for this sort-key position,
+ * add them to result list. Put inequality to the end of the list.
+ */
+ mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
+ if (matched_inequality)
+ mergeclauses = lappend(mergeclauses, matched_inequality);
/*
* If we didn't find a mergeclause, we're done --- any additional
* sort-key positions in the pathkeys are useless. (But we can still
* mergejoin if we found at least one mergeclause.)
+ *
+ * Also, if we found an inequality clause, we can't add any more
+ * clauses after it.
*/
- if (matched_restrictinfos == NIL)
+ if (matched_restrictinfos == NIL || matched_inequality != NULL)
break;
-
- /*
- * If we did find usable mergeclause(s) for this sort-key position,
- * add them to result list.
- */
- mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
}
return mergeclauses;
}
/*
+ * Find inequality merge clauses in the given list of merge clauses.
+ */
+static List*
+find_inequality_clauses(List *clauses)
+{
+ List *result = NIL;
+ ListCell *lc;
+ foreach(lc, clauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo*) lfirst(lc);
+ Assert(rinfo->mergeopfamilies);
+ if (!rinfo->is_mj_equality)
+ result = lappend(result, rinfo);
+ }
+ return result;
+}
+
+/*
* select_outer_pathkeys_for_merge
* Builds a pathkey list representing a possible sort ordering
* that can be used with the given mergeclauses.
@@ -1119,20 +1196,41 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *
select_outer_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
- RelOptInfo *joinrel)
+ RelOptInfo *joinrel,
+ bool *have_inequality)
{
- List *pathkeys = NIL;
+ List *eq_pathkeys = NIL;
int nClauses = list_length(mergeclauses);
EquivalenceClass **ecs;
int *scores;
int necs;
ListCell *lc;
int j;
+ PathKey *ineq_pathkey = NULL;
+ int ineq_strategy = BTLessStrategyNumber;
+ RestrictInfo *ineq_clause = NULL;
+ int ineq_ec_index = -1;
+
+ *have_inequality = false;
/* Might have no mergeclauses */
if (nClauses == 0)
return NIL;
+ {
+ List *ineq_clauses = find_inequality_clauses(mergeclauses);
+
+ if (list_length(ineq_clauses) > 1)
+ return NIL;
+
+ if (list_length(ineq_clauses) == 1)
+ {
+ *have_inequality = true;
+ ineq_clause = linitial(ineq_clauses);
+ ineq_strategy = get_merge_sort_strategy(ineq_clause);
+ }
+ }
+
/*
* Make arrays of the ECs used by the mergeclauses (dropping any
* duplicates) and their "popularity" scores.
@@ -1183,32 +1281,79 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
}
/*
+ * Find the equivalence class corresponding to the inequality clause.
+ */
+ if (ineq_clause)
+ {
+ EquivalenceClass *oeclass = ineq_clause->outer_is_left
+ ? ineq_clause->left_ec : ineq_clause->right_ec;
+
+ for (ineq_ec_index = 0; ineq_ec_index < necs; ineq_ec_index++)
+ if (ecs[ineq_ec_index] == oeclass)
+ break;
+
+ Assert(ineq_ec_index < necs);
+ }
+
+ /*
* 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.
+ *
+ * Moreover, for the pathkey that corresponds to the inequality merge clause,
+ * we have to use a particular sort direction, so we check this too.
*/
+
if (root->query_pathkeys)
{
+ List *root_pathkeys = root->query_pathkeys;
foreach(lc, root->query_pathkeys)
{
PathKey *query_pathkey = (PathKey *) lfirst(lc);
EquivalenceClass *query_ec = query_pathkey->pk_eclass;
for (j = 0; j < necs; j++)
- {
if (ecs[j] == query_ec)
break; /* found match */
- }
+
if (j >= necs)
break; /* didn't find match */
+
+ if (j == ineq_ec_index)
+ {
+ /*
+ * We found query pathkey corresponding to the inequality merge
+ * clause. Check that it has a suitable sort direction. If it
+ * does, store it separately, because it must be the last one
+ * in the list of join pathkeys.
+ */
+ if (query_pathkey->pk_strategy == ineq_strategy)
+ {
+ /*
+ * root->query_pathkeys shouldn't be redundant, so this pathkey
+ * must be the first one we see for this equivalence class.
+ */
+ Assert(ineq_pathkey == 0);
+ ineq_pathkey = query_pathkey;
+ /*
+ * Mark this pathkey as already-emitted and remove it from the
+ * list of root pathkeys.
+ */
+ scores[ineq_ec_index] = -1;
+ root_pathkeys = list_delete(list_copy(root_pathkeys), ineq_pathkey);
+ }
+ else
+ break; /* pathkey for inequality clause has wrong direction */
+ }
}
+
/* if we got to the end of the list, we have them all */
if (lc == NULL)
{
/* copy query_pathkeys as starting point for our output */
- pathkeys = list_copy(root->query_pathkeys);
+ eq_pathkeys = list_copy(root_pathkeys);
/* mark their ECs as already-emitted */
- foreach(lc, root->query_pathkeys)
+ foreach(lc, root_pathkeys)
{
PathKey *query_pathkey = (PathKey *) lfirst(lc);
EquivalenceClass *query_ec = query_pathkey->pk_eclass;
@@ -1226,9 +1371,10 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
}
/*
- * Add remaining ECs to the list in popularity order, using a default sort
- * ordering. (We could use qsort() here, but the list length is usually
- * so small it's not worth it.)
+ * Add remaining ECs to the list in popularity order. (We could use qsort()
+ * here, but the list length is usually so small it's not worth it.) Use
+ * a default sort ordering for the equality clauses, and the ordering we
+ * computed earlier for the inequality clause.
*/
for (;;)
{
@@ -1236,6 +1382,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
int best_score;
EquivalenceClass *ec;
PathKey *pathkey;
+ int strategy;
best_j = 0;
best_score = scores[0];
@@ -1251,20 +1398,35 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
break; /* all done */
ec = ecs[best_j];
scores[best_j] = -1;
+ strategy = best_j == ineq_ec_index ? ineq_strategy : BTLessStrategyNumber;
pathkey = make_canonical_pathkey(root,
ec,
linitial_oid(ec->ec_opfamilies),
- BTLessStrategyNumber,
- false);
+ strategy,
+ strategy == BTGreaterStrategyNumber);
/* can't be redundant because no duplicate ECs */
- Assert(!pathkey_is_redundant(pathkey, pathkeys));
- pathkeys = lappend(pathkeys, pathkey);
+ Assert(!pathkey_is_redundant(pathkey, eq_pathkeys));
+
+ if (best_j == ineq_ec_index)
+ /*
+ * Pathkey for inequality clause must be the last one,
+ * record it separately.
+ */
+ ineq_pathkey = pathkey;
+ else
+ eq_pathkeys = lappend(eq_pathkeys, pathkey);
}
pfree(ecs);
pfree(scores);
- return pathkeys;
+ if (ineq_pathkey)
+ {
+ Assert(!pathkey_is_redundant(ineq_pathkey, eq_pathkeys));
+ return lappend(eq_pathkeys, ineq_pathkey);
+ }
+ else
+ return eq_pathkeys;
}
/*
@@ -1388,6 +1550,10 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
* one of the directions happens to match an ORDER BY key, in which case
* that direction should be preferred, in hopes of avoiding a final sort step.
* right_merge_direction() implements this heuristic.
+ *
+ * Note that a merge join on an inequality clause can be performed only for
+ * a particular ordering of inputs, so we keep both sort directions if such
+ * clause is present.
*/
static int
pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
@@ -1399,12 +1565,9 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
{
PathKey *pathkey = (PathKey *) lfirst(i);
bool matched = false;
+ bool right_direction = right_merge_direction(root, pathkey);
ListCell *j;
- /* If "wrong" direction, not useful for merging */
- if (!right_merge_direction(root, pathkey))
- break;
-
/*
* First look into the EquivalenceClass of the pathkey, to see if
* there are any members not yet joined to the rel. If so, it's
@@ -1412,7 +1575,16 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
*/
if (rel->has_eclass_joins &&
eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
+ {
+ /*
+ * If "wrong" direction, not useful for merging on an equality
+ * clause.
+ */
+ if (!right_direction)
+ return useful;
+
matched = true;
+ }
else
{
/*
@@ -1426,10 +1598,16 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
if (restrictinfo->mergeopfamilies == NIL)
continue;
+
update_mergeclause_eclasses(root, restrictinfo);
- if (pathkey->pk_eclass == restrictinfo->left_ec ||
- pathkey->pk_eclass == restrictinfo->right_ec)
+ /*
+ * Consider pathkey useful if it has the "right" direction,
+ * or if the correspoinding join clause is an inequality.
+ */
+ if ((pathkey->pk_eclass == restrictinfo->left_ec
+ || pathkey->pk_eclass == restrictinfo->right_ec)
+ && (right_direction || !restrictinfo->is_mj_equality))
{
matched = true;
break;
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 8f474bd97c..5acd20a3ef 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2013,6 +2013,20 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
initialize_mergeclause_eclasses(root, restrictinfo);
}
}
+ else if (restrictinfo->mergeopfamilies)
+ {
+ /* Not an equality 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);
@@ -2625,6 +2639,11 @@ check_mergejoinable(RestrictInfo *restrictinfo)
restrictinfo->mergeopfamilies = get_equality_opfamilies(opno);
restrictinfo->is_mj_equality = true;
}
+ else
+ {
+ restrictinfo->mergeopfamilies = get_inequality_opfamilies(opno);
+ restrictinfo->is_mj_equality = false;
+ }
}
/*
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index fcc8323f62..60b29f5eec 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3022,7 +3022,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
@@ -3205,18 +3204,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 4a69fbb4c9..e914da39a5 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -389,6 +389,46 @@ get_equality_opfamilies(Oid opno)
}
/*
+ * get_inequality_opfamilies
+ * Given an operator, returns a list of operator families in which it
+ * represents btree inequality.
+ *
+ * Also see the comment for get_equality_opfamilies().
+ */
+List *
+get_inequality_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
* operator, but operating on its LHS and/or RHS datatype.
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index a953820f43..7c02299b71 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1661,6 +1661,9 @@ 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
+ * Ineq_Present true if the last merge clause is inequalty
+ * Ineq_JoinLesser true if join lesser values for inequality
+ * Ineq_JoinEqual true if join equal values for inequality
* ----------------
*/
/* private in nodeMergejoin.c: */
@@ -1671,6 +1674,9 @@ typedef struct MergeJoinState
JoinState js; /* its first field is NodeTag */
int mj_NumClauses;
MergeJoinClause mj_Clauses; /* array of length mj_NumClauses */
+ bool mj_Ineq_Present;
+ bool mj_Ineq_JoinLesser;
+ bool mj_Ineq_JoinEqual;
int mj_JoinState;
bool mj_SkipMarkRestore;
bool mj_ExtraMarks;
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index c9e44318ad..3b6f17652a 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,
+ bool *have_inequality);
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 68b01ef377..e8d9187053 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -75,6 +75,7 @@ extern bool get_ordering_op_properties(Oid opno,
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_equality_opfamilies(Oid opno);
+extern List *get_inequality_opfamilies(Oid opno);
extern bool get_compatible_hash_operators(Oid opno,
Oid *lhs_opno, Oid *rhs_opno);
extern bool get_op_hash_functions(Oid opno,
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index c50a206efb..91e49d5244 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, J2_TBL.k;
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 | 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
- | 0 | | zero | 2 | 4
- | 0 | | zero | | 0
(9 rows)
--
@@ -1846,6 +1847,122 @@ SELECT '' AS "xxx", *
(1 row)
--
+-- Full merge join
+--
+set enable_hashjoin to 0;
+-- simple
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+ i | j | t | i | k
+---+---+-------+---+----
+ | 0 | zero | |
+ | | null | |
+ | | | 0 |
+ | | | |
+ 8 | 8 | eight | |
+ 7 | 7 | seven | |
+ 6 | 6 | six | |
+ 5 | 0 | five | |
+ 4 | 1 | four | |
+ 3 | 2 | three | 2 | 4
+ 2 | 3 | two | 2 | 4
+ 1 | 4 | one | 2 | 4
+ 1 | 4 | one | 2 | 2
+ 0 | | zero | 2 | 4
+ 0 | | zero | 2 | 2
+ | | | | 0
+ | | | 1 | -1
+ | | | 3 | -3
+ | | | 5 | -5
+ | | | 5 | -5
+(20 rows)
+
+-- output ordering
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k order by j2_tbl.k desc;
+ i | j | t | i | k
+---+---+-------+---+----
+ | | null | |
+ | 0 | zero | |
+ | | | 0 |
+ | | | |
+ 8 | 8 | eight | |
+ 7 | 7 | seven | |
+ 6 | 6 | six | |
+ 5 | 0 | five | |
+ 4 | 1 | four | |
+ 2 | 3 | two | 2 | 4
+ 3 | 2 | three | 2 | 4
+ 1 | 4 | one | 2 | 4
+ 0 | | zero | 2 | 4
+ 1 | 4 | one | 2 | 2
+ 0 | | zero | 2 | 2
+ | | | | 0
+ | | | 1 | -1
+ | | | 3 | -3
+ | | | 5 | -5
+ | | | 5 | -5
+(20 rows)
+
+-- multiple clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i = j2_tbl.k;
+ i | j | t | i | k
+---+---+-------+---+----
+ | | | 5 | -5
+ | | | 5 | -5
+ | | | 3 | -3
+ | | | 1 | -1
+ | | | | 0
+ 0 | | zero | |
+ 1 | 4 | one | |
+ 2 | 3 | two | |
+ | | | 2 | 2
+ 3 | 2 | three | |
+ 4 | 1 | four | 2 | 4
+ | | | 0 |
+ | | | |
+ 5 | 0 | five | |
+ 6 | 6 | six | |
+ 7 | 7 | seven | |
+ 8 | 8 | eight | |
+ | | null | |
+ | 0 | zero | |
+(19 rows)
+
+-- multiple inequality clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i < j2_tbl.k;
+ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+-- using an index
+create index idx_j1_tbl_i on j1_tbl(i);
+analyze j1_tbl;
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.k;
+ QUERY PLAN
+-------------------------------------
+ Merge Full Join
+ Merge Cond: (j1_tbl.i > j2_tbl.k)
+ -> Sort
+ Sort Key: j1_tbl.i
+ -> Seq Scan on j1_tbl
+ -> Sort
+ Sort Key: j2_tbl.k
+ -> Seq Scan on j2_tbl
+(8 rows)
+
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+ QUERY PLAN
+-------------------------------------
+ Merge Full Join
+ Merge Cond: (j1_tbl.i < j2_tbl.k)
+ -> Sort
+ Sort Key: j1_tbl.i DESC
+ -> Seq Scan on j1_tbl
+ -> Sort
+ Sort Key: j2_tbl.k DESC
+ -> Seq Scan on j2_tbl
+(8 rows)
+
+drop index idx_j1_tbl_i;
+analyze j1_tbl;
+reset enable_hashjoin;
+--
-- semijoin selectivity for <>
--
explain (costs off)
@@ -5128,43 +5245,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: (i.f1 < (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)))
+ -> Sort
+ Output: i.f1
+ Sort Key: i.f1 DESC
+ -> Seq Scan on public.int4_tbl i
+ Output: 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)) DESC
+ -> 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: (b.q1 < b2.f1)
+ -> Sort
+ Output: b.q1, b.q2
+ Sort Key: b.q1 DESC
+ -> Seq Scan on public.int8_tbl b
+ Output: b.q1, b.q2
+ -> Sort
+ Output: b2.f1
+ Sort Key: b2.f1 DESC
+ -> Seq Scan on public.int4_tbl b2
+ Output: b2.f1
+ -> 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
- Output: i.f1
- -> Seq Scan on public.int4_tbl i
- Output: i.f1
-(34 rows)
+ -> Seq Scan on public.int8_tbl c
+ Output: c.q1, c.q2
+(42 rows)
-- check processing of postponed quals (bug #9041)
explain (verbose, costs off)
@@ -5471,6 +5596,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);
@@ -5740,6 +5866,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.out
index 4fccd9ae54..5d4028ba79 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -4,6 +4,8 @@
--
-- Enable partitionwise join, which by default is disabled.
SET enable_partitionwise_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.sql
index fc84237ce9..f85eeb00aa 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, J2_TBL.k;
--
@@ -194,6 +195,36 @@ SELECT '' AS "xxx", *
FROM J1_TBL LEFT JOIN J2_TBL USING (i) WHERE (i = 1);
--
+-- Full merge join
+--
+
+set enable_hashjoin to 0;
+
+-- simple
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+
+-- output ordering
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k order by j2_tbl.k desc;
+
+-- multiple clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i = j2_tbl.k;
+
+-- multiple inequality clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i < j2_tbl.k;
+
+-- using an index
+create index idx_j1_tbl_i on j1_tbl(i);
+analyze j1_tbl;
+
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.k;
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+
+drop index idx_j1_tbl_i;
+analyze j1_tbl;
+
+reset enable_hashjoin;
+
+--
-- semijoin selectivity for <>
--
explain (costs off)
@@ -1812,6 +1843,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);
@@ -1912,6 +1945,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.sql
index a2d8b1be55..54c5e46d99 100644
--- a/src/test/regress/sql/partition_join.sql
+++ b/src/test/regress/sql/partition_join.sql
@@ -6,6 +6,9 @@
-- Enable partitionwise join, which by default is disabled.
SET enable_partitionwise_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
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index f3cbe2f889..f50205ec8a 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -172,31 +172,30 @@ 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));
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_strategy = mergestrategies[iClause];
bool nulls_first = mergenullsfirst[iClause];
- int op_strategy;
+ int join_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid sortfunc;
@@ -207,26 +206,26 @@ 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_strategy == BTLessStrategyNumber)
clause->ssup.ssup_reverse = false;
- else if (opstrategy == BTGreaterStrategyNumber)
+ else if (sort_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_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_strategy,
&op_lefttype,
&op_righttype);
- if (op_strategy != BTEqualStrategyNumber) /* should not happen */
+ if (join_strategy != BTEqualStrategyNumber) /* should not happen */
elog(ERROR, "cannot merge using non-equality operator %u",
qual->opno);
@@ -265,8 +264,6 @@ MJExamineQuals(List *mergeclauses,
iClause++;
}
-
- return clauses;
}
/*
@@ -378,20 +375,29 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
return result;
}
+/* Tuple comparison result */
+typedef enum
+{
+ MJCR_NextInner = 1,
+ MJCR_NextOuter = -1,
+ MJCR_Join = 0
+} MJCompareResult;
+
/*
* MJCompare
*
- * Compare the mergejoinable values of the current two input tuples
- * and return 0 if they are equal (ie, the mergejoin equalities all
- * succeed), >0 if outer > inner, <0 if outer < inner.
+ * Compare the mergejoinable values of the current two input tuples.
+ * If they are equal, i.e., the mergejoin equalities all succeed,
+ * return MJCR_Join, if outer > inner, MJCR_NextInner, and else
+ * MJCR_NextOuter.
*
* 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 +414,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 +425,14 @@ 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);
+
+ result = sort_result == 0 ? MJCR_Join
+ : sort_result < 0 ? MJCR_NextOuter : MJCR_NextInner;
- if (result != 0)
+ if (result != MJCR_Join)
break;
}
@@ -435,9 +445,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 +613,7 @@ ExecMergeJoin(PlanState *pstate)
ExprState *joinqual;
ExprState *otherqual;
bool qualResult;
- int compareResult;
+ MJCompareResult compareResult;
PlanState *innerPlan;
TupleTableSlot *innerTupleSlot;
PlanState *outerPlan;
@@ -891,11 +901,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 +1058,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 +1116,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 +1192,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 +1201,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;
/*
@@ -1592,12 +1604,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 82255b0d1d..8b8321ba8e 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -2185,6 +2185,7 @@ _copyRestrictInfo(const RestrictInfo *from)
COPY_SCALAR_FIELD(norm_selec);
COPY_SCALAR_FIELD(outer_selec);
COPY_NODE_FIELD(mergeopfamilies);
+ COPY_SCALAR_FIELD(is_mj_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.c
index 011d2a3fa9..fd03a42bd3 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2477,6 +2477,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_mj_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/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 70a925c63a..212a8025f6 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -68,9 +68,9 @@ static bool reconsider_full_join_clause(PlannerInfo *root,
/*
* process_equivalence
- * The given clause has a mergejoinable operator and can be applied without
- * any delay by an outer join, so its two sides can be considered equal
- * anywhere they are both computable; moreover that equality can be
+ * The given clause has a mergejoinable equality operator and can be applied
+ * without any delay by an outer join, so its two sides can be considered
+ * equal anywhere they are both computable; moreover that equality can be
* extended transitively. Record this knowledge in the EquivalenceClass
* data structure, if applicable. Returns true if successful, false if not
* (in which case caller should treat the clause as ordinary, not an
@@ -233,6 +233,7 @@ process_equivalence(PlannerInfo *root,
op_input_types(opno, &item1_type, &item2_type);
opfamilies = restrictinfo->mergeopfamilies;
+ Assert(restrictinfo->is_mj_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_equality_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_equality_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 7fc70804f8..b294b787e1 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2982,8 +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)
- continue; /* not mergejoinable */
+ if (!restrictinfo->is_mj_equality)
+ continue; /* not a mergejoinable equality */
/*
* The clause certainly doesn't refer to anything but the given rel.
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 3f1c1b3477..ac14818448 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -1446,7 +1446,7 @@ have_partkey_equi_join(RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype,
continue;
/* Skip clauses which are not equality conditions. */
- if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
+ if (!rinfo->is_mj_equality && !OidIsValid(rinfo->hashjoinoperator))
continue;
opexpr = (OpExpr *) rinfo->clause;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index ef58cff28d..c067f70970 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_equality_opfamilies(equality_op);
if (!opfamilies) /* certainly should find some */
elog(ERROR, "could not find opfamilies for equality operator %u",
equality_op);
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index ef25fefa45..ed41f3913d 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -237,11 +237,10 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
}
/*
- * Search for mergejoinable clauses that constrain the inner rel against
- * either the outer rel or a pseudoconstant. 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 either the outer rel or a pseudoconstant. Mergejoinable equality
+ * clauses are based on equality operators for some btree opclass, and don't
+ * contain volatile functions, so it's what we want.
*/
foreach(l, innerrel->joininfo)
{
@@ -267,10 +266,10 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
continue; /* else, ignore; not useful here */
}
- /* Ignore if it's not a mergejoinable clause */
+ /* Ignore if it's not a mergejoinable equality clause */
if (!restrictinfo->can_join ||
- restrictinfo->mergeopfamilies == NIL)
- continue; /* not mergejoinable */
+ !restrictinfo->is_mj_equality)
+ continue;
/*
* Check if clause has the form "outer op inner" or "inner op outer",
@@ -1084,11 +1083,10 @@ 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 either the outer rel. Mergejoinable equality clauses are based
+ * on equality operators for some btree opclass, and don't contain volatile
+ * functions, so it's what we want.
*/
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_mj_equality)
continue; /* not mergejoinable */
/*
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index a436b53806..8f474bd97c 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_equality_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_mj_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_mj_equality) /* EC might have changed this */
initialize_mergeclause_eclasses(root, restrictinfo);
/* ... and fall through to distribute_restrictinfo_to_rels */
}
@@ -2616,9 +2618,14 @@ 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_equality_opfamilies(opno);
+ restrictinfo->is_mj_equality = true;
+ }
+ }
/*
* 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.c
index 1075dde40c..ee65b03815 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_mj_equality = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 51b6b4f7bb..4a69fbb4c9 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -341,9 +341,9 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type)
}
/*
- * get_mergejoin_opfamilies
- * Given a putatively mergejoinable operator, return a list of the OIDs
- * of the btree opfamilies in which it represents equality.
+ * get_equality_opfamilies
+ * Given an operator, return a list of the OIDs of the btree opfamilies
+ * in which it represents equality.
*
* It is possible (though at present unusual) for an operator to be equality
* in more than one opfamily, hence the result is a list. This also lets us
@@ -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_equality_opfamilies(Oid opno)
{
List *result = NIL;
CatCList *catlist;
@@ -1164,11 +1164,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
@@ -1177,7 +1177,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;
@@ -1234,7 +1234,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/relation.h b/src/include/nodes/relation.h
index b1c63173c2..fa63dd255a 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1890,6 +1890,7 @@ typedef struct RestrictInfo
/* valid if clause is mergejoinable, else NIL */
List *mergeopfamilies; /* opfamilies containing clause operator */
+ bool is_mj_equality; /* is this a mergejoinable equality clause? */
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index 1f6c04a8f3..68b01ef377 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -74,7 +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_mergejoin_opfamilies(Oid opno);
+extern List *get_equality_opfamilies(Oid opno);
extern bool get_compatible_hash_operators(Oid opno,
Oid *lhs_opno, Oid *rhs_opno);
extern bool get_op_hash_functions(Oid opno,
@@ -99,7 +99,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);
