Re: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware) - Mailing list pgsql-bugs

I see that what you've been doing here is basically trying to rescue my
previous patch attempt.  I'm not in love with that approach anymore.
I think a better fix is to do what I suggested a bit upthread: forcibly
mark upper "C" Vars with both joins in varnullingrels, so that the
planner is always working with upper quals that look like they'd come
from input written according to the second form of the identity.
Here's a patch series that does it that way.

Although this passes check-world for me, there are some loose ends
that could use review:

* Does update_commutable_vars() update everything it needs to?
I modeled it on prepjointree's perform_pullup_replace_vars(), but
since this is happening later during planning there are additional
derived data structures it needs to update.  Did I miss any?
Also, is it really necessary to update parse->targetList, or would
updating root->processed_tlist be sufficient at this point?

* As implemented, we'll invoke update_commutable_vars() once per
commutable pair of joins, assuming that they are written in the
first form of identity 3 (which'd be the common case).  Is that
costly enough to justify inventing some way to combine the updates
for all such pairs into one querytree traversal?

* I changed the API of add_nulling_relids() so that it could support
updating an RTE_SUBQUERY query.  This breaks the possibility of applying
it to the whole main Query (it would make the wrong choice of initial
levelsup), but we never do that.  Would it be better to invent an
alternate entry point so that both cases could be supported?  Should
remove_nulling_relids be changed similarly?

Also, while checking the test cases shown upthread, I was interested to
notice that this code actually chooses a different join order in some
cases.  For the example at [1], v15 does

 Nested Loop Left Join  (cost=0.00..4.46 rows=16 width=4)
   ->  Seq Scan on t1  (cost=0.00..1.02 rows=2 width=1)
   ->  Materialize  (cost=0.00..3.26 rows=8 width=3)
         ->  Nested Loop Left Join  (cost=0.00..3.22 rows=8 width=3)
               Join Filter: t3.x
               ->  Nested Loop Left Join  (cost=0.00..2.09 rows=4 width=2)
                     Join Filter: t2.x
                     ->  Seq Scan on t2  (cost=0.00..1.02 rows=2 width=1)
                     ->  Materialize  (cost=0.00..1.03 rows=2 width=1)
                           ->  Seq Scan on t3  (cost=0.00..1.02 rows=2 width=1)
               ->  Materialize  (cost=0.00..1.03 rows=2 width=1)
                     ->  Seq Scan on t4  (cost=0.00..1.02 rows=2 width=1)

but with this patch we do

 Nested Loop Left Join  (cost=0.00..4.45 rows=16 width=4)
   Join Filter: t3.x
   ->  Nested Loop Left Join  (cost=0.00..3.22 rows=8 width=3)
         ->  Seq Scan on t1  (cost=0.00..1.02 rows=2 width=1)
         ->  Materialize  (cost=0.00..2.11 rows=4 width=2)
               ->  Nested Loop Left Join  (cost=0.00..2.09 rows=4 width=2)
                     Join Filter: t2.x
                     ->  Seq Scan on t2  (cost=0.00..1.02 rows=2 width=1)
                     ->  Materialize  (cost=0.00..1.03 rows=2 width=1)
                           ->  Seq Scan on t3  (cost=0.00..1.02 rows=2 width=1)
   ->  Materialize  (cost=0.00..1.03 rows=2 width=1)
         ->  Seq Scan on t4  (cost=0.00..1.02 rows=2 width=1)

This is correct AFAICS, and it's slightly cheaper, so an optimistic
conclusion would be that we're making a cost-based decision to use a plan
shape that the old code could not find for some reason.  But these costs
are pretty close, within the "fuzz factor", so this might be a random
effect.  It might be interesting to see if inserting unequal amounts
of data in the tables would drive the costs further apart, allowing
us to say that this code really does beat v15 in terms of planning
flexibility.

            regards, tom lane

[1] https://www.postgresql.org/message-id/CAMbWs4-_KdVEJ62o6KbtA%2B_KJnQa7WZCc48VsPQ9in6TSN0Kxg%40mail.gmail.com

From 0831d57c1b29c63094b93a4d458ccee7e53575cc Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Fri, 12 May 2023 12:31:55 -0400
Subject: [PATCH v4 1/2] Split RestrictInfo.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 c7265746d77679a37a36a0658d7f55cc2583dadf Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Fri, 12 May 2023 12:52:53 -0400
Subject: [PATCH v4 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.

Discussion: https://postgr.es/m/0b819232-4b50-f245-1c7d-c8c61bf41827@postgrespro.ru
---
 src/backend/optimizer/README           |  16 ++
 src/backend/optimizer/plan/initsplan.c | 241 ++++++++++++++++++++++++-
 src/backend/optimizer/util/relnode.c   |  58 +++---
 src/backend/rewrite/rewriteManip.c     |   9 +-
 src/test/regress/expected/join.out     |  34 ++++
 src/test/regress/sql/join.sql          |  16 ++
 6 files changed, 339 insertions(+), 35 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..9d72437c6a 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,12 @@ 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,
+                                   SpecialJoinInfo *otherinfo);
+static void update_commutable_vars_in_jointree(PlannerInfo *root,
+                                               Node *jtnode,
+                                               SpecialJoinInfo *sjinfo,
+                                               Bitmapset *added_relids);
 static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
                                   List *clause);
 static void deconstruct_distribute_oj_quals(PlannerInfo *root,
@@ -1655,7 +1662,10 @@ make_outerjoininfo(PlannerInfo *root,
     /* Anything left? */
     if (commute_below_l || commute_below_r)
     {
-        /* Yup, so we must update the derived data in the SpecialJoinInfos */
+        /*
+         * Yup, so we must update the derived data in the SpecialJoinInfos,
+         * and adjust upper Vars if needed.
+         */
         sjinfo->commute_below_l = commute_below_l;
         sjinfo->commute_below_r = commute_below_r;
         foreach(l, root->join_info_list)
@@ -1663,17 +1673,246 @@ make_outerjoininfo(PlannerInfo *root,
             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);
+                update_commutable_vars(root, sjinfo, otherinfo);
+            }
             else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
+            {
                 otherinfo->commute_above_r =
                     bms_add_member(otherinfo->commute_above_r, ojrelid);
+                /* no need to change upper Vars in this case */
+            }
         }
     }

     return sjinfo;
 }

+/*
+ * update_commutable_vars
+ *      Mark Vars above a commutable pair of outer joins with both OJs' 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.
+ *
+ * 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 B/C join
+ * otherinfo: SpecialJoinInfo for the syntactically-lower A/B join
+ * sjinfo is not yet part of root->join_info_list, but otherinfo is
+ */
+static void
+update_commutable_vars(PlannerInfo *root, SpecialJoinInfo *sjinfo,
+                       SpecialJoinInfo *otherinfo)
+{
+    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 otherinfo->ojrelid to nullingrels of
+     * anything referencing the upper join's min RHS.
+     */
+    target_relids = sjinfo->min_righthand;
+    Assert(otherinfo->ojrelid != 0);
+    added_relids = bms_make_singleton(otherinfo->ojrelid);
+
+    /*
+     * 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, added_relids);
+    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 *added_relids)
+{
+    Bitmapset  *target_relids = sjinfo->min_righthand;
+
+    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, added_relids);
+        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, added_relids);
+        update_commutable_vars_in_jointree(root, j->rarg, sjinfo, added_relids);
+        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
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..76d4d13e47 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 *
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