remove-self-join-v1.patch

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 477b9f7..334793c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -76,13 +76,9 @@ static void set_rel_size(PlannerInfo *root, RelOptInfo *rel,
 			 Index rti, RangeTblEntry *rte);
 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 				 Index rti, RangeTblEntry *rte);
-static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel,
-				   RangeTblEntry *rte);
 static void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel);
 static void set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
 						  RangeTblEntry *rte);
-static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
-					   RangeTblEntry *rte);
 static void set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel,
 						 RangeTblEntry *rte);
 static void set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
@@ -366,7 +362,7 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel,
 				else
 				{
 					/* Plain relation */
-					set_plain_rel_size(root, rel, rte);
+					set_plain_rel_size(root, rel);
 				}
 				break;
 			case RTE_SUBQUERY:
@@ -449,7 +445,7 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 				else
 				{
 					/* Plain relation */
-					set_plain_rel_pathlist(root, rel, rte);
+					set_plain_rel_pathlist(root, rel);
 				}
 				break;
 			case RTE_SUBQUERY:
@@ -516,8 +512,8 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  * set_plain_rel_size
  *	  Set size estimates for a plain relation (no subquery, no inheritance)
  */
-static void
-set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
+void
+set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel)
 {
 	/*
 	 * Test any partial indexes of rel for applicability.  We must do this
@@ -691,8 +687,8 @@ set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
  * set_plain_rel_pathlist
  *	  Build access paths for a plain relation (no subquery, no inheritance)
  */
-static void
-set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
+void
+set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel)
 {
 	Relids		required_outer;
 
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index f295558..d79b3c7 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2961,7 +2961,7 @@ ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
- * relation_has_unique_index_for
+ * relation_get_unique_index_for
  *	  Determine whether the relation provably has at most one row satisfying
  *	  a set of equality conditions, because the conditions constrain all
  *	  columns of some unique index.
@@ -2982,8 +2982,8 @@ ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
  * this routine automatically adds in any usable baserestrictinfo clauses.
  * (Note that the passed-in restrictlist will be destructively modified!)
  */
-bool
-relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
+IndexOptInfo *
+relation_get_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 							  List *restrictlist,
 							  List *exprlist, List *oprlist)
 {
@@ -2993,7 +2993,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 
 	/* Short-circuit if no indexes... */
 	if (rel->indexlist == NIL)
-		return false;
+		return NULL;
 
 	/*
 	 * Examine the rel's restriction clauses for usable var = const clauses
@@ -3034,7 +3034,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 
 	/* Short-circuit the easy case */
 	if (restrictlist == NIL && exprlist == NIL)
-		return false;
+		return NULL;
 
 	/* Examine each index of the relation ... */
 	foreach(ic, rel->indexlist)
@@ -3131,10 +3131,10 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 
 		/* Matched all columns of this index? */
 		if (c == ind->ncolumns)
-			return true;
+			return ind;
 	}
 
-	return false;
+	return NULL;
 }
 
 /*
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 7008e13..d57ac82 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -15,11 +15,15 @@
 #include "postgres.h"
 
 #include "miscadmin.h"
+#include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/joininfo.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "optimizer/plancat.h"
+#include "optimizer/predtest.h"
 #include "optimizer/prep.h"
+#include "optimizer/restrictinfo.h"
 #include "partitioning/partbounds.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
@@ -747,6 +751,240 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 	return joinrel;
 }
 
+static bool
+has_relation_reference_walker(Node *node, void *context)
+{
+	if (node == NULL)
+		return false;
+
+	if (IsA(node, Var))
+		return ((Var *) node)->varno == (Index) (intptr_t) context;
+
+	return expression_tree_walker(node, has_relation_reference_walker, context);
+}
+
+static bool
+has_relation_reference(PathTarget *target, Index relid)
+{
+	return has_relation_reference_walker((Node *) target->exprs,
+										 (void *) (intptr_t) relid);
+}
+
+static bool
+set_varno_walker(Node *node, void *context)
+{
+	if (node == NULL)
+		return false;
+
+	if (IsA(node, Var))
+		((Var *) node)->varno = (Index) (intptr_t) context;
+
+	return expression_tree_walker(node, set_varno_walker, context);
+}
+
+static void
+set_varno(Expr *target, Index relid)
+{
+	set_varno_walker((Node *) target, (void*) (intptr_t) relid);
+}
+
+static inline bool
+clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel,
+						RelOptInfo *innerrel)
+{
+	if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
+		bms_is_subset(rinfo->right_relids, innerrel->relids))
+	{
+		/* lefthand side is outer */
+		rinfo->outer_is_left = true;
+		return true;
+	}
+	else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
+			 bms_is_subset(rinfo->right_relids, outerrel->relids))
+	{
+		/* righthand side is outer */
+		rinfo->outer_is_left = false;
+		return true;
+	}
+	return false;				/* no good for these input relations */
+}
+
+static void
+init_simple_rel(PlannerInfo *root, RelOptInfo *rel, Index relid)
+{
+	RangeTblEntry *rte;
+
+	/* Fetch RTE for relation */
+	rte = root->simple_rte_array[relid];
+	Assert(rte != NULL);
+
+	rel->reloptkind = RELOPT_BASEREL;
+	rel->rtekind = rte->rtekind;
+	rel->rows = 0;
+	rel->relid = relid;
+
+	/* min_attr, max_attr, attr_needed, attr_widths are set below */
+
+	/* Check type of rtable entry */
+	switch (rte->rtekind)
+	{
+		case RTE_RELATION:
+			/* Table --- retrieve statistics from the system catalogs */
+			get_relation_info(root, rte->relid, rte->inh, rel);
+			break;
+		case RTE_SUBQUERY:
+		case RTE_FUNCTION:
+		case RTE_TABLEFUNC:
+		case RTE_VALUES:
+		case RTE_CTE:
+		case RTE_NAMEDTUPLESTORE:
+
+			/*
+			 * Subquery, function, tablefunc, values list, CTE, or ENR --- set
+			 * up attr range and arrays
+			 *
+			 * Note: 0 is included in range to support whole-row Vars
+			 */
+			rel->min_attr = 0;
+			rel->max_attr = list_length(rte->eref->colnames);
+			rel->attr_needed = (Relids *)
+				palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
+			rel->attr_widths = (int32 *)
+				palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
+			break;
+		default:
+			elog(ERROR, "unrecognized RTE kind: %d",
+				 (int) rte->rtekind);
+			break;
+	}
+}
+
+static IndexOptInfo *
+get_inner_unique_index(PlannerInfo *root, RelOptInfo *innerRel,
+							 RelOptInfo *outerRel, List *restrictlist)
+{
+	ListCell *lc;
+	List *rl = list_copy(restrictlist);
+	foreach(lc, rl)
+	{
+		if (!clause_sides_match_join((RestrictInfo *) lfirst(lc),
+									 outerRel, innerRel))
+			return NULL;
+	}
+
+	return relation_get_unique_index_for(root, innerRel, rl, 0, 0);
+}
+
+/*
+ * This function optimizes out an inner join of a relation to itself on a
+ * unique column. When the inner relation is not referenced by the targetlist,
+ * we can transfer the filters from the inner relation to the outer one, and
+ * scan it instead of joining.
+ */
+static bool
+reduce_self_unique_join(PlannerInfo *root, RelOptInfo *outerrel,
+						RelOptInfo *innerrel, RelOptInfo *joinrel,
+						List *restrictlist)
+{
+	List *mergedRinfos;
+	ListCell *lc;
+	IndexOptInfo *outeridx, *inneridx;
+	Bitmapset *oldRelids = joinrel->relids;
+
+	outeridx = get_inner_unique_index(root, outerrel, innerrel, restrictlist);
+	if (!outeridx)
+		return false;
+
+	/*
+	 * Join can be reduced only if the unique constraint is immediate.
+	 * Otherwise, the constraint does not always hold inside a transaction.
+	 */
+	if (!outeridx->immediate)
+		return false;
+
+	inneridx = get_inner_unique_index(root, innerrel, outerrel, restrictlist);
+	if (!inneridx)
+		return false;
+
+	/* We must have the same unique index for both relations. */
+	if (outeridx->indexoid != inneridx->indexoid)
+		return false;
+
+	/* A sanity check: this is the same index on the same relation. */
+	Assert(root->simple_rte_array[outerrel->relid]->relid
+			== root->simple_rte_array[innerrel->relid]->relid);
+
+	/*
+	 * If some columns of the inner relation are in the target list,
+	 * we have to keep it.
+	 */
+	if (has_relation_reference(joinrel->reltarget, innerrel->relid))
+		return false;
+
+	/*
+	 * All the necessary conditions hold and we can change the join
+	 * into a scan on the outer relation. First, append the filters
+	 * from inner relation to the outer.
+	 */
+	mergedRinfos = list_copy(outerrel->baserestrictinfo);
+	foreach(lc, innerrel->baserestrictinfo)
+	{
+		RestrictInfo *oldRinfo = lfirst_node(RestrictInfo, lc);
+		RestrictInfo *newRinfo;
+		Expr *newClause;
+
+		if (is_redundant_derived_clause(oldRinfo, mergedRinfos))
+			continue;			/* derived from same EquivalenceClass */
+
+		newClause = copyObject(oldRinfo->clause);
+		set_varno(newClause, outerrel->relid);
+
+		/*
+		 * !!!FIXME This check doesn't work, because predicate_implied_by
+		 * uses equal() to compare Var nodes. For the Vars transfered from
+		 * another relation, some parameters such as varoattno and location
+		 * are different. They are not meaningful for the purposes of
+		 * Maybe just don't compare them?
+		 */
+		if (!contain_mutable_functions((Node *) newClause)
+			&& predicate_implied_by(list_make1(newClause), mergedRinfos,
+								 /* weak = */ false ))
+			continue;			/* provably implied by r1 */
+
+		/*
+		 * Make a new rinfo instead of copying, because it has quite a few
+		 * internal fields that depend on relid.
+		 */
+		newRinfo = make_restrictinfo(newClause,
+								  oldRinfo->is_pushed_down,
+								  oldRinfo->outerjoin_delayed,
+								  oldRinfo->pseudoconstant,
+								  oldRinfo->security_level,
+								  bms_make_singleton(outerrel->relid) /* required relids */,
+								  NULL /* outer relids */,
+								  oldRinfo->nullable_relids);
+		mergedRinfos = lappend(mergedRinfos, newRinfo);
+	}
+
+	/*
+	 * Pretend that the join relation is a base relation, and
+	 * plan it as usual.
+	 */
+	init_simple_rel(root, joinrel, outerrel->relid);
+
+	joinrel->baserestrictinfo = mergedRinfos;
+	joinrel->relids = bms_make_singleton(joinrel->relid);
+
+	set_plain_rel_size(root, joinrel);
+	set_plain_rel_pathlist(root, joinrel);
+
+	joinrel->relids = oldRelids;
+
+	elog(LOG, "Removed self join.");
+
+	return true;
+}
+
 /*
  * populate_joinrel_with_paths
  *	  Add paths to the given joinrel for given pair of joining relations. The
@@ -786,6 +1024,10 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
 				mark_dummy_rel(joinrel);
 				break;
 			}
+
+			if (reduce_self_unique_join(root, rel1, rel2, joinrel, restrictlist))
+				break;
+
 			add_paths_to_joinrel(root, joinrel, rel1, rel2,
 								 JOIN_INNER, sjinfo,
 								 restrictlist);
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 0e73f9c..128af10 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -601,7 +601,7 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
 		 * reference to unique indexes.  Make sure there's at least one
 		 * suitable unique index.  It must be immediately enforced, and if
 		 * it's a partial index, it must match the query.  (Keep these
-		 * conditions in sync with relation_has_unique_index_for!)
+		 * conditions in sync with relation_get_unique_index_for!)
 		 */
 		ListCell   *lc;
 
@@ -658,10 +658,10 @@ rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
 	{
 		/*
 		 * Examine the indexes to see if we have a matching unique index.
-		 * relation_has_unique_index_for automatically adds any usable
+		 * relation_get_unique_index_for automatically adds any usable
 		 * restriction clauses for the rel, so we needn't do that here.
 		 */
-		if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
+		if (relation_get_unique_index_for(root, rel, clause_list, NIL, NIL))
 			return true;
 	}
 	else if (rel->rtekind == RTE_SUBQUERY)
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 0317763..bc9741a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -4593,9 +4593,17 @@ fix_indexqual_references(PlannerInfo *root, IndexPath *index_path)
 			 * Check to see if the indexkey is on the right; if so, commute
 			 * the clause.  The indexkey should be the side that refers to
 			 * (only) the base relation.
+			 *
+			 * index->rel->relids can be a multi-bit set, so the check
+			 * cannot be simplified to a plain comparison. The multi-bit
+			 * relids are produced by the unique inner join removal, see
+			 * reduce_self_unique_join().
 			 */
-			if (!bms_equal(rinfo->left_relids, index->rel->relids))
+			if (!bms_is_empty(rinfo->right_relids)
+				&& bms_is_subset(rinfo->right_relids, index->rel->relids))
+			{
 				CommuteOpExpr(op);
+			}
 
 			/*
 			 * Now replace the indexkey expression with an index Var.
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index e190ad4..c65474f 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1583,7 +1583,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 	 * clauses for the rel, as well.
 	 */
 	if (rel->rtekind == RTE_RELATION && sjinfo->semi_can_btree &&
-		relation_has_unique_index_for(root, rel, NIL,
+		relation_get_unique_index_for(root, rel, NIL,
 									  sjinfo->semi_rhs_exprs,
 									  sjinfo->semi_operators))
 	{
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index cafde30..d2f8bcb 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -50,6 +50,8 @@ extern PGDLLIMPORT join_search_hook_type join_search_hook;
 
 extern RelOptInfo *make_one_rel(PlannerInfo *root, List *joinlist);
 extern void set_dummy_rel_pathlist(RelOptInfo *rel);
+extern void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel);
+extern void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel);
 extern RelOptInfo *standard_join_search(PlannerInfo *root, int levels_needed,
 					 List *initial_rels);
 
@@ -71,7 +73,7 @@ extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel);
  *	  routines to generate index paths
  */
 extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
-extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
+extern IndexOptInfo *relation_get_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
 							  List *restrictlist,
 							  List *exprlist, List *oprlist);
 extern bool indexcol_is_bool_constant_for_query(IndexOptInfo *index,
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index cbc882d..7f3691f 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2918,6 +2918,65 @@ where nt3.id = 1 and ss2.b3;
 (1 row)
 
 --
+-- test removal of semi or inner joins on unique columns
+-- !!!FIXME check coverage
+--
+analyze nt1;
+explain (costs off)
+select a.* from nt1 a
+join (select * from nt1 where a1) b on a.id = b.id;
+    QUERY PLAN     
+-------------------
+ Seq Scan on nt1 a
+   Filter: a1
+(2 rows)
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id) and id < 2;
+     QUERY PLAN     
+--------------------
+ Seq Scan on nt1 a
+   Filter: (id < 2)
+(2 rows)
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id and id < 2);
+     QUERY PLAN     
+--------------------
+ Seq Scan on nt1 a
+   Filter: (id < 2)
+(2 rows)
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id) and a1;
+    QUERY PLAN     
+-------------------
+ Seq Scan on nt1 a
+   Filter: a1
+(2 rows)
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id and a1);
+    QUERY PLAN     
+-------------------
+ Seq Scan on nt1 a
+   Filter: a1
+(2 rows)
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id and a1) and id < 2;
+         QUERY PLAN          
+-----------------------------
+ Seq Scan on nt1 a
+   Filter: (a1 AND (id < 2))
+(2 rows)
+
+--
 -- test case where a PlaceHolderVar is propagated into a subquery
 --
 explain (costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 86c6d5b..1fc6a02 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -851,6 +851,36 @@ from nt3 as nt3
 where nt3.id = 1 and ss2.b3;
 
 --
+-- test removal of semi or inner joins on unique columns
+-- !!!FIXME check coverage
+--
+analyze nt1;
+
+explain (costs off)
+select a.* from nt1 a
+join (select * from nt1 where a1) b on a.id = b.id;
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id) and id < 2;
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id and id < 2);
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id) and a1;
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id and a1);
+
+explain (costs off)
+select a.* from nt1 a
+where exists (select * from nt1 where id = a.id and a1) and id < 2;
+
+--
 -- test case where a PlaceHolderVar is propagated into a subquery
 --