Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware) - Mailing list pgsql-bugs
| From | Tom Lane |
|---|---|
| Subject | Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware) |
| Date | |
| Msg-id | 3014965.1684293045@sss.pgh.pa.us Whole thread Raw |
| In response to | Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware) (Tom Lane <tgl@sss.pgh.pa.us>) |
| Responses |
Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware)
|
| List | pgsql-bugs |
After further poking at this, I've concluded that you're right and
we should not try to make the "add extra nullingrels all the time"
approach work. It still seems theoretically cleaner to me, but
there are too many messy special cases.
Accordingly, here's a reviewed/revised version of the v3 patch series
you posted earlier. Significant changes:
* I was not impressed by the idea of adding a join_info_array to look
up by ojrelid. It seemed to me that your changes around that replaced
foreach loops over join_info_list with bms_next_member loops over
relid sets that you often had to do extra calculations to create.
Whether that's a performance win at all is debatable. Moreover,
I realized from testing this that situations where there are
pushed-down OJs are pretty rare (there are *none* in the core
regression tests before the cases added below), so optimizing for
that at the cost of extra cycles when it doesn't happen is probably
not the way.
* I did keep the idea of splitting up commute_below from my other
patch series. That's 0001 below and then I rebased 0002-0004 on
that.
* I'm not terribly happy with 0004 as it stands, specifically the
business of making build_join_rel recalculate pushed_down_ojrelids
from scratch. Again, that's adding cycles to the mainline case to
support an unusual case. It'd be better to make
add_outer_joins_to_relids have an extra output that is the
pushed_down_ojrelids set, and pass that forward. I ran out of time
to make that happen today, though.
* 0005 below adds the original test case and cases based on the other
examples given at various points in this thread. I put that last
because until 0004 one or the other of these tests fails miserably.
All the expected outputs here match what v15 does.
* While I've not done it here, I'm seriously considering reverting
those Asserts in setrefs.c back to somewhat-informative elogs,
at least till late in beta. It seems like we are still at a point
where we need to make it easy to acquire info about failures in this
logic, and using Asserts isn't all that conducive to that.
regards, tom lane
From 771782ff9698fb3073dc42f479d7e54d217ad9cf Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Tue, 16 May 2023 18:47:05 -0400
Subject: [PATCH v6 1/5] Split SpecialJoinInfo.commute_below into LHS and RHS
parts.
Storing just a single relid set seems to have been a poor decision,
as there are more places where that adds effort than removes effort
compared to having separate LHS and RHS sets. Up to now, none of
the involved places were performance-critical, but the next patch
in this series will add a usage that's hit multiple times per outer
join joinrel. So let's split the field into two parts, making it
more like commute_above_[lr].
---
src/backend/optimizer/path/costsize.c | 6 ++-
src/backend/optimizer/path/joinrels.c | 3 +-
src/backend/optimizer/plan/analyzejoins.c | 3 +-
src/backend/optimizer/plan/initsplan.c | 60 ++++++++++-------------
src/backend/optimizer/util/orclauses.c | 3 +-
src/include/nodes/pathnodes.h | 17 ++++---
6 files changed, 47 insertions(+), 45 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 0a2562c149..3039186530 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4788,7 +4788,8 @@ compute_semi_anti_join_factors(PlannerInfo *root,
norm_sjinfo.ojrelid = 0;
norm_sjinfo.commute_above_l = NULL;
norm_sjinfo.commute_above_r = NULL;
- norm_sjinfo.commute_below = NULL;
+ norm_sjinfo.commute_below_l = NULL;
+ norm_sjinfo.commute_below_r = NULL;
/* we don't bother trying to make the remaining fields valid */
norm_sjinfo.lhs_strict = false;
norm_sjinfo.semi_can_btree = false;
@@ -4956,7 +4957,8 @@ approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
sjinfo.ojrelid = 0;
sjinfo.commute_above_l = NULL;
sjinfo.commute_above_r = NULL;
- sjinfo.commute_below = NULL;
+ sjinfo.commute_below_l = NULL;
+ sjinfo.commute_below_r = NULL;
/* we don't bother trying to make the remaining fields valid */
sjinfo.lhs_strict = false;
sjinfo.semi_can_btree = false;
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 4c6ea3a2f0..c0d9c50270 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -740,7 +740,8 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
sjinfo->ojrelid = 0;
sjinfo->commute_above_l = NULL;
sjinfo->commute_above_r = NULL;
- sjinfo->commute_below = NULL;
+ sjinfo->commute_below_l = NULL;
+ sjinfo->commute_below_r = NULL;
/* we don't bother trying to make the remaining fields valid */
sjinfo->lhs_strict = false;
sjinfo->semi_can_btree = false;
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 657b6e5907..1116ad978e 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -399,7 +399,8 @@ remove_rel_from_query(PlannerInfo *root, int relid, int ojrelid,
/* relid cannot appear in these fields, but ojrelid can: */
sjinfo->commute_above_l = bms_del_member(sjinfo->commute_above_l, ojrelid);
sjinfo->commute_above_r = bms_del_member(sjinfo->commute_above_r, ojrelid);
- sjinfo->commute_below = bms_del_member(sjinfo->commute_below, ojrelid);
+ sjinfo->commute_below_l = bms_del_member(sjinfo->commute_below_l, ojrelid);
+ sjinfo->commute_below_r = bms_del_member(sjinfo->commute_below_r, ojrelid);
}
/*
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 06f90882c4..5cbb7b9a86 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -1213,8 +1213,8 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem)
* positioning decisions will be made later, when we revisit the
* postponed clauses.
*/
- if (sjinfo->commute_below)
- ojscope = bms_add_members(ojscope, sjinfo->commute_below);
+ ojscope = bms_add_members(ojscope, sjinfo->commute_below_l);
+ ojscope = bms_add_members(ojscope, sjinfo->commute_below_r);
}
else
postponed_oj_qual_list = NULL;
@@ -1400,7 +1400,8 @@ make_outerjoininfo(PlannerInfo *root,
/* these fields may get added to later: */
sjinfo->commute_above_l = NULL;
sjinfo->commute_above_r = NULL;
- sjinfo->commute_below = NULL;
+ sjinfo->commute_below_l = NULL;
+ sjinfo->commute_below_r = NULL;
compute_semijoin_info(root, sjinfo, clause);
@@ -1643,37 +1644,30 @@ make_outerjoininfo(PlannerInfo *root,
* Now that we've identified the correct min_lefthand and min_righthand,
* any commute_below_l or commute_below_r relids that have not gotten
* added back into those sets (due to intervening outer joins) are indeed
- * commutable with this one. Update the derived data in the
- * SpecialJoinInfos.
+ * commutable with this one.
+ *
+ * First, delete any subsequently-added-back relids (this is easier than
+ * maintaining commute_below_l/r precisely through all the above).
*/
+ commute_below_l = bms_del_members(commute_below_l, min_lefthand);
+ commute_below_r = bms_del_members(commute_below_r, min_righthand);
+
+ /* Anything left? */
if (commute_below_l || commute_below_r)
{
- Relids commute_below;
-
- /*
- * Delete any subsequently-added-back relids (this is easier than
- * maintaining commute_below_l/r precisely through all the above).
- */
- commute_below_l = bms_del_members(commute_below_l, min_lefthand);
- commute_below_r = bms_del_members(commute_below_r, min_righthand);
-
- /* Anything left? */
- commute_below = bms_union(commute_below_l, commute_below_r);
- if (!bms_is_empty(commute_below))
+ /* Yup, so we must update the derived data in the SpecialJoinInfos */
+ sjinfo->commute_below_l = commute_below_l;
+ sjinfo->commute_below_r = commute_below_r;
+ foreach(l, root->join_info_list)
{
- /* Yup, so we must update the data structures */
- sjinfo->commute_below = commute_below;
- foreach(l, root->join_info_list)
- {
- SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
-
- if (bms_is_member(otherinfo->ojrelid, commute_below_l))
- otherinfo->commute_above_l =
- bms_add_member(otherinfo->commute_above_l, ojrelid);
- else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
- otherinfo->commute_above_r =
- bms_add_member(otherinfo->commute_above_r, ojrelid);
- }
+ SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
+
+ if (bms_is_member(otherinfo->ojrelid, commute_below_l))
+ otherinfo->commute_above_l =
+ bms_add_member(otherinfo->commute_above_l, ojrelid);
+ else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
+ otherinfo->commute_above_r =
+ bms_add_member(otherinfo->commute_above_r, ojrelid);
}
}
@@ -1889,8 +1883,7 @@ deconstruct_distribute_oj_quals(PlannerInfo *root,
* as-is.
*/
Assert(sjinfo->lhs_strict); /* else we shouldn't be here */
- if (sjinfo->commute_above_r ||
- bms_overlap(sjinfo->commute_below, sjinfo->syn_lefthand))
+ if (sjinfo->commute_above_r || sjinfo->commute_below_l)
{
Relids joins_above;
Relids joins_below;
@@ -1901,8 +1894,7 @@ deconstruct_distribute_oj_quals(PlannerInfo *root,
/* Identify the outer joins this one commutes with */
joins_above = sjinfo->commute_above_r;
- joins_below = bms_intersect(sjinfo->commute_below,
- sjinfo->syn_lefthand);
+ joins_below = sjinfo->commute_below_l;
/*
* Generate qual variants with different sets of nullingrels bits.
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index 85ecdfc14f..ca8b5ff92f 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -334,7 +334,8 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
sjinfo.ojrelid = 0;
sjinfo.commute_above_l = NULL;
sjinfo.commute_above_r = NULL;
- sjinfo.commute_below = NULL;
+ sjinfo.commute_below_l = NULL;
+ sjinfo.commute_below_r = NULL;
/* we don't bother trying to make the remaining fields valid */
sjinfo.lhs_strict = false;
sjinfo.semi_can_btree = false;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 7d4f24d250..23dd671bf4 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2783,11 +2783,15 @@ typedef struct PlaceHolderVar
* 3, when this join is in the RHS of the upper join (so, this is the lower
* join in the second form of the identity).
*
- * commute_below is filled with the relids of syntactically-lower outer joins
- * that have been found to commute with this one per outer join identity 3.
- * (We need not record which side they are on, since that can be determined
- * by seeing whether the lower join's relid appears in syn_lefthand or
- * syn_righthand.)
+ * commute_below_l is filled with the relids of syntactically-lower outer
+ * joins that have been found to commute with this one per outer join identity
+ * 3 and are in the LHS of this join (so, this is the upper join in the first
+ * form of the identity).
+ *
+ * commute_below_r is filled with the relids of syntactically-lower outer
+ * joins that have been found to commute with this one per outer join identity
+ * 3 and are in the RHS of this join (so, this is the upper join in the second
+ * form of the identity).
*
* lhs_strict is true if the special join's condition cannot succeed when the
* LHS variables are all NULL (this means that an outer join can commute with
@@ -2829,7 +2833,8 @@ struct SpecialJoinInfo
Index ojrelid; /* outer join's RT index; 0 if none */
Relids commute_above_l; /* commuting OJs above this one, if LHS */
Relids commute_above_r; /* commuting OJs above this one, if RHS */
- Relids commute_below; /* commuting OJs below this one */
+ Relids commute_below_l; /* commuting OJs in this one's LHS */
+ Relids commute_below_r; /* commuting OJs in this one's RHS */
bool lhs_strict; /* joinclause is strict for some LHS rel */
/* Remaining fields are set only for JOIN_SEMI jointype: */
bool semi_can_btree; /* true if semi_operators are all btree */
--
2.31.1
From 2b52c286dd8ed1c8cabaa18a579183461e47f3af Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Tue, 16 May 2023 19:05:44 -0400
Subject: [PATCH v6 2/5] Postpone adding pushed down ojrelid to a join's
relids.
When we apply outer join identity 3 in the forward direction, don't
immediately add the now-lower join's relid to the relid set of the
join. This represents the fact that values from the "C" relation
(the join's RHS) aren't going to be fully correct until we perform
the other, commuted join.
Per report from Andrey Lepikhov. Thanks to Richard Guo for
investigation and testing.
Discussion: https://postgr.es/m/0b819232-4b50-f245-1c7d-c8c61bf41827@postgrespro.ru
---
src/backend/optimizer/README | 21 ++++++
src/backend/optimizer/path/equivclass.c | 20 +++---
src/backend/optimizer/path/indxpath.c | 2 +-
src/backend/optimizer/path/joinrels.c | 85 +++++++++++++++++++++--
src/backend/optimizer/plan/analyzejoins.c | 13 ++--
src/backend/optimizer/util/relnode.c | 9 ++-
src/include/optimizer/paths.h | 4 +-
7 files changed, 127 insertions(+), 27 deletions(-)
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index 227278eb6c..d017f3555a 100644
--- a/src/backend/optimizer/README
+++ b/src/backend/optimizer/README
@@ -410,6 +410,8 @@ joins. However, when building Vars representing the outputs of join
relations, we need to ensure that their varnullingrels are set to
values consistent with the syntactic join order, so that they will
appear equal() to pre-existing Vars in the upper part of the query.
+(We also have to be careful about where we place qual clauses using
+such Vars, as described below.)
Outer joins also complicate handling of subquery pull-up. Consider
@@ -507,6 +509,25 @@ problem for join relation identification either, since whether a semijoin
has been completed is again implicit in the set of base relations
included in the join.
+As usual, outer join identity 3 complicates matters. If we start with
+ (A leftjoin B on (Pab)) leftjoin C on (Pbc)
+then the parser will have marked any C Vars appearing above these joins
+with the RT index of the B/C join. If we now transform to
+ A leftjoin (B leftjoin C on (Pbc)) on (Pab)
+then it would appear that a clause using only such Vars could be pushed
+down and applied as a filter clause (not a join clause) at the lower
+B/C join. But *this might not give the right answer* since the clause
+might see a non-null value for the C Var that will be replaced by null
+once the A/B join is performed. We handle this by saying that the
+pushed-down join hasn't completely performed the work of the B/C join
+and hence is not entitled to include that outer join relid in its
+relid set. When we form the A/B join, both outer joins' relids will
+be added to its relid set, and then the upper clause will be applied
+at the correct join level. (Note there is no problem when identity 3
+is applied in the other direction: if we started with the second form
+then upper C Vars are marked with both outer join relids, so they
+cannot drop below whichever join is applied second.)
+
There is one additional complication for qual clause placement, which
occurs when we have made multiple versions of an outer-join clause as
described previously (that is, we have both "Pbc" and "Pb*c" forms of
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 9949d5b1d3..ecb1343d1a 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1366,19 +1366,20 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
* commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
* we already have "b.y = a.x", we return the existing clause.
*
- * If we are considering an outer join, ojrelid is the associated OJ relid,
- * otherwise it's zero.
+ * If we are considering an outer join, sjinfo is the associated OJ info,
+ * otherwise it can be NULL.
*
* join_relids should always equal bms_union(outer_relids, inner_rel->relids)
- * plus ojrelid if that's not zero. We could simplify this function's API by
- * computing it internally, but most callers have the value at hand anyway.
+ * plus whatever add_outer_joins_to_relids() would add. We could simplify
+ * this function's API by computing it internally, but most callers have the
+ * value at hand anyway.
*/
List *
generate_join_implied_equalities(PlannerInfo *root,
Relids join_relids,
Relids outer_relids,
RelOptInfo *inner_rel,
- Index ojrelid)
+ SpecialJoinInfo *sjinfo)
{
List *result = NIL;
Relids inner_relids = inner_rel->relids;
@@ -1396,8 +1397,9 @@ generate_join_implied_equalities(PlannerInfo *root,
nominal_inner_relids = inner_rel->top_parent_relids;
/* ECs will be marked with the parent's relid, not the child's */
nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
- if (ojrelid != 0)
- nominal_join_relids = bms_add_member(nominal_join_relids, ojrelid);
+ nominal_join_relids = add_outer_joins_to_relids(root,
+ nominal_join_relids,
+ sjinfo);
}
else
{
@@ -1418,7 +1420,7 @@ generate_join_implied_equalities(PlannerInfo *root,
* At inner joins, we can be smarter: only consider eclasses mentioning
* both input rels.
*/
- if (ojrelid != 0)
+ if (sjinfo && sjinfo->ojrelid != 0)
matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
else
matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
@@ -1467,7 +1469,7 @@ generate_join_implied_equalities(PlannerInfo *root,
* generate_join_implied_equalities_for_ecs
* As above, but consider only the listed ECs.
*
- * For the sole current caller, we can assume ojrelid == 0, that is we are
+ * For the sole current caller, we can assume sjinfo == NULL, that is we are
* not interested in outer-join filter clauses. This might need to change
* in future.
*/
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 9f4698f2a2..1436dbc2f2 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3364,7 +3364,7 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
otherrels),
otherrels,
rel,
- 0));
+ NULL));
/*
* Normally we remove quals that are implied by a partial index's
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index c0d9c50270..262d3aec65 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -710,9 +710,8 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
return NULL;
}
- /* If we have an outer join, add its RTI to form the canonical relids. */
- if (sjinfo && sjinfo->ojrelid != 0)
- joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
+ /* Add outer join relid(s) to form the canonical relids. */
+ joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo);
/* Swap rels if needed to match the join info. */
if (reversed)
@@ -776,6 +775,81 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
return joinrel;
}
+/*
+ * add_outer_joins_to_relids
+ * Add relids to input_relids to represent any outer joins that will be
+ * calculated at this join.
+ *
+ * input_relids is the union of the relid sets of the two input relations.
+ * Note that we modify this in-place and return it; caller must bms_copy()
+ * it first, if a separate value is desired.
+ *
+ * sjinfo represents the join being performed.
+ */
+Relids
+add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids,
+ SpecialJoinInfo *sjinfo)
+{
+ /* Nothing to do if this isn't an outer join with an assigned relid. */
+ if (sjinfo == NULL || sjinfo->ojrelid == 0)
+ return input_relids;
+
+ /*
+ * If it's not a left join, we have no rules that would permit executing
+ * it in non-syntactic order, so just form the syntactic relid set. (This
+ * is just a quick-exit test; we'd come to the same conclusion anyway,
+ * since its commute_below_l and commute_above_l sets must be empty.)
+ */
+ if (sjinfo->jointype != JOIN_LEFT)
+ return bms_add_member(input_relids, sjinfo->ojrelid);
+
+ /*
+ * Add the OJ relid unless this join has been pushed into the RHS of a
+ * syntactically-lower left join per OJ identity 3. (If it has, then we
+ * cannot claim that its outputs represent the final state of its RHS.)
+ */
+ if (bms_is_subset(sjinfo->commute_below_l, input_relids))
+ input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
+
+ /*
+ * Contrariwise, if we are now forming the final result of such a commuted
+ * pair of OJs, it's time to add the relid(s) of the pushed-down join(s).
+ * We can skip this if this join was never a candidate to be pushed up.
+ */
+ if (sjinfo->commute_above_l)
+ {
+ ListCell *lc;
+
+ /*
+ * The current join could complete the nulling of more than one
+ * pushed-down join, so we have to examine all the SpecialJoinInfos.
+ * Because join_info_list was built in bottom-up order, it's
+ * sufficient to traverse it once: an ojrelid we add in one loop
+ * iteration would not have affected decisions of earlier iterations.
+ */
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
+
+ if (othersj == sjinfo ||
+ othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT)
+ continue; /* definitely not interesting */
+
+ if (othersj->commute_below_l == NULL)
+ continue; /* was never a candidate to be pushed down */
+
+ /* Add it if not already present but conditions now satisfied */
+ if (!bms_is_member(othersj->ojrelid, input_relids) &&
+ bms_is_subset(othersj->min_lefthand, input_relids) &&
+ bms_is_subset(othersj->min_righthand, input_relids) &&
+ bms_is_subset(othersj->commute_below_l, input_relids))
+ input_relids = bms_add_member(input_relids, othersj->ojrelid);
+ }
+ }
+
+ return input_relids;
+}
+
/*
* populate_joinrel_with_paths
* Add paths to the given joinrel for given pair of joining relations. The
@@ -1535,9 +1609,8 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
/* Build correct join relids for child join */
child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids);
- if (child_sjinfo->ojrelid != 0)
- child_joinrelids = bms_add_member(child_joinrelids,
- child_sjinfo->ojrelid);
+ child_joinrelids = add_outer_joins_to_relids(root, child_joinrelids,
+ child_sjinfo);
/* Find the AppendRelInfo structures */
appinfos = find_appinfos_by_relids(root, child_joinrelids, &nappinfos);
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 1116ad978e..7463b3696a 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -88,8 +88,11 @@ restart:
*/
innerrelid = bms_singleton_member(sjinfo->min_righthand);
- /* Compute the relid set for the join we are considering */
- joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+ /*
+ * Compute the relid set for the join we are considering. We can
+ * assume things are done in syntactic order.
+ */
+ joinrelids = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
if (sjinfo->ojrelid != 0)
joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
@@ -201,8 +204,8 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
if (!rel_supports_distinctness(root, innerrel))
return false;
- /* Compute the relid set for the join we are considering */
- inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+ /* Compute the syntactic relid set for the join we are considering */
+ inputrelids = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
Assert(sjinfo->ojrelid != 0);
joinrelids = bms_copy(inputrelids);
joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
@@ -666,7 +669,7 @@ reduce_unique_semijoins(PlannerInfo *root)
joinrelids,
sjinfo->min_lefthand,
innerrel,
- 0),
+ NULL),
innerrel->joininfo);
/* Test whether the innerrel is unique for those clauses. */
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 68fd033595..0d849d9494 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -870,8 +870,7 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
joinrel->reloptkind = RELOPT_OTHER_JOINREL;
joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids);
- if (sjinfo->ojrelid != 0)
- joinrel->relids = bms_add_member(joinrel->relids, sjinfo->ojrelid);
+ joinrel->relids = add_outer_joins_to_relids(root, joinrel->relids, sjinfo);
joinrel->rows = 0;
/* cheap startup cost is interesting iff not all tuples to be retrieved */
joinrel->consider_startup = (root->tuple_fraction > 0);
@@ -1259,7 +1258,7 @@ build_joinrel_restrictlist(PlannerInfo *root,
joinrel->relids,
outer_rel->relids,
inner_rel,
- sjinfo->ojrelid));
+ sjinfo));
return result;
}
@@ -1543,7 +1542,7 @@ get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
joinrelids,
required_outer,
baserel,
- 0));
+ NULL));
/* Compute set of serial numbers of the enforced clauses */
pserials = NULL;
@@ -1666,7 +1665,7 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
join_and_req,
required_outer,
joinrel,
- 0);
+ NULL);
/* We only want ones that aren't movable to lower levels */
dropped_ecs = NIL;
foreach(lc, eclauses)
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 5b9db7733d..d9e1623274 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -104,6 +104,8 @@ extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
extern void join_search_one_level(PlannerInfo *root, int level);
extern RelOptInfo *make_join_rel(PlannerInfo *root,
RelOptInfo *rel1, RelOptInfo *rel2);
+extern Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids,
+ SpecialJoinInfo *sjinfo);
extern bool have_join_order_restriction(PlannerInfo *root,
RelOptInfo *rel1, RelOptInfo *rel2);
extern bool have_dangerous_phv(PlannerInfo *root,
@@ -150,7 +152,7 @@ extern List *generate_join_implied_equalities(PlannerInfo *root,
Relids join_relids,
Relids outer_relids,
RelOptInfo *inner_rel,
- Index ojrelid);
+ SpecialJoinInfo *sjinfo);
extern List *generate_join_implied_equalities_for_ecs(PlannerInfo *root,
List *eclasses,
Relids join_relids,
--
2.31.1
From c6df0d6e55b3aed79ffd23670656a991e8a243c9 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Tue, 16 May 2023 19:33:01 -0400
Subject: [PATCH v6 3/5] Examine the transitive closure in
add_outer_joins_to_relids.
We also have to check outer joins that commute with commutators
of the one we just completed.
Richard Guo
Discussion: https://postgr.es/m/0b819232-4b50-f245-1c7d-c8c61bf41827@postgrespro.ru
---
src/backend/optimizer/path/joinrels.c | 29 +++++++++++++++++++++------
1 file changed, 23 insertions(+), 6 deletions(-)
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 262d3aec65..e8beaca196 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -804,12 +804,17 @@ add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids,
return bms_add_member(input_relids, sjinfo->ojrelid);
/*
- * Add the OJ relid unless this join has been pushed into the RHS of a
- * syntactically-lower left join per OJ identity 3. (If it has, then we
+ * We cannot add the OJ relid if this join has been pushed into the RHS of
+ * a syntactically-lower left join per OJ identity 3. (If it has, then we
* cannot claim that its outputs represent the final state of its RHS.)
+ * There will not be any higher OJs that can be added either, so we're
+ * done.
*/
- if (bms_is_subset(sjinfo->commute_below_l, input_relids))
- input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
+ if (!bms_is_subset(sjinfo->commute_below_l, input_relids))
+ return input_relids;
+
+ /* OK to add OJ's own relid */
+ input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
/*
* Contrariwise, if we are now forming the final result of such a commuted
@@ -818,6 +823,7 @@ add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids,
*/
if (sjinfo->commute_above_l)
{
+ Relids commute_above_rels = bms_copy(sjinfo->commute_above_l);
ListCell *lc;
/*
@@ -835,15 +841,26 @@ add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids,
othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT)
continue; /* definitely not interesting */
- if (othersj->commute_below_l == NULL)
- continue; /* was never a candidate to be pushed down */
+ if (!bms_is_member(othersj->ojrelid, commute_above_rels))
+ continue;
/* Add it if not already present but conditions now satisfied */
if (!bms_is_member(othersj->ojrelid, input_relids) &&
bms_is_subset(othersj->min_lefthand, input_relids) &&
bms_is_subset(othersj->min_righthand, input_relids) &&
bms_is_subset(othersj->commute_below_l, input_relids))
+ {
input_relids = bms_add_member(input_relids, othersj->ojrelid);
+
+ /*
+ * We must also check any joins that othersj potentially
+ * commutes with. They likewise must appear later in
+ * join_info_list than othersj itself, so we can visit them
+ * later in this loop.
+ */
+ commute_above_rels = bms_add_members(commute_above_rels,
+ othersj->commute_above_l);
+ }
}
}
--
2.31.1
From cc1178cfe3302034bfe20e58de0766622487aa77 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Tue, 16 May 2023 22:44:11 -0400
Subject: [PATCH v6 4/5] Fix additions of nullingrels to joinrels' output
targetlists.
Don't mark Vars and PHVs prematurely in build_joinrel_tlist,
and consider the transitive closure of previously-pushed-down
outer joins to see if additional marking is needed.
Richard Guo
Discussion: https://postgr.es/m/0b819232-4b50-f245-1c7d-c8c61bf41827@postgrespro.ru
---
src/backend/optimizer/util/relnode.c | 60 ++++++++++++++++++++++++----
1 file changed, 52 insertions(+), 8 deletions(-)
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 0d849d9494..e6d2d7a353 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -42,6 +42,7 @@ typedef struct JoinHashEntry
static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *input_rel,
+ Relids pushed_down_ojrelids,
SpecialJoinInfo *sjinfo,
bool can_null);
static List *build_joinrel_restrictlist(PlannerInfo *root,
@@ -649,6 +650,7 @@ build_join_rel(PlannerInfo *root,
{
RelOptInfo *joinrel;
List *restrictlist;
+ Relids pushed_down_ojrelids;
/* This function should be used only for join between parents. */
Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel));
@@ -757,9 +759,13 @@ build_join_rel(PlannerInfo *root,
* and inner rels we first try to build it from. But the contents should
* be the same regardless.
*/
- build_joinrel_tlist(root, joinrel, outer_rel, sjinfo,
+ pushed_down_ojrelids = bms_difference(joinrel->relids,
+ bms_union(outer_rel->relids,
+ inner_rel->relids));
+ pushed_down_ojrelids = bms_del_member(pushed_down_ojrelids, sjinfo->ojrelid);
+ build_joinrel_tlist(root, joinrel, outer_rel, pushed_down_ojrelids, sjinfo,
(sjinfo->jointype == JOIN_FULL));
- build_joinrel_tlist(root, joinrel, inner_rel, sjinfo,
+ build_joinrel_tlist(root, joinrel, inner_rel, pushed_down_ojrelids, sjinfo,
(sjinfo->jointype != JOIN_INNER));
add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel, sjinfo);
@@ -1046,17 +1052,24 @@ min_join_parameterization(PlannerInfo *root,
* identity 3 (see optimizer/README). We must take steps to ensure that
* the output Vars have the same nulling bitmaps that they would if the
* two joins had been done in syntactic order; else they won't match Vars
- * appearing higher in the query tree. We need to do two things:
+ * appearing higher in the query tree. We need to do three things:
*
- * First, we add the outer join's relid to the nulling bitmap only if the Var
- * or PHV actually comes from within the syntactically nullable side(s) of the
- * outer join. This takes care of the possibility that we have transformed
+ * First, we add the outer join's relid to the nulling bitmap only if the
+ * outer join has been completely performed and the Var or PHV actually
+ * comes from within the syntactically nullable side(s) of the outer join.
+ * This takes care of the possibility that we have transformed
* (A leftjoin B on (Pab)) leftjoin C on (Pbc)
* to
* A leftjoin (B leftjoin C on (Pbc)) on (Pab)
- * Here the now-upper A/B join must not mark C columns as nulled by itself.
+ * Here the pushed-down B/C join cannot mark C columns as nulled yet,
+ * while the now-upper A/B join must not mark C columns as nulled by itself.
*
- * Second, any relid in sjinfo->commute_above_r that is already part of
+ * Second, perform the same operation for each outer-join relid listed in
+ * pushed_down_ojrelids (which, in this example, would be "C" when we are
+ * at the now-upper A/B join). This allows the now-upper join to complete
+ * the marking of "C" Vars that now have fully valid values.
+ *
+ * Third, any relid in sjinfo->commute_above_r that is already part of
* the joinrel is added to the nulling bitmaps of nullable Vars and PHVs.
* This takes care of the reverse case where we implement
* A leftjoin (B leftjoin C on (Pbc)) on (Pab)
@@ -1069,6 +1082,7 @@ min_join_parameterization(PlannerInfo *root,
static void
build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *input_rel,
+ Relids pushed_down_ojrelids,
SpecialJoinInfo *sjinfo,
bool can_null)
{
@@ -1100,11 +1114,26 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
phv = copyObject(phv);
/* See comments above to understand this logic */
if (sjinfo->ojrelid != 0 &&
+ bms_is_member(sjinfo->ojrelid, relids) &&
(bms_is_subset(phv->phrels, sjinfo->syn_righthand) ||
(sjinfo->jointype == JOIN_FULL &&
bms_is_subset(phv->phrels, sjinfo->syn_lefthand))))
phv->phnullingrels = bms_add_member(phv->phnullingrels,
sjinfo->ojrelid);
+ if (pushed_down_ojrelids)
+ {
+ ListCell *lc;
+
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
+
+ if (bms_is_member(othersj->ojrelid, pushed_down_ojrelids) &&
+ bms_is_subset(phv->phrels, othersj->syn_righthand))
+ phv->phnullingrels = bms_add_member(phv->phnullingrels,
+ othersj->ojrelid);
+ }
+ }
phv->phnullingrels =
bms_join(phv->phnullingrels,
bms_intersect(sjinfo->commute_above_r,
@@ -1165,11 +1194,26 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
var = copyObject(var);
/* See comments above to understand this logic */
if (sjinfo->ojrelid != 0 &&
+ bms_is_member(sjinfo->ojrelid, relids) &&
(bms_is_member(var->varno, sjinfo->syn_righthand) ||
(sjinfo->jointype == JOIN_FULL &&
bms_is_member(var->varno, sjinfo->syn_lefthand))))
var->varnullingrels = bms_add_member(var->varnullingrels,
sjinfo->ojrelid);
+ if (pushed_down_ojrelids)
+ {
+ ListCell *lc;
+
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
+
+ if (bms_is_member(othersj->ojrelid, pushed_down_ojrelids) &&
+ bms_is_member(var->varno, othersj->syn_righthand))
+ var->varnullingrels = bms_add_member(var->varnullingrels,
+ othersj->ojrelid);
+ }
+ }
var->varnullingrels =
bms_join(var->varnullingrels,
bms_intersect(sjinfo->commute_above_r,
--
2.31.1
From 53706ae32f84c70821932cf8d4a796df2ba6a3c8 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Tue, 16 May 2023 22:45:19 -0400
Subject: [PATCH v6 5/5] Add test cases for new join planning logic.
Discussion: https://postgr.es/m/0b819232-4b50-f245-1c7d-c8c61bf41827@postgrespro.ru
---
src/test/regress/expected/join.out | 143 +++++++++++++++++++++++++++++
src/test/regress/sql/join.sql | 47 ++++++++++
2 files changed, 190 insertions(+)
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index b5f440e43e..9bafadde66 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2357,6 +2357,149 @@ where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
----+----+----------+----------
(0 rows)
+--
+-- checks for correct handling of quals in multiway outer joins
+--
+explain (costs off)
+select t1.f1
+from int4_tbl t1, int4_tbl t2
+ left join int4_tbl t3 on t3.f1 > 0
+ left join int4_tbl t4 on t3.f1 > 1
+where t4.f1 is null;
+ QUERY PLAN
+-------------------------------------------------------
+ Nested Loop
+ -> Nested Loop Left Join
+ Filter: (t4.f1 IS NULL)
+ -> Seq Scan on int4_tbl t2
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (t3.f1 > 1)
+ -> Seq Scan on int4_tbl t3
+ Filter: (f1 > 0)
+ -> Materialize
+ -> Seq Scan on int4_tbl t4
+ -> Seq Scan on int4_tbl t1
+(12 rows)
+
+select t1.f1
+from int4_tbl t1, int4_tbl t2
+ left join int4_tbl t3 on t3.f1 > 0
+ left join int4_tbl t4 on t3.f1 > 1
+where t4.f1 is null;
+ f1
+----
+(0 rows)
+
+explain (costs off)
+select *
+from int4_tbl t1 left join int4_tbl t2 on true
+ left join int4_tbl t3 on t2.f1 > 0
+ left join int4_tbl t4 on t3.f1 > 0;
+ QUERY PLAN
+-------------------------------------------------------
+ Nested Loop Left Join
+ -> Seq Scan on int4_tbl t1
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (t3.f1 > 0)
+ -> Nested Loop Left Join
+ Join Filter: (t2.f1 > 0)
+ -> Seq Scan on int4_tbl t2
+ -> Materialize
+ -> Seq Scan on int4_tbl t3
+ -> Materialize
+ -> Seq Scan on int4_tbl t4
+(12 rows)
+
+explain (costs off)
+select * from onek t1
+ left join onek t2 on t1.unique1 = t2.unique1
+ left join onek t3 on t2.unique1 != t3.unique1
+ left join onek t4 on t3.unique1 = t4.unique1;
+ QUERY PLAN
+----------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: (t2.unique1 <> t3.unique1)
+ -> Hash Left Join
+ Hash Cond: (t1.unique1 = t2.unique1)
+ -> Seq Scan on onek t1
+ -> Hash
+ -> Seq Scan on onek t2
+ -> Materialize
+ -> Hash Left Join
+ Hash Cond: (t3.unique1 = t4.unique1)
+ -> Seq Scan on onek t3
+ -> Hash
+ -> Seq Scan on onek t4
+(13 rows)
+
+explain (costs off)
+select * from int4_tbl t1
+ left join (select now() from int4_tbl t2
+ left join int4_tbl t3 on t2.f1 = t3.f1
+ left join int4_tbl t4 on t3.f1 = t4.f1) s on true
+ inner join int4_tbl t5 on true;
+ QUERY PLAN
+-------------------------------------------------------------
+ Nested Loop
+ -> Nested Loop Left Join
+ -> Seq Scan on int4_tbl t1
+ -> Materialize
+ -> Hash Left Join
+ Hash Cond: (t3.f1 = t4.f1)
+ -> Hash Left Join
+ Hash Cond: (t2.f1 = t3.f1)
+ -> Seq Scan on int4_tbl t2
+ -> Hash
+ -> Seq Scan on int4_tbl t3
+ -> Hash
+ -> Seq Scan on int4_tbl t4
+ -> Materialize
+ -> Seq Scan on int4_tbl t5
+(15 rows)
+
+explain (costs off)
+select * from int4_tbl t1
+ left join int4_tbl t2 on true
+ left join int4_tbl t3 on true
+ left join int4_tbl t4 on t2.f1 = t3.f1;
+ QUERY PLAN
+-------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: (t2.f1 = t3.f1)
+ -> Nested Loop Left Join
+ -> Nested Loop Left Join
+ -> Seq Scan on int4_tbl t1
+ -> Materialize
+ -> Seq Scan on int4_tbl t2
+ -> Materialize
+ -> Seq Scan on int4_tbl t3
+ -> Materialize
+ -> Seq Scan on int4_tbl t4
+(11 rows)
+
+explain (costs off)
+select * from int4_tbl t1
+ left join int4_tbl t2 on true
+ left join int4_tbl t3 on t2.f1 = t3.f1
+ left join int4_tbl t4 on t3.f1 != t4.f1;
+ QUERY PLAN
+-------------------------------------------------------
+ Nested Loop Left Join
+ -> Seq Scan on int4_tbl t1
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (t3.f1 <> t4.f1)
+ -> Hash Left Join
+ Hash Cond: (t2.f1 = t3.f1)
+ -> Seq Scan on int4_tbl t2
+ -> Hash
+ -> Seq Scan on int4_tbl t3
+ -> Materialize
+ -> Seq Scan on int4_tbl t4
+(12 rows)
+
--
-- check a case where we formerly got confused by conflicting sort orders
-- in redundant merge join path keys
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 437934e80b..a44234b0af 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -441,6 +441,53 @@ select a.f1, b.f1, t.thousand, t.tenthous from
(select sum(f1) as f1 from int4_tbl i4b) b
where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
+--
+-- checks for correct handling of quals in multiway outer joins
+--
+explain (costs off)
+select t1.f1
+from int4_tbl t1, int4_tbl t2
+ left join int4_tbl t3 on t3.f1 > 0
+ left join int4_tbl t4 on t3.f1 > 1
+where t4.f1 is null;
+
+select t1.f1
+from int4_tbl t1, int4_tbl t2
+ left join int4_tbl t3 on t3.f1 > 0
+ left join int4_tbl t4 on t3.f1 > 1
+where t4.f1 is null;
+
+explain (costs off)
+select *
+from int4_tbl t1 left join int4_tbl t2 on true
+ left join int4_tbl t3 on t2.f1 > 0
+ left join int4_tbl t4 on t3.f1 > 0;
+
+explain (costs off)
+select * from onek t1
+ left join onek t2 on t1.unique1 = t2.unique1
+ left join onek t3 on t2.unique1 != t3.unique1
+ left join onek t4 on t3.unique1 = t4.unique1;
+
+explain (costs off)
+select * from int4_tbl t1
+ left join (select now() from int4_tbl t2
+ left join int4_tbl t3 on t2.f1 = t3.f1
+ left join int4_tbl t4 on t3.f1 = t4.f1) s on true
+ inner join int4_tbl t5 on true;
+
+explain (costs off)
+select * from int4_tbl t1
+ left join int4_tbl t2 on true
+ left join int4_tbl t3 on true
+ left join int4_tbl t4 on t2.f1 = t3.f1;
+
+explain (costs off)
+select * from int4_tbl t1
+ left join int4_tbl t2 on true
+ left join int4_tbl t3 on t2.f1 = t3.f1
+ left join int4_tbl t4 on t3.f1 != t4.f1;
+
--
-- check a case where we formerly got confused by conflicting sort orders
-- in redundant merge join path keys
--
2.31.1
pgsql-bugs by date: