Re: [sqlsmith] Failed to generate plan on lateral subqueries

Amit Langote <Langote_Amit_f8(at)lab(dot)ntt(dot)co(dot)jp> writes:
> On 2015/12/07 2:52, Andreas Seltenreich wrote:
>> I've added new grammar rules to sqlsmith and improved some older ones.
>> This was rewarded with a return of "failed to generate plan" errors.
>> The failing queries all contain a lateral subquery.

> * Removing the limit (fetch first...) in lateral sub-queries makes the
> errors go away for all above queries.

Yeah. I've been able to reduce Andreas' first example to

select * from
text_tbl tt1
left join int8_tbl i8 on i8.q1 = 42,
lateral (select
i8.q2,
tt2.f1
from
text_tbl tt2
limit 1
) as ss
where tt1.f1 = ss.f1;

ERROR: failed to build any 3-way joins

The key features are (1) a subquery with a LATERAL reference to the inner
side of a left join, and (2) a degenerate join condition for the left
join, ie it only references the inner side. (2) causes the planner to
see the left join as a clauseless join, so it prefers to postpone it
as long as possible. In this case it will try to join tt1 to ss first,
because the WHERE condition is an inner-join clause linking those two,
and inner joins are allowed to associate into the lefthand sides of left
joins. But now it's stuck: because of the lateral reference to i8, the
only way to generate a join between tt1+ss and i8 is for i8 to be on the
outside of a nestloop, and that doesn't work because nestloop can only
handle LEFT outer joins not RIGHT outer joins. So that's a dead end;
but because it thought earlier that tt1 could be joined to ss, it did not
generate the tt1+i8 join at all, so it fails to find any way to build the
final join.

If you remove the LIMIT then the sub-select can be flattened, causing
the problem to go away because there's no longer a lateral ordering
constraint (there's not actually any need to evaluate i8.q2 while
scanning tt2).

I think the way to fix this is that join_is_legal() should be taught to
notice whether the proposed join would have unresolved lateral references
to other relations that it will need to be on the outside of any join to.
If join_is_legal were to reject tt1+ss then the has_legal_joinclause
tests at the bottom of have_join_order_restriction would fail, so
have_join_order_restriction would correctly report that there's a
constraint forcing tt1 and i8 to be joined directly despite the lack
of a join clause.

Andreas' second example is a similar situation, with the addition of a
PlaceHolderVar in the sub-select (since it has a non-strict output
variable that has to bubble up through an outer join). In this case
we fail earlier, because although join_is_legal again lets us try to
make a join that can't be useful, the check_hazardous_phv() test that
I recently added to joinpath.c recognizes that there's no safe way
to make that join, so it rejects all the possible join paths and we
end up with a joinrel with no paths, leading to the different error
message.

I think that fixing join_is_legal() may be enough to take care of
this case too, but I need to think about whether there could still be
any cases in which check_hazardous_phv() would reject all paths for
a joinrel. It might be that that logic is in the wrong place and
needs to be folded into join_is_legal(), or that join_is_legal()
*also* has to account for this (which would be annoying).

I've not traced through the third example in detail, but it looks
like it's just a variant of these problems.

regards, tom lane