Re: LATERAL

On Wed, Sep 9, 2009 at 11:25 PM, Andrew Gierth
<andrew(at)tao11(dot)riddles(dot)org(dot)uk> wrote:
>  >> 4. LATERAL allows some optimizations that aren't currently done, either
>  >> by explicitly rewriting the query, or (in theory) the optimizer itself
>  >> could consider a lateral plan (I believe Oracle does this). This would
>  >> apply to queries of this form:
>  >>
>  >> SELECT ... FROM t1 LEFT JOIN (t2 JOIN t3 ON (t2.a=t3.a)) on (t1.a=t2.a);
>  >>
>  >> which currently forces the t2/t3 join to occur first even where t1 is
>  >> small; this could be rewritten with LATERAL as:
>  >>
>  >> SELECT ...
>  >>        FROM t1
>  >>        LEFT JOIN LATERAL (select * from t2 join t3 on (t2.a=t3.a)
>  >>                            where t2.a=t1.a) s
>  >>        ON true;
>
>  Robert> Well, you haven't actually commuted the joins here - how do
>  Robert> you have in mind for PostgreSQL to execute this?  I'm
>  Robert> guessing that it's something like a nest loop with t1 as the
>  Robert> outer side and the lateral subquery as the inner side, so
>  Robert> that the executor repeatedly executes
>  Robert> "select * from t2 join t3 on t2.a = t3.a where t2.a = $1"?
>
> Yup.
>
> The current execution plans for this type of query are completely
> disastrous if t1 is small (or qualified so as to be small) and t2 and
> t3 are large. Having LATERAL would allow the query to be rewritten to
> perform reasonably; a bonus would be for the planner to consider the
> lateral join automatically without requiring it to be explicitly
> requested.

I've been turning this one over in my head. It seems to me that this
is very similar to what we already do with inner index-scans, only
generalized to joinrels. When we consider nested loop plans in
match_unsorted_outer(), we really consider two quite different types
of plans - call them parameterized and unparameterized. The
unparameterized variants considered regardless of the details of the
inner plan, and basically rescan the same identical inner side once
per outer row, possibly with a materialize node interposed. The
parameterized variants are what the inner index-scan code is looking
at: they also involve rescanning the inner path, but not the same set
of tuples every time. Instead, we look for cases where an index is
available that can support a lookup of the specific values that the
outer side needs on each pass as an index condition.

Currently, however, we only consider this possibility when the inner
rel is NOT a joinrel. It seems like it might be possible to change
this, but it doesn't look straightforward. When the inner rel is a
baserel, there's really nothing to do except grovel through the
indexes looking for something useful, and then estimate the cost of
using it. When the inner rel is a joinrel, it's a lot more
complicated. A parameterized nested loop might be right even if only
some of the rels making up the joinrel are indexed (imagine t2 IJ t3
IJ t4 where t2 and t3 are large and indexed and t4 is small and
unindexed). In addition, the relations making up the inner rel could
be joined in any order and using a variety of strategies. The path
that is best when trying to suck down the ENTIRE inner rel doesn't
necessarily bear any resemblence to the plan that is best when trying
to suck down only a part of it.

To some extent, this seems like a tangent as far as LATERAL is
concerned: I think the primary reason why people want LATERAL
(certainly, why I want it) is for SRFs, for which there isn't any
choice of execution plan anyway. But it's certainly an interesting
optimization problem, and I wish I had some better ideas on how to
tackle it.

...Robert