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 | 2489296.1684195396@sss.pgh.pa.us Whole thread Raw |
| In response to | Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware) (Richard Guo <guofenglinux@gmail.com>) |
| Responses |
Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware)
(Richard Guo <guofenglinux@gmail.com>)
|
| List | pgsql-bugs |
Richard Guo <guofenglinux@gmail.com> writes:
> On Sat, May 13, 2023 at 1:25 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Here's a patch series that does it that way.
> I explored this approach before and found that there are several
> problems with it that we need to resolve to make it work [1]. I
> reviewed the patches here and it seems that the second problem still
> exists. Quote it here.
Yeah, I realized over the weekend that I'd forgotten to update
deconstruct_distribute_oj_quals, and that the patch was missing some
potential join orders. Notably, the case that I thought was a performance
improvement turned out to be a mirage. It appears that the reason the
planner doesn't find the lowest-cost plan there is that it's following
the heuristic that it should avoid applying clause-free joins when
possible, so in that case it wants to put off the join to t1 as long
as possible. The bug forced it to make that join earlier which turned
out to be good. (I suppose this calls that whole heuristic into question;
but a few days before beta is no time to start revisiting heuristics
we've used for decades.)
> Also, it seems that PHVs in outer join's target list are not handled
> correctly, check the query below which causes assertion failure in
> search_indexed_tlist_for_phv.
Good catch! I think the problem here is that add_nulling_relids() is
being too aggressive: it's adding a nullingrel to a PHV when that's
nonsensical because the PHV is required to be computed above that join.
I fixed it with
- bms_overlap(phv->phrels, context->target_relids))
+ bms_is_subset(phv->phrels, context->target_relids))
which I think is sufficient, though if it proves not to be maybe we could
instead remove phv->phrels from the updated phnullingrels.
> BTW, there is a typo in the 0001's subject. It should be
> SpecialJoinInfo.commute_below rather than RestrictInfo.commute_below.
D'oh. Here's a patchset with these issues addressed.
regards, tom lane
From 0dcfda62dcf59fe70e2448d2b44d2b253a848bae Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Mon, 15 May 2023 19:24:57 -0400
Subject: [PATCH v5 1/2] 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 103356580ef248605fa7ce1c42a30995027115b7 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Mon, 15 May 2023 19:52:06 -0400
Subject: [PATCH v5 2/2] Fix mishandling of quals above a commuted pair of
outer joins.
If the planner applied outer join identity 3 in the forward direction,
it was possible for higher qual clauses referencing the "C" relation
to drop down to the B/C join (below the now-upper A/B join). This
gave the wrong answers, since values that would become NULL after
applying the A/B join might not be NULL at that point.
There is no hazard if the original input is written in the second
form of the identity, because then upper C Vars will be marked as
nullable by both joins so we'll make correct qual placement decisions
whether we commute the joins or not. Hence, the best fix seems to
be to forcibly mark upper C Vars as nullable by both joins once we
detect that they are potentially commutable.
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 | 16 +
src/backend/optimizer/plan/initsplan.c | 482 ++++++++++++++++++-------
src/backend/optimizer/util/relnode.c | 58 ++-
src/backend/rewrite/rewriteManip.c | 13 +-
src/test/regress/expected/join.out | 34 ++
src/test/regress/sql/join.sql | 16 +
6 files changed, 458 insertions(+), 161 deletions(-)
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index 227278eb6c..f41b368c1c 100644
--- a/src/backend/optimizer/README
+++ b/src/backend/optimizer/README
@@ -507,6 +507,22 @@ 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. There is no danger if the original input was
+in the second form, since then upper C Vars will be marked with the RT
+indexes of both joins, and the normal qual placement rules will ensure
+that quals are placed appropriately. We handle this problem by forcibly
+marking upper C Vars with both RT indexes when we detect that we have a
+commutable pair of joins that were initially written in the first form.
+
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/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 5cbb7b9a86..4cb7bb07ad 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -31,6 +31,7 @@
#include "optimizer/prep.h"
#include "optimizer/restrictinfo.h"
#include "parser/analyze.h"
+#include "parser/parsetree.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"
#include "utils/typcache.h"
@@ -97,6 +98,10 @@ static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
Relids inner_join_rels,
JoinType jointype, Index ojrelid,
List *clause);
+static void update_commutable_vars(PlannerInfo *root, SpecialJoinInfo *sjinfo);
+static void update_commutable_vars_in_jointree(PlannerInfo *root,
+ Node *jtnode,
+ SpecialJoinInfo *sjinfo);
static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
List *clause);
static void deconstruct_distribute_oj_quals(PlannerInfo *root,
@@ -1350,6 +1355,7 @@ make_outerjoininfo(PlannerInfo *root,
{
SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
Relids clause_relids;
+ Relids clause_baserelids;
Relids strict_relids;
Relids min_lefthand;
Relids min_righthand;
@@ -1419,6 +1425,18 @@ make_outerjoininfo(PlannerInfo *root,
*/
clause_relids = pull_varnos(root, (Node *) clause);
+ /*
+ * Because the clause may already have been modified by a lower-level
+ * invocation of update_commutable_vars(), it may contain nullingrel
+ * references to joins that are syntactically below this one and that
+ * we've previously determined to be commutable with others below this
+ * one. If we test the full clause_relids set against lower OJs'
+ * syn_lefthand or syn_righthand below, we may decide that outer join
+ * identity 3 doesn't apply in cases where it does. As a slightly hacky
+ * way around that, consider only baserels in those checks.
+ */
+ clause_baserelids = bms_intersect(clause_relids, root->all_baserels);
+
/*
* For which relids is the clause strict, ie, it cannot succeed if the
* rel's columns are all NULL?
@@ -1537,13 +1555,18 @@ make_outerjoininfo(PlannerInfo *root,
else if (jointype == JOIN_LEFT &&
otherinfo->jointype == JOIN_LEFT &&
bms_overlap(strict_relids, otherinfo->min_righthand) &&
- !bms_overlap(clause_relids, otherinfo->syn_lefthand))
+ !bms_overlap(clause_baserelids, otherinfo->syn_lefthand))
{
/* Identity 3 applies, so remove the ordering restriction */
min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid);
/* Record the (still tentative) commutability relationship */
- commute_below_l =
- bms_add_member(commute_below_l, otherinfo->ojrelid);
+ commute_below_l = bms_add_member(commute_below_l,
+ otherinfo->ojrelid);
+ /* We can commute with anything the lower OJ commutes with */
+ min_lefthand = bms_del_members(min_lefthand,
+ otherinfo->commute_below_l);
+ commute_below_l = bms_add_members(commute_below_l,
+ otherinfo->commute_below_l);
}
}
@@ -1567,7 +1590,7 @@ make_outerjoininfo(PlannerInfo *root,
*/
if (bms_overlap(right_rels, otherinfo->syn_righthand))
{
- if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
+ if (bms_overlap(clause_baserelids, otherinfo->syn_righthand) ||
!bms_overlap(clause_relids, otherinfo->min_lefthand) ||
have_unsafe_phvs ||
jointype == JOIN_SEMI ||
@@ -1669,11 +1692,237 @@ make_outerjoininfo(PlannerInfo *root,
otherinfo->commute_above_r =
bms_add_member(otherinfo->commute_above_r, ojrelid);
}
+ /* Adjust upper Vars if needed */
+ if (commute_below_l)
+ update_commutable_vars(root, sjinfo);
}
return sjinfo;
}
+/*
+ * update_commutable_vars
+ * Mark Vars above a commutable nest of outer joins with all their relids
+ *
+ * We have identified a pair of outer joins that are commutable according to
+ * outer join identity 3, and were written in the first form of the identity:
+ * (A leftjoin B on (Pab)) leftjoin C on (Pbc)
+ * This means that any C Vars appearing above the two joins are marked with
+ * only the B/C join's relid in varnullingrels. Had the query been written
+ * according to the second form,
+ * A leftjoin (B leftjoin C on (Pbc)) on (Pab)
+ * then upper C vars would have both OJs' relids in their varnullingrels.
+ *
+ * Our task here is to mark such upper C Vars (and PlaceHolderVars) with
+ * the A/B join's relid too, so that they will look the same regardless of
+ * the query's syntactic form. One critical reason for doing this is that
+ * if we do commute to the second form, quals using these Vars must not be
+ * allowed to drop below the A/B join: the Vars might not yet be null in
+ * join rows where they should be null.
+ *
+ * Actually, the current join might reference several potential commutator
+ * joins in commute_below_l, but we can add them all to upper varnullingrels
+ * in one pass, since our policy is that Vars referencing such nests
+ * should have all those OJs' relids in varnullingrels.
+ *
+ * Because this is invoked during a recursive scan of the jointree, we cannot
+ * mutate the jointree's structure (compare perform_pullup_replace_vars() in
+ * prepjointree.c, which has a similar constraint). So we can't just let
+ * add_nulling_relids() loose on the whole tree; we have to be careful to
+ * apply it only to the qual subtrees. We can save a little bit of work
+ * by not descending into jointree sections we've already processed, since
+ * those could not contain references to the Vars of interest.
+ *
+ * sjinfo: just-completed SpecialJoinInfo for the syntactically-upper join
+ */
+static void
+update_commutable_vars(PlannerInfo *root, SpecialJoinInfo *sjinfo)
+{
+ Query *parse = root->parse;
+ Bitmapset *target_relids;
+ Bitmapset *added_relids;
+ ListCell *lc;
+
+ /*
+ * We can use add_nulling_relids() to do the grunt work within
+ * subexpressions. Tell it to add commute_below_l to nullingrels of
+ * anything referencing the upper join's min RHS.
+ */
+ target_relids = sjinfo->min_righthand;
+ added_relids = sjinfo->commute_below_l;
+ Assert(!bms_is_empty(added_relids)); /* else we shouldn't be here */
+
+ /*
+ * Update Vars appearing in the targetList, returningList, and other
+ * top-level structures.
+ */
+ parse->targetList = (List *)
+ add_nulling_relids((Node *) parse->targetList,
+ target_relids, added_relids);
+ parse->returningList = (List *)
+ add_nulling_relids((Node *) parse->returningList,
+ target_relids, added_relids);
+ root->processed_tlist = (List *)
+ add_nulling_relids((Node *) root->processed_tlist,
+ target_relids, added_relids);
+
+ foreach(lc, parse->windowClause)
+ {
+ WindowClause *wc = lfirst_node(WindowClause, lc);
+
+ if (wc->runCondition != NIL)
+ wc->runCondition = (List *)
+ add_nulling_relids((Node *) wc->runCondition,
+ target_relids, added_relids);
+ }
+ if (parse->onConflict)
+ {
+ parse->onConflict->onConflictSet = (List *)
+ add_nulling_relids((Node *) parse->onConflict->onConflictSet,
+ target_relids, added_relids);
+ parse->onConflict->onConflictWhere =
+ add_nulling_relids(parse->onConflict->onConflictWhere,
+ target_relids, added_relids);
+
+ /*
+ * We assume ON CONFLICT's arbiterElems, arbiterWhere, exclRelTlist
+ * can't contain any references to an outer join's result.
+ */
+ }
+ if (parse->mergeActionList)
+ {
+ foreach(lc, parse->mergeActionList)
+ {
+ MergeAction *action = lfirst(lc);
+
+ action->qual = add_nulling_relids(action->qual,
+ target_relids, added_relids);
+ action->targetList = (List *)
+ add_nulling_relids((Node *) action->targetList,
+ target_relids, added_relids);
+ }
+ }
+ update_commutable_vars_in_jointree(root, (Node *) parse->jointree, sjinfo);
+ Assert(parse->setOperations == NULL);
+ parse->havingQual = add_nulling_relids(parse->havingQual,
+ target_relids, added_relids);
+
+ /*
+ * Unlike perform_pullup_replace_vars(), we needn't process appendrels'
+ * translated_vars lists, because there won't be any join output vars
+ * there. We needn't process joinaliasvars lists either --- those are
+ * empty at this point, cf subquery_planner().
+ */
+}
+
+/*
+ * Helper routine for update_commutable_vars: do add_nulling_relids on every
+ * expression in the jointree, without changing the jointree structure itself.
+ * Ugly, but there's no other way...
+ */
+static void
+update_commutable_vars_in_jointree(PlannerInfo *root,
+ Node *jtnode,
+ SpecialJoinInfo *sjinfo)
+{
+ Bitmapset *target_relids = sjinfo->min_righthand;
+ Bitmapset *added_relids = sjinfo->commute_below_l;
+
+ if (jtnode == NULL)
+ return;
+ if (IsA(jtnode, RangeTblRef))
+ {
+ /*
+ * If the RangeTblRef refers to a LATERAL subquery, it might contain
+ * references to the target join, which we must update. We drive this
+ * from the jointree scan, rather than a scan of the rtable, so that
+ * we can avoid processing no-longer-referenced RTEs.
+ */
+ int varno = ((RangeTblRef *) jtnode)->rtindex;
+ RangeTblEntry *rte = rt_fetch(varno, root->parse->rtable);
+ RelOptInfo *rel;
+
+ if (rte->lateral)
+ {
+ /* Update sub-structure of the RTE */
+ switch (rte->rtekind)
+ {
+ case RTE_RELATION:
+ /* shouldn't be marked LATERAL unless tablesample */
+ Assert(rte->tablesample);
+ rte->tablesample = (TableSampleClause *)
+ add_nulling_relids((Node *) rte->tablesample,
+ target_relids, added_relids);
+ break;
+ case RTE_SUBQUERY:
+ /* this does the right thing, see add_nulling_relids */
+ rte->subquery = (Query *)
+ add_nulling_relids((Node *) rte->subquery,
+ target_relids, added_relids);
+ break;
+ case RTE_FUNCTION:
+ rte->functions = (List *)
+ add_nulling_relids((Node *) rte->functions,
+ target_relids, added_relids);
+ break;
+ case RTE_TABLEFUNC:
+ rte->tablefunc = (TableFunc *)
+ add_nulling_relids((Node *) rte->tablefunc,
+ target_relids, added_relids);
+ break;
+ case RTE_VALUES:
+ rte->values_lists = (List *)
+ add_nulling_relids((Node *) rte->values_lists,
+ target_relids, added_relids);
+ break;
+ case RTE_JOIN:
+ case RTE_CTE:
+ case RTE_NAMEDTUPLESTORE:
+ case RTE_RESULT:
+ /* these shouldn't be marked LATERAL */
+ Assert(false);
+ break;
+ }
+
+ /*
+ * We must also update the rel's lateral_vars list, since that's
+ * already been constructed.
+ */
+ rel = find_base_rel(root, varno);
+ rel->lateral_vars = (List *)
+ add_nulling_relids((Node *) rel->lateral_vars,
+ target_relids, added_relids);
+ }
+ }
+ else if (IsA(jtnode, FromExpr))
+ {
+ FromExpr *f = (FromExpr *) jtnode;
+ ListCell *l;
+
+ foreach(l, f->fromlist)
+ update_commutable_vars_in_jointree(root, lfirst(l), sjinfo);
+ f->quals = add_nulling_relids(f->quals, target_relids, added_relids);
+ }
+ else if (IsA(jtnode, JoinExpr))
+ {
+ JoinExpr *j = (JoinExpr *) jtnode;
+
+ /*
+ * We don't need to recurse into the children or quals of the upper
+ * commutable join.
+ */
+ if (j->rtindex == sjinfo->ojrelid)
+ return;
+
+ update_commutable_vars_in_jointree(root, j->larg, sjinfo);
+ update_commutable_vars_in_jointree(root, j->rarg, sjinfo);
+ j->quals = add_nulling_relids(j->quals, target_relids, added_relids);
+ }
+ else
+ elog(ERROR, "unrecognized node type: %d",
+ (int) nodeTag(jtnode));
+}
+
/*
* compute_semijoin_info
* Fill semijoin-related fields of a new SpecialJoinInfo
@@ -1883,36 +2132,46 @@ deconstruct_distribute_oj_quals(PlannerInfo *root,
* as-is.
*/
Assert(sjinfo->lhs_strict); /* else we shouldn't be here */
- if (sjinfo->commute_above_r || sjinfo->commute_below_l)
+ if (sjinfo->commute_below_l || sjinfo->commute_above_r)
{
- Relids joins_above;
Relids joins_below;
- Relids joins_so_far;
+ Relids joins_above;
List *quals;
+ Relids this_qualscope = qualscope;
+ Relids this_ojscope = ojscope;
int save_last_rinfo_serial;
- ListCell *lc;
/* Identify the outer joins this one commutes with */
- joins_above = sjinfo->commute_above_r;
joins_below = sjinfo->commute_below_l;
+ joins_above = sjinfo->commute_above_r;
/*
* Generate qual variants with different sets of nullingrels bits.
*
- * We only need bit-sets that correspond to the successively less
- * deeply syntactically-nested subsets of this join and its
- * commutators. That's true first because obviously only those forms
- * of the Vars and PHVs could appear elsewhere in the query, and
- * second because the outer join identities do not provide a way to
- * re-order such joins in a way that would require different marking.
- * (That is, while the current join may commute with several others,
- * none of those others can commute with each other.) To visit the
- * interesting joins in syntactic nesting order, we rely on the
- * jtitems list to be ordered that way.
+ * You might think we need all the possible combinations of
+ * nullingrels bits that can generated from this OJ and its
+ * commutators. However, because we have a policy that Vars appearing
+ * above a nest of commuting OJs bear all those OJs' nullingrel marks
+ * regardless of the order they are implemented in, we need at most
+ * three variants:
+ *
+ * We need the qual with all the nest's bits removed. This version
+ * applies if we choose to implement this OJ first (lowest).
+ *
+ * We need the qual with just the joins_below bits added, if that set
+ * isn't empty. This version applies when we've not chosen to commute
+ * this join with any of those joins (it doesn't matter what order
+ * they were done in).
+ *
+ * We need the qual with both the joins_below and joins_above bits
+ * added (but not, of course, this join's own bit), if joins_above
+ * isn't empty. This version applies when this join has been pushed
+ * up out of some other join's RHS to be applied after it.
*
- * We first strip out all the nullingrels bits corresponding to
- * commutating joins below this one, and then successively put them
- * back as we crawl up the join stack.
+ * Other possibilities are not needed because once a given join has
+ * been commuted out of the serial order "A leftjoin B on (Pab)
+ * leftjoin C on (Pbc) leftjoin D on (Pcd) ...", there is no longer
+ * any identity that would let it commute with remaining nest members.
*/
quals = jtitem->oj_joinclauses;
if (!bms_is_empty(joins_below))
@@ -1930,125 +2189,98 @@ deconstruct_distribute_oj_quals(PlannerInfo *root,
*/
save_last_rinfo_serial = root->last_rinfo_serial;
- joins_so_far = NULL;
- foreach(lc, jtitems)
- {
- JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc);
- SpecialJoinInfo *othersj = otherjtitem->sjinfo;
- bool below_sjinfo = false;
- bool above_sjinfo = false;
- Relids this_qualscope;
- Relids this_ojscope;
- bool allow_equivalence,
- has_clone,
- is_clone;
-
- if (othersj == NULL)
- continue; /* not an outer-join item, ignore */
-
- if (bms_is_member(othersj->ojrelid, joins_below))
- {
- /* othersj commutes with sjinfo from below left */
- below_sjinfo = true;
- }
- else if (othersj == sjinfo)
- {
- /* found our join in syntactic order */
- Assert(bms_equal(joins_so_far, joins_below));
- }
- else if (bms_is_member(othersj->ojrelid, joins_above))
- {
- /* othersj commutes with sjinfo from above */
- above_sjinfo = true;
- }
- else
- {
- /* othersj is not relevant, ignore */
- continue;
- }
+ /*
+ * We generate EquivalenceClasses only from the form of the quals
+ * without nullingrels bits set. An EC made from this version of the
+ * quals can be useful below the outer-join nest, whereas the version
+ * with nullingrels bits set would not be. We cannot generate ECs
+ * from more than one version, or we'll make nonsensical conclusions
+ * that Vars with nullingrels bits set are equal to their versions
+ * without. Fortunately, such ECs wouldn't be very useful anyway,
+ * because they'd equate values not observable outside the join nest.
+ * (See optimizer/README.)
+ *
+ * This form of the quals is also marked as has_clone but not
+ * is_clone.
+ */
+ distribute_quals_to_rels(root, quals,
+ jtitem,
+ sjinfo,
+ root->qual_security_level,
+ this_qualscope,
+ this_ojscope,
+ nonnullable_rels,
+ true, /* allow_equivalence */
+ true, /* has_clone */
+ false, /* is_clone */
+ NULL); /* no more postponement */
+ if (joins_below)
+ {
/* Reset serial counter for this version of the quals */
root->last_rinfo_serial = save_last_rinfo_serial;
/*
- * When we are looking at joins above sjinfo, we are envisioning
- * pushing sjinfo to above othersj, so add othersj's nulling bit
- * before distributing the quals. We should add it to Vars coming
- * from the current join's LHS: we want to transform the second
- * form of OJ identity 3 to the first form, in which Vars of
- * relation B will appear nulled by the syntactically-upper OJ
- * within the Pbc clause, but those of relation C will not. (In
- * the notation used by optimizer/README, we're converting a qual
- * of the form Pbc to Pb*c.)
+ * Add lower joins' relids to the qual. We should add them to
+ * Vars coming from the current join's LHS: we want to transform
+ * the second form of OJ identity 3 to the first form, in which
+ * Vars of relation B will appear nulled by the
+ * syntactically-upper OJ within the Pbc clause, but those of
+ * relation C will not. (In the notation used by
+ * optimizer/README, we're converting a qual of the form Pbc to
+ * Pb*c.)
*/
- if (above_sjinfo)
- quals = (List *)
- add_nulling_relids((Node *) quals,
- sjinfo->syn_lefthand,
- bms_make_singleton(othersj->ojrelid));
-
- /* Compute qualscope and ojscope for this join level */
- this_qualscope = bms_union(qualscope, joins_so_far);
- this_ojscope = bms_union(ojscope, joins_so_far);
- if (above_sjinfo)
- {
- /* othersj is not yet in joins_so_far, but we need it */
- this_qualscope = bms_add_member(this_qualscope,
- othersj->ojrelid);
- this_ojscope = bms_add_member(this_ojscope,
- othersj->ojrelid);
- /* sjinfo is in joins_so_far, and we don't want it */
- this_ojscope = bms_del_member(this_ojscope,
- sjinfo->ojrelid);
- }
+ quals = (List *)
+ add_nulling_relids((Node *) quals,
+ sjinfo->syn_lefthand,
+ joins_below);
- /*
- * We generate EquivalenceClasses only from the first form of the
- * quals, with the fewest nullingrels bits set. An EC made from
- * this version of the quals can be useful below the outer-join
- * nest, whereas versions with some nullingrels bits set would not
- * be. We cannot generate ECs from more than one version, or
- * we'll make nonsensical conclusions that Vars with nullingrels
- * bits set are equal to their versions without. Fortunately,
- * such ECs wouldn't be very useful anyway, because they'd equate
- * values not observable outside the join nest. (See
- * optimizer/README.)
- *
- * The first form of the quals is also the only one marked as
- * has_clone rather than is_clone.
- */
- allow_equivalence = (joins_so_far == NULL);
- has_clone = allow_equivalence;
- is_clone = !has_clone;
+ /* Compute qualscope and ojscope for this form */
+ this_qualscope = bms_union(this_qualscope, joins_below);
+ this_ojscope = bms_union(this_ojscope, joins_below);
distribute_quals_to_rels(root, quals,
- otherjtitem,
+ jtitem,
sjinfo,
root->qual_security_level,
this_qualscope,
- this_ojscope, nonnullable_rels,
- allow_equivalence,
- has_clone,
- is_clone,
+ this_ojscope,
+ nonnullable_rels,
+ false, /* allow_equivalence */
+ false, /* has_clone */
+ true, /* is_clone */
NULL); /* no more postponement */
+ }
+
+ if (joins_above)
+ {
+ /* Reset serial counter for this version of the quals */
+ root->last_rinfo_serial = save_last_rinfo_serial;
/*
- * Adjust qual nulling bits for next level up, if needed. We
- * don't want to put sjinfo's own bit in at all, and if we're
- * above sjinfo then we did it already. Here, we should mark all
- * Vars coming from the lower join's RHS. (Again, we are
- * converting a qual of the form Pbc to Pb*c, but now we are
- * putting back bits that were there in the parser output and were
- * temporarily stripped above.)
+ * Add upper joins' relids to the qual. As above, we should add
+ * them to Vars coming from the current join's LHS.
*/
- if (below_sjinfo)
- quals = (List *)
- add_nulling_relids((Node *) quals,
- othersj->syn_righthand,
- bms_make_singleton(othersj->ojrelid));
-
- /* ... and track joins processed so far */
- joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid);
+ quals = (List *)
+ add_nulling_relids((Node *) quals,
+ sjinfo->syn_lefthand,
+ joins_above);
+
+ /* Compute qualscope and ojscope for this form */
+ this_qualscope = bms_union(this_qualscope, joins_above);
+ this_ojscope = bms_union(this_ojscope, joins_above);
+
+ distribute_quals_to_rels(root, quals,
+ jtitem,
+ sjinfo,
+ root->qual_security_level,
+ this_qualscope,
+ this_ojscope,
+ nonnullable_rels,
+ false, /* allow_equivalence */
+ false, /* has_clone */
+ true, /* is_clone */
+ NULL); /* no more postponement */
}
}
else
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 68fd033595..73c1457e07 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -1039,33 +1039,29 @@ min_join_parameterization(PlannerInfo *root,
* of data that was cached at the baserel level by set_rel_width().
*
* Pass can_null as true if the join is an outer join that can null Vars
- * from this input relation. If so, we will (normally) add the join's relid
+ * from this input relation. If so, we will add the join's relid (if any)
* to the nulling bitmaps of Vars and PHVs bubbled up from the input.
*
* When forming an outer join's target list, special handling is needed
- * in case the outer join was commuted with another one per outer join
- * 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:
- *
- * 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
- * (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.
- *
- * Second, 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)
- * as
+ * in case the outer join can commute with another one per outer join
+ * identity 3 (see optimizer/README). We must ensure that the output Vars
+ * have nulling bitmaps matching what higher levels of the tree expect.
+ * We previously forced join-output Vars in the higher levels to have both
+ * joins' relids in their nulling bitmaps (see update_commutable_vars()).
+ * To match that outcome, any relid in sjinfo->commute_below_l that is already
+ * part of the joinrel is added to the nulling bitmaps of nullable Vars and
+ * PHVs. This takes care of the possibility that the join is written and
+ * implemented in the form
* (A leftjoin B on (Pab)) leftjoin C on (Pbc)
* The C columns emitted by the B/C join need to be shown as nulled by both
- * the B/C and A/B joins, even though they've not physically traversed the
- * A/B join.
+ * the B/C and A/B joins, even though they've not physically traversed the A/B
+ * join. Likewise, 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 case where we originally had
+ * A leftjoin (B leftjoin C on (Pbc)) on (Pab)
+ * but it's been transformed to the first form. (If we have implemented
+ * the joins in this second form, no additional work is needed, no matter
+ * which form was written originally.)
*/
static void
build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
@@ -1100,12 +1096,13 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
{
phv = copyObject(phv);
/* See comments above to understand this logic */
- if (sjinfo->ojrelid != 0 &&
- (bms_is_subset(phv->phrels, sjinfo->syn_righthand) ||
- (sjinfo->jointype == JOIN_FULL &&
- bms_is_subset(phv->phrels, sjinfo->syn_lefthand))))
+ if (sjinfo->ojrelid != 0)
phv->phnullingrels = bms_add_member(phv->phnullingrels,
sjinfo->ojrelid);
+ phv->phnullingrels =
+ bms_join(phv->phnullingrels,
+ bms_intersect(sjinfo->commute_below_l,
+ relids));
phv->phnullingrels =
bms_join(phv->phnullingrels,
bms_intersect(sjinfo->commute_above_r,
@@ -1165,12 +1162,13 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
{
var = copyObject(var);
/* See comments above to understand this logic */
- if (sjinfo->ojrelid != 0 &&
- (bms_is_member(var->varno, sjinfo->syn_righthand) ||
- (sjinfo->jointype == JOIN_FULL &&
- bms_is_member(var->varno, sjinfo->syn_lefthand))))
+ if (sjinfo->ojrelid != 0)
var->varnullingrels = bms_add_member(var->varnullingrels,
sjinfo->ojrelid);
+ var->varnullingrels =
+ bms_join(var->varnullingrels,
+ bms_intersect(sjinfo->commute_below_l,
+ relids));
var->varnullingrels =
bms_join(var->varnullingrels,
bms_intersect(sjinfo->commute_above_r,
diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c
index 52b3f77078..0d5f6ee24d 100644
--- a/src/backend/rewrite/rewriteManip.c
+++ b/src/backend/rewrite/rewriteManip.c
@@ -1129,6 +1129,10 @@ AddInvertedQual(Query *parsetree, Node *qual)
* add_nulling_relids() finds Vars and PlaceHolderVars that belong to any
* of the target_relids, and adds added_relids to their varnullingrels
* and phnullingrels fields.
+ *
+ * Note: unlike many of the other functions in this file, if this is invoked
+ * directly on a Query node, it will mutate contained Vars of level 1 not
+ * level 0. This is desirable for current uses.
*/
Node *
add_nulling_relids(Node *node,
@@ -1140,10 +1144,7 @@ add_nulling_relids(Node *node,
context.target_relids = target_relids;
context.added_relids = added_relids;
context.sublevels_up = 0;
- return query_or_expression_tree_mutator(node,
- add_nulling_relids_mutator,
- &context,
- 0);
+ return add_nulling_relids_mutator(node, &context);
}
static Node *
@@ -1175,7 +1176,7 @@ add_nulling_relids_mutator(Node *node,
PlaceHolderVar *phv = (PlaceHolderVar *) node;
if (phv->phlevelsup == context->sublevels_up &&
- bms_overlap(phv->phrels, context->target_relids))
+ bms_is_subset(phv->phrels, context->target_relids))
{
Relids newnullingrels = bms_union(phv->phnullingrels,
context->added_relids);
@@ -1261,7 +1262,7 @@ remove_nulling_relids_mutator(Node *node,
PlaceHolderVar *phv = (PlaceHolderVar *) node;
if (phv->phlevelsup == context->sublevels_up &&
- !bms_overlap(phv->phrels, context->except_relids))
+ !bms_is_subset(phv->phrels, context->except_relids))
{
/*
* Note: it might seem desirable to remove the PHV altogether if
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index b5f440e43e..39c57d5c59 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2357,6 +2357,40 @@ where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
----+----+----------+----------
(0 rows)
+--
+-- check for correct placement of non-strict qual in a multiway outer join
+--
+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)
+
--
-- 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..fc2ea35a4f 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -441,6 +441,22 @@ 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;
+--
+-- check for correct placement of non-strict qual in a multiway outer join
+--
+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;
+
--
-- 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: