[PATCH] Keeps tracking the uniqueness with UniqueKey

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!

[1]
https://www.postgresql.org/message-id/flat/CAKU4AWqOORqW900O-%2BL4L2%2B0xknsEqpfcs9FF7SeiO9TmpeZOg%40mail.gmail.com#f5d97cc66b9cd330add2fbb004a4d107

[2]
https://www.postgresql.org/message-id/CAKU4AWqOORqW900O-%2BL4L2%2B0xknsEqpfcs9FF7SeiO9TmpeZOg%40mail.gmail.com

Best regards
Andy Fan