From: Tom Lane <tgl@sss.pgh.pa.us>
To: David Rowley <david.rowley@2ndquadrant.com>
cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>,
        Simon Riggs <simon@2ndquadrant.com>,
        PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: Performance improvement for joins where outer side is unique
In-reply-to: <13653.1457731978@sss.pgh.pa.us>
References: <20150320.121140.148610378.horiguchi.kyotaro@lab.ntt.co.jp>
 <CAPpHfdviphQFjk-gaGZGGxLAyt=YuVdJLnntsxOKnU296s9u-Q@mail.gmail.com>
 <CAKJS1f-=1y0-f5FFV2_r7LtS+CL2Lw-nhJjXB3O_0FmBqnK=3A@mail.gmail.com>
 <27152324.eFKJb4Khb5@dinodell> <8608754a32d1325c2f83ba8b1df71585@xs4all.nl>
 <55DA1F9F.5040204@2ndquadrant.com>
 <CAKJS1f-9UTo6fA+h8rojd30CujSKscZamLn5YnKw5+ASbV0Wwg@mail.gmail.com>
 <5085.1440375543@sss.pgh.pa.us>
 <CAKJS1f_8hrzTDCu0pwERWj_dLZu-6DYFQJAtNT+vM6UeOn0kHw@mail.gmail.com>
 <8907.1440383377@sss.pgh.pa.us>
 <CAKJS1f8JCt15ngEP8sZO-JYYT8mS6HUP_CT0T6S_0ogk1kQt+Q@mail.gmail.com>
 <CAKJS1f_4hm3qwKeHYKftd+BQuYBgdNR+rk+XP_JW9EY-ALHZbQ@mail.gmail.com>
 <56718B15.6060507@2ndquadrant.com>
 <CAKJS1f_i7dGh9ytc0DuaX3JJaN7Gp9AGXNbdtWjj0PkPzNzUeg@mail.gmail.com>
 <5671FF0D.2010403@2ndquadrant.com>
 <CANP8+j+vxfEf3dqhnzKAnDopnnUM-Zjb90gNT=haEQNQePj9Mw@mail.gmail.com>
 <CAKJS1f8MpcL4_oS+n-vmnisd_8OMuZR2vyLETOF7ABSLk_iNZg@mail.gmail.com>
 <56A25A72.2090505@2ndquadrant.com> <CAKJS1f-V7xEh6+!
 YHrCRNaZzbk7mbgPvi9MdXTCD8eJ=ROuq2Mg@mail.gmail.com>
 <24304.1457482780@sss.pgh.pa.us>
 <CAKJS1f-qN8NVT456XT6-NW+Vc_n0-jfCVtaQio0JoOWzP6F2ig@mail.gmail.com>
 <13653.1457731978@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Fri, 11 Mar 2016 16:32:58 -0500"
Date: Fri, 11 Mar 2016 17:43:10 -0500
Message-ID: <16023.1457736190@sss.pgh.pa.us>
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

I wrote:
> I wondered why, instead of inventing an extra semantics-modifying flag,
> we couldn't just change the jointype to *be* JOIN_SEMI when we've
> discovered that the inner side is unique.

BTW, to clarify: I'm not imagining that we'd make this change in the
query jointree, as for example prepjointree.c might do.  That would appear
to add join order constraints, which we don't want.  But I'm thinking that
at the instant where we form a join Path, we could change the Path's
jointype to be JOIN_SEMI or JOIN_SEMI_OUTER if we're able to prove the
inner side unique, rather than annotating the Path with a separate flag.
Then that representation is what propagates forward.

It seems like the major intellectual complexity here is to figure out
how to detect inner-side-unique at reasonable cost.  I see that for
LEFT joins you're caching that in the SpecialJoinInfos, which is probably
fine.  But for INNER joins it looks like you're just doing it over again
for every candidate join, and that seems mighty expensive.

			regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers