To: Simon Riggs <simon@2ndquadrant.com>
cc: pgsql-hackers@postgreSQL.org
Subject: Re: [PERFORM] Outer joins and equivalence 
In-reply-to: <1212436031.4120.400.camel@ebony.site> 
References: <1211918358.4489.257.camel@ebony.site>
	<14085.1211924592@sss.pgh.pa.us>
	<1212426644.4120.378.camel@ebony.site>
	<1212436031.4120.400.camel@ebony.site>
Comments: In-reply-to Simon Riggs <simon@2ndquadrant.com>
	message dated "Mon, 02 Jun 2008 20:47:11 +0100"
Date: Wed, 04 Jun 2008 22:18:12 -0400
Message-ID: <8599.1212632292@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

[ redirecting thread from -performance to -hackers ]

Simon Riggs <simon@2ndquadrant.com> writes:
> I've got a test case which shows something related and weird, though not
> the exact case.

> The queries shown here have significantly different costs, depending
> upon whether we use tables a or b in the query. Since a and b are
> equivalent this result isn't expected at all.

Hmm.  I had been guessing that there was something about your original
query that prevented the system from applying best_appendrel_indexscan,
but after fooling with this a bit, I don't believe that's the issue
at all.  The problem is that these two cases "should" be equivalent:

  select ... from a join b on (a.id = b.id) left join c on (a.id = c.id);

  select ... from a join b on (a.id = b.id) left join c on (b.id = c.id);

but they are not seen that way by the current planner.  It correctly
forms an EquivalenceClass consisting of a.id and b.id, but it cannot put
c.id into that same class, and so the clause a.id = c.id is just left
alone; there is noplace that can generate "b.id = c.id" as an
alternative join condition.  This means that (for the first query)
we can consider the join orders "(a join b) leftjoin c" and
"(a leftjoin c) join b", but there is no way to consider the join
order "(b leftjoin c) join a"; to implement that we'd need to have the
alternative join clause available.  So if that join order is
significantly better than the other two, we lose.

This is going to take a bit of work to fix :-(.  I am toying with the
idea that we could go ahead and put c.id into the EquivalenceClass
as a sort of second-class citizen that's labeled as associated with this
particular outer join --- the implication being that we can execute the
outer join using a generated clause that equates c.id to any one of the
first-class members of the EquivalenceClass, but above the outer join
we can't assume that c.id hasn't gone to null, so it's not really equal
to anything else in the class.  I think it might also be possible
to get rid of the reconsider_outer_join_clauses() kluge in favor of
driving transitive-equality-to-a-constant off of this representation.

However there's a larger issue here, which is the very identity of an
outer join :-(.  Currently, for the first query above, the left join
is defined as being between a and c, with a being the minimum
left-hand-side needed to form the join.  To be able to handle a case
like this, it seems that the notion of a "minimum left hand side"
falls apart altogether.  We can execute the OJ using either a or b
as left hand side.  So the current representation of OuterJoinInfo,
and the code that uses it to enforce valid join orders, needs a serious
rethink.

Looks like 8.4 development material to me, rather than something we
can hope to back-patch a fix for...

			regards, tom lane