Thread: UniqueKey v2

UniqueKey v2

From
zhihuifan1213@163.com
Date:
Hi,

David and I had worked the uniquekey stuff since 2020[1], and later it
is blocked by the NULL values stuff. Now the blocker should be removed
by Var.varnullingrels, so it is time to work on this again. During the
past 3 years, we have found more and more interesting usage of it. 

Here is a design document and a part of implementation.

What is UniqueKey?
-----------------

UniqueKey represents a uniqueness information for a RelOptInfo. for
example:  

SELECT id FROM t;

where the ID is the UniqueKey for the RelOptInfo (t).  In the real word,
it has the following attributes:

1). It should be EquivalenceClass based. for example:

SELECT a FROM t WHERE a = id;

In this case, the UniqueKey should be 1 EC with two members
- EC(EM(a), EM(id)). 


2). Each UniqueKey may be made up with 1+ EquivalenceClass. for example:

CREATE TABLE t(a int not null,  b int not null);
CREATE UNIQUE INDEX on t(a, b);
SELECT * FROM t;

Where the UniqueKey for RelOptInfo (t) will be 2 ECs with each 1 has 1
member.

- EC(em=a), EC(em=b)

3). Each RelOptInfo may have 1+ UniqueKeys.

CREATE TABLE t(a int not null,  b int not null, c int not null);
CREATE UNIQUE INDEX on t(a, b);
CREATE UNIQUE INDEX on t(c);

SELECT * FROM t;

Where the UniqueKey for RelOptInfo (t) will be
- [EC(em=a), EC(em=b)].
- [EC(em=c)]

4). A special case is about the one-row case. It works like:
SELECT * FROM t WHERE id = 1;
Here every single expression in the RelOptInfo (t) is unique. 

Where can we use it?
--------------------
1. mark the distinct as no-op.  SELECT DISTINCT uniquekey FROM v; This
  optimization has been required several times in our threads. 
  
2. Figure out more pathkey within the onerow case, then some planning
  time can be reduced to be big extend. This user case is not absurd, I
  run into a real user case like this: 
  
  CREATE TABLE small_t (id int primary key, b int, c int .. u int);
  CREATE INDEX ON small_t(b);
  CREATE INDEX ON small_t(c);
  ..

  SELECT * FROM small_t s
    JOIN t1 on t1.sb = s.b
    JOIN T2 on t2.sc = s.c
    ..
    JOIN t20 on t20.su = s.u
  WHERE s.id = 1;

  Without the above optimization, we don't know s.b /s.c is ordered
  already, so it might keep more different paths for small_t because of
  they have different interesting pathkey, and use more planning time
  for sorting to support merge join.
  
  With the above optimization, the planning time should be reduced since
  the seq scan can produce a ordered result for every expression. 
  
3. Figure out more interesting pathkey after join with normal UniqueKey.

  CREATE TABLE t(id int primary key, b int, c int);
  CREATE INDEX on t(c);
  ANALYZE t;

  explain (costs off)
  select t1.id, t2.c from t t1
    join t1 t2 on t1.id = t2.b
    and t2.c > 3
  order by t1.id, t2.c;

                    QUERY PLAN                    
  --------------------------------------------------
  Sort Key: t1.id, t2.c   <---  this sort can be avoided actually. 
  ->  Nested Loop
        Join Filter: (t1.id = t2.b)
        ->  Index Only Scan using t_pkey on t t1
        ->  Index Scan using t1_c_idx on t1 t2
              Index Cond: (c > 3)

  *Without knowing the t1.id is unique*,  which means there are some
  duplicated data in t1.id, the duplication data in t1 will break the
  order of (t1.id, t2.c), but if we know the t1.id is unique, the sort
  will be not needed.  I'm pretty happy with this finding.
      
4. Optimize some group by case, like

  SELECT id, sum(b) FROM t GROUP BY id
  is same with
  SELECT id, b from t;

  I'm not sure how often it is in the real life, I'm not so excited with
  this for now.

  
How to present ECs in UniqueKey?
--------------------------------

I choose "Bitmapset *eclass_indexes;" finally, which is because
Bitmapset is memory compact and good at bms_union,  bms_is_subset
stuffs. The value in the bitmap is the positions in root->eq_classes. It
is also be able to present the UniqueKey which is made up from multi
relations or upper relation. I'm pleased with the EC strategy because
the existing logic would even create a EC with single members which
means we don't need to create any EquivalenceClass for our own. for
example, in the case of 

SELECT DISTINCT pk FROM t;

a EquivalenceClass with single member is created.


How to present single row in UniqueKey
-------------------------------------

I just use a 'Index relid', an non-zero value means the
RelOptInfo[relid] is single row.  For the case like

SELECT * FROM t WHERE id = 1;
The UniqueKey is:
- UniqueKey(eclass_indexes=NULL, relid=1)

during a join, any unique keys join with single row, it's uniqueness can
be kept.

SELECT t1.uk, t2.a FROM t WHERE t2.id = 1 and any-qual(t1, t2);
- UniqueKey (t1.uk)

more specially, join two single row like:

SELECT * FROM t1 join t2 on true where t1.id = 1 and t2.id = 2;

the UniqueKey for the JoinRel will be:
- UniqueKey(eclass_indexes=NULL, relid=1)
- UniqueKey(eclass_indexes=NULL, relid=2)

However, the current single row presentation can't works well with Upper
relation, which I think it would be acceptable. See the following case:

SELECT count(*) FROM t1 JOIN t2 on true;


How to maintain the uniquekey?
-------------------------------
the uniquekey is maintained from baserel to join rel then to upper
relation. In the base rel, it comes from unique index. From the join
relation, it is maintained with two rules:

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

  SELECT t1.pk FROM t1 JOIN t2 ON t1.a = t2.pk;
  UniqueKey on t1:  t1.pk
  UniqueKey on t1 Join t2:  t1.pk

- The combined unique key from both sides are unique all the times.
  SELECT t1.pk , t2.pk FROM t1 join t2 on true;
  UniqueKey on t1 join t2:  (t1.pk, t2.pk)

Some other operations like DISTINCT, GROUP BY can produce UniqueKey as well.

NULL values
-----------
I added notnullattrs in RelOptInfo, which present if these attributes may
not be NULL after the baserestrictinfo is executed. not-null-attributes
may be generated by not-null constraint in catalog or baserestrictinfo
(only) filter. However it is possible become NULLs because of outer
join, then Var.varnullingrels is used in this case. see
'var_is_nullable' function call. 

To simplify the UniqueKey module, it doesn't care about the null values
during the maintaining, which means it may contains multi NULL values
all the time by design. However whenever a user case care about that,
the user case can get the answer with the above logic, that is what
'mark-distinct-as-noop' does. 

How to reduce the overhead
----------------------------------
UniqueKey employs the similar strategy like PathKey, it only maintain
the interesting PathKey. Currently the interesting UniqueKey includes:
1). It is subset of distinct_pathkeys.
2). It is used in mergeable join clauses for unique key deduction (for
the join rel case, rule 1). In this case, it can be discarded quickly if
the join has been done.

To avoid to check if an uniquekey is subset of distinct clause again and
again, I cached the result into UnqiueKey struct during the UniqueKey
creation. 

Since our first goal is just used for marking distinct as no-op, so if
there is no distinct clause at all, unique key will be not maintained at
the beginning. so we can have some codes like:

if (root->distinct_pathkeys == NULL)
return;

This fast path is NOT added for now for better code coverage.

What I have now:
----------------

The current patch just maintain the UniqueKey at the baserel level and
used it for mark-distinct-as-noop purpose. including the basic idea of

- How the UniqueKey is defined. 
- How to find out the interesting pathkey in the base relation level.
- How to figure out the unique key contains NULL values.

Also the test cases are prepared, see uniquekey.sql.

Some deep issues can only be found during the development, but I still
like to gather more feedback to see if anything is wrong at the first
place. Like what role will the collation play on for UniqueKey.

Any thought?



Thanks.

[1]
https://www.postgresql.org/message-id/CAApHDvrBXjAvH45dEAZFOk-hzOt1mJC7-fxZ2v49mc5njtA7VQ%40mail.gmail.com

Best Regards
Andy Fan

Attachment

Re: UniqueKey v2

From
jian he
Date:
hi.
After `git am`, I still cannot build.

../../Desktop/pg_sources/main/postgres/src/backend/optimizer/path/uniquekey.c:125:45:
error: variable ‘var’ set but not used
[-Werror=unused-but-set-variable]
  125 |                         Var                *var;
      |                                             ^~~


You also need to change src/backend/optimizer/path/meson.build.

git apply failed.

git am warning:
Applying: uniquekey on base relation and used it for mark-distinct-as-op.
.git/rebase-apply/patch:876: new blank line at EOF.
+
warning: 1 line adds whitespace errors.

I think you can use `git diff --check`
(https://git-scm.com/docs/git-diff) to check for whitespace related
errors.



Re: UniqueKey v2

From
zhihuifan1213@163.com
Date:
jian he <jian.universality@gmail.com> writes:

Hi jian,

> hi.
> After `git am`, I still cannot build.
>
> ../../Desktop/pg_sources/main/postgres/src/backend/optimizer/path/uniquekey.c:125:45:
> error: variable ‘var’ set but not used
> [-Werror=unused-but-set-variable]
>   125 |                         Var                *var;
>       |                                             ^~~

Thanks for this report, looks clang 11 can't capture this error.  I have
switched to clang 17 which would report this issue at the first place.

>
> You also need to change src/backend/optimizer/path/meson.build.

Great thanks.

>
> git apply failed.
>
> git am warning:
> Applying: uniquekey on base relation and used it for mark-distinct-as-op.
> .git/rebase-apply/patch:876: new blank line at EOF.
> +
> warning: 1 line adds whitespace errors.
>
> I think you can use `git diff --check`
> (https://git-scm.com/docs/git-diff) to check for whitespace related
> errors.

thanks for the really good suggestion.  Here is the newer version:



-- 
Best Regards
Andy Fan

Attachment

Re: UniqueKey v2

From
jian he
Date:
On Tue, Oct 17, 2023 at 11:21 AM <zhihuifan1213@163.com> wrote:
>
>
> thanks for the really good suggestion.  Here is the newer version:
>

--- a/src/backend/optimizer/path/meson.build
+++ b/src/backend/optimizer/path/meson.build
@@ -10,4 +10,5 @@ backend_sources += files(
   'joinrels.c',
   'pathkeys.c',
   'tidpath.c',
+  'uniquekey.c'
 )
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 3ac25d47..5ed550ca 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -264,7 +264,10 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,

    int strategy, bool nulls_first);
 extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,

 List *live_childrels);
-
+/*
+ * uniquekey.c
+ *     uniquekey.c related functions.
+ */

---------
i did some simple tests using text data type.

it works with the primary key, not with unique indexes.
it does not work when the column is unique, not null.

The following is my test.

begin;
CREATE COLLATION case_insensitive (provider = icu, locale =
'und-u-ks-level2', deterministic = false);
CREATE COLLATION upper_first (provider = icu, locale = 'und-u-kf-upper');
commit;
begin;
CREATE TABLE test_uniquekey3(a text, b text);
CREATE TABLE test_uniquekey4(a text, b text);
CREATE TABLE test_uniquekey5(a text, b text);
CREATE TABLE test_uniquekey6(a text, b text);
CREATE TABLE test_uniquekey7(a text not null, b text not null);
CREATE TABLE test_uniquekey8(a text not null, b text not null);
CREATE TABLE test_uniquekey9(a text primary key COLLATE upper_first, b
text not null);
CREATE TABLE test_uniquekey10(a text primary key COLLATE
case_insensitive, b text not null);
create unique index on test_uniquekey3 (a COLLATE case_insensitive nulls first)
    nulls distinct
    with (fillfactor = 80);
create unique index on test_uniquekey4 (a COLLATE case_insensitive nulls first)
    nulls not distinct
    with (fillfactor = 80);
create unique index on test_uniquekey5 (a COLLATE upper_first nulls first)
    nulls distinct;
create unique index on test_uniquekey6 (a COLLATE upper_first nulls first)
    nulls not distinct;
create unique index on test_uniquekey7 (a COLLATE upper_first nulls
first) nulls distinct;
create unique index on test_uniquekey8 (a COLLATE case_insensitive
nulls first) nulls not distinct;
insert into test_uniquekey3(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey4(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey5(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey6(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey7(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey8(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey9(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey10(a,b) select g::text, (g+10)::text from
generate_series(1,1e5) g;
insert into test_uniquekey3(a) VALUES(null),(null),(null);
insert into test_uniquekey4(a) VALUES(null);
insert into test_uniquekey5(a) VALUES(null),(null),(null);
insert into test_uniquekey6(a) VALUES(null);
commit;

ANALYZE test_uniquekey3, test_uniquekey4, test_uniquekey5
        ,test_uniquekey6,test_uniquekey7, test_uniquekey8
        ,test_uniquekey9, test_uniquekey10;

explain (costs off) select distinct a from test_uniquekey3;
explain (costs off) select distinct a from test_uniquekey4;
explain (costs off) select distinct a from test_uniquekey5;
explain (costs off) select distinct a from test_uniquekey6;
explain (costs off) select distinct a from test_uniquekey7;
explain (costs off) select distinct a from test_uniquekey8;
explain (costs off) select distinct a from test_uniquekey9;
explain (costs off) select distinct a from test_uniquekey10;
explain (costs off) select distinct a from test_uniquekey3 where a < '2000';
explain (costs off) select distinct a from test_uniquekey4 where a < '2000';
explain (costs off) select distinct a from test_uniquekey5 where a < '2000';
explain (costs off) select distinct a from test_uniquekey6 where a < '2000';
explain (costs off) select distinct a from test_uniquekey7 where a < '2000';
explain (costs off) select distinct a from test_uniquekey8 where a < '2000';
explain (costs off) select distinct a from test_uniquekey9 where a < '2000';
explain (costs off) select distinct a from test_uniquekey10 where a < '2000';

--very high selectivity
explain (costs off) select distinct a from test_uniquekey3 where a < '1001';
explain (costs off) select distinct a from test_uniquekey4 where a < '1001';
explain (costs off) select distinct a from test_uniquekey5 where a < '1001';
explain (costs off) select distinct a from test_uniquekey6 where a < '1001';
explain (costs off) select distinct a from test_uniquekey7 where a < '1001';
explain (costs off) select distinct a from test_uniquekey8 where a < '1001';
explain (costs off) select distinct a from test_uniquekey9 where a < '1001';
explain (costs off) select distinct a from test_uniquekey10 where a < '1001';
explain (costs off,ANALYZE) select distinct a from test_uniquekey9
where a < '1001';
explain (costs off,ANALYZE) select distinct a from test_uniquekey10
where a < '1001';



Re: UniqueKey v2

From
zhihuifan1213@163.com
Date:
> i did some simple tests using text data type.
>
> it works with the primary key, not with unique indexes.
> it does not work when the column is unique, not null.
>
> The following is my test.

Can you simplify your test case please? I can't undertand what "doesn't
work" mean here and for which case. FWIW, this feature has nothing with
the real data, I don't think inserting any data is helpful unless I
missed anything. 


-- 
Best Regards
Andy Fan




Re: UniqueKey v2

From
jian he
Date:
On Fri, Oct 20, 2023 at 4:33 PM <zhihuifan1213@163.com> wrote:
>
>
> > i did some simple tests using text data type.
> >
> > it works with the primary key, not with unique indexes.
> > it does not work when the column is unique, not null.
> >
> > The following is my test.
>
> Can you simplify your test case please? I can't undertand what "doesn't
> work" mean here and for which case. FWIW, this feature has nothing with
> the real data, I don't think inserting any data is helpful unless I
> missed anything.

Sorry for not explaining it very well.
"make distinct as no-op."
my understanding: it means: if fewer rows meet the criteria "columnX <
 const_a;" , after analyze the table, it should use index only scan
for the queryA?
--queryA:
select distinct columnX from the_table where columnX <  const_a;

There are several ways for columnX to be unique: primark key, unique
key, unique key nulls distinct, unique key nulls not distinct, unique
key and not null.

After applying your patch, only the primary key case will make the
queryA explain output using the index-only scan.



Re: UniqueKey v2

From
zhihuifan1213@163.com
Date:
jian he <jian.universality@gmail.com> writes:

> On Fri, Oct 20, 2023 at 4:33 PM <zhihuifan1213@163.com> wrote:
>>
>>
>> > i did some simple tests using text data type.
>> >
>> > it works with the primary key, not with unique indexes.
>> > it does not work when the column is unique, not null.
>> >
>> > The following is my test.
>>
>> Can you simplify your test case please? I can't undertand what "doesn't
>> work" mean here and for which case. FWIW, this feature has nothing with
>> the real data, I don't think inserting any data is helpful unless I
>> missed anything.
>
> Sorry for not explaining it very well.
> "make distinct as no-op."
> my understanding: it means: if fewer rows meet the criteria "columnX <
>  const_a;" , after analyze the table, it should use index only scan

No, "mark distinct as no-op" means the distinct node can be discarded
automatically since it is not needed any more. The simplest case would
be "select distinct pk from t", where it should be same as "select pk
from t".  You can check the testcase for the more cases.

--
Best Regards
Andy Fan




Re: UniqueKey v2

From
zhihuifan1213@163.com
Date:
zhihuifan1213@163.com writes:

Hi,

Here is the v3, the mainly changes is it maintains the UniqueKey on
joinrel level, which probabaly is the most important part of this
feature. It shows how the UnqiueKey on joinrel is generated and how it
is discarded due to non-interesting-uniquekey and also show much details
about the single-row case.

I will always maintain README.uniquekey under src/backend/optimizer/path/
to include the latest state of this feature to save the time for
reviewer from going through from the begining. I also use the word "BAD
CASE" in uniquekey.sql to demo which sistuation is not handled well so
far, that probably needs more attention at the first review. 



-- 
Best Regards
Andy Fan

Attachment

Re: UniqueKey v2

From
Antonin Houska
Date:
zhihuifan1213@163.com wrote:

> Here is the v3, ...

I'm trying to enhance the join removal functionality (will post my patch in a
separate thread soon) and I consider your patch very helpful in this
area.

Following is my review. Attached are also some fixes and one enhancement:
propagation of the unique keys (UK) from a subquery to the parent query
(0004). (Note that 0001 is just your patch rebased).


* I think that, before EC is considered suitable for an UK, its ec_opfamilies
  field needs to be checked. I try to do that in
  find_ec_position_matching_expr(), see 0004.


* Set-returning functions (SRFs) can make a "distinct path" necessary even if
  the join output is unique.


* RelOptInfo.notnullattrs

  My understanding is that this field contains the set attributes whose
  uniqueness is guaranteed by the unique key. They are acceptable because they
  are either 1) not allowed to be NULL due to NOT NULL constraint or 2) NULL
  value makes the containing row filtered out, so the row cannot break
  uniqueness of the output. Am I right?

  If so, I suggest to change the field name to something less generic, maybe
  'uniquekey_attrs' or 'uniquekey_candidate_attrs', and adding a comment that
  more checks are needed before particular attribute can actually be used in
  UniqueKey.


* add_uniquekey_for_uniqueindex()

  I'd appreciate an explanation why the "single-row UK" is created. I think
  the reason for unique_exprs==NIL is that a restriction clause VAR=CONST
  exists for each column of the unique index. Whether I'm right or not, a
  comment should state clearly what the reason is.


* uniquekey_useful_for_merging()

  How does uniqueness relate to merge join? In README.uniquekey you seem to
  point out that a single row is always sorted, but I don't think this
  function is related to that fact. (Instead, I'd expect that pathkeys are
  added to all paths for a single-row relation, but I'm not sure you do that
  in the current version of the patch.)


* is_uniquekey_useful_afterjoin()

  Now that my patch (0004) allows propagation of the unique keys from a
  subquery to the upper query, I was wondering if the UniqueKey structure
  needs the 'use_for_distinct field' I mean we should now propagate the unique
  keys to the parent query whether the subquery has DISTINCT clause or not. I
  noticed that the field is checked by is_uniquekey_useful_afterjoin(), so I
  changed the function to always returned true. However nothing changed in the
  output of regression tests (installcheck). Do you insist that the
  'use_for_distinct' field is needed?


* uniquekey_contains_multinulls()

  ** Instead of calling the function when trying to use the UK, how about
     checking the ECs when considering creation of the UK? If the tests fail,
     just don't create the UK.

  ** What does the 'multi' word in the function name mean?


* relation_is_distinct_for()

  The function name is too similar to rel_is_distinct_for(). I think the name
  should indicate that you are checking the relation against a set of
  pathkeys. Maybe rel_is_distinct_for_pathkeys() (and remove 'distinct' from
  the argument name)? At the same time, it might be good to rename
  rel_is_distinct_for() to rel_is_distinct_for_clauses().


* uniquekey_contains_in()

  Shouldn't this be uniquekey_contained_in()? And likewise, shouldn't the
  comment be " ... if UniqueKey is contained in the list of EquivalenceClass"
  ?

  (In general, even though I'm not English native speaker, I think I see quite
  a few grammar issues, which often make reading of the comments/documentation
  a bit difficult.)


* Combining the UKs

  IMO this is the most problematic part of the patch. You call
  populate_joinrel_uniquekeys() for the same join multiple times, each time
  with a different 'restrictlist', and you try to do two things at the same
  time: 1) combine the UKs of the input relations into the UKs of the join
  relation, 2) check if the join relation can be marked single-row.

  I think that both 1) and 2) should be independent from join order, and thus
  both computations should only take place once for given set of input
  relations. And I think they should be done separately:

  1) Compute the join UKs

  As you admit in a comment in populate_joinrel_uniquekeys(), neither join
  method nor clauses should matter. So I think you only need to pick the
  "component UKs" (i.e. UKs of the input relations) which are usable above
  that join (i.e. neither the join itself nor any join below sets any column
  of the UK to NULL) and combine them.

  Of course one problem is that the number of combinations can grow
  exponentially as new relations are joined. I'm not sure it's necessary to
  combine the UKs (and to discard some of them) immediately. Instead, maybe we
  can keep lists of UKs only for base relations, and postpone picking the
  suitable UKs and combining them until we actually need to check the relation
  uniqueness.

  2) Check if the join relation is single-row

  I in order to get rid of the dependency on 'restrictlist', I think you can
  use ECs. Consider a query from your regression tests:

CREATE TABLE uk_t (id int primary key, a int not null, b int not null, c int, d int, e int);

SELECT distinct t1.d FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id and t1.id = 1;

  The idea here seems to be that no more than one row of t1 matches the query
  clauses. Therefore, if t2(id) is unique, the clause t1.e=t2.id ensures that
  no more than one row of t2 matches the query (because t1 cannot provide the
  clause with more than one input value of 'e'). And therefore, the join also
  produces at most one row.

  My theory is that relation is single-row if it has an UK such that each of
  its ECs meets at least one of the following conditions:

  a) contains a constant

  b) contains a column of a relation which has already been proven single-row.

  b) is referenced by an UK of a relation which has already been proven
     single-row.

  I think that in the example above, an EC {t1.e, t2.id} should exist. So when
  checking whether 't2' is single-row, the condition b) cam be ised: the UK of
  't2' should reference the EC {t1.e, t2.id}, which in turn contains the
  column t1.e. And 't1' is unique because its EC meets the condition a). (Of
  course you need to check em_jdomain before you use particular EM.)


Are you going to submit the patch to the first CF of PG 18?

Please let me know if I can contribute to the effort by reviewing or writing
some code.

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


From 9fe85dae62ae580f377771935ee399e7f46dc99b Mon Sep 17 00:00:00 2001
From: Antonin Houska <ah@cybertec.at>
Date: Thu, 18 Apr 2024 14:43:02 +0200
Subject: [PATCH 1/5] Unique keys rebased.

The original patch:
https://www.postgresql.org/message-id/871qczm9oc.fsf%40163.com
---
 src/backend/nodes/list.c                    |  17 +
 src/backend/optimizer/path/Makefile         |   3 +-
 src/backend/optimizer/path/README.uniquekey | 220 +++++++
 src/backend/optimizer/path/allpaths.c       |   2 +
 src/backend/optimizer/path/equivclass.c     |  48 ++
 src/backend/optimizer/path/joinrels.c       |   2 +
 src/backend/optimizer/path/uniquekey.c      | 654 ++++++++++++++++++++
 src/backend/optimizer/plan/initsplan.c      |  10 +-
 src/backend/optimizer/plan/planner.c        |  33 +
 src/backend/optimizer/util/plancat.c        |  10 +
 src/backend/optimizer/util/relnode.c        |   2 +
 src/include/nodes/pathnodes.h               |  19 +
 src/include/nodes/pg_list.h                 |   2 +
 src/include/optimizer/paths.h               |  13 +
 src/test/regress/expected/join.out          |  11 +-
 src/test/regress/expected/uniquekey.out     | 268 ++++++++
 src/test/regress/parallel_schedule          |   2 +-
 src/test/regress/sql/uniquekey.sql          | 104 ++++
 18 files changed, 1410 insertions(+), 10 deletions(-)
 create mode 100644 src/backend/optimizer/path/README.uniquekey
 create mode 100644 src/backend/optimizer/path/uniquekey.c
 create mode 100644 src/test/regress/expected/uniquekey.out
 create mode 100644 src/test/regress/sql/uniquekey.sql

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index e2615ab105..20eb1267eb 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -695,6 +695,23 @@ list_member_ptr(const List *list, const void *datum)
     return false;
 }
 
+/*
+ * Return index of the datum in list if found. otherwise return -1.
+ */
+int
+list_member_ptr_pos(const List *list, const void *datum)
+{
+    ListCell   *lc;
+
+    foreach(lc, list)
+    {
+        if (lfirst(lc) == datum)
+            return foreach_current_index(lc);
+    }
+
+    return -1;
+}
+
 /*
  * Return true iff the integer 'datum' is a member of the list.
  */
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f..63cc1505d9 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -21,6 +21,7 @@ OBJS = \
     joinpath.o \
     joinrels.o \
     pathkeys.o \
-    tidpath.o
+    tidpath.o \
+    uniquekey.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/path/README.uniquekey b/src/backend/optimizer/path/README.uniquekey
new file mode 100644
index 0000000000..be13b113b9
--- /dev/null
+++ b/src/backend/optimizer/path/README.uniquekey
@@ -0,0 +1,220 @@
+Here is a design document and a part of implementation.
+
+What is UniqueKey?
+-----------------
+
+UniqueKey represents a uniqueness information for a RelOptInfo. for
+example:
+
+SELECT id FROM t;
+
+where the ID is the UniqueKey for the RelOptInfo (t).  In the real world,
+it has the following attributes:
+
+1). It should be EquivalenceClass based. for example:
+
+SELECT a FROM t WHERE a = id;
+
+In this case, the UniqueKey should be 1 EC with two members
+- EC(EM(a), EM(id)).
+
+
+2). Each UniqueKey may be made up with 1+ EquivalenceClass. for example:
+
+CREATE TABLE t(a int not null,  b int not null);
+CREATE UNIQUE INDEX on t(a, b);
+SELECT * FROM t;
+
+Where the UniqueKey for RelOptInfo (t) will be 2 ECs with each one has 1
+member.
+
+- EC(em=a), EC(em=b)
+
+3). Each RelOptInfo may have 1+ UniqueKeys.
+
+CREATE TABLE t(a int not null,  b int not null, c int not null);
+CREATE UNIQUE INDEX on t(a, b);
+CREATE UNIQUE INDEX on t(c);
+
+SELECT * FROM t;
+
+Where the UniqueKey for RelOptInfo (t) will be
+- [EC(em=a), EC(em=b)].
+- [EC(em=c)]
+
+4). A special case is about the one-row case. It works like:
+SELECT * FROM t WHERE id = 1;
+Here every single expression in the RelOptInfo (t) is unique since only
+one row here.
+
+Where can we use it?
+--------------------
+1. mark the distinct as no-op.  SELECT DISTINCT uniquekey FROM v; This
+  optimization has been required several times in our threads.
+
+2. Figure out more pathkey within the onerow case, then some planning
+  time can be reduced to be big extend. This user case is not absurd,
+  a real user case like this:
+
+  CREATE TABLE small_t (id int primary key, b int, c int .. u int);
+  CREATE INDEX ON small_t(b);
+  CREATE INDEX ON small_t(c);
+  ..
+
+  SELECT * FROM small_t s
+    JOIN t1 on t1.sb = s.b
+    JOIN T2 on t2.sc = s.c
+    ..
+    JOIN t20 on t20.su = s.u
+  WHERE s.id = 1;
+
+  Without the above optimization, we don't know s.b /s.c is ordered
+  already, so it might keep more different paths for small_t because of
+  they have different interesting pathkey, and use more planning time
+  for sorting to support merge join.
+
+  With the above optimization, the planning time should be reduced since
+  the seq scan can produce a ordered result for every expression.
+
+3. Figure out more interesting pathkey after join with normal UniqueKey.
+
+  CREATE TABLE t(id int primary key, b int, c int);
+  CREATE INDEX on t(c);
+  ANALYZE t;
+
+  explain (costs off)
+  select t1.id, t2.c from t t1
+    join t1 t2 on t1.id = t2.b
+    and t2.c > 3
+  order by t1.id, t2.c;
+
+            QUERY PLAN
+  --------------------------------------------------
+  Sort Key: t1.id, t2.c   <---  this sort can be avoided actually.
+  ->  Nested Loop
+    Join Filter: (t1.id = t2.b)
+    ->  Index Only Scan using t_pkey on t t1
+    ->  Index Scan using t1_c_idx on t1 t2
+          Index Cond: (c > 3)
+
+  *Without knowing the t1.id is unique*,  which means there are some
+  duplicated data in t1.id, the duplication data in t1 will break the
+  order of (t1.id, t2.c), but if we know the t1.id is unique, the sort
+  will be not needed.  I'm pretty happy with this finding.
+
+4. Optimize some group by case, like
+
+  SELECT id, sum(b) FROM t GROUP BY id
+  is same with
+  SELECT id, b from t;
+
+  I'm not sure how often it is in the real life, I'm not so excited with
+  this for now.
+
+
+How to present ECs in UniqueKey?
+--------------------------------
+
+I choose "Bitmapset *eclass_indexes;" finally, which is because
+Bitmapset is memory compact and good at bms_union,  bms_is_subset
+stuffs. The value in the bitmap is the positions in root->eq_classes. It
+is also be able to present the UniqueKey which is made up from multi
+relations or upper relation.
+
+How to present single row in UniqueKey
+-------------------------------------
+
+I just use a 'Index relid', an non-zero value means the
+RelOptInfo[relid] is single row.  For the case like
+
+SELECT * FROM t WHERE id = 1;
+The UniqueKey is:
+- UniqueKey(eclass_indexes=NULL, relid=1)
+
+during a join, any unique keys join with single row, it's uniqueness can
+be kept.
+
+SELECT t1.uk, t2.a FROM t WHERE t2.id = 1 and any-qual(t1, t2);
+- UniqueKey (t1.uk)
+
+more specially, join two single row like:
+
+SELECT * FROM t1 join t2 on true where t1.id = 1 and t2.id = 2;
+
+the UniqueKey for the JoinRel will be:
+- UniqueKey(eclass_indexes=NULL, relid=1)
+- UniqueKey(eclass_indexes=NULL, relid=2)
+
+However, the current single row presentation can't works well with Upper
+relation, which I think it would be acceptable. See the following case:
+
+SELECT count(*) FROM t1 JOIN t2 on true;
+
+
+How to maintain the uniquekey?
+-------------------------------
+the uniquekey is maintained from baserel to join rel then to upper
+relation. In the base rel, it comes from unique index. From the join
+relation, it is maintained with two rules:
+
+- the uniquekey in one side is still unique if it can't be duplicated
+  after the join. for example:
+
+  SELECT t1.pk FROM t1 JOIN t2 ON t1.a = t2.pk;
+  UniqueKey on t1:  t1.pk
+  UniqueKey on t1 Join t2:  t1.pk
+
+- The combined unique key from both sides are unique all the times.
+  SELECT t1.pk , t2.pk FROM t1 join t2 on true;
+  UniqueKey on t1 join t2:  (t1.pk, t2.pk)
+
+Some other operations like DISTINCT, GROUP BY can produce UniqueKey as well.
+
+NULL values
+-----------
+notnullattrs are added into RelOptInfo, which present if these attributes
+may not be NULL after the baserestrictinfo is executed. not-null-attributes
+may be generated by not-null constraint in catalog or baserestrictinfo
+(only) filter. However it is possible become NULLs because of outer
+join, then Var.varnullingrels is used in this case. see
+'var_is_nullable' function call.
+
+To simplify the UniqueKey module, it doesn't care about the null values
+during the maintaining, which means it may contains multi NULL values
+all the time by design. However whenever a user case care about that,
+the user case can get the answer with the above logic, that is what
+'mark-distinct-as-noop' does.
+
+How to reduce the overhead
+----------------------------------
+UniqueKey employs the similar strategy like PathKey, it only maintain
+the interesting PathKey. Currently the interesting UniqueKey includes:
+1). It is subset of distinct_pathkeys.
+2). It is used in mergeable join clauses for unique key deduction (for
+the join rel case, rule 1). In this case, it can be discarded quickly if
+the join has been done.
+
+To avoid to check if an uniquekey is subset of distinct clause again and
+again, I cached the result into UnqiueKey struct during the UniqueKey
+creation.
+
+Since our first goal is just used for marking distinct as no-op, so if
+there is no distinct clause at all, unique key will be not maintained at
+the beginning. so we can have some codes like:
+
+if (root->distinct_pathkeys == NULL)
+return;
+
+This fast path is NOT added for now for better code coverage.
+
+What I have now:
+----------------
+
+The current patch just maintain the UniqueKey at the baserel/joinrel level
+and used it for mark-distinct-as-noop purpose. including the basic idea of
+
+- How the UniqueKey is defined.
+- How to find out the interesting pathkey in the baserel/joinrel level.
+- How to figure out the unique key contains NULL values.
+
+Also the test cases are prepared, see uniquekey.sql.
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index cc51ae1757..ced0fce415 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -455,6 +455,8 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel,
         }
     }
 
+    populate_baserel_uniquekeys(root, rel);
+
     /*
      * We insist that all non-dummy rels have a nonzero rowcount estimate.
      */
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 1d6bedb399..892cd0000c 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -755,6 +755,54 @@ get_eclass_for_sort_expr(PlannerInfo *root,
     return newec;
 }
 
+/*
+ * find_ec_position_matching_expr
+ *        Locate the position of EquivalenceClass whose members matching
+ *        the given expr, if any; return -1 if no match.
+ */
+int
+find_ec_position_matching_expr(PlannerInfo *root,
+                               Expr *expr,
+                               RelOptInfo *baserel)
+{
+    int            i = -1;
+
+    while ((i = bms_next_member(baserel->eclass_indexes, i)) >= 0)
+    {
+        EquivalenceClass *ec = list_nth(root->eq_classes, i);
+
+        if (find_ec_member_matching_expr(ec, expr, baserel->relids))
+            return i;
+    }
+    return -1;
+}
+
+/*
+ * build_ec_positions_for_exprs
+ *
+ *        Given a list of exprs, find the related EC positions for each of
+ *        them. if any exprs has no EC related, return NULL;
+ */
+Bitmapset *
+build_ec_positions_for_exprs(PlannerInfo *root, List *exprs, RelOptInfo *rel)
+{
+    ListCell   *lc;
+    Bitmapset  *res = NULL;
+
+    foreach(lc, exprs)
+    {
+        int            pos = find_ec_position_matching_expr(root, lfirst(lc), rel);
+
+        if (pos < 0)
+        {
+            bms_free(res);
+            return NULL;
+        }
+        res = bms_add_member(res, pos);
+    }
+    return res;
+}
+
 /*
  * find_ec_member_matching_expr
  *        Locate an EquivalenceClass member matching the given expr, if any;
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index f3a9412d18..b5c2b7d084 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -761,6 +761,8 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
                              sjinfo, pushed_down_joins,
                              &restrictlist);
 
+    populate_joinrel_uniquekeys(root, joinrel, rel1, rel2, restrictlist, sjinfo->jointype);
+
     /*
      * If we've already proven this join is empty, we needn't consider any
      * more paths for it.
diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c
new file mode 100644
index 0000000000..ecc7c6d802
--- /dev/null
+++ b/src/backend/optimizer/path/uniquekey.c
@@ -0,0 +1,654 @@
+/*-------------------------------------------------------------------------
+ *
+ * uniquekey.c
+ *      Utilities for maintaining uniquekey.
+ *
+ *
+ * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *      src/backend/optimizer/path/uniquekey.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/sysattr.h"
+#include "nodes/nodeFuncs.h"
+#include "nodes/pathnodes.h"
+#include "optimizer/optimizer.h"
+#include "optimizer/paths.h"
+
+
+/* Functions to populate UniqueKey */
+static bool add_uniquekey_for_uniqueindex(PlannerInfo *root,
+                                          IndexOptInfo *unique_index,
+                                          List *truncatable_exprs,
+                                          List *expr_opfamilies);
+static bool unique_ecs_useful_for_distinct(PlannerInfo *root, Bitmapset *ec_indexes);
+
+/* Helper functions to create UniqueKey. */
+static UniqueKey * make_uniquekey(Bitmapset *eclass_indexes,
+                                  bool useful_for_distinct);
+static void mark_rel_singlerow(RelOptInfo *rel, int relid);
+
+static UniqueKey * rel_singlerow_uniquekey(RelOptInfo *rel);
+static bool uniquekey_contains_multinulls(PlannerInfo *root, RelOptInfo *rel, UniqueKey * ukey);
+
+/* Debug only */
+static void print_uniquekey(PlannerInfo *root, RelOptInfo *rel);
+
+static bool uniquekey_contains_in(PlannerInfo *root, UniqueKey * ukey, Bitmapset *ecs, Relids relids);
+static bool is_uniquekey_useful_afterjoin(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *joinrel);
+
+/*
+ * populate_baserel_uniquekeys
+ *
+ *        UniqueKey on baserel comes from unique indexes. Any expression
+ * which equals with Const can be stripped and the left expressions are
+ * still unique.
+ */
+void
+populate_baserel_uniquekeys(PlannerInfo *root, RelOptInfo *rel)
+{
+    ListCell   *lc;
+    List       *truncatable_exprs = NIL,
+               *expr_opfamilies = NIL;
+
+    /*
+     * Currently we only use UniqueKey for mark-distinct-as-noop case, so if
+     * there is no-distinct-clause at all, we can ignore the maintenance at
+     * the first place. however for code coverage at the development stage, we
+     * bypass this fastpath on purpose.
+     *
+     * XXX: even we want this fastpath, we still need to distinguish even the
+     * current subquery has no DISTINCT, but the upper query may have.
+     */
+
+    /*
+     * if (root->distinct_pathkeys == NIL) return;
+     */
+    foreach(lc, rel->baserestrictinfo)
+    {
+        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+        if (rinfo->mergeopfamilies == NIL)
+            continue;
+
+        if (!IsA(rinfo->clause, OpExpr))
+            continue;
+
+        if (bms_is_empty(rinfo->left_relids))
+            truncatable_exprs = lappend(truncatable_exprs, get_rightop(rinfo->clause));
+        else if (bms_is_empty(rinfo->right_relids))
+            truncatable_exprs = lappend(truncatable_exprs, get_leftop(rinfo->clause));
+        else
+            continue;
+
+        expr_opfamilies = lappend(expr_opfamilies, rinfo->mergeopfamilies);
+    }
+
+    foreach(lc, rel->indexlist)
+    {
+        IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+        if (!index->unique || !index->immediate ||
+            (index->indpred != NIL && !index->predOK))
+            continue;
+
+        if (add_uniquekey_for_uniqueindex(root, index,
+                                          truncatable_exprs,
+                                          expr_opfamilies))
+            /* Find a singlerow case, no need to go through other indexes. */
+            return;
+    }
+
+    print_uniquekey(root, rel);
+}
+
+
+/*
+ * add_uniquekey_for_uniqueindex
+ *
+ *         populate a UniqueKey if it is interesting, return true iff the
+ * UniqueKey is an SingleRow. Only the interesting UniqueKeys are kept.
+ */
+static bool
+add_uniquekey_for_uniqueindex(PlannerInfo *root, IndexOptInfo *unique_index,
+                              List *truncatable_exprs, List *expr_opfamilies)
+{
+    List       *unique_exprs = NIL;
+    Bitmapset  *unique_ecs = NULL;
+    ListCell   *indexpr_item;
+    RelOptInfo *rel = unique_index->rel;
+    bool        used_for_distinct;
+    int            c;
+
+    indexpr_item = list_head(unique_index->indexprs);
+
+    for (c = 0; c < unique_index->nkeycolumns; c++)
+    {
+        int            attr = unique_index->indexkeys[c];
+        Expr       *expr;        /* The candidate for UniqueKey expression. */
+        bool        matched_const = false;
+        ListCell   *lc1,
+                   *lc2;
+
+        if (attr > 0)
+        {
+            expr = list_nth_node(TargetEntry, unique_index->indextlist, c)->expr;
+        }
+        else if (attr == 0)
+        {
+            /* Expression index */
+            expr = lfirst(indexpr_item);
+            indexpr_item = lnext(unique_index->indexprs, indexpr_item);
+        }
+        else                    /* attr < 0 */
+        {
+            /* Index on OID is possible, not handle it for now. */
+            return false;
+        }
+
+        /* Ignore the expr which are equals to const. */
+        forboth(lc1, truncatable_exprs, lc2, expr_opfamilies)
+        {
+            if (list_member_oid((List *) lfirst(lc2), unique_index->opfamily[c]) &&
+                match_index_to_operand((Node *) lfirst(lc1), c, unique_index))
+            {
+                matched_const = true;
+                break;
+            }
+        }
+
+        if (matched_const)
+            continue;
+
+        unique_exprs = lappend(unique_exprs, expr);
+    }
+
+    if (unique_exprs == NIL)
+    {
+        /* single row is always interesting. */
+        mark_rel_singlerow(rel, rel->relid);
+        return true;
+    }
+
+    /*
+     * if no EquivalenceClass is found for any exprs in unique exprs, we are
+     * sure the whole exprs are not in the DISTINCT clause or mergeable join
+     * clauses. so it is not interesting.
+     */
+    unique_ecs = build_ec_positions_for_exprs(root, unique_exprs, rel);
+    if (unique_ecs == NULL)
+        return false;
+
+    used_for_distinct = unique_ecs_useful_for_distinct(root, unique_ecs);
+
+
+    rel->uniquekeys = lappend(rel->uniquekeys,
+                              make_uniquekey(unique_ecs,
+                                             used_for_distinct));
+    return false;
+}
+
+/*
+ *    make_uniquekey
+ *        Based on UnqiueKey rules, it is impossible for a UnqiueKey
+ * which have eclass_indexes and relid both set. This function just
+ * handle eclass_indexes case.
+ */
+static UniqueKey *
+make_uniquekey(Bitmapset *eclass_indexes, bool useful_for_distinct)
+{
+    UniqueKey  *ukey = makeNode(UniqueKey);
+
+    ukey->eclass_indexes = eclass_indexes;
+    ukey->relid = 0;
+    ukey->use_for_distinct = useful_for_distinct;
+    return ukey;
+}
+
+/*
+ * mark_rel_singlerow
+ *    mark a relation as singlerow.
+ */
+static void
+mark_rel_singlerow(RelOptInfo *rel, int relid)
+{
+    UniqueKey  *ukey = makeNode(UniqueKey);
+
+    ukey->relid = relid;
+    rel->uniquekeys = list_make1(ukey);
+}
+
+static inline bool
+uniquekey_is_singlerow(UniqueKey * ukey)
+{
+    return ukey->relid != 0;
+}
+
+/*
+ *
+ *    Return the UniqueKey if rel is a singlerow Relation. othwise
+ * return NULL.
+ */
+static UniqueKey *
+rel_singlerow_uniquekey(RelOptInfo *rel)
+{
+    if (rel->uniquekeys != NIL)
+    {
+        UniqueKey  *ukey = linitial_node(UniqueKey, rel->uniquekeys);
+
+        if (ukey->relid)
+            return ukey;
+    }
+    return NULL;
+}
+
+/*
+ * print_uniquekey
+ *    Used for easier reivew, should be removed before commit.
+ */
+static void
+print_uniquekey(PlannerInfo *root, RelOptInfo *rel)
+{
+    if (!enable_geqo)
+    {
+        ListCell   *lc;
+
+        elog(INFO, "Rel = %s", bmsToString(rel->relids));
+        foreach(lc, rel->uniquekeys)
+        {
+            UniqueKey  *ukey = lfirst_node(UniqueKey, lc);
+
+            elog(INFO, "UNIQUEKEY{indexes=%s, singlerow_rels=%d, use_for_distinct=%d}",
+                 bmsToString(ukey->eclass_indexes),
+                 ukey->relid,
+                 ukey->use_for_distinct);
+        }
+    }
+}
+
+/*
+ *    is it possible that the var contains multi NULL values in the given
+ * RelOptInfo rel?
+ */
+static bool
+var_is_nullable(PlannerInfo *root, Var *var, RelOptInfo *rel)
+{
+    RelOptInfo *base_rel;
+
+    /* check if the outer join can add the NULL values.  */
+    if (bms_overlap(var->varnullingrels, rel->relids))
+        return true;
+
+    /* check if the user data has the NULL values. */
+    base_rel = root->simple_rel_array[var->varno];
+    return !bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber, base_rel->notnullattrs);
+}
+
+
+/*
+ * uniquekey_contains_multinulls
+ *
+ *    Check if the uniquekey contains nulls values.
+ */
+static bool
+uniquekey_contains_multinulls(PlannerInfo *root, RelOptInfo *rel, UniqueKey * ukey)
+{
+    int            i = -1;
+
+    while ((i = bms_next_member(ukey->eclass_indexes, i)) >= 0)
+    {
+        EquivalenceClass *ec = list_nth_node(EquivalenceClass, root->eq_classes, i);
+        ListCell   *lc;
+
+        foreach(lc, ec->ec_members)
+        {
+            EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+            Var           *var;
+
+            var = (Var *) em->em_expr;
+
+            if (!IsA(var, Var))
+                continue;
+
+            if (var_is_nullable(root, var, rel))
+                return true;
+            else
+
+                /*
+                 * If any one of member in the EC is not nullable, we all the
+                 * members are not nullable since they are equal with each
+                 * other.
+                 */
+                break;
+        }
+    }
+
+    return false;
+}
+
+
+/*
+ * relation_is_distinct_for
+ *
+ * Check if the rel is distinct for distinct_pathkey.
+ */
+bool
+relation_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *distinct_pathkey)
+{
+    ListCell   *lc;
+    UniqueKey  *singlerow_ukey = rel_singlerow_uniquekey(rel);
+    Bitmapset  *pathkey_bm = NULL;
+
+    if (singlerow_ukey)
+    {
+        return !uniquekey_contains_multinulls(root, rel, singlerow_ukey);
+    }
+
+    foreach(lc, distinct_pathkey)
+    {
+        PathKey    *pathkey = lfirst_node(PathKey, lc);
+        int            pos = list_member_ptr_pos(root->eq_classes, pathkey->pk_eclass);
+
+        if (pos == -1)
+            return false;
+
+        pathkey_bm = bms_add_member(pathkey_bm, pos);
+    }
+
+    foreach(lc, rel->uniquekeys)
+    {
+        UniqueKey  *ukey = lfirst_node(UniqueKey, lc);
+
+        if (bms_is_subset(ukey->eclass_indexes, pathkey_bm) &&
+            !uniquekey_contains_multinulls(root, rel, ukey))
+            return true;
+    }
+
+    return false;
+}
+
+/*
+ * unique_ecs_useful_for_distinct
+ *
+ *    Return true if all the EquivalenceClass for ecs exists in root->distinct_pathkey.
+ */
+static bool
+unique_ecs_useful_for_distinct(PlannerInfo *root, Bitmapset *ec_indexes)
+{
+    int            i = -1;
+
+    while ((i = bms_next_member(ec_indexes, i)) >= 0)
+    {
+        EquivalenceClass *ec = list_nth(root->eq_classes, i);
+        ListCell   *p;
+        bool        found = false;
+
+        foreach(p, root->distinct_pathkeys)
+        {
+            PathKey    *pathkey = lfirst_node(PathKey, p);
+
+            if (ec == pathkey->pk_eclass)
+            {
+                found = true;
+                break;
+            }
+        }
+        if (!found)
+            return false;
+    }
+    return true;
+}
+
+/*
+ * populate_joinrel_uniquekey_for_rel
+ *
+ *    Check if the pattern of rel.any_column = other_rel.unique_key_column
+ * exists, if so, the uniquekey in rel is still valid after join and it is
+ * added into joinrel and return true. otherwise return false.
+ */
+static bool
+populate_joinrel_uniquekey_for_rel(PlannerInfo *root, RelOptInfo *joinrel,
+                                   RelOptInfo *rel, RelOptInfo *other_rel,
+                                   List *restrictlist)
+{
+    bool        rel_keep_unique = false;
+    Bitmapset  *other_ecs = NULL;
+    Relids        other_relids = NULL;
+    ListCell   *lc;
+
+    if (rel_singlerow_uniquekey(other_rel))
+    {
+        /*
+         * any uniquekeys stuff join with single-row, its uniqueness is still
+         * kept.
+         */
+        goto done;
+    }
+
+    /* find out the ECs which the rel.any_columns equals to. */
+    foreach(lc, restrictlist)
+    {
+        RestrictInfo *r = lfirst_node(RestrictInfo, lc);
+
+        if (r->mergeopfamilies == NIL)
+            continue;
+
+        /* Build the Bitmapset for easy comparing. */
+        if (bms_equal(r->left_relids, rel->relids) && r->right_ec != NULL)
+        {
+            other_ecs = bms_add_member(other_ecs, list_member_ptr_pos(root->eq_classes, r->right_ec));
+            other_relids = bms_add_members(other_relids, r->right_relids);
+        }
+        else if (bms_equal(r->right_relids, rel->relids) && r->left_ec != NULL)
+        {
+            other_ecs = bms_add_member(other_ecs, list_member_ptr_pos(root->eq_classes, r->left_ec));
+            other_relids = bms_add_members(other_relids, r->left_relids);
+        }
+    }
+
+    /* Check if these ECs include a uniquekey of other_rel */
+    foreach(lc, other_rel->uniquekeys)
+    {
+        UniqueKey  *ukey = lfirst_node(UniqueKey, lc);
+
+        if (uniquekey_contains_in(root, ukey, other_ecs, other_relids))
+        {
+            rel_keep_unique = true;
+            break;
+        }
+    }
+
+    if (!rel_keep_unique)
+        return false;
+
+done:
+
+    /*
+     * Now copy the uniquekey in rel to joinrel, but first we need to know if
+     * it is useful.
+     */
+    foreach(lc, rel->uniquekeys)
+    {
+        UniqueKey  *ukey = lfirst_node(UniqueKey, lc);
+
+        if (is_uniquekey_useful_afterjoin(root, ukey, joinrel))
+        {
+            if (uniquekey_is_singlerow(ukey))
+            {
+                /*
+                 * XXX (?): a). NULL values. b). other relids rather than
+                 * ukey->relid.
+                 */
+                mark_rel_singlerow(joinrel, ukey->relid);
+                break;
+            }
+            joinrel->uniquekeys = lappend(joinrel->uniquekeys, ukey);
+        }
+    }
+
+    return true;
+}
+
+/*
+ * populate_joinrel_uniquekeys
+ */
+void
+populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel,
+                            RelOptInfo *outerrel, RelOptInfo *innerrel,
+                            List *restrictlist, JoinType jointype)
+{
+    bool        outeruk_still_valid = false,
+                inneruk_still_valid = false;
+    ListCell   *lc,
+               *lc2;
+
+    if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+    {
+        foreach(lc, outerrel->uniquekeys)
+        {
+            /*
+             * the uniquekey on the outer side is not changed after semi/anti
+             * join.
+             */
+            joinrel->uniquekeys = lappend(joinrel->uniquekeys, lfirst(lc));
+        }
+        return;
+    }
+
+    if (outerrel->uniquekeys == NIL || innerrel->uniquekeys == NIL)
+        return;
+
+    outeruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, outerrel,
+                                                             innerrel, restrictlist);
+    inneruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, innerrel,
+                                                             outerrel, restrictlist);
+
+    if (outeruk_still_valid || inneruk_still_valid)
+
+        /*
+         * the uniquekey on outers or inners have been added into joinrel so
+         * the combined uniuqekey from both sides is not needed.
+         */
+        return;
+
+    /*
+     * The combined UniqueKey is still unique no matter the join method or
+     * join clauses. So let build the combined ones.
+     */
+    foreach(lc, outerrel->uniquekeys)
+    {
+        UniqueKey  *outer_ukey = lfirst(lc);
+
+        if (!is_uniquekey_useful_afterjoin(root, outer_ukey, joinrel))
+            /* discard the uniquekey which is not interesting. */
+            continue;
+
+        /* singlerow will make the inneruk_still_valid true */
+        Assert(!uniquekey_is_singlerow(outer_ukey));
+
+        foreach(lc2, innerrel->uniquekeys)
+        {
+            UniqueKey  *inner_ukey = lfirst(lc2);
+
+            if (!is_uniquekey_useful_afterjoin(root, inner_ukey, joinrel))
+                continue;
+
+            /* singlerow will make the outeruk_still_valid true */
+            Assert(!uniquekey_is_singlerow(inner_ukey));
+
+            joinrel->uniquekeys = lappend(joinrel->uniquekeys,
+                                          make_uniquekey(
+                                                         bms_union(outer_ukey->eclass_indexes,
inner_ukey->eclass_indexes),
+                                                         outer_ukey->use_for_distinct ||
inner_ukey->use_for_distinct));
+        }
+    }
+}
+
+/*
+ * uniquekey_contains_in
+ *    Return if UniqueKey contains in the list of EquivalenceClass
+ * or the UniqueKey's SingleRow contains in relids.
+ */
+static bool
+uniquekey_contains_in(PlannerInfo *root, UniqueKey * ukey, Bitmapset *ecs, Relids relids)
+{
+
+    if (uniquekey_is_singlerow(ukey))
+    {
+        return bms_is_member(ukey->relid, relids);
+    }
+
+    return bms_is_subset(ukey->eclass_indexes, ecs);
+}
+
+
+/*
+ * uniquekey_useful_for_merging
+ *    Check if the uniquekey is useful for mergejoins above the given relation.
+ *
+ * similar with pathkeys_useful_for_merging.
+ */
+static bool
+uniquekey_useful_for_merging(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *rel)
+{
+
+    int            i = -1;
+
+    while ((i = bms_next_member(ukey->eclass_indexes, i)) >= 0)
+    {
+        EquivalenceClass *ec = list_nth(root->eq_classes, i);
+        ListCell   *j;
+        bool        matched = false;
+
+        if (rel->has_eclass_joins && eclass_useful_for_merging(root, ec, rel))
+        {
+            matched = true;
+        }
+        else
+        {
+            foreach(j, rel->joininfo)
+            {
+                RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
+
+                if (restrictinfo->mergeopfamilies == NIL)
+                    continue;
+                update_mergeclause_eclasses(root, restrictinfo);
+
+                if (ec == restrictinfo->left_ec || ec == restrictinfo->right_ec)
+                {
+                    matched = true;
+                    break;
+                }
+            }
+        }
+
+        if (!matched)
+            return false;
+    }
+
+    return true;
+}
+
+/*
+ * is_uniquekey_useful_afterjoin
+ *
+ *  uniquekey is useful when it contains in distinct_pathkey or in mergable join clauses.
+ */
+static bool
+is_uniquekey_useful_afterjoin(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *joinrel)
+{
+    if (ukey->use_for_distinct)
+        return true;
+
+    /* XXX might needs a better judgement */
+    if (uniquekey_is_singlerow(ukey))
+        return true;
+
+
+    return uniquekey_useful_for_merging(root, ukey, joinrel);
+}
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e2c68fe6f9..a04a6022bc 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2678,7 +2678,15 @@ add_base_clause_to_rel(PlannerInfo *root, Index relid,
     }
 
     /* Add clause to rel's restriction list */
-    rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo);
+    rel->baserestrictinfo = lappend(rel->baserestrictinfo,
+                                    restrictinfo);
+    {
+        List       *not_null_vars = find_nonnullable_vars((Node *) restrictinfo->clause);
+
+        if (not_null_vars != NIL)
+            rel->notnullattrs = bms_union(rel->notnullattrs,
+                                          list_nth(not_null_vars, rel->relid));
+    }
 
     /* Update security level info */
     rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5320da51a0..e40c729e7e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1671,9 +1671,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
                                                 gset_data);
             /* Fix things up if grouping_target contains SRFs */
             if (parse->hasTargetSRFs)
+            {
                 adjust_paths_for_srfs(root, current_rel,
                                       grouping_targets,
                                       grouping_targets_contain_srfs);
+                current_rel->uniquekeys = NIL;
+            }
         }
 
         /*
@@ -1734,6 +1737,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
      * Now we are prepared to build the final-output upperrel.
      */
     final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
+    /* simple_copy_uniquekeys(final_rel, current_rel); */
 
     /*
      * If the input rel is marked consider_parallel and there's nothing that's
@@ -4009,6 +4013,22 @@ create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel,
                                       gd,
                                       extra->targetList);
 
+    if (root->parse->groupingSets)
+    {
+        /* nothing to do */
+    }
+    else if (root->parse->groupClause && root->group_pathkeys != NIL)
+    {
+        /*
+         * populate_uniquekeys_from_pathkeys(root, grouped_rel,
+         * root->group_pathkeys);
+         */
+    }
+    else
+    {
+        /* SingleRow Case */
+    }
+
     /* Build final grouping paths */
     add_paths_to_grouping_rel(root, input_rel, grouped_rel,
                               partially_grouped_rel, agg_costs, gd,
@@ -4632,9 +4652,22 @@ create_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
 {
     RelOptInfo *distinct_rel;
 
+    /*
+     * distinct_pathkeys may be NIL if it distinctClause is not sortable. XXX:
+     * What should we do for the else?
+     */
+    if (root->distinct_pathkeys &&
+        relation_is_distinct_for(root, input_rel, root->distinct_pathkeys))
+        return input_rel;
+
     /* For now, do all work in the (DISTINCT, NULL) upperrel */
     distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
 
+    /*
+     * populate_uniquekeys_from_pathkeys(root, distinct_rel,
+     * root->distinct_pathkeys);
+     */
+
     /*
      * We don't compute anything at this level, so distinct_rel will be
      * parallel-safe if the input rel is parallel-safe.  In particular, if
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 130f838629..438ec75689 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -119,6 +119,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
     Relation    relation;
     bool        hasindex;
     List       *indexinfos = NIL;
+    Index        i;
 
     /*
      * We need not lock the relation since it was already locked, either by
@@ -203,6 +204,15 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
     /* Retrieve the parallel_workers reloption, or -1 if not set. */
     rel->rel_parallel_workers = RelationGetParallelWorkers(relation, -1);
 
+    for (i = 0; i < relation->rd_att->natts; i++)
+    {
+        FormData_pg_attribute attr = relation->rd_att->attrs[i];
+
+        if (attr.attnotnull)
+            rel->notnullattrs = bms_add_member(rel->notnullattrs,
+                                               attr.attnum - FirstLowInvalidHeapAttributeNumber);
+    }
+
     /*
      * Make list of indexes.  Ignore indexes on system catalogs if told to.
      * Don't bother with indexes from traditional inheritance parents.  For
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index e05b21c884..0e3d427fbb 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -286,6 +286,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
     rel->all_partrels = NULL;
     rel->partexprs = NULL;
     rel->nullable_partexprs = NULL;
+    rel->uniquekeys = NIL;
 
     /*
      * Pass assorted information down the inheritance hierarchy.
@@ -768,6 +769,7 @@ build_join_rel(PlannerInfo *root,
     joinrel->all_partrels = NULL;
     joinrel->partexprs = NULL;
     joinrel->nullable_partexprs = NULL;
+    joinrel->uniquekeys = NIL;
 
     /* Compute information relevant to the foreign relations. */
     set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 6c71098f2d..4e879b0b7c 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -881,6 +881,7 @@ typedef struct RelOptInfo
      * Vars/Exprs, cost, width
      */
     struct PathTarget *reltarget;
+    List       *uniquekeys;        /* A list of UniqueKey. */
 
     /*
      * materialization information
@@ -919,6 +920,9 @@ typedef struct RelOptInfo
     /* array indexed [min_attr .. max_attr] */
     int32       *attr_widths pg_node_attr(read_write_ignore);
 
+    /* The not null attrs from catalogs or baserestrictinfo. */
+    Bitmapset  *notnullattrs;
+
     /*
      * Zero-based set containing attnums of NOT NULL columns.  Not populated
      * for rels corresponding to non-partitioned inh==true RTEs.
@@ -1477,6 +1481,21 @@ typedef struct PathKeyInfo
     List       *clauses;
 } PathKeyInfo;
 
+
+typedef struct UniqueKey
+{
+    pg_node_attr(no_read, no_query_jumble)
+
+    NodeTag        type;
+    Bitmapset  *eclass_indexes; /* Indexes in PlannerInfo's eq_class list of
+                                 * ECs that is unique for a RelOptInfo. */
+    int            relid;
+    bool        use_for_distinct;    /* true if it is used in distinct-pathkey,
+                                     * in this case we would never check if we
+                                     * should discard it during join search. */
+}            UniqueKey;
+
+
 /*
  * VolatileFunctionStatus -- allows nodes to cache their
  * contain_volatile_functions properties. VOLATILITY_UNKNOWN means not yet
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 52df93759f..9d860f0135 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -632,6 +632,8 @@ extern bool list_member_int(const List *list, int datum);
 extern bool list_member_oid(const List *list, Oid datum);
 extern bool list_member_xid(const List *list, TransactionId datum);
 
+extern int    list_member_ptr_pos(const List *list, const void *datum);
+
 extern pg_nodiscard List *list_delete(List *list, void *datum);
 extern pg_nodiscard List *list_delete_ptr(List *list, void *datum);
 extern pg_nodiscard List *list_delete_int(List *list, int datum);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 39ba461548..f3c683b2c9 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -142,11 +142,17 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 extern EquivalenceMember *find_ec_member_matching_expr(EquivalenceClass *ec,
                                                        Expr *expr,
                                                        Relids relids);
+extern int    find_ec_position_matching_expr(PlannerInfo *root,
+                                           Expr *expr,
+                                           RelOptInfo *rel);
 extern EquivalenceMember *find_computable_ec_member(PlannerInfo *root,
                                                     EquivalenceClass *ec,
                                                     List *exprs,
                                                     Relids relids,
                                                     bool require_parallel_safe);
+extern Bitmapset *build_ec_positions_for_exprs(PlannerInfo *root,
+                                               List *exprs,
+                                               RelOptInfo *rel);
 extern bool relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
                                          EquivalenceClass *ec,
                                          bool require_parallel_safe);
@@ -270,4 +276,11 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
 extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
                                     List *live_childrels);
 
+extern bool relation_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
+                                     List *distinct_pathkey);
+extern void populate_baserel_uniquekeys(PlannerInfo *root,
+                                        RelOptInfo *baserel);
+extern void populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel,
+                                        RelOptInfo *outerrel, RelOptInfo *innerrel,
+                                        List *restrictlist, JoinType jointype);
 #endif                            /* PATHS_H */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 8b640c2fc2..675b5b1484 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5671,18 +5671,15 @@ select d.* from d left join (select * from b group by b.id, b.c_id) s
 explain (costs off)
 select d.* from d left join (select distinct * from b) s
   on d.a = s.id;
-              QUERY PLAN              
---------------------------------------
+             QUERY PLAN             
+------------------------------------
  Merge Right Join
    Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+   ->  Index Scan using b_pkey on b
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
-(9 rows)
+(6 rows)
 
 -- join removal is not possible here
 explain (costs off)
diff --git a/src/test/regress/expected/uniquekey.out b/src/test/regress/expected/uniquekey.out
new file mode 100644
index 0000000000..aa712c2dd7
--- /dev/null
+++ b/src/test/regress/expected/uniquekey.out
@@ -0,0 +1,268 @@
+CREATE TABLE uk_t (id int primary key, a int not null, b int not null, c int, d int, e int);
+explain (costs off)
+select distinct id from uk_t;
+    QUERY PLAN    
+------------------
+ Seq Scan on uk_t
+(1 row)
+
+explain (costs off)
+select distinct e from uk_t where id = e;
+     QUERY PLAN     
+--------------------
+ Seq Scan on uk_t
+   Filter: (id = e)
+(2 rows)
+
+create unique index on uk_t (a, b);
+create unique index on uk_t (c, d);
+explain (costs off)
+select distinct a, b from uk_t;
+    QUERY PLAN    
+------------------
+ Seq Scan on uk_t
+(1 row)
+
+explain (costs off)
+select distinct c, d from uk_t;
+       QUERY PLAN       
+------------------------
+ HashAggregate
+   Group Key: c, d
+   ->  Seq Scan on uk_t
+(3 rows)
+
+explain (costs off)
+select distinct c, d from uk_t
+where c > 0 and d > 0;
+                QUERY PLAN                 
+-------------------------------------------
+ Bitmap Heap Scan on uk_t
+   Recheck Cond: ((c > 0) AND (d > 0))
+   ->  Bitmap Index Scan on uk_t_c_d_idx
+         Index Cond: ((c > 0) AND (d > 0))
+(4 rows)
+
+explain (costs off)
+select distinct d from uk_t
+where c > 1 and d > 0;
+                   QUERY PLAN                    
+-------------------------------------------------
+ HashAggregate
+   Group Key: d
+   ->  Bitmap Heap Scan on uk_t
+         Recheck Cond: ((c > 1) AND (d > 0))
+         ->  Bitmap Index Scan on uk_t_c_d_idx
+               Index Cond: ((c > 1) AND (d > 0))
+(6 rows)
+
+explain (costs off)
+select distinct d from uk_t
+where c = 1 and d > 0;
+                QUERY PLAN                 
+-------------------------------------------
+ Bitmap Heap Scan on uk_t
+   Recheck Cond: ((c = 1) AND (d > 0))
+   ->  Bitmap Index Scan on uk_t_c_d_idx
+         Index Cond: ((c = 1) AND (d > 0))
+(4 rows)
+
+-- test the join case --
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id;
+           QUERY PLAN            
+---------------------------------
+ Hash Join
+   Hash Cond: (t1.e = t2.id)
+   ->  Seq Scan on uk_t t1
+   ->  Hash
+         ->  Seq Scan on uk_t t2
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.a and t1.d = t2.b;
+                   QUERY PLAN                   
+------------------------------------------------
+ Hash Join
+   Hash Cond: ((t1.e = t2.a) AND (t1.d = t2.b))
+   ->  Seq Scan on uk_t t1
+   ->  Hash
+         ->  Seq Scan on uk_t t2
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON t1.e = t2.id;
+     QUERY PLAN      
+---------------------
+ Seq Scan on uk_t t1
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON t1.e = t2.a and t1.d = t2.b;
+     QUERY PLAN      
+---------------------
+ Seq Scan on uk_t t1
+(1 row)
+
+-- outer join makes null values so distinct can't be a no-op.
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 RIGHT JOIN uk_t t2 ON t1.e = t2.id;
+              QUERY PLAN               
+---------------------------------------
+ HashAggregate
+   Group Key: t1.id
+   ->  Hash Right Join
+         Hash Cond: (t1.e = t2.id)
+         ->  Seq Scan on uk_t t1
+         ->  Hash
+               ->  Seq Scan on uk_t t2
+(7 rows)
+
+-- single row case.
+-- single row is unqiue all the time.
+-- case 1:
+-- t1.d is single row at base rel level, and because of t1.e = t2.id, it is
+-- still single row after join.
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.d FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id and t1.id = 1;
+                    QUERY PLAN                    
+--------------------------------------------------
+ Nested Loop
+   ->  Index Scan using uk_t_pkey on uk_t t1
+         Index Cond: (id = 1)
+   ->  Index Only Scan using uk_t_pkey on uk_t t2
+         Index Cond: (id = t1.e)
+(5 rows)
+
+-- case 2
+-- any uniquekey which join with single row whose uniqueness can be kept.
+-- t1.d is single row at base rel level because of t1.id = 1
+-- so t2's uniquekey can be kept when join with t2.any_column.
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id FROM uk_t t1 JOIN uk_t t2 ON t2.e = t1.e and t1.id = 1;
+                    QUERY PLAN                     
+---------------------------------------------------
+ Hash Join
+   Hash Cond: (t2.e = t1.e)
+   ->  Seq Scan on uk_t t2
+   ->  Hash
+         ->  Index Scan using uk_t_pkey on uk_t t1
+               Index Cond: (id = 1)
+(6 rows)
+
+insert into uk_t SELECT 1, 2, 3, 4, 5, 6;
+-- combined uniquekey cases.
+-- the combinations of uniquekeys from the 2 sides is still unique
+-- no matter the join method and join clauses.
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON true;
+           QUERY PLAN            
+---------------------------------
+ Nested Loop
+   ->  Seq Scan on uk_t t1
+   ->  Materialize
+         ->  Seq Scan on uk_t t2
+(4 rows)
+
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON true;
+ id | id 
+----+----
+  1 |  1
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON false;
+        QUERY PLAN        
+--------------------------
+ Result
+   One-Time Filter: false
+(2 rows)
+
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON false;
+ id | id 
+----+----
+(0 rows)
+
+-- BAD CASE: the distinct should be marked as noop in the below 4 cases, but
+-- since it is nullable by outer join, so it can't be removed. However the rule
+-- here should be if both uniquekey are not nullable, the combinations of them
+-- is not *mutli* nullable even by outer join. It is not clear to me how to
+-- implement it since I am just feeling not maintaining the not-null stuff
+-- during the joins is pretty amazing, otherwise there are too many stuff to
+-- do to cover this special case.
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON true;
+              QUERY PLAN               
+---------------------------------------
+ HashAggregate
+   Group Key: t2.id, t1.id
+   ->  Nested Loop Left Join
+         ->  Seq Scan on uk_t t1
+         ->  Materialize
+               ->  Seq Scan on uk_t t2
+(6 rows)
+
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON true;
+ id | id 
+----+----
+  1 |  1
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON false;
+              QUERY PLAN              
+--------------------------------------
+ HashAggregate
+   Group Key: id, t1.id
+   ->  Nested Loop Left Join
+         Join Filter: false
+         ->  Seq Scan on uk_t t1
+         ->  Result
+               One-Time Filter: false
+(7 rows)
+
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON false;
+ id | id 
+----+----
+    |  1
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON true;
+              QUERY PLAN               
+---------------------------------------
+ HashAggregate
+   Group Key: t2.id, t1.id
+   ->  Merge Full Join
+         ->  Seq Scan on uk_t t1
+         ->  Materialize
+               ->  Seq Scan on uk_t t2
+(6 rows)
+
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON true;
+ id | id 
+----+----
+  1 |  1
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON false;
+                 QUERY PLAN                  
+---------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: t2.id, t1.id
+         ->  Merge Full Join
+               Join Filter: false
+               ->  Seq Scan on uk_t t1
+               ->  Materialize
+                     ->  Seq Scan on uk_t t2
+(8 rows)
+
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON false;
+ id | id 
+----+----
+  1 |   
+    |  1
+(2 rows)
+
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 675c567617..8d9ede091d 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -62,7 +62,7 @@ test: sanity_check
 # join depends on create_misc
 # ----------
 test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join
aggregatestransactions random portals arrays btree_index hash_index update delete namespace prepared_xacts
 
-
+test: uniquekey
 # ----------
 # Another group of parallel tests
 # ----------
diff --git a/src/test/regress/sql/uniquekey.sql b/src/test/regress/sql/uniquekey.sql
new file mode 100644
index 0000000000..4db0213a04
--- /dev/null
+++ b/src/test/regress/sql/uniquekey.sql
@@ -0,0 +1,104 @@
+CREATE TABLE uk_t (id int primary key, a int not null, b int not null, c int, d int, e int);
+
+explain (costs off)
+select distinct id from uk_t;
+
+explain (costs off)
+select distinct e from uk_t where id = e;
+
+create unique index on uk_t (a, b);
+create unique index on uk_t (c, d);
+
+explain (costs off)
+select distinct a, b from uk_t;
+
+explain (costs off)
+select distinct c, d from uk_t;
+
+explain (costs off)
+select distinct c, d from uk_t
+where c > 0 and d > 0;
+
+explain (costs off)
+select distinct d from uk_t
+where c > 1 and d > 0;
+
+explain (costs off)
+select distinct d from uk_t
+where c = 1 and d > 0;
+
+
+-- test the join case --
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id;
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.a and t1.d = t2.b;
+
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON t1.e = t2.id;
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON t1.e = t2.a and t1.d = t2.b;
+
+-- outer join makes null values so distinct can't be a no-op.
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.id FROM uk_t t1 RIGHT JOIN uk_t t2 ON t1.e = t2.id;
+
+-- single row case.
+
+-- single row is unqiue all the time.
+
+-- case 1:
+-- t1.d is single row at base rel level, and because of t1.e = t2.id, it is
+-- still single row after join.
+EXPLAIN (COSTS OFF)
+SELECT distinct t1.d FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id and t1.id = 1;
+
+-- case 2
+-- any uniquekey which join with single row whose uniqueness can be kept.
+-- t1.d is single row at base rel level because of t1.id = 1
+-- so t2's uniquekey can be kept when join with t2.any_column.
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id FROM uk_t t1 JOIN uk_t t2 ON t2.e = t1.e and t1.id = 1;
+
+insert into uk_t SELECT 1, 2, 3, 4, 5, 6;
+
+-- combined uniquekey cases.
+-- the combinations of uniquekeys from the 2 sides is still unique
+-- no matter the join method and join clauses.
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON true;
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON true;
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON false;
+SELECT distinct t2.id, t1.id FROM uk_t t1 JOIN uk_t t2 ON false;
+
+
+-- BAD CASE: the distinct should be marked as noop in the below 4 cases, but
+-- since it is nullable by outer join, so it can't be removed. However the rule
+-- here should be if both uniquekey are not nullable, the combinations of them
+-- is not *mutli* nullable even by outer join. It is not clear to me how to
+-- implement it since I am just feeling not maintaining the not-null stuff
+-- during the joins is pretty amazing, otherwise there are too many stuff to
+-- do to cover this special case.
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON true;
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON true;
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON false;
+SELECT distinct t2.id, t1.id FROM uk_t t1 LEFT JOIN uk_t t2 ON false;
+
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON true;
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON true;
+
+EXPLAIN (COSTS OFF)
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON false;
+SELECT distinct t2.id, t1.id FROM uk_t t1 FULL JOIN uk_t t2 ON false;
-- 
2.44.0

From 0351ade32c93e9360b11c7dd00b521cebb3c86dd Mon Sep 17 00:00:00 2001
From: Antonin Houska <ah@cybertec.at>
Date: Thu, 18 Apr 2024 15:28:36 +0200
Subject: [PATCH 2/5] Moved functions to uniquekey.c.

They are not called from other modules.
---
 src/backend/optimizer/path/equivclass.c | 48 ----------------------
 src/backend/optimizer/path/uniquekey.c  | 53 +++++++++++++++++++++++++
 src/include/optimizer/paths.h           |  6 ---
 3 files changed, 53 insertions(+), 54 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 892cd0000c..1d6bedb399 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -755,54 +755,6 @@ get_eclass_for_sort_expr(PlannerInfo *root,
     return newec;
 }
 
-/*
- * find_ec_position_matching_expr
- *        Locate the position of EquivalenceClass whose members matching
- *        the given expr, if any; return -1 if no match.
- */
-int
-find_ec_position_matching_expr(PlannerInfo *root,
-                               Expr *expr,
-                               RelOptInfo *baserel)
-{
-    int            i = -1;
-
-    while ((i = bms_next_member(baserel->eclass_indexes, i)) >= 0)
-    {
-        EquivalenceClass *ec = list_nth(root->eq_classes, i);
-
-        if (find_ec_member_matching_expr(ec, expr, baserel->relids))
-            return i;
-    }
-    return -1;
-}
-
-/*
- * build_ec_positions_for_exprs
- *
- *        Given a list of exprs, find the related EC positions for each of
- *        them. if any exprs has no EC related, return NULL;
- */
-Bitmapset *
-build_ec_positions_for_exprs(PlannerInfo *root, List *exprs, RelOptInfo *rel)
-{
-    ListCell   *lc;
-    Bitmapset  *res = NULL;
-
-    foreach(lc, exprs)
-    {
-        int            pos = find_ec_position_matching_expr(root, lfirst(lc), rel);
-
-        if (pos < 0)
-        {
-            bms_free(res);
-            return NULL;
-        }
-        res = bms_add_member(res, pos);
-    }
-    return res;
-}
-
 /*
  * find_ec_member_matching_expr
  *        Locate an EquivalenceClass member matching the given expr, if any;
diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c
index ecc7c6d802..d3f9aaaac8 100644
--- a/src/backend/optimizer/path/uniquekey.c
+++ b/src/backend/optimizer/path/uniquekey.c
@@ -26,6 +26,11 @@ static bool add_uniquekey_for_uniqueindex(PlannerInfo *root,
                                           IndexOptInfo *unique_index,
                                           List *truncatable_exprs,
                                           List *expr_opfamilies);
+static Bitmapset *build_ec_positions_for_exprs(PlannerInfo *root, List *exprs,
+                                               RelOptInfo *rel);
+static int find_ec_position_matching_expr(PlannerInfo *root,
+                                          Expr *expr,
+                                          RelOptInfo *baserel);
 static bool unique_ecs_useful_for_distinct(PlannerInfo *root, Bitmapset *ec_indexes);
 
 /* Helper functions to create UniqueKey. */
@@ -193,6 +198,54 @@ add_uniquekey_for_uniqueindex(PlannerInfo *root, IndexOptInfo *unique_index,
     return false;
 }
 
+/*
+ * find_ec_position_matching_expr
+ *        Locate the position of EquivalenceClass whose members matching
+ *        the given expr, if any; return -1 if no match.
+ */
+static int
+find_ec_position_matching_expr(PlannerInfo *root,
+                               Expr *expr,
+                               RelOptInfo *baserel)
+{
+    int            i = -1;
+
+    while ((i = bms_next_member(baserel->eclass_indexes, i)) >= 0)
+    {
+        EquivalenceClass *ec = list_nth(root->eq_classes, i);
+
+        if (find_ec_member_matching_expr(ec, expr, baserel->relids))
+            return i;
+    }
+    return -1;
+}
+
+/*
+ * build_ec_positions_for_exprs
+ *
+ *        Given a list of exprs, find the related EC positions for each of
+ *        them. if any exprs has no EC related, return NULL;
+ */
+static Bitmapset *
+build_ec_positions_for_exprs(PlannerInfo *root, List *exprs, RelOptInfo *rel)
+{
+    ListCell   *lc;
+    Bitmapset  *res = NULL;
+
+    foreach(lc, exprs)
+    {
+        int            pos = find_ec_position_matching_expr(root, lfirst(lc), rel);
+
+        if (pos < 0)
+        {
+            bms_free(res);
+            return NULL;
+        }
+        res = bms_add_member(res, pos);
+    }
+    return res;
+}
+
 /*
  *    make_uniquekey
  *        Based on UnqiueKey rules, it is impossible for a UnqiueKey
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f3c683b2c9..b3fadd2f05 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -142,17 +142,11 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 extern EquivalenceMember *find_ec_member_matching_expr(EquivalenceClass *ec,
                                                        Expr *expr,
                                                        Relids relids);
-extern int    find_ec_position_matching_expr(PlannerInfo *root,
-                                           Expr *expr,
-                                           RelOptInfo *rel);
 extern EquivalenceMember *find_computable_ec_member(PlannerInfo *root,
                                                     EquivalenceClass *ec,
                                                     List *exprs,
                                                     Relids relids,
                                                     bool require_parallel_safe);
-extern Bitmapset *build_ec_positions_for_exprs(PlannerInfo *root,
-                                               List *exprs,
-                                               RelOptInfo *rel);
 extern bool relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
                                          EquivalenceClass *ec,
                                          bool require_parallel_safe);
-- 
2.44.0

From 1a6ccb87c4be7d0f15ff8d273f28929ec0fc9264 Mon Sep 17 00:00:00 2001
From: Antonin Houska <ah@cybertec.at>
Date: Thu, 18 Apr 2024 16:20:06 +0200
Subject: [PATCH 3/5] Do not use expression indexes to create unique keys.

The existing code does not rely on predOK when checking uniqueness, so don't
let the new code do that.
---
 src/backend/optimizer/path/uniquekey.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c
index d3f9aaaac8..0b65ff135f 100644
--- a/src/backend/optimizer/path/uniquekey.c
+++ b/src/backend/optimizer/path/uniquekey.c
@@ -98,8 +98,12 @@ populate_baserel_uniquekeys(PlannerInfo *root, RelOptInfo *rel)
     {
         IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
 
-        if (!index->unique || !index->immediate ||
-            (index->indpred != NIL && !index->predOK))
+        /*
+         * Like in relation_has_unique_index_for(), we shouldn't use predOK
+         * because its validity might depend on join clauses, however here we
+         * test uniqueness of the join input.
+         */
+        if (!index->unique || !index->immediate || index->indpred != NIL)
             continue;
 
         if (add_uniquekey_for_uniqueindex(root, index,
-- 
2.44.0

From 47efe758434ba8a58de50b0124853de29f48f6b4 Mon Sep 17 00:00:00 2001
From: Antonin Houska <ah@cybertec.at>
Date: Thu, 18 Apr 2024 16:40:36 +0200
Subject: [PATCH 4/5] Teach the planner to pass UniqueKey nodes from a subquery
 to the parent query.

So far it was only possible to recognize uniqueness of the output of
relatively simple subqueries. With this feature, more complex subqueries can
be checked, even those "hidden" in a view with security_barrier enabled. Thus
there should be more opportunities to apply specific optimizations. Typically,
when the inner relation of join is unique, then INNER join can be replaced
with SEMI join.
---
 src/backend/optimizer/path/allpaths.c     |  17 +
 src/backend/optimizer/path/equivclass.c   |   5 +-
 src/backend/optimizer/path/indxpath.c     |   6 +-
 src/backend/optimizer/path/pathkeys.c     |   6 +-
 src/backend/optimizer/path/uniquekey.c    | 487 ++++++++++++++++++++--
 src/backend/optimizer/plan/analyzejoins.c |  46 ++
 src/backend/optimizer/plan/planner.c      |  84 +++-
 src/include/nodes/pathnodes.h             |  26 +-
 src/include/optimizer/paths.h             |  10 +
 src/test/regress/expected/join.out        |  66 +--
 src/test/regress/expected/subselect.out   |  24 ++
 src/test/regress/sql/join.sql             |  13 +-
 src/test/regress/sql/subselect.sql        |  13 +
 13 files changed, 729 insertions(+), 74 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index ced0fce415..faedc4a247 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2667,6 +2667,23 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
         return;
     }
 
+    /*
+     * Translate the subquery unique keys so that 'rel' can use them.
+     *
+     * The final relation is not guaranteed to have the target set, so
+     * retrieve it from ->upper_targets.
+     *
+     * Unique keys are currently not supported for RELOPT_OTHER_MEMBER_REL.
+     */
+    if (rel->reloptkind == RELOPT_BASEREL)
+    {
+        PathTarget    *sub_final_target;
+
+        sub_final_target = rel->subroot->upper_targets[UPPERREL_FINAL];
+        convert_unique_keys_for_rel(root, rel, NULL, sub_final_rel,
+                                    sub_final_target);
+    }
+
     /*
      * Mark rel with estimated output rows, width, etc.  Note that we have to
      * do this before generating outer-query paths, else cost_subqueryscan is
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 1d6bedb399..95d4722b41 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -591,9 +591,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
                          Oid collation,
                          Index sortref,
                          Relids rel,
+                         JoinDomain *jdomain,
                          bool create_it)
 {
-    JoinDomain *jdomain;
     Relids        expr_relids;
     EquivalenceClass *newec;
     EquivalenceMember *newem;
@@ -609,7 +609,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
      * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
      * BY, etc), they can be presumed to belong to the top JoinDomain.
      */
-    jdomain = linitial_node(JoinDomain, root->join_domains);
+    if (jdomain == NULL)
+        jdomain = linitial_node(JoinDomain, root->join_domains);
 
     /*
      * Scan through the existing EquivalenceClasses for a match
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 2230b13104..87081627ac 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -151,7 +151,6 @@ static IndexClause *match_clause_to_indexcol(PlannerInfo *root,
                                              RestrictInfo *rinfo,
                                              int indexcol,
                                              IndexOptInfo *index);
-static bool IsBooleanOpfamily(Oid opfamily);
 static IndexClause *match_boolean_index_clause(PlannerInfo *root,
                                                RestrictInfo *rinfo,
                                                int indexcol, IndexOptInfo *index);
@@ -2275,8 +2274,11 @@ match_clause_to_indexcol(PlannerInfo *root,
  * If the opfamily OID is in the range of built-in objects, we can rely
  * on hard-wired knowledge of which built-in opfamilies support this.
  * For extension opfamilies, there's no choice but to do a catcache lookup.
+ *
+ * TODO If the call from equivclass.c remains, move this function to better
+ * place.
  */
-static bool
+bool
 IsBooleanOpfamily(Oid opfamily)
 {
     if (opfamily < FirstNormalObjectId)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 1d61881a6b..9e69085b5d 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -233,7 +233,7 @@ make_pathkey_from_sortinfo(PlannerInfo *root,
     /* Now find or (optionally) create a matching EquivalenceClass */
     eclass = get_eclass_for_sort_expr(root, expr,
                                       opfamilies, opcintype, collation,
-                                      sortref, rel, create_it);
+                                      sortref, rel, NULL, create_it);
 
     /* Fail if no EC and !create_it */
     if (!eclass)
@@ -1122,6 +1122,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
                                              sub_eclass->ec_collation,
                                              0,
                                              rel->relids,
+                                             NULL,
                                              false);
 
                 /*
@@ -1203,6 +1204,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
                                                         sub_expr_coll,
                                                         0,
                                                         rel->relids,
+                                                        NULL,
                                                         false);
 
                     /*
@@ -1467,6 +1469,7 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
                                  ((OpExpr *) clause)->inputcollid,
                                  0,
                                  NULL,
+                                 NULL,
                                  true);
     restrictinfo->right_ec =
         get_eclass_for_sort_expr(root,
@@ -1476,6 +1479,7 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
                                  ((OpExpr *) clause)->inputcollid,
                                  0,
                                  NULL,
+                                 NULL,
                                  true);
 }
 
diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c
index 0b65ff135f..4200663b82 100644
--- a/src/backend/optimizer/path/uniquekey.c
+++ b/src/backend/optimizer/path/uniquekey.c
@@ -19,7 +19,20 @@
 #include "nodes/pathnodes.h"
 #include "optimizer/optimizer.h"
 #include "optimizer/paths.h"
+#include "utils/lsyscache.h"
 
+/*
+ * Information on a column of an unique index for which we are trying to
+ * create an unique key.
+ */
+typedef struct UniqueKeyExpr
+{
+    /* The expression itself. */
+    Expr    *expr;
+
+    /* Operator family to find / create suitable equivalence class. */
+    Oid        opfamily;
+} UniqueKeyExpr;
 
 /* Functions to populate UniqueKey */
 static bool add_uniquekey_for_uniqueindex(PlannerInfo *root,
@@ -29,23 +42,24 @@ static bool add_uniquekey_for_uniqueindex(PlannerInfo *root,
 static Bitmapset *build_ec_positions_for_exprs(PlannerInfo *root, List *exprs,
                                                RelOptInfo *rel);
 static int find_ec_position_matching_expr(PlannerInfo *root,
-                                          Expr *expr,
-                                          RelOptInfo *baserel);
+                                          RelOptInfo *baserel,
+                                          Expr *expr, List *opfamilies);
 static bool unique_ecs_useful_for_distinct(PlannerInfo *root, Bitmapset *ec_indexes);
 
 /* Helper functions to create UniqueKey. */
-static UniqueKey * make_uniquekey(Bitmapset *eclass_indexes,
+static UniqueKey * make_uniquekey(Bitmapset *item_indexes,
+                                  List *opfamily_lists,
                                   bool useful_for_distinct);
 static void mark_rel_singlerow(RelOptInfo *rel, int relid);
 
 static UniqueKey * rel_singlerow_uniquekey(RelOptInfo *rel);
-static bool uniquekey_contains_multinulls(PlannerInfo *root, RelOptInfo *rel, UniqueKey * ukey);
 
 /* Debug only */
 static void print_uniquekey(PlannerInfo *root, RelOptInfo *rel);
 
 static bool uniquekey_contains_in(PlannerInfo *root, UniqueKey * ukey, Bitmapset *ecs, Relids relids);
 static bool is_uniquekey_useful_afterjoin(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *joinrel);
+static int find_expr_pos_in_list(Expr *expr, List *list);
 
 /*
  * populate_baserel_uniquekeys
@@ -61,6 +75,9 @@ populate_baserel_uniquekeys(PlannerInfo *root, RelOptInfo *rel)
     List       *truncatable_exprs = NIL,
                *expr_opfamilies = NIL;
 
+    if (rel->reloptkind != RELOPT_BASEREL)
+        return;
+
     /*
      * Currently we only use UniqueKey for mark-distinct-as-noop case, so if
      * there is no-distinct-clause at all, we can ignore the maintenance at
@@ -132,7 +149,8 @@ add_uniquekey_for_uniqueindex(PlannerInfo *root, IndexOptInfo *unique_index,
     ListCell   *indexpr_item;
     RelOptInfo *rel = unique_index->rel;
     bool        used_for_distinct;
-    int            c;
+    int            c, i;
+    List        *opfamily_lists = NIL;
 
     indexpr_item = list_head(unique_index->indexprs);
 
@@ -143,6 +161,7 @@ add_uniquekey_for_uniqueindex(PlannerInfo *root, IndexOptInfo *unique_index,
         bool        matched_const = false;
         ListCell   *lc1,
                    *lc2;
+        UniqueKeyExpr    *uexpr;
 
         if (attr > 0)
         {
@@ -174,7 +193,10 @@ add_uniquekey_for_uniqueindex(PlannerInfo *root, IndexOptInfo *unique_index,
         if (matched_const)
             continue;
 
-        unique_exprs = lappend(unique_exprs, expr);
+        uexpr = palloc_object(UniqueKeyExpr);
+        uexpr->expr = expr;
+        uexpr->opfamily = unique_index->opfamily[c];
+        unique_exprs = lappend(unique_exprs, uexpr);
     }
 
     if (unique_exprs == NIL)
@@ -193,35 +215,94 @@ add_uniquekey_for_uniqueindex(PlannerInfo *root, IndexOptInfo *unique_index,
     if (unique_ecs == NULL)
         return false;
 
+    /* Collect the operator families. */
+    i = -1;
+    while ((i = bms_next_member(unique_ecs, i)) >= 0)
+    {
+        EquivalenceClass    *ec = list_nth(root->eq_classes, i);
+
+        opfamily_lists = lappend(opfamily_lists, ec->ec_opfamilies);
+    }
+
     used_for_distinct = unique_ecs_useful_for_distinct(root, unique_ecs);
 
 
     rel->uniquekeys = lappend(rel->uniquekeys,
-                              make_uniquekey(unique_ecs,
+                              make_uniquekey(unique_ecs, opfamily_lists,
                                              used_for_distinct));
     return false;
 }
 
 /*
  * find_ec_position_matching_expr
- *        Locate the position of EquivalenceClass whose members matching
- *        the given expr, if any; return -1 if no match.
+ *        Locate the position of EquivalenceClass whose members matching the
+ *        given expr. Try to create EC if suitable one does not exist. Return -1
+ *        if there is not enough information in the catalog about the data type
+ *        to create the EC.
  */
 static int
-find_ec_position_matching_expr(PlannerInfo *root,
-                               Expr *expr,
-                               RelOptInfo *baserel)
+find_ec_position_matching_expr(PlannerInfo *root, RelOptInfo *baserel,
+                               Expr *expr, List *opfamilies)
 {
     int            i = -1;
+    EquivalenceClass *ec;
+    int        ec_index;
+    JoinDomain *jdomain;
+    ListCell    *lc;
+
+    /*
+     * XXX Currently the function is only used to build unique keys, so we
+     * don't create ECs for boolean columns: normal EC processing does not
+     * create them as well and build_index_pathkeys() considers boolean
+     * pathkeys redundant, so missing boolean EC is o.k. However, if we
+     * created the boolean ECs, build_index_pathkeys() would return the
+     * corresponding pathkeys, and those could mismatch query_pathkeys.
+     * Shouldn't this be handled in pathkeys_useful_for_ordering()?
+     */
+    foreach(lc, opfamilies)
+    {
+        /* XXX The result should be the same for each item of the list. */
+        if (IsBooleanOpfamily(lfirst_oid(lc)))
+            return -1;
+    }
 
     while ((i = bms_next_member(baserel->eclass_indexes, i)) >= 0)
     {
-        EquivalenceClass *ec = list_nth(root->eq_classes, i);
+        List    *diff;
+
+        ec = list_nth(root->eq_classes, i);
+
+        /*
+         * The EC must understand equality in the same way as the unique index
+         * that guarantees the uniqueness. That is, ec_opfamilies must contain
+         * all the opfamilies passed by the caller.
+         */
+        diff = list_difference_oid(opfamilies, ec->ec_opfamilies);
+        if (list_length(diff) > 0)
+            continue;
 
         if (find_ec_member_matching_expr(ec, expr, baserel->relids))
             return i;
     }
-    return -1;
+
+    /* Create the EC. */
+    jdomain = makeNode(JoinDomain);
+    jdomain->jd_relids = pull_varnos(root, (Node *) expr);
+    ec = get_eclass_for_sort_expr(root, expr,
+                                  opfamilies,
+                                  exprType((Node *) expr),
+                                  exprCollation((Node *) expr),
+                                  0,
+                                  NULL,
+                                  jdomain,
+                                  true);
+    ec_index = list_length(root->eq_classes) - 1;
+
+    /* The new EC should now be known to both 'root' and 'baserel'. */
+    Assert(ec == llast(root->eq_classes));
+    Assert(bms_is_member(ec_index, baserel->eclass_indexes));
+
+    return ec_index;
 }
 
 /*
@@ -238,7 +319,10 @@ build_ec_positions_for_exprs(PlannerInfo *root, List *exprs, RelOptInfo *rel)
 
     foreach(lc, exprs)
     {
-        int            pos = find_ec_position_matching_expr(root, lfirst(lc), rel);
+        UniqueKeyExpr    *uexpr = (UniqueKeyExpr *) lfirst(lc);
+        int            pos = find_ec_position_matching_expr(root, rel,
+                                                         uexpr->expr,
+                                                         list_make1_oid(uexpr->opfamily));
 
         if (pos < 0)
         {
@@ -248,20 +332,23 @@ build_ec_positions_for_exprs(PlannerInfo *root, List *exprs, RelOptInfo *rel)
         res = bms_add_member(res, pos);
     }
     return res;
+
 }
 
 /*
  *    make_uniquekey
  *        Based on UnqiueKey rules, it is impossible for a UnqiueKey
- * which have eclass_indexes and relid both set. This function just
- * handle eclass_indexes case.
+ * which have item_indexes and relid both set. This function just
+ * handle item_indexes case.
  */
 static UniqueKey *
-make_uniquekey(Bitmapset *eclass_indexes, bool useful_for_distinct)
+make_uniquekey(Bitmapset *item_indexes, List *opfamily_lists,
+               bool useful_for_distinct)
 {
     UniqueKey  *ukey = makeNode(UniqueKey);
 
-    ukey->eclass_indexes = eclass_indexes;
+    ukey->item_indexes = item_indexes;
+    ukey->opfamily_lists = opfamily_lists;
     ukey->relid = 0;
     ukey->use_for_distinct = useful_for_distinct;
     return ukey;
@@ -321,7 +408,7 @@ print_uniquekey(PlannerInfo *root, RelOptInfo *rel)
             UniqueKey  *ukey = lfirst_node(UniqueKey, lc);
 
             elog(INFO, "UNIQUEKEY{indexes=%s, singlerow_rels=%d, use_for_distinct=%d}",
-                 bmsToString(ukey->eclass_indexes),
+                 bmsToString(ukey->item_indexes),
                  ukey->relid,
                  ukey->use_for_distinct);
         }
@@ -352,12 +439,12 @@ var_is_nullable(PlannerInfo *root, Var *var, RelOptInfo *rel)
  *
  *    Check if the uniquekey contains nulls values.
  */
-static bool
+bool
 uniquekey_contains_multinulls(PlannerInfo *root, RelOptInfo *rel, UniqueKey * ukey)
 {
     int            i = -1;
 
-    while ((i = bms_next_member(ukey->eclass_indexes, i)) >= 0)
+    while ((i = bms_next_member(ukey->item_indexes, i)) >= 0)
     {
         EquivalenceClass *ec = list_nth_node(EquivalenceClass, root->eq_classes, i);
         ListCell   *lc;
@@ -421,7 +508,7 @@ relation_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *distinct_path
     {
         UniqueKey  *ukey = lfirst_node(UniqueKey, lc);
 
-        if (bms_is_subset(ukey->eclass_indexes, pathkey_bm) &&
+        if (bms_is_subset(ukey->item_indexes, pathkey_bm) &&
             !uniquekey_contains_multinulls(root, rel, ukey))
             return true;
     }
@@ -611,6 +698,10 @@ populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel,
         foreach(lc2, innerrel->uniquekeys)
         {
             UniqueKey  *inner_ukey = lfirst(lc2);
+            Bitmapset    *indexes_new;
+            List    *opfamily_lists_new = NIL;
+            int        i;
+            ListCell    *lo, *li;
 
             if (!is_uniquekey_useful_afterjoin(root, inner_ukey, joinrel))
                 continue;
@@ -618,9 +709,35 @@ populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel,
             /* singlerow will make the outeruk_still_valid true */
             Assert(!uniquekey_is_singlerow(inner_ukey));
 
+            /* Assemble opfamily_lists_new in the correct order.  */
+            i = -1;
+            indexes_new = bms_union(outer_ukey->item_indexes, inner_ukey->item_indexes);
+            lo = list_head(outer_ukey->opfamily_lists);
+            li = list_head(inner_ukey->opfamily_lists);
+            while ((i = bms_next_member(indexes_new, i)) >= 0)
+            {
+                List    *l;
+
+                if (bms_is_member(i, outer_ukey->item_indexes))
+                {
+                    l = lfirst(lo);
+                    lo = lnext(outer_ukey->opfamily_lists, lo);
+                }
+                else
+                {
+                    Assert(bms_is_member(i, inner_ukey->item_indexes));
+
+                    l = lfirst(li);
+                    li = lnext(inner_ukey->opfamily_lists, li);
+                }
+
+                opfamily_lists_new = lappend(opfamily_lists_new, l);
+            }
+
             joinrel->uniquekeys = lappend(joinrel->uniquekeys,
                                           make_uniquekey(
-                                                         bms_union(outer_ukey->eclass_indexes,
inner_ukey->eclass_indexes),
+                                                         indexes_new,
+                                                         opfamily_lists_new,
                                                          outer_ukey->use_for_distinct ||
inner_ukey->use_for_distinct));
         }
     }
@@ -640,7 +757,7 @@ uniquekey_contains_in(PlannerInfo *root, UniqueKey * ukey, Bitmapset *ecs, Relid
         return bms_is_member(ukey->relid, relids);
     }
 
-    return bms_is_subset(ukey->eclass_indexes, ecs);
+    return bms_is_subset(ukey->item_indexes, ecs);
 }
 
 
@@ -656,7 +773,7 @@ uniquekey_useful_for_merging(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *re
 
     int            i = -1;
 
-    while ((i = bms_next_member(ukey->eclass_indexes, i)) >= 0)
+    while ((i = bms_next_member(ukey->item_indexes, i)) >= 0)
     {
         EquivalenceClass *ec = list_nth(root->eq_classes, i);
         ListCell   *j;
@@ -709,3 +826,321 @@ is_uniquekey_useful_afterjoin(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *j
 
     return uniquekey_useful_for_merging(root, ukey, joinrel);
 }
+
+
+/*
+ * convert_unique_keys_for_rel
+ *
+ * Convert unique keys of 'input_relation' and assign them to 'rel'. The
+ * comments of UniqueKey explain the difference in the format.
+ *
+ * This function assumes that at least one of the relations is "upper
+ * relation". If 'input_rel' is upper and 'rel' is base/join rel, pass NULL
+ * for 'target'.
+ */
+void
+convert_unique_keys_for_rel(PlannerInfo *root, RelOptInfo *rel,
+                            PathTarget *target, RelOptInfo *input_rel,
+                            PathTarget *input_target)
+{
+    ListCell    *lc1;
+
+    /* No unique keys, in case we return early. */
+    rel->uniquekeys = NIL;
+
+    /*
+     * Set-returning functions can break uniqueness. This does not necessarily
+     * affect all of the upper relations, but checking is not trivial and
+     * should be done by the caller rather than by this function. Make the
+     * logic simple for now.
+     */
+    if (root->parse->hasTargetSRFs)
+        return;
+
+    /* No keys to convert? */
+    if (input_rel->uniquekeys == NIL)
+        return;
+
+    /*
+     * If both relations are upper and if they have the same target,
+     * just copy the uniquekeys unmodified.
+     */
+    if (IS_UPPER_REL(rel) && IS_UPPER_REL(input_rel) &&
+        target == input_target)
+    {
+        rel->uniquekeys = copyObject(input_rel->uniquekeys);
+        return;
+    }
+
+    foreach(lc1, input_rel->uniquekeys)
+    {
+        UniqueKey  *key = lfirst_node(UniqueKey, lc1);
+        Bitmapset    *item_indexes_new = NULL;
+        List    *opfamily_lists_new = NIL;
+        int        matched;
+        int        i = -1;
+        ListCell    *lc2;
+
+        if (!IS_UPPER_REL(input_rel))
+        {
+            /* Conversion between base/join rels is currently not needed. */
+            IS_UPPER_REL(rel);
+
+            /*
+             * For each key, check its ECs and find the EM present in
+             * 'target'.
+             */
+            while ((i = bms_next_member(key->item_indexes, i)) >= 0)
+            {
+                EquivalenceClass *ec = list_nth(root->eq_classes, i);
+
+                matched = -1;
+                foreach(lc2, ec->ec_members)
+                {
+                    EquivalenceMember *em;
+                    Expr    *expr;
+
+                    em = lfirst_node(EquivalenceMember, lc2);
+                    expr = em->em_expr;
+
+                    /* EMs can be wrapped in RelabelType. */
+                    while (expr && IsA(expr, RelabelType))
+                        expr = ((RelabelType *) expr)->arg;
+
+                    /*
+                     * Currently we only accept Vars, for simplicity (and
+                     * because the unique key shouldn't contain other
+                     * nodes). In general, we look for expressions that map
+                     * unique input value to unique output value. Not sure
+                     * though how we can recognize them easily.
+                     */
+                    if (!IsA(expr, Var))
+                        continue;
+
+                    matched = find_expr_pos_in_list(expr, target->exprs);
+                    if (matched >= 0)
+                        break;
+                }
+
+                if (matched >= 0)
+                {
+                    item_indexes_new = bms_add_member(item_indexes_new,
+                                                      matched);
+                    opfamily_lists_new = lappend(opfamily_lists_new,
+                                                 ec->ec_opfamilies);
+                }
+                else
+                {
+                    /* The caller does not want an incomplete unique key. */
+                    bms_free(item_indexes_new);
+                    item_indexes_new = NULL;
+                    list_free(opfamily_lists_new);
+                    opfamily_lists_new = NIL;
+                    break;
+                }
+            }
+        }
+        else
+        {
+            ListCell    *lc2 = list_head(key->opfamily_lists);
+
+            /* IS_UPPER_REL(input_rel) */
+
+            Assert(bms_num_members(key->item_indexes) ==
+                   list_length(key->opfamily_lists));
+
+            /*
+             * For an upper relation, 'index_items' point to expressions of an
+             * existing target. For each key, find its target expressions in
+             * 'target' or (if target==NULL) in the members of the ECs 'rel'
+             * belongs to.
+             */
+            while ((i = bms_next_member(key->item_indexes, i)) >= 0)
+            {
+                Expr    *expr;
+
+                expr = (Expr *) list_nth(input_target->exprs, i);
+
+                if (target)
+                {
+                    Assert(IS_UPPER_REL(rel));
+
+                    matched = find_expr_pos_in_list(expr, target->exprs);
+                }
+                else
+                {
+                    ListCell    *lc3;
+                    Var        *target_var = NULL;
+
+                    /*
+                     * 'rel' should be a base relation, not upper or join
+                     * relation.
+                     */
+                    Assert(!IS_UPPER_REL(rel));
+                    Assert(rel->relid > 0);
+
+                    /*
+                     * Base relation should use plain Var nodes to reference
+                     * the subquery target. Find the Var in the base relation
+                     * target that points to this expression.
+                     */
+                    foreach(lc3, rel->reltarget->exprs)
+                    {
+                        Var        *var;
+
+                        /*
+                         * If a general expression happens to be there, give
+                         * up because it can break uniqueness of the relation
+                         * output.
+                         */
+                        if (!IsA(lfirst(lc3), Var))
+                            return;
+
+                        var = lfirst_node(Var, lc3);
+
+                        if (var->varno == rel->relid &&
+                            var->varattno == (i + 1))
+                        {
+                            target_var = var;
+                            break;
+                        }
+                    }
+                    if (target_var)
+                    {
+                        List        *opfamilies = lfirst(lc2);
+
+                        matched = find_ec_position_matching_expr(root, rel,
+                                                                 (Expr *) target_var,
+                                                                 opfamilies);
+                        lc2 = lnext(key->opfamily_lists, lc2);
+                    }
+                    else
+                        matched = -1;
+
+                    if (matched >= 0)
+                    {
+                        /*
+                         * By generating the unique key the subquery
+                         * guarantees that the value of the output column
+                         * cannot be NULL.
+                         */
+                        rel->notnullattrs = bms_add_member(rel->notnullattrs,
+                                                           target_var->varattno -
FirstLowInvalidHeapAttributeNumber);
+                    }
+                    else
+                        matched = -1;
+                }
+
+                if (matched >= 0)
+                    item_indexes_new = bms_add_member(item_indexes_new,
+                                                      matched);
+                else
+                {
+                    /* The caller does not want an incomplete unique key. */
+                    bms_free(item_indexes_new);
+                    item_indexes_new = NULL;
+                    break;
+                }
+            }
+        }
+
+        if (item_indexes_new)
+        {
+            UniqueKey    *key_new;
+
+            if (!IS_UPPER_REL(input_rel))
+                Assert(opfamily_lists_new);
+            else
+            {
+                Assert(opfamily_lists_new == NIL);
+
+                opfamily_lists_new = copyObject(key->opfamily_lists);
+            }
+
+
+            key_new = make_uniquekey(item_indexes_new, opfamily_lists_new,
+                                     true);
+            rel->uniquekeys = lappend(rel->uniquekeys, key_new);
+        }
+    }
+}
+
+List *
+create_uniquekeys_for_sortop(SetOperationStmt *topop, List *targetlist)
+{
+    ListCell    *l, *lg;
+    int        i;
+    Bitmapset    *key_idxs = NULL;
+    List    *opfamily_lists = NIL;
+    UniqueKey    *key;
+
+    if (topop->all)
+    {
+        /*
+         * There is no easy way to combine unique keys of the individual
+         * queries.
+         */
+        return NIL;
+    }
+
+    /* Iterate like in query_is_distinct_for() */
+    lg = list_head(topop->groupClauses);
+    i = 0;
+    foreach(l, targetlist)
+    {
+        TargetEntry *tle = (TargetEntry *) lfirst(l);
+        SortGroupClause *sgc;
+        List    *sgc_opfamilies;
+
+        if (tle->resjunk)
+        {
+            i++;
+            continue;    /* ignore resjunk columns */
+        }
+
+        key_idxs = bms_add_member(key_idxs, i++);
+
+        /* non-resjunk columns should have grouping clauses */
+        Assert(lg != NULL);
+        sgc = (SortGroupClause *) lfirst(lg);
+        lg = lnext(topop->groupClauses, lg);
+        sgc_opfamilies = get_mergejoin_opfamilies(sgc->eqop);
+        if (sgc_opfamilies == NIL)
+        {
+            /* XXX Shouldn' this be ERROR? */
+            bms_free(key_idxs);
+            key_idxs = NULL;
+            break;
+        }
+        opfamily_lists = lappend(opfamily_lists, sgc_opfamilies);
+    }
+
+    if (key_idxs == NULL)
+        return NIL;
+
+    key = make_uniquekey(key_idxs, opfamily_lists, true);
+
+    return list_make1(key);
+}
+
+/*
+ * Return a zero-based index of an expression in a list, or -1 if not found.
+ */
+static int
+find_expr_pos_in_list(Expr *expr, List *list)
+{
+    ListCell    *lc;
+    int        idx = 0;
+
+    foreach(lc, list)
+    {
+        Expr    *lexpr = (Expr *) lfirst(lc);
+
+        if (equal(expr, lexpr))
+            return idx;
+
+        idx++;
+    }
+
+    return -1;
+}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 506fccd20c..3029d1a5b0 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -839,6 +839,13 @@ reduce_unique_semijoins(PlannerInfo *root)
 static bool
 rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
 {
+    /*
+     * If uniquekeys could already be setup, the relation definitely supports
+     * distinctness.
+     */
+    if (rel->uniquekeys)
+        return true;
+
     /* We only know about baserels ... */
     if (rel->reloptkind != RELOPT_BASEREL)
         return false;
@@ -899,6 +906,45 @@ static bool
 rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
                     List **extra_clauses)
 {
+    /*
+     * Use unique keys if already available, but do not skip filling of
+     * extra_clauses if caller is interested in it.
+     */
+    if (rel->uniquekeys && extra_clauses == NULL)
+    {
+        Relids        ecs = NULL;
+        ListCell    *l;
+
+        /* First, express the clauses in the form of EC indexes. */
+        foreach(l, clause_list)
+        {
+            RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
+            EquivalenceClass    *ec;
+
+            if (rinfo->outer_is_left)
+                ec = rinfo->right_ec;
+            else
+                ec = rinfo->left_ec;
+
+            /* EC pointers might not have been updated yet. */
+            while (ec->ec_merged)
+                ec = ec->ec_merged;
+
+            ecs = bms_add_member(ecs,
+                                 list_member_ptr_pos(root->eq_classes, ec));
+        }
+
+        /* Now check if a clause exists for each unique key expression. */
+        foreach(l, rel->uniquekeys)
+        {
+            UniqueKey  *ukey = lfirst_node(UniqueKey, l);
+
+            if (bms_is_subset(ukey->item_indexes, ecs) &&
+                !uniquekey_contains_multinulls(root, rel, ukey))
+                return true;
+        }
+    }
+
     /*
      * We could skip a couple of tests here if we assume all callers checked
      * rel_supports_distinctness first, but it doesn't seem worth taking any
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index e40c729e7e..075f98ed16 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1318,6 +1318,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
     RelOptInfo *final_rel;
     FinalPathExtraData extra;
     ListCell   *lc;
+    PathTarget *sort_input_target = NULL;
 
     /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
     if (parse->limitCount || parse->limitOffset)
@@ -1363,6 +1364,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
         /* Also extract the PathTarget form of the setop result tlist */
         final_target = current_rel->cheapest_total_path->pathtarget;
 
+        /*
+         * If in a subquery, the target might be needed by the parent query,
+         * in order to convert unique keys.
+         */
+        root->upper_targets[UPPERREL_FINAL] = final_target;
+
         /* And check whether it's parallel safe */
         final_target_parallel_safe =
             is_parallel_safe(root, (Node *) final_target->exprs);
@@ -1395,7 +1402,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
     else
     {
         /* No set operations, do regular planning */
-        PathTarget *sort_input_target;
         List       *sort_input_targets;
         List       *sort_input_targets_contain_srfs;
         bool        sort_input_target_parallel_safe;
@@ -1645,10 +1651,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
 
         /*
          * Save the various upper-rel PathTargets we just computed into
-         * root->upper_targets[].  The core code doesn't use this, but it
-         * provides a convenient place for extensions to get at the info.  For
-         * consistency, we save all the intermediate targets, even though some
-         * of the corresponding upperrels might not be needed for this query.
+         * root->upper_targets[]. In the core we need it to convert unique
+         * keys of a subquery so the parent query can use them. Besides that
+         * it provides a convenient place for extensions to get at the info.
+         * For consistency, we save all the intermediate targets, even though
+         * some of the corresponding upperrels might not be needed for this
+         * query.
          */
         root->upper_targets[UPPERREL_FINAL] = final_target;
         root->upper_targets[UPPERREL_ORDERED] = final_target;
@@ -1720,6 +1728,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
      */
     if (parse->sortClause)
     {
+        RelOptInfo    *input_rel = current_rel;
+        PathTarget    *input_target;
+
         current_rel = create_ordered_paths(root,
                                            current_rel,
                                            final_target,
@@ -1731,13 +1742,53 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
             adjust_paths_for_srfs(root, current_rel,
                                   final_targets,
                                   final_targets_contain_srfs);
+
+        if (!parse->setOperations)
+            input_target = sort_input_target;
+        else
+            /*
+             * Unlike other upper rels, UPPERREL_SETOP should have the target
+             * initialized properly
+             */
+            input_target = input_rel->reltarget;
+
+        convert_unique_keys_for_rel(root, current_rel, final_target,
+                                    input_rel, input_target);
     }
 
     /*
      * Now we are prepared to build the final-output upperrel.
      */
     final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
-    /* simple_copy_uniquekeys(final_rel, current_rel); */
+
+
+    if (!parse->setOperations)
+    {
+        /*
+         * Make sure unique keys are valid for final_rel.
+         */
+        convert_unique_keys_for_rel(root, final_rel, final_target, current_rel,
+                                    final_target);
+
+    }
+    /*
+     * TODO Consider if this is worth the effort. For set operations other
+     * than UNION ALL, the detection of uniqueness is simple enough to be
+     * handled by query_is_distinct_for(). (That function probably should not
+     * be removed because it can be useful before the unique keys have been
+     * initialized.)
+     */
+    else
+    {
+        SetOperationStmt *topop;
+
+        Assert(IS_UPPER_REL(current_rel));
+
+        /* For set operations, we can create the keys from scratch. */
+        topop = castNode(SetOperationStmt, parse->setOperations);
+        final_rel->uniquekeys = create_uniquekeys_for_sortop(topop,
+                                                             root->parse->targetList);
+    }
 
     /*
      * If the input rel is marked consider_parallel and there's nothing that's
@@ -3680,6 +3731,14 @@ create_grouping_paths(PlannerInfo *root,
     grouped_rel = make_grouping_rel(root, input_rel, target,
                                     target_parallel_safe, parse->havingQual);
 
+    /* Try to initialize unique keys. */
+    if (!root->parse->groupingSets)
+        convert_unique_keys_for_rel(root, grouped_rel, target, input_rel,
+                                    input_rel->reltarget);
+    else
+        /* Grouping sets can break uniqueness. */
+        grouped_rel->uniquekeys = NIL;
+
     /*
      * Create either paths for a degenerate grouping or paths for ordinary
      * grouping, as appropriate.
@@ -4441,6 +4500,10 @@ create_window_paths(PlannerInfo *root,
     /* For now, do all work in the (WINDOW, NULL) upperrel */
     window_rel = fetch_upper_rel(root, UPPERREL_WINDOW, NULL);
 
+    /* Make sure unique keys are valid for window_rel. */
+    convert_unique_keys_for_rel(root, window_rel, output_target, input_rel,
+                                input_target);
+
     /*
      * If the input relation is not parallel-safe, then the window relation
      * can't be parallel-safe, either.  Otherwise, we need to examine the
@@ -4664,9 +4727,14 @@ create_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
     distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
 
     /*
-     * populate_uniquekeys_from_pathkeys(root, distinct_rel,
-     * root->distinct_pathkeys);
+     * Make sure unique keys are valid for distinct_rel.
+     *
+     * Both input and output relation should use the same target in this case,
+     * however the targets are not necessarily assigned to the relations, so
+     * pass them explicitly.
      */
+    convert_unique_keys_for_rel(root, distinct_rel, target, input_rel,
+                                target);
 
     /*
      * We don't compute anything at this level, so distinct_rel will be
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 4e879b0b7c..3b53b82ba1 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1487,13 +1487,33 @@ typedef struct UniqueKey
     pg_node_attr(no_read, no_query_jumble)
 
     NodeTag        type;
-    Bitmapset  *eclass_indexes; /* Indexes in PlannerInfo's eq_class list of
-                                 * ECs that is unique for a RelOptInfo. */
+
+    /*
+     * A subset of columns that is unique across the output rows of the
+     * underlying relation.
+     *
+     * For base relations and joins, the indexes point to equivalence classes
+     * the columns belong to. (Essentially it's a subset of
+     * RelOptInfo.eclass_indexes)
+     *
+     * For upper relations, the indexes point to the items of the relation
+     * target.
+     */
+    Bitmapset  *item_indexes;
+
+    /*
+     * Here we store the operator families for each member of
+     * 'item_indexes'. (i-th item of the list corresponds to i-th member of
+     * 'item_indexes'). This is needed to create ECs in the parent query if
+     * the upper relation represents a subquery.
+     */
+    List    *opfamily_lists;
+
     int            relid;
     bool        use_for_distinct;    /* true if it is used in distinct-pathkey,
                                      * in this case we would never check if we
                                      * should discard it during join search. */
-}            UniqueKey;
+} UniqueKey;
 
 
 /*
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index b3fadd2f05..4b99ce6557 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -82,6 +82,8 @@ extern bool match_index_to_operand(Node *operand, int indexcol,
                                    IndexOptInfo *index);
 extern void check_index_predicates(PlannerInfo *root, RelOptInfo *rel);
 
+extern bool IsBooleanOpfamily(Oid opfamily);
+
 /*
  * tidpath.c
  *      routines to generate tid paths
@@ -138,6 +140,7 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
                                                   Oid collation,
                                                   Index sortref,
                                                   Relids rel,
+                                                  JoinDomain *jdomain,
                                                   bool create_it);
 extern EquivalenceMember *find_ec_member_matching_expr(EquivalenceClass *ec,
                                                        Expr *expr,
@@ -277,4 +280,11 @@ extern void populate_baserel_uniquekeys(PlannerInfo *root,
 extern void populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel,
                                         RelOptInfo *outerrel, RelOptInfo *innerrel,
                                         List *restrictlist, JoinType jointype);
+extern void convert_unique_keys_for_rel(PlannerInfo *root, RelOptInfo *rel,
+                                        PathTarget *target, RelOptInfo *input_rel,
+                                        PathTarget *input_target);
+extern List *create_uniquekeys_for_sortop(SetOperationStmt *topop,
+                                          List *targetlist);
+extern bool uniquekey_contains_multinulls(PlannerInfo *root, RelOptInfo *rel,
+                                          UniqueKey * ukey);
 #endif                            /* PATHS_H */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 675b5b1484..571198a86a 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5648,38 +5648,52 @@ select d.* from d left join (select distinct * from b) s
  Seq Scan on d
 (1 row)
 
--- 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)
+-- when the GROUP BY contains a column that is not in the join condition, join
+-- removal takes place too, due to "unique keys" (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, verbose on)
 select d.* from d left join (select * from b group by b.id, b.c_id) s
   on d.a = s.id;
-                QUERY PLAN                
-------------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Group
-         Group Key: b.id
-         ->  Index Scan using b_pkey on b
-   ->  Sort
-         Sort Key: d.a
-         ->  Seq Scan on d
-(8 rows)
+                   QUERY PLAN                   
+------------------------------------------------
+ Hash Left Join
+   Output: d.a, d.b
+   Inner Unique: true
+   Hash Cond: (d.a = s.id)
+   ->  Seq Scan on pg_temp.d
+         Output: d.a, d.b
+   ->  Hash
+         Output: s.id
+         ->  Subquery Scan on s
+               Output: s.id
+               ->  HashAggregate
+                     Output: b.id, b.c_id
+                     Group Key: b.id
+                     ->  Seq Scan on pg_temp.b
+                           Output: b.id, b.c_id
+(15 rows)
 
 -- similarly, but keying off a DISTINCT clause
-explain (costs off)
+explain (costs off, verbose on)
 select d.* from d left join (select distinct * from b) s
   on d.a = s.id;
-             QUERY PLAN             
-------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Index Scan using b_pkey on b
-   ->  Sort
-         Sort Key: d.a
-         ->  Seq Scan on d
-(6 rows)
+                QUERY PLAN                
+------------------------------------------
+ Hash Left Join
+   Output: d.a, d.b
+   Inner Unique: true
+   Hash Cond: (d.a = s.id)
+   ->  Seq Scan on pg_temp.d
+         Output: d.a, d.b
+   ->  Hash
+         Output: s.id
+         ->  Subquery Scan on s
+               Output: s.id
+               ->  Seq Scan on pg_temp.b
+                     Output: b.id, b.c_id
+(12 rows)
 
 -- join removal is not possible here
 explain (costs off)
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index 9eecdc1e92..b9147e8f1a 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2105,3 +2105,27 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
                                                Filter: (odd = b.odd)
 (16 rows)
 
+-- Check that uniqueness of the view output is recognized.
+begin;
+create table tabx as select * from generate_series(1,100) idx;
+create table taby as select * from generate_series(1,100) idy;
+create unique index on taby using btree (idy);
+create view viewy_barrier with (security_barrier=true) as select * from taby;
+analyze tabx, taby;
+explain (costs off, verbose on)
+select * from tabx x left join viewy_barrier y on idy = idx;
+             QUERY PLAN              
+-------------------------------------
+ Hash Left Join
+   Output: x.idx, taby.idy
+   Inner Unique: true
+   Hash Cond: (x.idx = taby.idy)
+   ->  Seq Scan on public.tabx x
+         Output: x.idx
+   ->  Hash
+         Output: taby.idy
+         ->  Seq Scan on public.taby
+               Output: taby.idy
+(10 rows)
+
+rollback;
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index c4c6c7b8ba..bf8fb27072 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2047,16 +2047,17 @@ explain (costs off)
 select d.* from d left join (select distinct * from b) s
   on d.a = s.id and d.b = s.c_id;
 
--- 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)
+-- when the GROUP BY contains a column that is not in the join condition, join
+-- removal takes place too, due to "unique keys" (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, verbose on)
 select d.* from d left join (select * from b group by b.id, b.c_id) s
   on d.a = s.id;
 
 -- similarly, but keying off a DISTINCT clause
-explain (costs off)
+explain (costs off, verbose on)
 select d.* from d left join (select distinct * from b) s
   on d.a = s.id;
 
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index 75a9b718b2..7b82242221 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -1020,3 +1020,16 @@ WHERE a.thousand < 750;
 explain (costs off)
 SELECT * FROM tenk1 A LEFT JOIN tenk2 B
 ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
+
+
+-- Check that uniqueness of the view output is recognized.
+begin;
+create table tabx as select * from generate_series(1,100) idx;
+create table taby as select * from generate_series(1,100) idy;
+create unique index on taby using btree (idy);
+create view viewy_barrier with (security_barrier=true) as select * from taby;
+analyze tabx, taby;
+explain (costs off, verbose on)
+select * from tabx x left join viewy_barrier y on idy = idx;
+
+rollback;
-- 
2.44.0


Re: UniqueKey v2

From
Andy Fan
Date:
Hello Antonin,

> zhihuifan1213@163.com wrote:
>
>> Here is the v3, ...
>
> I'm trying to enhance the join removal functionality (will post my patch in a
> separate thread soon) and I consider your patch very helpful in this
> area.

Thanks for these words.  The point 2) and 3) is pretty interesting to me
at [1] and "enhance join removal" is another interesting user case. 

> Following is my review. Attached are also some fixes and one enhancement:
> propagation of the unique keys (UK) from a subquery to the parent query
> (0004). (Note that 0001 is just your patch rebased).

Thanks for that! more enhancment like uniquekey in partitioned table is
needed. This post is mainly used to check if more people is still
interested with this. 

> Are you going to submit the patch to the first CF of PG 18?

Since there are still known work to do, I'm not sure if it is OK to
submit in CF. What do you think about this part?

>
> Please let me know if I can contribute to the effort by reviewing or writing
> some code.

Absolutely yes! please feel free to review / writing any of them and do
remember add yourself into the author list if you do that. 

Thanks for your review suggestion, I will get to this very soon if once
I get time, I hope it is in 4 weeks. 

[1]
https://www.postgresql.org/message-id/7mlamswjp81p.fsf%40e18c07352.et15sqa

-- 
Best Regards
Andy Fan




Re: UniqueKey v2

From
Andy Fan
Date:
Hello Antonin,

Thanks for interesting with this topic!

> * I think that, before EC is considered suitable for an UK, its ec_opfamilies
>   field needs to be checked. I try to do that in
>   find_ec_position_matching_expr(), see 0004.

Could you make the reason clearer for adding 'List *opfamily_lists;'
into UniqueKey?  You said "This is needed to create ECs in the parent
query if the upper relation represents a subquery." but I didn't get the
it. Since we need to maintain the UniqueKey in the many places, I'd like
to keep it as simple as possbile. Of course, anything essentical should
be added for sure. 

>
> * Set-returning functions (SRFs) can make a "distinct path" necessary even if
>   the join output is unique.

You are right at this point, I will fix it in the coming version.

>
> * RelOptInfo.notnullattrs
>
>   My understanding is that this field contains the set attributes whose
>   uniqueness is guaranteed by the unique key. They are acceptable because they
>   are either 1) not allowed to be NULL due to NOT NULL constraint or 2) NULL
>   value makes the containing row filtered out, so the row cannot break
>   uniqueness of the output. Am I right?
>
>   If so, I suggest to change the field name to something less generic, maybe
>   'uniquekey_attrs' or 'uniquekey_candidate_attrs', and adding a comment that
>   more checks are needed before particular attribute can actually be used in
>   UniqueKey.

I don't think so, UniqueKey is just one of the places to use this
not-null property, see 3af704098 for the another user case of it. 

(Because of 3af704098, we should leverage notnullattnums somehow in this
patch, which will be included in the next version as well).

> * add_uniquekey_for_uniqueindex()
>
>   I'd appreciate an explanation why the "single-row UK" is created. I think
>   the reason for unique_exprs==NIL is that a restriction clause VAR=CONST
>   exists for each column of the unique index. Whether I'm right or not, a
>   comment should state clearly what the reason is.

You are understanding it correctly. I will add comments in the next
version.

>
> * uniquekey_useful_for_merging()
>
>   How does uniqueness relate to merge join? In README.uniquekey you seem to
>   point out that a single row is always sorted, but I don't think this
>   function is related to that fact. (Instead, I'd expect that pathkeys are
>   added to all paths for a single-row relation, but I'm not sure you do that
>   in the current version of the patch.)

The merging is for "mergejoinable join clauses", see function
eclass_useful_for_merging. Usually I think it as operator "t1.a = t2.a";

> * is_uniquekey_useful_afterjoin()
>
>   Now that my patch (0004) allows propagation of the unique keys from a
>   subquery to the upper query, I was wondering if the UniqueKey structure
>   needs the 'use_for_distinct field' I mean we should now propagate the unique
>   keys to the parent query whether the subquery has DISTINCT clause or not. I
>   noticed that the field is checked by is_uniquekey_useful_afterjoin(), so I
>   changed the function to always returned true. However nothing changed in the
>   output of regression tests (installcheck). Do you insist that the
>   'use_for_distinct' field is needed?
>
>
> * uniquekey_contains_multinulls()
>
>   ** Instead of calling the function when trying to use the UK, how about
>      checking the ECs when considering creation of the UK? If the tests fail,
>      just don't create the UK.

I don't think so since we maintain the UniqueKey from bottom to top, you
can double check if my reason is appropriate.  

CREATE TABLE t1(a int);
CREATE INDEX ON t1(a);

SELECT distinct t1.a FROM t1 JOIN t2 using(a);

We need to create the UniqueKey on the baserel for t1 and the NULL
values is filtered out in the joinrel. so we have to creating it with
allowing NULL values first. 

>   ** What does the 'multi' word in the function name mean?

multi means multiple, I thought we use this short name in the many
places, for ex bt_multi_page_stats after a quick search. 

> * relation_is_distinct_for()
>
>   The function name is too similar to rel_is_distinct_for(). I think the name
>   should indicate that you are checking the relation against a set of
>   pathkeys. Maybe rel_is_distinct_for_pathkeys() (and remove 'distinct' from
>   the argument name)? At the same time, it might be good to rename
>   rel_is_distinct_for() to rel_is_distinct_for_clauses().

OK.

> * uniquekey_contains_in()
>
>   Shouldn't this be uniquekey_contained_in()? And likewise, shouldn't the
>   comment be " ... if UniqueKey is contained in the list of EquivalenceClass"
>   ?

OK.
>
>   (In general, even though I'm not English native speaker, I think I see quite
>   a few grammar issues, which often make reading of the comments/documentation

Your English is really good:)

>
>
> * Combining the UKs
>
>   IMO this is the most problematic part of the patch. You call
>   populate_joinrel_uniquekeys() for the same join multiple times,

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

populate_joinrel_uniquekeys(root, joinrel, rel1, rel2, ...);

so it should be only called once per joinrel.

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

    outeruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, outerrel,
                                                             innerrel, restrictlist);
    inneruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, innerrel,
                                                             outerrel, restrictlist);

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

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

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

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

AND the blow codes:


    if (outeruk_still_valid || inneruk_still_valid)

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


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

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

>   each time
>   with a different 'restrictlist', and you try to do two things at the same
>   time: 1) combine the UKs of the input relations into the UKs of the join
>   relation, 2) check if the join relation can be marked single-row.
>
>   I think that both 1) and 2) should be independent from join order, and thus
>   both computations should only take place once for given set of input
>   relations. And I think they should be done separately:
>
>   1) Compute the join UKs
>
>   As you admit in a comment in populate_joinrel_uniquekeys(), neither join
>   method nor clauses should matter. So I think you only need to pick the
>   "component UKs" (i.e. UKs of the input relations) which are usable above
>   that join (i.e. neither the join itself nor any join below sets any column
>   of the UK to NULL) and combine them.

We need to do this only after the "if (!outeruk_still_valid &&
!inneruk_still_valid)" check, as explained above. 

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

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

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

You are correct and IMO my current code are able to tell it is a single
row as well.

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

I'm interested with "get rid of the dependency on 'restrictlist', I
think you can use ECs.", let's see what we can improve.
>
>   My theory is that relation is single-row if it has an UK such that each of
>   its ECs meets at least one of the following conditions:
>
>   a) contains a constant

True.
>
>   b) contains a column of a relation which has already been proven single-row.

True, not sure if it is easy to tell.

>   b) is referenced by an UK of a relation which has already been proven
>      single-row.

I can't follow here...

>
>   I think that in the example above, an EC {t1.e, t2.id} should exist. So when
>   checking whether 't2' is single-row, the condition b) cam be ised: the UK of
>   't2' should reference the EC {t1.e, t2.id}, which in turn contains the
>   column t1.e. And 't1' is unique because its EC meets the condition a). (Of
>   course you need to check em_jdomain before you use particular EM.)

I think the existing rule 1 for joinrel works well with the singlerow
case naturally, what can be improved if we add the theory you suggested
here? 

-- 
Best Regards
Andy Fan




Re: UniqueKey v2

From
Antonin Houska
Date:
Andy Fan <zhihuifan1213@163.com> wrote:

> > * I think that, before EC is considered suitable for an UK, its ec_opfamilies
> >   field needs to be checked. I try to do that in
> >   find_ec_position_matching_expr(), see 0004.
>
> Could you make the reason clearer for adding 'List *opfamily_lists;'
> into UniqueKey?  You said "This is needed to create ECs in the parent
> query if the upper relation represents a subquery." but I didn't get the
> it. Since we need to maintain the UniqueKey in the many places, I'd like
> to keep it as simple as possbile. Of course, anything essentical should
> be added for sure.

If unique keys are generated for a subquery output, they also need to be
created for the corresponding relation in the upper query ("sub" in the
following example):

select * from tab1 left join (select * from tab2) sub;

However, to create an unique key for "sub", you need an EC for each expression
of the key. And to create an EC, you in turn need the list of operator
families.

Even if the parent query already had ECs for the columns of "sub" which are
contained in the unique key, you need to make sure that those ECs are
"compatible" with the ECs of the subquery which generated the unique key. That
is, if an EC of the subquery considers certain input values equal, the EC of
the parent query must also be able to determine if they are equal or not.

> > * RelOptInfo.notnullattrs
> >
> >   My understanding is that this field contains the set attributes whose
> >   uniqueness is guaranteed by the unique key. They are acceptable because they
> >   are either 1) not allowed to be NULL due to NOT NULL constraint or 2) NULL
> >   value makes the containing row filtered out, so the row cannot break
> >   uniqueness of the output. Am I right?
> >
> >   If so, I suggest to change the field name to something less generic, maybe
> >   'uniquekey_attrs' or 'uniquekey_candidate_attrs', and adding a comment that
> >   more checks are needed before particular attribute can actually be used in
> >   UniqueKey.
>
> I don't think so, UniqueKey is just one of the places to use this
> not-null property, see 3af704098 for the another user case of it.
>
> (Because of 3af704098, we should leverage notnullattnums somehow in this
> patch, which will be included in the next version as well).

In your patch you modify 'notnullattrs' in add_base_clause_to_rel(), but that
does not happen to 'notnullattnums' in the current master branch. Thus I think
that 'notnullattrs' is specific to the unique keys feature, so the field name
should be less generic.

> >
> > * uniquekey_useful_for_merging()
> >
> >   How does uniqueness relate to merge join? In README.uniquekey you seem to
> >   point out that a single row is always sorted, but I don't think this
> >   function is related to that fact. (Instead, I'd expect that pathkeys are
> >   added to all paths for a single-row relation, but I'm not sure you do that
> >   in the current version of the patch.)
>
> The merging is for "mergejoinable join clauses", see function
> eclass_useful_for_merging. Usually I think it as operator "t1.a = t2.a";

My question is: why is the uniqueness important specifically to merge join? I
understand that join evaluation can be more efficient if we know that one
input relation is unique (i.e. we only scan that relation until we find the
first match), but this is not specific to merge join.

> > * is_uniquekey_useful_afterjoin()
> >
> >   Now that my patch (0004) allows propagation of the unique keys from a
> >   subquery to the upper query, I was wondering if the UniqueKey structure
> >   needs the 'use_for_distinct field' I mean we should now propagate the unique
> >   keys to the parent query whether the subquery has DISTINCT clause or not. I
> >   noticed that the field is checked by is_uniquekey_useful_afterjoin(), so I
> >   changed the function to always returned true. However nothing changed in the
> >   output of regression tests (installcheck). Do you insist that the
> >   'use_for_distinct' field is needed?

I miss your answer to this comment.

> > * uniquekey_contains_multinulls()
> >
> >   ** Instead of calling the function when trying to use the UK, how about
> >      checking the ECs when considering creation of the UK? If the tests fail,
> >      just don't create the UK.
>
> I don't think so since we maintain the UniqueKey from bottom to top, you
> can double check if my reason is appropriate.
>
> CREATE TABLE t1(a int);
> CREATE INDEX ON t1(a);
>
> SELECT distinct t1.a FROM t1 JOIN t2 using(a);
>
> We need to create the UniqueKey on the baserel for t1 and the NULL
> values is filtered out in the joinrel. so we have to creating it with
> allowing NULL values first.

ok

> >   ** What does the 'multi' word in the function name mean?
>
> multi means multiple, I thought we use this short name in the many
> places, for ex bt_multi_page_stats after a quick search.

Why not simply uniquekey_contains_nulls() ?

Actually I wouldn't say that an instance of UniqueKey contains any value (NULL
or NOT NULL) because it describes the whole relation rather than particular
row. I consider UniqueKey to be a set of expressions. How about
uniquekey_expression_nullable() ?

> >
> >
> > * Combining the UKs
> >
> >   IMO this is the most problematic part of the patch. You call
> >   populate_joinrel_uniquekeys() for the same join multiple times,
>
> Why do you think so? The below code is called in "make_join_rel"

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

I need to check this part more in detail.

> Is your original question is about populate_joinrel_uniquekey_for_rel
> rather than populate_joinrel_uniquekeys? We have the below codes:
>
>     outeruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, outerrel,
>                                                              innerrel, restrictlist);
>     inneruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, innerrel,
>                                                              outerrel, restrictlist);
>
> This is mainly because of the following theory. Quoted from
> README.uniquekey. Let's called this as "rule 1".
>
> """
> How to maintain the uniquekey?
> -------------------------------
> .. From the join relation, it is maintained with two rules:
>
> - the uniquekey in one side is still unique if it can't be duplicated
>   after the join. for example:
>
>   SELECT t1.pk FROM t1 JOIN t2 ON t1.a = t2.pk;
>   UniqueKey on t1:  t1.pk
>   UniqueKey on t1 Join t2:  t1.pk
> """
>
> AND the blow codes:
>
>
>     if (outeruk_still_valid || inneruk_still_valid)
>
>         /*
>          * the uniquekey on outers or inners have been added into joinrel so
>          * the combined uniuqekey from both sides is not needed.
>          */
>         return;
>
>
> We don't create the component uniquekey if any one side of the boths
> sides is unique already. For example:
>
> "(t1.id) in joinrel(t1, t2) is unique" OR "(t2.id) in joinrel is
> unique", there is no need to create component UniqueKey (t1.id, t2.id);

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

> >
> >   Of course one problem is that the number of combinations can grow
> >   exponentially as new relations are joined.
>
> Yes, that's why "rule 1" needed and "How to reduce the overhead" in
> UniqueKey.README is introduced.

What if we are interested in unique keys of a subquery, but the subquery has
no DISTINCT clause?

> >
> >   2) Check if the join relation is single-row
> >
> >   I in order to get rid of the dependency on 'restrictlist', I think you can
> >   use ECs. Consider a query from your regression tests:
> >
> > CREATE TABLE uk_t (id int primary key, a int not null, b int not null, c int, d int, e int);
> >
> > SELECT distinct t1.d FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id and t1.id = 1;
> >
> >   The idea here seems to be that no more than one row of t1 matches the query
> >   clauses. Therefore, if t2(id) is unique, the clause t1.e=t2.id ensures that
> >   no more than one row of t2 matches the query (because t1 cannot provide the
> >   clause with more than one input value of 'e'). And therefore, the join also
> >   produces at most one row.
>
> You are correct and IMO my current code are able to tell it is a single
> row as well.
>
> 1. Since t1.id = 1, so t1 is single row, so t1.d is unqiuekey as a
> consequence.
> 2. Given t2.id is unique, t1.e = t2.id so t1's unqiuekey can be kept
> after the join because of rule 1 on joinrel. and t1 is singlerow, so the
> joinrel is singlerow as well.
>
> I'm interested with "get rid of the dependency on 'restrictlist', I
> think you can use ECs.", let's see what we can improve.
> >
> >   My theory is that relation is single-row if it has an UK such that each of
> >   its ECs meets at least one of the following conditions:
> >
> >   a) contains a constant
>
> True.
> >
> >   b) contains a column of a relation which has already been proven single-row.
>
> True, not sure if it is easy to tell.
>
> >   b) is referenced by an UK of a relation which has already been proven
> >      single-row.
>
> I can't follow here...

This is similar to EC containing a constant: if an EC is used by a single-row
UK, all its member can only have a single value.

> >
> >   I think that in the example above, an EC {t1.e, t2.id} should exist. So when
> >   checking whether 't2' is single-row, the condition b) cam be used: the UK of
> >   't2' should reference the EC {t1.e, t2.id}, which in turn contains the
> >   column t1.e. And 't1' is unique because its EC meets the condition a). (Of
> >   course you need to check em_jdomain before you use particular EM.)
>
> I think the existing rule 1 for joinrel works well with the singlerow
> case naturally, what can be improved if we add the theory you suggested
> here?

This is still the explanation of the idea how to mark join unique key as a
single-row separately from the other logic. As noted above, I need to learn
more about the unique keys of a join.

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



Re: UniqueKey v2

From
Antonin Houska
Date:
Antonin Houska <ah@cybertec.at> wrote:

> Andy Fan <zhihuifan1213@163.com> wrote:
> > >
> > > * Combining the UKs
> > >
> > >   IMO this is the most problematic part of the patch. You call
> > >   populate_joinrel_uniquekeys() for the same join multiple times,
> >
> > Why do you think so? The below code is called in "make_join_rel"
>
> Consider join of tables "a", "b" and "c". My understanding is that
> make_join_rel() is called once with rel1={a} and rel2={b join c}, then with
> rel1={a join b} and rel2={c}, etc. I wanted to say that each call should
> produce the same set of unique keys.
>
> I need to check this part more in detail.

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

A JOIN (B JOIN C)

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

B JOIN (A JOIN C)

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

> > Is your original question is about populate_joinrel_uniquekey_for_rel
> > rather than populate_joinrel_uniquekeys? We have the below codes:
> >
> >     outeruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, outerrel,
> >                                                              innerrel, restrictlist);
> >     inneruk_still_valid = populate_joinrel_uniquekey_for_rel(root, joinrel, innerrel,
> >                                                              outerrel, restrictlist);
> >
> > This is mainly because of the following theory. Quoted from
> > README.uniquekey. Let's called this as "rule 1".
> >
> > """
> > How to maintain the uniquekey?
> > -------------------------------
> > .. From the join relation, it is maintained with two rules:
> >
> > - the uniquekey in one side is still unique if it can't be duplicated
> >   after the join. for example:
> >
> >   SELECT t1.pk FROM t1 JOIN t2 ON t1.a = t2.pk;
> >   UniqueKey on t1:  t1.pk
> >   UniqueKey on t1 Join t2:  t1.pk
> > """
> >
> > AND the blow codes:
> >
> >
> >     if (outeruk_still_valid || inneruk_still_valid)
> >
> >         /*
> >          * the uniquekey on outers or inners have been added into joinrel so
> >          * the combined uniuqekey from both sides is not needed.
> >          */
> >         return;
> >
> >
> > We don't create the component uniquekey if any one side of the boths
> > sides is unique already. For example:
> >
> > "(t1.id) in joinrel(t1, t2) is unique" OR "(t2.id) in joinrel is
> > unique", there is no need to create component UniqueKey (t1.id, t2.id);
>
> ok, I need to check more in detail how this part works.

This optimization makes sense to me.

> > >
> > >   Of course one problem is that the number of combinations can grow
> > >   exponentially as new relations are joined.
> >
> > Yes, that's why "rule 1" needed and "How to reduce the overhead" in
> > UniqueKey.README is introduced.

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

> > >
> > >   2) Check if the join relation is single-row
> > >
> > >   I in order to get rid of the dependency on 'restrictlist', I think you can
> > >   use ECs. Consider a query from your regression tests:
> > >
> > > CREATE TABLE uk_t (id int primary key, a int not null, b int not null, c int, d int, e int);
> > >
> > > SELECT distinct t1.d FROM uk_t t1 JOIN uk_t t2 ON t1.e = t2.id and t1.id = 1;
> > >
> > >   The idea here seems to be that no more than one row of t1 matches the query
> > >   clauses. Therefore, if t2(id) is unique, the clause t1.e=t2.id ensures that
> > >   no more than one row of t2 matches the query (because t1 cannot provide the
> > >   clause with more than one input value of 'e'). And therefore, the join also
> > >   produces at most one row.
> >
> > You are correct and IMO my current code are able to tell it is a single
> > row as well.
> >
> > 1. Since t1.id = 1, so t1 is single row, so t1.d is unqiuekey as a
> > consequence.
> > 2. Given t2.id is unique, t1.e = t2.id so t1's unqiuekey can be kept
> > after the join because of rule 1 on joinrel. and t1 is singlerow, so the
> > joinrel is singlerow as well.

ok, I think I understand now.

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



Re: UniqueKey v2

From
Andy Fan
Date:
Antonin Houska <ah@cybertec.at> writes:

>> Could you make the reason clearer for adding 'List *opfamily_lists;'
>> into UniqueKey?  You said "This is needed to create ECs in the parent
>> query if the upper relation represents a subquery." but I didn't get the
>> it. Since we need to maintain the UniqueKey in the many places, I'd like
>> to keep it as simple as possbile. Of course, anything essentical should
>> be added for sure. 
>
> If unique keys are generated for a subquery output, they also need to be
> created for the corresponding relation in the upper query ("sub" in the
> following example):

OK.
>
> select * from tab1 left join (select * from tab2) sub;
>
> However, to create an unique key for "sub", you need an EC for each expression
> of the key.

OK.
> And to create an EC, you in turn need the list of operator
> families.

I'm thinking if we need to "create" any EC. Can you find out a user case
where the outer EC is missed and the UniqueKey is still interesting? I
don't have an example now.  

convert_subquery_pathkeys has a similar sistuation and has the following
codes:

                outer_ec =
                    get_eclass_for_sort_expr(root,
                                             (Expr *) outer_var,
                                             sub_eclass->ec_opfamilies,
                                             sub_member->em_datatype,
                                             sub_eclass->ec_collation,
                                             0,
                                             rel->relids,
                                             NULL,
                                             false);

                /*
                 * If we don't find a matching EC, sub-pathkey isn't
                 * interesting to the outer query
                 */
                if (outer_ec)
                    best_pathkey =
                        make_canonical_pathkey(root,
                                               outer_ec,
                                               sub_pathkey->pk_opfamily,
                                               sub_pathkey->pk_strategy,
                                               sub_pathkey->pk_nulls_first);
            }

> Even if the parent query already had ECs for the columns of "sub" which are
> contained in the unique key, you need to make sure that those ECs are
> "compatible" with the ECs of the subquery which generated the unique key. That
> is, if an EC of the subquery considers certain input values equal, the EC of
> the parent query must also be able to determine if they are equal or not.
>
>> > * RelOptInfo.notnullattrs
>> >
>> >   My understanding is that this field contains the set attributes whose
>> >   uniqueness is guaranteed by the unique key. They are acceptable because they
>> >   are either 1) not allowed to be NULL due to NOT NULL constraint or 2) NULL
>> >   value makes the containing row filtered out, so the row cannot break
>> >   uniqueness of the output. Am I right?
>> >
>> >   If so, I suggest to change the field name to something less generic, maybe
>> >   'uniquekey_attrs' or 'uniquekey_candidate_attrs', and adding a comment that
>> >   more checks are needed before particular attribute can actually be used in
>> >   UniqueKey.
>> 
>> I don't think so, UniqueKey is just one of the places to use this
>> not-null property, see 3af704098 for the another user case of it. 
>> 
>> (Because of 3af704098, we should leverage notnullattnums somehow in this
>> patch, which will be included in the next version as well).
>
> In your patch you modify 'notnullattrs' in add_base_clause_to_rel(), but that
> does not happen to 'notnullattnums' in the current master branch. Thus I think
> that 'notnullattrs' is specific to the unique keys feature, so the field name
> should be less generic.

OK.

>> >
>> > * uniquekey_useful_for_merging()
>> >
>> >   How does uniqueness relate to merge join? In README.uniquekey you seem to
>> >   point out that a single row is always sorted, but I don't think this
>> >   function is related to that fact. (Instead, I'd expect that pathkeys are
>> >   added to all paths for a single-row relation, but I'm not sure you do that
>> >   in the current version of the patch.)
>> 
>> The merging is for "mergejoinable join clauses", see function
>> eclass_useful_for_merging. Usually I think it as operator "t1.a = t2.a";
>
> My question is: why is the uniqueness important specifically to merge join? I
> understand that join evaluation can be more efficient if we know that one
> input relation is unique (i.e. we only scan that relation until we find the
> first match), but this is not specific to merge join.

So the answer is the "merging" in uniquekey_useful_for_merging() has
nothing with merge join. 

>> > * is_uniquekey_useful_afterjoin()
>> >
>> >   Now that my patch (0004) allows propagation of the unique keys from a
>> >   subquery to the upper query, I was wondering if the UniqueKey structure
>> >   needs the 'use_for_distinct field' I mean we should now propagate the unique
>> >   keys to the parent query whether the subquery has DISTINCT clause or not. I
>> >   noticed that the field is checked by is_uniquekey_useful_afterjoin(), so I
>> >   changed the function to always returned true. However nothing changed in the
>> >   output of regression tests (installcheck). Do you insist that the
>> >   'use_for_distinct' field is needed?
>
> I miss your answer to this comment.

After we considers the uniquekey from subquery, 'use_for_distinct' field
is not needed.

>> >   ** What does the 'multi' word in the function name mean?
>> 
>> multi means multiple, I thought we use this short name in the many
>> places, for ex bt_multi_page_stats after a quick search. 
>
> Why not simply uniquekey_contains_nulls() ?

> Actually I wouldn't say that an instance of UniqueKey contains any value (NULL
> or NOT NULL) because it describes the whole relation rather than particular
> row. I consider UniqueKey to be a set of expressions. How about
> uniquekey_expression_nullable() ?

uniquekey_expression_nullable() is a better name, I will use it in the
next version.

IIUC, we have reached to the agreement based on your latest response for
the most of the questions. Please point me if I missed anything.  

>> >   Of course one problem is that the number of combinations can grow
>> >   exponentially as new relations are joined.
>> 
>> Yes, that's why "rule 1" needed and "How to reduce the overhead" in
>> UniqueKey.README is introduced. 
>
> What if we are interested in unique keys of a subquery, but the subquery has
> no DISTINCT clause?

I agree we should remove the prerequisite of "use_for_distinct". 

-- 
Best Regards
Andy Fan




Re: UniqueKey v2

From
Andy Fan
Date:
>> Consider join of tables "a", "b" and "c". My understanding is that
>> make_join_rel() is called once with rel1={a} and rel2={b join c}, then with
>> rel1={a join b} and rel2={c}, etc. I wanted to say that each call should
>> produce the same set of unique keys.
>> 
>> I need to check this part more in detail.
>
> I think I understand now. By calling populate_joinrel_uniquekeys() for various
> orderings, you can find out that various input relation unique keys can
> represent the whole join. For example, if the ordering is
>
> A JOIN (B JOIN C)
>
> you can prove that the unique keys of A can be used for the whole join, while
> for the ordering
>
> B JOIN (A JOIN C)
>
> you can prove the same for the unique keys of B, and so on.

Yes.

>> > We don't create the component uniquekey if any one side of the boths
>> > sides is unique already. For example:
>> > 
>> > "(t1.id) in joinrel(t1, t2) is unique" OR "(t2.id) in joinrel is
>> > unique", there is no need to create component UniqueKey (t1.id, t2.id);  
>> 
>> ok, I need to check more in detail how this part works.
>
> This optimization makes sense to me.

OK.

>> > >
>> > >   Of course one problem is that the number of combinations can grow
>> > >   exponentially as new relations are joined.
>> > 
>> > Yes, that's why "rule 1" needed and "How to reduce the overhead" in
>> > UniqueKey.README is introduced. 
>
> I think there should yet be some guarantee that the number of unique keys does
> not grow exponentially. Perhaps a constant that allows a relation (base or
> join) to have at most N unique keys. (I imagine N to be rather small, e.g. 3
> or 4.) And when picking the "best N keys", one criterion could be the number
> of expressions in the key (the shorter key the better).

I don't want to introduce this complextity right now. I'm more
inerested with how to work with them effectivity. main effort includes: 

- the design of bitmapset which is memory usage friendly and easy for
combinations.
- Optimize the singlerow cases to reduce N UnqiueKeys to 1 UniqueKey.

I hope we can pay more attention to this optimization (at most N
UniqueKeys) when the major inforastruce has been done. 

>> > You are correct and IMO my current code are able to tell it is a single
>> > row as well.
>> > 
>> > 1. Since t1.id = 1, so t1 is single row, so t1.d is unqiuekey as a
>> > consequence.
>> > 2. Given t2.id is unique, t1.e = t2.id so t1's unqiuekey can be kept
>> > after the join because of rule 1 on joinrel. and t1 is singlerow, so the
>> > joinrel is singlerow as well.
>
> ok, I think I understand now.

OK.

At last, this probably is my first non-trival patchs which has multiple
authors, I don't want myself is the bottleneck for the coorperation, so
if you need something to do done sooner, please don't hesitate to ask me
for it explicitly.

Here is my schedule about this. I can provide the next version based
our discussion and your patches at the eariler of next week. and update
the UniqueKey.README to make sure the overall design clearer. What I
hope you to pay more attention is the UniqueKey.README besides the
code. I hope the UniqueKey.README can reduce the effort for others to
understand the overall design enormously.

-- 
Best Regards
Andy Fan




Re: UniqueKey v2

From
Antonin Houska
Date:
Andy Fan <zhihuifan1213@163.com> wrote:
> Antonin Houska <ah@cybertec.at> writes:
>
> >> Could you make the reason clearer for adding 'List *opfamily_lists;'
> >> into UniqueKey?  You said "This is needed to create ECs in the parent
> >> query if the upper relation represents a subquery." but I didn't get the
> >> it. Since we need to maintain the UniqueKey in the many places, I'd like
> >> to keep it as simple as possbile. Of course, anything essentical should
> >> be added for sure.
> >
> > If unique keys are generated for a subquery output, they also need to be
> > created for the corresponding relation in the upper query ("sub" in the
> > following example):
>
> OK.
> >
> > select * from tab1 left join (select * from tab2) sub;
> >
> > However, to create an unique key for "sub", you need an EC for each expression
> > of the key.
>
> OK.
> > And to create an EC, you in turn need the list of operator
> > families.
>
> I'm thinking if we need to "create" any EC. Can you find out a user case
> where the outer EC is missed and the UniqueKey is still interesting? I
> don't have an example now.
>
> convert_subquery_pathkeys has a similar sistuation and has the following
> codes:
>
>                 outer_ec =
>                     get_eclass_for_sort_expr(root,
>                                              (Expr *) outer_var,
>                                              sub_eclass->ec_opfamilies,
>                                              sub_member->em_datatype,
>                                              sub_eclass->ec_collation,
>                                              0,
>                                              rel->relids,
>                                              NULL,
>                                              false);
>
>                 /*
>                  * If we don't find a matching EC, sub-pathkey isn't
>                  * interesting to the outer query
>                  */
>                 if (outer_ec)
>                     best_pathkey =
>                         make_canonical_pathkey(root,
>                                                outer_ec,
>                                                sub_pathkey->pk_opfamily,
>                                                sub_pathkey->pk_strategy,
>                                                sub_pathkey->pk_nulls_first);
>             }

I think that convert_subquery_pathkeys() just does not try that hard to
achieve its goal.

The example where it's important to create the EC in the outer query is what I
added to the subselect.sql regression test in the 0004- diff in [1]:

create table tabx as select * from generate_series(1,100) idx;
create table taby as select * from generate_series(1,100) idy;
create unique index on taby using btree (idy);
create view view_barrier with (security_barrier=true) as select * from taby;
analyze tabx, taby;
explain (costs off, verbose on) select * from tabx x left join view_barrier y on idy = idx;

If you modify find_ec_position_matching_expr() to return -1 instead of
creating the EC, you will get this plan

Hash Left Join
   Output: x.idx, taby.idy
   Hash Cond: (x.idx = taby.idy)
   ->  Seq Scan on public.tabx x
         Output: x.idx
   ->  Hash
         Output: taby.idy
         ->  Seq Scan on public.taby
               Output: taby.idy

instead of this

Hash Left Join
   Output: x.idx, taby.idy
   Inner Unique: true
   Hash Cond: (x.idx = taby.idy)
   ->  Seq Scan on public.tabx x
         Output: x.idx
   ->  Hash
         Output: taby.idy
         ->  Seq Scan on public.taby
               Output: taby.idy

> >> > * uniquekey_useful_for_merging()
> >> >
> >> >   How does uniqueness relate to merge join? In README.uniquekey you seem to
> >> >   point out that a single row is always sorted, but I don't think this
> >> >   function is related to that fact. (Instead, I'd expect that pathkeys are
> >> >   added to all paths for a single-row relation, but I'm not sure you do that
> >> >   in the current version of the patch.)
> >>
> >> The merging is for "mergejoinable join clauses", see function
> >> eclass_useful_for_merging. Usually I think it as operator "t1.a = t2.a";
> >
> > My question is: why is the uniqueness important specifically to merge join? I
> > understand that join evaluation can be more efficient if we know that one
> > input relation is unique (i.e. we only scan that relation until we find the
> > first match), but this is not specific to merge join.
>
> So the answer is the "merging" in uniquekey_useful_for_merging() has
> nothing with merge join.

I don't understand. The function comment does mention merge join:

/*
 * uniquekey_useful_for_merging
 *    Check if the uniquekey is useful for mergejoins above the given relation.
 *
 * similar with pathkeys_useful_for_merging.
 */
static bool
uniquekey_useful_for_merging(PlannerInfo *root, UniqueKey * ukey, RelOptInfo *rel)


[1] https://www.postgresql.org/message-id/7971.1713526758%40antos

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