[PATCH] Keeps tracking the uniqueness with UniqueKey

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
50 messages Options
123
Reply | Threaded
Open this post in threaded view
|

[PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan
Greetings.

This thread is a follow-up thread for [1], where I submit a patch for erasing the
distinct node if we have known the data is unique for sure.  But since the 
implementation has changed a lot from the beginning and they are not very 
related, so I start this new thread to discuss the new strategy to save the time 
of reviewers.

As I said above, my original intention is just used to erase the distinct clause,  
then Tom Lane suggested function query_is_distinct_for,  I found the uniqueness 
can be used for costing,  remove_useless_join, reduce_unqiue_semijoins.  
David suggested to maintain the uniqueness from bottom to top, like join 
& subqueries, group-by, distinct, union and so on(we call it as UniqueKey).  
Ideally the uniqueness will be be lost in any case. This current implementation
follows the David's suggestion and also thanks Ashutosh who reminded me 
the cost should be ok while I had concerns of this at the beginning.

A new field named uniquekeys was added in RelOptInfo struct, which is a
list of UniqueKey struct.  

typedef struct UniqueKey
{
    NodeTag     type;
    List       *exprs;
    List       *positions;
    bool       grantee;
} UniqueKey;

exprs is a list of exprs which is unique if we don't care about the null vaues on 
current RelOptInfo.

positions is a list of the sequence no. of the exprs in the current RelOptInfo, 
which is used for SubQuery. like

create table t1 (a int primary key, b int);
create table t2 (a int primary key, b int);
select .. from t1,  (select b from t2 group by t2) t2 ..;

The UniqueKey for the subquery will be Var(varno=1, varattno=2),  but for the 
top query, the UniqueKey of t2 should be Var(varno=2, varattrno=1),  the 1 here 
need to be calculated by UnqiueKey->positions.

grantee field is introduced mainly for remove_useless_join & reduce_unique_semijions. 
Take the above case for example:

-- b is nullable.  so select b from t2 still can result in duplicated rows.
create unique index t2_uk_b on t2(b);  

-- the left join still can be removed since t2.b is a unique index and the nullable 
doesn't matter here.
select t1.* from t1 left join t2 on (t1.b = t2.b);  

so t2.b will still be an UniqueKey for t2, just that the grantee = false.

A branch of functions like populate_xxx_unqiuekeys for manipulating uniquekeys 
for a lot of cases, xxx maybe baserel, joinrel, paritioned table, unionrel, groupbyrel, 
distincrel and so on.  partitioned table has some not obviously troubles due to 
users can create index on the childrel directly and differently.  You can check 
the comments of the code for details.


When maintaining the uniquekeys of joinrel,  we have a rule that if both rels have 
UniqueKeys,  then any combination from the 2 sides is a unqiquekey of the joinrel. 
I used two algorithms to keep the length of the UniqueKeys short.  One is we only 
add useful UniqueKey to the RelOptInfo.uniquekeys.  If the expr isn't shown in 
rel->reltargets->exprs, it will not be used for others, so we can ignore it safely. 
The another one is if column sets A is unqiuekey already,  any superset of A 
will no need to be added as an UnqiueKey. 


The overall cost of the maintaining unqiuekeys should be ok.  If you check the code,
you may find there are many 2 or 3 levels foreach, but most of them are started with 
unique index, and I used UnqiueKeyContext and SubqueryUnqiueKeyContext in joinrel 
and subquery case to avoid too many loops.

Now I have used the UnqiueKey to erase the unnecessary distinct/group by, and also changed
the rel_is_distinct_for to use UnqiueKeys.  so we can handle more cases.

create table m1 (a int primary key,  b int, c int);
create table m2 (a int primary key,  b int, c int);
create table m3 (a int primary key,  b int, c int);

Wit the current patch, we can get:
task3=# explain select  t1.a from m3 t1 left join  (select m1.a from m1, m2 where m1.b = m2.a limit 1) t2 on (t1.a = t2.a);
                       QUERY PLAN
---------------------------------------------------------
 Seq Scan on m3 t1  (cost=0.00..32.60 rows=2260 width=4)


Before the patch, we will get:
postgres=# explain select  t1.a from m3 t1 left join  (select m1.a from m1, m2 where m1.b = m2.a limit 1) t2 on (t1.a = t2.a)
postgres-# ;
                                          QUERY PLAN
-----------------------------------------------------------------------------------------------
 Hash Left Join  (cost=0.39..41.47 rows=2260 width=4)
   Hash Cond: (t1.a = m1.a)
   ->  Seq Scan on m3 t1  (cost=0.00..32.60 rows=2260 width=4)
   ->  Hash  (cost=0.37..0.37 rows=1 width=4)
         ->  Limit  (cost=0.15..0.36 rows=1 width=4)
               ->  Nested Loop  (cost=0.15..470.41 rows=2260 width=4)
                     ->  Seq Scan on m1  (cost=0.00..32.60 rows=2260 width=8)
                     ->  Index Only Scan using m2_pkey on m2  (cost=0.15..0.19 rows=1 width=4)
                           Index Cond: (a = m1.b)


The "limit 1" here is just want to avoid the pull_up_subquery to pull up the subquery,  
I think we may still have opportunities to improve this further if we check if we can 
remove a join *just before we join 2 relations*.  we may have the similar situation 
for reduce_unique_semijions joins.  After the changes has been done, we can remove 
the "limit 1" here to show the diffidence.  I didn't include this change in current patch 
since I think the effort may be not small and I want to keep this patch simple.

Some known issues needs attentions:
1. I didn't check the collation at the whole stage, one reason is the relation_has_unique_index_for
 doesn't check it as well.  The other reason if a in collation A is unique, and then A in collation B is 
unique as well,  we can ignore it. [2]
2. Current test case contrib/postgres_fdw/sql/postgres_fdw.sql is still failed.  I am not sure if 
the bug is in my patch or not.

Kindly waiting for your feedback,  Thanks you!




Best regards
Andy Fan

v1-0001-Maintain-the-uniqueness-of-a-Query-from-bottom-to.patch (114K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan


On Mon, Mar 23, 2020 at 6:21 PM Andy Fan <[hidden email]> wrote:
Greetings.

This thread is a follow-up thread for [1], where I submit a patch for erasing the
distinct node if we have known the data is unique for sure.  But since the 
implementation has changed a lot from the beginning and they are not very 
related, so I start this new thread to discuss the new strategy to save the time 
of reviewers.

As I said above, my original intention is just used to erase the distinct clause,  
then Tom Lane suggested function query_is_distinct_for,  I found the uniqueness 
can be used for costing,  remove_useless_join, reduce_unqiue_semijoins.  
David suggested to maintain the uniqueness from bottom to top, like join 
& subqueries, group-by, distinct, union and so on(we call it as UniqueKey).  
Ideally the uniqueness will be be lost in any case. This current implementation
follows the David's suggestion and also thanks Ashutosh who reminded me 
the cost should be ok while I had concerns of this at the beginning.

A new field named uniquekeys was added in RelOptInfo struct, which is a
list of UniqueKey struct.  

typedef struct UniqueKey
{
    NodeTag     type;
    List       *exprs;
    List       *positions;
    bool       grantee;
} UniqueKey;

exprs is a list of exprs which is unique if we don't care about the null vaues on 
current RelOptInfo.

positions is a list of the sequence no. of the exprs in the current RelOptInfo, 
which is used for SubQuery. like

create table t1 (a int primary key, b int);
create table t2 (a int primary key, b int);
select .. from t1,  (select b from t2 group by t2) t2 ..;

The UniqueKey for the subquery will be Var(varno=1, varattno=2),  but for the 
top query, the UniqueKey of t2 should be Var(varno=2, varattrno=1),  the 1 here 
need to be calculated by UnqiueKey->positions.

grantee field is introduced mainly for remove_useless_join & reduce_unique_semijions. 
Take the above case for example:

-- b is nullable.  so select b from t2 still can result in duplicated rows.
create unique index t2_uk_b on t2(b);  

-- the left join still can be removed since t2.b is a unique index and the nullable 
doesn't matter here.
select t1.* from t1 left join t2 on (t1.b = t2.b);  

so t2.b will still be an UniqueKey for t2, just that the grantee = false.

A branch of functions like populate_xxx_unqiuekeys for manipulating uniquekeys 
for a lot of cases, xxx maybe baserel, joinrel, paritioned table, unionrel, groupbyrel, 
distincrel and so on.  partitioned table has some not obviously troubles due to 
users can create index on the childrel directly and differently.  You can check 
the comments of the code for details.


When maintaining the uniquekeys of joinrel,  we have a rule that if both rels have 
UniqueKeys,  then any combination from the 2 sides is a unqiquekey of the joinrel. 
I used two algorithms to keep the length of the UniqueKeys short.  One is we only 
add useful UniqueKey to the RelOptInfo.uniquekeys.  If the expr isn't shown in 
rel->reltargets->exprs, it will not be used for others, so we can ignore it safely. 
The another one is if column sets A is unqiuekey already,  any superset of A 
will no need to be added as an UnqiueKey. 


The overall cost of the maintaining unqiuekeys should be ok.  If you check the code,
you may find there are many 2 or 3 levels foreach, but most of them are started with 
unique index, and I used UnqiueKeyContext and SubqueryUnqiueKeyContext in joinrel 
and subquery case to avoid too many loops.

Now I have used the UnqiueKey to erase the unnecessary distinct/group by, and also changed
the rel_is_distinct_for to use UnqiueKeys.  so we can handle more cases.

create table m1 (a int primary key,  b int, c int);
create table m2 (a int primary key,  b int, c int);
create table m3 (a int primary key,  b int, c int);

Wit the current patch, we can get:
task3=# explain select  t1.a from m3 t1 left join  (select m1.a from m1, m2 where m1.b = m2.a limit 1) t2 on (t1.a = t2.a);
                       QUERY PLAN
---------------------------------------------------------
 Seq Scan on m3 t1  (cost=0.00..32.60 rows=2260 width=4)


Before the patch, we will get:
postgres=# explain select  t1.a from m3 t1 left join  (select m1.a from m1, m2 where m1.b = m2.a limit 1) t2 on (t1.a = t2.a)
postgres-# ;
                                          QUERY PLAN
-----------------------------------------------------------------------------------------------
 Hash Left Join  (cost=0.39..41.47 rows=2260 width=4)
   Hash Cond: (t1.a = m1.a)
   ->  Seq Scan on m3 t1  (cost=0.00..32.60 rows=2260 width=4)
   ->  Hash  (cost=0.37..0.37 rows=1 width=4)
         ->  Limit  (cost=0.15..0.36 rows=1 width=4)
               ->  Nested Loop  (cost=0.15..470.41 rows=2260 width=4)
                     ->  Seq Scan on m1  (cost=0.00..32.60 rows=2260 width=8)
                     ->  Index Only Scan using m2_pkey on m2  (cost=0.15..0.19 rows=1 width=4)
                           Index Cond: (a = m1.b)


The "limit 1" here is just want to avoid the pull_up_subquery to pull up the subquery,  
I think we may still have opportunities to improve this further if we check if we can 
remove a join *just before we join 2 relations*.  we may have the similar situation 
for reduce_unique_semijions joins.  After the changes has been done, we can remove 
the "limit 1" here to show the diffidence.  I didn't include this change in current patch 
since I think the effort may be not small and I want to keep this patch simple.

Some known issues needs attentions:
1. I didn't check the collation at the whole stage, one reason is the relation_has_unique_index_for
 doesn't check it as well.  The other reason if a in collation A is unique, and then A in collation B is 
unique as well,  we can ignore it. [2]
2. Current test case contrib/postgres_fdw/sql/postgres_fdw.sql is still failed.  I am not sure if 
the bug is in my patch or not.

Kindly waiting for your feedback,  Thanks you!



Just update the patch which do some test case changes.
1.    add "ANALYZE" command before running the explain.
2.    order by with an explicit collate settings.  
3.    As for the postgres_fdw.sql,  I just copied the results.out to expected.out,  
that's should be correct based on the result.  However I added my comment
around that. 

Now suppose the cbfot should pass this time. 

Best Regards.
Andy Fan

  
 

v2-0001-Maintain-the-uniqueness-of-a-Query-from-bottom-to.patch (121K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan
Because I replied the old thread,  cfbot run a test based on the old patch
on that thread.  I have detached the old thread from commitfest.   Reply this 
email again to wake up Mr. cfbot with the right information.  

v2-0001-Maintain-the-uniqueness-of-a-Query-from-bottom-to.patch (121K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan
In reply to this post by Andy Fan

Just update the patch which do some test case changes.
1.    add "ANALYZE" command before running the explain.
2.    order by with an explicit collate settings.  

Thanks  Rushabh for pointing this out, or else I'd spend much more time to figure
out why I get a different order on Windows. 

3.    As for the postgres_fdw.sql,  I just copied the results.out to expected.out,  
that's should be correct based on the result.  However I added my comment
around that. 

The issue doesn't exist at all.  The confusion was introduced by a misunderstanding
of the test case (I treated count (xx)  filter (xxx) as a window function rather than an aggration
function). so just fixed the it cleanly.

Some other changes made in the new patch:
1.   Fixed bug for UniqueKey calculation for OUTER join.
2.   Fixed some typo error in comments.
3.   Renamed the field "grantee" as "guarantee".

Best Regards
Andy Fan
  

v3-0001-Maintain-UniqueKey-at-each-RelOptInfo-this-inform.patch (120K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
On Sun, 29 Mar 2020 at 20:50, Andy Fan <[hidden email]> wrote:
> Some other changes made in the new patch:
> 1.   Fixed bug for UniqueKey calculation for OUTER join.
> 2.   Fixed some typo error in comments.
> 3.   Renamed the field "grantee" as "guarantee".

I've had a look over this patch. Thank for you doing further work on it.

I've noted down the following during my read of the code:

1. There seem to be some cases where joins are no longer being
detected as unique. This is evident in postgres_fdw.out. We shouldn't
be regressing any of these cases.

2. The following change does not seem like it should be part of this
patch.  I understand you perhaps have done as you think it will
improve the performance of checking if an expression is in a list of
expressions.

- COMPARE_SCALAR_FIELD(varno);
+ /* Compare varattno first since it has higher selectivity than varno */
  COMPARE_SCALAR_FIELD(varattno);
+ COMPARE_SCALAR_FIELD(varno);

If you think that is true, then please do it as a separate effort and
provide benchmarks with your findings.

3. list_all_members_in. I think this would be better named as
list_is_subset. Please follow the lead of bms_is_subset().
Additionally, you should Assert that IsPointerList is true as there's
nothing else to indicate that it can't be used for an int or Oid list.

4. guarantee is not a very good name for the field in UniqueKey.
Maybe something like is_not_null?

5. I think you should be performing a bms_del_member during join
removal rather than removing this Assert()

- Assert(bms_equal(rel->relids, root->all_baserels));

FWIW, it's far from perfect that you've needed to delay the left join
removal, but I do understand why you've done it. It's also far from
perfect that you're including removed relations in the
total_table_pages calculation. c6e4133fae1 took some measures to
improve this calculation and this is making it worse again.

6. Can you explain why you moved the populate_baserel_uniquekeys()
call out of set_plain_rel_size()?

7. I don't think the removal of rel_supports_distinctness() is
warranted.  Is it not ok to check if the relation has any uniquekeys?
It's possible, particularly in join_is_removable that this can save
quite a large amount of effort.

8. Your spelling of unique is incorrect in many places:

src/backend/nodes/makefuncs.c: * makeUnqiueKey
src/backend/optimizer/path/uniquekeys.c:static List
*initililze_unqiuecontext_for_joinrel(RelOptInfo *joinrel,
src/backend/optimizer/path/uniquekeys.c: * check if combination of
unqiuekeys from both side is still useful for us,
src/backend/optimizer/path/uniquekeys.c:        outerrel_uniquekey_ctx
= initililze_unqiuecontext_for_joinrel(joinrel, outerrel);
src/backend/optimizer/path/uniquekeys.c:        innerrel_uniquekey_ctx
= initililze_unqiuecontext_for_joinrel(joinrel, innerrel);
src/backend/optimizer/path/uniquekeys.c: * we need to convert the
UnqiueKey from sub_final_rel to currel via the positions info in
src/backend/optimizer/path/uniquekeys.c:                ctx->pos =
pos; /* the position in current targetlist,  will be used to set
UnqiueKey */
src/backend/optimizer/path/uniquekeys.c: * Check if Unqiue key of the
innerrel is valid after join. innerrel's UniqueKey
src/backend/optimizer/path/uniquekeys.c: * initililze_unqiuecontext_for_joinrel
src/backend/optimizer/path/uniquekeys.c: * all the unqiuekeys which
are not possible to use later
src/backend/optimizer/path/uniquekeys.c:initililze_unqiuecontext_for_joinrel(RelOptInfo
*joinrel,  RelOptInfo *inputrel)
src/backend/optimizer/plan/analyzejoins.c:                      /*
This UnqiueKey is what we want */
src/backend/optimizer/plan/planner.c:   /* If we the result if unqiue
already, we just return the input_rel directly */
src/include/nodes/pathnodes.h: * exprs is a list of exprs which is
unqiue on current RelOptInfo.
src/test/regress/expected/join.out:-- XXXX: since b.id is unqiue now
so the group by cluase is erased, so
src/test/regress/expected/select_distinct.out:-- create unqiue index on dist_p
src/test/regress/expected/select_distinct.out:-- we also support
create unqiue index on each child tables
src/test/regress/sql/join.sql:-- XXXX: since b.id is unqiue now so the
group by cluase is erased, so
src/test/regress/sql/select_distinct.sql:-- create unqiue index on dist_p
src/test/regress/sql/select_distinct.sql:-- we also support create
unqiue index on each child tables

9. A few things wrong with the following fragment:

/* set the not null info now */
ListCell *lc;
foreach(lc, find_nonnullable_vars(qual))
{
Var *var = lfirst_node(Var, lc);
RelOptInfo *rel = root->simple_rel_array[var->varno];
if (var->varattno > InvalidAttrNumber)
rel->not_null_cols = bms_add_member(rel->not_null_cols, var->varattno);
}

a. including a function call in the foreach macro is not a practise
that we really follow. It's true that the macro now assigns the 2nd
param to a variable. Previous to 1cff1b95ab6 this was not the case and
it's likely best not to leave any bad examples around that code which
might get backported might follow.
b. We generally subtract InvalidAttrNumber from varattno when
including in a Bitmapset.
c. not_null_cols is not well named. I think notnullattrs
d. not_null_cols should not be a Relids type, it should be Bitmapset.

10. add_uniquekey_for_onerow() seems pretty wasteful.  Is there really
a need to add each item in the rel's targetlist to the uniquekey list?
What if we just add an empty list to the unique keys, that way if we
need to test if some expr is a superset of any uniquekey, then we'll
see it is as any set is a superset of an empty set.  Likely the empty
set of uniquekeys should be the only one in the rel's uniquekey list.

11. In create_distinct_paths() the code is now calling
get_sortgrouplist_exprs() multiple times with the same input. I think
it would be better to just call it once and set the result in a local
variable.

12. The comment in the code below is not true. The List contains
Lists, of which contain UniqueKeys

List    *uniquekeys; /* List of UniqueKey */

13. I'm having trouble parsing the final sentence in:

+ * can only guarantee the uniqueness without considering the null values. This
+ * field is necessary for remove_useless_join & reduce_unique_semijions since
+ * these cases don't care about the null values.

Why is the field which stores the nullability of the key required for
code that does not care about the nullability of the key?

Also please check your spelling of the word "join"

14. In the following fragment, instead of using i+1, please assign the
FormData_pg_attribute to a variable named attr and use attr->attnum.
Also, please see what I mentioned above about subtracting
InvalidAttrNumber

+ rel->not_null_cols = bms_add_member(rel->not_null_cols, i+1);

15. The tests you've changed the expected outcome of in join.out
should be updated so that the GROUP BY and DISTINCT clause is not
removed. This will allow the test to continue testing what it was
intended to test. You can do this by changing the columns in the GROUP
BY clause so that the new code does not find uniquekeys for those
columns.

16. The tests in aggregates.out are in a similar situation. There are
various tests trying to ensure that remove_useless_groupby_columns()
does what it's meant to do. You can modify these tests to add a join
which is non-unique to effectively duplicate the PK column.

17. In your select_distinct tests, can you move away from naming the
tables starting with select_distinct?  It makes reading queries pretty
hard.

e.g. explain (costs off) select distinct uk1, uk2 from
select_distinct_a where uk2 is not null;

When I first glanced that, I failed to see the underscores and the
query looked invalid.

18. Check the spelling if "erased". You have it spelt as "ereased" in
a couple of locations.

19. Please pay attention to the capitalisation of SQL keywords in the
test files you've modified. I understand we're very inconsistent in
this department in general, but we do at least try not to mix
capitalisation within the same file.  Basically, please upper case the
keywords in select_distinct.sql

20. In addition to the above, please try to wrap long SQL lines so
they're below 80 chars.

I'll review the patch in more detail once the above points have been addressed.

David


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Tom Lane-2
[ not a review, just some drive-by comments on David's comments ]

David Rowley <[hidden email]> writes:
> 2. The following change does not seem like it should be part of this
> patch.  I understand you perhaps have done as you think it will
> improve the performance of checking if an expression is in a list of
> expressions.

> - COMPARE_SCALAR_FIELD(varno);
> + /* Compare varattno first since it has higher selectivity than varno */
>   COMPARE_SCALAR_FIELD(varattno);
> + COMPARE_SCALAR_FIELD(varno);

> If you think that is true, then please do it as a separate effort and
> provide benchmarks with your findings.

By and large, I'd reject such micro-optimizations on their face.
The rule in the nodes/ support files is to list fields in the same
order they're declared in.  There is no chance that it's worth
deviating from that for this.

I can believe that there'd be value in, say, comparing all
scalar fields before all non-scalar ones.  But piecemeal hacks
wouldn't be the way to handle that either.  In any case, I'd
prefer to implement such a plan within the infrastructure to
auto-generate these files that Andres keeps muttering about.

> a. including a function call in the foreach macro is not a practise
> that we really follow. It's true that the macro now assigns the 2nd
> param to a variable. Previous to 1cff1b95ab6 this was not the case and
> it's likely best not to leave any bad examples around that code which
> might get backported might follow.

No, I think you're misremembering.  foreach's second arg is
single-evaluation in all branches.  There were some preliminary
versions of 1cff1b95ab6 in which it would not have been, but that
was sufficiently dangerous that I found a way to get rid of it.

> b. We generally subtract InvalidAttrNumber from varattno when
> including in a Bitmapset.

ITYM FirstLowInvalidHeapAttributeNumber, but yeah.  Otherwise
the code fails on system columns, and there's seldom a good
reason to risk that.

                        regards, tom lane


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan
In reply to this post by David Rowley
Thanks David for your time,  I will acknowledge every item you mentioned 
with the updated patch.  Now I just talk about part of them.


1. There seem to be some cases where joins are no longer being
detected as unique. This is evident in postgres_fdw.out. We shouldn't
be regressing any of these cases.

You are correct,  the issue here is  I didn't distinguish the one_row case 
in UniqueKey struct.  Actually when a outer relation is join with a relation
which has only one row,  there must be at most one row match the outer join.
The only-one-row case in postgres_fdw.out come from aggregation 
call. I will added one more field "bool onerow" in UniqueKey struct.  and
also try your optimization suggestion for the onerow UniqueKey.
 
2. The following change does not seem like it should be part of this
patch.  I understand you perhaps have done as you think it will
improve the performance of checking if an expression is in a list of
expressions.

- COMPARE_SCALAR_FIELD(varno);
+ /* Compare varattno first since it has higher selectivity than varno */
  COMPARE_SCALAR_FIELD(varattno);
+ COMPARE_SCALAR_FIELD(varno);

I did have a hesitation when I make this changes.  so I'd rollback this change
at the following patch. 
 
If you think that is true, then please do it as a separate effort and
provide benchmarks with your findings.

3. list_all_members_in. I think this would be better named as
list_is_subset. Please follow the lead of bms_is_subset().
Additionally, you should Assert that IsPointerList is true as there's
nothing else to indicate that it can't be used for an int or Oid list.

4. guarantee is not a very good name for the field in UniqueKey.
Maybe something like is_not_null?

 
5. I think you should be performing a bms_del_member during join
removal rather than removing this Assert()

- Assert(bms_equal(rel->relids, root->all_baserels));

FWIW, it's far from perfect that you've needed to delay the left join
removal, but I do understand why you've done it. It's also far from
perfect that you're including removed relations in the
total_table_pages calculation. c6e4133fae1 took some measures to
improve this calculation and this is making it worse again.

Since the removed relation depends on the UniqueKey which has to be
calculated after  total_table_pages calculation in current code, so that's 
something I must do.  But if the relation is not removable,  there is no waste
at all.  If it is removable,  such gain will much higher than the loss.  I'm 
not sure this should be a concern.   

Actually looks the current remove_useless_join has some limits which can't
remove a joinrel,  I still didn't figure out why.  In the past we have some limited
ability to detect the unqiueness after join, so that's would be ok.  Since  we have
such ability now,  this may be another opportunity to improve the join_is_removable
function, but I'd not like put such thing in this patch. 

Since you said "far from perfect" twice for this point and I only get one reason (we 
may plan a node which we removed later),  do I miss the other one? 

6. Can you explain why you moved the populate_baserel_uniquekeys()
call out of set_plain_rel_size()?

This is to be consistent with populate_partitionedrel_uniquekeys, which
is set at set_append_rel_pathlist.  
  
7. I don't think the removal of rel_supports_distinctness() is
warranted.  Is it not ok to check if the relation has any uniquekeys?

I think this is a good suggestion.  I will follow that.  

8. Your spelling of unique is incorrect in many places:

src/backend/nodes/makefuncs.c: * makeUnqiueKey
src/backend/optimizer/path/uniquekeys.c:static List
*initililze_unqiuecontext_for_joinrel(RelOptInfo *joinrel,
src/backend/optimizer/path/uniquekeys.c: * check if combination of
unqiuekeys from both side is still useful for us,
src/backend/optimizer/path/uniquekeys.c:        outerrel_uniquekey_ctx
= initililze_unqiuecontext_for_joinrel(joinrel, outerrel);
src/backend/optimizer/path/uniquekeys.c:        innerrel_uniquekey_ctx
= initililze_unqiuecontext_for_joinrel(joinrel, innerrel);
src/backend/optimizer/path/uniquekeys.c: * we need to convert the
UnqiueKey from sub_final_rel to currel via the positions info in
src/backend/optimizer/path/uniquekeys.c:                ctx->pos =
pos; /* the position in current targetlist,  will be used to set
UnqiueKey */
src/backend/optimizer/path/uniquekeys.c: * Check if Unqiue key of the
innerrel is valid after join. innerrel's UniqueKey
src/backend/optimizer/path/uniquekeys.c: * initililze_unqiuecontext_for_joinrel
src/backend/optimizer/path/uniquekeys.c: * all the unqiuekeys which
are not possible to use later
src/backend/optimizer/path/uniquekeys.c:initililze_unqiuecontext_for_joinrel(RelOptInfo
*joinrel,  RelOptInfo *inputrel)
src/backend/optimizer/plan/analyzejoins.c:                      /*
This UnqiueKey is what we want */
src/backend/optimizer/plan/planner.c:   /* If we the result if unqiue
already, we just return the input_rel directly */
src/include/nodes/pathnodes.h: * exprs is a list of exprs which is
unqiue on current RelOptInfo.
src/test/regress/expected/join.out:-- XXXX: since b.id is unqiue now
so the group by cluase is erased, so
src/test/regress/expected/select_distinct.out:-- create unqiue index on dist_p
src/test/regress/expected/select_distinct.out:-- we also support
create unqiue index on each child tables
src/test/regress/sql/join.sql:-- XXXX: since b.id is unqiue now so the
group by cluase is erased, so
src/test/regress/sql/select_distinct.sql:-- create unqiue index on dist_p
src/test/regress/sql/select_distinct.sql:-- we also support create
unqiue index on each child tables

9. A few things wrong with the following fragment:

/* set the not null info now */
ListCell *lc;
foreach(lc, find_nonnullable_vars(qual))
{
Var *var = lfirst_node(Var, lc);
RelOptInfo *rel = root->simple_rel_array[var->varno];
if (var->varattno > InvalidAttrNumber)
rel->not_null_cols = bms_add_member(rel->not_null_cols, var->varattno);
}

a. including a function call in the foreach macro is not a practise
that we really follow. It's true that the macro now assigns the 2nd
param to a variable. Previous to 1cff1b95ab6 this was not the case and
it's likely best not to leave any bad examples around that code which
might get backported might follow.
b. We generally subtract InvalidAttrNumber from varattno when
including in a Bitmapset.
c. not_null_cols is not well named. I think notnullattrs
d. not_null_cols should not be a Relids type, it should be Bitmapset.

If it is a Bitmapset,  we have to pass it with "&" usually.  is it our practice? 
 
10. add_uniquekey_for_onerow() seems pretty wasteful.  Is there really
a need to add each item in the rel's targetlist to the uniquekey list?
What if we just add an empty list to the unique keys, that way if we
need to test if some expr is a superset of any uniquekey, then we'll
see it is as any set is a superset of an empty set.  Likely the empty
set of uniquekeys should be the only one in the rel's uniquekey list.

11. In create_distinct_paths() the code is now calling
get_sortgrouplist_exprs() multiple times with the same input. I think
it would be better to just call it once and set the result in a local
variable.

12. The comment in the code below is not true. The List contains
Lists, of which contain UniqueKeys

List    *uniquekeys; /* List of UniqueKey */

It is a list of UniqueKey,  the UniqueKey can have a list of exprs. 
 
13. I'm having trouble parsing the final sentence in:

+ * can only guarantee the uniqueness without considering the null values. This
+ * field is necessary for remove_useless_join & reduce_unique_semijions since
+ * these cases don't care about the null values.

Why is the field which stores the nullability of the key required for
code that does not care about the nullability of the key?

The guarantee is introduced to for the following cases:

create table t1 (a int primary key, b int);
create table t2 (a int primary key, b int);
select .. from t1,  (select b from t2 group by t2) t2 ..;

-- b is nullable.  so t2(b) can't be a normal UniqueKey (which means b may have some 
duplicated rows)
create unique index t2_uk_b on t2(b);  

-- the left join still can be removed since t2.b is a unique index and the nullable 
doesn't matter here.
select t1.* from t1 left join t2 on (t1.b = t2.b);  

do you think we have can do some optimization in this case? I don't understand 
your question well. 
 
15. The tests you've changed the expected outcome of in join.out
should be updated so that the GROUP BY and DISTINCT clause is not
removed. This will allow the test to continue testing what it was
intended to test. You can do this by changing the columns in the GROUP
BY clause so that the new code does not find uniquekeys for those
columns.   

Thanks for your explanation, very impressive!
 
16. The tests in aggregates.out are in a similar situation. There are
various tests trying to ensure that remove_useless_groupby_columns()
does what it's meant to do. You can modify these tests to add a join
which is non-unique to effectively duplicate the PK column.

17. In your select_distinct tests, can you move away from naming the
tables starting with select_distinct?  It makes reading queries pretty
hard.

e.g. explain (costs off) select distinct uk1, uk2 from
select_distinct_a where uk2 is not null;

When I first glanced that, I failed to see the underscores and the
query looked invalid.

18. Check the spelling if "erased". You have it spelt as "ereased" in
a couple of locations.

OK,  I just installed a spell check plugin for my editor, hope it will catch such
errors next time. 
 
 
19. Please pay attention to the capitalisation of SQL keywords in the
test files you've modified. I understand we're very inconsistent in
this department in general, but we do at least try not to mix
capitalisation within the same file.  Basically, please upper case the
keywords in select_distinct.sql

20. In addition to the above, please try to wrap long SQL lines so
they're below 80 chars.

I'll review the patch in more detail once the above points have been addressed.

David
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
On Wed, 1 Apr 2020 at 13:45, Andy Fan <[hidden email]> wrote:

>> 5. I think you should be performing a bms_del_member during join
>> removal rather than removing this Assert()
>>
>> - Assert(bms_equal(rel->relids, root->all_baserels));
>>
>> FWIW, it's far from perfect that you've needed to delay the left join
>> removal, but I do understand why you've done it. It's also far from
>> perfect that you're including removed relations in the
>> total_table_pages calculation. c6e4133fae1 took some measures to
>> improve this calculation and this is making it worse again.
>>
> Since the removed relation depends on the UniqueKey which has to be
> calculated after  total_table_pages calculation in current code, so that's
> something I must do.  But if the relation is not removable,  there is no waste
> at all.  If it is removable,  such gain will much higher than the loss.  I'm
> not sure this should be a concern.

The reason join removals was done so early in planning before was to
save the planner from having to do additional work for relations which
were going to be removed later.  For example, building path lists.

> Actually looks the current remove_useless_join has some limits which can't
> remove a joinrel,  I still didn't figure out why.  In the past we have some limited
> ability to detect the unqiueness after join, so that's would be ok.  Since  we have
> such ability now,  this may be another opportunity to improve the join_is_removable
> function, but I'd not like put such thing in this patch.

Yeah, there's certainly more left join shapes that we could remove.
e.g when the left join relation is not a singleton rel.  We shouldn't
do anything to purposefully block additional join removals as a result
of adding UniqueKeys, but likely shouldn't go to any trouble to make
additional ones work. That can be done later.

> Since you said "far from perfect" twice for this point and I only get one reason (we
> may plan a node which we removed later),  do I miss the other one?

a) additional planning work by not removing the join sooner. b) wrong
total page calculation.

In theory b) could be fixed by subtracting the removed join rels pages
after we remove it, but unfortunately, there's no point since we've
built the paths by that time already and we really only use the value
to determine how much IO is going to be random vs sequential, which is
determined during set_base_rel_pathlists()

>> d. not_null_cols should not be a Relids type, it should be Bitmapset.
>>
> If it is a Bitmapset,  we have to pass it with "&" usually.  is it our practice?

Well, a Bitmapset pointer.   Relids is saved for range table indexes.
Storing anything else in there is likely to lead to confusion.

>> 12. The comment in the code below is not true. The List contains
>> Lists, of which contain UniqueKeys
>>
>> List    *uniquekeys; /* List of UniqueKey */
>>
> It is a list of UniqueKey,  the UniqueKey can have a list of exprs.

Hmm, so this is what I called a UniqueKeySet in the original patch.
I'm a bit divided by that change. With PathKeys, technically you can
make use of a Path with a given set of PathKeys if you only require
some leading subset of those keys.  That's not the case for
UniqueKeys, it's all or nothing, so perhaps having the singular name
is better than the plural name I gave it. However, I'm not certain.

(Really PathKey does not seem like a great name in the first place
since it has nothing to do with keys)

>> 13. I'm having trouble parsing the final sentence in:
>>
>> + * can only guarantee the uniqueness without considering the null values. This
>> + * field is necessary for remove_useless_join & reduce_unique_semijions since
>> + * these cases don't care about the null values.
>>
>> Why is the field which stores the nullability of the key required for
>> code that does not care about the nullability of the key?
>>
> The guarantee is introduced to for the following cases:
>
> create table t1 (a int primary key, b int);
> create table t2 (a int primary key, b int);
> select .. from t1,  (select b from t2 group by t2) t2 ..;
>
> -- b is nullable.  so t2(b) can't be a normal UniqueKey (which means b may have some
> duplicated rows)
> create unique index t2_uk_b on t2(b);
>
> -- the left join still can be removed since t2.b is a unique index and the nullable
> doesn't matter here.
> select t1.* from t1 left join t2 on (t1.b = t2.b);
>
> do you think we have can do some optimization in this case? I don't understand
> your question well.

OK, so by "don't care", you mean, don't duplicate NULL values.  I
assumed you had meant that it does not matter either way, as in: don't
mind if there are NULL values or not. It might be best to have a go at
changing the wording to be more explicit to what you mean there.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan
In reply to this post by David Rowley
The updated patch should fixed all the issues.  See the comments below for more
information. 

On Tue, Mar 31, 2020 at 9:44 AM David Rowley <[hidden email]> wrote:
On Sun, 29 Mar 2020 at 20:50, Andy Fan <[hidden email]> wrote:
> Some other changes made in the new patch:
> 1.   Fixed bug for UniqueKey calculation for OUTER join.
> 2.   Fixed some typo error in comments.
> 3.   Renamed the field "grantee" as "guarantee".

I've had a look over this patch. Thank for you doing further work on it.

I've noted down the following during my read of the code:

1. There seem to be some cases where joins are no longer being
detected as unique. This is evident in postgres_fdw.out. We shouldn't
be regressing any of these cases.

The issue here is  I didn't distinguish the one_row case in UniqueKey struct.
 Actually when a outer relation is join with a relation which has only one row,  
there must be at most one row match the outer join.The only-one-row case in 
postgres_fdw.out come from aggregation call.

Added a new field "onerow" in UniqueKey struct.  and optimize the onerow
UniqueKey to not record every exprs.  See add_uniquekey_for_onerow
and relation_is_onerow.  
 
2. The following change does not seem like it should be part of this
patch.  I understand you perhaps have done as you think it will
improve the performance of checking if an expression is in a list of
expressions.

- COMPARE_SCALAR_FIELD(varno);
+ /* Compare varattno first since it has higher selectivity than varno */
  COMPARE_SCALAR_FIELD(varattno);
+ COMPARE_SCALAR_FIELD(varno);

If you think that is true, then please do it as a separate effort and
provide benchmarks with your findings.

Rollbacked.  
 
3. list_all_members_in. I think this would be better named as
list_is_subset. Please follow the lead of bms_is_subset().
Additionally, you should Assert that IsPointerList is true as there's
nothing else to indicate that it can't be used for an int or Oid list.

Done
 
4. guarantee is not a very good name for the field in UniqueKey.
Maybe something like is_not_null?

I tried is_not_null, but when it is is_not_null equals false, it is a double 
negation, and not feel good for me.  At last, I used multi_nullvals to show
the UniqueKey may yield multi null values so the uniqueness is not guaranteed.
 
5. I think you should be performing a bms_del_member during join
removal rather than removing this Assert()

- Assert(bms_equal(rel->relids, root->all_baserels));

Done 

FWIW, it's far from perfect that you've needed to delay the left join
removal, but I do understand why you've done it. It's also far from
perfect that you're including removed relations in the
total_table_pages calculation. c6e4133fae1 took some measures to
improve this calculation and this is making it worse again.

6. Can you explain why you moved the populate_baserel_uniquekeys()
call out of set_plain_rel_size()?

7. I don't think the removal of rel_supports_distinctness() is
warranted.  Is it not ok to check if the relation has any uniquekeys?
It's possible, particularly in join_is_removable that this can save
quite a large amount of effort.

Done
 
8. Your spelling of unique is incorrect in many places:

src/backend/nodes/makefuncs.c: * makeUnqiueKey
src/backend/optimizer/path/uniquekeys.c:static List
*initililze_unqiuecontext_for_joinrel(RelOptInfo *joinrel,
src/backend/optimizer/path/uniquekeys.c: * check if combination of
unqiuekeys from both side is still useful for us,
src/backend/optimizer/path/uniquekeys.c:        outerrel_uniquekey_ctx
= initililze_unqiuecontext_for_joinrel(joinrel, outerrel);
src/backend/optimizer/path/uniquekeys.c:        innerrel_uniquekey_ctx
= initililze_unqiuecontext_for_joinrel(joinrel, innerrel);
src/backend/optimizer/path/uniquekeys.c: * we need to convert the
UnqiueKey from sub_final_rel to currel via the positions info in
src/backend/optimizer/path/uniquekeys.c:                ctx->pos =
pos; /* the position in current targetlist,  will be used to set
UnqiueKey */
src/backend/optimizer/path/uniquekeys.c: * Check if Unqiue key of the
innerrel is valid after join. innerrel's UniqueKey
src/backend/optimizer/path/uniquekeys.c: * initililze_unqiuecontext_for_joinrel
src/backend/optimizer/path/uniquekeys.c: * all the unqiuekeys which
are not possible to use later
src/backend/optimizer/path/uniquekeys.c:initililze_unqiuecontext_for_joinrel(RelOptInfo
*joinrel,  RelOptInfo *inputrel)
src/backend/optimizer/plan/analyzejoins.c:                      /*
This UnqiueKey is what we want */
src/backend/optimizer/plan/planner.c:   /* If we the result if unqiue
already, we just return the input_rel directly */
src/include/nodes/pathnodes.h: * exprs is a list of exprs which is
unqiue on current RelOptInfo.
src/test/regress/expected/join.out:-- XXXX: since b.id is unqiue now
so the group by cluase is erased, so
src/test/regress/expected/select_distinct.out:-- create unqiue index on dist_p
src/test/regress/expected/select_distinct.out:-- we also support
create unqiue index on each child tables
src/test/regress/sql/join.sql:-- XXXX: since b.id is unqiue now so the
group by cluase is erased, so
src/test/regress/sql/select_distinct.sql:-- create unqiue index on dist_p
src/test/regress/sql/select_distinct.sql:-- we also support create
unqiue index on each child tables
9. A few things wrong with the following fragment:

/* set the not null info now */
ListCell *lc;
foreach(lc, find_nonnullable_vars(qual))
{
Var *var = lfirst_node(Var, lc);
RelOptInfo *rel = root->simple_rel_array[var->varno];
if (var->varattno > InvalidAttrNumber)
rel->not_null_cols = bms_add_member(rel->not_null_cols, var->varattno);
}

a. including a function call in the foreach macro is not a practise
that we really follow. It's true that the macro now assigns the 2nd
param to a variable. Previous to 1cff1b95ab6 this was not the case and
it's likely best not to leave any bad examples around that code which
might get backported might follow.
b. We generally subtract InvalidAttrNumber from varattno when
including in a Bitmapset.
c. not_null_cols is not well named. I think notnullattrs
d. not_null_cols should not be a Relids type, it should be Bitmapset.

Above 2 Done
 
10. add_uniquekey_for_onerow() seems pretty wasteful.  Is there really
a need to add each item in the rel's targetlist to the uniquekey list?
What if we just add an empty list to the unique keys, that way if we
need to test if some expr is a superset of any uniquekey, then we'll
see it is as any set is a superset of an empty set.  Likely the empty
set of uniquekeys should be the only one in the rel's uniquekey list.

 
Now I use a single UniqueKey to show this situation.  See 
add_uniquekey_for_onerow and relation_is_onerow.  
 
11. In create_distinct_paths() the code is now calling
get_sortgrouplist_exprs() multiple times with the same input. I think
it would be better to just call it once and set the result in a local
variable.

Done
 
12. The comment in the code below is not true. The List contains
Lists, of which contain UniqueKeys

List    *uniquekeys; /* List of UniqueKey */

13. I'm having trouble parsing the final sentence in:

+ * can only guarantee the uniqueness without considering the null values. This
+ * field is necessary for remove_useless_join & reduce_unique_semijions since
+ * these cases don't care about the null values.

Why is the field which stores the nullability of the key required for
code that does not care about the nullability of the key?

Also please check your spelling of the word "join"

 
Actually I didn't find the spell error for "join".. 
 
14. In the following fragment, instead of using i+1, please assign the
FormData_pg_attribute to a variable named attr and use attr->attnum.
Also, please see what I mentioned above about subtracting
InvalidAttrNumber

+ rel->not_null_cols = bms_add_member(rel->not_null_cols, i+1);

Done
 
15. The tests you've changed the expected outcome of in join.out
should be updated so that the GROUP BY and DISTINCT clause is not
removed. This will allow the test to continue testing what it was
intended to test. You can do this by changing the columns in the GROUP
BY clause so that the new code does not find uniquekeys for those
columns.

Done
 
16. The tests in aggregates.out are in a similar situation. There are
various tests trying to ensure that remove_useless_groupby_columns()
does what it's meant to do. You can modify these tests to add a join
which is non-unique to effectively duplicate the PK column.

 
There are some exceptions at this part.  
1. The test for  remove_useless_groupby_columns has some overlap 
with our current erasing group node logic,  like the test for a single relation.
so I just modified 2 tests case for this purpose.
2. When I read the code in remove_useless_groupby_columns,  I found a 
new case for our UniqueKey.   
select * from m1 where a > (select avg(b) from m2 group by M1.A);
where the m1.a will have var->varlevelsup > 0, how should we set the UniqueKey
for this grouprel .  I add some in-completed check at add_uniquekey_from_sortgroups 
function. but I'm not sure if we need that. 
3.  remove_useless_groupby_columns maintains the parse->constraintDeps
when it depends on primary key,  but UniqueKey doesn't maintain such data. 
since we have translation layer which should protect us from the concurrency issue
and isolation issue.  Do we need to do that as well in UniqueKey?
 
17. In your select_distinct tests, can you move away from naming the
tables starting with select_distinct?  It makes reading queries pretty
hard.

e.g. explain (costs off) select distinct uk1, uk2 from
select_distinct_a where uk2 is not null;

When I first glanced that, I failed to see the underscores and the
query looked invalid. 
 
18. Check the spelling if "erased". You have it spelt as "ereased" in
a couple of locations.

19. Please pay attention to the capitalisation of SQL keywords in the
test files you've modified. I understand we're very inconsistent in
this department in general, but we do at least try not to mix
capitalisation within the same file.  Basically, please upper case the
keywords in select_distinct.sql

20. In addition to the above, please try to wrap long SQL lines so
they're below 80 chars.

All above 4 item Done.
 
I'll review the patch in more detail once the above points have been addressed.
 
David

v4-0001-Maintain-UniqueKey-at-each-RelOptInfo-this-inform.patch (118K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
On Fri, 3 Apr 2020 at 15:18, Andy Fan <[hidden email]> wrote:

>
> The updated patch should fixed all the issues.  See the comments below for more
> information.
>
> On Tue, Mar 31, 2020 at 9:44 AM David Rowley <[hidden email]> wrote:
>>
>> + * can only guarantee the uniqueness without considering the null values. This
>> + * field is necessary for remove_useless_join & reduce_unique_semijions since
>> + * these cases don't care about the null values.
>>
>> Why is the field which stores the nullability of the key required for
>> code that does not care about the nullability of the key?
>>
>> Also please check your spelling of the word "join"
>>
>
> Actually I didn't find the spell error for "join"..

It was in reduce_unique_semijions. That should be
reduce_unique_semijoins. I see you fixed it in the patch though.

> 3.  remove_useless_groupby_columns maintains the parse->constraintDeps
> when it depends on primary key,  but UniqueKey doesn't maintain such data.
> since we have translation layer which should protect us from the concurrency issue
> and isolation issue.  Do we need to do that as well in UniqueKey?

I'm pretty sure that code is pretty bogus in
remove_useless_groupby_columns(). It perhaps was just copied from
check_functional_grouping(), where it is required. Looks like the
(ahem) author of d4c3a156c got that wrong... :-(

The reason check_functional_grouping() needs it is for things like
creating a view with a GROUP BY clause that has a column in the SELECT
list that is functionally dependant on the GROUP BY columns. e.g:

create table z (a int primary key, b int);
create view view_z as select a,b from z group by a;
alter table z drop constraint z_pkey;
ERROR:  cannot drop constraint z_pkey on table z because other objects
depend on it
DETAIL:  view view_z depends on constraint z_pkey on table z
HINT:  Use DROP ... CASCADE to drop the dependent objects too.

Here that view would become invalid if the PK was dropped, so we must
record the dependency in that case.  Doing so is what causes that
error message.

For just planner smarts such as LEFT JOIN removal, Unique Joins, and
all this Unique Key stuff, we really don't need to record the
dependency as if the index or constraint is dropped, then that'll
cause a relcache invalidation and we'll see the invalidation when we
attempt to execute the cached plan. That will cause the statement to
be re-planned and we'll not see the unique index when we do that.

We should probably just get rid of that code in
remove_useless_groupby_columns() to stop people getting confused about
that.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Tom Lane-2
David Rowley <[hidden email]> writes:
> For just planner smarts such as LEFT JOIN removal, Unique Joins, and
> all this Unique Key stuff, we really don't need to record the
> dependency as if the index or constraint is dropped, then that'll
> cause a relcache invalidation and we'll see the invalidation when we
> attempt to execute the cached plan. That will cause the statement to
> be re-planned and we'll not see the unique index when we do that.

You need to make sure that the thing you're concerned about will actually
cause a relcache invalidation of a table in the query.  But yeah, if it
will then there's not a need to have any other invalidation mechanism.

(It occurs to me BTW that we've been overly conservative about using
NOT NULL constraints in planning, because of failing to consider that.
Addition or drop of NOT NULL has to cause a change in
pg_attribute.attnotnull, which will definitely cause a relcache inval
on its table, cf rules in CacheInvalidateHeapTuple().  So we *don't*
need to have a pg_constraint entry corresponding to the NOT NULL, as
we've mistakenly supposed in some past discussions.)

                        regards, tom lane


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
On Fri, 3 Apr 2020 at 16:40, Tom Lane <[hidden email]> wrote:
> (It occurs to me BTW that we've been overly conservative about using
> NOT NULL constraints in planning, because of failing to consider that.
> Addition or drop of NOT NULL has to cause a change in
> pg_attribute.attnotnull, which will definitely cause a relcache inval
> on its table, cf rules in CacheInvalidateHeapTuple().  So we *don't*
> need to have a pg_constraint entry corresponding to the NOT NULL, as
> we've mistakenly supposed in some past discussions.)

Agreed for remove_useless_groupby_columns(), but we'd need it if we
wanted to detect functional dependencies in
check_functional_grouping() using unique indexes.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan


On Fri, Apr 3, 2020 at 12:08 PM David Rowley <[hidden email]> wrote:
On Fri, 3 Apr 2020 at 16:40, Tom Lane <[hidden email]> wrote:
> (It occurs to me BTW that we've been overly conservative about using
> NOT NULL constraints in planning, because of failing to consider that.
> Addition or drop of NOT NULL has to cause a change in
> pg_attribute.attnotnull, which will definitely cause a relcache inval
> on its table, cf rules in CacheInvalidateHeapTuple().  So we *don't*
> need to have a pg_constraint entry corresponding to the NOT NULL, as
> we've mistakenly supposed in some past discussions.)

Agreed for remove_useless_groupby_columns(), but we'd need it if we
wanted to detect functional dependencies in
check_functional_grouping() using unique indexes.

Thanks for the explanation.  I will add the removal in the next version of this
patch.

Best Regards
Andy Fan
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
On Fri, 3 Apr 2020 at 21:56, Andy Fan <[hidden email]> wrote:

>
>
>
> On Fri, Apr 3, 2020 at 12:08 PM David Rowley <[hidden email]> wrote:
>>
>> On Fri, 3 Apr 2020 at 16:40, Tom Lane <[hidden email]> wrote:
>> > (It occurs to me BTW that we've been overly conservative about using
>> > NOT NULL constraints in planning, because of failing to consider that.
>> > Addition or drop of NOT NULL has to cause a change in
>> > pg_attribute.attnotnull, which will definitely cause a relcache inval
>> > on its table, cf rules in CacheInvalidateHeapTuple().  So we *don't*
>> > need to have a pg_constraint entry corresponding to the NOT NULL, as
>> > we've mistakenly supposed in some past discussions.)
>>
>> Agreed for remove_useless_groupby_columns(), but we'd need it if we
>> wanted to detect functional dependencies in
>> check_functional_grouping() using unique indexes.
>
>
> Thanks for the explanation.  I will add the removal in the next version of this
> patch.

There's no need for this patch to touch
remove_useless_groupby_columns().  Fixes for that should be considered
independently and *possibly* even backpatched.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
In reply to this post by Andy Fan
On Fri, 3 Apr 2020 at 15:18, Andy Fan <[hidden email]> wrote:
> All above 4 item Done.

Just to explain my view on this going forward for PG14.  I do plan to
do a more thorough review of this soon.  I wasn't so keen on pursuing
this for PG13 as the skip scans patch [1] needs to use the same
infrastructure this patch has added and it does not, yet.

The infrastructure (knowing the unique properties of a RelOptInfo), as
provided by the patch Andy has been working on, which is based on my
rough prototype version, I believe should be used for the skip scans
patch as well.  I understand that as skip scans currently stands,
Jasper has done quite a bit of work to add the UniqueKeys, however,
this was unfortunately based on some early description of UniqueKeys
where I had thought that we could just store EquivalenceClasses. I no
longer think that's the case, and I believe the implementation that we
require is something more along the lines of Andy's latest version of
the patch.  However, I've not quite stared at it long enough to be
highly confident in that.

I'd like to strike up a bit of a plan to move both Andy's work and the
Skip scans work forward for PG14.

Here are my thoughts so far:

1. Revise v4 of remove DISTINCT patch to split the patch into two pieces.

0001 should add the UniqueKey code but not any additional planner
smarts to use them (i.e remove GROUP BY / DISTINCT) elimination parts.
Join removals and Unique joins should use UniqueKeys in this patch.
0002 should add back the GROUP BY  / DISTINCT smarts and add whatever
tests should be added for that and include updating existing expected
results and modifying any tests which no longer properly test what
they're meant to be testing.

I've done this with the attached patch.

2. David / Jesper to look at 0001 and build or align the existing skip
scans 0001 patch to make use of Andy's 0001 patch. This will require
tagging UniqueKeys onto Paths, not just RelOptInfos, plus a bunch of
other work.


Clearly UniqueKeys must suit both needs and since we have two
different implementations each providing some subset of the features,
then clearly we're not yet ready to move both skip scans and this
patch forward together. We need to align that and move both patches
forward together. Hopefully, the attached 0001 patch helps move that
along.



While I'm here, a quick review of Andy's v4 patch. I didn't address
any of this in the attached v5. These are only based on what I saw
when shuffling some code around. It's not an in-depth review.

1. Out of date comment in join.sql

-- join removal is not possible when the GROUP BY contains a column that is
-- not in the join condition.  (Note: as of 9.6, we notice that b.id is a
-- primary key and so drop b.c_id from the GROUP BY of the resulting plan;
-- but this happens too late for join removal in the outer plan level.)
explain (costs off)
select d.* from d left join (select d, c_id from b group by b.d, b.c_id) s
  on d.a = s.d;

You've changed the GROUP BY clause so it does not include b.id, so the
Note in the comment is now misleading.

2. I think 0002 is overly restrictive in its demands that
parse->hasAggs must be false. We should be able to just use a Group
Aggregate with unsorted input when the input_rel is unique on the
GROUP BY clause.  This will save on hashing and sorting.  Basically
similar to what we do for when a query contains aggregates without any
GROUP BY.

3. I don't quite understand why you changed this to a right join:

 -- Test case where t1 can be optimized but not t2
 explain (costs off) select t1.*,t2.x,t2.z
-from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
+from t1 right join t2 on t1.a = t2.x and t1.b = t2.y

Perhaps this change is left over from some previous version of the patch?

[1] https://commitfest.postgresql.org/27/1741/

v5-0001-Introduce-UniqueKeys-to-determine-RelOptInfo-uniq.patch (87K) Download Attachment
v5-0002-Skip-DISTINCT-GROUP-BY-if-input-is-already-unique.patch (33K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan
Hi David:

Thanks for your time. 
 
1. Out of date comment in join.sql

-- join removal is not possible when the GROUP BY contains a column that is
-- not in the join condition.  (Note: as of 9.6, we notice that b.id is a
-- primary key and so drop b.c_id from the GROUP BY of the resulting plan;
-- but this happens too late for join removal in the outer plan level.)
explain (costs off)
select d.* from d left join (select d, c_id from b group by b.d, b.c_id) s
  on d.a = s.d;

You've changed the GROUP BY clause so it does not include b.id, so the
Note in the comment is now misleading.

Thanks, I will fix this one in the following patch. 
 

2. I think 0002 is overly restrictive in its demands that
parse->hasAggs must be false. We should be able to just use a Group
Aggregate with unsorted input when the input_rel is unique on the
GROUP BY clause.  This will save on hashing and sorting.  Basically
similar to what we do for when a query contains aggregates without any
GROUP BY.


Yes,  This will be a perfect result,  the difficult is the current aggregation function
execution is highly coupled with Agg node(ExecInitAgg) which is removed in the
unique case.  I ever make the sum (w/o finalfn) and avg(with finalfn)
works in a hack way, but still many stuffs is not handled.  Let me prepare the code
for this purpose in 1~2  days to see if I'm going with the right direction. 

Ashutosh also has an idea[1] that if the relation underlying an Agg node is 
known to be unique for given groupByClause, we could safely use 
AGG_SORTED strategy. Though the input is not ordered, it's sorted thus for every row Agg
node will combine/finalize the aggregate result.  

I will target the perfect result first and see how many effort do we need, if not,
I will try Ashutosh's suggestion. 

 
3. I don't quite understand why you changed this to a right join:

 -- Test case where t1 can be optimized but not t2
 explain (costs off) select t1.*,t2.x,t2.z
-from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
+from t1 right join t2 on t1.a = t2.x and t1.b = t2.y

Perhaps this change is left over from some previous version of the patch?

This is on purpose.   the original test case is used to test we can short
the group key for t1 but not t2 for aggregation, but if I keep the inner join, the 
aggnode will be removed totally, so I have to change it to right join in order
to keep the aggnode.  The full test case is:

-- Test case where t1 can be optimized but not t2

explain (costs off) select t1.*,t2.x,t2.z

from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y

group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;


where (a, b) is the primary key of t1. 



Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

David Rowley
On Wed, 15 Apr 2020 at 12:19, Andy Fan <[hidden email]> wrote:

>
>> 2. I think 0002 is overly restrictive in its demands that
>> parse->hasAggs must be false. We should be able to just use a Group
>> Aggregate with unsorted input when the input_rel is unique on the
>> GROUP BY clause.  This will save on hashing and sorting.  Basically
>> similar to what we do for when a query contains aggregates without any
>> GROUP BY.
>>
>
> Yes,  This will be a perfect result,  the difficult is the current aggregation function
> execution is highly coupled with Agg node(ExecInitAgg) which is removed in the
> unique case.

This case here would be slightly different. It would be handled by
still creating a Group Aggregate path, but just not consider Hash
Aggregate and not Sort the input to the Group Aggregate path. Perhaps
that's best done by creating a new flag bit and using it in
create_grouping_paths() in the location where we set the flags
variable.  If you determine that the input_rel is unique for the GROUP
BY clause, and that there are aggregate functions, then set a flag,
e.g GROUPING_INPUT_UNIQUE. Likely there will be a few other flags that
you can skip setting in that function, for example, there's no need to
check if the input can sort, so no need for GROUPING_CAN_USE_SORT,
since you won't need to sort, likewise for GROUPING_CAN_USE_HASH. I'd
say there also is no need for checking if we can set
GROUPING_CAN_PARTIAL_AGG (What would be the point in doing partial
aggregation when there's 1 row per group?)   Then down in
add_paths_to_grouping_rel(), just add a special case before doing any
other code, such as:

if ((extra->flags & GROUPING_INPUT_UNIQUE) != 0 && parse->groupClause != NIL)
{
Path    *path = input_rel->cheapest_total_path;

add_path(grouped_rel, (Path *)
create_agg_path(root,
grouped_rel,
path,
grouped_rel->reltarget,
AGG_SORTED,
AGGSPLIT_SIMPLE,
parse->groupClause,
havingQual,
agg_costs,
dNumGroups));
return;
}

You may also want to consider the cheapest startup path there too so
that the LIMIT processing can do something smarter later in planning
(assuming cheapest_total_path != cheapest_startup_path (which you'd
need to check for)).

Perhaps it would be better to only set the GROUPING_INPUT_UNIQUE if
there is a groupClause, then just Assert(parse->groupClause != NIL)
inside that if.

David


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan


On Wed, Apr 15, 2020 at 11:00 AM David Rowley <[hidden email]> wrote:
On Wed, 15 Apr 2020 at 12:19, Andy Fan <[hidden email]> wrote:
>
>> 2. I think 0002 is overly restrictive in its demands that
>> parse->hasAggs must be false. We should be able to just use a Group
>> Aggregate with unsorted input when the input_rel is unique on the
>> GROUP BY clause.  This will save on hashing and sorting.  Basically
>> similar to what we do for when a query contains aggregates without any
>> GROUP BY.
>>
>
> Yes,  This will be a perfect result,  the difficult is the current aggregation function
> execution is highly coupled with Agg node(ExecInitAgg) which is removed in the
> unique case.

This case here would be slightly different. It would be handled by
still creating a Group Aggregate path, but just not consider Hash
Aggregate and not Sort the input to the Group Aggregate path. Perhaps
that's best done by creating a new flag bit and using it in
create_grouping_paths() in the location where we set the flags
variable.  If you determine that the input_rel is unique for the GROUP
BY clause, and that there are aggregate functions, then set a flag,
e.g GROUPING_INPUT_UNIQUE. Likely there will be a few other flags that
you can skip setting in that function, for example, there's no need to
check if the input can sort, so no need for GROUPING_CAN_USE_SORT,
since you won't need to sort, likewise for GROUPING_CAN_USE_HASH. I'd
say there also is no need for checking if we can set
GROUPING_CAN_PARTIAL_AGG (What would be the point in doing partial
aggregation when there's 1 row per group?)   Then down in
add_paths_to_grouping_rel(), just add a special case before doing any
other code, such as:

if ((extra->flags & GROUPING_INPUT_UNIQUE) != 0 && parse->groupClause != NIL)
{
Path    *path = input_rel->cheapest_total_path;

add_path(grouped_rel, (Path *)
create_agg_path(root,
grouped_rel,
path,
grouped_rel->reltarget,
AGG_SORTED,
AGGSPLIT_SIMPLE,
parse->groupClause,
havingQual,
agg_costs,
dNumGroups));
return;
}

You may also want to consider the cheapest startup path there too so
that the LIMIT processing can do something smarter later in planning
(assuming cheapest_total_path != cheapest_startup_path (which you'd
need to check for)).

Perhaps it would be better to only set the GROUPING_INPUT_UNIQUE if
there is a groupClause, then just Assert(parse->groupClause != NIL)
inside that if.


Thank you for your detailed explanation.   The attached v6 has included this feature.  
Here is the the data to show the improvement.

Test cases:
create table grp2 (a int primary key, b char(200), c int);
insert into grp2 select i, 'x', i from generate_series(1, 10000000)i;
analyze grp2;
explain analyze select a, sum(c) from grp2 group by a;

w/o this feature:

postgres=# explain analyze select a, sum(c) from grp2 group by a;
                                                                 QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
 GroupAggregate  (cost=0.43..712718.44 rows=10000000 width=12) (actual time=0.088..15491.027 rows=10000000 loops=1)
   Group Key: a
   ->  Index Scan using grp2_pkey on grp2  (cost=0.43..562718.44 rows=10000000 width=8) (actual time=0.068..6503.459 rows=10000000 loops=1)
 Planning Time: 0.916 ms
 Execution Time: 16252.397 ms
(5 rows)

Since the order of my data in heap and index is exactly same, which makes
the index scan much faster.  The following is to test the cost of the *hash* aggregation,

postgres=# set enable_indexscan to off;
SET
postgres=# explain analyze select a, sum(c) from grp2 group by a;
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=765531.00..943656.00 rows=10000000 width=12) (actual time=14424.379..30133.171 rows=10000000 loops=1)
   Group Key: a
   Planned Partitions: 128
   Peak Memory Usage: 4153 kB
   Disk Usage: 2265608 kB
   HashAgg Batches: 640
   ->  Seq Scan on grp2  (cost=0.00..403031.00 rows=10000000 width=8) (actual time=0.042..2808.281 rows=10000000 loops=1)
 Planning Time: 0.159 ms
 Execution Time: 31098.804 ms
(9 rows)

With this feature:
explain analyze select a, sum(c) from grp2 group by a;
                                                        QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
 GroupAggregate  (cost=0.00..553031.57 rows=10000023 width=12) (actual time=0.044..13209.485 rows=10000000 loops=1)
   Group Key: a
   ->  Seq Scan on grp2  (cost=0.00..403031.23 rows=10000023 width=8) (actual time=0.023..4938.171 rows=10000000 loops=1)
 Planning Time: 0.400 ms
 Execution Time: 13749.121 ms
(5 rows)

During the implementation,  I also added AGG_UNIQUE AggStrategy to 
record this information in Agg Plan node, this is a simple way to do it and
should be semantic correct. 

V6 also includes:
1.  Fix the comment misleading you mentioned above.
2.  Fixed a concern case for `relation_has_uniquekeys_for` function. 

+       /* For UniqueKey->onerow case, the uniquekey->exprs is empty as well
+        * so we can't rely on list_is_subset to handle this special cases
+        */
+       if (exprs == NIL)
+               return false;


Best Regards
Andy Fan

v6-0002-Skip-DISTINCT-GROUP-BY-if-input-is-already-unique.patch (49K) Download Attachment
v6-0001-Introduce-UniqueKeys-to-determine-RelOptInfo-uniq.patch (88K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Ashutosh Bapat-2
On Thu, Apr 16, 2020 at 7:47 AM Andy Fan <[hidden email]> wrote:

> (9 rows)
>
> With this feature:
> explain analyze select a, sum(c) from grp2 group by a;
>                                                         QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------
>  GroupAggregate  (cost=0.00..553031.57 rows=10000023 width=12) (actual time=0.044..13209.485 rows=10000000 loops=1)
>    Group Key: a
>    ->  Seq Scan on grp2  (cost=0.00..403031.23 rows=10000023 width=8) (actual time=0.023..4938.171 rows=10000000 loops=1)
>  Planning Time: 0.400 ms
>  Execution Time: 13749.121 ms
> (5 rows)
>

Applying the patch gives a white space warning
git am /tmp/v6-000*
Applying: Introduce UniqueKeys to determine RelOptInfo unique properties
.git/rebase-apply/patch:545: indent with spaces.
    /* Fast path */
warning: 1 line adds whitespace errors.
Applying: Skip DISTINCT / GROUP BY if input is already unique

Compiling the patch causes one warning
nodeAgg.c:2134:3: warning: enumeration value ‘AGG_UNIQUE’ not handled
in switch [-Wswitch]

I have not looked at the patch. The numbers above look good. The time
spent in summing up a column in each row (we are summing only one
number per group) is twice the time it took to read those rows from
the table. That looks odd. But it may not be something unrelated to
your patch. I also observed that for explain analyze select a from
grp2 group by a; we just produce a plan containing seq scan node,
which is a good thing.


--
Best Wishes,
Ashutosh Bapat


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Keeps tracking the uniqueness with UniqueKey

Andy Fan


On Thu, Apr 16, 2020 at 8:36 PM Ashutosh Bapat <[hidden email]> wrote:
On Thu, Apr 16, 2020 at 7:47 AM Andy Fan <[hidden email]> wrote:

> (9 rows)
>
> With this feature:
> explain analyze select a, sum(c) from grp2 group by a;
>                                                         QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------
>  GroupAggregate  (cost=0.00..553031.57 rows=10000023 width=12) (actual time=0.044..13209.485 rows=10000000 loops=1)
>    Group Key: a
>    ->  Seq Scan on grp2  (cost=0.00..403031.23 rows=10000023 width=8) (actual time=0.023..4938.171 rows=10000000 loops=1)
>  Planning Time: 0.400 ms
>  Execution Time: 13749.121 ms
> (5 rows)
>

Applying the patch gives a white space warning
git am /tmp/v6-000*
Applying: Introduce UniqueKeys to determine RelOptInfo unique properties
.git/rebase-apply/patch:545: indent with spaces.
    /* Fast path */
warning: 1 line adds whitespace errors.
Applying: Skip DISTINCT / GROUP BY if input is already unique

Compiling the patch causes one warning
nodeAgg.c:2134:3: warning: enumeration value ‘AGG_UNIQUE’ not handled
in switch [-Wswitch]


Thanks, I will fix them together with some detailed review suggestion.  
(I know the review need lots of time, so appreciated for it).  
 
I have not looked at the patch. The numbers above look good. The time
spent in summing up a column in each row (we are summing only one
number per group) is twice the time it took to read those rows from
the table. That looks odd. But it may not be something unrelated to
your patch. I also observed that for explain analyze select a from
grp2 group by a; we just produce a plan containing seq scan node,
which is a good thing.

Great and welcome back Ashutosh:)  
 
--
Best Wishes,
Ashutosh Bapat
123