From: Antonin Houska <ah@cybertec.at>
To: Andy Fan <zhihuifan1213@163.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
    David Rowley <dgrowleyml@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>,
    Ashutosh Bapat <ashutosh.bapat.oss@gmail.com>,
    jian he <jian.universality@gmail.com>
Subject: Re: UniqueKey v2
In-reply-to: <3739.1715594150@antos>
References: <7mlamswjp81p.fsf@e18c07352.et15sqa> <871qczm9oc.fsf@163.com> <7971.1713526758@antos> <875xvrnzga.fsf@163.com> <3739.1715594150@antos>
Comments: In-reply-to Antonin Houska <ah@cybertec.at>
   message dated "Mon, 13 May 2024 11:55:50 +0200."
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <4985.1715622135.1@antos>
Content-Transfer-Encoding: quoted-printable
Date: Mon, 13 May 2024 19:42:15 +0200
Message-ID: <4986.1715622135@antos>
Archived-At: <https://www.postgresql.org/message-id/4986.1715622135%40antos>
Precedence: bulk

Antonin Houska <ah@cybertec.at> wrote:

> Andy Fan <zhihuifan1213@163.com> wrote:
> > >
> > > * Combining the UKs
> > >
> > >   IMO this is the most problematic part of the patch. You call
> > >   populate_joinrel_uniquekeys() for the same join multiple times,
> > =

> > Why do you think so? The below code is called in "make_join_rel"
> =

> Consider join of tables "a", "b" and "c". My understanding is that
> make_join_rel() is called once with rel1=3D{a} and rel2=3D{b join c}, th=
en with
> rel1=3D{a join b} and rel2=3D{c}, etc. I wanted to say that each call sh=
ould
> produce the same set of unique keys.
> =

> I need to check this part more in detail.

I think I understand now. By calling populate_joinrel_uniquekeys() for var=
ious
orderings, you can find out that various input relation unique keys can
represent the whole join. For example, if the ordering is

A JOIN (B JOIN C)

you can prove that the unique keys of A can be used for the whole join, wh=
ile
for the ordering

B JOIN (A JOIN C)

you can prove the same for the unique keys of B, and so on.

> > Is your original question is about populate_joinrel_uniquekey_for_rel
> > rather than populate_joinrel_uniquekeys? We have the below codes:
> > =

> > 	outeruk_still_valid =3D populate_joinrel_uniquekey_for_rel(root, join=
rel, outerrel,
> > 															 innerrel, restrictlist);
> > 	inneruk_still_valid =3D populate_joinrel_uniquekey_for_rel(root, join=
rel, innerrel,
> > 															 outerrel, restrictlist);
> > =

> > This is mainly because of the following theory. Quoted from
> > README.uniquekey. Let's called this as "rule 1".
> > =

> > """
> > How to maintain the uniquekey?
> > -------------------------------
> > .. From the join relation, it is maintained with two rules:
> > =

> > - the uniquekey in one side is still unique if it can't be duplicated
> >   after the join. for example:
> > =

> >   SELECT t1.pk FROM t1 JOIN t2 ON t1.a =3D t2.pk;
> >   UniqueKey on t1:  t1.pk
> >   UniqueKey on t1 Join t2:  t1.pk
> > """
> > =

> > AND the blow codes:
> > =

> > =

> > 	if (outeruk_still_valid || inneruk_still_valid)
> > =

> > 		/*
> > 		 * the uniquekey on outers or inners have been added into joinrel so
> > 		 * the combined uniuqekey from both sides is not needed.
> > 		 */
> > 		return;
> > =

> > =

> > We don't create the component uniquekey if any one side of the boths
> > sides is unique already. For example:
> > =

> > "(t1.id) in joinrel(t1, t2) is unique" OR "(t2.id) in joinrel is
> > unique", there is no need to create component UniqueKey (t1.id, t2.id)=
;  =

> =

> ok, I need to check more in detail how this part works.

This optimization makes sense to me.

> > >
> > >   Of course one problem is that the number of combinations can grow
> > >   exponentially as new relations are joined.
> > =

> > Yes, that's why "rule 1" needed and "How to reduce the overhead" in
> > UniqueKey.README is introduced. =


I think there should yet be some guarantee that the number of unique keys =
does
not grow exponentially. Perhaps a constant that allows a relation (base or
join) to have at most N unique keys. (I imagine N to be rather small, e.g.=
 3
or 4.) And when picking the "best N keys", one criterion could be the numb=
er
of expressions in the key (the shorter key the better).

> > >
> > >   2) Check if the join relation is single-row
> > >
> > >   I in order to get rid of the dependency on 'restrictlist', I think=
 you can
> > >   use ECs. Consider a query from your regression tests:
> > >
> > > CREATE TABLE uk_t (id int primary key, a int not null, b int not nul=
l, c int, d int, e int);
> > >
> > > SELECT distinct t1.d FROM uk_t t1 JOIN uk_t t2 ON t1.e =3D t2.id and=
 t1.id =3D 1;
> > >
> > >   The idea here seems to be that no more than one row of t1 matches =
the query
> > >   clauses. Therefore, if t2(id) is unique, the clause t1.e=3Dt2.id e=
nsures that
> > >   no more than one row of t2 matches the query (because t1 cannot pr=
ovide the
> > >   clause with more than one input value of 'e'). And therefore, the =
join also
> > >   produces at most one row.
> > =

> > You are correct and IMO my current code are able to tell it is a singl=
e
> > row as well.
> > =

> > 1. Since t1.id =3D 1, so t1 is single row, so t1.d is unqiuekey as a
> > consequence.
> > 2. Given t2.id is unique, t1.e =3D t2.id so t1's unqiuekey can be kept
> > after the join because of rule 1 on joinrel. and t1 is singlerow, so t=
he
> > joinrel is singlerow as well.

ok, I think I understand now.

-- =

Antonin Houska
Web: https://www.cybertec-postgresql.com