Thread: Re: UniqueKey on Partitioned table.

> On Sat, Feb 20, 2021 at 10:25:59AM +0800, Andy Fan wrote:
>
> The attached is a UnqiueKey with EquivalenceClass patch, I just complete the
> single relation part and may have bugs. I just attached it here for design
> review only. and the not-null-attrs is just v1 which we can continue
> discussing on the original thread[2].

Thanks for the patch. After a short look through it I'm a bit confused
and wanted to clarify, now uniquekeys list could contain both Expr and
EquivalenceClass?

On Sat, Mar 27, 2021 at 11:44 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
>
>
> On Sat, Mar 27, 2021 at 3:07 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
>>
>> > On Sat, Feb 20, 2021 at 10:25:59AM +0800, Andy Fan wrote:
>> >
>> > The attached is a UnqiueKey with EquivalenceClass patch, I just complete the
>> > single relation part and may have bugs. I just attached it here for design
>> > review only. and the not-null-attrs is just v1 which we can continue
>> > discussing on the original thread[2].
>>
>> Thanks for the patch. After a short look through it I'm a bit confused
>> and wanted to clarify, now uniquekeys list could contain both Expr and
>> EquivalenceClass?
>
>
> Yes,  That's because I don't want to create a new EquivalenceClass (which
> would make the PlannerInfo->eq_classes longer) if we don't have
> one , then I just used one Expr instead for this case.
> However during the
> test, I found some EquivalenceClass with only 1 EquivalenceMember
> unexpectedly.
>

Pathkeys may induce single member ECs. Why UniqueKeys are an exception?

-- 
Best Wishes,
Ashutosh Bapat

On Tue, 30 Mar 2021 at 02:27, Ashutosh Bapat
<ashutosh.bapat.oss@gmail.com> wrote:
>
> On Sat, Mar 27, 2021 at 11:44 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
> >
> > On Sat, Mar 27, 2021 at 3:07 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> >> Thanks for the patch. After a short look through it I'm a bit confused
> >> and wanted to clarify, now uniquekeys list could contain both Expr and
> >> EquivalenceClass?
> >
> >
> > Yes,  That's because I don't want to create a new EquivalenceClass (which
> > would make the PlannerInfo->eq_classes longer) if we don't have
> > one , then I just used one Expr instead for this case.
> > However during the
> > test, I found some EquivalenceClass with only 1 EquivalenceMember
> > unexpectedly.
> >
>
> Pathkeys may induce single member ECs. Why UniqueKeys are an exception?

I doubt that it should be. get_eclass_for_sort_expr() makes
single-member ECs for sorts.  I imagine the UniqueKey stuff should
copy that... However, get_eclass_for_sort_expr() can often dominate
the planning effort in queries to partitioned tables with a large
number of partitions when the query has an ORDER BY. Perhaps Andy is
trying to sidestep that issue?

I mentioned a few things in [1] on what I think about this.

David

[1] https://www.postgresql.org/message-id/CAApHDvoDMyw=hTuW-258yqNK4bhW6CpguJU_GZBh4x+rnoem3w@mail.gmail.com

> b).  How to present the element
> in UniqueKey.  Prue EquivalenceClasses or Mix of Expr and EquivalenceClass as
> we just talked about.
I think the reason we add ECs for sort expressions is to use
transitive relationship. The EC may start with a single member but
later in the planning that member might find partners which are all
equivalent. Result ordered by one is also ordered by the other. The
same logic applies to UniqueKey as well, isn't it. In a result if a
set of columns makes a row unique, the set of columns represented by
the other EC member should be unique. Though a key will start as a
singleton it might EC partners later and thus thus unique key will
transition to all the members. With that logic UniqueKey should use
just ECs instead of bare expressions.

-- 
Best Wishes,
Ashutosh Bapat

On Tue, 6 Apr 2021 at 22:31, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> On Wed, Mar 31, 2021 at 9:12 PM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:
>> I think the reason we add ECs for sort expressions is to use
>> transitive relationship. The EC may start with a single member but
>> later in the planning that member might find partners which are all
>> equivalent. Result ordered by one is also ordered by the other. The
>> same logic applies to UniqueKey as well, isn't it. In a result if a
>> set of columns makes a row unique, the set of columns represented by
>> the other EC member should be unique. Though a key will start as a
>> singleton it might EC partners later and thus thus unique key will
>> transition to all the members. With that logic UniqueKey should use
>> just ECs instead of bare expressions.
>
>
> TBH, I haven't thought about this too hard, but I think when we build the
> UniqueKey, all the ECs have been built already.  So can you think out an
> case we start with an EC with a single member at the beginning and
> have more members later for UniqueKey cases?

I don't really know if it matters which order things happen. We still
end up with a single EC containing {a,b} whether we process ORDER BY b
or WHERE a=b first.

In any case, the reason we want PathKeys to be ECs rather than just
Exprs is to allow cases such as the following to use an index to
perform the sort.

# create table ab (a int, b int);
# create index on ab(a);
# set enable_seqscan=0;
# explain select * from ab where a=b order by b;
                             QUERY PLAN
---------------------------------------------------------------------
 Index Scan using ab_a_idx on ab  (cost=0.15..83.70 rows=11 width=8)
   Filter: (a = b)
(2 rows)

Of course, we couldn't use this index to provide pre-sorted results if
"where a=b" hadn't been there.

David

On Tue, Apr 6, 2021 at 6:55 PM David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Tue, 6 Apr 2021 at 22:31, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> > On Wed, Mar 31, 2021 at 9:12 PM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:
> >> I think the reason we add ECs for sort expressions is to use
> >> transitive relationship. The EC may start with a single member but
> >> later in the planning that member might find partners which are all
> >> equivalent. Result ordered by one is also ordered by the other. The
> >> same logic applies to UniqueKey as well, isn't it. In a result if a
> >> set of columns makes a row unique, the set of columns represented by
> >> the other EC member should be unique. Though a key will start as a
> >> singleton it might EC partners later and thus thus unique key will
> >> transition to all the members. With that logic UniqueKey should use
> >> just ECs instead of bare expressions.
> >
> >
> > TBH, I haven't thought about this too hard, but I think when we build the
> > UniqueKey, all the ECs have been built already.  So can you think out an
> > case we start with an EC with a single member at the beginning and
> > have more members later for UniqueKey cases?
>
> I don't really know if it matters which order things happen. We still
> end up with a single EC containing {a,b} whether we process ORDER BY b
> or WHERE a=b first.
>

I think it is time to talk about this again.  Take the below query as example:

SELECT * FROM t1, t2 WHERE t1.pk = t2.pk;

Then when I populate_baserel_uniquekeys for t1, we already have
EC{Members={t1.pk, t2.pk}} in root->eq_classes already. Then I use
this EC directly for t1's UniqueKey.  The result is:

T1's UniqueKey : [ EC{Members={t1.pk, t2.pk}} ].

*Would this be OK since at the baserel level,  the "t1.pk = t2.pk" is not
executed yet?*

I tried the below example to test how PathKey is maintained.
CREATE TABLE t1 (a INT, b INT);
CREATE TABLE t2 (a INT, b INT);
CREATE INDEX ON t1(b);

SELECT * FROM t1, t2 WHERE t1.b = t2.b and t1.b > 3;

then we can get t1's Path:

Index Scan on (b),  PathKey.pk_class include 2 members (t1.b, t2.b}
even before the Join.

So looks the answer for my question should be "yes"? Hope I have
made myself clear.

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

On Sat, 17 Jul 2021 at 19:32, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> SELECT * FROM t1, t2 WHERE t1.pk = t2.pk;
>
> Then when I populate_baserel_uniquekeys for t1, we already have
> EC{Members={t1.pk, t2.pk}} in root->eq_classes already. Then I use
> this EC directly for t1's UniqueKey.  The result is:
>
> T1's UniqueKey : [ EC{Members={t1.pk, t2.pk}} ].
>
> *Would this be OK since at the baserel level,  the "t1.pk = t2.pk" is not
> executed yet?*
>
> I tried the below example to test how PathKey is maintained.
> CREATE TABLE t1 (a INT, b INT);
> CREATE TABLE t2 (a INT, b INT);
> CREATE INDEX ON t1(b);
>
> SELECT * FROM t1, t2 WHERE t1.b = t2.b and t1.b > 3;
>
> then we can get t1's Path:
>
> Index Scan on (b),  PathKey.pk_class include 2 members (t1.b, t2.b}
> even before the Join.
>
> So looks the answer for my question should be "yes"? Hope I have
> made myself clear.

I don't see the problem. The reason PathKeys use EquivalenceClasses is
so that queries like: SELECT * FROM tab WHERE a=b ORDER BY b; can see
that they're also ordered by a.  This is useful because if there
happens to be an index on tab(a) then we can use it to provide the
required ordering for this query.

We'll want the same with UniqueKeys.  The same thing there looks like:

CREATE TABLE tab (a int primary key, b int not null);

select distinct b from tab where a=b;

Since we have the EquivalenceClass with {a,b} stored in the UniqueKey,
then we should be able to execute this without doing any distinct
operation.

David

On Sat, Jul 17, 2021 at 3:45 PM David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Sat, 17 Jul 2021 at 19:32, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> > SELECT * FROM t1, t2 WHERE t1.pk = t2.pk;
> >
> > Then when I populate_baserel_uniquekeys for t1, we already have
> > EC{Members={t1.pk, t2.pk}} in root->eq_classes already. Then I use
> > this EC directly for t1's UniqueKey.  The result is:
> >
> > T1's UniqueKey : [ EC{Members={t1.pk, t2.pk}} ].
> >
> > *Would this be OK since at the baserel level,  the "t1.pk = t2.pk" is not
> > executed yet?*
> >
> > I tried the below example to test how PathKey is maintained.
> > CREATE TABLE t1 (a INT, b INT);
> > CREATE TABLE t2 (a INT, b INT);
> > CREATE INDEX ON t1(b);
> >
> > SELECT * FROM t1, t2 WHERE t1.b = t2.b and t1.b > 3;
> >
> > then we can get t1's Path:
> >
> > Index Scan on (b),  PathKey.pk_class include 2 members (t1.b, t2.b}
> > even before the Join.
> >
> > So looks the answer for my question should be "yes"? Hope I have
> > made myself clear.
>
> I don't see the problem.

Thanks for the double check,  that removes a big blocker for my development.
I'd submit a new patch very soon.

> The reason PathKeys use EquivalenceClasses is
> so that queries like: SELECT * FROM tab WHERE a=b ORDER BY b; can see
> that they're also ordered by a.  This is useful because if there
> happens to be an index on tab(a) then we can use it to provide the
> required ordering for this query.
>
> We'll want the same with UniqueKeys.  The same thing there looks like:
>
> CREATE TABLE tab (a int primary key, b int not null);
>
> select distinct b from tab where a=b;
>
> Since we have the EquivalenceClass with {a,b} stored in the UniqueKey,
> then we should be able to execute this without doing any distinct
> operation.
>
> David



-- 
Best Regards
Andy Fan (https://www.aliyun.com/)