Dead-end joins from LATERAL references across outer joins

This is a long one, sorry. The short version: join_is_legal()
can accept a join whose lateral parameter can never be supplied, and
that makes the planner fail with "failed to build any N-way joins".
Below is my analysis of why this happens and a proposal for how to
catch it in general, which is what I'd like to discuss. Details
below.

The query below (found by Claude) fails with "ERROR: failed to build
any 5-way joins" in v14 to master.

create table t (a int, b int);

select 1 from t t1 left join (t t2 cross join t t3) on true
cross join lateral generate_series(t3.a, 1) g4(k)
left join lateral generate_series(g4.k, 2) g5(k) on t2.a = 1;

Here, the clause of O9 (the outer join with relid 9) is strict for t2,
so identity 3 allows O9 to commute into O5's RHS, and the join t2/g5
is legal as far as outer join ordering goes. But g5 references g4
laterally, so the t2/g5 join is parameterized by g4 and can only be
used on the inside of a nestloop with g4 on the outside. IOW, the
t2/g5 join waits for g4.

Now, g4 references t3, which is in O5's RHS, while g4 itself is not.
So g4 must see t3 as nulled by O5, which means g4 has to be joined
above O5. g4 waits for O5.

And O5 has t2 in its RHS. Once t2 is joined with g5, O5 can only be
formed on top of the t2/g5 join. O5 waits for the t2/g5 join.

That's a cycle!! Every path for the t2/g5 join requires a parameter
that can never be supplied, so the join can never be part of a
complete plan. That by itself would just be wasted work, but the
clauseless-join heuristics in join_search_one_level() take a legal
join with a join clause as evidence that some other join rel need not
be formed. Here the join rels that the workable join orders need are
never built, and the top level ends up empty.

The general pattern is this. Once a proposed join contains a rel that
an outer join needs, that outer join can no longer be formed strictly
outside the join; it has to join into the join's own join tree. Any
rel that needs the output of that outer join then has to join into the
same tree, so it cannot supply a parameter to the join.
join_is_legal() already searches for rels that are forced into the
join's own join tree, but it only follows outer joins whose LHS
overlaps the rels found so far, and lateral references to rels found
so far (newly added in b84ad0cd9). Neither catches O5 here, whose LHS
is t1, nor g4, which references t3. (Commit 55fa1b067 fixed the
special case where the outer join's relid shows up in the minimum
parameterization directly; this is the general case of that.)

I've been thinking about how to fix the general case for a while, but
still can't quite wrap my head around all the details. Here is what I
have so far. I'd like to hear what others think.

To detect the general case we need two pieces of information about
each outer join that we don't have today.

One piece is max_righthand, which is the set of rels that can end up
within the outer join's RHS. That is its syn_righthand, plus the RHS
of any upper outer join that identity 3 can move into it, and so on
recursively. This is narrower than commute_above_l, which is filled
in before we know whether the upper join's LHS actually lies within
the lower join's RHS.

The reason we need it is that syn_righthand is the wrong thing to test
when asking whether a rel has to be above an outer join. A rel that
identity 3 can move into the RHS doesn't have to be above the outer
join, even though it is outside syn_righthand. And a rel that is
outside max_righthand but references a rel inside it does have to be
above the outer join: the referenced rel ends up either within the
RHS, where the referencing rel sees it nulled, or above the outer
join, in which case the referencing rel must be above it as well. g4
is the simplest case of this: it is outside O5's max_righthand and
references t3.

We also need it in rule 2 below. When an outer join has to be formed
above the proposed join, its RHS rels normally can't supply parameters
to the join. But if the proposed join itself can be within that RHS,
they can. For example:

select 1 from t t1 left join (t t2 cross join t t3) on true
left join lateral generate_series(t3.a, 1) g4(k) on t2.a = 1;

Here the t2/g4 join is parameterized by t3, and O5 has to be formed
above it, since t2 is in O5's RHS. But identity 3 lets the whole
t2/g4 join sit within O5's RHS, so t3 can still be joined to it there,
and in fact the planner picks t1 left join (t3 nestloop (t2 left join
g4)). Without max_righthand we would add O5's RHS to the set and
reject this join.

The other piece is required_rels, which is the set of relids that must
be joined together before the outer join can be formed: min_lefthand
plus min_righthand, plus the inputs of any lower outer join that this
set includes or spans, where "spans" means the set has a rel from the
lower join's RHS together with a rel that cannot be within it. The
min sets alone aren't enough, because identity 3 strips the lower
join's relid out of them even when the upper join cannot actually
commute into the lower join's RHS. For example:

select 1 from t t1 left join (t t2 cross join t t3) on true
cross join t t4
left join t t5 on t2.a = t5.a and t4.a = t5.b
left join lateral generate_series(t5.b, 1) g6(k) on t3.a = g6.k;

The clause of O9 is strict for t2 and doesn't mention t1, so
make_outerjoininfo() treats it as commutable with O5 and its
min_lefthand is just {t2, t4}. But O9 can't really be formed within
O5's RHS, because t4 isn't there; it needs t2 and t4 joined together,
and that can only happen once O5 is formed. So O9's required_rels has
to include all of O5's inputs, t3 among them. Now consider the t3/g6
join, which is parameterized by t5. With the min sets alone nothing
would tell us that O9 can't be formed strictly outside it. With
required_rels, rule 1 below adds O9 because of t3, rule 2 then adds t5
because the t3/g6 join can't be within O9's RHS, and the join is
rejected. On master it is accepted and the query fails the same
error.

With those two pieces of information, the search in join_is_legal()
applies three rules until no more rels can be added:

1. An outer join whose required_rels overlaps the set cannot be formed
strictly outside the join: add its relid. This subsumes the check
from 55fa1b067, which is removed.

2. If an outer join's LHS overlaps the set, add its RHS, as before.
Also, if its relid is in the set and the join rel cannot be within its
max_righthand, the outer join will be formed above the join rel, so
add its RHS too.

3. Add input rels that laterally reference a rel in the set, as
before, plus input rels that need the output of an outer join in the
set: those outside its max_righthand that reference a rel within it.

For the first query, the search starts from {t2, g5}. Rule 1 adds O5
since it needs t2, rule 3 adds g4 since it needs O5's output, and g4
is the parameter the join needs, so the join is rejected.

Attached is a patch that implements this. I'd like to hear what
people think about it, in particular: 1) whether the rules make sense;
2) whether there are still cases where we accept a dead-end join; and
3) whether the rules can ever reject a legal join.

I don't intend to back-patch this. It is fairly invasive, and the new
SpecialJoinInfo fields would break ABI. The latter could be worked
around by recomputing the information locally where it is needed, but
the invasiveness is the main concern.

- Richard