From: Antonin Houska <ah@cybertec.at>
To: pgsql-hackers@postgresql.org
Subject: Re: Performance improvement for joins where outer side is unique
In-reply-to: 
 <CAKJS1f_jRki1PQ4X-9UGKa-wnBhECQLnrxCX5haQzu4SDR_r2Q@mail.gmail.com>
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> <24304.1457482780@sss.pgh
 .pa.us> <CAKJS1f-qN8NVT456XT6-NW+Vc_n0-jfCVtaQio0JoOWzP6F2ig@mail.gmail.com>
 <13653.1457731978@sss.pgh.pa.us> <16023.1457736190@sss.pgh.pa.us>
 <CAKJS1f_jRki1PQ4X-9UGKa-wnBhECQLnrxCX5haQzu4SDR_r2Q@mail.gmail.com>
Comments: In-reply-to David Rowley <david.rowley@2ndquadrant.com>
   message dated "Sat, 12 Mar 2016 23:56:47 +1300."
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Date: Fri, 27 Jan 2017 14:14:04 +0100
Message-ID: <18764.1485522844@localhost>
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

I thought about the patch from the perspective of "grouped relations"
(especially [1]). When looking for the appropriate context within the threa=
d,
I picked this message.

David Rowley <david.rowley@2ndquadrant.com> wrote:

> On 12 March 2016 at 11:43, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >
> > 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 probab=
ly
> > fine.  But for INNER joins it looks like you're just doing it over again
> > for every candidate join, and that seems mighty expensive.

> ... I'll look into that.
>=20
> The other thing I thought of was to add a dedicated list for unique
> indexes in RelOptInfo, this would also allow
> rel_supports_distinctness() to do something a bit smarter than just
> return false if there's no indexes. That might not buy us much though,
> but at least relations tend to have very little unique indexes, even
> when they have lots of indexes.

I'm thinking of a concept of "unique keys", similar to path keys that the
planner already uses. Besides the current evaluation of uniqueness of the
inner side of a join, the planner would (kind of) union the unique keys of =
the
joined rels, ie compute a list of expressions which generates an unique row
throughout the new join result. (Requirement is that each key must be usable
in join expression, as opposed to filter.)

To figure out whether at most one inner row exists per outer row, each uniq=
ue
key of the inner relation which references the outer relation needs to match
an unique key of the outer relation (but it's probably wrong if multiple
unique keys of the inner rel reference the same key of the outer rel).

Like path key, the unique key would also point to an equivalence class. Thus
mere equality of the EC pointers could perhaps be used to evaluate the match
of the inner and outer keys.

Given that rel_is_distinct_for() currently does not accept joins, this chan=
ge
would make the patch more generic. (BTW, with this approach, unique_rels and
non_unique_rels caches would have to be stored per-relation (RelOptInfo), as
opposed to PlannerInfo.)

The reason I'd like the unique keys is that - from the "grouped relation"
point of view - the relation uniqueness also needs to be checked against the
GROUP BY clause. Thus the "unique keys" concept seem to me like an useful
abstraction.

Does this proposal seem to have a serious flaw?

[1]
https://www.postgresql.org/message-id/CAKJS1f_h1CLff92B%3D%2BbdrMK2Nf3EfGWa=
Ju2WbzQUYcSBUi02ag%40mail.gmail.com

--=20
Antonin Houska
Cybertec Sch=C3=B6nig & Sch=C3=B6nig GmbH
Gr=C3=B6hrm=C3=BChlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at


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