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

From 32c220b1a12b3c622553ed0fc93f8556619e020f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Fri, 31 Jan 2020 19:38:05 +0800
Subject: [PATCH] Erase the distinctClause if the result is unique by
 definition

For a single relation, we can tell it by any one of the following
is true:
1. The pk is in the target list.
2. The uk is in the target list and the columns is not null
3. The columns in group-by clause is also in the target list

for relation join, we can tell it by:
if every relation in the jointree yield a unique result set,then
the final result is unique as well regardless the join method.
for semi/anti join, we will ignore the righttable.
---
 src/backend/nodes/bitmapset.c                 |  40 +++
 src/backend/optimizer/path/costsize.c         |   1 +
 src/backend/optimizer/plan/planner.c          | 292 ++++++++++++++++++
 src/backend/utils/cache/relcache.c            |  23 ++
 src/backend/utils/misc/guc.c                  |  10 +
 src/include/nodes/bitmapset.h                 |   2 +
 src/include/optimizer/cost.h                  |   1 +
 src/include/utils/rel.h                       |   3 +
 src/test/regress/expected/join.out            |  16 +-
 .../regress/expected/select_distinct_2.out    | 141 +++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/sql/select_distinct_2.sql    |  42 +++
 12 files changed, 565 insertions(+), 9 deletions(-)
 create mode 100644 src/test/regress/expected/select_distinct_2.out
 create mode 100644 src/test/regress/sql/select_distinct_2.sql

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 648cc1a7eb..76ce9b526e 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1167,3 +1167,43 @@ bms_hash_value(const Bitmapset *a)
 	return DatumGetUInt32(hash_any((const unsigned char *) a->words,
 								   (lastword + 1) * sizeof(bitmapword)));
 }
+
+/*
+ * bms_array_copy --
+ *
+ * copy the bms data in the newly palloc memory
+ */
+
+Bitmapset**
+bms_array_copy(Bitmapset **bms_array, int len)
+{
+	Bitmapset **res;
+	int i;
+	if (bms_array == NULL || len < 1)
+		return NULL;
+
+	res = palloc(sizeof(Bitmapset*) * len);
+	for(i = 0; i < len; i++)
+	{
+		res[i] = bms_copy(bms_array[i]);
+	}
+	return res;
+}
+
+/*
+ * bms_array_free
+ *
+ * free the element in the array one by one, free the array as well at last
+ */
+void
+bms_array_free(Bitmapset **bms_array,  int len)
+{
+	int idx;
+	if (bms_array == NULL)
+		return;
+	for(idx = 0 ; idx < len; idx++)
+	{
+		bms_free(bms_array[idx]);
+	}
+	pfree(bms_array);
+}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index b5a0033721..dde16b5d44 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -138,6 +138,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_distinct_elimination = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..6f7d85f96e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -22,8 +22,10 @@
 #include "access/htup_details.h"
 #include "access/parallel.h"
 #include "access/sysattr.h"
+#include "access/relation.h"
 #include "access/table.h"
 #include "access/xact.h"
+#include "catalog/index.h"
 #include "catalog/pg_constraint.h"
 #include "catalog/pg_inherits.h"
 #include "catalog/pg_proc.h"
@@ -35,6 +37,7 @@
 #include "lib/bipartite_match.h"
 #include "lib/knapsack.h"
 #include "miscadmin.h"
+#include "nodes/bitmapset.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #ifdef OPTIMIZER_DEBUG
@@ -248,6 +251,7 @@ static bool group_by_has_partkey(RelOptInfo *input_rel,
 								 List *targetList,
 								 List *groupClause);
 static int	common_prefix_cmp(const void *a, const void *b);
+static void	preprocess_distinct_node(PlannerInfo *root);
 
 
 /*****************************************************************************
@@ -989,6 +993,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	/* Remove any redundant GROUP BY columns */
 	remove_useless_groupby_columns(root);
 
+	if (enable_distinct_elimination)
+		preprocess_distinct_node(root);
+
 	/*
 	 * If we have any outer joins, try to reduce them to plain inner joins.
 	 * This step is most easily done after we've done expression
@@ -7409,3 +7416,288 @@ group_by_has_partkey(RelOptInfo *input_rel,
 
 	return true;
 }
+
+/*
+ * is_unique_result_already
+ *
+ * Given a relation, we can know its primary key + unique key information
+ * unique target is the target list of distinct/distinct on target.
+ * not_null_columns is a union of not null columns based on catalog and quals.
+ * then we can know the result is unique already before executing it if
+ * the primary key or uk + not null in target list.
+ */
+static bool
+is_unique_result_already(Relation relation,
+						 Bitmapset *unique_target,
+						 Bitmapset *not_null_columns)
+{
+	int i;
+	Bitmapset *pkattr = RelationGetIndexAttrBitmap(relation,
+												   INDEX_ATTR_BITMAP_PRIMARY_KEY);
+
+	/*
+	 * if the pk is in the target list,
+	 * the result set is unique for this relation
+	 */
+	if (pkattr != NULL &&
+		!bms_is_empty(pkattr) &&
+		bms_is_subset(pkattr, unique_target))
+	{
+		return true;
+	}
+
+	/*
+	 * check if the pk is in the unique index
+	 */
+	for (i = 0; i < relation->rd_plain_ukcount; i++)
+	{
+		Bitmapset *ukattr = relation->rd_plain_ukattrs[i];
+		if (!bms_is_empty(ukattr)
+			&& bms_is_subset(ukattr, unique_target)
+			&& bms_is_subset(ukattr, not_null_columns))
+			return true;
+	}
+
+	/*
+	 * If a unique index is in the target list, and the columns are not null
+	 * the result set is unique as well
+	 */
+
+	return false;
+}
+
+
+/*
+ * scan_non_semi_anti_relids
+ *
+ * scan jointree to get non-semi/anti join rtindex.
+ */
+static void
+scan_non_semi_anti_relids(Node* jtnode, Relids* relids)
+{
+	if (jtnode == NULL)
+		return;
+
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*relids = bms_add_member(*relids, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			scan_non_semi_anti_relids(lfirst(l), relids);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		scan_non_semi_anti_relids(j->larg, relids);
+		if (j->jointype != JOIN_SEMI && j->jointype != JOIN_ANTI)
+		{
+			scan_non_semi_anti_relids(j->rarg, relids);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+
+}
+
+/*
+ * preprocess_distinct_node
+ *
+ * remove the distinctClause if it is not necessary by definition
+ */
+static void
+preprocess_distinct_node(PlannerInfo *root)
+{
+	Query *query = root->parse;
+	ListCell *lc;
+	int num_of_rtables;
+	Bitmapset **targetlist_by_table = NULL;
+    Bitmapset **notnullcolumns = NULL;
+	Index rel_idx = 0;
+	bool should_distinct_elimination = false;
+	Relids non_semi_anti_relids = NULL;
+
+	if (query->distinctClause == NIL)
+		return;
+
+	scan_non_semi_anti_relids((Node*)query->jointree, &non_semi_anti_relids);
+
+	foreach(lc, query->rtable)
+	{
+		RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
+		rel_idx++;
+		if (!bms_is_member(rel_idx, non_semi_anti_relids))
+			continue;
+		/* we only handle the basic Relation for now */
+		if (rte->rtekind != RTE_RELATION)
+			return;
+	}
+
+	num_of_rtables = bms_num_members(non_semi_anti_relids);
+
+	/*
+	 * If the columns in group clause is in the target list
+	 * we don't need distinct
+	 */
+	if (query->groupClause != NIL)
+	{
+		Bitmapset *groupclause_bm = NULL;
+		Bitmapset *groupclause_in_targetlist_bm = NULL;
+		ListCell *lc;
+		foreach(lc, query->groupClause)
+			groupclause_bm = bms_add_member(groupclause_bm,
+												lfirst_node(SortGroupClause, lc)->tleSortGroupRef);
+
+		foreach(lc, query->targetList)
+		{
+			TargetEntry *te = lfirst_node(TargetEntry, lc);
+			if (te->resjunk)
+				continue;
+			groupclause_in_targetlist_bm = bms_add_member(groupclause_in_targetlist_bm,
+														  te->ressortgroupref);
+		}
+
+		should_distinct_elimination = bms_is_subset(groupclause_bm,
+													groupclause_in_targetlist_bm);
+		bms_free(groupclause_bm);
+		bms_free(groupclause_in_targetlist_bm);
+		if (should_distinct_elimination)
+			goto ret;
+	}
+
+	targetlist_by_table = palloc0(sizeof(Bitmapset*) * num_of_rtables);
+	notnullcolumns = palloc0(sizeof(Bitmapset* ) * num_of_rtables);
+
+	/* build the targetlist_by_table */
+	foreach(lc, query->targetList)
+	{
+		TargetEntry *te = lfirst_node(TargetEntry, lc);
+		Expr *expr = te->expr;
+		Var *var;
+		Bitmapset **target_column_per_rel;
+		int target_attno;
+
+		if (!IsA(expr, Var))
+			continue;
+
+		var = (Var *)(expr);
+		if (var->varlevelsup != 0)
+			continue;
+
+		target_column_per_rel = &targetlist_by_table[var->varno - 1];
+		target_attno = var->varattno - FirstLowInvalidHeapAttributeNumber;
+
+		/*
+		 * for distinct On (..), we only count the field in .. rather than
+		 * all the entries in target list
+		 */
+		if (query->hasDistinctOn)
+		{
+			Index ref = te->ressortgroupref;
+			ListCell *lc;
+
+			/*
+			 * A fastpath to know if the targetEntry is in the distinctClause
+			 */
+			if (ref == 0)
+				continue;
+
+			/*
+			 * Even the ref is not zero, it may be in sort as well, so we
+			 * need dobule check.
+			 */
+			foreach(lc, query->distinctClause)
+			{
+				if (ref == lfirst_node(SortGroupClause, lc)->tleSortGroupRef)
+					*target_column_per_rel = bms_add_member(*target_column_per_rel,
+															target_attno);
+			}
+		}
+		else
+			*target_column_per_rel = bms_add_member(*target_column_per_rel,
+													target_attno);
+	}
+
+	/* find out nonnull columns from qual via find_nonnullable_vars */
+	foreach(lc, find_nonnullable_vars(query->jointree->quals))
+	{
+		Var *not_null_var;
+		Bitmapset **notnullcolumns_per_rel;
+		int notnull_attno;
+		if (!IsA(lfirst(lc), Var))
+			continue;
+		not_null_var = lfirst_node(Var, lc);
+		if (not_null_var->varno == INNER_VAR ||
+			not_null_var->varno == OUTER_VAR ||
+			not_null_var->varno == INDEX_VAR)
+			continue;
+		notnullcolumns_per_rel = &notnullcolumns[not_null_var->varno - 1];
+		notnull_attno = not_null_var->varattno - FirstLowInvalidHeapAttributeNumber;
+		*notnullcolumns_per_rel = bms_add_member(*notnullcolumns_per_rel,
+												 notnull_attno);
+	}
+
+	/* Check if each related rtable can yield a unique result set */
+	rel_idx = 0;
+	foreach(lc, query->rtable)
+	{
+		Relation relation;
+		TupleDesc desc;
+		RangeTblEntry *rte;
+		int attr_idx;
+
+		if (!bms_is_member(rel_idx+1, non_semi_anti_relids))
+			continue;
+
+		rte = lfirst_node(RangeTblEntry, lc);
+		Assert(rte->rtekind == RTE_RELATION);
+		Assert(rte->relid != InvalidOid);
+
+	    relation = relation_open(rte->relid, RowExclusiveLock);
+		desc = relation->rd_att;
+		attr_idx = 0;
+
+		/* Add the notnullcolumns based on catalog */
+		for(; attr_idx < desc->natts; attr_idx++)
+		{
+			int notnull_attno;
+			if (!desc->attrs[attr_idx].attnotnull)
+				continue;
+			notnull_attno = attr_idx + 1 - FirstLowInvalidHeapAttributeNumber;
+			notnullcolumns[rel_idx] = bms_add_member(notnullcolumns[rel_idx],
+													 notnull_attno);
+		}
+
+		/* check non-nullable in qual, only col is not null checked now */
+		if (!is_unique_result_already(relation,
+									  targetlist_by_table[rel_idx],
+									  notnullcolumns[rel_idx]))
+		{
+			RelationClose(relation);
+			goto ret;
+		}
+		RelationClose(relation);
+		rel_idx++;
+	}
+
+	should_distinct_elimination = true;
+
+ ret:
+	bms_array_free(notnullcolumns, num_of_rtables);
+	bms_array_free(targetlist_by_table, num_of_rtables);
+	bms_free(non_semi_anti_relids);
+
+	if (should_distinct_elimination)
+	{
+		query->distinctClause = NIL;
+		query->hasDistinctOn = false;
+	}
+}
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index df025a5a30..d8a76a2273 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -2346,6 +2346,8 @@ RelationDestroyRelation(Relation relation, bool remember_tupdesc)
 	bms_free(relation->rd_keyattr);
 	bms_free(relation->rd_pkattr);
 	bms_free(relation->rd_idattr);
+	if (relation->rd_plain_ukattrs)
+		bms_array_free(relation->rd_plain_ukattrs, relation->rd_plain_ukcount);
 	if (relation->rd_pubactions)
 		pfree(relation->rd_pubactions);
 	if (relation->rd_options)
@@ -4762,6 +4764,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
 	Bitmapset  *indexattrs;		/* indexed columns */
 	Bitmapset  *uindexattrs;	/* columns in unique indexes */
 	Bitmapset  *pkindexattrs;	/* columns in the primary index */
+	Bitmapset  **ukindexattrs = NULL; /* columns in the unique indexes */
 	Bitmapset  *idindexattrs;	/* columns in the replica identity */
 	List	   *indexoidlist;
 	List	   *newindexoidlist;
@@ -4769,6 +4772,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
 	Oid			relreplindex;
 	ListCell   *l;
 	MemoryContext oldcxt;
+	int plain_uk_index_count = 0, index_count = 0, indexno = 0;
 
 	/* Quick exit if we already computed the result. */
 	if (relation->rd_indexattr != NULL)
@@ -4826,6 +4830,9 @@ restart:
 	uindexattrs = NULL;
 	pkindexattrs = NULL;
 	idindexattrs = NULL;
+	index_count = list_length(indexoidlist);
+	ukindexattrs = palloc0(sizeof(Bitmapset *) * index_count);
+
 	foreach(l, indexoidlist)
 	{
 		Oid			indexOid = lfirst_oid(l);
@@ -4875,6 +4882,9 @@ restart:
 		/* Is this index the configured (or default) replica identity? */
 		isIDKey = (indexOid == relreplindex);
 
+		if (isKey)
+			plain_uk_index_count++;
+
 		/* Collect simple attribute references */
 		for (i = 0; i < indexDesc->rd_index->indnatts; i++)
 		{
@@ -4904,6 +4914,11 @@ restart:
 				if (isIDKey && i < indexDesc->rd_index->indnkeyatts)
 					idindexattrs = bms_add_member(idindexattrs,
 												  attrnum - FirstLowInvalidHeapAttributeNumber);
+
+				if (isKey)
+					ukindexattrs[indexno] = bms_add_member(ukindexattrs[indexno],
+														   attrnum - FirstLowInvalidHeapAttributeNumber);
+
 			}
 		}
 
@@ -4914,6 +4929,7 @@ restart:
 		pull_varattnos(indexPredicate, 1, &indexattrs);
 
 		index_close(indexDesc, AccessShareLock);
+		indexno++;
 	}
 
 	/*
@@ -4940,6 +4956,7 @@ restart:
 		bms_free(pkindexattrs);
 		bms_free(idindexattrs);
 		bms_free(indexattrs);
+		bms_array_free(ukindexattrs, index_count);
 
 		goto restart;
 	}
@@ -4953,6 +4970,8 @@ restart:
 	relation->rd_pkattr = NULL;
 	bms_free(relation->rd_idattr);
 	relation->rd_idattr = NULL;
+	bms_array_free(relation->rd_plain_ukattrs, relation->rd_plain_ukcount);
+	relation->rd_plain_ukattrs = NULL;
 
 	/*
 	 * Now save copies of the bitmaps in the relcache entry.  We intentionally
@@ -4966,6 +4985,8 @@ restart:
 	relation->rd_pkattr = bms_copy(pkindexattrs);
 	relation->rd_idattr = bms_copy(idindexattrs);
 	relation->rd_indexattr = bms_copy(indexattrs);
+	relation->rd_plain_ukattrs = bms_array_copy(ukindexattrs, index_count);
+	relation->rd_plain_ukcount = plain_uk_index_count;
 	MemoryContextSwitchTo(oldcxt);
 
 	/* We return our original working copy for caller to play with */
@@ -5618,6 +5639,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_keyattr = NULL;
 		rel->rd_pkattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_plain_ukattrs = NULL;
+		rel->rd_plain_ukcount = 0;
 		rel->rd_pubactions = NULL;
 		rel->rd_statvalid = false;
 		rel->rd_statlist = NIL;
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index e44f71e991..fa798dd564 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1064,6 +1064,16 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_distinct_elimination", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables plan-time and run-time unique elimination."),
+		    gettext_noop("Allows the query planner to remove the uncecessary distinct clause."), 
+			GUC_EXPLAIN
+		},
+		&enable_distinct_elimination,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index b7b18a0b68..ff30feb521 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -117,4 +117,6 @@ extern int	bms_prev_member(const Bitmapset *a, int prevbit);
 /* support for hashtables using Bitmapsets as keys: */
 extern uint32 bms_hash_value(const Bitmapset *a);
 
+extern Bitmapset **bms_array_copy(Bitmapset **bms_array, int len);
+extern void bms_array_free(Bitmapset **bms_array,  int len);
 #endif							/* BITMAPSET_H */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index cb012ba198..4fa5d32df6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_distinct_elimination;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 44ed04dd3f..7c5a6d65b6 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -120,6 +120,9 @@ typedef struct RelationData
 	Bitmapset  *rd_indexattr;	/* identifies columns used in indexes */
 	Bitmapset  *rd_keyattr;		/* cols that can be ref'd by foreign keys */
 	Bitmapset  *rd_pkattr;		/* cols included in primary key */
+	Bitmapset  **rd_plain_ukattrs;    /* cols included in the plain unique indexes,
+                                   only non-expression, non-partical columns are count */
+	int        rd_plain_ukcount;  /* the no. of uk count */
 	Bitmapset  *rd_idattr;		/* included in replica identity index */
 
 	PublicationActions *rd_pubactions;	/* publication actions */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..3f6595d53b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4433,17 +4433,17 @@ 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              
---------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct_2.out b/src/test/regress/expected/select_distinct_2.out
new file mode 100644
index 0000000000..9c0dd564c8
--- /dev/null
+++ b/src/test/regress/expected/select_distinct_2.out
@@ -0,0 +1,141 @@
+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: b, c, d, e
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+create unique index select_distinct_a_uk on select_distinct_a(c, d);
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: b, c, d, e
+   ->  Seq Scan on select_distinct_a
+         Filter: (c IS NOT NULL)
+(4 rows)
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null and d is not null;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: ((c IS NOT NULL) AND (d IS NOT NULL))
+(2 rows)
+
+explain select distinct d, e from select_distinct_a group by d, e;
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ HashAggregate  (cost=15.85..17.85 rows=200 width=8)
+   Group Key: d, e
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=390 width=8)
+(3 rows)
+
+create table select_distinct_b(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+explain (costs off) select distinct * from select_distinct_a a, select_distinct_b b;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_a a
+   ->  Materialize
+         ->  Seq Scan on select_distinct_b b
+(4 rows)
+
+explain (costs off) select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b;
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.b, a.c, b.a, b.b
+         ->  Nested Loop
+               ->  Seq Scan on select_distinct_a a
+               ->  Materialize
+                     ->  Seq Scan on select_distinct_b b
+(7 rows)
+
+explain (costs off) select distinct a.d, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (d IS NOT NULL)
+(5 rows)
+
+explain (costs off) select distinct a.d, b.a from select_distinct_a a, select_distinct_b b group by a.d, b.a;
+                    QUERY PLAN                     
+---------------------------------------------------
+ HashAggregate
+   Group Key: a.d, b.a
+   ->  Nested Loop
+         ->  Seq Scan on select_distinct_a a
+         ->  Materialize
+               ->  Seq Scan on select_distinct_b b
+(6 rows)
+
+explain (costs off) select distinct a, b from select_distinct_a where a in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop Semi Join
+   ->  Seq Scan on select_distinct_a
+   ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b
+         Index Cond: (a = select_distinct_a.a)
+(4 rows)
+
+explain (costs off) select distinct a, b from select_distinct_a where a not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+explain (costs off) select distinct * from select_distinct_a a, (select a, max(b) as b from select_distinct_b group by a) b
+where a.a in (select a from select_distinct_b)
+and a.b = b.b;
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.a, a.b, a.c, a.d, a.e, select_distinct_b_1.a
+         ->  Nested Loop
+               Join Filter: (a.b = (max(select_distinct_b_1.b)))
+               ->  HashAggregate
+                     Group Key: select_distinct_b_1.a
+                     ->  Seq Scan on select_distinct_b select_distinct_b_1
+               ->  Materialize
+                     ->  Nested Loop Semi Join
+                           ->  Seq Scan on select_distinct_a a
+                           ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b
+                                 Index Cond: (a = a.a)
+(13 rows)
+
+explain (costs off) select distinct on(a) a, b from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+explain (costs off) select distinct on(a, b) a, b from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index a1c90eb905..e053214f9d 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -73,6 +73,7 @@ select name, setting from pg_settings where name like 'enable%';
               name              | setting 
 --------------------------------+---------
  enable_bitmapscan              | on
+ enable_distinct_elimination    | on
  enable_gathermerge             | on
  enable_hashagg                 | on
  enable_hashjoin                | on
@@ -89,7 +90,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(17 rows)
+(18 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/select_distinct_2.sql b/src/test/regress/sql/select_distinct_2.sql
new file mode 100644
index 0000000000..cad8d40dc6
--- /dev/null
+++ b/src/test/regress/sql/select_distinct_2.sql
@@ -0,0 +1,42 @@
+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a;
+
+create unique index select_distinct_a_uk on select_distinct_a(c, d);
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null;
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null and d is not null;
+
+explain select distinct d, e from select_distinct_a group by d, e;
+
+
+create table select_distinct_b(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+
+explain (costs off) select distinct * from select_distinct_a a, select_distinct_b b;
+
+explain (costs off) select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b;
+
+explain (costs off) select distinct a.d, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null;
+
+explain (costs off) select distinct a.d, b.a from select_distinct_a a, select_distinct_b b group by a.d, b.a;
+
+explain (costs off) select distinct a, b from select_distinct_a where a in (select a from select_distinct_b);
+
+explain (costs off) select distinct a, b from select_distinct_a where a not in (select a from select_distinct_b);
+
+explain (costs off) select distinct * from select_distinct_a a, (select a, max(b) as b from select_distinct_b group by a) b
+where a.a in (select a from select_distinct_b)
+and a.b = b.b;
+
+explain (costs off) select distinct on(a) a, b from select_distinct_a;
+explain (costs off) select distinct on(a, b) a, b from select_distinct_a;
+
+drop table select_distinct_a;
+drop table select_distinct_b;
-- 
2.20.1 (Apple Git-117)

From 94edaece73503572d4489d41e6644efe1e13f652 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Fri, 31 Jan 2020 19:38:05 +0800
Subject: [PATCH] Erase the distinctClause if the result is unique by
 definition

For a single relation, we can tell it by any one of the following
is true:
1. The pk is in the target list.
2. The uk is in the target list and the columns is not null
3. The columns in group-by clause is also in the target list

for relation join, we can tell it by:
if every relation in the jointree yield a unique result set,then
the final result is unique as well regardless the join method.
for semi/anti join, we don't have such restriction on the right
table.
---
 src/backend/nodes/bitmapset.c                 |  40 +++
 src/backend/optimizer/path/costsize.c         |   1 +
 src/backend/optimizer/plan/planner.c          | 292 ++++++++++++++++++
 src/backend/utils/cache/relcache.c            |  23 ++
 src/backend/utils/misc/guc.c                  |  10 +
 src/include/nodes/bitmapset.h                 |   2 +
 src/include/optimizer/cost.h                  |   1 +
 src/include/utils/rel.h                       |   3 +
 src/test/regress/expected/join.out            |  16 +-
 .../regress/expected/select_distinct_2.out    | 141 +++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/sql/select_distinct_2.sql    |  42 +++
 12 files changed, 565 insertions(+), 9 deletions(-)
 create mode 100644 src/test/regress/expected/select_distinct_2.out
 create mode 100644 src/test/regress/sql/select_distinct_2.sql

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 648cc1a7eb..76ce9b526e 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1167,3 +1167,43 @@ bms_hash_value(const Bitmapset *a)
 	return DatumGetUInt32(hash_any((const unsigned char *) a->words,
 								   (lastword + 1) * sizeof(bitmapword)));
 }
+
+/*
+ * bms_array_copy --
+ *
+ * copy the bms data in the newly palloc memory
+ */
+
+Bitmapset**
+bms_array_copy(Bitmapset **bms_array, int len)
+{
+	Bitmapset **res;
+	int i;
+	if (bms_array == NULL || len < 1)
+		return NULL;
+
+	res = palloc(sizeof(Bitmapset*) * len);
+	for(i = 0; i < len; i++)
+	{
+		res[i] = bms_copy(bms_array[i]);
+	}
+	return res;
+}
+
+/*
+ * bms_array_free
+ *
+ * free the element in the array one by one, free the array as well at last
+ */
+void
+bms_array_free(Bitmapset **bms_array,  int len)
+{
+	int idx;
+	if (bms_array == NULL)
+		return;
+	for(idx = 0 ; idx < len; idx++)
+	{
+		bms_free(bms_array[idx]);
+	}
+	pfree(bms_array);
+}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index b5a0033721..dde16b5d44 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -138,6 +138,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_distinct_elimination = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..6f7d85f96e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -22,8 +22,10 @@
 #include "access/htup_details.h"
 #include "access/parallel.h"
 #include "access/sysattr.h"
+#include "access/relation.h"
 #include "access/table.h"
 #include "access/xact.h"
+#include "catalog/index.h"
 #include "catalog/pg_constraint.h"
 #include "catalog/pg_inherits.h"
 #include "catalog/pg_proc.h"
@@ -35,6 +37,7 @@
 #include "lib/bipartite_match.h"
 #include "lib/knapsack.h"
 #include "miscadmin.h"
+#include "nodes/bitmapset.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #ifdef OPTIMIZER_DEBUG
@@ -248,6 +251,7 @@ static bool group_by_has_partkey(RelOptInfo *input_rel,
 								 List *targetList,
 								 List *groupClause);
 static int	common_prefix_cmp(const void *a, const void *b);
+static void	preprocess_distinct_node(PlannerInfo *root);
 
 
 /*****************************************************************************
@@ -989,6 +993,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	/* Remove any redundant GROUP BY columns */
 	remove_useless_groupby_columns(root);
 
+	if (enable_distinct_elimination)
+		preprocess_distinct_node(root);
+
 	/*
 	 * If we have any outer joins, try to reduce them to plain inner joins.
 	 * This step is most easily done after we've done expression
@@ -7409,3 +7416,288 @@ group_by_has_partkey(RelOptInfo *input_rel,
 
 	return true;
 }
+
+/*
+ * is_unique_result_already
+ *
+ * Given a relation, we can know its primary key + unique key information
+ * unique target is the target list of distinct/distinct on target.
+ * not_null_columns is a union of not null columns based on catalog and quals.
+ * then we can know the result is unique already before executing it if
+ * the primary key or uk + not null in target list.
+ */
+static bool
+is_unique_result_already(Relation relation,
+						 Bitmapset *unique_target,
+						 Bitmapset *not_null_columns)
+{
+	int i;
+	Bitmapset *pkattr = RelationGetIndexAttrBitmap(relation,
+												   INDEX_ATTR_BITMAP_PRIMARY_KEY);
+
+	/*
+	 * if the pk is in the target list,
+	 * the result set is unique for this relation
+	 */
+	if (pkattr != NULL &&
+		!bms_is_empty(pkattr) &&
+		bms_is_subset(pkattr, unique_target))
+	{
+		return true;
+	}
+
+	/*
+	 * check if the pk is in the unique index
+	 */
+	for (i = 0; i < relation->rd_plain_ukcount; i++)
+	{
+		Bitmapset *ukattr = relation->rd_plain_ukattrs[i];
+		if (!bms_is_empty(ukattr)
+			&& bms_is_subset(ukattr, unique_target)
+			&& bms_is_subset(ukattr, not_null_columns))
+			return true;
+	}
+
+	/*
+	 * If a unique index is in the target list, and the columns are not null
+	 * the result set is unique as well
+	 */
+
+	return false;
+}
+
+
+/*
+ * scan_non_semi_anti_relids
+ *
+ * scan jointree to get non-semi/anti join rtindex.
+ */
+static void
+scan_non_semi_anti_relids(Node* jtnode, Relids* relids)
+{
+	if (jtnode == NULL)
+		return;
+
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*relids = bms_add_member(*relids, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			scan_non_semi_anti_relids(lfirst(l), relids);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		scan_non_semi_anti_relids(j->larg, relids);
+		if (j->jointype != JOIN_SEMI && j->jointype != JOIN_ANTI)
+		{
+			scan_non_semi_anti_relids(j->rarg, relids);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+
+}
+
+/*
+ * preprocess_distinct_node
+ *
+ * remove the distinctClause if it is not necessary by definition
+ */
+static void
+preprocess_distinct_node(PlannerInfo *root)
+{
+	Query *query = root->parse;
+	ListCell *lc;
+	int num_of_rtables;
+	Bitmapset **targetlist_by_table = NULL;
+    Bitmapset **notnullcolumns = NULL;
+	Index rel_idx = 0;
+	bool should_distinct_elimination = false;
+	Relids non_semi_anti_relids = NULL;
+
+	if (query->distinctClause == NIL)
+		return;
+
+	scan_non_semi_anti_relids((Node*)query->jointree, &non_semi_anti_relids);
+
+	foreach(lc, query->rtable)
+	{
+		RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
+		rel_idx++;
+		if (!bms_is_member(rel_idx, non_semi_anti_relids))
+			continue;
+		/* we only handle the basic Relation for now */
+		if (rte->rtekind != RTE_RELATION)
+			return;
+	}
+
+	num_of_rtables = bms_num_members(non_semi_anti_relids);
+
+	/*
+	 * If the columns in group clause is in the target list
+	 * we don't need distinct
+	 */
+	if (query->groupClause != NIL)
+	{
+		Bitmapset *groupclause_bm = NULL;
+		Bitmapset *groupclause_in_targetlist_bm = NULL;
+		ListCell *lc;
+		foreach(lc, query->groupClause)
+			groupclause_bm = bms_add_member(groupclause_bm,
+												lfirst_node(SortGroupClause, lc)->tleSortGroupRef);
+
+		foreach(lc, query->targetList)
+		{
+			TargetEntry *te = lfirst_node(TargetEntry, lc);
+			if (te->resjunk)
+				continue;
+			groupclause_in_targetlist_bm = bms_add_member(groupclause_in_targetlist_bm,
+														  te->ressortgroupref);
+		}
+
+		should_distinct_elimination = bms_is_subset(groupclause_bm,
+													groupclause_in_targetlist_bm);
+		bms_free(groupclause_bm);
+		bms_free(groupclause_in_targetlist_bm);
+		if (should_distinct_elimination)
+			goto ret;
+	}
+
+	targetlist_by_table = palloc0(sizeof(Bitmapset*) * num_of_rtables);
+	notnullcolumns = palloc0(sizeof(Bitmapset* ) * num_of_rtables);
+
+	/* build the targetlist_by_table */
+	foreach(lc, query->targetList)
+	{
+		TargetEntry *te = lfirst_node(TargetEntry, lc);
+		Expr *expr = te->expr;
+		Var *var;
+		Bitmapset **target_column_per_rel;
+		int target_attno;
+
+		if (!IsA(expr, Var))
+			continue;
+
+		var = (Var *)(expr);
+		if (var->varlevelsup != 0)
+			continue;
+
+		target_column_per_rel = &targetlist_by_table[var->varno - 1];
+		target_attno = var->varattno - FirstLowInvalidHeapAttributeNumber;
+
+		/*
+		 * for distinct On (..), we only count the field in .. rather than
+		 * all the entries in target list
+		 */
+		if (query->hasDistinctOn)
+		{
+			Index ref = te->ressortgroupref;
+			ListCell *lc;
+
+			/*
+			 * A fastpath to know if the targetEntry is in the distinctClause
+			 */
+			if (ref == 0)
+				continue;
+
+			/*
+			 * Even the ref is not zero, it may be in sort as well, so we
+			 * need dobule check.
+			 */
+			foreach(lc, query->distinctClause)
+			{
+				if (ref == lfirst_node(SortGroupClause, lc)->tleSortGroupRef)
+					*target_column_per_rel = bms_add_member(*target_column_per_rel,
+															target_attno);
+			}
+		}
+		else
+			*target_column_per_rel = bms_add_member(*target_column_per_rel,
+													target_attno);
+	}
+
+	/* find out nonnull columns from qual via find_nonnullable_vars */
+	foreach(lc, find_nonnullable_vars(query->jointree->quals))
+	{
+		Var *not_null_var;
+		Bitmapset **notnullcolumns_per_rel;
+		int notnull_attno;
+		if (!IsA(lfirst(lc), Var))
+			continue;
+		not_null_var = lfirst_node(Var, lc);
+		if (not_null_var->varno == INNER_VAR ||
+			not_null_var->varno == OUTER_VAR ||
+			not_null_var->varno == INDEX_VAR)
+			continue;
+		notnullcolumns_per_rel = &notnullcolumns[not_null_var->varno - 1];
+		notnull_attno = not_null_var->varattno - FirstLowInvalidHeapAttributeNumber;
+		*notnullcolumns_per_rel = bms_add_member(*notnullcolumns_per_rel,
+												 notnull_attno);
+	}
+
+	/* Check if each related rtable can yield a unique result set */
+	rel_idx = 0;
+	foreach(lc, query->rtable)
+	{
+		Relation relation;
+		TupleDesc desc;
+		RangeTblEntry *rte;
+		int attr_idx;
+
+		if (!bms_is_member(rel_idx+1, non_semi_anti_relids))
+			continue;
+
+		rte = lfirst_node(RangeTblEntry, lc);
+		Assert(rte->rtekind == RTE_RELATION);
+		Assert(rte->relid != InvalidOid);
+
+	    relation = relation_open(rte->relid, RowExclusiveLock);
+		desc = relation->rd_att;
+		attr_idx = 0;
+
+		/* Add the notnullcolumns based on catalog */
+		for(; attr_idx < desc->natts; attr_idx++)
+		{
+			int notnull_attno;
+			if (!desc->attrs[attr_idx].attnotnull)
+				continue;
+			notnull_attno = attr_idx + 1 - FirstLowInvalidHeapAttributeNumber;
+			notnullcolumns[rel_idx] = bms_add_member(notnullcolumns[rel_idx],
+													 notnull_attno);
+		}
+
+		/* check non-nullable in qual, only col is not null checked now */
+		if (!is_unique_result_already(relation,
+									  targetlist_by_table[rel_idx],
+									  notnullcolumns[rel_idx]))
+		{
+			RelationClose(relation);
+			goto ret;
+		}
+		RelationClose(relation);
+		rel_idx++;
+	}
+
+	should_distinct_elimination = true;
+
+ ret:
+	bms_array_free(notnullcolumns, num_of_rtables);
+	bms_array_free(targetlist_by_table, num_of_rtables);
+	bms_free(non_semi_anti_relids);
+
+	if (should_distinct_elimination)
+	{
+		query->distinctClause = NIL;
+		query->hasDistinctOn = false;
+	}
+}
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index df025a5a30..d8a76a2273 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -2346,6 +2346,8 @@ RelationDestroyRelation(Relation relation, bool remember_tupdesc)
 	bms_free(relation->rd_keyattr);
 	bms_free(relation->rd_pkattr);
 	bms_free(relation->rd_idattr);
+	if (relation->rd_plain_ukattrs)
+		bms_array_free(relation->rd_plain_ukattrs, relation->rd_plain_ukcount);
 	if (relation->rd_pubactions)
 		pfree(relation->rd_pubactions);
 	if (relation->rd_options)
@@ -4762,6 +4764,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
 	Bitmapset  *indexattrs;		/* indexed columns */
 	Bitmapset  *uindexattrs;	/* columns in unique indexes */
 	Bitmapset  *pkindexattrs;	/* columns in the primary index */
+	Bitmapset  **ukindexattrs = NULL; /* columns in the unique indexes */
 	Bitmapset  *idindexattrs;	/* columns in the replica identity */
 	List	   *indexoidlist;
 	List	   *newindexoidlist;
@@ -4769,6 +4772,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
 	Oid			relreplindex;
 	ListCell   *l;
 	MemoryContext oldcxt;
+	int plain_uk_index_count = 0, index_count = 0, indexno = 0;
 
 	/* Quick exit if we already computed the result. */
 	if (relation->rd_indexattr != NULL)
@@ -4826,6 +4830,9 @@ restart:
 	uindexattrs = NULL;
 	pkindexattrs = NULL;
 	idindexattrs = NULL;
+	index_count = list_length(indexoidlist);
+	ukindexattrs = palloc0(sizeof(Bitmapset *) * index_count);
+
 	foreach(l, indexoidlist)
 	{
 		Oid			indexOid = lfirst_oid(l);
@@ -4875,6 +4882,9 @@ restart:
 		/* Is this index the configured (or default) replica identity? */
 		isIDKey = (indexOid == relreplindex);
 
+		if (isKey)
+			plain_uk_index_count++;
+
 		/* Collect simple attribute references */
 		for (i = 0; i < indexDesc->rd_index->indnatts; i++)
 		{
@@ -4904,6 +4914,11 @@ restart:
 				if (isIDKey && i < indexDesc->rd_index->indnkeyatts)
 					idindexattrs = bms_add_member(idindexattrs,
 												  attrnum - FirstLowInvalidHeapAttributeNumber);
+
+				if (isKey)
+					ukindexattrs[indexno] = bms_add_member(ukindexattrs[indexno],
+														   attrnum - FirstLowInvalidHeapAttributeNumber);
+
 			}
 		}
 
@@ -4914,6 +4929,7 @@ restart:
 		pull_varattnos(indexPredicate, 1, &indexattrs);
 
 		index_close(indexDesc, AccessShareLock);
+		indexno++;
 	}
 
 	/*
@@ -4940,6 +4956,7 @@ restart:
 		bms_free(pkindexattrs);
 		bms_free(idindexattrs);
 		bms_free(indexattrs);
+		bms_array_free(ukindexattrs, index_count);
 
 		goto restart;
 	}
@@ -4953,6 +4970,8 @@ restart:
 	relation->rd_pkattr = NULL;
 	bms_free(relation->rd_idattr);
 	relation->rd_idattr = NULL;
+	bms_array_free(relation->rd_plain_ukattrs, relation->rd_plain_ukcount);
+	relation->rd_plain_ukattrs = NULL;
 
 	/*
 	 * Now save copies of the bitmaps in the relcache entry.  We intentionally
@@ -4966,6 +4985,8 @@ restart:
 	relation->rd_pkattr = bms_copy(pkindexattrs);
 	relation->rd_idattr = bms_copy(idindexattrs);
 	relation->rd_indexattr = bms_copy(indexattrs);
+	relation->rd_plain_ukattrs = bms_array_copy(ukindexattrs, index_count);
+	relation->rd_plain_ukcount = plain_uk_index_count;
 	MemoryContextSwitchTo(oldcxt);
 
 	/* We return our original working copy for caller to play with */
@@ -5618,6 +5639,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_keyattr = NULL;
 		rel->rd_pkattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_plain_ukattrs = NULL;
+		rel->rd_plain_ukcount = 0;
 		rel->rd_pubactions = NULL;
 		rel->rd_statvalid = false;
 		rel->rd_statlist = NIL;
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index e44f71e991..fa798dd564 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1064,6 +1064,16 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_distinct_elimination", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables plan-time and run-time unique elimination."),
+		    gettext_noop("Allows the query planner to remove the uncecessary distinct clause."), 
+			GUC_EXPLAIN
+		},
+		&enable_distinct_elimination,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index b7b18a0b68..ff30feb521 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -117,4 +117,6 @@ extern int	bms_prev_member(const Bitmapset *a, int prevbit);
 /* support for hashtables using Bitmapsets as keys: */
 extern uint32 bms_hash_value(const Bitmapset *a);
 
+extern Bitmapset **bms_array_copy(Bitmapset **bms_array, int len);
+extern void bms_array_free(Bitmapset **bms_array,  int len);
 #endif							/* BITMAPSET_H */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index cb012ba198..4fa5d32df6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_distinct_elimination;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 44ed04dd3f..7c5a6d65b6 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -120,6 +120,9 @@ typedef struct RelationData
 	Bitmapset  *rd_indexattr;	/* identifies columns used in indexes */
 	Bitmapset  *rd_keyattr;		/* cols that can be ref'd by foreign keys */
 	Bitmapset  *rd_pkattr;		/* cols included in primary key */
+	Bitmapset  **rd_plain_ukattrs;    /* cols included in the plain unique indexes,
+                                   only non-expression, non-partical columns are count */
+	int        rd_plain_ukcount;  /* the no. of uk count */
 	Bitmapset  *rd_idattr;		/* included in replica identity index */
 
 	PublicationActions *rd_pubactions;	/* publication actions */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..3f6595d53b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4433,17 +4433,17 @@ 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              
---------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct_2.out b/src/test/regress/expected/select_distinct_2.out
new file mode 100644
index 0000000000..9c0dd564c8
--- /dev/null
+++ b/src/test/regress/expected/select_distinct_2.out
@@ -0,0 +1,141 @@
+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: b, c, d, e
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+create unique index select_distinct_a_uk on select_distinct_a(c, d);
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: b, c, d, e
+   ->  Seq Scan on select_distinct_a
+         Filter: (c IS NOT NULL)
+(4 rows)
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null and d is not null;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: ((c IS NOT NULL) AND (d IS NOT NULL))
+(2 rows)
+
+explain select distinct d, e from select_distinct_a group by d, e;
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ HashAggregate  (cost=15.85..17.85 rows=200 width=8)
+   Group Key: d, e
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=390 width=8)
+(3 rows)
+
+create table select_distinct_b(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+explain (costs off) select distinct * from select_distinct_a a, select_distinct_b b;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_a a
+   ->  Materialize
+         ->  Seq Scan on select_distinct_b b
+(4 rows)
+
+explain (costs off) select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b;
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.b, a.c, b.a, b.b
+         ->  Nested Loop
+               ->  Seq Scan on select_distinct_a a
+               ->  Materialize
+                     ->  Seq Scan on select_distinct_b b
+(7 rows)
+
+explain (costs off) select distinct a.d, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (d IS NOT NULL)
+(5 rows)
+
+explain (costs off) select distinct a.d, b.a from select_distinct_a a, select_distinct_b b group by a.d, b.a;
+                    QUERY PLAN                     
+---------------------------------------------------
+ HashAggregate
+   Group Key: a.d, b.a
+   ->  Nested Loop
+         ->  Seq Scan on select_distinct_a a
+         ->  Materialize
+               ->  Seq Scan on select_distinct_b b
+(6 rows)
+
+explain (costs off) select distinct a, b from select_distinct_a where a in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop Semi Join
+   ->  Seq Scan on select_distinct_a
+   ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b
+         Index Cond: (a = select_distinct_a.a)
+(4 rows)
+
+explain (costs off) select distinct a, b from select_distinct_a where a not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+explain (costs off) select distinct * from select_distinct_a a, (select a, max(b) as b from select_distinct_b group by a) b
+where a.a in (select a from select_distinct_b)
+and a.b = b.b;
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.a, a.b, a.c, a.d, a.e, select_distinct_b_1.a
+         ->  Nested Loop
+               Join Filter: (a.b = (max(select_distinct_b_1.b)))
+               ->  HashAggregate
+                     Group Key: select_distinct_b_1.a
+                     ->  Seq Scan on select_distinct_b select_distinct_b_1
+               ->  Materialize
+                     ->  Nested Loop Semi Join
+                           ->  Seq Scan on select_distinct_a a
+                           ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b
+                                 Index Cond: (a = a.a)
+(13 rows)
+
+explain (costs off) select distinct on(a) a, b from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+explain (costs off) select distinct on(a, b) a, b from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index a1c90eb905..e053214f9d 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -73,6 +73,7 @@ select name, setting from pg_settings where name like 'enable%';
               name              | setting 
 --------------------------------+---------
  enable_bitmapscan              | on
+ enable_distinct_elimination    | on
  enable_gathermerge             | on
  enable_hashagg                 | on
  enable_hashjoin                | on
@@ -89,7 +90,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(17 rows)
+(18 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/select_distinct_2.sql b/src/test/regress/sql/select_distinct_2.sql
new file mode 100644
index 0000000000..cad8d40dc6
--- /dev/null
+++ b/src/test/regress/sql/select_distinct_2.sql
@@ -0,0 +1,42 @@
+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a;
+
+create unique index select_distinct_a_uk on select_distinct_a(c, d);
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null;
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null and d is not null;
+
+explain select distinct d, e from select_distinct_a group by d, e;
+
+
+create table select_distinct_b(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+
+explain (costs off) select distinct * from select_distinct_a a, select_distinct_b b;
+
+explain (costs off) select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b;
+
+explain (costs off) select distinct a.d, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null;
+
+explain (costs off) select distinct a.d, b.a from select_distinct_a a, select_distinct_b b group by a.d, b.a;
+
+explain (costs off) select distinct a, b from select_distinct_a where a in (select a from select_distinct_b);
+
+explain (costs off) select distinct a, b from select_distinct_a where a not in (select a from select_distinct_b);
+
+explain (costs off) select distinct * from select_distinct_a a, (select a, max(b) as b from select_distinct_b group by a) b
+where a.a in (select a from select_distinct_b)
+and a.b = b.b;
+
+explain (costs off) select distinct on(a) a, b from select_distinct_a;
+explain (costs off) select distinct on(a, b) a, b from select_distinct_a;
+
+drop table select_distinct_a;
+drop table select_distinct_b;
-- 
2.20.1 (Apple Git-117)

From 01159c3011f9798a21ad42c419435f9b23ec7a88 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Fri, 31 Jan 2020 19:38:05 +0800
Subject: [PATCH] Erase the distinctClause if the result is unique by
 definition

For a single relation, we can tell it by any one of the following
is true:
1. The pk is in the target list.
2. The uk is in the target list and the columns is not null
3. The columns in group-by clause is also in the target list

for relation join, we can tell it by:
if every relation in the jointree yield a unique result set,then
the final result is unique as well regardless the join method.
for semi/anti join, we don't have such restriction on the right
table.
---
 src/backend/nodes/bitmapset.c                 |  40 +++
 src/backend/optimizer/path/costsize.c         |   1 +
 src/backend/optimizer/plan/planner.c          | 301 ++++++++++++++++++
 src/backend/utils/cache/relcache.c            |  23 ++
 src/backend/utils/misc/guc.c                  |  10 +
 src/include/nodes/bitmapset.h                 |   2 +
 src/include/optimizer/cost.h                  |   1 +
 src/include/utils/rel.h                       |   3 +
 src/test/regress/expected/join.out            |  16 +-
 .../regress/expected/select_distinct_2.out    | 237 ++++++++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/sql/select_distinct_2.sql    |  81 +++++
 12 files changed, 709 insertions(+), 9 deletions(-)
 create mode 100644 src/test/regress/expected/select_distinct_2.out
 create mode 100644 src/test/regress/sql/select_distinct_2.sql

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 648cc1a7eb..76ce9b526e 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1167,3 +1167,43 @@ bms_hash_value(const Bitmapset *a)
 	return DatumGetUInt32(hash_any((const unsigned char *) a->words,
 								   (lastword + 1) * sizeof(bitmapword)));
 }
+
+/*
+ * bms_array_copy --
+ *
+ * copy the bms data in the newly palloc memory
+ */
+
+Bitmapset**
+bms_array_copy(Bitmapset **bms_array, int len)
+{
+	Bitmapset **res;
+	int i;
+	if (bms_array == NULL || len < 1)
+		return NULL;
+
+	res = palloc(sizeof(Bitmapset*) * len);
+	for(i = 0; i < len; i++)
+	{
+		res[i] = bms_copy(bms_array[i]);
+	}
+	return res;
+}
+
+/*
+ * bms_array_free
+ *
+ * free the element in the array one by one, free the array as well at last
+ */
+void
+bms_array_free(Bitmapset **bms_array,  int len)
+{
+	int idx;
+	if (bms_array == NULL)
+		return;
+	for(idx = 0 ; idx < len; idx++)
+	{
+		bms_free(bms_array[idx]);
+	}
+	pfree(bms_array);
+}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index b5a0033721..dde16b5d44 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -138,6 +138,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_distinct_elimination = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..2974dc3a8a 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -22,8 +22,10 @@
 #include "access/htup_details.h"
 #include "access/parallel.h"
 #include "access/sysattr.h"
+#include "access/relation.h"
 #include "access/table.h"
 #include "access/xact.h"
+#include "catalog/index.h"
 #include "catalog/pg_constraint.h"
 #include "catalog/pg_inherits.h"
 #include "catalog/pg_proc.h"
@@ -35,6 +37,7 @@
 #include "lib/bipartite_match.h"
 #include "lib/knapsack.h"
 #include "miscadmin.h"
+#include "nodes/bitmapset.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #ifdef OPTIMIZER_DEBUG
@@ -248,6 +251,7 @@ static bool group_by_has_partkey(RelOptInfo *input_rel,
 								 List *targetList,
 								 List *groupClause);
 static int	common_prefix_cmp(const void *a, const void *b);
+static void	preprocess_distinct_node(PlannerInfo *root);
 
 
 /*****************************************************************************
@@ -989,6 +993,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	/* Remove any redundant GROUP BY columns */
 	remove_useless_groupby_columns(root);
 
+	if (enable_distinct_elimination)
+		preprocess_distinct_node(root);
+
 	/*
 	 * If we have any outer joins, try to reduce them to plain inner joins.
 	 * This step is most easily done after we've done expression
@@ -7409,3 +7416,297 @@ group_by_has_partkey(RelOptInfo *input_rel,
 
 	return true;
 }
+
+/*
+ * is_unique_result_already
+ *
+ * Given a relation, we can know its primary key + unique key information
+ * unique target is the target list of distinct/distinct on target.
+ * not_null_columns is a union of not null columns based on catalog and quals.
+ * then we can know the result is unique already before executing it if
+ * the primary key or uk + not null in target list.
+ */
+static bool
+is_unique_result_already(Relation relation,
+						 Bitmapset *unique_target,
+						 Bitmapset *not_null_columns)
+{
+	int i;
+	Bitmapset *pkattr = RelationGetIndexAttrBitmap(relation,
+												   INDEX_ATTR_BITMAP_PRIMARY_KEY);
+
+	/*
+	 * if the pk is in the target list,
+	 * the result set is unique for this relation
+	 */
+	if (pkattr != NULL &&
+		!bms_is_empty(pkattr) &&
+		bms_is_subset(pkattr, unique_target))
+	{
+		return true;
+	}
+
+	/*
+	 * check if the pk is in the unique index
+	 */
+	for (i = 0; i < relation->rd_plain_ukcount; i++)
+	{
+		Bitmapset *ukattr = relation->rd_plain_ukattrs[i];
+		if (!bms_is_empty(ukattr)
+			&& bms_is_subset(ukattr, unique_target)
+			&& bms_is_subset(ukattr, not_null_columns))
+			return true;
+	}
+
+	/*
+	 * If a unique index is in the target list, and the columns are not null
+	 * the result set is unique as well
+	 */
+
+	return false;
+}
+
+
+/*
+ * scan_non_semi_anti_relids
+ *
+ * scan jointree to get non-semi/anti join rtindex.
+ */
+static void
+scan_non_semi_anti_relids(Node* jtnode, Relids* relids)
+{
+	if (jtnode == NULL)
+		return;
+
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*relids = bms_add_member(*relids, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			scan_non_semi_anti_relids(lfirst(l), relids);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		scan_non_semi_anti_relids(j->larg, relids);
+		if (j->jointype != JOIN_SEMI && j->jointype != JOIN_ANTI)
+		{
+			scan_non_semi_anti_relids(j->rarg, relids);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+
+}
+
+/*
+ * preprocess_distinct_node
+ *
+ * remove the distinctClause if it is not necessary by definition
+ */
+static void
+preprocess_distinct_node(PlannerInfo *root)
+{
+	Query *query = root->parse;
+	ListCell *lc;
+	int num_of_rtables;
+	Bitmapset **targetlist_by_table = NULL;
+    Bitmapset **notnullcolumns = NULL;
+	Index rel_idx = 0;
+	bool should_distinct_elimination = false;
+	Relids non_semi_anti_relids = NULL;
+
+	if (query->distinctClause == NIL)
+		return;
+
+	/*
+	 * This rewrite depends on the primark key, unique/not null
+	 * constraints, and it may be dropped after get the plan.
+	 * If the IsoLevel is XACT_READ_UNCOMMTTIED, it may produces
+	 * duplicated rows after we remove the distinct node
+	 */
+	if (XactIsoLevel == XACT_READ_UNCOMMITTED)
+		return;
+
+	scan_non_semi_anti_relids((Node*)query->jointree, &non_semi_anti_relids);
+
+	foreach(lc, query->rtable)
+	{
+		RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
+		rel_idx++;
+		if (!bms_is_member(rel_idx, non_semi_anti_relids))
+			continue;
+		/* we only handle the basic Relation for now */
+		if (rte->rtekind != RTE_RELATION)
+			return;
+	}
+
+	num_of_rtables = list_length(query->rtable);
+
+	/*
+	 * If the columns in group clause is in the target list
+	 * we don't need distinct
+	 */
+	if (query->groupClause != NIL)
+	{
+		Bitmapset *groupclause_bm = NULL;
+		Bitmapset *groupclause_in_targetlist_bm = NULL;
+		ListCell *lc;
+		foreach(lc, query->groupClause)
+			groupclause_bm = bms_add_member(groupclause_bm,
+												lfirst_node(SortGroupClause, lc)->tleSortGroupRef);
+
+		foreach(lc, query->targetList)
+		{
+			TargetEntry *te = lfirst_node(TargetEntry, lc);
+			if (te->resjunk)
+				continue;
+			groupclause_in_targetlist_bm = bms_add_member(groupclause_in_targetlist_bm,
+														  te->ressortgroupref);
+		}
+
+		should_distinct_elimination = bms_is_subset(groupclause_bm,
+													groupclause_in_targetlist_bm);
+		bms_free(groupclause_bm);
+		bms_free(groupclause_in_targetlist_bm);
+		if (should_distinct_elimination)
+			goto ret;
+	}
+
+	targetlist_by_table = palloc0(sizeof(Bitmapset*) * num_of_rtables);
+	notnullcolumns = palloc0(sizeof(Bitmapset* ) * num_of_rtables);
+
+	/* build the targetlist_by_table */
+	foreach(lc, query->targetList)
+	{
+		TargetEntry *te = lfirst_node(TargetEntry, lc);
+		Expr *expr = te->expr;
+		Var *var;
+		Bitmapset **target_column_per_rel;
+		int target_attno;
+
+		if (!IsA(expr, Var))
+			continue;
+
+		var = (Var *)(expr);
+		if (var->varlevelsup != 0)
+			continue;
+
+		target_column_per_rel = &targetlist_by_table[var->varno - 1];
+		target_attno = var->varattno - FirstLowInvalidHeapAttributeNumber;
+
+		/*
+		 * for distinct On (..), we only count the field in .. rather than
+		 * all the entries in target list
+		 */
+		if (query->hasDistinctOn)
+		{
+			Index ref = te->ressortgroupref;
+			ListCell *lc;
+
+			/*
+			 * A fastpath to know if the targetEntry is in the distinctClause
+			 */
+			if (ref == 0)
+				continue;
+
+			/*
+			 * Even the ref is not zero, it may be in sort as well, so we
+			 * need dobule check.
+			 */
+			foreach(lc, query->distinctClause)
+			{
+				if (ref == lfirst_node(SortGroupClause, lc)->tleSortGroupRef)
+					*target_column_per_rel = bms_add_member(*target_column_per_rel,
+															target_attno);
+			}
+		}
+		else
+			*target_column_per_rel = bms_add_member(*target_column_per_rel,
+													target_attno);
+	}
+
+	/* find out nonnull columns from qual via find_nonnullable_vars */
+	foreach(lc, find_nonnullable_vars(query->jointree->quals))
+	{
+		Var *not_null_var;
+		Bitmapset **notnullcolumns_per_rel;
+		int notnull_attno;
+		if (!IsA(lfirst(lc), Var))
+			continue;
+		not_null_var = lfirst_node(Var, lc);
+		if (not_null_var->varno == INNER_VAR ||
+			not_null_var->varno == OUTER_VAR ||
+			not_null_var->varno == INDEX_VAR)
+			continue;
+		notnullcolumns_per_rel = &notnullcolumns[not_null_var->varno - 1];
+		notnull_attno = not_null_var->varattno - FirstLowInvalidHeapAttributeNumber;
+		*notnullcolumns_per_rel = bms_add_member(*notnullcolumns_per_rel,
+												 notnull_attno);
+	}
+
+	/* Check if each related rtable can yield a unique result set */
+	rel_idx = 0;
+	foreach(lc, query->rtable)
+	{
+		Relation relation;
+		TupleDesc desc;
+		RangeTblEntry *rte;
+		int attr_idx;
+
+		if (!bms_is_member(rel_idx+1, non_semi_anti_relids))
+			continue;
+
+		rte = lfirst_node(RangeTblEntry, lc);
+		Assert(rte->rtekind == RTE_RELATION);
+		Assert(rte->relid != InvalidOid);
+
+	    relation = relation_open(rte->relid, RowExclusiveLock);
+		desc = relation->rd_att;
+		attr_idx = 0;
+
+		/* Add the notnullcolumns based on catalog */
+		for(; attr_idx < desc->natts; attr_idx++)
+		{
+			int notnull_attno;
+			if (!desc->attrs[attr_idx].attnotnull)
+				continue;
+			notnull_attno = attr_idx + 1 - FirstLowInvalidHeapAttributeNumber;
+			notnullcolumns[rel_idx] = bms_add_member(notnullcolumns[rel_idx],
+													 notnull_attno);
+		}
+
+		/* check non-nullable in qual, only col is not null checked now */
+		if (!is_unique_result_already(relation,
+									  targetlist_by_table[rel_idx],
+									  notnullcolumns[rel_idx]))
+		{
+			RelationClose(relation);
+			goto ret;
+		}
+		RelationClose(relation);
+		rel_idx++;
+	}
+
+	should_distinct_elimination = true;
+
+ ret:
+	bms_array_free(notnullcolumns, num_of_rtables);
+	bms_array_free(targetlist_by_table, num_of_rtables);
+	bms_free(non_semi_anti_relids);
+
+	if (should_distinct_elimination)
+	{
+		query->distinctClause = NIL;
+		query->hasDistinctOn = false;
+	}
+}
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index df025a5a30..d8a76a2273 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -2346,6 +2346,8 @@ RelationDestroyRelation(Relation relation, bool remember_tupdesc)
 	bms_free(relation->rd_keyattr);
 	bms_free(relation->rd_pkattr);
 	bms_free(relation->rd_idattr);
+	if (relation->rd_plain_ukattrs)
+		bms_array_free(relation->rd_plain_ukattrs, relation->rd_plain_ukcount);
 	if (relation->rd_pubactions)
 		pfree(relation->rd_pubactions);
 	if (relation->rd_options)
@@ -4762,6 +4764,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
 	Bitmapset  *indexattrs;		/* indexed columns */
 	Bitmapset  *uindexattrs;	/* columns in unique indexes */
 	Bitmapset  *pkindexattrs;	/* columns in the primary index */
+	Bitmapset  **ukindexattrs = NULL; /* columns in the unique indexes */
 	Bitmapset  *idindexattrs;	/* columns in the replica identity */
 	List	   *indexoidlist;
 	List	   *newindexoidlist;
@@ -4769,6 +4772,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
 	Oid			relreplindex;
 	ListCell   *l;
 	MemoryContext oldcxt;
+	int plain_uk_index_count = 0, index_count = 0, indexno = 0;
 
 	/* Quick exit if we already computed the result. */
 	if (relation->rd_indexattr != NULL)
@@ -4826,6 +4830,9 @@ restart:
 	uindexattrs = NULL;
 	pkindexattrs = NULL;
 	idindexattrs = NULL;
+	index_count = list_length(indexoidlist);
+	ukindexattrs = palloc0(sizeof(Bitmapset *) * index_count);
+
 	foreach(l, indexoidlist)
 	{
 		Oid			indexOid = lfirst_oid(l);
@@ -4875,6 +4882,9 @@ restart:
 		/* Is this index the configured (or default) replica identity? */
 		isIDKey = (indexOid == relreplindex);
 
+		if (isKey)
+			plain_uk_index_count++;
+
 		/* Collect simple attribute references */
 		for (i = 0; i < indexDesc->rd_index->indnatts; i++)
 		{
@@ -4904,6 +4914,11 @@ restart:
 				if (isIDKey && i < indexDesc->rd_index->indnkeyatts)
 					idindexattrs = bms_add_member(idindexattrs,
 												  attrnum - FirstLowInvalidHeapAttributeNumber);
+
+				if (isKey)
+					ukindexattrs[indexno] = bms_add_member(ukindexattrs[indexno],
+														   attrnum - FirstLowInvalidHeapAttributeNumber);
+
 			}
 		}
 
@@ -4914,6 +4929,7 @@ restart:
 		pull_varattnos(indexPredicate, 1, &indexattrs);
 
 		index_close(indexDesc, AccessShareLock);
+		indexno++;
 	}
 
 	/*
@@ -4940,6 +4956,7 @@ restart:
 		bms_free(pkindexattrs);
 		bms_free(idindexattrs);
 		bms_free(indexattrs);
+		bms_array_free(ukindexattrs, index_count);
 
 		goto restart;
 	}
@@ -4953,6 +4970,8 @@ restart:
 	relation->rd_pkattr = NULL;
 	bms_free(relation->rd_idattr);
 	relation->rd_idattr = NULL;
+	bms_array_free(relation->rd_plain_ukattrs, relation->rd_plain_ukcount);
+	relation->rd_plain_ukattrs = NULL;
 
 	/*
 	 * Now save copies of the bitmaps in the relcache entry.  We intentionally
@@ -4966,6 +4985,8 @@ restart:
 	relation->rd_pkattr = bms_copy(pkindexattrs);
 	relation->rd_idattr = bms_copy(idindexattrs);
 	relation->rd_indexattr = bms_copy(indexattrs);
+	relation->rd_plain_ukattrs = bms_array_copy(ukindexattrs, index_count);
+	relation->rd_plain_ukcount = plain_uk_index_count;
 	MemoryContextSwitchTo(oldcxt);
 
 	/* We return our original working copy for caller to play with */
@@ -5618,6 +5639,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_keyattr = NULL;
 		rel->rd_pkattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_plain_ukattrs = NULL;
+		rel->rd_plain_ukcount = 0;
 		rel->rd_pubactions = NULL;
 		rel->rd_statvalid = false;
 		rel->rd_statlist = NIL;
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index e44f71e991..fa798dd564 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1064,6 +1064,16 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_distinct_elimination", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables plan-time and run-time unique elimination."),
+		    gettext_noop("Allows the query planner to remove the uncecessary distinct clause."), 
+			GUC_EXPLAIN
+		},
+		&enable_distinct_elimination,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index b7b18a0b68..ff30feb521 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -117,4 +117,6 @@ extern int	bms_prev_member(const Bitmapset *a, int prevbit);
 /* support for hashtables using Bitmapsets as keys: */
 extern uint32 bms_hash_value(const Bitmapset *a);
 
+extern Bitmapset **bms_array_copy(Bitmapset **bms_array, int len);
+extern void bms_array_free(Bitmapset **bms_array,  int len);
 #endif							/* BITMAPSET_H */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index cb012ba198..4fa5d32df6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_distinct_elimination;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 44ed04dd3f..7c5a6d65b6 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -120,6 +120,9 @@ typedef struct RelationData
 	Bitmapset  *rd_indexattr;	/* identifies columns used in indexes */
 	Bitmapset  *rd_keyattr;		/* cols that can be ref'd by foreign keys */
 	Bitmapset  *rd_pkattr;		/* cols included in primary key */
+	Bitmapset  **rd_plain_ukattrs;    /* cols included in the plain unique indexes,
+                                   only non-expression, non-partical columns are count */
+	int        rd_plain_ukcount;  /* the no. of uk count */
 	Bitmapset  *rd_idattr;		/* included in replica identity index */
 
 	PublicationActions *rd_pubactions;	/* publication actions */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..3f6595d53b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4433,17 +4433,17 @@ 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              
---------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct_2.out b/src/test/regress/expected/select_distinct_2.out
new file mode 100644
index 0000000000..28080ecc21
--- /dev/null
+++ b/src/test/regress/expected/select_distinct_2.out
@@ -0,0 +1,237 @@
+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: b, c, d, e
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+create unique index select_distinct_a_uk on select_distinct_a(c, d);
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: b, c, d, e
+   ->  Seq Scan on select_distinct_a
+         Filter: (c IS NOT NULL)
+(4 rows)
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null and d is not null;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: ((c IS NOT NULL) AND (d IS NOT NULL))
+(2 rows)
+
+explain select distinct d, e from select_distinct_a group by d, e;
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ HashAggregate  (cost=15.85..17.85 rows=200 width=8)
+   Group Key: d, e
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=390 width=8)
+(3 rows)
+
+create table select_distinct_b(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+explain (costs off) select distinct * from select_distinct_a a, select_distinct_b b;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_a a
+   ->  Materialize
+         ->  Seq Scan on select_distinct_b b
+(4 rows)
+
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (2, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (5, 'e', 'e', 0, 5);
+explain (costs off) select distinct a.c, a.d, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null order by 1;
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop
+   ->  Index Only Scan using select_distinct_a_uk on select_distinct_a a
+         Index Cond: (d IS NOT NULL)
+   ->  Materialize
+         ->  Seq Scan on select_distinct_b b
+(5 rows)
+
+-- left join
+explain
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a left join select_distinct_b b on (a.a = b.a)
+order by 1;
+                                                     QUERY PLAN                                                     
+--------------------------------------------------------------------------------------------------------------------
+ Sort  (cost=177.24..179.14 rows=760 width=176)
+   Sort Key: a.a
+   ->  Nested Loop Left Join  (cost=0.15..140.88 rows=760 width=176)
+         ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+         ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b b  (cost=0.15..0.31 rows=2 width=88)
+               Index Cond: (a = a.a)
+(6 rows)
+
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a left join select_distinct_b b on (a.a = b.a)
+order by 1;
+ a |          b           | a |          b           
+---+----------------------+---+----------------------
+ 1 | a                    | 1 | a                   
+ 2 | b                    |   | 
+ 3 | c                    |   | 
+(3 rows)
+
+-- full join
+explain
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a full outer join select_distinct_b b on (a.a = b.a)
+order by 1;
+                                       QUERY PLAN                                        
+-----------------------------------------------------------------------------------------
+ Sort  (cost=10000000096.63..10000000098.53 rows=760 width=176)
+   Sort Key: a.a
+   ->  Hash Full Join  (cost=10000000018.77..10000000060.26 rows=760 width=176)
+         Hash Cond: (a.a = b.a)
+         ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+         ->  Hash  (cost=13.90..13.90 rows=390 width=88)
+               ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=88)
+(7 rows)
+
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a full outer join select_distinct_b b on (a.a = b.a)
+order by 1;
+ a |          b           | a |          b           
+---+----------------------+---+----------------------
+ 1 | a                    | 1 | a                   
+ 2 | b                    |   | 
+ 3 | c                    |   | 
+   |                      | 5 | e                   
+   |                      | 4 | d                   
+(5 rows)
+
+-- Cartesian join
+explain (costs off) select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b order by 1;
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.b, a.c, b.a, b.b
+         ->  Nested Loop
+               ->  Seq Scan on select_distinct_a a
+               ->  Materialize
+                     ->  Seq Scan on select_distinct_b b
+(7 rows)
+
+select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b order by 1;
+          b           |          c           | a |          b           
+----------------------+----------------------+---+----------------------
+ a                    | a                    | 1 | a                   
+ a                    | a                    | 4 | d                   
+ a                    | a                    | 5 | e                   
+ b                    | A                    | 1 | a                   
+ b                    | A                    | 4 | d                   
+ b                    | A                    | 5 | e                   
+ c                    | c                    | 1 | a                   
+ c                    | c                    | 4 | d                   
+ c                    | c                    | 5 | e                   
+(9 rows)
+
+explain (costs off) select distinct a.d, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (d IS NOT NULL)
+(5 rows)
+
+-- Semi/anti join
+explain (costs off) select distinct a, b from select_distinct_a where a in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop Semi Join
+   ->  Seq Scan on select_distinct_a
+   ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b
+         Index Cond: (a = select_distinct_a.a)
+(4 rows)
+
+explain (costs off) select distinct a, b from select_distinct_a where a not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+-- group
+explain (costs off) select distinct a.d, b.a from select_distinct_a a, select_distinct_b b group by a.d, b.a;
+                    QUERY PLAN                     
+---------------------------------------------------
+ HashAggregate
+   Group Key: a.d, b.a
+   ->  Nested Loop
+         ->  Seq Scan on select_distinct_a a
+         ->  Materialize
+               ->  Seq Scan on select_distinct_b b
+(6 rows)
+
+-- If we have subquery on rangetable, we can't handle it now.
+explain (costs off) select distinct * from select_distinct_a a, (select a, max(b) as b from select_distinct_b group by a) b
+where a.a in (select a from select_distinct_b)
+and a.b = b.b;
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.a, a.b, a.c, a.d, a.e, select_distinct_b_1.a
+         ->  Nested Loop
+               Join Filter: (a.b = (max(select_distinct_b_1.b)))
+               ->  HashAggregate
+                     Group Key: select_distinct_b_1.a
+                     ->  Seq Scan on select_distinct_b select_distinct_b_1
+               ->  Materialize
+                     ->  Nested Loop Semi Join
+                           ->  Seq Scan on select_distinct_a a
+                           ->  Index Only Scan using select_distinct_b_pkey on select_distinct_b
+                                 Index Cond: (a = a.a)
+(13 rows)
+
+-- Distinct On
+explain (costs off) select distinct on(a) a, b from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+explain (costs off) select distinct on(a, b) a, b from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+create view v_distinct as select distinct a, b from select_distinct_a;
+explain select * from v_distinct;
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=390 width=88)
+(1 row)
+
+select * from v_distinct;
+ a |          b           
+---+----------------------
+ 1 | a                   
+ 2 | b                   
+ 3 | c                   
+(3 rows)
+
+drop view v_distinct;
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index a1c90eb905..e053214f9d 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -73,6 +73,7 @@ select name, setting from pg_settings where name like 'enable%';
               name              | setting 
 --------------------------------+---------
  enable_bitmapscan              | on
+ enable_distinct_elimination    | on
  enable_gathermerge             | on
  enable_hashagg                 | on
  enable_hashjoin                | on
@@ -89,7 +90,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(17 rows)
+(18 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/select_distinct_2.sql b/src/test/regress/sql/select_distinct_2.sql
new file mode 100644
index 0000000000..3d124462dc
--- /dev/null
+++ b/src/test/regress/sql/select_distinct_2.sql
@@ -0,0 +1,81 @@
+create table select_distinct_a(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+-- no node for distinct.
+explain (costs off) select distinct * from select_distinct_a;
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a;
+
+create unique index select_distinct_a_uk on select_distinct_a(c, d);
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null;
+
+explain (costs off) select distinct b,c,d,e from select_distinct_a where c is not null and d is not null;
+
+explain select distinct d, e from select_distinct_a group by d, e;
+
+
+create table select_distinct_b(a int, b char(20),  c char(20) not null,  d int, e int, primary key(a, b));
+
+explain (costs off) select distinct * from select_distinct_a a, select_distinct_b b;
+
+
+
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (2, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (5, 'e', 'e', 0, 5);
+
+explain (costs off) select distinct a.c, a.d, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null order by 1;
+
+
+-- left join
+explain
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a left join select_distinct_b b on (a.a = b.a)
+order by 1;
+
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a left join select_distinct_b b on (a.a = b.a)
+order by 1;
+
+-- full join
+explain
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a full outer join select_distinct_b b on (a.a = b.a)
+order by 1;
+
+select distinct a.a, a.b, b.a, b.b from select_distinct_a a full outer join select_distinct_b b on (a.a = b.a)
+order by 1;
+
+-- Cartesian join
+explain (costs off) select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b order by 1;
+
+select distinct a.b, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b order by 1;
+
+explain (costs off) select distinct a.d, a.c, b.a, b.b from select_distinct_a a, select_distinct_b b where a.d is not null;
+
+-- Semi/anti join
+explain (costs off) select distinct a, b from select_distinct_a where a in (select a from select_distinct_b);
+
+explain (costs off) select distinct a, b from select_distinct_a where a not in (select a from select_distinct_b);
+
+-- group
+explain (costs off) select distinct a.d, b.a from select_distinct_a a, select_distinct_b b group by a.d, b.a;
+
+-- If we have subquery on rangetable, we can't handle it now.
+explain (costs off) select distinct * from select_distinct_a a, (select a, max(b) as b from select_distinct_b group by a) b
+where a.a in (select a from select_distinct_b)
+and a.b = b.b;
+
+-- Distinct On
+explain (costs off) select distinct on(a) a, b from select_distinct_a;
+explain (costs off) select distinct on(a, b) a, b from select_distinct_a;
+
+create view v_distinct as select distinct a, b from select_distinct_a;
+
+explain select * from v_distinct;
+select * from v_distinct;
+
+drop view v_distinct;
+drop table select_distinct_a;
+drop table select_distinct_b;
+
+
-- 
2.20.1 (Apple Git-117)

From 1d4fb1214b3f6b216654825985fb3ef2c5e045e8 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Mon, 24 Feb 2020 20:16:42 +0800
Subject: [PATCH] Erase the distinctClause if the result is unique by
 definition

For a single relation, we can tell it by any one of the following
is true:
1. The pk is in the target list.
2. The uk is in the target list and the columns is not null
3. The columns in group-by clause is also in the target list

for relation join, we can tell it by:
if every relation in the jointree yield a unique result set,then
the final result is unique as well regardless the join method.
---
 src/backend/nodes/bitmapset.c                 |  18 ++
 src/backend/optimizer/path/costsize.c         |   1 +
 src/backend/optimizer/plan/analyzejoins.c     | 246 +++++++++++++++-
 src/backend/optimizer/plan/planner.c          |  28 ++
 src/backend/utils/misc/guc.c                  |  10 +
 src/include/nodes/bitmapset.h                 |   1 +
 src/include/optimizer/cost.h                  |   1 +
 src/include/optimizer/planmain.h              |   2 +
 src/test/regress/expected/aggregates.out      |  13 +-
 src/test/regress/expected/join.out            |  16 +-
 .../regress/expected/select_distinct_2.out    | 276 ++++++++++++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/sql/select_distinct_2.sql    |  84 ++++++
 13 files changed, 679 insertions(+), 20 deletions(-)
 create mode 100644 src/test/regress/expected/select_distinct_2.out
 create mode 100644 src/test/regress/sql/select_distinct_2.sql

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 648cc1a7eb..5cb6924a29 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1167,3 +1167,21 @@ bms_hash_value(const Bitmapset *a)
 	return DatumGetUInt32(hash_any((const unsigned char *) a->words,
 								   (lastword + 1) * sizeof(bitmapword)));
 }
+
+/*
+ * bms_array_free
+ *
+ * free the element in the array one by one, free the array as well at last
+ */
+void
+bms_array_free(Bitmapset **bms_array,  int len)
+{
+	int idx;
+	if (bms_array == NULL)
+		return;
+	for(idx = 0 ; idx < len; idx++)
+	{
+		bms_free(bms_array[idx]);
+	}
+	pfree(bms_array);
+}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index b5a0033721..dde16b5d44 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -138,6 +138,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_distinct_elimination = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index d0ff660284..a15ba80808 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -22,6 +22,7 @@
  */
 #include "postgres.h"
 
+#include "access/relation.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/joininfo.h"
@@ -30,7 +31,10 @@
 #include "optimizer/paths.h"
 #include "optimizer/planmain.h"
 #include "optimizer/tlist.h"
+#include "parser/parsetree.h"
 #include "utils/lsyscache.h"
+#include "utils/rel.h"
+#include "utils/relcache.h"
 
 /* local functions */
 static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
@@ -801,9 +805,248 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 		if (l == NULL)			/* had matches for all? */
 			return true;
 	}
+	return query_is_distinct_agg(query, colnos, opids);
+}
+
+/*
+ * scan_non_semi_anti_relids
+ *
+ * scan jointree to get non-semi/anti join rtindex.
+ */
+static void
+scan_non_semi_anti_relids(Node* jtnode, Relids* relids)
+{
+	if (jtnode == NULL)
+		return;
+
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*relids = bms_add_member(*relids, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			scan_non_semi_anti_relids(lfirst(l), relids);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		scan_non_semi_anti_relids(j->larg, relids);
+		if (j->jointype != JOIN_SEMI && j->jointype != JOIN_ANTI)
+		{
+			scan_non_semi_anti_relids(j->rarg, relids);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+
+}
+
+/*
+ * query_distinct_through_join
+ *
+ * check if the result is unique after the join. if every relation
+ * yields a unique result, the result is unique as well
+ */
+bool
+query_distinct_through_join(PlannerInfo *root, List *colnos, List *opids)
+{
+	RangeTblEntry *rte;
+	int rt_index;
+	Relids non_semi_anti_relids = NULL, tmp = NULL;
+	ListCell *lc1, *lc2;
+
+	/* be filled with metadata and find_nonnull_var */
+	Bitmapset **non_null_var_per_table = NULL;
+	Query *query = root->parse;
+	int max_len;
+
+    /* be used for relation_has_unique_for */
+	List **non_null_expr_per_table = NULL;
+	List **non_null_opids_per_table = NULL;
+	bool ret = true;
+	int idx = 0;
+
+	if (query->hasTargetSRFs)
+		return false;
 
+	/* remove the relids for right semi/anti */
+	scan_non_semi_anti_relids((Node*)query->jointree, &non_semi_anti_relids);
+
+	rt_index = -1;
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+		List *indexlist = root->simple_rel_array[rt_index]->indexlist;
+		bool found = false;
+		rte = rt_fetch(rt_index, query->rtable);
+
+		/* for the subquery, we just handle some simple case */
+		if (rte->rtekind == RTE_SUBQUERY)
+		{
+			Query *subquery = rte->subquery;
+			List *sub_opnos = NIL;
+			List *sub_opids = NIL;
+			if (!query_supports_distinctness(subquery))
+			{
+				ret = false;
+				goto done;
+			}
+
+			forboth(lc1, colnos, lc2, opids)
+			{
+				TargetEntry *tle = get_tle_by_resno(query->targetList, lfirst_int(lc1));
+				Var *var;
+				if (!IsA(tle->expr, Var))
+					continue;
+				var =(Var*)tle->expr;
+				if (var->varno == rt_index)
+				{
+					sub_opnos = lappend_int(sub_opnos, var->varattno);
+					sub_opids = lappend_oid(sub_opids, lfirst_oid(lc2));
+				}
+			}
+
+			if (query_is_distinct_for(subquery, sub_opnos, sub_opids))
+			{
+				tmp = bms_add_member(tmp, rt_index);
+			}
+			else
+			{
+				ret = false;
+				goto done;
+			}
+		}
+		else if (rte->rtekind != RTE_RELATION)
+		{
+			ret = false;
+			goto done;
+		}
+		else
+		{
+			foreach(lc1, indexlist)
+			{
+				IndexOptInfo *ind = lfirst_node(IndexOptInfo, lc1);
+				if (ind->unique && ind->immediate && (ind->indpred == NIL || ind->predOK))
+				{
+					found = true;
+					break;
+				}
+			}
+
+			/* if any relation has no pk/uk index, we return fast */
+			if (!found)
+			{
+				ret = false;
+				goto done;
+			}
+		}
+	}
+
+	non_semi_anti_relids = bms_del_members(non_semi_anti_relids, tmp);
 	/*
-	 * Otherwise, a set-returning function in the query's targetlist can
+	 * we know all the base rte is RTE_RELATION and every one has uk/pk index
+	 */
+
+	max_len = list_length(query->rtable) + 1;
+	non_null_var_per_table = palloc0(max_len * sizeof(Bitmapset *));
+	non_null_expr_per_table = palloc0(max_len * sizeof(Bitmapset *));
+	non_null_opids_per_table = palloc0(max_len * sizeof(Bitmapset *));
+
+	/* fill non_null_var_per_table with restrictinfo */
+	foreach(lc1, find_nonnullable_vars(query->jointree->quals))
+	{
+		Var *var;
+
+		if (!IsA(lfirst(lc1), Var))
+			continue;
+		var = lfirst_node(Var, lc1);
+		if (var->varno == INNER_VAR ||
+			var->varno == OUTER_VAR ||
+			var->varno == INDEX_VAR)
+			continue;
+		non_null_var_per_table[var->varno] = bms_add_member(
+			non_null_var_per_table[var->varno], var->varattno);
+	}
+
+	rt_index = -1;
+	/* fill non_null_var_per_table with catalog */
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+		int attr_idx = 0;
+		Relation relation;
+		TupleDesc desc;
+
+		rte = rt_fetch(rt_index, query->rtable);
+		relation =  relation_open(rte->relid, AccessShareLock);
+		desc = relation->rd_att;
+
+		for(; attr_idx < desc->natts; attr_idx++)
+		{
+			if (!desc->attrs[attr_idx].attnotnull)
+				continue;
+			non_null_var_per_table[rt_index] = bms_add_member(
+				non_null_var_per_table[rt_index], attr_idx+1);
+		}
+		relation_close(relation, AccessShareLock);
+	}
+
+	/* fiter all the colnos and opids which is not null */
+	forboth(lc1, colnos, lc2, opids)
+	{
+		int colno = lfirst_int(lc1);
+		TargetEntry *tle = get_tle_by_resno(query->targetList, colno);
+		Var *var = NULL;
+		/* We don't know the varno if the target tle->expr is not a Var */
+		if (!IsA(tle->expr, Var))
+			continue;
+		var = (Var *)tle->expr;
+		if (!bms_is_member(var->varattno, non_null_var_per_table[var->varno]))
+			continue;
+		non_null_expr_per_table[var->varno] = lappend(
+			non_null_expr_per_table[var->varno], tle->expr);
+		non_null_opids_per_table[var->varno] = lappend_oid(
+			non_null_opids_per_table[var->varno], lfirst_oid(lc2));
+	}
+
+	rt_index = -1;
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+
+		/* if any one can't yield a unique result, we return fast */
+		if (!relation_has_unique_index_for(root, root->simple_rel_array[rt_index],
+										   NIL,
+										   non_null_expr_per_table[rt_index],
+										   non_null_opids_per_table[rt_index]))
+		{
+			ret = false;
+			goto done;
+		}
+	}
+done:
+	bms_array_free(non_null_var_per_table, max_len);
+	for(idx = 0; idx < max_len; idx++)
+	{
+		list_free(non_null_expr_per_table[idx]);
+		list_free(non_null_opids_per_table[idx]);
+	}
+	return ret;
+}
+
+bool
+query_is_distinct_agg(Query *query, List *colnos, List *opids)
+{
+	ListCell   *l;
+	Oid			opid;
+
+	/*
+	 * a set-returning function in the query's targetlist can
 	 * result in returning duplicate rows, despite any grouping that might
 	 * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
 	 * columns, it would be safe because they'd be expanded before grouping.
@@ -901,7 +1144,6 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 				return true;
 		}
 	}
-
 	/*
 	 * XXX Are there any other cases in which we can easily see the result
 	 * must be distinct?
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..690fab676c 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -22,8 +22,10 @@
 #include "access/htup_details.h"
 #include "access/parallel.h"
 #include "access/sysattr.h"
+#include "access/relation.h"
 #include "access/table.h"
 #include "access/xact.h"
+#include "catalog/index.h"
 #include "catalog/pg_constraint.h"
 #include "catalog/pg_inherits.h"
 #include "catalog/pg_proc.h"
@@ -35,6 +37,7 @@
 #include "lib/bipartite_match.h"
 #include "lib/knapsack.h"
 #include "miscadmin.h"
+#include "nodes/bitmapset.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #ifdef OPTIMIZER_DEBUG
@@ -64,6 +67,8 @@
 #include "utils/rel.h"
 #include "utils/selfuncs.h"
 #include "utils/syscache.h"
+#include "utils/typcache.h"
+
 
 /* GUC parameters */
 double		cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
@@ -4737,6 +4742,29 @@ create_distinct_paths(PlannerInfo *root,
 	Path	   *path;
 	ListCell   *lc;
 
+	if (enable_distinct_elimination)
+	{
+		List *colnos = NIL;
+		List *opnos = NIL;
+		ListCell *lc;
+
+		Assert(parse->distinctClause != NIL);
+
+		foreach(lc, parse->distinctClause)
+		{
+			SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
+			int idx = sgc->tleSortGroupRef;
+			TargetEntry *tle = get_tle_by_resno(parse->targetList, idx);
+			if (tle->resjunk)
+				continue;
+			colnos = lappend_int(colnos, idx);
+			opnos = lappend_oid(opnos, sgc->eqop);
+		}
+
+		if (query_is_distinct_agg(parse, colnos, opnos) ||
+			query_distinct_through_join(root, colnos, opnos))
+			return input_rel;
+	}
 	/* For now, do all work in the (DISTINCT, NULL) upperrel */
 	distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
 
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index e44f71e991..fa798dd564 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1064,6 +1064,16 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_distinct_elimination", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables plan-time and run-time unique elimination."),
+		    gettext_noop("Allows the query planner to remove the uncecessary distinct clause."), 
+			GUC_EXPLAIN
+		},
+		&enable_distinct_elimination,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index b7b18a0b68..5d6f04ffa9 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -117,4 +117,5 @@ extern int	bms_prev_member(const Bitmapset *a, int prevbit);
 /* support for hashtables using Bitmapsets as keys: */
 extern uint32 bms_hash_value(const Bitmapset *a);
 
+extern void bms_array_free(Bitmapset **bms_array,  int len);
 #endif							/* BITMAPSET_H */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index cb012ba198..4fa5d32df6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_distinct_elimination;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index eab486a621..ebd4f24577 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -100,6 +100,8 @@ extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
 extern void reduce_unique_semijoins(PlannerInfo *root);
 extern bool query_supports_distinctness(Query *query);
 extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
+extern bool query_is_distinct_agg(Query *query, List *colnos, List *opids);
+extern bool query_distinct_through_join(PlannerInfo *root, List *colnos, List *opids);
 extern bool innerrel_is_unique(PlannerInfo *root,
 							   Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel,
 							   JoinType jointype, List *restrictlist, bool force_cache);
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index f457b5b150..6712571578 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -870,14 +870,12 @@ explain (costs off)
   select distinct max(unique2) from tenk1;
                              QUERY PLAN                              
 ---------------------------------------------------------------------
- HashAggregate
-   Group Key: $0
+ Result
    InitPlan 1 (returns $0)
      ->  Limit
            ->  Index Only Scan Backward using tenk1_unique2 on tenk1
                  Index Cond: (unique2 IS NOT NULL)
-   ->  Result
-(7 rows)
+(5 rows)
 
 select distinct max(unique2) from tenk1;
  max  
@@ -1036,7 +1034,7 @@ explain (costs off)
   select distinct min(f1), max(f1) from minmaxtest;
                                          QUERY PLAN                                          
 ---------------------------------------------------------------------------------------------
- Unique
+ Result
    InitPlan 1 (returns $0)
      ->  Limit
            ->  Merge Append
@@ -1059,10 +1057,7 @@ explain (costs off)
                  ->  Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest_8
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest_9
-   ->  Sort
-         Sort Key: ($0), ($1)
-         ->  Result
-(26 rows)
+(23 rows)
 
 select distinct min(f1), max(f1) from minmaxtest;
  min | max 
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..3f6595d53b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4433,17 +4433,17 @@ 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              
---------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct_2.out b/src/test/regress/expected/select_distinct_2.out
new file mode 100644
index 0000000000..2ece95a806
--- /dev/null
+++ b/src/test/regress/expected/select_distinct_2.out
@@ -0,0 +1,276 @@
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: uk1, uk2
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 > 1)
+(2 rows)
+
+-- distinct erased due to group by
+explain select distinct e from select_distinct_a group by e;
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ HashAggregate  (cost=14.88..16.88 rows=200 width=4)
+   Group Key: e
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=390 width=4)
+(3 rows)
+
+-- distinct erased due to the restirctinfo
+explain select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Index Scan using select_distinct_a_pkey on select_distinct_a  (cost=0.15..8.17 rows=1 width=84)
+   Index Cond: ((pk1 = 1) AND (pk2 = 'c'::bpchar))
+(2 rows)
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (uk2 IS NOT NULL)
+(5 rows)
+
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+         uk1          | uk2 |         pk1          | pk2 
+----------------------+-----+----------------------+-----
+ a                    |   0 | a                    |   0
+ a                    |   0 | d                    |   0
+ a                    |   0 | e                    |   0
+ A                    |   0 | a                    |   0
+ A                    |   0 | d                    |   0
+ A                    |   0 | e                    |   0
+ c                    |   0 | a                    |   0
+ c                    |   0 | d                    |   0
+ c                    |   0 | e                    |   0
+(9 rows)
+
+-- left join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+                                    QUERY PLAN                                     
+-----------------------------------------------------------------------------------
+ Nested Loop Left Join  (cost=0.00..2310.28 rows=760 width=176)
+   Join Filter: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+   ->  Materialize  (cost=0.00..15.85 rows=390 width=92)
+         ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=92)
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+(5 rows)
+
+-- right join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+                                                  QUERY PLAN                                                  
+--------------------------------------------------------------------------------------------------------------
+ Nested Loop Left Join  (cost=0.15..140.88 rows=760 width=176)
+   ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=92)
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a a  (cost=0.15..0.31 rows=2 width=88)
+         Index Cond: (pk1 = b.a)
+(4 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+     |                      | d                    |   0
+(5 rows)
+
+-- full join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                                    QUERY PLAN                                     
+-----------------------------------------------------------------------------------
+ Hash Full Join  (cost=10000000018.77..10000000060.26 rows=760 width=176)
+   Hash Cond: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+   ->  Hash  (cost=13.90..13.90 rows=390 width=92)
+         ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=92)
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+     |                      | d                    |   0
+(6 rows)
+
+-- distinct can't be erased since b.pk2 is missed
+explain select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                                          QUERY PLAN                                           
+-----------------------------------------------------------------------------------------------
+ Unique  (cost=10000000096.63..10000000104.23 rows=760 width=172)
+   ->  Sort  (cost=10000000096.63..10000000098.53 rows=760 width=172)
+         Sort Key: a.pk1, a.pk2, b.pk1
+         ->  Hash Full Join  (cost=10000000018.77..10000000060.26 rows=760 width=172)
+               Hash Cond: (a.pk1 = b.a)
+               ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+               ->  Hash  (cost=13.90..13.90 rows=390 width=88)
+                     ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=88)
+(8 rows)
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+-- we also can handle some limited subquery
+explain select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+                                                QUERY PLAN                                                
+----------------------------------------------------------------------------------------------------------
+ Nested Loop  (cost=15.02..107.38 rows=390 width=184)
+   ->  HashAggregate  (cost=14.88..16.88 rows=200 width=4)
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b  (cost=0.00..13.90 rows=390 width=4)
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a  (cost=0.15..0.42 rows=2 width=180)
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+explain select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+                                                QUERY PLAN                                                
+----------------------------------------------------------------------------------------------------------
+ Nested Loop  (cost=15.02..107.38 rows=390 width=184)
+   ->  HashAggregate  (cost=14.88..16.88 rows=200 width=4)
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b  (cost=0.00..13.90 rows=390 width=4)
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a  (cost=0.15..0.42 rows=2 width=180)
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: pk1
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain select * from distinct_v1;
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain select * from distinct_v1;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ HashAggregate  (cost=15.84..17.84 rows=200 width=88)
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+alter table select_distinct_a alter column uk1 set not null;
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain execute pt;
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain execute pt;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ HashAggregate  (cost=15.84..17.84 rows=200 width=88)
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index a1c90eb905..e053214f9d 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -73,6 +73,7 @@ select name, setting from pg_settings where name like 'enable%';
               name              | setting 
 --------------------------------+---------
  enable_bitmapscan              | on
+ enable_distinct_elimination    | on
  enable_gathermerge             | on
  enable_hashagg                 | on
  enable_hashjoin                | on
@@ -89,7 +90,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(17 rows)
+(18 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/select_distinct_2.sql b/src/test/regress/sql/select_distinct_2.sql
new file mode 100644
index 0000000000..2fc54e7e36
--- /dev/null
+++ b/src/test/regress/sql/select_distinct_2.sql
@@ -0,0 +1,84 @@
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+
+-- distinct erased due to group by
+explain select distinct e from select_distinct_a group by e;
+
+-- distinct erased due to the restirctinfo
+explain select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+
+
+-- left join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+
+-- right join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- full join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- distinct can't be erased since b.pk2 is missed
+explain select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+
+-- we also can handle some limited subquery
+explain select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+
+explain select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 set not null;
+
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain execute pt;
+alter table select_distinct_a alter column uk1 drop not null;
+explain execute pt;
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
-- 
2.21.0

From 9449c09688d542c4dc201ee866f67d67304cff98 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Wed, 4 Mar 2020 14:33:56 +0800
Subject: [PATCH v2] [PATCH] Erase the distinct path if the result is unique by
 catalog

For a single relation, we can tell it by any one of the following
is true:
1. The pk is in the target list.
2. The uk is in the target list and the columns is not null
3. The columns in group-by clause is also in the target list

for relation join, we can tell it by:
if every relation in the jointree yield a unique result set,then
the final result is unique as well regardless the join method.
---
 .../postgres_fdw/expected/postgres_fdw.out    |  28 +-
 src/backend/optimizer/path/costsize.c         |   1 +
 src/backend/optimizer/plan/analyzejoins.c     | 184 +++++++++++-
 src/backend/optimizer/plan/planner.c          |  27 ++
 src/backend/optimizer/util/plancat.c          |   9 +
 src/backend/utils/misc/guc.c                  |  10 +
 src/include/nodes/pathnodes.h                 |   1 +
 src/include/optimizer/cost.h                  |   1 +
 src/include/optimizer/planmain.h              |   2 +
 src/test/regress/expected/aggregates.out      |  13 +-
 src/test/regress/expected/join.out            |  16 +-
 src/test/regress/expected/select_distinct.out | 276 ++++++++++++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/sql/select_distinct.sql      |  84 ++++++
 14 files changed, 619 insertions(+), 36 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 84fd3ad2e0..215f10bf7d 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2902,22 +2902,20 @@ select sum(c1%3), sum(distinct c1%3 order by c1%3) filter (where c1%3 < 2), c2 f
 -- Outer query is aggregation query
 explain (verbose, costs off)
 select distinct (select count(*) filter (where t2.c2 = 6 and t2.c1 < 10) from ft1 t1 where t1.c1 = 6) from ft2 t2 where t2.c2 % 6 = 0 order by 1;
-                                                          QUERY PLAN                                                          
-------------------------------------------------------------------------------------------------------------------------------
- Unique
+                                                       QUERY PLAN                                                       
+------------------------------------------------------------------------------------------------------------------------
+ Sort
    Output: ((SubPlan 1))
-   ->  Sort
-         Output: ((SubPlan 1))
-         Sort Key: ((SubPlan 1))
-         ->  Foreign Scan
-               Output: (SubPlan 1)
-               Relations: Aggregate on (public.ft2 t2)
-               Remote SQL: SELECT count(*) FILTER (WHERE ((c2 = 6) AND ("C 1" < 10))) FROM "S 1"."T 1" WHERE (((c2 % 6) = 0))
-               SubPlan 1
-                 ->  Foreign Scan on public.ft1 t1
-                       Output: (count(*) FILTER (WHERE ((t2.c2 = 6) AND (t2.c1 < 10))))
-                       Remote SQL: SELECT NULL FROM "S 1"."T 1" WHERE (("C 1" = 6))
-(13 rows)
+   Sort Key: ((SubPlan 1))
+   ->  Foreign Scan
+         Output: (SubPlan 1)
+         Relations: Aggregate on (public.ft2 t2)
+         Remote SQL: SELECT count(*) FILTER (WHERE ((c2 = 6) AND ("C 1" < 10))) FROM "S 1"."T 1" WHERE (((c2 % 6) = 0))
+         SubPlan 1
+           ->  Foreign Scan on public.ft1 t1
+                 Output: (count(*) FILTER (WHERE ((t2.c2 = 6) AND (t2.c1 < 10))))
+                 Remote SQL: SELECT NULL FROM "S 1"."T 1" WHERE (("C 1" = 6))
+(11 rows)
 
 select distinct (select count(*) filter (where t2.c2 = 6 and t2.c1 < 10) from ft1 t1 where t1.c1 = 6) from ft2 t2 where t2.c2 % 6 = 0 order by 1;
  count 
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index b5a0033721..dde16b5d44 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -138,6 +138,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_distinct_elimination = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index d0ff660284..dee152af29 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -30,6 +30,7 @@
 #include "optimizer/paths.h"
 #include "optimizer/planmain.h"
 #include "optimizer/tlist.h"
+#include "parser/parsetree.h"
 #include "utils/lsyscache.h"
 
 /* local functions */
@@ -47,7 +48,8 @@ static bool is_innerrel_unique_for(PlannerInfo *root,
 								   RelOptInfo *innerrel,
 								   JoinType jointype,
 								   List *restrictlist);
-
+static void transform_colno_for_subquery(Query *query, List *colnos, List *opids,
+										List **sub_colnos, List **sub_opids);
 
 /*
  * remove_useless_joins
@@ -801,9 +803,18 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 		if (l == NULL)			/* had matches for all? */
 			return true;
 	}
+	return query_is_distinct_agg(query, colnos, opids);
+}
+
+
+bool
+query_is_distinct_agg(Query *query, List *colnos, List *opids)
+{
+	ListCell   *l;
+	Oid			opid;
 
 	/*
-	 * Otherwise, a set-returning function in the query's targetlist can
+	 * a set-returning function in the query's targetlist can
 	 * result in returning duplicate rows, despite any grouping that might
 	 * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
 	 * columns, it would be safe because they'd be expanded before grouping.
@@ -901,7 +912,6 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 				return true;
 		}
 	}
-
 	/*
 	 * XXX Are there any other cases in which we can easily see the result
 	 * must be distinct?
@@ -913,6 +923,174 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 	return false;
 }
 
+/*
+ * scan_non_semi_anti_relids
+ *
+ * Scan jointree to get rid of right table of semi/anti join rtindex.
+ */
+static void
+scan_non_semi_anti_relids(Node* jtnode, Relids* relids)
+{
+	if (jtnode == NULL)
+		return;
+
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*relids = bms_add_member(*relids, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			scan_non_semi_anti_relids(lfirst(l), relids);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		scan_non_semi_anti_relids(j->larg, relids);
+		if (j->jointype != JOIN_SEMI && j->jointype != JOIN_ANTI)
+		{
+			scan_non_semi_anti_relids(j->rarg, relids);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+
+}
+
+/*
+ * transform_colno_for_subquery
+ */
+static void
+transform_colno_for_subquery(Query *query, List *colnos, List *opids,
+							List **sub_colnos, List **sub_opids)
+{
+	ListCell *lc1, *lc2;
+	TargetEntry *tle;
+
+	forboth(lc1, colnos, lc2, opids)
+	{
+		tle = get_tle_by_resno(query->targetList, lfirst_int(lc1));
+		Assert(IsA(tle->expr, Var));
+		*sub_colnos = lappend_int(*sub_colnos, ((Var*)tle->expr)->varattno);
+		*sub_opids = lappend_oid(*sub_opids, lfirst_oid(lc2));
+	}
+}
+
+/*
+ * query_distinct_through_join
+ * If every relation yields a unique result in the join, so the join result
+ * is unqiue as well. We need to distinguish right table in semi/anti
+ * join, which we don't care.
+ */
+bool
+query_distinct_through_join(PlannerInfo *root, List *colnos, List *opids)
+{
+	Query *query = root->parse;
+	Relids non_semi_anti_relids = NULL;
+
+    /* Used for relation_has_unique_for */
+	List **non_null_expr_per_table = NULL;
+	/* Used for query_is_distinct_for */
+	List **non_null_colno_per_table = NULL;
+	/* Used for both as above*/
+	List **non_null_opids_per_table = NULL;
+	/* Not null info from restrictinfo and catalog */
+	Bitmapset **non_null_varno_per_table = NULL;
+
+	int rt_index;
+	ListCell *lc1, *lc2;
+	RangeTblEntry *rte;
+	RelOptInfo *rel;
+	int max_rt_index = list_length(query->rtable) + 1;
+	
+	/* Remove the relids for the right table in semi/anti join */
+	scan_non_semi_anti_relids((Node*)query->jointree, &non_semi_anti_relids);
+
+	non_null_varno_per_table = palloc0(max_rt_index * sizeof(Bitmapset *));
+
+	foreach(lc1, find_nonnullable_vars(query->jointree->quals))
+	{
+		Var *var;
+		if (!IsA(lfirst(lc1), Var))
+			continue;
+		var = lfirst_node(Var, lc1);
+		if (var->varno == INNER_VAR ||
+			var->varno == OUTER_VAR ||
+			var->varno == INDEX_VAR)
+			continue;
+		non_null_varno_per_table[var->varno] = bms_add_member(
+			non_null_varno_per_table[var->varno], var->varattno);
+	}
+
+	/* Add the non null info in catalog */
+	rt_index = -1;
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+		non_null_varno_per_table[rt_index] = bms_join(non_null_varno_per_table[rt_index],
+													  root->simple_rel_array[rt_index]->not_null_cols_relids);
+	}
+
+	non_null_expr_per_table = palloc0(max_rt_index * sizeof(List *));
+	non_null_opids_per_table = palloc0(max_rt_index * sizeof(List *));
+	non_null_colno_per_table = palloc0(max_rt_index * sizeof(List *));
+
+	/* Filter out the nullable columns and split them per table*/
+	forboth(lc1, colnos, lc2, opids)
+	{
+		int colno = lfirst_int(lc1);
+		TargetEntry *tle = get_tle_by_resno(query->targetList, colno);
+		Var *var = NULL;
+		if (!IsA(tle->expr, Var))
+			continue;
+		var = (Var *)tle->expr;
+		if (!bms_is_member(var->varattno, non_null_varno_per_table[var->varno]))
+			continue;
+		non_null_expr_per_table[var->varno] = lappend(
+			non_null_expr_per_table[var->varno], tle->expr);
+		non_null_opids_per_table[var->varno] = lappend_oid(
+			non_null_opids_per_table[var->varno], lfirst_oid(lc2));
+		non_null_colno_per_table[var->varno] = lappend_int(
+			non_null_colno_per_table[var->varno],
+			colno);
+	}
+
+	/* Check if every relation yields a unqiue result, if anyone doesn't return false */
+	rt_index = -1;
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+		rte = root->simple_rte_array[rt_index];
+		rel = root->simple_rel_array[rt_index];
+		if (rte->rtekind == RTE_RELATION &&
+			relation_has_unique_index_for(root, rel, NIL,
+										  non_null_expr_per_table[rt_index],
+										  non_null_opids_per_table[rt_index]))
+			continue;
+		if (rte->rtekind == RTE_SUBQUERY &&
+			query_supports_distinctness(rte->subquery))
+		{
+			List *subquery_colnos = NIL;
+			List *subquery_opids = NIL;
+			transform_colno_for_subquery(root->parse,
+										non_null_colno_per_table[rt_index],
+										non_null_opids_per_table[rt_index],
+										&subquery_colnos,
+										&subquery_opids);
+			if (query_is_distinct_for(rte->subquery, subquery_colnos, subquery_opids))
+				continue;
+			return false;
+		}
+		return false;
+	}
+	return true;
+}
+
 /*
  * distinct_col_search - subroutine for query_is_distinct_for
  *
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..9d56e6c88e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4737,6 +4737,33 @@ create_distinct_paths(PlannerInfo *root,
 	Path	   *path;
 	ListCell   *lc;
 
+	if (enable_distinct_elimination)
+	{
+		List *colnos = NIL;
+		List *opnos = NIL;
+		ListCell *lc;
+
+		Assert(parse->distinctClause != NIL);
+
+		foreach(lc, parse->distinctClause)
+		{
+			SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
+			int idx = sgc->tleSortGroupRef;
+			TargetEntry *tle = get_tle_by_resno(parse->targetList, idx);
+			if (tle->resjunk)
+				continue;
+			/* even column x is not null, f(x) may be null as well, so ignore it */
+			if (!IsA(tle->expr, Var))
+				continue;
+			colnos = lappend_int(colnos, idx);
+			opnos = lappend_oid(opnos, sgc->eqop);
+		}
+
+		if ((query_supports_distinctness(parse)
+			 && query_is_distinct_agg(parse, colnos, opnos)) ||
+			query_distinct_through_join(root, colnos, opnos))
+			return input_rel;
+	}
 	/* For now, do all work in the (DISTINCT, NULL) upperrel */
 	distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
 
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index d82fc5ab8b..e57b456d9b 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -117,6 +117,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	int        i;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -460,6 +461,14 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (inhparent && relation->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
 		set_relation_partition_info(root, rel, relation);
 
+	Assert(rel->not_null_cols_relids == NULL);
+	for(i = 0; i < relation->rd_att->natts;  i++)
+	{
+		if (!relation->rd_att->attrs[i].attnotnull)
+			continue;
+		rel->not_null_cols_relids = bms_add_member(rel->not_null_cols_relids, i+1);
+	}
+
 	table_close(relation, NoLock);
 
 	/*
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index e44f71e991..fa798dd564 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1064,6 +1064,16 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_distinct_elimination", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables plan-time and run-time unique elimination."),
+		    gettext_noop("Allows the query planner to remove the uncecessary distinct clause."), 
+			GUC_EXPLAIN
+		},
+		&enable_distinct_elimination,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3d3be197e0..51db013f5d 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -687,6 +687,7 @@ typedef struct RelOptInfo
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	int			rel_parallel_workers;	/* wanted number of parallel workers */
+	Relids     not_null_cols_relids; /* not null cols by catalogs,starts with 1 */
 
 	/* Information about foreign tables and foreign joins */
 	Oid			serverid;		/* identifies server for the table or join */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index cb012ba198..4fa5d32df6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_distinct_elimination;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index eab486a621..ebd4f24577 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -100,6 +100,8 @@ extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
 extern void reduce_unique_semijoins(PlannerInfo *root);
 extern bool query_supports_distinctness(Query *query);
 extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
+extern bool query_is_distinct_agg(Query *query, List *colnos, List *opids);
+extern bool query_distinct_through_join(PlannerInfo *root, List *colnos, List *opids);
 extern bool innerrel_is_unique(PlannerInfo *root,
 							   Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel,
 							   JoinType jointype, List *restrictlist, bool force_cache);
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index f457b5b150..6712571578 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -870,14 +870,12 @@ explain (costs off)
   select distinct max(unique2) from tenk1;
                              QUERY PLAN                              
 ---------------------------------------------------------------------
- HashAggregate
-   Group Key: $0
+ Result
    InitPlan 1 (returns $0)
      ->  Limit
            ->  Index Only Scan Backward using tenk1_unique2 on tenk1
                  Index Cond: (unique2 IS NOT NULL)
-   ->  Result
-(7 rows)
+(5 rows)
 
 select distinct max(unique2) from tenk1;
  max  
@@ -1036,7 +1034,7 @@ explain (costs off)
   select distinct min(f1), max(f1) from minmaxtest;
                                          QUERY PLAN                                          
 ---------------------------------------------------------------------------------------------
- Unique
+ Result
    InitPlan 1 (returns $0)
      ->  Limit
            ->  Merge Append
@@ -1059,10 +1057,7 @@ explain (costs off)
                  ->  Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest_8
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest_9
-   ->  Sort
-         Sort Key: ($0), ($1)
-         ->  Result
-(26 rows)
+(23 rows)
 
 select distinct min(f1), max(f1) from minmaxtest;
  min | max 
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..3f6595d53b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4433,17 +4433,17 @@ 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              
---------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index f3696c6d1d..73729c8606 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -244,3 +244,279 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
  t
 (1 row)
 
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: uk1, uk2
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 > 1)
+(2 rows)
+
+-- distinct erased due to group by
+explain select distinct e from select_distinct_a group by e;
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ HashAggregate  (cost=14.88..16.88 rows=200 width=4)
+   Group Key: e
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=390 width=4)
+(3 rows)
+
+-- distinct erased due to the restirctinfo
+explain select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Index Scan using select_distinct_a_pkey on select_distinct_a  (cost=0.15..8.17 rows=1 width=84)
+   Index Cond: ((pk1 = 1) AND (pk2 = 'c'::bpchar))
+(2 rows)
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (uk2 IS NOT NULL)
+(5 rows)
+
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+         uk1          | uk2 |         pk1          | pk2 
+----------------------+-----+----------------------+-----
+ a                    |   0 | a                    |   0
+ a                    |   0 | d                    |   0
+ a                    |   0 | e                    |   0
+ A                    |   0 | a                    |   0
+ A                    |   0 | d                    |   0
+ A                    |   0 | e                    |   0
+ c                    |   0 | a                    |   0
+ c                    |   0 | d                    |   0
+ c                    |   0 | e                    |   0
+(9 rows)
+
+-- left join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+                                    QUERY PLAN                                     
+-----------------------------------------------------------------------------------
+ Nested Loop Left Join  (cost=0.00..2310.28 rows=760 width=176)
+   Join Filter: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+   ->  Materialize  (cost=0.00..15.85 rows=390 width=92)
+         ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=92)
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+(5 rows)
+
+-- right join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+                                                  QUERY PLAN                                                  
+--------------------------------------------------------------------------------------------------------------
+ Nested Loop Left Join  (cost=0.15..140.88 rows=760 width=176)
+   ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=92)
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a a  (cost=0.15..0.31 rows=2 width=88)
+         Index Cond: (pk1 = b.a)
+(4 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+     |                      | d                    |   0
+(5 rows)
+
+-- full join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                                    QUERY PLAN                                     
+-----------------------------------------------------------------------------------
+ Hash Full Join  (cost=10000000018.77..10000000060.26 rows=760 width=176)
+   Hash Cond: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+   ->  Hash  (cost=13.90..13.90 rows=390 width=92)
+         ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=92)
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+     |                      | d                    |   0
+(6 rows)
+
+-- distinct can't be erased since b.pk2 is missed
+explain select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                                          QUERY PLAN                                           
+-----------------------------------------------------------------------------------------------
+ Unique  (cost=10000000096.63..10000000104.23 rows=760 width=172)
+   ->  Sort  (cost=10000000096.63..10000000098.53 rows=760 width=172)
+         Sort Key: a.pk1, a.pk2, b.pk1
+         ->  Hash Full Join  (cost=10000000018.77..10000000060.26 rows=760 width=172)
+               Hash Cond: (a.pk1 = b.a)
+               ->  Seq Scan on select_distinct_a a  (cost=0.00..13.90 rows=390 width=88)
+               ->  Hash  (cost=13.90..13.90 rows=390 width=88)
+                     ->  Seq Scan on select_distinct_b b  (cost=0.00..13.90 rows=390 width=88)
+(8 rows)
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+-- we also can handle some limited subquery
+explain select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+                                                QUERY PLAN                                                
+----------------------------------------------------------------------------------------------------------
+ Nested Loop  (cost=15.02..107.38 rows=390 width=184)
+   ->  HashAggregate  (cost=14.88..16.88 rows=200 width=4)
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b  (cost=0.00..13.90 rows=390 width=4)
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a  (cost=0.15..0.42 rows=2 width=180)
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+explain select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+                                                QUERY PLAN                                                
+----------------------------------------------------------------------------------------------------------
+ Nested Loop  (cost=15.02..107.38 rows=390 width=184)
+   ->  HashAggregate  (cost=14.88..16.88 rows=200 width=4)
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b  (cost=0.00..13.90 rows=390 width=4)
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a  (cost=0.15..0.42 rows=2 width=180)
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: pk1
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain select * from distinct_v1;
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain select * from distinct_v1;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ HashAggregate  (cost=15.84..17.84 rows=200 width=88)
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+alter table select_distinct_a alter column uk1 set not null;
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain execute pt;
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain execute pt;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ HashAggregate  (cost=15.84..17.84 rows=200 width=88)
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a  (cost=0.00..13.90 rows=388 width=88)
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index a1c90eb905..e053214f9d 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -73,6 +73,7 @@ select name, setting from pg_settings where name like 'enable%';
               name              | setting 
 --------------------------------+---------
  enable_bitmapscan              | on
+ enable_distinct_elimination    | on
  enable_gathermerge             | on
  enable_hashagg                 | on
  enable_hashjoin                | on
@@ -89,7 +90,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(17 rows)
+(18 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index a605e86449..813361ad89 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -73,3 +73,87 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
 SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
 SELECT 2 IS NOT DISTINCT FROM null as "no";
 SELECT null IS NOT DISTINCT FROM null as "yes";
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+
+-- distinct erased due to group by
+explain select distinct e from select_distinct_a group by e;
+
+-- distinct erased due to the restirctinfo
+explain select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+
+
+-- left join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+
+-- right join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- full join
+explain select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- distinct can't be erased since b.pk2 is missed
+explain select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+
+-- we also can handle some limited subquery
+explain select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+
+explain select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 set not null;
+
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain execute pt;
+alter table select_distinct_a alter column uk1 drop not null;
+explain execute pt;
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
-- 
2.21.0

From 8c5deb1b79d960502f5878ee8750f95ad50d1e74 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Wed, 4 Mar 2020 14:33:56 +0800
Subject: [PATCH v3] [PATCH] Erase the distinct path if the result is unique by
 catalog

For a single relation, we can tell it by any one of the following
is true:
1. The pk is in the target list.
2. The uk is in the target list and the columns is not null
3. The columns in group-by clause is also in the target list

for relation join, we can tell it by:
if every relation in the jointree yield a unique result set,then
the final result is unique as well regardless the join method.
---
 .../postgres_fdw/expected/postgres_fdw.out    |  28 +-
 src/backend/optimizer/path/costsize.c         |   1 +
 src/backend/optimizer/plan/analyzejoins.c     | 184 +++++++++++-
 src/backend/optimizer/plan/planner.c          |  27 ++
 src/backend/optimizer/util/plancat.c          |   9 +
 src/backend/utils/misc/guc.c                  |  10 +
 src/include/nodes/pathnodes.h                 |   1 +
 src/include/optimizer/cost.h                  |   1 +
 src/include/optimizer/planmain.h              |   2 +
 src/test/regress/expected/aggregates.out      |  13 +-
 src/test/regress/expected/join.out            |  16 +-
 src/test/regress/expected/select_distinct.out | 276 ++++++++++++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/sql/select_distinct.sql      |  84 ++++++
 14 files changed, 619 insertions(+), 36 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 84fd3ad2e0..215f10bf7d 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2902,22 +2902,20 @@ select sum(c1%3), sum(distinct c1%3 order by c1%3) filter (where c1%3 < 2), c2 f
 -- Outer query is aggregation query
 explain (verbose, costs off)
 select distinct (select count(*) filter (where t2.c2 = 6 and t2.c1 < 10) from ft1 t1 where t1.c1 = 6) from ft2 t2 where t2.c2 % 6 = 0 order by 1;
-                                                          QUERY PLAN                                                          
-------------------------------------------------------------------------------------------------------------------------------
- Unique
+                                                       QUERY PLAN                                                       
+------------------------------------------------------------------------------------------------------------------------
+ Sort
    Output: ((SubPlan 1))
-   ->  Sort
-         Output: ((SubPlan 1))
-         Sort Key: ((SubPlan 1))
-         ->  Foreign Scan
-               Output: (SubPlan 1)
-               Relations: Aggregate on (public.ft2 t2)
-               Remote SQL: SELECT count(*) FILTER (WHERE ((c2 = 6) AND ("C 1" < 10))) FROM "S 1"."T 1" WHERE (((c2 % 6) = 0))
-               SubPlan 1
-                 ->  Foreign Scan on public.ft1 t1
-                       Output: (count(*) FILTER (WHERE ((t2.c2 = 6) AND (t2.c1 < 10))))
-                       Remote SQL: SELECT NULL FROM "S 1"."T 1" WHERE (("C 1" = 6))
-(13 rows)
+   Sort Key: ((SubPlan 1))
+   ->  Foreign Scan
+         Output: (SubPlan 1)
+         Relations: Aggregate on (public.ft2 t2)
+         Remote SQL: SELECT count(*) FILTER (WHERE ((c2 = 6) AND ("C 1" < 10))) FROM "S 1"."T 1" WHERE (((c2 % 6) = 0))
+         SubPlan 1
+           ->  Foreign Scan on public.ft1 t1
+                 Output: (count(*) FILTER (WHERE ((t2.c2 = 6) AND (t2.c1 < 10))))
+                 Remote SQL: SELECT NULL FROM "S 1"."T 1" WHERE (("C 1" = 6))
+(11 rows)
 
 select distinct (select count(*) filter (where t2.c2 = 6 and t2.c1 < 10) from ft1 t1 where t1.c1 = 6) from ft2 t2 where t2.c2 % 6 = 0 order by 1;
  count 
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index b5a0033721..dde16b5d44 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -138,6 +138,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_distinct_elimination = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index d0ff660284..dee152af29 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -30,6 +30,7 @@
 #include "optimizer/paths.h"
 #include "optimizer/planmain.h"
 #include "optimizer/tlist.h"
+#include "parser/parsetree.h"
 #include "utils/lsyscache.h"
 
 /* local functions */
@@ -47,7 +48,8 @@ static bool is_innerrel_unique_for(PlannerInfo *root,
 								   RelOptInfo *innerrel,
 								   JoinType jointype,
 								   List *restrictlist);
-
+static void transform_colno_for_subquery(Query *query, List *colnos, List *opids,
+										List **sub_colnos, List **sub_opids);
 
 /*
  * remove_useless_joins
@@ -801,9 +803,18 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 		if (l == NULL)			/* had matches for all? */
 			return true;
 	}
+	return query_is_distinct_agg(query, colnos, opids);
+}
+
+
+bool
+query_is_distinct_agg(Query *query, List *colnos, List *opids)
+{
+	ListCell   *l;
+	Oid			opid;
 
 	/*
-	 * Otherwise, a set-returning function in the query's targetlist can
+	 * a set-returning function in the query's targetlist can
 	 * result in returning duplicate rows, despite any grouping that might
 	 * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
 	 * columns, it would be safe because they'd be expanded before grouping.
@@ -901,7 +912,6 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 				return true;
 		}
 	}
-
 	/*
 	 * XXX Are there any other cases in which we can easily see the result
 	 * must be distinct?
@@ -913,6 +923,174 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 	return false;
 }
 
+/*
+ * scan_non_semi_anti_relids
+ *
+ * Scan jointree to get rid of right table of semi/anti join rtindex.
+ */
+static void
+scan_non_semi_anti_relids(Node* jtnode, Relids* relids)
+{
+	if (jtnode == NULL)
+		return;
+
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*relids = bms_add_member(*relids, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			scan_non_semi_anti_relids(lfirst(l), relids);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		scan_non_semi_anti_relids(j->larg, relids);
+		if (j->jointype != JOIN_SEMI && j->jointype != JOIN_ANTI)
+		{
+			scan_non_semi_anti_relids(j->rarg, relids);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+
+}
+
+/*
+ * transform_colno_for_subquery
+ */
+static void
+transform_colno_for_subquery(Query *query, List *colnos, List *opids,
+							List **sub_colnos, List **sub_opids)
+{
+	ListCell *lc1, *lc2;
+	TargetEntry *tle;
+
+	forboth(lc1, colnos, lc2, opids)
+	{
+		tle = get_tle_by_resno(query->targetList, lfirst_int(lc1));
+		Assert(IsA(tle->expr, Var));
+		*sub_colnos = lappend_int(*sub_colnos, ((Var*)tle->expr)->varattno);
+		*sub_opids = lappend_oid(*sub_opids, lfirst_oid(lc2));
+	}
+}
+
+/*
+ * query_distinct_through_join
+ * If every relation yields a unique result in the join, so the join result
+ * is unqiue as well. We need to distinguish right table in semi/anti
+ * join, which we don't care.
+ */
+bool
+query_distinct_through_join(PlannerInfo *root, List *colnos, List *opids)
+{
+	Query *query = root->parse;
+	Relids non_semi_anti_relids = NULL;
+
+    /* Used for relation_has_unique_for */
+	List **non_null_expr_per_table = NULL;
+	/* Used for query_is_distinct_for */
+	List **non_null_colno_per_table = NULL;
+	/* Used for both as above*/
+	List **non_null_opids_per_table = NULL;
+	/* Not null info from restrictinfo and catalog */
+	Bitmapset **non_null_varno_per_table = NULL;
+
+	int rt_index;
+	ListCell *lc1, *lc2;
+	RangeTblEntry *rte;
+	RelOptInfo *rel;
+	int max_rt_index = list_length(query->rtable) + 1;
+	
+	/* Remove the relids for the right table in semi/anti join */
+	scan_non_semi_anti_relids((Node*)query->jointree, &non_semi_anti_relids);
+
+	non_null_varno_per_table = palloc0(max_rt_index * sizeof(Bitmapset *));
+
+	foreach(lc1, find_nonnullable_vars(query->jointree->quals))
+	{
+		Var *var;
+		if (!IsA(lfirst(lc1), Var))
+			continue;
+		var = lfirst_node(Var, lc1);
+		if (var->varno == INNER_VAR ||
+			var->varno == OUTER_VAR ||
+			var->varno == INDEX_VAR)
+			continue;
+		non_null_varno_per_table[var->varno] = bms_add_member(
+			non_null_varno_per_table[var->varno], var->varattno);
+	}
+
+	/* Add the non null info in catalog */
+	rt_index = -1;
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+		non_null_varno_per_table[rt_index] = bms_join(non_null_varno_per_table[rt_index],
+													  root->simple_rel_array[rt_index]->not_null_cols_relids);
+	}
+
+	non_null_expr_per_table = palloc0(max_rt_index * sizeof(List *));
+	non_null_opids_per_table = palloc0(max_rt_index * sizeof(List *));
+	non_null_colno_per_table = palloc0(max_rt_index * sizeof(List *));
+
+	/* Filter out the nullable columns and split them per table*/
+	forboth(lc1, colnos, lc2, opids)
+	{
+		int colno = lfirst_int(lc1);
+		TargetEntry *tle = get_tle_by_resno(query->targetList, colno);
+		Var *var = NULL;
+		if (!IsA(tle->expr, Var))
+			continue;
+		var = (Var *)tle->expr;
+		if (!bms_is_member(var->varattno, non_null_varno_per_table[var->varno]))
+			continue;
+		non_null_expr_per_table[var->varno] = lappend(
+			non_null_expr_per_table[var->varno], tle->expr);
+		non_null_opids_per_table[var->varno] = lappend_oid(
+			non_null_opids_per_table[var->varno], lfirst_oid(lc2));
+		non_null_colno_per_table[var->varno] = lappend_int(
+			non_null_colno_per_table[var->varno],
+			colno);
+	}
+
+	/* Check if every relation yields a unqiue result, if anyone doesn't return false */
+	rt_index = -1;
+	while ((rt_index = bms_next_member(non_semi_anti_relids, rt_index)) >= 0 )
+	{
+		rte = root->simple_rte_array[rt_index];
+		rel = root->simple_rel_array[rt_index];
+		if (rte->rtekind == RTE_RELATION &&
+			relation_has_unique_index_for(root, rel, NIL,
+										  non_null_expr_per_table[rt_index],
+										  non_null_opids_per_table[rt_index]))
+			continue;
+		if (rte->rtekind == RTE_SUBQUERY &&
+			query_supports_distinctness(rte->subquery))
+		{
+			List *subquery_colnos = NIL;
+			List *subquery_opids = NIL;
+			transform_colno_for_subquery(root->parse,
+										non_null_colno_per_table[rt_index],
+										non_null_opids_per_table[rt_index],
+										&subquery_colnos,
+										&subquery_opids);
+			if (query_is_distinct_for(rte->subquery, subquery_colnos, subquery_opids))
+				continue;
+			return false;
+		}
+		return false;
+	}
+	return true;
+}
+
 /*
  * distinct_col_search - subroutine for query_is_distinct_for
  *
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..9d56e6c88e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4737,6 +4737,33 @@ create_distinct_paths(PlannerInfo *root,
 	Path	   *path;
 	ListCell   *lc;
 
+	if (enable_distinct_elimination)
+	{
+		List *colnos = NIL;
+		List *opnos = NIL;
+		ListCell *lc;
+
+		Assert(parse->distinctClause != NIL);
+
+		foreach(lc, parse->distinctClause)
+		{
+			SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
+			int idx = sgc->tleSortGroupRef;
+			TargetEntry *tle = get_tle_by_resno(parse->targetList, idx);
+			if (tle->resjunk)
+				continue;
+			/* even column x is not null, f(x) may be null as well, so ignore it */
+			if (!IsA(tle->expr, Var))
+				continue;
+			colnos = lappend_int(colnos, idx);
+			opnos = lappend_oid(opnos, sgc->eqop);
+		}
+
+		if ((query_supports_distinctness(parse)
+			 && query_is_distinct_agg(parse, colnos, opnos)) ||
+			query_distinct_through_join(root, colnos, opnos))
+			return input_rel;
+	}
 	/* For now, do all work in the (DISTINCT, NULL) upperrel */
 	distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
 
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index d82fc5ab8b..e57b456d9b 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -117,6 +117,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	int        i;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -460,6 +461,14 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (inhparent && relation->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
 		set_relation_partition_info(root, rel, relation);
 
+	Assert(rel->not_null_cols_relids == NULL);
+	for(i = 0; i < relation->rd_att->natts;  i++)
+	{
+		if (!relation->rd_att->attrs[i].attnotnull)
+			continue;
+		rel->not_null_cols_relids = bms_add_member(rel->not_null_cols_relids, i+1);
+	}
+
 	table_close(relation, NoLock);
 
 	/*
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index e44f71e991..fa798dd564 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1064,6 +1064,16 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_distinct_elimination", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables plan-time and run-time unique elimination."),
+		    gettext_noop("Allows the query planner to remove the uncecessary distinct clause."), 
+			GUC_EXPLAIN
+		},
+		&enable_distinct_elimination,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3d3be197e0..51db013f5d 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -687,6 +687,7 @@ typedef struct RelOptInfo
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	int			rel_parallel_workers;	/* wanted number of parallel workers */
+	Relids     not_null_cols_relids; /* not null cols by catalogs,starts with 1 */
 
 	/* Information about foreign tables and foreign joins */
 	Oid			serverid;		/* identifies server for the table or join */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index cb012ba198..4fa5d32df6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_distinct_elimination;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index eab486a621..ebd4f24577 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -100,6 +100,8 @@ extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
 extern void reduce_unique_semijoins(PlannerInfo *root);
 extern bool query_supports_distinctness(Query *query);
 extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
+extern bool query_is_distinct_agg(Query *query, List *colnos, List *opids);
+extern bool query_distinct_through_join(PlannerInfo *root, List *colnos, List *opids);
 extern bool innerrel_is_unique(PlannerInfo *root,
 							   Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel,
 							   JoinType jointype, List *restrictlist, bool force_cache);
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index f457b5b150..6712571578 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -870,14 +870,12 @@ explain (costs off)
   select distinct max(unique2) from tenk1;
                              QUERY PLAN                              
 ---------------------------------------------------------------------
- HashAggregate
-   Group Key: $0
+ Result
    InitPlan 1 (returns $0)
      ->  Limit
            ->  Index Only Scan Backward using tenk1_unique2 on tenk1
                  Index Cond: (unique2 IS NOT NULL)
-   ->  Result
-(7 rows)
+(5 rows)
 
 select distinct max(unique2) from tenk1;
  max  
@@ -1036,7 +1034,7 @@ explain (costs off)
   select distinct min(f1), max(f1) from minmaxtest;
                                          QUERY PLAN                                          
 ---------------------------------------------------------------------------------------------
- Unique
+ Result
    InitPlan 1 (returns $0)
      ->  Limit
            ->  Merge Append
@@ -1059,10 +1057,7 @@ explain (costs off)
                  ->  Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest_8
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest_9
-   ->  Sort
-         Sort Key: ($0), ($1)
-         ->  Result
-(26 rows)
+(23 rows)
 
 select distinct min(f1), max(f1) from minmaxtest;
  min | max 
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..3f6595d53b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4433,17 +4433,17 @@ 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              
---------------------------------------
- Merge Right Join
-   Merge Cond: (b.id = d.a)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index f3696c6d1d..c27e7d4b67 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -244,3 +244,279 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
  t
 (1 row)
 
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: uk1, uk2
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 > 1)
+(2 rows)
+
+-- distinct erased due to group by
+explain (costs off) select distinct e from select_distinct_a group by e;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: e
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+-- distinct erased due to the restirctinfo
+explain (costs off) select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+                          QUERY PLAN                          
+--------------------------------------------------------------
+ Index Scan using select_distinct_a_pkey on select_distinct_a
+   Index Cond: ((pk1 = 1) AND (pk2 = 'c'::bpchar))
+(2 rows)
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (uk2 IS NOT NULL)
+(5 rows)
+
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+         uk1          | uk2 |         pk1          | pk2 
+----------------------+-----+----------------------+-----
+ a                    |   0 | a                    |   0
+ a                    |   0 | d                    |   0
+ a                    |   0 | e                    |   0
+ A                    |   0 | a                    |   0
+ A                    |   0 | d                    |   0
+ A                    |   0 | e                    |   0
+ c                    |   0 | a                    |   0
+ c                    |   0 | d                    |   0
+ c                    |   0 | e                    |   0
+(9 rows)
+
+-- left join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop Left Join
+   Join Filter: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a
+   ->  Materialize
+         ->  Seq Scan on select_distinct_b b
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+(5 rows)
+
+-- right join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Nested Loop Left Join
+   ->  Seq Scan on select_distinct_b b
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a a
+         Index Cond: (pk1 = b.a)
+(4 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+     |                      | d                    |   0
+(5 rows)
+
+-- full join
+explain (costs off)  select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                 QUERY PLAN                  
+---------------------------------------------
+ Hash Full Join
+   Hash Cond: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a
+   ->  Hash
+         ->  Seq Scan on select_distinct_b b
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+     |                      | d                    |   0
+(6 rows)
+
+-- distinct can't be erased since b.pk2 is missed
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.pk1, a.pk2, b.pk1
+         ->  Hash Full Join
+               Hash Cond: (a.pk1 = b.a)
+               ->  Seq Scan on select_distinct_a a
+               ->  Hash
+                     ->  Seq Scan on select_distinct_b b
+(8 rows)
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+-- we also can handle some limited subquery
+explain (costs off) select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+                              QUERY PLAN                              
+----------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+explain (costs off) select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+                              QUERY PLAN                              
+----------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: pk1
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select * from distinct_v1;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) select * from distinct_v1;
+                        QUERY PLAN                         
+-----------------------------------------------------------
+ HashAggregate
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+alter table select_distinct_a alter column uk1 set not null;
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain (costs off)  execute pt;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) execute pt;
+                        QUERY PLAN                         
+-----------------------------------------------------------
+ HashAggregate
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index a1c90eb905..e053214f9d 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -73,6 +73,7 @@ select name, setting from pg_settings where name like 'enable%';
               name              | setting 
 --------------------------------+---------
  enable_bitmapscan              | on
+ enable_distinct_elimination    | on
  enable_gathermerge             | on
  enable_hashagg                 | on
  enable_hashjoin                | on
@@ -89,7 +90,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(17 rows)
+(18 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index a605e86449..282ca58cf9 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -73,3 +73,87 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
 SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
 SELECT 2 IS NOT DISTINCT FROM null as "no";
 SELECT null IS NOT DISTINCT FROM null as "yes";
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+
+-- distinct erased due to group by
+explain (costs off) select distinct e from select_distinct_a group by e;
+
+-- distinct erased due to the restirctinfo
+explain (costs off) select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+
+
+-- left join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+
+-- right join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- full join
+explain (costs off)  select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- distinct can't be erased since b.pk2 is missed
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+
+-- we also can handle some limited subquery
+explain (costs off) select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+
+explain (costs off) select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 set not null;
+
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain (costs off)  execute pt;
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) execute pt;
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
-- 
2.21.0

diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f..7b9820c25f 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 \
+	uniquekeys.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 905bbe77d8..10bcc0e4fa 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -579,6 +579,12 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	 */
 	check_index_predicates(root, rel);
 
+	/*
+	 * Now that we've marked which partial indexes are suitable, we can now
+	 * build the relation's unique keys.
+	 */
+	populate_baserel_uniquekeys(root, rel);
+
 	/* Mark rel with estimated output rows, width, etc */
 	set_baserel_size_estimates(root, rel);
 }
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index a21c295b99..3dd060f926 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -752,6 +752,8 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 		return joinrel;
 	}
 
+	propagate_unique_keys_to_joinrel(root, joinrel, rel1, rel2, restrictlist);
+
 	/* Add paths to the join relation. */
 	populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
 								restrictlist);
diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.c
new file mode 100644
index 0000000000..40261db1b3
--- /dev/null
+++ b/src/backend/optimizer/path/uniquekeys.c
@@ -0,0 +1,295 @@
+/*-------------------------------------------------------------------------
+ *
+ * uniquekeys.c
+ *	  Utilities for matching and building unique keys
+ *
+ * Portions Copyright (c) 2020, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/backend/optimizer/path/uniquekeys.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "optimizer/pathnode.h"
+
+/*
+ * populate_baserel_uniquekeys
+ *		Populate 'baserel' uniquekeys list by looking at the rel's unique indexes
+ */
+void
+populate_baserel_uniquekeys(PlannerInfo *root, RelOptInfo *baserel)
+{
+	ListCell *lc;
+
+	Assert(baserel->rtekind == RTE_RELATION);
+
+	foreach(lc, baserel->indexlist)
+	{
+		IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
+		UniqueKeySet *keyset;
+		List	   *keys;
+		int			c;
+		int			exprno;
+
+		/*
+		 * If the index is not unique, or not immediately enforced, or if it's
+		 * a partial index that doesn't match the query, it's useless here.
+		 */
+		if (!ind->unique || !ind->immediate ||
+			(ind->indpred != NIL && !ind->predOK))
+			continue;
+
+		keys = NIL;
+		exprno = 0;
+
+		for (c = 0; c < ind->nkeycolumns; c++)
+		{
+			UniqueKey	*key = makeNode(UniqueKey);
+
+			key->uk_collation = ind->indexcollations[c];
+			key->uk_opfamily = ind->opfamily[c];
+			/* XXX is this too lazy? Should I be building my own Var here from indexkeys[c]? */
+			key->uk_expr = copyObject(((TargetEntry *) list_nth(ind->indextlist, c))->expr);
+
+			keys = lappend(keys, key);
+		}
+
+		keyset = makeNode(UniqueKeySet);
+		/* XXX check and update the non_null_keys for NOT NULL Vars */
+		keyset->non_null_keys = NULL;
+		keyset->keys = keys;
+
+		baserel->uniquekeys = lappend(baserel->uniquekeys, keyset);
+	}
+}
+
+static bool
+relation_is_unique_for_keys(PlannerInfo *root, UniqueKeySet *keyset, List *exprs)
+{
+	ListCell *lc;
+
+	foreach(lc, keyset->keys)
+	{
+		UniqueKey *key = (UniqueKey *) lfirst(lc);
+		ListCell *lc2;
+		bool found = false;
+
+		foreach(lc2, exprs)
+		{
+			Expr *expr = (Expr *) lfirst(lc2);
+
+			/* XXX check collation */
+			if (equal(key->uk_expr, expr))
+			{
+				found = true;
+				break;
+			}
+		}
+
+		if (!found)
+			return false;
+	}
+
+	return true;
+}
+
+/*
+ * relation_has_uniquekeys_for
+ *		Returns true if we have proofs that 'rel' cannot return multiple rows with
+ *		the same values in each of 'exprs'.  Otherwise returns false.
+ */
+bool
+relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel, List *exprs,
+							bool req_nonnull)
+{
+	ListCell *lc;
+
+	foreach(lc, rel->uniquekeys)
+	{
+		UniqueKeySet *keyset =  (UniqueKeySet *) lfirst(lc);
+
+		/*
+		 * When we require the keys cannot produce NULL values, skip over sets where
+		 * not all keys are marked as non-null.
+		 */
+		if (req_nonnull && bms_num_members(keyset->non_null_keys) < list_length(keyset->keys))
+			continue;
+
+		if (relation_is_unique_for_keys(root, keyset, exprs))
+			return true;
+	}
+
+	return false;
+}
+
+/*
+ * clause_sides_match_join
+ *	  Determine whether a join clause is of the right form to use in this join.
+ *
+ * We already know that the clause is a binary opclause referencing only the
+ * rels in the current join.  The point here is to check whether it has the
+ * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
+ * rather than mixing outer and inner vars on either side.  If it matches,
+ * we set the transient flag outer_is_left to identify which side is which.
+ */
+static inline bool
+clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,
+						Relids innerrelids)
+{
+	if (bms_is_subset(rinfo->left_relids, outerrelids) &&
+		bms_is_subset(rinfo->right_relids, innerrelids))
+	{
+		/* lefthand side is outer */
+		rinfo->outer_is_left = true;
+		return true;
+	}
+	else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
+			 bms_is_subset(rinfo->right_relids, outerrelids))
+	{
+		/* righthand side is outer */
+		rinfo->outer_is_left = false;
+		return true;
+	}
+	return false;				/* no good for these input relations */
+}
+
+static bool
+clauselist_matches_uniquekeys(List *clause_list, UniqueKeySet *keyset, bool outer_side)
+{
+	ListCell *lc;
+
+	foreach(lc, keyset->keys)
+	{
+		UniqueKey *key = (UniqueKey *)lfirst(lc);
+		ListCell *lc2;
+		bool matched_expr = false;
+
+		foreach(lc2, clause_list)
+		{
+			RestrictInfo *rinfo = (RestrictInfo *)lfirst(lc2);
+			Node	   *rexpr;
+
+			/*
+			 * The condition's equality operator must be a member of the
+			 * index opfamily, else it is not asserting the right kind of
+			 * equality behavior for this index.  We check this first
+			 * since it's probably cheaper than match_index_to_operand().
+			 */
+			if (!list_member_oid(rinfo->mergeopfamilies, key->uk_opfamily))
+				continue;
+
+			/*
+			 * XXX at some point we may need to check collations here too.
+			 * For the moment we assume all collations reduce to the same
+			 * notion of equality.
+			 */
+
+			 /* OK, see if the condition operand matches the index key */
+			if (rinfo->outer_is_left != outer_side)
+				rexpr = get_rightop(rinfo->clause);
+			else
+				rexpr = get_leftop(rinfo->clause);
+
+			if (IsA(rexpr, RelabelType))
+				rexpr = (Node *)((RelabelType *)rexpr)->arg;
+
+			if (equal(rexpr, key->uk_expr))
+			{
+				matched_expr = true;
+				break;
+			}
+		}
+
+		if (!matched_expr)
+			return false;
+	}
+
+	return true;
+}
+
+/*
+ * propagate_unique_keys_to_joinrel
+ *		Using 'restrictlist' determine if rel2 can duplicate rows in rel1 and
+ *		vice-versa.  If the relation at the other side of the join cannot
+ *		cause row duplication, then tag the uniquekeys for the relation onto
+ *		'joinrel's uniquekey list.
+ */
+void
+propagate_unique_keys_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
+								 RelOptInfo *rel1, RelOptInfo *rel2,
+								 List *restrictlist)
+{
+	ListCell *lc;
+	List	*clause_list = NIL;
+	bool	matched;
+
+	/*
+	 * XXX what about base quals being compared to Consts? We're not looking
+	 * at those here at all.  We'd need to split the joinrel into base rel
+	 * components and tag on the base quals to clause_list, as, or course a
+	 * join rel does not contain any base quals.
+	 */
+	foreach(lc, restrictlist)
+	{
+		RestrictInfo *restrictinfo = (RestrictInfo *)lfirst(lc);
+
+		/* XXX what do we do about these?  We don't know the join type yet */
+		//if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
+		//{
+		//	continue;
+		//}
+
+		/* Ignore if it's not a mergejoinable clause */
+		if (!restrictinfo->can_join ||
+			restrictinfo->mergeopfamilies == NIL)
+			continue;			/* not mergejoinable */
+
+		/*
+		 * Check if clause has the form "outer op inner" or "inner op outer",
+		 * and if so mark which side is inner.
+		 */
+		if (!clause_sides_match_join(restrictinfo, rel1->relids, rel2->relids))
+			continue;			/* no good for these input relations */
+
+		/* OK, add to list */
+		clause_list = lappend(clause_list, restrictinfo);
+	}
+
+	matched = false;
+	foreach(lc, rel1->uniquekeys)
+	{
+		UniqueKeySet *keys = (UniqueKeySet *) lfirst(lc);
+
+		/* XXX need to think about how to update the not-null bits here */
+		if (clauselist_matches_uniquekeys(clause_list, keys, true))
+		{
+			matched = true;
+			break;
+		}
+	}
+
+	/* If we get a match then propagate the unique keys of rel2 onto the join rel */
+	if (matched)
+		joinrel->uniquekeys = list_concat(joinrel->uniquekeys, rel2->uniquekeys);
+
+	matched = false;
+	foreach(lc, rel2->uniquekeys)
+	{
+		UniqueKeySet *keys = (UniqueKeySet *)lfirst(lc);
+
+		/* XXX need to think about how to update the not-null bits here */
+		if (clauselist_matches_uniquekeys(clause_list, keys, false))
+		{
+			matched = true;
+			break;
+		}
+	}
+
+	/* If we get a match then propagate the unique keys of rel1 onto the join rel */
+	if (matched)
+		joinrel->uniquekeys = list_concat(joinrel->uniquekeys, rel1->uniquekeys);
+}
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index b44efd6314..06846b1b83 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4757,6 +4757,21 @@ create_distinct_paths(PlannerInfo *root,
 	distinct_rel->useridiscurrent = input_rel->useridiscurrent;
 	distinct_rel->fdwroutine = input_rel->fdwroutine;
 
+	/* XXX just doing this in a really hacky way to see if it works... */
+	if (relation_has_uniquekeys_for(root, input_rel, get_sortgrouplist_exprs(parse->distinctClause, parse->targetList), false))
+	{
+
+		add_path(distinct_rel, (Path *)cheapest_input_path);
+
+		/* XXX yeah yeah, need to call the hooks etc. */
+
+		/* Now choose the best path(s) */
+		set_cheapest(distinct_rel);
+
+		return distinct_rel;
+	}
+
+
 	/* Estimate number of distinct rows there will be */
 	if (parse->groupClause || parse->groupingSets || parse->hasAggs ||
 		root->hasHavingQual)
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 8a76afe8cc..4db76fdb28 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -260,6 +260,8 @@ typedef enum NodeTag
 	T_EquivalenceClass,
 	T_EquivalenceMember,
 	T_PathKey,
+	T_UniqueKeySet,
+	T_UniqueKey,
 	T_PathTarget,
 	T_RestrictInfo,
 	T_IndexClause,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 0ceb809644..5fc725e2e7 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -706,6 +706,7 @@ typedef struct RelOptInfo
 	QualCost	baserestrictcost;	/* cost of evaluating the above */
 	Index		baserestrict_min_security;	/* min security_level found in
 											 * baserestrictinfo */
+	List	   *uniquekeys;		/* List of UniqueKeysets */
 	List	   *joininfo;		/* RestrictInfo structures for join clauses
 								 * involving this rel */
 	bool		has_eclass_joins;	/* T means joininfo is incomplete */
@@ -1016,6 +1017,31 @@ typedef struct PathKey
 	bool		pk_nulls_first; /* do NULLs come before normal values? */
 } PathKey;
 
+/* UniqueKeySet
+ *
+ * Represents a set of unique keys
+ */
+typedef struct UniqueKeySet
+{
+	NodeTag		type;
+
+	Bitmapset *non_null_keys;	/* indexes of 'keys' proved non-null */
+	List		*keys;	/* list of UniqueKeys */
+} UniqueKeySet;
+
+/*
+ * UniqueKey
+ *
+ * Represents the unique properties held by a RelOptInfo or a Path
+ */
+typedef struct UniqueKey
+{
+	NodeTag		type;
+
+	Oid			uk_collation;	/* collation, if datatypes are collatable */
+	Oid			uk_opfamily;	/* btree opfamily defining the ordering */
+	Expr	   *uk_expr;		/* unique key expression */
+} UniqueKey;
 
 /*
  * PathTarget
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9ab73bd20c..16c1faa41e 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -240,4 +240,18 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
 extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 									List *live_childrels);
 
+/*
+ * uniquekeys.c
+ *	  Utilities for matching and building unique keys
+ */
+extern void populate_baserel_uniquekeys(PlannerInfo *root,
+										RelOptInfo *baserel);
+extern bool relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel,
+										List *exprs, bool req_nonnull);
+extern void propagate_unique_keys_to_joinrel(PlannerInfo *root,
+											 RelOptInfo *joinrel,
+											 RelOptInfo *rel1,
+											 RelOptInfo *rel2,
+											 List *restrictlist);
+
 #endif							/* PATHS_H */

From 60c6662b6782d5d4ad4bba0c57fd5b9fecee7364 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Mon, 16 Mar 2020 00:48:13 +0800
Subject: [PATCH v4] [Patch] Bypass distinctClause & groupbyClause if the exprs
 is unique already

---
 src/backend/nodes/list.c                      |  27 +
 src/backend/optimizer/path/Makefile           |   3 +-
 src/backend/optimizer/path/allpaths.c         |   7 +-
 src/backend/optimizer/path/joinrels.c         |   2 +
 src/backend/optimizer/path/uniquekeys.c       | 473 ++++++++++++++++++
 src/backend/optimizer/plan/initsplan.c        |   9 +-
 src/backend/optimizer/plan/planner.c          |  43 ++
 src/backend/optimizer/util/plancat.c          |   8 +
 src/include/nodes/pathnodes.h                 |  27 +
 src/include/nodes/pg_list.h                   |   2 +
 src/include/optimizer/paths.h                 |  17 +
 src/test/regress/expected/aggregates.out      |  38 +-
 src/test/regress/expected/join.out            |  26 +-
 src/test/regress/expected/select_distinct.out | 276 ++++++++++
 src/test/regress/sql/select_distinct.sql      |  84 ++++
 15 files changed, 1003 insertions(+), 39 deletions(-)
 create mode 100644 src/backend/optimizer/path/uniquekeys.c

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index bd0c58cd81..a54c8e66bb 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -688,6 +688,33 @@ list_member_oid(const List *list, Oid datum)
 	return false;
 }
 
+/* 
+ * Return ture iff there is an equal member in target for every
+ * member in members
+ */
+bool
+list_all_members_in(const List *members, const List *target)
+{
+	const ListCell	*lc1, *lc2;
+	if (target == NIL && members != NIL)
+		return false;
+	foreach(lc1, members)
+	{
+		bool found = false;
+		foreach(lc2, target)
+		{
+			if (equal(lfirst(lc1), lfirst(lc2)))
+			{
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+			return false;
+	}
+	return true;
+}
+
 /*
  * Delete the n'th cell (counting from 0) in list.
  *
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f..7b9820c25f 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 \
+	uniquekeys.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 8286d9cf34..2c65d3715b 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -158,6 +158,7 @@ make_one_rel(PlannerInfo *root, List *joinlist)
 	/*
 	 * Construct the all_baserels Relids set.
 	 */
+
 	root->all_baserels = NULL;
 	for (rti = 1; rti < root->simple_rel_array_size; rti++)
 	{
@@ -578,7 +579,9 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	 * first since partial unique indexes can affect size estimates.
 	 */
 	check_index_predicates(root, rel);
-
+	
+	populate_baserel_uniquekeys(root, rel);
+	
 	/* Mark rel with estimated output rows, width, etc */
 	set_baserel_size_estimates(root, rel);
 }
@@ -2321,6 +2324,8 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 		return;
 	}
 
+	rel->uniquekeys = sub_final_rel->uniquekeys;
+	
 	/*
 	 * 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/joinrels.c b/src/backend/optimizer/path/joinrels.c
index a21c295b99..f1243f31e7 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -920,6 +920,8 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
 
 	/* Apply partitionwise join technique, if possible. */
 	try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist);
+
+	propagate_unique_keys_to_joinrel(root, joinrel, rel1, rel2, restrictlist, sjinfo->jointype);
 }
 
 
diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.c
new file mode 100644
index 0000000000..1be2c4f0db
--- /dev/null
+++ b/src/backend/optimizer/path/uniquekeys.c
@@ -0,0 +1,473 @@
+/*-------------------------------------------------------------------------
+ *
+ * uniquekeys.c
+ *	  Utilities for matching and building unique keys
+ *
+ * Portions Copyright (c) 2020, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/backend/optimizer/path/uniquekeys.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+
+/*
+ * Examine the rel's restriction clauses for usable var = const clauses
+ */
+static List*
+get_mergeable_const_restrictlist(RelOptInfo *rel)
+{
+	List	*restrictlist = NIL;
+	ListCell	*lc;
+	foreach(lc, rel->baserestrictinfo)
+	{
+		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+
+		/*
+		 * Note: can_join won't be set for a restriction clause, but
+		 * mergeopfamilies will be if it has a mergejoinable operator and
+		 * doesn't contain volatile functions.
+		 */
+		if (restrictinfo->mergeopfamilies == NIL)
+			continue;			/* not mergejoinable */
+
+		/* XXX can't we check if is a Const */
+
+		/*
+		 * The clause certainly doesn't refer to anything but the given rel.
+		 * If either side is pseudoconstant then we can use it.
+		 */
+		if (bms_is_empty(restrictinfo->left_relids))
+		{
+			/* righthand side is inner */
+			restrictinfo->outer_is_left = true;
+		}
+		else if (bms_is_empty(restrictinfo->right_relids))
+		{
+			/* lefthand side is inner */
+			restrictinfo->outer_is_left = false;
+		}
+		else
+			continue;
+
+		/* OK, add to list */
+		restrictlist = lappend(restrictlist, restrictinfo);
+	}
+
+	return restrictlist;
+
+}
+
+
+/*
+ * Return true if uk = Const in the restrictlist
+ */
+static bool
+match_index_to_restrictinfo(IndexOptInfo *unique_ind, List *restrictlist)
+{
+	int c = 0;
+
+	if (restrictlist == NIL)
+		return false;
+
+	for(c = 0;  c < unique_ind->nkeycolumns; c++)
+	{
+		ListCell	*lc;
+		foreach(lc, restrictlist)
+		{
+			RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+			Node	   *rexpr;
+
+			/*
+			 * The condition's equality operator must be a member of the
+			 * index opfamily, else it is not asserting the right kind of
+			 * equality behavior for this index.  We check this first
+			 * since it's probably cheaper than match_index_to_operand().
+			 */
+			if (!list_member_oid(rinfo->mergeopfamilies, unique_ind->opfamily[c]))
+				continue;
+
+			/*
+			 * XXX at some point we may need to check collations here too.
+			 * For the moment we assume all collations reduce to the same
+			 * notion of equality.
+			 */
+
+			/* OK, see if the condition operand matches the index key */
+			if (rinfo->outer_is_left)
+				rexpr = get_rightop(rinfo->clause);
+			else
+				rexpr = get_leftop(rinfo->clause);
+
+			if (!match_index_to_operand(rexpr, c, unique_ind))
+			{
+				return false;
+			}
+		}
+	}
+	return true;
+}
+
+/*
+ * add_uniquekey_from_index
+ * 	We only add the Index Vars whose expr exists in rel->reltarget
+ */
+static void
+add_uniquekey_from_index(RelOptInfo *rel, IndexOptInfo *unique_index)
+{
+	int	c = 0;
+	List	*exprs = NIL;
+
+	/* We only add the index which exists in rel->reltarget */
+	for(c = 0; c < unique_index->nkeycolumns; c++)
+	{
+		ListCell	*lc;
+		bool	find_in_exprs = false;
+		foreach(lc, rel->reltarget->exprs)
+		{
+			Var *var;
+			/* We never knows a FuncExpr is nullable or not,  we only handle Var now */
+			if (!IsA(lfirst(lc), Var))
+				continue;
+			var = lfirst_node(Var, lc);
+			if (var->varattno < InvalidAttrNumber)
+				/* System column */
+				continue;
+			/* Must check not null for unqiue index */
+			if (!bms_is_member(var->varattno, rel->not_null_cols))
+				continue;
+
+			/* To keep the uniquekey short, We only add it if it exists in rel->reltrget->exprs */
+			if (match_index_to_operand((Node *)lfirst(lc), c, unique_index))
+			{
+				find_in_exprs = true;
+				exprs = lappend(exprs, lfirst(lc));
+				break;
+			}
+		}
+		if (!find_in_exprs)
+			return;
+	}
+	rel->uniquekeys = lappend(rel->uniquekeys, exprs);
+}
+
+/*
+ * populate_baserel_uniquekeys
+ *		Populate 'baserel' uniquekeys list by looking at the rel's unique index
+ * add baserestrictinfo     
+ */
+void
+populate_baserel_uniquekeys(PlannerInfo *root, RelOptInfo *baserel)
+{
+	ListCell *lc;
+	List	*restrictlist = get_mergeable_const_restrictlist(baserel);
+	bool	return_one_row = false;
+	List	*matched_uk_indexes = NIL;
+
+	Assert(baserel->rtekind == RTE_RELATION);
+
+	foreach(lc, baserel->indexlist)
+	{
+		IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
+		/*
+		 * If the index is not unique, or not immediately enforced, or if it's
+		 * a partial index that doesn't match the query, it's useless here.
+		 */
+		if (!ind->unique || !ind->immediate ||
+			(ind->indpred != NIL && !ind->predOK))
+			continue;
+
+		if (match_index_to_restrictinfo(ind, restrictlist))
+		{
+			return_one_row = true;
+			break;
+		}
+		matched_uk_indexes = lappend(matched_uk_indexes, ind);
+	}
+
+	if (return_one_row)
+	{
+		foreach(lc,  baserel->reltarget->exprs)
+		{
+			/* Every columns in this relation is unqiue since only 1 row returned
+			 * No bother to check it is a var or not, also we don't need the check nullable
+			 */
+			baserel->uniquekeys = lappend(baserel->uniquekeys,
+										  list_make1(lfirst(lc)));
+		}
+	}
+	else
+	{
+		foreach(lc,   matched_uk_indexes)
+			add_uniquekey_from_index(baserel, lfirst_node(IndexOptInfo, lc));
+	}
+}
+
+
+/*
+ * relation_has_uniquekeys_for
+ *		Returns true if we have proofs that 'rel' cannot return multiple rows with
+ *		the same values in each of 'exprs'.  Otherwise returns false.
+ */
+bool
+relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel, List *exprs)
+{
+	ListCell *lc;
+
+	foreach(lc, rel->uniquekeys)
+	{
+		List *unique_exprs = lfirst_node(List, lc);
+		if (unique_exprs == NIL)
+			continue;
+		if (list_all_members_in(unique_exprs, exprs))
+			return true;
+	}
+	return false;
+}
+
+/*
+ * clause_sides_match_join
+ *	  Determine whether a join clause is of the right form to use in this join.
+ *
+ * We already know that the clause is a binary opclause referencing only the
+ * rels in the current join.  The point here is to check whether it has the
+ * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
+ * rather than mixing outer and inner vars on either side.  If it matches,
+ * we set the transient flag outer_is_left to identify which side is which.
+ */
+static inline bool
+clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,
+						Relids innerrelids)
+{
+	if (bms_is_subset(rinfo->left_relids, outerrelids) &&
+		bms_is_subset(rinfo->right_relids, innerrelids))
+	{
+		/* lefthand side is outer */
+		rinfo->outer_is_left = true;
+		return true;
+	}
+	else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
+			 bms_is_subset(rinfo->right_relids, outerrelids))
+	{
+		/* righthand side is outer */
+		rinfo->outer_is_left = false;
+		return true;
+	}
+	return false;				/* no good for these input relations */
+}
+
+/*
+ * clauselist_matches_uniquekeys
+ *   Detect the pattern that rel1.uk_expr =  rel2.normal_expr in clause_list, 
+ * if so, we are sure that the UniqueKey of rel2 still can be unqiue key in joinrel.
+ */
+static bool
+clauselist_matches_uniquekeys(List *clause_list, List *uniquekey,  bool outer_side)
+{
+	ListCell *lc;
+
+	if (uniquekey == NIL)
+		return false;
+
+	foreach(lc, uniquekey)
+	{
+		Node *expr = (Node *)lfirst(lc);
+		ListCell *lc2;
+		bool matched_expr = false;
+
+		foreach(lc2, clause_list)
+		{
+			RestrictInfo *rinfo = (RestrictInfo *)lfirst(lc2);
+			Node	   *rexpr;
+
+			/*
+			 * The condition's equality operator must be a member of the
+			 * index opfamily, else it is not asserting the right kind of
+			 * equality behavior for this index.  We check this first
+			 * since it's probably cheaper than match_index_to_operand().
+			 */
+			/* XXXXX do we need this?  uk_opfamily is a Concept when we come to Index
+			 * for UniqueKey looks we don't need it
+			 **/
+			/* if (!list_member_oid(rinfo->mergeopfamilies, key->uk_opfamily)) */
+			/* 	continue; */
+
+			/*
+			 * XXX at some point we may need to check collations here too.
+			 * For the moment we assume all collations reduce to the same
+			 * notion of equality.
+			 */
+
+			 /* OK, see if the condition operand matches the index key */
+			if (rinfo->outer_is_left != outer_side)
+				rexpr = get_rightop(rinfo->clause);
+			else
+				rexpr = get_leftop(rinfo->clause);
+
+			if (IsA(rexpr, RelabelType))
+				rexpr = (Node *)((RelabelType *)rexpr)->arg;
+
+			if (equal(rexpr, expr))
+			{
+				matched_expr = true;
+				break;
+			}
+		}
+
+		if (!matched_expr)
+			return false;
+	}
+
+	return true;
+}
+
+/*
+ * Used to record if a uniquekey has been added to joinrel, if so we don't
+ * need to add other superset of this uniquekey to the joinrel.
+ */
+typedef struct UniqueKeyContextData
+{
+	List	*uniquekey;
+	/* Set to true if the unique key has been added to joinrel->uniquekeys */
+	bool	added_to_joinrel;
+} *UniqueKeyContext;
+
+
+/*
+ * initililze_unqiuecontext_for_joinrel
+ * Return a List of UniqueKeyContext for an inputrel, we also filter out 
+ * all the unqiuekeys which are not possible to use later
+ */
+static List *
+initililze_unqiuecontext_for_joinrel(RelOptInfo *joinrel,  RelOptInfo *inputrel)
+{
+	List	*res = NIL;
+	ListCell *lc;
+	foreach(lc,  inputrel->uniquekeys)
+	{
+		UniqueKeyContext context;
+		/* If it isn't shown in joinrel->reltarget->exprs, it will be not referenced by others */
+		if (!list_all_members_in(lfirst_node(List, lc), joinrel->reltarget->exprs))
+			continue;
+		context = palloc(sizeof(struct UniqueKeyContextData));
+		context->uniquekey = lfirst_node(List, lc);
+		context->added_to_joinrel = false;
+		res = lappend(res, context);
+	}
+	return res;
+
+}
+
+/*
+ * propagate_unique_keys_to_joinrel
+ *		Using 'restrictlist' determine if rel2 can duplicate rows in rel1 and
+ *		vice-versa.  If the relation at the other side of the join cannot
+ *		cause row duplication, then tag the uniquekeys for the relation onto
+ *		'joinrel's uniquekey list.
+ */
+void
+propagate_unique_keys_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
+								 RelOptInfo *rel1, RelOptInfo *rel2,
+								 List *restrictlist, JoinType jointype)
+{
+	ListCell *lc, *lc2;
+	List	*clause_list = NIL;
+	List	*rel1_uniquekey_context;
+	List	*rel2_uniquekey_context;
+
+	/* Care about the left relation only for SEMI/ANTI join */
+	if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+	{
+		foreach(lc, rel1->uniquekeys)
+		{
+			List	*uniquekey = lfirst_node(List, lc);
+			if (list_all_members_in(uniquekey, joinrel->reltarget->exprs))
+				joinrel->uniquekeys = lappend(joinrel->uniquekeys, uniquekey);
+		}
+		return;
+	}
+
+	rel1_uniquekey_context = initililze_unqiuecontext_for_joinrel(joinrel, rel1);
+	rel2_uniquekey_context = initililze_unqiuecontext_for_joinrel(joinrel, rel2);
+	
+	if (rel1_uniquekey_context == NIL || rel2_uniquekey_context == NIL)
+		return;
+
+	foreach(lc, restrictlist)
+	{
+		RestrictInfo *restrictinfo = (RestrictInfo *)lfirst(lc);
+
+
+		if (IS_OUTER_JOIN(jointype) &&
+			RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
+			continue;
+
+		/* Ignore if it's not a mergejoinable clause */
+		if (!restrictinfo->can_join ||
+			restrictinfo->mergeopfamilies == NIL)
+			continue;			/* not mergejoinable */
+
+		/*
+		 * Check if clause has the form "outer op inner" or "inner op outer",
+		 * and if so mark which side is inner.
+		 */
+		if (!clause_sides_match_join(restrictinfo, rel1->relids, rel2->relids))
+			continue;			/* no good for these input relations */
+
+		/* OK, add to list */
+		clause_list = lappend(clause_list, restrictinfo);
+	}
+
+	foreach(lc, rel1_uniquekey_context)
+	{
+		List	*uniquekey = ((UniqueKeyContext)lfirst(lc))->uniquekey;
+		if (clauselist_matches_uniquekeys(clause_list, uniquekey, true))
+		{
+			foreach(lc2, rel2_uniquekey_context)
+			{
+				UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc);
+				joinrel->uniquekeys = lappend(joinrel->uniquekeys, ctx->uniquekey);
+				ctx->added_to_joinrel = true;
+			}
+			break;
+		}
+	}
+
+	foreach(lc, rel2_uniquekey_context)
+	{
+		List	*uniquekey = ((UniqueKeyContext)lfirst(lc))->uniquekey;
+		if (clauselist_matches_uniquekeys(clause_list, uniquekey, true))
+		{
+			foreach(lc2, rel1_uniquekey_context)
+			{
+				UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc);
+				joinrel->uniquekeys = lappend(joinrel->uniquekeys, ctx->uniquekey);
+				ctx->added_to_joinrel = true;
+			}
+			break;
+		}
+	}
+
+	foreach(lc, rel1_uniquekey_context)
+	{
+		UniqueKeyContext context1 = (UniqueKeyContext) lfirst(lc);
+		if (context1->added_to_joinrel)
+			continue;
+		foreach(lc2, rel2_uniquekey_context)
+		{
+			UniqueKeyContext context2 = (UniqueKeyContext) lfirst(lc2);
+			List	*uniquekey = NIL;
+			if (context2->added_to_joinrel)
+				continue;
+			uniquekey = list_copy(context1->uniquekey);
+			uniquekey = list_concat(uniquekey, context2->uniquekey);
+			joinrel->uniquekeys = lappend(joinrel->uniquekeys, uniquekey);
+		}
+	}
+}
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e978b491f6..a674e271e7 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -829,7 +829,14 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 		foreach(l, (List *) f->quals)
 		{
 			Node	   *qual = (Node *) lfirst(l);
-
+			ListCell	*lc;
+			foreach(lc, find_nonnullable_vars(qual))
+			{
+				Var *var = lfirst_node(Var, lc);
+				RelOptInfo *rel = root->simple_rel_array[var->varno];
+				if (var->varattno > InvalidAttrNumber)
+					rel->not_null_cols = bms_add_member(rel->not_null_cols, var->varattno);
+			}
 			distribute_qual_to_rels(root, qual,
 									false, below_outer_join, JOIN_INNER,
 									root->qual_security_level,
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6f2153593..e300dad442 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -2389,6 +2389,9 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		add_path(final_rel, path);
 	}
 
+	/* Copy the uniquekeys to final_rel */
+	final_rel->uniquekeys = current_rel->uniquekeys;
+	
 	/*
 	 * Generate partial paths for final_rel, too, if outer query levels might
 	 * be able to make use of them.
@@ -3813,6 +3816,20 @@ create_grouping_paths(PlannerInfo *root,
 	Query	   *parse = root->parse;
 	RelOptInfo *grouped_rel;
 	RelOptInfo *partially_grouped_rel;
+	ListCell	*lc;
+
+	List	*required_unique_keys = get_sortgrouplist_exprs(parse->groupClause,
+															parse->targetList);
+	/*
+	 * If the groupby clauses is unique already,  groupping node is not necessary
+	 * if there is no aggreation functions
+	 */
+	if (required_unique_keys != NIL &&
+		!parse->hasAggs &&
+		!parse->hasWindowFuncs &&
+		parse->havingQual == NULL &&
+		relation_has_uniquekeys_for(root, input_rel, required_unique_keys))
+		return input_rel;
 
 	/*
 	 * Create grouping relation to hold fully aggregated grouping and/or
@@ -3901,6 +3918,19 @@ create_grouping_paths(PlannerInfo *root,
 	}
 
 	set_cheapest(grouped_rel);
+
+	/* Copy the upperrel's uniquekeys to grouped_rel and add the one which caused
+	 * by groupBy clause
+	 */
+	foreach(lc, input_rel->uniquekeys)
+	{
+		List	*uniquekey = lfirst_node(List, lc);
+		if (list_all_members_in(uniquekey, grouped_rel->reltarget->exprs))
+			grouped_rel->uniquekeys = lappend(grouped_rel->uniquekeys, uniquekey);
+	}
+	if (required_unique_keys != NIL)
+		grouped_rel->uniquekeys = lappend(grouped_rel->uniquekeys,
+										  required_unique_keys);
 	return grouped_rel;
 }
 
@@ -4736,6 +4766,12 @@ create_distinct_paths(PlannerInfo *root,
 	bool		allow_hash;
 	Path	   *path;
 	ListCell   *lc;
+	List	   *required_unique_keys =  get_sortgrouplist_exprs(parse->distinctClause,
+																parse->targetList);
+
+	/* If we the result if unqiue already, we just return the input_rel directly */
+	if (relation_has_uniquekeys_for(root, input_rel, required_unique_keys))
+		return input_rel;
 
 	/* For now, do all work in the (DISTINCT, NULL) upperrel */
 	distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
@@ -4920,6 +4956,10 @@ create_distinct_paths(PlannerInfo *root,
 	/* Now choose the best path(s) */
 	set_cheapest(distinct_rel);
 
+	/* All the UK before distinct is still valid and we can add one more required_unique_keys */
+	distinct_rel->uniquekeys = list_copy(input_rel->uniquekeys);
+	distinct_rel->uniquekeys = lappend(distinct_rel->uniquekeys,
+											required_unique_keys);
 	return distinct_rel;
 }
 
@@ -5066,6 +5106,9 @@ create_ordered_paths(PlannerInfo *root,
 	 * need us to do it.
 	 */
 	Assert(ordered_rel->pathlist != NIL);
+	
+	/* Copy the unique keys */
+	ordered_rel->uniquekeys = input_rel->uniquekeys;
 
 	return ordered_rel;
 }
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index d82fc5ab8b..34d30b181c 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -117,6 +117,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	int			i;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -460,6 +461,13 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (inhparent && relation->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
 		set_relation_partition_info(root, rel, relation);
 
+	Assert(rel->not_null_cols == NULL);
+	for(i = 0; i < relation->rd_att->natts; i++)
+	{
+		if (relation->rd_att->attrs[i].attnotnull)
+			rel->not_null_cols = bms_add_member(rel->not_null_cols, i+1);
+	}
+
 	table_close(relation, NoLock);
 
 	/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3d3be197e0..ee26cfdb5c 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -687,6 +687,7 @@ typedef struct RelOptInfo
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	int			rel_parallel_workers;	/* wanted number of parallel workers */
+	Relids		not_null_cols; /* the non null column for this relation, start from 1 */
 
 	/* Information about foreign tables and foreign joins */
 	Oid			serverid;		/* identifies server for the table or join */
@@ -706,6 +707,7 @@ typedef struct RelOptInfo
 	QualCost	baserestrictcost;	/* cost of evaluating the above */
 	Index		baserestrict_min_security;	/* min security_level found in
 											 * baserestrictinfo */
+	List	   *uniquekeys;		/* List of Var groups */
 	List	   *joininfo;		/* RestrictInfo structures for join clauses
 								 * involving this rel */
 	bool		has_eclass_joins;	/* T means joininfo is incomplete */
@@ -1016,6 +1018,31 @@ typedef struct PathKey
 	bool		pk_nulls_first; /* do NULLs come before normal values? */
 } PathKey;
 
+/* UniqueKeySet
+ *
+ * Represents a set of unique keys
+ */
+typedef struct UniqueKeySet
+{
+	NodeTag		type;
+
+	Bitmapset *non_null_keys;	/* indexes of 'keys' proved non-null */
+	List		*keys;	/* list of UniqueKeys */
+} UniqueKeySet;
+
+/*
+ * UniqueKey
+ *
+ * Represents the unique properties held by a RelOptInfo or a Path
+ */
+typedef struct UniqueKey
+{
+	NodeTag		type;
+
+	Oid			uk_collation;	/* collation, if datatypes are collatable */
+	Oid			uk_opfamily;	/* btree opfamily defining the ordering */
+	Expr	   *uk_expr;		/* unique key expression */
+} UniqueKey;
 
 /*
  * PathTarget
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 14ea2766ad..5dfb93895c 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -528,6 +528,8 @@ extern bool list_member_ptr(const List *list, const void *datum);
 extern bool list_member_int(const List *list, int datum);
 extern bool list_member_oid(const List *list, Oid datum);
 
+extern bool list_all_members_in(const List *members, const List *target);
+
 extern List *list_delete(List *list, void *datum);
 extern List *list_delete_ptr(List *list, void *datum);
 extern List *list_delete_int(List *list, int datum);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9ab73bd20c..f0cc2c4245 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -240,4 +240,21 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
 extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 									List *live_childrels);
 
+/*
+ * uniquekeys.c
+ *	  Utilities for matching and building unique keys
+ */
+extern void populate_baserel_uniquekeys(PlannerInfo *root,
+										RelOptInfo *baserel);
+extern bool relation_has_uniquekeys_for(PlannerInfo *root,
+										RelOptInfo *rel,
+										List *exprs);
+										
+extern void propagate_unique_keys_to_joinrel(PlannerInfo *root,
+											 RelOptInfo *joinrel,
+											 RelOptInfo *rel1,
+											 RelOptInfo *rel2,
+											 List *restrictlist,
+											 JoinType jointype);
+
 #endif							/* PATHS_H */
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index f457b5b150..07dab0ed5d 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1092,12 +1092,10 @@ create temp table t2 (x int, y int, z int, primary key (x, y));
 create temp table t3 (a int, b int, c int, primary key(a, b) deferrable);
 -- Non-primary-key columns can be removed from GROUP BY
 explain (costs off) select * from t1 group by a,b,c,d;
-      QUERY PLAN      
-----------------------
- HashAggregate
-   Group Key: a, b
-   ->  Seq Scan on t1
-(3 rows)
+   QUERY PLAN   
+----------------
+ Seq Scan on t1
+(1 row)
 
 -- No removal can happen if the complete PK is not present in GROUP BY
 explain (costs off) select a,c from t1 group by a,c,d;
@@ -1112,16 +1110,14 @@ explain (costs off) select a,c from t1 group by a,c,d;
 explain (costs off) select *
 from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
 group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t2.z;
-                      QUERY PLAN                      
-------------------------------------------------------
- HashAggregate
-   Group Key: t1.a, t1.b, t2.x, t2.y
-   ->  Hash Join
-         Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b))
-         ->  Seq Scan on t2
-         ->  Hash
-               ->  Seq Scan on t1
-(7 rows)
+                   QUERY PLAN                   
+------------------------------------------------
+ Hash Join
+   Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b))
+   ->  Seq Scan on t2
+   ->  Hash
+         ->  Seq Scan on t1
+(5 rows)
 
 -- Test case where t1 can be optimized but not t2
 explain (costs off) select t1.*,t2.x,t2.z
@@ -1161,12 +1157,10 @@ explain (costs off) select * from t1 group by a,b,c,d;
 
 -- Okay to remove columns if we're only querying the parent.
 explain (costs off) select * from only t1 group by a,b,c,d;
-      QUERY PLAN      
-----------------------
- HashAggregate
-   Group Key: a, b
-   ->  Seq Scan on t1
-(3 rows)
+   QUERY PLAN   
+----------------
+ Seq Scan on t1
+(1 row)
 
 create temp table p_t1 (
   a int,
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 761376b007..a5d98cf421 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4417,33 +4417,31 @@ select d.* from d left join (select distinct * from b) s
 explain (costs off)
 select d.* from d left join (select * from b group by b.id, b.c_id) s
   on d.a = s.id;
-                QUERY PLAN                
-------------------------------------------
+             QUERY PLAN             
+------------------------------------
  Merge Right Join
    Merge Cond: (b.id = d.a)
-   ->  Group
-         Group Key: b.id
-         ->  Index Scan using b_pkey on b
+   ->  Index Scan using b_pkey on b
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
-(8 rows)
+(6 rows)
 
 -- similarly, but keying off a DISTINCT clause
 explain (costs off)
 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)
-   ->  Unique
-         ->  Sort
-               Sort Key: b.id, b.c_id
-               ->  Seq Scan on b
+           QUERY PLAN            
+---------------------------------
+ Merge Left Join
+   Merge Cond: (d.a = s.id)
    ->  Sort
          Sort Key: d.a
          ->  Seq Scan on d
+   ->  Sort
+         Sort Key: s.id
+         ->  Subquery Scan on s
+               ->  Seq Scan on b
 (9 rows)
 
 -- check join removal works when uniqueness of the join condition is enforced
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index f3696c6d1d..c27e7d4b67 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -244,3 +244,279 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
  t
 (1 row)
 
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: uk1, uk2
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 > 1)
+(2 rows)
+
+-- distinct erased due to group by
+explain (costs off) select distinct e from select_distinct_a group by e;
+             QUERY PLAN              
+-------------------------------------
+ HashAggregate
+   Group Key: e
+   ->  Seq Scan on select_distinct_a
+(3 rows)
+
+-- distinct erased due to the restirctinfo
+explain (costs off) select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+                          QUERY PLAN                          
+--------------------------------------------------------------
+ Index Scan using select_distinct_a_pkey on select_distinct_a
+   Index Cond: ((pk1 = 1) AND (pk2 = 'c'::bpchar))
+(2 rows)
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop
+   ->  Seq Scan on select_distinct_b b
+   ->  Materialize
+         ->  Seq Scan on select_distinct_a a
+               Filter: (uk2 IS NOT NULL)
+(5 rows)
+
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+         uk1          | uk2 |         pk1          | pk2 
+----------------------+-----+----------------------+-----
+ a                    |   0 | a                    |   0
+ a                    |   0 | d                    |   0
+ a                    |   0 | e                    |   0
+ A                    |   0 | a                    |   0
+ A                    |   0 | d                    |   0
+ A                    |   0 | e                    |   0
+ c                    |   0 | a                    |   0
+ c                    |   0 | d                    |   0
+ c                    |   0 | e                    |   0
+(9 rows)
+
+-- left join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+                 QUERY PLAN                  
+---------------------------------------------
+ Nested Loop Left Join
+   Join Filter: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a
+   ->  Materialize
+         ->  Seq Scan on select_distinct_b b
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+(5 rows)
+
+-- right join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Nested Loop Left Join
+   ->  Seq Scan on select_distinct_b b
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a a
+         Index Cond: (pk1 = b.a)
+(4 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+     |                      | d                    |   0
+(5 rows)
+
+-- full join
+explain (costs off)  select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                 QUERY PLAN                  
+---------------------------------------------
+ Hash Full Join
+   Hash Cond: (a.pk1 = b.a)
+   ->  Seq Scan on select_distinct_a a
+   ->  Hash
+         ->  Seq Scan on select_distinct_b b
+(5 rows)
+
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+ pk1 |         pk2          |         pk1          | pk2 
+-----+----------------------+----------------------+-----
+   1 | a                    | a                    |   0
+   1 | a                    | e                    |   0
+   1 | b                    | a                    |   0
+   1 | b                    | e                    |   0
+   3 | c                    |                      |    
+     |                      | d                    |   0
+(6 rows)
+
+-- distinct can't be erased since b.pk2 is missed
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: a.pk1, a.pk2, b.pk1
+         ->  Hash Full Join
+               Hash Cond: (a.pk1 = b.a)
+               ->  Seq Scan on select_distinct_a a
+               ->  Hash
+                     ->  Seq Scan on select_distinct_b b
+(8 rows)
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Only Scan using select_distinct_a_pkey on select_distinct_a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+              QUERY PLAN               
+---------------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on select_distinct_b
+(4 rows)
+
+-- we also can handle some limited subquery
+explain (costs off) select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+                              QUERY PLAN                              
+----------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+explain (costs off) select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+                              QUERY PLAN                              
+----------------------------------------------------------------------
+ Nested Loop
+   ->  HashAggregate
+         Group Key: select_distinct_b.a
+         ->  Seq Scan on select_distinct_b
+   ->  Index Scan using select_distinct_a_pkey on select_distinct_a a
+         Index Cond: (pk1 = select_distinct_b.a)
+(6 rows)
+
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+ pk1 |         pk2          |         uk1          | uk2 | e | a 
+-----+----------------------+----------------------+-----+---+---
+   1 | a                    | a                    |   0 | 1 | 1
+   1 | b                    | A                    |   0 | 2 | 1
+(2 rows)
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+                QUERY PLAN                 
+-------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: pk1
+         ->  Seq Scan on select_distinct_a
+(4 rows)
+
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+(1 row)
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select * from distinct_v1;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) select * from distinct_v1;
+                        QUERY PLAN                         
+-----------------------------------------------------------
+ HashAggregate
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+alter table select_distinct_a alter column uk1 set not null;
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain (costs off)  execute pt;
+          QUERY PLAN           
+-------------------------------
+ Seq Scan on select_distinct_a
+   Filter: (uk2 IS NOT NULL)
+(2 rows)
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) execute pt;
+                        QUERY PLAN                         
+-----------------------------------------------------------
+ HashAggregate
+   Group Key: select_distinct_a.uk1, select_distinct_a.uk2
+   ->  Seq Scan on select_distinct_a
+         Filter: (uk2 IS NOT NULL)
+(4 rows)
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index a605e86449..282ca58cf9 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -73,3 +73,87 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
 SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
 SELECT 2 IS NOT DISTINCT FROM null as "no";
 SELECT null IS NOT DISTINCT FROM null as "yes";
+create table select_distinct_a(pk1 int, pk2 char(20),  uk1 char(20) not null,  uk2 int, e int, primary key(pk1, pk2));
+create unique index select_distinct_a_uk on select_distinct_a(uk1, uk2);
+create table select_distinct_b(a int, b char(20), pk1 char(20), pk2 int, e int, primary key(pk1, pk2));
+
+-- distinct erased since (pk1, pk2)
+explain (costs off) select distinct * from select_distinct_a;
+
+-- distinct can't be reased since since we required all the uk must be not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a;
+
+-- distinct ereased since uk + not null
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select distinct uk1, uk2 from select_distinct_a where uk2 > 1;
+
+-- distinct erased due to group by
+explain (costs off) select distinct e from select_distinct_a group by e;
+
+-- distinct erased due to the restirctinfo
+explain (costs off) select distinct uk1 from select_distinct_a where pk1 = 1 and pk2 = 'c';
+
+-- test join
+set enable_mergejoin to off;
+set enable_hashjoin to off;
+
+insert into select_distinct_a values(1, 'a', 'a', 0, 1), (1, 'b', 'A', 0, 2), (3, 'c', 'c', 0, 3);
+insert into select_distinct_b values(1, 'a', 'a', 0, 1), (4, 'd', 'd', 0, 4), (1, 'e', 'e', 0, 5);
+
+-- Cartesian join
+explain (costs off) select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null;
+select distinct a.uk1, a.uk2, b.pk1, b.pk2 from select_distinct_a a, select_distinct_b b where a.uk2 is not null order by 1, 2, 3, 4;
+
+
+-- left join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a left join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;;
+
+-- right join
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a right join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- full join
+explain (costs off)  select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+select distinct a.pk1, a.pk2, b.pk1, b.pk2 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a) order by 1, 2, 3, 4;
+
+-- distinct can't be erased since b.pk2 is missed
+explain (costs off) select distinct a.pk1, a.pk2, b.pk1 from select_distinct_a a full outer join select_distinct_b b on (a.pk1 = b.a);
+
+
+-- Semi/anti join
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 in (select a from select_distinct_b);
+explain (costs off) select distinct pk1, pk2 from select_distinct_a where pk1 not in (select a from select_distinct_b);
+
+-- we also can handle some limited subquery
+explain (costs off) select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a,  (select a from select_distinct_b group by a) b where a.pk1 = b.a order by 1, 2, 3;
+
+explain (costs off) select distinct * from select_distinct_a a,  (select distinct a from select_distinct_b) b where a.pk1 = b.a;
+select distinct * from select_distinct_a a, (select distinct a from select_distinct_b) b where a.pk1 = b.a order by 1 ,2, 3;
+
+-- Distinct On
+-- can't erase since pk2 is missed
+explain (costs off) select distinct on(pk1) pk1, pk2 from select_distinct_a;
+-- ok to erase
+explain (costs off) select distinct on(pk1, pk2) pk1, pk2 from select_distinct_a;
+
+
+-- test some view.
+create view distinct_v1 as select distinct uk1, uk2 from select_distinct_a where uk2 is not null;
+explain (costs off) select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) select * from distinct_v1;
+
+alter table select_distinct_a alter column uk1 set not null;
+
+-- test generic plan
+prepare pt as select * from distinct_v1;
+explain (costs off)  execute pt;
+alter table select_distinct_a alter column uk1 drop not null;
+explain (costs off) execute pt;
+
+drop view distinct_v1;
+drop table select_distinct_a;
+drop table select_distinct_b;
-- 
2.21.0