Thread: [PATCH] Erase the distinctClause if the result is unique by definition

Hi:

I wrote a patch to erase the distinctClause if the result is unique by 

definition,  I find this because a user switch this code from oracle 

to PG and find the performance is bad due to this,  so I adapt pg for

this as well. 

This patch doesn't work for a well-written SQL,  but some drawback 

of a SQL may be not very obvious,  since the cost of checking is pretty

low as well,  so I think it would be ok to add.. 

Please see the patch for details.   

Thank you. 

Hi Andy,

What might help is to add more description to your email message like giving examples to explain your idea.

Anyway, I looked at the testcases you added for examples.

+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN          
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)

From this example, it seems that the distinct operation can be dropped because (a, b) is a primary key. Is my understanding correct?

I like the idea since it eliminates one expensive operation.

However the patch as presented has some problems

1. What happens if the primary key constraint or NOT NULL constraint gets dropped between a prepare and execute? The plan will no more be valid and thus execution may produce non-distinct results.

PostgreSQL has similar concept of allowing non-grouping expression as part of targetlist when those expressions can be proved to be functionally dependent on the GROUP BY clause. See check_functional_grouping() and its caller. I think, DISTINCT elimination should work on similar lines.

2. For the same reason described in check_functional_grouping(), using unique indexes for eliminating DISTINCT should be discouraged.

3. If you could eliminate DISTINCT you could similarly eliminate GROUP BY as well

4. The patch works only at the query level, but that functionality can be expanded generally to other places which add Unique/HashAggregate/Group nodes if the underlying relation can be proved to produce distinct rows. But that's probably more work since we will have to label paths with unique keys similar to pathkeys.

5. Have you tested this OUTER joins, which can render inner side nullable?

On Thu, Feb 6, 2020 at 11:31 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:

update the patch with considering the semi/anti join. 

Can anyone help to review this patch?  

Thanks

On Fri, Jan 31, 2020 at 8:39 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

Hi:

I wrote a patch to erase the distinctClause if the result is unique by 

definition,  I find this because a user switch this code from oracle 

to PG and find the performance is bad due to this,  so I adapt pg for

this as well. 

This patch doesn't work for a well-written SQL,  but some drawback 

of a SQL may be not very obvious,  since the cost of checking is pretty

low as well,  so I think it would be ok to add.. 

Please see the patch for details.   

Thank you. 

--

--

Best Wishes,

Ashutosh Bapat

Hi Ashutosh:

   Thanks for your time. 

On Fri, Feb 7, 2020 at 11:54 PM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:

Hi Andy,

What might help is to add more description to your email message like giving examples to explain your idea.

Anyway, I looked at the testcases you added for examples.

+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN          
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)

From this example, it seems that the distinct operation can be dropped because (a, b) is a primary key. Is my understanding correct?

Yes, you are correct.   Actually I added then to commit message,

but it's true that I should have copied them in this email body as

 well.  so copy it now. 

[PATCH] Erase the distinctClause if the result is unique by
 definition

However the patch as presented has some problems

1. What happens if the primary key constraint or NOT NULL constraint gets dropped between a prepare and execute? The plan will no more be valid and thus execution may produce non-distinct results.

Will this still be an issue if user use doesn't use a "read uncommitted" 

isolation level?  I suppose it should be ok for this case.  But even though

I should add an isolation level check for this.  Just added that in the patch

to continue discussing of this issue. 

 

PostgreSQL has similar concept of allowing non-grouping expression as part of targetlist when those expressions can be proved to be functionally dependent on the GROUP BY clause. See check_functional_grouping() and its caller. I think, DISTINCT elimination should work on similar lines.

2. For the same reason described in check_functional_grouping(), using unique indexes for eliminating DISTINCT should be discouraged.

 

I checked the comments of check_functional_grouping,  the reason is 

 * Currently we only check to see if the rel has a primary key that is a
 * subset of the grouping_columns.  We could also use plain unique constraints
 * if all their columns are known not null, but there's a problem: we need
 * to be able to represent the not-null-ness as part of the constraints added
 * to *constraintDeps.  FIXME whenever not-null constraints get represented
 * in pg_constraint.

Actually I am doubtful the reason for pg_constraint since we still be able 

to get the not null information from relation->rd_attr->attrs[n].attnotnull which 

is just what this patch did.   

3. If you could eliminate DISTINCT you could similarly eliminate GROUP BY as well

This is a good point.   The rules may have some different for join,  so I prefer 

to to focus on the current one so far.

 

4. The patch works only at the query level, but that functionality can be expanded generally to other places which add Unique/HashAggregate/Group nodes if the underlying relation can be proved to produce distinct rows. But that's probably more work since we will have to label paths with unique keys similar to pathkeys.

 

Do you mean adding some information into PlannerInfo,  and when we create 

a node for Unique/HashAggregate/Group,  we can just create a dummy node? 

[PATCH] Erase the distinctClause if the result is unique by
 definition

I forgot to mention this in the last round of comments. Your patch was actually removing distictClause from the Query structure. Please avoid doing that. If you remove it, you are also removing the evidence that this Query had a DISTINCT clause in it.

 

However the patch as presented has some problems

1. What happens if the primary key constraint or NOT NULL constraint gets dropped between a prepare and execute? The plan will no more be valid and thus execution may produce non-distinct results.

Will this still be an issue if user use doesn't use a "read uncommitted" 

isolation level?  I suppose it should be ok for this case.  But even though

I should add an isolation level check for this.  Just added that in the patch

to continue discussing of this issue. 

In PostgreSQL there's no "read uncommitted".

But that doesn't matter since a query can be prepared outside a transaction and executed within one or more subsequent transactions.

--

Best Wishes,

Ashutosh Bapat

On Tue, Feb 11, 2020 at 10:57:26AM +0800, Andy Fan wrote:
> On Tue, Feb 11, 2020 at 12:22 AM Ashutosh Bapat <
> ashutosh.bapat.oss@gmail.com> wrote:
>
> > I forgot to mention this in the last round of comments. Your patch was
> > actually removing distictClause from the Query structure. Please avoid
> > doing that. If you remove it, you are also removing the evidence that this
> > Query had a DISTINCT clause in it.
> >
>
> Yes, I removed it because it is the easiest way to do it.  what is the
> purpose of keeping the evidence?
>
> >> However the patch as presented has some problems
> >> 1. What happens if the primary key constraint or NOT NULL constraint gets
> >> dropped between a prepare and execute? The plan will no more be valid and
> >> thus execution may produce non-distinct results.
>
> > But that doesn't matter since a query can be prepared outside a
> > transaction and executed within one or more subsequent transactions.
> >
>
> Suppose after a DDL, the prepared statement need to be re-parsed/planned
> if it is not executed or it will prevent the DDL to happen.
>
> The following is my test.
>
> postgres=# create table t (a int primary key, b int not null,  c int);
> CREATE TABLE
> postgres=# insert into t values(1, 1, 1), (2, 2, 2);
> INSERT 0 2
> postgres=# create unique index t_idx1 on t(b);
> CREATE INDEX
>
> postgres=# prepare st as select distinct b from t where c = $1;
> PREPARE
> postgres=# explain execute st(1);
>                    QUERY PLAN
> -------------------------------------------------
>  Seq Scan on t  (cost=0.00..1.02 rows=1 width=4)
>    Filter: (c = 1)
> (2 rows)
> ...
> postgres=# explain execute st(1);
>                    QUERY PLAN
> -------------------------------------------------
>  Seq Scan on t  (cost=0.00..1.02 rows=1 width=4)
>    Filter: (c = $1)
> (2 rows)
>
> -- session 2
> postgres=# alter table t alter column b drop not null;
> ALTER TABLE
>
> -- session 1:
> postgres=# explain execute st(1);
>                          QUERY PLAN
> -------------------------------------------------------------
>  Unique  (cost=1.03..1.04 rows=1 width=4)
>    ->  Sort  (cost=1.03..1.04 rows=1 width=4)
>          Sort Key: b
>          ->  Seq Scan on t  (cost=0.00..1.02 rows=1 width=4)
>                Filter: (c = $1)
> (5 rows)
>
> -- session 2
> postgres=# insert into t values (3, null, 3), (4, null, 3);
> INSERT 0 2
>
> -- session 1
> postgres=# execute st(3);
>  b
> ---
>
> (1 row)
>
> and if we prepare sql outside a transaction, and execute it in the
> transaction, the other session can't drop the constraint until the
> transaction is ended.

And what if you create a view on top of a query containing a distinct clause
rather than using prepared statements?  FWIW your patch doesn't handle such
case at all, without even needing to drop constraints: 

CREATE TABLE t (a int primary key, b int not null,  c int);
INSERT INTO t VALUEs(1, 1, 1), (2, 2, 2);
CREATE UNIQUE INDEX t_idx1 on t(b);
CREATE VIEW v1 AS SELECT DISTINCT b FROM t;
EXPLAIN SELECT * FROM v1;
server closed the connection unexpectedly
        This probably means the server terminated abnormally
        before or while processing the request.

I also think this is not the right way to handle this optimization.

>
> and if we prepare sql outside a transaction, and execute it in the
> transaction, the other session can't drop the constraint until the
> transaction is ended.

And what if you create a view on top of a query containing a distinct clause
rather than using prepared statements?  FWIW your patch doesn't handle such
case at all, without even needing to drop constraints:

CREATE TABLE t (a int primary key, b int not null,  c int);
INSERT INTO t VALUEs(1, 1, 1), (2, 2, 2);
CREATE UNIQUE INDEX t_idx1 on t(b);
CREATE VIEW v1 AS SELECT DISTINCT b FROM t;
EXPLAIN SELECT * FROM v1;
server closed the connection unexpectedly
        This probably means the server terminated abnormally
        before or while processing the request.

I also think this is not the right way to handle this optimization.

Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> writes:
>> On Sat, Feb 8, 2020 at 12:53 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>> Do you mean adding some information into PlannerInfo,  and when we create
>> a node for Unique/HashAggregate/Group,  we can just create a dummy node?

> Not so much as PlannerInfo but something on lines of PathKey. See PathKey
> structure and related code. What I envision is PathKey class is also
> annotated with the information whether that PathKey implies uniqueness.
> E.g. a PathKey derived from a Primary index would imply uniqueness also. A
> PathKey derived from say Group operation also implies uniqueness. Then just
> by looking at the underlying Path we would be able to say whether we need
> Group/Unique node on top of it or not. I think that would make it much
> wider usecase and a very useful optimization.

FWIW, that doesn't seem like a very prudent approach to me, because it
confuses sorted-ness with unique-ness.  PathKeys are about sorting,
but it's possible to have uniqueness guarantees without having sorted
anything, for instance via hashed grouping.

I haven't looked at this patch, but I'd expect it to use infrastructure
related to query_is_distinct_for(), and that doesn't deal in PathKeys.

On Tue, Feb 11, 2020 at 12:22 AM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:

[PATCH] Erase the distinctClause if the result is unique by
 definition

I forgot to mention this in the last round of comments. Your patch was actually removing distictClause from the Query structure. Please avoid doing that. If you remove it, you are also removing the evidence that this Query had a DISTINCT clause in it.

Yes, I removed it because it is the easiest way to do it.  what is the purpose of keeping the evidence?

Suppose after a DDL, the prepared statement need to be re-parsed/planned 

if it is not executed or it will prevent the DDL to happen.  

-- session 2

postgres=# alter table t alter column b drop not null;
ALTER TABLE

-- session 1:

postgres=# explain execute st(1);
                         QUERY PLAN
-------------------------------------------------------------
 Unique  (cost=1.03..1.04 rows=1 width=4)
   ->  Sort  (cost=1.03..1.04 rows=1 width=4)
         Sort Key: b
         ->  Seq Scan on t  (cost=0.00..1.02 rows=1 width=4)
               Filter: (c = $1)
(5 rows)

On Tue, Feb 11, 2020 at 10:06:17PM +0530, Ashutosh Bapat wrote:
> On Tue, Feb 11, 2020 at 8:27 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
> > On Tue, Feb 11, 2020 at 12:22 AM Ashutosh Bapat <
> > ashutosh.bapat.oss@gmail.com> wrote:
> >
> >>>
> >>> [PATCH] Erase the distinctClause if the result is unique by
> >>>  definition
> >>
> >> I forgot to mention this in the last round of comments. Your patch was
> >> actually removing distictClause from the Query structure. Please avoid
> >> doing that. If you remove it, you are also removing the evidence that this
> >> Query had a DISTINCT clause in it.
> >
> > Yes, I removed it because it is the easiest way to do it.  what is the
> > purpose of keeping the evidence?
> >
>
> Julien's example provides an explanation for this. The Query structure is
> serialised into a view definition. Removing distinctClause from there means
> that the view will never try to produce unique results.

And also I think that this approach will have a lot of other unexpected side
effects.  Isn't changing the Query going to affect pg_stat_statements queryid
computing for instance?

On Tue, Feb 11, 2020 at 8:27 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Tue, Feb 11, 2020 at 12:22 AM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:

[PATCH] Erase the distinctClause if the result is unique by
 definition

I forgot to mention this in the last round of comments. Your patch was actually removing distictClause from the Query structure. Please avoid doing that. If you remove it, you are also removing the evidence that this Query had a DISTINCT clause in it.

Yes, I removed it because it is the easiest way to do it.  what is the purpose of keeping the evidence?

Julien's example provides an explanation for this. The Query structure is serialised into a view definition. Removing distinctClause from there means that the view will never try to produce unique results.

 

-- session 2

postgres=# alter table t alter column b drop not null;
ALTER TABLE

-- session 1:

postgres=# explain execute st(1);
                         QUERY PLAN
-------------------------------------------------------------
 Unique  (cost=1.03..1.04 rows=1 width=4)
   ->  Sort  (cost=1.03..1.04 rows=1 width=4)
         Sort Key: b
         ->  Seq Scan on t  (cost=0.00..1.02 rows=1 width=4)
               Filter: (c = $1)
(5 rows)

Since this prepared statement is parameterised PostgreSQL is replanning it every time it gets executed. It's not using a stored prepared plan. Try without parameters. Also make sure that a prepared plan is used for execution and not a new plan.

On Wed, Feb 12, 2020 at 12:36 AM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:

On Tue, Feb 11, 2020 at 8:27 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Tue, Feb 11, 2020 at 12:22 AM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> wrote:

[PATCH] Erase the distinctClause if the result is unique by
 definition

I forgot to mention this in the last round of comments. Your patch was actually removing distictClause from the Query structure. Please avoid doing that. If you remove it, you are also removing the evidence that this Query had a DISTINCT clause in it.

Yes, I removed it because it is the easiest way to do it.  what is the purpose of keeping the evidence?

Julien's example provides an explanation for this. The Query structure is serialised into a view definition. Removing distinctClause from there means that the view will never try to produce unique results.

 

 

Actually it is not true.  If a view is used in the query,  the definition will be *copied*

into the query tree. so if we modify the query tree,  the definition of the view never

touched.  The issue of Julien reported is because of a typo error. 

-- session 2

postgres=# alter table t alter column b drop not null;
ALTER TABLE

-- session 1:

postgres=# explain execute st(1);
                         QUERY PLAN
-------------------------------------------------------------
 Unique  (cost=1.03..1.04 rows=1 width=4)
   ->  Sort  (cost=1.03..1.04 rows=1 width=4)
         Sort Key: b
         ->  Seq Scan on t  (cost=0.00..1.02 rows=1 width=4)
               Filter: (c = $1)
(5 rows)

Since this prepared statement is parameterised PostgreSQL is replanning it every time it gets executed. It's not using a stored prepared plan. Try without parameters. Also make sure that a prepared plan is used for execution and not a new plan.

Even for  parameterised prepared statement, it is still possible to generate an generic

plan. so it will not replanning every time.  But no matter generic plan or not,  after a DDL like

changing the NOT NULL constraints.   pg will generated a plan based on the stored query

tree.   However, the query tree will be *copied* again to generate a new plan. so even I 

modified the query tree,  everything will be ok as well. 

At last,  I am agreed with that modifying the query tree is not a good idea. 

so my updated patch doesn't use it any more.  

Andy Fan <zhihui.fan1213@gmail.com> writes:
> Please see if you have any comments.   Thanks

The cfbot isn't at all happy with this.  Its linux build is complaining
about a possibly-uninitialized variable, and then giving up:

https://travis-ci.org/postgresql-cfbot/postgresql/builds/656722993

The Windows build isn't using -Werror, but it is crashing in at least
two different spots in the regression tests:

https://ci.appveyor.com/project/postgresql-cfbot/postgresql/build/1.0.81778

I've not attempted to identify the cause of that.

At a high level, I'm a bit disturbed that this focuses only on DISTINCT
and doesn't (appear to) have any equivalent intelligence for GROUP BY,
though surely that offers much the same opportunities for optimization.
It seems like it'd be worthwhile to take a couple steps back and see
if we couldn't recast the logic to work for both.

Some other random comments:

* Don't especially like the way you broke query_is_distinct_for()
into two functions, especially when you then introduced a whole
lot of other code in between. 

That's just making reviewer's job
harder to see what changed.  It makes the comments a bit disjointed
too, that is where you even had any.  (Zero introductory comment
for query_is_distinct_agg is *not* up to project coding standards.
There are a lot of other undercommented places in this patch, too.)

* Definitely don't like having query_distinct_through_join re-open
all the relations.  The data needed for this should get absorbed
while plancat.c has the relations open at the beginning.  (Non-nullness
of columns, in particular, seems like it'll be useful for other
purposes; I'm a bit surprised the planner isn't using that already.)

* In general, query_distinct_through_join seems hugely messy, expensive,
and not clearly correct.  If it is correct, the existing comments sure
aren't enough to explain what it is doing or why. 

* There seem to be some pointless #include additions, eg in planner.c
the added code doesn't look to justify any of them.  Please also
avoid unnecessary whitespace changes, those also slow down reviewing.

* I see you decided to add a new regression test file select_distinct_2.
That's a poor choice of name because it conflicts with our rules for the
naming of alternative output files.  Besides which, you forgot to plug
it into the test schedule files, so it isn't actually getting run.
Is there a reason not to just add the new test cases to select_distinct?

* There are some changes in existing regression cases that aren't
visibly related to the stated purpose of the patch, eg it now
notices that "select distinct max(unique2) from tenk1" doesn't
require an explicit DISTINCT step.  That's not wrong, but I wonder
if maybe you should subdivide this patch into more than one patch,
because that must be coming from some separate change.  I'm also
wondering what caused the plan change in expected/join.out.

                        regards, tom lane

Thank you Tom for the review! 

On Mon, Mar 2, 2020 at 4:46 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Andy Fan <zhihui.fan1213@gmail.com> writes:
> Please see if you have any comments.   Thanks

The cfbot isn't at all happy with this.  Its linux build is complaining
about a possibly-uninitialized variable, and then giving up:

https://travis-ci.org/postgresql-cfbot/postgresql/builds/656722993

The Windows build isn't using -Werror, but it is crashing in at least
two different spots in the regression tests:

https://ci.appveyor.com/project/postgresql-cfbot/postgresql/build/1.0.81778

I've not attempted to identify the cause of that.

 

Before I submit the patch, I can make sure "make check-world" is successful, but

since the compile option is not same,  so I didn't catch the possibly-uninitialized 

variable.   As for the crash on the windows,  I didn't get the enough information 

now,  I will find a windows server and reproduce the cases.

I just found the link http://commitfest.cputube.org/ this morning, I will make sure

the next patch can go pass this test.  

At a high level, I'm a bit disturbed that this focuses only on DISTINCT
and doesn't (appear to) have any equivalent intelligence for GROUP BY,
though surely that offers much the same opportunities for optimization.
It seems like it'd be worthwhile to take a couple steps back and see
if we couldn't recast the logic to work for both.

OK,  Looks group by is a bit harder  than distinct since the aggregation function. 

I will go through the code to see why to add this logic.  

 

* There seem to be some pointless #include additions, eg in planner.c
the added code doesn't look to justify any of them.  Please also
avoid unnecessary whitespace changes, those also slow down reviewing.

 

* There are some changes in existing regression cases that aren't
visibly related to the stated purpose of the patch, eg it now
notices that "select distinct max(unique2) from tenk1" doesn't
require an explicit DISTINCT step.  That's not wrong, but I wonder
if maybe you should subdivide this patch into more than one patch,
because that must be coming from some separate change.  I'm also
wondering what caused the plan change in expected/join.out.

Per my purpose it should be in the same patch,  the logical here is we 

have distinct in the sql and the query is distinct already since the max

function (the rule is defined in query_is_distinct_agg which is splited from 

the original query_is_distinct_for clause).  

On Sat, 7 Mar 2020 at 00:47, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> Upload the newest patch so that the cfbot can pass.  The last patch failed
> because some explain without the (cost off).

I've only really glanced at this patch, but I think we need to do this
in a completely different way.

I've been mentioning UniqueKeys around this mailing list for quite a
while now [1]. To summarise the idea:

1. Add a new List field to RelOptInfo named unique_keys
2. During get_relation_info() process the base relation's unique
indexes and add to the RelOptInfo's unique_keys list the indexed
expressions from each unique index (this may need to be delayed until
check_index_predicates() since predOK is only set there)
3. Perhaps in add_paths_to_joinrel(), or maybe when creating the join
rel itself (I've not looked for the best location in detail),

determine if the join can cause rows to be duplicated. If it can't,
then add the UniqueKeys from that rel.  For example: SELECT * FROM t1
INNER JOIN t2 ON t1.unique = t2.not_unique; would have the joinrel for
{t1,t2} only take the unique keys from t2 (t1 can't duplicate t2 rows
since it's an eqijoin and t1.unique has a unique index).

If the
condition was t1.unique = t2.unique then we could take the unique keys
from both sides of the join, and with t1.non_unique = t2.non_unique,
we can take neither.
4. When creating the GROUP BY paths (when there are no aggregates),
don't bother doing anything if the input rel's unique keys are a
subset of the GROUP BY clause. Otherwise, create the group by paths
and tag the new unique keys onto the GROUP BY rel.
5. When creating the DISTINCT paths, don't bother if the input rel has
unique keys are a subset of the distinct clause.

4 and 5 will mean that: SELECT DISTINCT non_unique FROM t1 GROUP BY
non_unique will just uniquify once for the GROUP BY and not for the
distinct.  SELECT DISTINCT unique FROM t1 GROUP BY unique; won't do
anything to uniquify the results.

Because both 4 and 5 require that the uniquekeys are a subset of the
distinct/group by clause, an empty uniquekey set would mean that the
RelOptInfo returns no more than 1 row.  That would allow your:

SELECT DISTINCT max(non_unique) FROM t1; to skip doing the DISTINCT part.

There's a separate effort in
https://commitfest.postgresql.org/27/1741/ to implement some parts of
the uniquekeys idea.  However the implementation currently only covers
adding the unique keys to Paths, not to RelOptInfos.

I also believe that the existing code in analyzejoins.c should be
edited to make use of unique keys rather than how it looks at unique
indexes and group by / distinct clauses.

This should be ok. The time spent in annotating a RelOptInfo about
uniqueness is not going to be a lot. But doing so would help generic
elimination of Distinct/Group/Unique operations. What is
UniquePathKey; I didn't find this in your patch or in the code.

On Wed, 11 Mar 2020 at 02:50, Ashutosh Bapat
<ashutosh.bapat.oss@gmail.com> wrote:
>
> On Tue, Mar 10, 2020 at 1:49 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:
> > In my current implementation, it calculates the uniqueness for each
> > BaseRel only, but in your way,  looks we need to calculate the
> > UniquePathKey for both BaseRel and JoinRel.   This makes more
> > difference for multi table join.
>
> I didn't understand this concern. I think, it would be better to do it
> for all kinds of relation types base, join etc. This way we are sure
> that one method works across the planner to eliminate the need for
> Distinct or grouping. If we just implement something for base
> relations right now and don't do that for joins, there is a chance
> that that method may not work for joins when we come to implement it.

Yeah, it seems to me that we're seeing more and more features that
require knowledge of uniqueness of a RelOptInfo. The skip scans patch
needs to know if a join will cause row duplication so it knows if the
skip scan path can be joined to without messing up the uniqueness of
the skip scan.  Adding more and more places that loop over the rel's
indexlist just does not seem the right way to do it, especially so
when you have to dissect the join rel down to its base rel components
to check which indexes there are. Having the knowledge on-hand at the
RelOptInfo level means we no longer have to look at indexes for unique
proofs.

> > Another concern is UniquePathKey
> > is designed for a general purpose,  we need to maintain it no matter
> > distinctClause/groupbyClause.
>
> This should be ok. The time spent in annotating a RelOptInfo about
> uniqueness is not going to be a lot. But doing so would help generic
> elimination of Distinct/Group/Unique operations. What is
> UniquePathKey; I didn't find this in your patch or in the code.

Possibly a misinterpretation. There is some overlap between this patch
and the skip scan patch, both would like to skip doing explicit work
to implement DISTINCT. Skip scans just go about it by adding new path
types that scan the index and only gathers up unique values.  In that
case, the RelOptInfo won't contain the unique keys, but the skip scan
path will. How I imagine both of these patches working together in
create_distinct_paths() is that we first check if the DISTINCT clause
is a subset of the a set of the RelOptInfo's unique keys (this patch),
else we check if there are any paths with uniquekeys that we can use
to perform a no-op on the DISTINCT clause (the skip scan patch), if
none of those apply, we create the required paths to uniquify the
results.

On Wed, 11 Mar 2020 at 17:23, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> Now I am convinced that we should maintain UniquePath on RelOptInfo,
> I would see how to work with "Index Skip Scan" patch.

I've attached a very early proof of concept patch for unique keys.
The NULL detection stuff is not yet hooked up, so it'll currently do
the wrong thing for NULLable columns.  I've left some code in there
with my current idea of how to handle that, but I'll need to add more
code both to look at the catalogue tables to see if there's a NOT NULL
constraint and also to check for strict quals that filter out NULLs.

Additionally, I've not hooked up the collation checking stuff yet. I
just wanted to see if it would work ok for non-collatable types first.

I've added a couple of lines to create_distinct_paths() to check if
the input_rel has the required UniqueKeys to skip doing the DISTINCT.
It seems to work, but my tests so far are limited to:

create table t1(a int primary key, b int);
create table t2(a int primary key, b int);

postgres=# -- t2 could duplicate t1, don't remove DISTINCT
postgres=# explain (costs off) select distinct t1.a from t1 inner join
t2 on t1.a = t2.b;
            QUERY PLAN
----------------------------------
 HashAggregate
   Group Key: t1.a
   ->  Hash Join
         Hash Cond: (t2.b = t1.a)
         ->  Seq Scan on t2
         ->  Hash
               ->  Seq Scan on t1
(7 rows)


postgres=# -- neither rel can duplicate the other due to join on PK.
Remove DISTINCT
postgres=# explain (costs off) select distinct t1.a from t1 inner join
t2 on t1.a = t2.a;
         QUERY PLAN
----------------------------
 Hash Join
   Hash Cond: (t1.a = t2.a)
   ->  Seq Scan on t1
   ->  Hash
         ->  Seq Scan on t2
(5 rows)


postgres=# -- t2.a cannot duplicate t1 and t1.a is unique. Remove DISTINCT
postgres=# explain (costs off) select distinct t1.a from t1 inner join
t2 on t1.b = t2.a;
         QUERY PLAN
----------------------------
 Hash Join
   Hash Cond: (t1.b = t2.a)
   ->  Seq Scan on t1
   ->  Hash
         ->  Seq Scan on t2
(5 rows)


postgres=# -- t1.b can duplicate t2.a. Don't remove DISTINCT
postgres=# explain (costs off) select distinct t2.a from t1 inner join
t2 on t1.b = t2.a;
            QUERY PLAN
----------------------------------
 HashAggregate
   Group Key: t2.a
   ->  Hash Join
         Hash Cond: (t1.b = t2.a)
         ->  Seq Scan on t1
         ->  Hash
               ->  Seq Scan on t2
(7 rows)


postgres=# -- t1.a cannot duplicate t2.a. Remove DISTINCT.
postgres=# explain (costs off) select distinct t2.a from t1 inner join
t2 on t1.a = t2.b;
         QUERY PLAN
----------------------------
 Hash Join
   Hash Cond: (t2.b = t1.a)
   ->  Seq Scan on t2
   ->  Hash
         ->  Seq Scan on t1
(5 rows)

I've also left a bunch of XXX comments for things that I know need more thought.

I believe we can propagate the joinrel's unique keys where the patch
is currently doing it.  I understand that in
populate_joinrel_with_paths() we do things like swapping LEFT JOINs
for RIGHT JOINs and switch the input rels around, but we do so only
because it's equivalent, so I don't currently see why we can't take
the jointype for the SpecialJoinInfo. I need to know that as I'll need
to ignore pushed down RestrictInfos for outer joins.

I'm posting now as I know I've been mentioning this UniqueKeys idea
for quite a while and if it's not something that's going to get off
the ground, then it's better to figure that out now.

On Fri, 13 Mar 2020 at 14:47, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> 1.   for pupulate_baserel_uniquekeys,  we need handle the "pk = Const" as well.
> (relation_has_unqiue_for has a similar logic) currently the following distinct path is still
>  there.

Yeah, I left a comment in propagate_unique_keys_to_joinrel() to
mention that still needs to be done. 

> postgres=# explain select distinct b from t100 where pk = 1;
>                                     QUERY PLAN
> ----------------------------------------------------------------------------------
>  Unique  (cost=8.18..8.19 rows=1 width=4)
>    ->  Sort  (cost=8.18..8.19 rows=1 width=4)
>          Sort Key: b
>          ->  Index Scan using t100_pkey on t100  (cost=0.15..8.17 rows=1 width=4)
>                Index Cond: (pk = 1)
> (5 rows)
>
> I think in this case,  we can add  both (pk) and (b) as the UniquePaths.  If so we
> can get more opportunities to reach our goal.

The UniqueKeySet containing "b" could only be added in the
distinct_rel in the upper planner. It must not change the input_rel
for the distinct.

It's likely best to steer clear of calling UniqueKeys UniquePaths as
it might confuse people.  The term "path" is used in PostgreSQL as a
lightweight representation containing all the information required to
build a plan node in createplan.c. More details in
src/backend/optimizer/README.

> 2.  As for the propagate_unique_keys_to_joinrel,  we can add 1 more UniquePath as
> (rel1_unique_paths,  rel2_unique_paths) if the current rules doesn't apply.
> or else the following cases can't be handled.
>
> postgres=# explain select distinct t100.pk,  t101.pk from t100, t101;
>                                    QUERY PLAN
> --------------------------------------------------------------------------------
>  Unique  (cost=772674.11..810981.11 rows=5107600 width=8)
>    ->  Sort  (cost=772674.11..785443.11 rows=5107600 width=8)
>          Sort Key: t100.pk, t101.pk
>          ->  Nested Loop  (cost=0.00..63915.85 rows=5107600 width=8)
>                ->  Seq Scan on t100  (cost=0.00..32.60 rows=2260 width=4)
>                ->  Materialize  (cost=0.00..43.90 rows=2260 width=4)
>                      ->  Seq Scan on t101  (cost=0.00..32.60 rows=2260 width=4)
> (7 rows)

I don't really follow what you mean here. It seems to me there's no
way we can skip doing DISTINCT in the case above.  If you've just
missed out the join clause and you meant to have "WHERE t100.pk =
t101.pk", then we can likely fix that later with some sort of
functional dependency tracking.

Likely we can just add a Relids field
to UniqueKeySet to track which relids are functionally dependant on a
row from the UniqueKeySet's uk_exprs.  That might be as simple as just
pull_varnos from the non-matched exprs and checking to ensure the
result is a subset of functionally dependant rels.  I'd need to give
that more thought.

Was this a case you had working in your patch?

> But if we add such rule,  the unique paths probably become much longer,  so we need
> a strategy to tell if the UniquePath is useful for our query,  if not,  we can ignore that.
> rel->reltarget maybe a good info for such optimization.   I think we can take this into
> consideration for pupulate_baserel_uniquekeys as well.

I don't really think the number of unique indexes in a base rel will
really ever get out of hand for legitimate cases.
propagate_unique_keys_to_joinrel is just concatenating baserel
UniqueKeySets to the joinrel. They're not copied, so it's just tagging
pointers onto the end of an array, which is at best a memcpy(), or at
worst a realloc() then memcpy(). That's not so costly.

> For the non_null info,  Tom suggested to add maintain such info RelOptInfo,
> I have done that for the not_null_info for basic relation catalog,  I think we can
> maintain the same flag for joinrel and the not null info from find_nonnullable_vars as
> well, but I still didn't find a good place to add that so far.

I'd considered just adding a get_notnull() function to lsyscache.c.
Just below get_attname() looks like a good spot.  I imagined just
setting the bit in the UniqueKeySet's non_null_keys field
corresponding to the column position from the index.  I could see the
benefit of having a field in RelOptInfo if there was some way to
determine the not-null properties of all columns in the table at once,

but there's not, so we're likely best just looking at the ones that
there are unique indexes on.

> A small question about the following code:
>
> +       if (relation_has_uniquekeys_for(root, input_rel, get_sortgrouplist_exprs(parse->distinctClause, parse->targetList), false))
> +       {
> +
> +               add_path(distinct_rel, (Path *)cheapest_input_path);
> +
> +               /* XXX yeah yeah, need to call the hooks etc. */
> +
> +               /* Now choose the best path(s) */
> +               set_cheapest(distinct_rel);
> +
> +               return distinct_rel;
> +       }
>
> Since we don't create new RelOptInfo/Path,  do we need to call add_path and set_cheapest?

The distinct_rel already exists. add_path() is the standard way we
have of adding paths to the rel's pathlist.  Why would you want to
bypass that? set_cheapest() is our standard way of looking at the
pathlist and figuring out the least costly one. It's not a very hard
job to do when there's just 1 path. Not sure why you'd want to do it
another way.

On Wed, 18 Mar 2020 at 15:57, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> I'm now writing the code for partition index stuff, which
> is a bit of boring, since every partition may have different unique index.

Why is that case so different?

For a partitioned table to have a valid unique index, a unique index
must exist on each partition having columns that are a superset of the
partition key columns. An IndexOptInfo will exist on the partitioned
table's RelOptInfo, in this case.

At the leaf partition level, wouldn't you just add the uniquekeys the
same as we do for base rels?