Re: join removal

On Sat, Mar 27, 2010 at 10:50 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> I'm not totally sure about this but I think it's possible to do this
>> without a combinatorial search.  Suppose we just iterate over the list
>> of
>> SpecialJoinInfo structures and look for those where jointype is LEFT,
>> delay_upper_joins is false, and min_righthand is a singleton; and then
>> consider the removability of a join between min_lefthand and
>> min_righthand.  I might be missing a case, but I think whatever answer
>> we get from that calculation is the answer, period.  Adding more
>> relations to the LHS won't change anything.
>
> Hmm ... that last isn't obvious to me.  The current computation in
> join_is_removable is clearly capable of making different decisions at
> different join levels, depending on whether any outputs of the RHS are
> seen to be required above the current join.

Right.

> It might be that in
> practice it has to succeed with the min LHS if it's going to succeed
> anywhere, but I'm not convinced.

It's a bit difficult to wrap one's brain around all the cases, but I
think that the statement in question is in fact true. Adding more
rels to the LHS could help to pass the "rels not used above the level
of the join" test by putting more rels under the join. But that begs
the question - how exactly are those rels being used? The only answer
I can see is that they're involved in some join clause between one of
the added tables and the RHS - in which case they should be part of
the min LHS in the first place.

There are a couple of problems with making this approach actually work
that I haven't figured out yet. One is that it's not exactly clear
how you ago about removing the join at this part. In particular, if
you remove one join, it might make some other join that wasn't
previously removable now able to be removed, and it's not exactly
clear to me how to make this method cope with that. But I think it's
worth thinking about because anything based on an O(n) pass over the
SpecialJoinInfo structures should be far cheaper than participating in
the combinatorial explosion that will ensue once we actually begin
testing through all the join orders.

...Robert