From: Ronan Dunklau <ronan.dunklau@aiven.io>
To: Greg Stark <stark@mit.edu>, Andrey Lepikhov <a.lepikhov@postgrespro.ru>
Cc: Andres Freund <andres@anarazel.de>,
 Laurenz Albe <laurenz.albe@cybertec.at>,
 Hywel Carver <hywel@skillerwhale.com>,
 PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Removing unneeded self joins
Date: Thu, 19 May 2022 13:47:36 +0200
Message-ID: <13021914.uLZWGnKmhe@aivenronan>
Organization: aiven
In-Reply-To: <a1d6290c-44e0-0dfc-3fca-66a68b3109ef@postgrespro.ru>
References: <64486b0b-0404-e39e-322d-0801154901f3@postgrespro.ru>
 <2537176.Lt9SDvczpP@aivenronan>
 <a1d6290c-44e0-0dfc-3fca-66a68b3109ef@postgrespro.ru>
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"
Archived-At: 
 <https://www.postgresql.org/message-id/13021914.uLZWGnKmhe%40aivenronan>
Precedence: bulk

Le jeudi 19 mai 2022, 12:48:18 CEST Andrey Lepikhov a =E9crit :
> On 5/17/22 19:14, Ronan Dunklau wrote:
> > Le vendredi 13 mai 2022, 07:07:47 CEST Andrey Lepikhov a =E9crit :
> >> New version of the feature.
> >> Here a minor bug with RowMarks is fixed. A degenerated case is fixed,
> >> when uniqueness of an inner deduced not from join quals, but from a
> >> baserestrictinfo clauses 'x=3Dconst', where x - unique field.
> >> Code, dedicated to solve second issue is controversial, so i attached
> >> delta.txt for quick observation.
> >> Maybe we should return to previous version of code, when we didn't spl=
it
> >> restriction list into join quals and base quals?
> >=20
> > Hello,
> >=20
> > I tried to find problematic cases, which would make the planning time g=
row
> > unacceptably, and couldn't devise it.
> >=20
> > The worst case scenario I could think of was as follows:
> >   - a query with many different self joins
> >   - an abundance of unique indexes on combinations of this table columns
> >   to
> >=20
> > consider
> >=20
> >   - additional predicates on the where clause on columns.
>=20
> Looking into the patch I can imagine, that the most difficult case is
> when a set of relations with the same OID is huge, but only small part
> of them (or nothing) can be removed.
> Also, removing a clause from restrictinfo list or from equivalence class
> adds non-linear complexity. So, you can dig this way ).
>=20
> > The base table I used for this was a table with 40 integers. 39 unique
> > indexes were defined on every combination of (c1, cX) with cX being
> > columns c2 to c40.
> >=20
> > I turned geqo off, set from_collapse_limit and join_collapse_limit to
> > unreasonably high values (30), and tried to run queries of the form:
> >=20
> > SELECT * FROM test_table t1
> > JOIN test_table tX ON t1.c1 =3D tX.c1 AND t1.c[X+2] =3D tX.cX
> > ...
> > JOIN test_table tX ON t1.c1 =3D tX.c1 AND t1.c[X+2] =3D tX.cX.
> >=20
> > So no self join can be eliminated in that case.
>=20
> I think, you should compare t1.cX with tX.cX to eliminate self-join.
> Cross-unique-index proof isn't supported now.

Yes, that's the point. I wanted to try to introduce as much complexity as I=
=20
could, without actually performing any self join elimination. The idea was =
to=20
try to come up with the worst case scenario.
>=20
> > The performance was very similar with or without the GUC enabled. I tes=
ted
> > the same thing without the patch, since the test for uniqueness has been
> > slightly altered and incurs a new allocation, but it doesn't seem to
> > change.
> >=20
> > One interesting side effect of this patch, is that removing any unneeded
> > self join cuts down the planification time very significantly, as we
> > lower the number of combinations to consider.
>=20
> Even more - removing a join we improve cardinality estimation.
>=20
> > As for the code:
> >   - Comments on relation_has_unique_index_ext and
> >   relation_has_unique_index_for>=20
> > should be rewritten, as relation_has_unique_index_for is now just a
> > special
> > case of relation_has_unique_index_ext. By the way, the comment would
> > probably be better read as: "but if extra_clauses isn't NULL".
> >=20
> >   - The whole thing about "extra_clauses", ie, baserestrictinfos which
> >   were
> >=20
> > used to determine uniqueness, is not very clear. Most functions where t=
he
> > new argument has been added have not seen an update in their comments,
> > and the name itself doesn't really convey the intented meaning: perhaps
> > required_non_join_clauses ?
> >=20
> > The way this works should be explained a bit more thoroughly, for examp=
le
> > in remove_self_joins_one_group the purpose of uclauses should be
> > explained. The fact that degenerate_case returns true when we don't have
> > any additional base restrict info is also confusing, as well as the
> > degenerate_case name.
> Agree,
> but after this case thoughts wander in my head: should we make one step
> back to pre-[1] approach? It looks like we have quite similar changes,
> but without special function for a 'degenerate case' detection and
> restrictlist splitting.

I'll take a look at that one.=20

>=20
> > I'll update if I think of more interesting things to add.
>=20
> Thank you for your efforts!
>=20
> See in attachment next version which fixes mistakes detected by
> zyu@yugabyte.com.
>=20
> [1]
> https://www.postgresql.org/message-id/raw/CAApHDvpggnFMC4yP-jUO7PKN%3DfXe=
ErW
> 5bOxisvJ0HvkHQEY%3DWw%40mail.gmail.com


=2D-=20
Ronan Dunklau