BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
От:
PG Bug reporting form <noreply@postgresql.org>
Дата:
The following bug has been logged on the website:
Bug reference: 19799
Logged by: Alperen Keles
Email address: alpkeles99@gmail.com
PostgreSQL version: 18.6
Operating system: Ubuntu 24.04 x86_64 (also macOS 26 arm64)
Description:
Hello,
With self-join elimination, this query fails at plan time with an
internal error:
CREATE TABLE t (a int PRIMARY KEY);
INSERT INTO t VALUES (1), (2);
SELECT s.y
FROM t d LEFT JOIN
(t x CROSS JOIN LATERAL (SELECT x.a AS v OFFSET 0) b
CROSS JOIN LATERAL (SELECT coalesce(b.v, 0) FROM t c
WHERE c.a = x.a) s(y))
ON true;
ERROR: XX000: failed to build any 3-way joins
LOCATION: standard_join_search, allpaths.c:3537 (18.6)
On builds with --enable-cassert the backend crashes instead:
TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"),
File: "initsplan.c", Line: 1370 (master; Line 1086 on REL_18_STABLE)
With SET enable_self_join_elimination = off the query returns the 4
expected rows (each of 1 and 2 twice). The table can be empty. It also
fails with FULL JOIN or RIGHT JOIN in place of the LEFT JOIN, with
(SELECT 1) in place of d, and with b written as LATERAL
generate_series(1, x.a) or a two-row LATERAL VALUES list; with
geqo_threshold = 2 the error is "geqo failed to make a valid plan". It
works without the outer join, without the unique key, with b.v or b.v
+ 1 in place of coalesce(b.v, 0), without OFFSET 0 in b, and with
join_collapse_limit = 1 and from_collapse_limit = 1.
Reproduced on 18.6 (REL_18_6, without assertions, macOS arm64),
REL_18_STABLE 4d62ef92fda, 19rc1 (REL_19_STABLE 1212d5d33b1) and
master 022a80fe6c1 (--enable-cassert, Ubuntu 24.04 x86_64), and master
a261fc2b722 without assertions. 17 and earlier have no self-join
elimination; 14 returns the rows.
The same assertion was reported in the thread "Assert failure in
create_lateral_join_info" and fixed by 3138f248cd3 ("Don't remove an
RTE_RESULT needed by a nested PlaceHolderVar"). That query was
reached through RTE_RESULT removal and works on master 022a80fe6c1,
which contains 3138f248cd3, but this one still fails there.
Found with a query fuzzer.
Regards,
Alperen Keles
Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
PG Bug reporting form 于2026年10月27日周二 04:32写道:
>
>
> CREATE TABLE t (a int PRIMARY KEY);
> INSERT INTO t VALUES (1), (2);
> SELECT s.y
> FROM t d LEFT JOIN
> (t x CROSS JOIN LATERAL (SELECT x.a AS v OFFSET 0) b
> CROSS JOIN LATERAL (SELECT coalesce(b.v, 0) FROM t c
> WHERE c.a = x.a) s(y))
> ON true;
> ERROR: XX000: failed to build any 3-way joins
> LOCATION: standard_join_search, allpaths.c:3537 (18.6)
>
> On builds with --enable-cassert the backend crashes instead:
>
> TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"),
> File: "initsplan.c", Line: 1370 (master; Line 1086 on REL_18_STABLE)
Thanks for the report.
I investigated this issue and found that self-join elimination can
create a self-referential lateral dependency through a PlaceHolderVar.
In the reported query, before self-join elimination, the relevant
dependencies are approximately:
c -> b -> x
Here, the PlaceHolderVar is evaluated at c, and its expression has a
lateral dependency on the subquery b. The lateral subquery b, in turn,
references x.
SJE determines that x and c can be merged. When x is replaced by c,
the dependencies become:
c -> b -> c
After SJE restarts join planning, create_lateral_join_info() computes
the transitive closure of the lateral dependencies.
The dependency from b to c is consequently propagated back to c,
causing c to acquire a lateral dependency on itself.
This eventually results in the reported planner error, or an assertion
failure in an assertion-enabled build.
There are a few possible ways to address this:
1. Adjust the PlaceHolderVar evaluation and lateral-dependency
information while removing the relation.
This seems risky because ph_eval_at and ph_lateral describe semantic
constraints on where the expression may be evaluated. Rewriting them
merely to allow SJE could change the semantics of the PlaceHolderVar.
2. Build a general lateral-dependency graph and reject an SJE
candidate whenever contracting the two relations would form a cycle.
This would handle arbitrary dependency chains, but it requires a
relatively large amount of new SJE code, including graph traversal and
cycle detection.
That seems like more machinery than the known problem requires.
3. Reject the SJE candidate when a PlaceHolderVar exposes the
problematic dependency pattern.
The attached patch takes the third, conservative approach. Before
merging two self-join candidates, it checks whether a PlaceHolderVar
evaluated at one candidate depends laterally on an intermediate
relation which, in turn, references the other candidate. If so, SJE
skips that pair.
This is similar in spirit to commit
3138f248cd3de43dd0f96760fc666152ea8a5c37: instead of attempting to
rewrite PlaceHolderVar placement information, avoid an optimization
that would make the existing placement constraints invalid.
The check is intentionally narrower than a general graph-cycle detector.
In particular, it preserves SJE when only a direct lateral reference
exists between the two candidates.
That case is safe because the dependency disappears when the
referenced relation is merged. For example, the existing test:
select * from sj t1
left join lateral
(select t1.a as t1a, * from sj t2) s
on true
where t1.a = s.a;
continues to be reduced to a scan of t2; the patch does not introduce
a plan change for that query.
I have run the regression tests with the attached patch, and they pass.
Thoughts?
--
Thanks,
Tender Wang
Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
От:
Haibo Yan <tristan.yim@gmail.com>
Дата:
On Mon, Oct 26, 2026 at 8:28 PM Tender Wang <tndrwang@gmail.com> wrote:
>
> PG Bug reporting form <noreply@postgresql.org> 于2026年10月27日周二 04:32写道:
> >
> >
> > CREATE TABLE t (a int PRIMARY KEY);
> > INSERT INTO t VALUES (1), (2);
> > SELECT s.y
> > FROM t d LEFT JOIN
> > (t x CROSS JOIN LATERAL (SELECT x.a AS v OFFSET 0) b
> > CROSS JOIN LATERAL (SELECT coalesce(b.v, 0) FROM t c
> > WHERE c.a = x.a) s(y))
> > ON true;
> > ERROR: XX000: failed to build any 3-way joins
> > LOCATION: standard_join_search, allpaths.c:3537 (18.6)
> >
> > On builds with --enable-cassert the backend crashes instead:
> >
> > TRAP: failed Assert("!bms_is_member(rti, lateral_relids)"),
> > File: "initsplan.c", Line: 1370 (master; Line 1086 on REL_18_STABLE)
>
> Thanks for the report.
>
> I investigated this issue and found that self-join elimination can
> create a self-referential lateral dependency through a PlaceHolderVar.
>
> In the reported query, before self-join elimination, the relevant
> dependencies are approximately:
>
> c -> b -> x
>
> Here, the PlaceHolderVar is evaluated at c, and its expression has a
> lateral dependency on the subquery b. The lateral subquery b, in turn,
> references x.
>
> SJE determines that x and c can be merged. When x is replaced by c,
> the dependencies become:
>
> c -> b -> c
>
> After SJE restarts join planning, create_lateral_join_info() computes
> the transitive closure of the lateral dependencies.
> The dependency from b to c is consequently propagated back to c,
> causing c to acquire a lateral dependency on itself.
> This eventually results in the reported planner error, or an assertion
> failure in an assertion-enabled build.
>
> There are a few possible ways to address this:
>
> 1. Adjust the PlaceHolderVar evaluation and lateral-dependency
> information while removing the relation.
>
> This seems risky because ph_eval_at and ph_lateral describe semantic
> constraints on where the expression may be evaluated. Rewriting them
> merely to allow SJE could change the semantics of the PlaceHolderVar.
>
> 2. Build a general lateral-dependency graph and reject an SJE
> candidate whenever contracting the two relations would form a cycle.
>
> This would handle arbitrary dependency chains, but it requires a
> relatively large amount of new SJE code, including graph traversal and
> cycle detection.
> That seems like more machinery than the known problem requires.
>
> 3. Reject the SJE candidate when a PlaceHolderVar exposes the
> problematic dependency pattern.
>
> The attached patch takes the third, conservative approach. Before
> merging two self-join candidates, it checks whether a PlaceHolderVar
> evaluated at one candidate depends laterally on an intermediate
> relation which, in turn, references the other candidate. If so, SJE
> skips that pair.
>
> This is similar in spirit to commit
> 3138f248cd3de43dd0f96760fc666152ea8a5c37: instead of attempting to
> rewrite PlaceHolderVar placement information, avoid an optimization
> that would make the existing placement constraints invalid.
>
> The check is intentionally narrower than a general graph-cycle detector.
> In particular, it preserves SJE when only a direct lateral reference
> exists between the two candidates.
> That case is safe because the dependency disappears when the
> referenced relation is merged. For example, the existing test:
>
> select * from sj t1
> left join lateral
> (select t1.a as t1a, * from sj t2) s
> on true
> where t1.a = s.a;
>
> continues to be reduced to a scan of t2; the patch does not introduce
> a plan change for that query.
> I have run the regression tests with the attached patch, and they pass.
>
> Thoughts?
> --
> Thanks,
> Tender Wang
Hi Tender,
Thanks for your patch. I tested it against the reduced reproducer
and a related PHV evaluation-site expansion case.
Your patch handles the reduced reproducer, but the following related
case still fails with self-join elimination enabled:
CREATE TABLE t (a int PRIMARY KEY);
INSERT INTO t VALUES (1), (2);
SELECT s.y
FROM t x,
abs(x.a) b,
LATERAL (
SELECT x.a + d.a + b.b AS y
FROM t c, t d
WHERE c.a = x.a AND d.a = x.a
) s
GROUP BY CUBE (1);
The expected result is {3, 6, NULL}. With assertions enabled, the
backend hits the lateral-dependency assertion at initsplan.c:1370.
Without assertions, planning fails with “failed to build any
2-way joins.” With self-join elimination disabled, the query returns
the expected multiset.
Before the candidate merge, the PHV is evaluated at d, so c is not
in ph_eval_at and your check skips the candidate. Replacing x with c
changes the PHV evaluation set to include c. The PHV dependency
through b then forms a cycle with b's rewritten reference to c.
The check does not simulate this substitution or recompute the PHV
evaluation and lateral sets before deciding whether the merge is safe.
We posted a proposed fix with regression tests in a separate message:
https://www.postgresql.org/message-id/CABXr29HQ1jLEMvOQ6bdXYM67U%2BLwkn3tJ5hwOM2SQCp46V4e6g%40mail.gmail.com
The patch simulates the candidate substitution, recomputes the PHV
evaluation and lateral sets, and rejects merges that would create a
cycle. It also updates planner state after accepted merges so later
candidates see the revised dependencies. The assertion-enabled and
non-assertion builds passed the 239-test core regression schedule.
Regards,
Haibo Yan
Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
От:
Tender Wang <tndrwang@gmail.com>
Дата:
Haibo Yan 于2026年10月28日周三 11:40写道: > > > Your patch handles the reduced reproducer, but the following related > case still fails with self-join elimination enabled: > > CREATE TABLE t (a int PRIMARY KEY); > INSERT INTO t VALUES (1), (2); > > SELECT s.y > FROM t x, > abs(x.a) b, > LATERAL ( > SELECT x.a + d.a + b.b AS y > FROM t c, t d > WHERE c.a = x.a AND d.a = x.a > ) s > GROUP BY CUBE (1); > Thanks for testing the patch and for providing this additional case. I agree that the current patch is too narrow to handle this case. As I mentioned in my previous message, the patch deliberately checks only the dependency pattern exposed by the original reproducer. I also considered a more general solution that models the lateral dependencies as a graph and checks whether merging two candidate relations would create a cycle. At the time, however, I was not sure that adding the amount of code needed for a general dependency-cycle check was justified for this single reported case. Therefore, I chose the smaller and more conservative fix as a first approach. Your new example demonstrates an important limitation of that approach: the dangerous dependency does not necessarily exist in the current ph_eval_at and ph_lateral sets. It can appear only after the candidate substitution changes the PHV evaluation sites and rewrites the lateral references. Consequently, inspecting only the dependency sets before the merge cannot cover this class of cases reliably. Given this additional report, it now seems that a general dependency cycle check is necessary. Such a check needs to simulate the candidate substitution, derive the resulting PHV evaluation and lateral dependencies, and reject the merge if the substituted dependency graph contains a cycle. It also needs to update the dependency state after an accepted merge, so that subsequent candidates are checked against the updated graph. -- Thanks, Tender Wang