Thread: Clause accidentally pushed down ( Possible bug in Making Vars outer-join aware)

Hi,
sqlancer benchmark raised an issue with pushing down clauses in LEFT 
JOINs. Example:

DROP TABLE IF EXISTS t1,t2,t3,t4 CASCADE;
CREATE TABLE t1 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t2 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t3 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t4 AS SELECT true AS x FROM generate_series(0,1) x;
ANALYZE;

EXPLAIN (ANALYZE, COSTS OFF)
SELECT ALL t1.x FROM t1, t2
   LEFT OUTER JOIN t3
   ON t3.x
     LEFT OUTER JOIN t4
     ON t3.x
WHERE t4.x ISNULL;

We should get zero tuples, right? But we have the explain:
Nested Loop (actual time=0.024..0.028 rows=4 loops=1)
...

REL_15_STABLE works correctly. As I remember, it could be induces by new 
machinery, introduced by the 'Making Vars outer-join aware' patch.

Sorry for flood, if you are working on that issue.

-- 
regards,
Andrey Lepikhov
Postgres Professional

Richard Guo <guofenglinux@gmail.com> writes:
> ISTM that for outer join identity 3, if we are given form
>     (A leftjoin B on (Pab)) leftjoin C on (Pbc)
> then references to C Vars in higher qual levels would be marked with the
> B/C join.  If we've transformed it to form
>     A leftjoin (B leftjoin C on (Pbc)) on (Pab)
> then references to C Vars in higher qual levels should be adjusted to
> include both B/C join and A/B join in their varnullingrels.

Hmm.  I remember having convinced myself that we didn't need to change
anything above the commuting OJs, but now I can't reconstruct the
reasoning :-(.

I wonder whether we could instead fix things by deeming that the result
of the pushed-down B/C join does not yet produce correct C* variables,
so that we won't allow conditions involving them to drop below the
pushed-up A/B join.  This would be a little bit messy in some places
because now we'd consider that the A/B join is adding two OJ relids
not just one to the output join relid set, while the B/C join is adding
no relids even though it must execute an outer join.  (But we already
have that notion for semijoins and some antijoins, so maybe it's fine.)

            regards, tom lane

On 23/2/2023 11:36, Richard Guo wrote:
> I've realized this hack is not correct :-(.  References to A Vars and B
> Vars in higher qual levels do not need this adjustment.  So this code
> change would add unnecessary relids for clauses that involve A Vars or B
> Vars but not C Vars, resulting them being placed at higher place than
> needed.
> 
> Maybe what we need is to add in commute_below_l (assuming it has been
> recorded in SpecialJoinInfo) rather than commute_below of outer joins
> mentioned within the clause?
Doing a comparison of pg15 and master initsplan.c I found that a clear 
and documented algorithm for delaying the application of a qual is lost 
or replaced with some commute_* fields.
It is not clear how we guarantee correct application delay of a qual. 
Which part of the code implements it now?

-- 
regards,
Andrey Lepikhov
Postgres Professional

On 27/2/2023 13:16, Richard Guo wrote:
> 
> On Mon, Feb 27, 2023 at 2:23 PM Andrey Lepikhov 
> <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.ru>> wrote:
> 
>     Doing a comparison of pg15 and master initsplan.c I found that a clear
>     and documented algorithm for delaying the application of a qual is lost
>     or replaced with some commute_* fields.
>     It is not clear how we guarantee correct application delay of a qual.
>     Which part of the code implements it now?
> 
> Do you mean function check_outerjoin_delay()?  Yes it has been removed
> in b448f1c8, since now we consider that outer joins listed in
> varnullingrels or phnullingrels are used in the clause, so that the
> clause would not be placed below outer joins that should null some of
> its vars.
I see. But these logics looks non-equivalent.
relnode.c::build_joinrel_tlist() adds relid into varnullingrels only in 
the case when the var exists in the target list. So, other joins, which 
don't have links to the var, don't get into the bitmapset too.

-- 
regards,
Andrey Lepikhov
Postgres Professional

Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> On 27/2/2023 13:16, Richard Guo wrote:
>> Do you mean function check_outerjoin_delay()?  Yes it has been removed
>> in b448f1c8, since now we consider that outer joins listed in
>> varnullingrels or phnullingrels are used in the clause, so that the
>> clause would not be placed below outer joins that should null some of
>> its vars.

> I see. But these logics looks non-equivalent.

They're not meant to be equivalent.  The new code should be more
flexible and more trustworthy --- in particular, there's nothing that
didn't suck about the old outerjoin_delayed mechanism.  Before we had
only a very ad-hoc model of where outer-join quals could be evaluated.
I've spent the last sixteen years living in fear that somebody would
find a bug in it that couldn't be fixed without making many plans
disastrously worse.  Now we have something that actually faithfully
represents where quals can be evaluated and why.

Admittedly the new stuff is having more teething pains than I'd hoped
for, but we'll work through it.  Most of the bugs are stemming from
the fact that we now need a rigorous representation of what is
happening when we commute outer joins per identity 3, and we're
finding out that we are not quite there yet.

            regards, tom lane

On 28/2/2023 00:02, Tom Lane wrote:
> Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
>> On 27/2/2023 13:16, Richard Guo wrote:
>>> Do you mean function check_outerjoin_delay()?  Yes it has been removed
>>> in b448f1c8, since now we consider that outer joins listed in
>>> varnullingrels or phnullingrels are used in the clause, so that the
>>> clause would not be placed below outer joins that should null some of
>>> its vars.
>> I see. But these logics looks non-equivalent.
> Admittedly the new stuff is having more teething pains than I'd hoped
> for, but we'll work through it.  Most of the bugs are stemming from
> the fact that we now need a rigorous representation of what is
> happening when we commute outer joins per identity 3, and we're
> finding out that we are not quite there yet.
Ok, maybe my language still not so fluent, as I think sometimes. In 
accordance to the example above:
1. varnullingrels contains relids of entries which can null the var. In 
our case it (correctly) contains t3 and OJ(t3,t4)
2. Syntactic scope of the clause correctly contains all relations and OJs
3. In the distribute_qual_to_rels I don't see a code which should 
disallow pushing down a clause from higher syntactic level into nullable 
side of OJ. Where is the logic which should limit the lowest level of 
the clause push down?

-- 
regards,
Andrey Lepikhov
Postgres Professional

Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> Ok, maybe my language still not so fluent, as I think sometimes. In 
> accordance to the example above:
> 1. varnullingrels contains relids of entries which can null the var. In 
> our case it (correctly) contains t3 and OJ(t3,t4)
> 2. Syntactic scope of the clause correctly contains all relations and OJs
> 3. In the distribute_qual_to_rels I don't see a code which should 
> disallow pushing down a clause from higher syntactic level into nullable 
> side of OJ. Where is the logic which should limit the lowest level of 
> the clause push down?

It's the same logic that prevents push-down to joins that lack a
relation you're trying to reference, namely the checks of
RestrictInfo.required_relids.  If a clause should be referring to the
possibly-nulled version of some variable, then its required_relids now
include the relid of the outer join that nulls that variable, so we
can't push it to below that outer join.

This is straightforward enough until you start applying outer join
identity 3:

3.    (A leftjoin B on (Pab)) leftjoin C on (Pbc)
    = A leftjoin (B leftjoin C on (Pbc)) on (Pab)
granting that Pbc is strict for B

Suppose that we are given a FROM clause in the first form and
that there's a non-strict WHERE clause referencing a column of C.
That clause should certainly see the nulled version of C, so if we
implement the join as written then we can apply the WHERE clause as
a filter condition (not join condition) on the join of A/B to C.
However, if we decide to implement the join according to the second
form of the identity, then the current code believes it can push
the WHERE clause down so that it's a filter on the join of B to C.
It's not quite obvious that that's wrong, but it is: we might see
C values that are non-null at this point but will become null after
application of the A/B join.  Then the WHERE clause gives misleading
answers, which is exactly what's going wrong in this example.

The way I'm proposing to fix this is to say that if the B/C join
is done first, then its output C columns do not yet satisfy the
nulling action of the syntactically-upper outer join, so we can't
yet apply clauses that need to see those outputs.  We can implement
that by not adding the outer join's relid to the joinrelids produced
by the B/C join: then clauses containing such Vars won't look like
they can be pushed down to that join.  Instead they'll get pushed
to the AB/C join, and to make that happen we'll have to add both
outer-join relids to the identifying relids of that join level.

BTW, there's no problem if we start from the second form of the
identity and transform to the first, because then any C references
above the join nest are already marked as requiring the nulling
actions of both of the joins, so they won't fall below the upper
join no matter which order we do the joins in.

So another way we could fix this is to run around and forcibly mark
all such Vars with the relids of both outer joins, thus producing
a parse tree that looks more like the second form of the identity.
However, we're pretty much committed already to keeping all Vars
marked according to the syntactic tree structure, so that solution
would require revisiting a lot of code (not to mention the cost of
mutating the parse tree like that).  I don't want to go that way
unless really forced into it.

I have a WIP patch that does it like this, and it fixes the presented
case; but it's not complete so it's still failing some existing
regression tests.  More later.

            regards, tom lane

I wrote:
> I have a WIP patch that does it like this, and it fixes the presented
> case; but it's not complete so it's still failing some existing
> regression tests.  More later.

Here's said patch.  Although this fixes the described problem and
passes check-world, I'm not totally happy with it yet: it feels
like the new add_outer_joins_to_relids() function is too expensive
to be doing every time we construct a join relation.  I wonder if
there is a way we can add more info to the SpecialJoinInfo data
structure to make it cheaper.  An obvious improvement is to store
commute_below_l explicitly instead of recomputing it over and over,
but that isn't going to move the needle all that far.  Is there a
way to not have to scan all the SpecialJoinInfos?

I may be worrying over nothing --- it's likely that the path
construction work that will happen after we make the join relation
RelOptInfo will swamp this cost anyway.  But it feels ugly.

Another thing I'm wondering about is whether this'd let us get
rid of RestrictInfo.is_pushed_down and RINFO_IS_PUSHED_DOWN.
I tried really hard to remove those in favor of checking to see
whether a qual clause's required_relids include the outer join
being formed, which seems like a much more principled way of
deciding whether it's a filter or join clause.  I couldn't get
that to work, but now I wonder if what I was running into was
really bugs associated with not understanding that we haven't
fully formed the lower outer join when we apply identity 3.

            regards, tom lane

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 011a0337da..64dfddea2a 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3367,7 +3367,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 d7cb11c851..be7865cc0a 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)
@@ -775,6 +774,102 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
     return joinrel;
 }

+/*
+ * XXX hack, if we need this we should probably be retaining commute_below_l
+ * as a field...
+ */
+static bool
+commute_below_l_is_subset(SpecialJoinInfo *sjinfo, Relids relids)
+{
+    if (sjinfo->commute_below == NULL)    /* easy case */
+        return true;
+    else
+    {
+        Relids        commute_below_l = bms_intersect(sjinfo->commute_below,
+                                                    sjinfo->syn_lefthand);
+        bool        result;
+
+        result = bms_is_subset(commute_below_l, relids);
+        bms_free(commute_below_l);
+        return result;
+    }
+}
+
+/*
+ * 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 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 (commute_below_l_is_subset(sjinfo, 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 == 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) &&
+                commute_below_l_is_subset(othersj, 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
@@ -1531,9 +1626,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 98cf3494e6..e4bb0847ce 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);
@@ -670,7 +673,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 9ad44a0508..13e568b414 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -872,8 +872,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);
@@ -1266,7 +1265,7 @@ build_joinrel_restrictlist(PlannerInfo *root,
                                                           joinrel->relids,
                                                           outer_rel->relids,
                                                           inner_rel,
-                                                          sjinfo->ojrelid));
+                                                          sjinfo));

     return result;
 }
@@ -1550,7 +1549,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;
@@ -1673,7 +1672,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,
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index e293de03c0..73edfc4bd0 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 5c0328ed76..bbb1b7d68f 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

Richard Guo <guofenglinux@gmail.com> writes:
> Hmm. Doing this complicates matters even more.  Maybe we can just loosen
> the cross-check for nullingrels to cope with this change by using
> NRM_SUBSET matches for joinquals (including mergeclauses, hashclauses
> and hashkeys) in set_join_references()?

That would be sad ... it'd basically be conceding defeat at the task
of knowing that we've accurately placed joinquals, which is one of
the most fundamental things I wanted to get out of this rewrite.

I might accept weakening those assertions as a stopgap that we plan to
work on more later, except that I'm afraid that this is telling us
there are still bugs in the area.

What's feeling like it might be the best thing is to go ahead and
syntactically convert to the second form of identity 3 as soon as
we've determined it's applicable, so that upper C Vars are always
marked with both OJ relids.  Not sure how much work is involved
there.

            regards, tom lane

[ sorry for slow response ]

Richard Guo <guofenglinux@gmail.com> writes:
> On Thu, Mar 2, 2023 at 11:27 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> What's feeling like it might be the best thing is to go ahead and
>> syntactically convert to the second form of identity 3 as soon as
>> we've determined it's applicable, so that upper C Vars are always
>> marked with both OJ relids.  Not sure how much work is involved
>> there.

> I'm thinking something that once we've determined identity 3 applies in
> make_outerjoininfo we record information about how to adjust relids for
> upper quals and store this info in all upper JoinTreeItems.  Then
> afterwards in distribute_qual_to_rels we check all this info stored in
> current JoinTreeItem and adjust relids for the qual accordingly.

> The info we record should consist of two parts, target_relids and
> added_relids.  Vars and PHVs in quals that belong to target_relids
> should be adjusted to include added_relids.

> Following this idea I come up with attached patch (no comments and test
> cases yet).  It fixes the presented case and passes check-world.  Before
> finishing it I'd like to know whether this idea works.  Any comments are
> appreciated.

This doesn't look hugely promising to me.  We do need to do something
like "Vars/PHVs referencing join X now need to also reference join Y",
but I think we need to actually change the individual Vars/PHVs not
just fake it by hacking the required_relids of RestrictInfos.  Otherwise
we're going to get assertion failures in setrefs.c about nullingrel
sets not matching up.

Also, in addition to upper-level quals, we need to apply the same
transformation to the query's targetlist and havingQual if anyway
(and perhaps also mergeActionList, not sure).

So the idea that I had was to, once we detect that X commutes with Y,
immediately call a function that recurses through the relevant parts
of root->parse and performs the required nullingrels updates.  This'd
result in multiple transformation traversals if there are several
commuting pairs of joins, but I doubt that that would really pose a
performance problem.  If it does, we could imagine splitting up
deconstruct_jointree still further, so that detection of commutable
OJs happens in a pass earlier than distribute_quals_to_rels, and then
we fix up Vars/PHVs throughout the tree in one scan done between those
passes.  But an extra deconstruct recursion pass isn't free either, so
I don't want to do that unless we actually see a performance problem.
Assuming we don't do that but perform this transformation during
deconstruct_jointree phase 2, it'd be too late to modify quals of
already-processed join tree nodes, but that's fine because they
couldn't contain Vars needing adjustment.  (We could exploit that
in an incomplete way by passing in the address of the current
JoinExpr, and not bothering to recurse below it.)  There is code
roughly like this in prepjointree.c already --- in particular, we'd
need to steal its hack of mutating join quals but not the JoinExpr and
FromExpr nodes themselves, to avoid breaking the recursion-in-progress.

I can have a go at coding this, or you can if you'd like to.

            regards, tom lane

On 4/4/23 08:00, Richard Guo wrote:
> I found a thinko in the v1 patch: we need to consider syn_righthand
> rather than min_righthand of the pushed down outer joins as we want to
> know if the Var or PHV actually comes from within the syntactically
> nullable sides.  Attach v2 to fix this.
> 
> I have some concerns that the new added foreach loop is too expensive to
> be doing for each Var or PHV.  But maybe it's no problem since we only
> loop over pushed down joins here.
I have passed through your patch and the 
'postpone-adding-pushed-down-ojrelid-to-relids' patch step-by-step. It 
looks logically correct.
Honestly, I don't happy with the top patch, because it looks a bit 
peculiar, but the sqlancer long test (which detected the problem before) 
didn't show any problems here.
But one thought is bugging me: do we have a guarantee, what with these 
Identity 3 transformations and 'delaying up to completely performed' 
technique we don't lose some joininfo clauses?

-- 
Regards
Andrey Lepikhov
Postgres Professional

On 4/21/23 14:34, Richard Guo wrote:
> 
> On Thu, Apr 20, 2023 at 1:06 PM Andrey Lepikhov 
> <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.ru>> wrote:
> Are you worried about upper clauses who reference to C vars?  In the
> second form when we've formed A/B join, which would have both outer
> joins' relids in its relid set, the upper clause will be able to be
> applied there, and it is the correct join level.
Yes, of course. I thought about the case with INNER JOINs in between, 
something like that:
a LEFT JOIN b ON b.x INNER JOIN c ON (b.x=c.x) LEFT JOIN d ON b.x ...
But, it is still a doubt.
> 
> BTW, cfbot reminds that a rebase is needed.  So re-attach the two
> patches.  Now I think it should be in 'Needs review' again in CF.  I'll
> go and do the change.
Thanks!

-- 
Regards
Andrey Lepikhov
Postgres Professional

Richard Guo <guofenglinux@gmail.com> writes:
> Hi Tom, how do you think about the v3 patch?

I need to look at it.  $life has been creating large distractions
for me lately, not to mention the release process ...

            regards, tom lane

On Sun, May 7, 2023 at 10:39 PM Richard Guo <guofenglinux@gmail.com> wrote:
> Hi Tom, how do you think about the v3 patch?

Hi Richard,

Thanks for working on this.

Today I reported an issue that Tom speculated might be related, so I
tried these patches and they didn't seem to fix it. It might be an
unrelated problem, but I thought it might be a good idea to put a link
to that thread here just for awareness:

https://www.postgresql.org/message-id/CA+TgmoYco=hmg+iX1CW9Y1_CzNoSL81J03wUG-d2_3=rue+L2A@mail.gmail.com

--
Robert Haas
EDB: http://www.enterprisedb.com

On Thu, May 11, 2023 at 12:11 PM Robert Haas <robertmhaas@gmail.com> wrote:
> On Sun, May 7, 2023 at 10:39 PM Richard Guo <guofenglinux@gmail.com> wrote:
> > Hi Tom, how do you think about the v3 patch?
>
> Hi Richard,
>
> Thanks for working on this.
>
> Today I reported an issue that Tom speculated might be related, so I
> tried these patches and they didn't seem to fix it. It might be an
> unrelated problem, but I thought it might be a good idea to put a link
> to that thread here just for awareness:
>
> https://www.postgresql.org/message-id/CA+TgmoYco=hmg+iX1CW9Y1_CzNoSL81J03wUG-d2_3=rue+L2A@mail.gmail.com

Seems like it was indeed unrelated.

--
Robert Haas
EDB: http://www.enterprisedb.com

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

I wrote:
> 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.

Hah, indeed so:

DROP TABLE IF EXISTS t1,t2,t3,t4 CASCADE;
CREATE TABLE t1 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t2 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t3 AS SELECT true AS x FROM generate_series(0,1) x;
CREATE TABLE t4 AS SELECT true AS x FROM generate_series(0,1000) x;
ANALYZE t1,t2,t3,t4;

EXPLAIN --(COSTS OFF)
select * from t1
  left join t2 on true
  left join t3 on t2.x
  left join t4 on t3.x;

v15 (and HEAD) find a plan of cost 180, this patch finds one
of cost 120.  This test case is pretty artificial of course;
can we come up with a more plausible query that we win on?

            regards, tom lane

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

Richard Guo <guofenglinux@gmail.com> writes:
> I doubt this is always right to add joins_below to all the vars
> belonging to sjinfo->syn_lefthand.  What if the joins in joins_below
> cannot commute with each other?  As a counterexample, consider the query
> below which causes assertion failure in search_indexed_tlist_for_var.
> The query is designed so that t1/t2 join cannot commute with t2/t3 join
> but can commute with t3/t4 join.

> explain (costs off)
> select * from t t1
>     left join t t2 on true
>     left join t t3 on true
>     left join t t4 on t2.a = t3.a;

Hm.  Actually, t1/t2 *can't* commute with the t4 join.  You can re-order
the t2 and t3 joins per identity 2:

select * from t t1
    left join t t3 on true
    left join t t2 on true
    left join t t4 on t2.a = t3.a;

but you're still stuck, identity 3 applies nowhere (because in either
case, the putative Pbc clause has also got a reference to A).

make_outerjoininfo is setting the t4 join's commute_below_l to include
t1/t2, but it seems to me that that indicates inadequate analysis in
make_outerjoininfo.  Is there still a problem here if we get rid of
that overoptimistic conclusion?  We should strive to do so even if
it's not fixing an observable problem, because in any case it's
causing the planner to waste time on unreachable join orders.

            regards, tom lane

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

Richard Guo <guofenglinux@gmail.com> writes:
> On Wed, May 17, 2023 at 11:10 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> * 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.

> Actually I did that in this way before I invented the join_info_array
> thing.  See patch 'v2-0001-Adjust-outer-join-s-target-list.patch' in
> https://www.postgresql.org/message-id/CAMbWs49CB3txv_s3SwC1L2h1DiUPAn%2Bv0-O4UFfg33b%2BHXNnTg%40mail.gmail.com
> A little difference is that that patch makes add_outer_joins_to_relids
> collect pushed down joins rather than pushed down ojrelids, so that in
> build_joinrel_tlist we can just loop over pushed down joins rather than
> the whole join_info_list.

Ah, good idea.  I made some cosmetic adjustments and pushed the lot.

We still have a couple of loose ends in this thread:

1. Do we need the change in add_nulling_relids that I postulated in [1]?

-            bms_overlap(phv->phrels, context->target_relids))
+            bms_is_subset(phv->phrels, context->target_relids))

The test case that made that fall over no longer does so, but I'm
suspicious that this is still needed.  I'm not quite sure though,
and I'm even less sure about the corresponding change in
remove_nulling_relids:

-            !bms_overlap(phv->phrels, context->except_relids))
+            !bms_is_subset(phv->phrels, context->except_relids))

which I made up pretty much out of whole cloth.

2. Can we do anything to tighten make_outerjoininfo's computation of
potential commutator pairs, as I speculated in [2]?  This isn't a bug
hazard anymore (I think), but adding useless bits there clearly does
cause us to waste cycles later.  If we can tighten that cheaply, it
should be a win.

3. In general, it seems like what your fixes are doing is computing
transitive closures of the commute_above relationships.  I wonder if
we can save anything by pre-calculating the closure sets.  Again,
I don't want to add cycles in cases where the whole thing doesn't
apply, but maybe we'd not have to.

            regards, tom lane

[1] https://www.postgresql.org/message-id/2489296.1684195396%40sss.pgh.pa.us
[2] https://www.postgresql.org/message-id/2766442.1684265014%40sss.pgh.pa.us

Richard Guo <guofenglinux@gmail.com> writes:
> BTW, it seems that there is a minor thinko in the changes.  In the
> outer-join removal logic, we use syn_xxxhand to compute the relid set
> for the join we are considering to remove.  I think this might be not
> right, because the outer joins may not be performed in syntactic order.

No, I don't believe that.  What we are interested in at this point is
the semantic effect (or lack of it) of the potentially-removable join.
It's fine to reason about that under the assumption that the joins will
be done in syntactic order.  If later parts of the planner decide to
implement the joins in a different order, that cannot change the
conclusion about whether it's safe to remove a join --- otherwise,
either we were mistaken to remove the join, or the reordering logic
is wrong.

I prefer the code as it stands now because it helps to decouple the
join-removal reasoning from the join-reordering logic, limiting any
possible effect of bugs in the latter.  (I think I might've had
some other reason for changing it as well, but can't reconstruct
that first thing in the morning.)

            regards, tom lane

Richard Guo <guofenglinux@gmail.com> writes:
> Take the query shown upthread as an example, which would trigger an
> Assert.

> create table t (a int unique, b int);

> explain (costs off)
> select 1 from t t1
>     left join (t t2 left join t t3 on t2.a = 1) on t2.a = 1;
> server closed the connection unexpectedly

> We'd be mistaken to think t1/t2 join is removable, because we are
> checking its syntactic relid set, which includes all rels, and so that
> are not aware that t2.a is used by t2/t3 join.

Ah, now your point has finally penetrated my thick skull: we can't
remove a join if its output is referenced at any join level that
we could potentially postpone past the join of interest, even
when that join is syntactically below it.  It seems like there
might be more than one way to skin that cat; maybe we could remove
it anyway and restrict the join order later?  But I agree that
three days before beta isn't the time to be rethinking the join
removal rules.

I remembered why it was that I wanted to change this logic, though.
It wasn't totally clear to me that min_lefthand + min_righthand
would account properly for outer joins below the one of interest.
However, considering it now it seems like that will hold, so now
I think your patch is correct.

            regards, tom lane

On 5/19/23 23:50, Tom Lane wrote:
> Richard Guo <guofenglinux@gmail.com> writes:
 >> ...
>> We'd be mistaken to think t1/t2 join is removable, because we are
>> checking its syntactic relid set, which includes all rels, and so that
>> are not aware that t2.a is used by t2/t3 join.
 > ...
> I think your patch is correct.

Because the feature pushed into the master, I checked it with the 
sqlancer tests. During all-weekend run no any problems were found.

-- 
Regards
Andrey Lepikhov
Postgres Professional

Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> Because the feature pushed into the master, I checked it with the 
> sqlancer tests. During all-weekend run no any problems were found.

Thanks for looking!  I strongly suspect that there still are some
problems in this area, but hopefully they are rare enough to go to
beta with.  I'll keep thinking about the issue.

            regards, tom lane