Re: join removal

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: Greg Stark <stark(at)mit(dot)edu>, "<pgsql-hackers(at)postgresql(dot)org>" <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: join removal
Date: 2010-03-27 20:11:37
Message-ID: 15142.1269720697@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Sat, Mar 27, 2010 at 10:50 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> 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.

After further reflection I think you're right, especially now that we
have that restriction against pushed-down join clauses in there.
Removal could only succeed when the rel's Vars are used just in the
left join's own join clauses, which means that only the min LHS can be
needed in order to compute those clauses.

> 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.

I think you just remove the RHS rel from the joinlist.

> 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.

I'm not seeing how that would occur or would matter, but the worst case
answer is to restart the scan of the SpecialJoinInfos from scratch any
time you succeed in doing a join removal.

> 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.

Agreed. Just deleting one rel from the join search space is an enormous
win.

regards, tom lane

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Robert Haas 2010-03-27 20:19:48 Re: join removal
Previous Message Simon Riggs 2010-03-27 19:36:47 Re: [COMMITTERS] pgsql: Augment WAL records for btree delete with GetOldestXmin() to