BUG #19765: Wrong result from a chain of LEFT JOINs since v16

PG Bug reporting form <noreply@postgresql.org> 于2026年10月16日周五 17:50写道：

EXPLAIN shows that all three join conditions have disappeared, leaving
three unqualified nested-loop left joins:

Nested Loop Left Join
-> Values Scan on "*VALUES*"
Filter: (column1 = 1)
-> Nested Loop Left Join
-> Nested Loop Left Join
-> Values Scan on "*VALUES*_1"
Filter: (column1 = 1)
-> Values Scan on "*VALUES*_2"
Filter: (column1 = 1)
-> Values Scan on "*VALUES*_3"
Filter: (column1 = 1)

I think the problem is in the interaction between constant propagation
in reconsider_outer_join_clauses() and outer-join identity 3.

To support join reordering, deconstruct_distribute_oj_quals()
generates variants of the join quals with different nullingrels
markings.
The least-nulled variants allow reconsider_outer_join_clause() to
propagate the constant through the chain: a=1 implies a restriction
b=1, then c=1, and finally d=1.
The corresponding join quals are replaced with constant-TRUE dummy clauses.

However, a restriction on the scan of C does not guarantee that c=1
still holds after C has been null-extended. In the chosen join order,

A LEFT JOIN ((B LEFT JOIN C) LEFT JOIN D)

the B/C join produces a row with c=NULL, since no C row passes c=1.
The original c=d qual would reject a match with D, whereas its TRUE
replacement allows d=1 to match.

Thus, deriving the inner-side restriction is not sufficient to
establish that the join qual is redundant.
In particular, replacing a strict qual with TRUE can invalidate the
reasoning that allowed the outer joins to commute.

I am considering guarding this optimization when a commuting lower
outer join could null-extend the outer operand.
Specifically, I would examine the joins in sjinfo->commute_below_l and
retain the original qual if one of their syn_righthand sets overlaps
the outer operand's relids.

It might also be possible to retain constant propagation while keeping
the original join qual, but that would require separating the
deduction from the decision to discard the qual.

--
Thanks,
Tender Wang

Hi,

On Fri, Oct 16, 2026 at 6:41 PM Tender Wang <tndrwang@gmail.com> wrote:

PG Bug reporting form <noreply@postgresql.org> 于2026年10月16日周五 17:50写道：

EXPLAIN shows that all three join conditions have disappeared, leaving
three unqualified nested-loop left joins:

Nested Loop Left Join
-> Values Scan on "*VALUES*"
Filter: (column1 = 1)
-> Nested Loop Left Join
-> Nested Loop Left Join
-> Values Scan on "*VALUES*_1"
Filter: (column1 = 1)
-> Values Scan on "*VALUES*_2"
Filter: (column1 = 1)
-> Values Scan on "*VALUES*_3"
Filter: (column1 = 1)

I think the problem is in the interaction between constant propagation
in reconsider_outer_join_clauses() and outer-join identity 3.

Thanks for the analysis. I also found the same cause with LLM help.

I am considering guarding this optimization when a commuting lower
outer join could null-extend the outer operand.
Specifically, I would examine the joins in sjinfo->commute_below_l and
retain the original qual if one of their syn_righthand sets overlaps
the outer operand's relids.

It seems that this might add an extra filter for a query like this

select b.b, c.c, d.d from (values (1),(2)) as b(b)
left join (values (7),(2)) as c(c) on b.b = c.c
left join (values (1),(2)) as d(d) on c.c = d.d
where b.b = 1;

I considered instead keeping the qual if the clone is incompatible
with some other outer join whose commute_below_l is non-empty. It
seemed like a narrower check that should preserve the optimization in
the above scenario.

I'm attaching the patch with this idea. Please take a look and let me
know what you think.

Thanks & Regards,
Nitin Motiani
Google

On Fri, Oct 16, 2026 at 10:11 PM Tender Wang <tndrwang@gmail.com> wrote:

Thus, deriving the inner-side restriction is not sufficient to
establish that the join qual is redundant.
In particular, replacing a strict qual with TRUE can invalidate the
reasoning that allowed the outer joins to commute.

I came to the same conclusion. To elaborate on it a bit more, the
problem is that when an outer join gets commuted into the RHS of a
lower outer join, we don't add its relid until the lower join is
formed (see add_outer_joins_to_relids). So in the meantime, its RHS
Vars can already have gone to NULL without having its nulling bit. If
a higher outer join that commutes with it gets joined on top at that
point, clone selection sees that the relid is missing and picks the
least-nulled version of its qual.

Normally that's fine, because the qual is strict and will reject the
null-extended rows anyway, which is what identity 3 depends on. But
once we've replaced that qual with a constant-TRUE dummy, nothing
rejects them, and we get bogus matches.

I think we can fix this by only making the TRUE dummy for clauses that
are not clones. For a clone, just throw the original clause back, as
v15 and earlier did.

- Richard

On Fri, Oct 16, 2026 at 8:34 PM Richard Guo <guofenglinux@gmail.com> wrote:

I think we can fix this by only making the TRUE dummy for clauses that
are not clones. For a clone, just throw the original clause back, as
v15 and earlier did.

I had first tried this change and it worked but for one of the tests
in join.sql, it also added a redundant filter.

On Fri, Oct 16, 2026 at 8:13 PM Nitin Motiani <nitinmotiani@google.com> wrote:

select b.b, c.c, d.d from (values (1),(2)) as b(b)
left join (values (7),(2)) as c(c) on b.b = c.c
left join (values (1),(2)) as d(d) on c.c = d.d
where b.b = 1;

And for the 3-join query like this, it looks like we will have an
extra filter. So in my patch [1]/messages/by-id/CAH5HC94V8kr1OcSDkzh2kGTNE6PU3ZXeF_G1LZ76BnE0E-9gnQ@mail.gmail.com, I skipped the TRUE dummy option if
the clone is incompatible with some other outer join whose
commute_below_l is non-empty as only such an outer join can have its
relid deferred (add_outer_joins_to_relids). That approach also seems
to work and avoids adding the extra filter in the above scenario.

Let me know what you think of this approach compared to the simpler
solution of removing the TRUE dummy for all the cases with clones.

Thanks,
Nitin Motiani
Google

[1]: /messages/by-id/CAH5HC94V8kr1OcSDkzh2kGTNE6PU3ZXeF_G1LZ76BnE0E-9gnQ@mail.gmail.com

Hi,

I'm attaching the rebased patch.

On Sat, Oct 17, 2026 at 1:05 PM Nitin Motiani <nitinmotiani@google.com> wrote:

On Fri, Oct 16, 2026 at 8:34 PM Richard Guo <guofenglinux@gmail.com> wrote:

I think we can fix this by only making the TRUE dummy for clauses that
are not clones. For a clone, just throw the original clause back, as
v15 and earlier did.

I had first tried this change and it worked but for one of the tests
in join.sql, it also added a redundant filter.

I am also attaching a patch with this simpler approach you suggested.
(v2-0001-Keep-all-cloned-outer-join-clauses.patch.txt). This keeps the
original clause for all clones. It also changes one existing plan in
join.out, where a redundant "Join Filter: (tt3.f1 = tt4.f1)" appears.

And I'm attaching the rebased patch for my narrower check from v1
(v2-0001-Keep-cloned-outer-join-clauses-only-where-needed.patch). This
keeps the original clause only if the clone is incompatible with
another outer join whose commute_below_l is non-empty). No changes to
existing regression output.

Please take a look and let me know which alternative seems better to you.

Thanks & Regards,
Nitin Motiani
Google

On Wed, Oct 21, 2026 at 7:30 PM Nitin Motiani <nitinmotiani@google.com> wrote:

Please take a look and let me know which alternative seems better to you.

Thanks for the patch! It's on my radar, but I'm currently occupied
with a few other items. I'll do my best to get to it before the minor
release.

- Richard

Richard Guo <guofenglinux@gmail.com> 于2026年10月22日周四 09:50写道：

On Wed, Oct 21, 2026 at 7:30 PM Nitin Motiani <nitinmotiani@google.com> wrote:

Please take a look and let me know which alternative seems better to you.

Thanks for the patch! It's on my radar, but I'm currently occupied
with a few other items. I'll do my best to get to it before the minor
release.

Thanks for the patch. The v2 patch fixes the wrong-result case, but
while reviewing it I noticed that it can retain more join clauses than
necessary.

For example, I forced the following join order using pg_plan_advice:

JOIN_ORDER(t1 t2 (t3 t4))

for the query:

select t1.a, t2.b, t3.c, t4.d
from t1
left join t2 on t1.a = t2.b
left join t3 on t2.b = t3.c
left join t4 on t3.c = t4.d
where t1.a = 1;

With v2, the relevant part of the plan is:

QUERY PLAN
-------------------------------------------
Hash Left Join
Hash Cond: (t2.b = t3.c)
-> Nested Loop Left Join
-> Seq Scan on t1
Filter: (a = 1)
-> Materialize
-> Seq Scan on t2
Filter: (b = 1)
-> Hash
-> Hash Left Join
Hash Cond: (t3.c = t4.d)
-> Seq Scan on t3
Filter: (c = 1)
-> Hash
-> Seq Scan on t4
Filter: (d = 1)
Supplied Plan Advice:
JOIN_ORDER(t1 t2 (t3 t4)) /* matched */

The (t2.b = t3.c) condition is necessary at this join level: t2.b may
already have been null-extended by the t1/t2 outer join.

However, (t3.c = t4.d) is redundant in the directly formed t3/t4 join.
At that level, t3.c is still the value from the preserved base
relation, and constant propagation has already restricted both sides
to 1.
Thus, retaining every affected cloned clause whenever a commuting
outer join exists is somewhat conservative.

I think the underlying issue is that the redundancy of such a clause
is placement-dependent. Constant propagation itself is valid, but it
does not imply that the original strict join clause can be discarded
at every join level at which its clone might be applied.

The attached v3 patch therefore separates those two decisions.

During reconsider_outer_join_clauses(), constant propagation still
proceeds as before.
For a cloned clause whose outer operand can be null-extended by a
commuting lower outer join, however, the patch retains the original
RestrictInfo and records the relevant outer-join relids instead of
replacing the clause unconditionally with a constant-TRUE dummy.

When constructing the restrictlist for a particular joinrel, the
original clause is included only when a recorded outer join: has both
of its minimum inputs available, meaning that it may already have
performed null-extension;

does not yet have its outer-join relid in the available relids; and is
still waiting for a commuting lower outer join to be completed.

This is the state in which the outer operand may already be NULL even
though the least-nulled clone remains applicable, so the strict join
clause is still required. At other join levels the retained clause is
omitted as redundant.

With v3 version:

the original wrong-result query returns 1 | 1 | NULL | NULL;

for the forced t1 t2 (t3 t4) join order, t2.b = t3.c is retained;

t3.c = t4.d is removed from the direct t3/t4 join; and the tree builds
successfully with assertions enabled.

The v3 patch is attached.
Thoughts?

--
Thanks,
Tender Wang

On Fri, Oct 23, 2026 at 12:42 PM Tender Wang <tndrwang@gmail.com> wrote:

I think the underlying issue is that the redundancy of such a clause
is placement-dependent. Constant propagation itself is valid, but it
does not imply that the original strict join clause can be discarded
at every join level at which its clone might be applied.

Right, the clause is redundant at the directly formed t3/t4 join, and
whether it is redundant depends on where it gets applied.

However, your v3 adds a new field to RestrictInfo, which breaks ABI
and can't be back-patched.

IMO keeping a redundant clause costs little if we mark it as having
selectivity 1.0, and it's no worse than what v15 and earlier did,
which always kept such clauses. So I think we should accept some
redundant clauses in the bug fix. The placement-aware redundancy
checks can be a possible improvement for master.

- Richard

On Thu, Oct 22, 2026 at 10:50 AM Richard Guo <guofenglinux@gmail.com> wrote:

Thanks for the patch! It's on my radar, but I'm currently occupied
with a few other items. I'll do my best to get to it before the minor
release.

I reviewed your v2 patch. It fixes this bug, but I don't think the
narrower check should rely on incompatible_relids. AFAIU, that field
is a placement filter: it lists the outer joins above which a clone
must not be evaluated, so that only one version of the clause is
accepted at any join level. The v2 patch reads it as "the set of
commuting joins whose nulling bit this clone lacks". That happens to
be true today, because of how deconstruct_distribute_oj_quals() builds
it, but it's not what the field means.

What matters is whether OUTERVAR lacks the nulling bit of a commuting
outer join whose relid can be withheld, and that can be checked
directly on the outer side's relids, which include its nullingrels:

if ((bms_is_member(othersj->ojrelid, sjinfo->commute_below_l) ||
bms_is_member(othersj->ojrelid, sjinfo->commute_above_r)) &&
!bms_is_member(othersj->ojrelid, outer_relids) &&
!bms_is_empty(othersj->commute_below_l))
return true;

That said, as Tender showed, the narrower check doesn't avoid all
redundant clauses either. So I still lean slightly toward simply
keeping all cloned clauses as-is (marked as having selectivity 1.0),
as v15 and earlier did. For example:

/* keep a cloned clause as-is */
if (rinfo->has_clone || rinfo->is_clone)
{
/* but the kept clause has no extra selectivity */
rinfo->norm_selec = 1.0;
rinfo->outer_selec = 1.0;
distribute_restrictinfo_to_rels(root, rinfo);
continue;
}

It's simpler, and its correctness doesn't depend on mirroring the
rules in add_outer_joins_to_relids(). This is also in line with
commit 716a051aa, where we stopped performing NullTest deduction for
clone clauses because their nullingrel bits may not reflect reality.
I don't think the redundant clauses cost enough to justify the extra
complexity of the narrower check. But this is a judgment call, and
neither approach is a clear win.

(Cc'ing Tom to have a look.)

- Richard

On Fri, Oct 23, 2026 at 1:10 PM Richard Guo <guofenglinux@gmail.com> wrote:

It's simpler, and its correctness doesn't depend on mirroring the
rules in add_outer_joins_to_relids(). This is also in line with
commit 716a051aa, where we stopped performing NullTest deduction for
clone clauses because their nullingrel bits may not reflect reality.
I don't think the redundant clauses cost enough to justify the extra
complexity of the narrower check. But this is a judgment call, and
neither approach is a clear win.

Thanks for the explanation regarding incompatible_relids and the
selectivity fields. Since the narrow check doesn't cover all the
cases, it does seem better to keep it simple.

Attached is v4 based on your suggestions, which keeps all cloned
outer-join clauses and sets norm_selec = 1.0 and outer_selec = 1.0 on
them. I also added a second test case where the
c/d outer join is written inside the RHS of the b/c outer join, which
also returns wrong results on master.

Regards,
Nitin Motiani
Google