BUG #19798: "failed to build any 4-way joins" with ROLLUP over a LATERAL subquery that references the nullable s
BUG #19798: "failed to build any 4-way joins" with ROLLUP over a LATERAL subquery that references the nullable s
От:
PG Bug reporting form <noreply@postgresql.org>
Дата:
The following bug has been logged on the website:
Bug reference: 19798
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,
A query with grouping sets fails at plan time with an internal error
when a LATERAL subquery over two tables returns a column of the
nullable side of an earlier LEFT JOIN. The same query without
grouping sets runs fine.
CREATE TABLE t (x int);
INSERT INTO t VALUES (1), (2);
SELECT s.y
FROM t b LEFT JOIN t a ON a.x = b.x
CROSS JOIN LATERAL (SELECT a.x AS y FROM t c, t d) s
GROUP BY ROLLUP (s.y);
ERROR: XX000: failed to build any 4-way joins
LOCATION: standard_join_search, allpaths.c:3538 (18.6)
The table can be empty. CUBE (s.y), GROUPING SETS ((s.y), ()) and a
RIGHT JOIN in place of the LEFT JOIN fail the same way. With three
tables in the subquery it fails with "5-way joins", and with
"t b LEFT JOIN (t a JOIN t f ON a.x = f.x) ON a.x = b.x" and three
tables in the subquery with "6-way joins". The query works with a
plain GROUP BY s.y or no GROUP BY, with one table in the subquery,
with an inner join instead of the LEFT JOIN, when the subquery
references b instead of a, or with join_collapse_limit = 1 and
from_collapse_limit = 1.
Reproduced on 18.6 (REL_18_STABLE 4d62ef92fda), 19rc1 (REL_19_STABLE
1212d5d33b1), 14.24 (REL_14_STABLE 14904052e65) and master 022a80fe6c1,
--enable-cassert, Ubuntu 24.04 x86_64; also on master and 18.6 on
macOS arm64. It is a plain ERROR, not an assertion failure. All of
these builds include the fix for the similar case in the thread
"failed to build any N-way joins" from a five-relation query
(commit b84ad0cd904 on master), and that thread's query works on
them, but this one still fails.
The first failing commit is 90947674fc9 ("Fix incorrect handling of
subquery pullup in the presence of grouping sets", 2018), which was
back-patched to 9.5. It fails, and its parent ca4587f3f94 returns the
rows.
As far as I can tell, since that commit pull_up_simple_subquery()
wraps the subquery output a.x, a lateral reference, in a
PlaceHolderVar evaluated at {c,d} when the query has grouping sets. So
c and d must be joined first, and the only legal 4-way join is
{b,a} + {c,d}. No join clause connects these two. In the bushy loop of
join_search_one_level() the pair is considered only with {b,a} as
old_rel, since {b,a} comes first in the level-2 list. {b,a} is skipped
there because it has no join clauses and has_join_restriction() is
false for it: it contains its outer join, and a joinrel's
lateral_referencers is always NULL. The 5-way and 6-way forms fail the
same way, because there the pair is considered only with the smaller
side, {b,a} or {b,a,f}, as old_rel.
Found with a query fuzzer.
Regards,
Alperen Keles
Re: BUG #19798: "failed to build any 4-way joins" with ROLLUP over a LATERAL subquery that references the nullable s
PG Bug reporting form 于2026年10月27日周二 04:32写道:
> As far as I can tell, since that commit pull_up_simple_subquery()
> wraps the subquery output a.x, a lateral reference, in a
> PlaceHolderVar evaluated at {c,d} when the query has grouping sets. So
> c and d must be joined first, and the only legal 4-way join is
> {b,a} + {c,d}. No join clause connects these two. In the bushy loop of
> join_search_one_level() the pair is considered only with {b,a} as
> old_rel, since {b,a} comes first in the level-2 list. {b,a} is skipped
> there because it has no join clauses and has_join_restriction() is
> false for it: it contains its outer join, and a joinrel's
> lateral_referencers is always NULL. The 5-way and 6-way forms fail the
> same way, because there the pair is considered only with the smaller
> side, {b,a} or {b,a,f}, as old_rel.
>
Thanks for the report and the detailed analysis. I investigated this
and reproduced the problem.
The grouping-sets processing causes the pulled-up lateral subquery
output to be represented by a PlaceHolderVar.
In the original example, the resulting PlaceHolderInfo looks roughly like this:
[ph_eval_at] Bitmapset [7 8] ({c, d})
[ph_lateral] Bitmapset [2 3] ({a, outer-join relid})
The value is evaluated at the join of c and d, but it depends on a
value supplied by the completed outer join between b and a. Therefore,
the only usable final join is the bushy join
{b, a, outer-join relid} + {c, d}
No ordinary join clause exists between these two sides.
The problem is that join_search_one_level() discards the first side
before considering that pair. In the bushy-join loop, it has this
preliminary check:
if (old_rel->joininfo == NIL &&
!old_rel->has_eclass_joins &&
!has_join_restriction(root, old_rel))
continue;
For the completed b/a outer join, joininfo is empty, and there are no
relevant EC joins.
has_join_restriction() also returns false.
The outer join is already contained in the joinrel; its lateral_relids
and lateral_referencers are both empty, and the joinrel is not a
subset of the PHV's ph_eval_at set.
However, that joinrel contains all the relations in the PHV's
ph_lateral set, so it supplies the lateral parameters required to
evaluate the PHV at {c,d}.
If the pair reaches have_join_order_restriction(), that function
recognizes the relationship and the join can be built successfully.
The preliminary one-sided check prevents that from happening.
This is especially visible for the 2+2 case because each unordered
pair is considered only once.
The b/a joinrel appears first in the level-2 list and is skipped as
old_rel; when the c/d joinrel is reached, the search doesn't look back
at b/a.
The larger examples fail for the same reason, with the smaller
provider-side joinrel being skipped.
I considered a few possible fixes.
First, removing the preliminary check from the bushy-join loop fixes
the problem, and all regression tests pass.
The pairwise checks already reject unrelated combinations. However,
this makes the planner examine more bushy-join pairs and defeats the
purpose of the existing pruning heuristic, so it seems too broad.
Second, I tried teaching has_join_restriction() to return true when a
relation contains a PHV's complete ph_lateral set.
That also fixes the bug, but it produced three plan changes in join.sql.
This also changes the classification of such relations in other parts
of join search, while the missing case is specific to bushy-join
pruning here.
The attached patch therefore keeps the existing pruning and adds a
local exception for a joinrel that provides all lateral parameters
required by a PHV whose evaluation relations have not yet been joined.
The preliminary check allows such a relation, after which the existing
pairwise have_join_order_restriction() test determines whether a
particular bushy join should be attempted.
The standard regression tests pass without plan changes.
Any thoughts?
--
Thanks,
Tender Wang
Re: BUG #19798: failed to build any 4-way joins
От:
Joao Rito <joaovictor.rito@gmail.com>
Дата:
Hi Tender, I tested your patch on current master (81b2179b492, built with cassert and tap tests) and it applies cleanly. On master the reproducer from the report (ROLLUP over a LATERAL subquery that references the nullable side of a LEFT JOIN) fails with "failed to build any 4-way joins", and two more variants I wrote fail with the same error, one of them also with "failed to build any 5-way joins". With the patch all of them run, and for the cases where I wrote an equivalent UNION ALL query (the reproducer and two of the variant queries), the results match. The regress suite passes (243 tests). What I did not test: other forms such as CUBE, GROUPING SETS and RIGHT JOIN (I only ran the cases above), the isolation and tap suites, pgindent, the docs, the back branches, other platforms (I ran one Linux build), and the effect on plan quality or planning time. Small suggestions: the patch has no regression test, so it could add one with the reproducer to join.sql or groupingsets.sql. I have no objection to the change in joinrels.c from what I could test. Regards, Joao Rito