Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL

On Mon, Oct 26, 2026 at 8:28 PM Tender Wang <tndrwang(at)gmail(dot)com> wrote:
>
> PG Bug reporting form <noreply(at)postgresql(dot)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