DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:cc:content-type:content-transfer-encoding;
	b=ouDOtEDBjxqJ3Wa1ZEFkpIJMWsoryq/i3gSC/6GDQaRQRIncTQ2pEyZ+fX1JTb2SWU
	eLvstrPZO18mbOMXwNwM298pJNMGxv0XUT0bjq0ttGbwbTriyE42EhhVBI/1p/mw05aD
	/8/sOYJePzkEP6E7JduQy7O0JMFXHaWpizE0U=
MIME-Version: 1.0
In-Reply-To: <49D3B56D.9050802@zg.htnet.hr>
References: <49D3969F.4030701@zg.htnet.hr> <7884.1238606350@sss.pgh.pa.us>
	<49D3B56D.9050802@zg.htnet.hr>
Date: Wed, 1 Apr 2009 17:14:43 -0400
Message-ID: <603c8f070904011414ld61c45dj3ce3cb7d8955dde6@mail.gmail.com>
Subject: Re: self join revisited
From: Robert Haas <robertmhaas@gmail.com>
To: Rikard Pavelic <rikard.pavelic@zg.htnet.hr>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, pgsql-performance@postgresql.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

> Can I try again? :)
>
> How hard would it be to teach the planner about preserving uniqueness of
> relations in subqueries?
> And using that information to remove unnecessary self joins on unique sets?
>
> I can try to rewrite some queries to test it on real data for how much
> gain it would provide.

I think join removal is a swell idea.  In fact, I went so far as to
post a patch to implement it.  :-)

http://archives.postgresql.org/message-id/603c8f070901181956j9541113xe68df5985d558a97@mail.gmail.com

It's a slightly different problem, because I'm looking at removing
left joins that provably don't change the output set due to a
sufficiently strong uniqueness contraint on the nullable side of the
join, and you're looking at removing self-joins that provably don't
change the output set, which I believe requires establishing that all
the columns of some unique index are constrained to be equal between
the two copies of the table.  But the two problems are very similar in
that you need an efficient way to assess whether there's an adequate
unique constraint, and some of the infrastructure could probably be
shared.

The problem from a coding perspective seems to be how and where to do
the test for unique-ness.  In either the left-join case or the
self-join case, you need to verify that one of the relations involved
has a unique index whose column list is equal to or a superset of the
available merge-joinable clauses (or perhaps hash-joinable clauses). I
ended up putting the logic in sort_inner_and_outer(), but that's
making the decision to drop the join fairly late in the game.  It
would be nice to make it earlier, before we start the dynamic
programming algorithm, especially for self-join removal, where
throwing away the join after it's been constructed involves moving the
quals around.

create_unique_path() also does some interesting stuff in this area,
but I haven't figured out how much of that might be applicable to join
removal.

...Robert