pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedBUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
4+ messages / 3 participants
[nested] [flat]
* BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
@ 2026-10-26 16:58 PG Bug reporting form <noreply@postgresql.org>
0 siblings, 1 reply; 4+ messages in thread
From: PG Bug reporting form @ 2026-10-26 16:58 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: alpkeles99@gmail.com
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
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
@ 2026-10-27 03:27 Tender Wang <tndrwang@gmail.com>
parent: PG Bug reporting form <noreply@postgresql.org>
0 siblings, 1 reply; 4+ messages in thread
From: Tender Wang @ 2026-10-27 03:27 UTC (permalink / raw)
To: alpkeles99@gmail.com; pgsql-bugs@lists.postgresql.org
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
Attachments:
0001-Fix-sje-crash-due-to-lateral-dependecy-cycle.patch (text/plain, 3.3K) download
From 283522782c10ce2d70acfde05dad3390a7f2952d Mon Sep 17 00:00:00 2001
From: Tender Wang <tndrwang@gmail.com>
Date: Tue, 27 Oct 2026 11:20:34 +0800
Subject: [PATCH] Fix sje crash due to lateral dependecy cycle
---
src/backend/optimizer/plan/analyzejoins.c | 67 ++++++++++++++++++++++-
1 file changed, 66 insertions(+), 1 deletion(-)
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 7aad91fd34e..91fba79699d 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -33,6 +33,7 @@
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+#include "optimizer/placeholder.h"
#include "optimizer/planmain.h"
#include "optimizer/prep.h"
#include "optimizer/restrictinfo.h"
@@ -96,6 +97,9 @@ static void fixup_selfjoin_jointree(PlannerInfo *root, Node *jtnode, int relid,
static List *fixup_selfjoin_quals(PlannerInfo *root, List *quals, int relid);
static Node *replace_selfjoin_qual(Node *qual);
static int self_join_candidates_cmp(const void *a, const void *b);
+static bool self_join_has_dangerous_lateral_phv(PlannerInfo *root,
+ int eval_relid,
+ int referenced_relid);
/*
@@ -1758,6 +1762,63 @@ match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
return true;
}
+/*
+ * Check whether a PHV evaluated at eval_relid depends laterally on a relation
+ * that in turn references referenced_relid. Merging those two rels would
+ * turn that two-step dependency into a cycle.
+ */
+static bool
+self_join_has_dangerous_lateral_phv(PlannerInfo *root, int eval_relid,
+ int referenced_relid)
+{
+ ListCell *lc;
+
+ foreach(lc, root->placeholder_list)
+ {
+ PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
+ int lateral_relid = -1;
+
+ if (!bms_is_member(eval_relid, phinfo->ph_eval_at))
+ continue;
+
+ while ((lateral_relid =
+ bms_next_member(phinfo->ph_lateral, lateral_relid)) >= 0)
+ {
+ RelOptInfo *lateral_rel;
+ ListCell *lc2;
+
+ lateral_rel = find_base_rel_ignore_join(root, lateral_relid);
+ if (lateral_rel == NULL)
+ continue;
+
+ foreach(lc2, lateral_rel->lateral_vars)
+ {
+ Node *node = (Node *) lfirst(lc2);
+
+ if (IsA(node, Var))
+ {
+ if (((Var *) node)->varno == referenced_relid)
+ return true;
+ }
+ else if (IsA(node, PlaceHolderVar))
+ {
+ PlaceHolderInfo *lateral_phinfo;
+
+ lateral_phinfo =
+ find_placeholder_info(root, (PlaceHolderVar *) node);
+ if (bms_is_member(referenced_relid,
+ lateral_phinfo->ph_eval_at))
+ return true;
+ }
+ else
+ Assert(false);
+ }
+ }
+ }
+
+ return false;
+}
+
/*
* Find and remove unique self-joins in a group of base relations that have
* the same Oid.
@@ -1861,8 +1922,12 @@ remove_self_joins_one_group(PlannerInfo *root, Relids relids)
joinrelids = bms_add_member(joinrelids, k);
/*
- * PHVs should not impose any constraints on removing self-joins.
+ * Merging the two relations must not turn an indirect LATERAL
+ * dependency through a PHV into a cycle.
*/
+ if (self_join_has_dangerous_lateral_phv(root, k, r) ||
+ self_join_has_dangerous_lateral_phv(root, r, k))
+ continue;
/*
* At this stage, joininfo lists of inner and outer can contain
--
2.43.0
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
@ 2026-10-28 03:40 Haibo Yan <tristan.yim@gmail.com>
parent: Tender Wang <tndrwang@gmail.com>
0 siblings, 1 reply; 4+ messages in thread
From: Haibo Yan @ 2026-10-28 03:40 UTC (permalink / raw)
To: Tender Wang <tndrwang@gmail.com>; +Cc: alpkeles99@gmail.com; pgsql-bugs@lists.postgresql.org
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.g...
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
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL
@ 2026-10-28 03:57 Tender Wang <tndrwang@gmail.com>
parent: Haibo Yan <tristan.yim@gmail.com>
0 siblings, 0 replies; 4+ messages in thread
From: Tender Wang @ 2026-10-28 03:57 UTC (permalink / raw)
To: Haibo Yan <tristan.yim@gmail.com>; +Cc: alpkeles99@gmail.com; pgsql-bugs@lists.postgresql.org
Haibo Yan <tristan.yim@gmail.com> 于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
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2026-10-28 03:57 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-10-26 16:58 BUG #19799: Self-join elimination: "failed to build any 3-way joins" with LATERAL PG Bug reporting form <noreply@postgresql.org>
2026-10-27 03:27 ` Tender Wang <tndrwang@gmail.com>
2026-10-28 03:40 ` Haibo Yan <tristan.yim@gmail.com>
2026-10-28 03:57 ` Tender Wang <tndrwang@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox