reduce-semijoins.patch

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 5aedcd1..93d9a3e 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
*************** add_paths_to_joinrel(PlannerInfo *root,
*** 126,135 ****
  	 *
  	 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
  	 * matter since the executor can make the equivalent optimization anyway;
! 	 * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
! 	 * know we're going to force uniqueness of the innerrel below.  For
! 	 * JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid letting that value escape
! 	 * this module.
  	 */
  	switch (jointype)
  	{
--- 126,141 ----
  	 *
  	 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
  	 * matter since the executor can make the equivalent optimization anyway;
! 	 * we need not expend planner cycles on proofs.  Furthermore, for either
! 	 * JOIN_SEMI or JOIN_UNIQUE_INNER, we must be considering a semijoin whose
! 	 * inner side is not provably unique --- else reduce_unique_semijoins
! 	 * would've simplified it --- so there's no point in calling
! 	 * innerrel_is_unique.  However, for JOIN_UNIQUE_INNER, if the LHS covers
! 	 * all of the associated semijoin's min_lefthand, then it's appropriate to
! 	 * set inner_unique because the path produced by create_unique_path will
! 	 * be unique relative to the LHS.  (If we have an LHS that's only part of
! 	 * the min_lefthand, that is *not* true.)  For JOIN_UNIQUE_OUTER, pass
! 	 * JOIN_INNER to avoid letting that value escape this module.
  	 */
  	switch (jointype)
  	{
*************** add_paths_to_joinrel(PlannerInfo *root,
*** 138,152 ****
  			extra.inner_unique = false; /* well, unproven */
  			break;
  		case JOIN_UNIQUE_INNER:
! 			extra.inner_unique = true;
  			break;
  		case JOIN_UNIQUE_OUTER:
! 			extra.inner_unique = innerrel_is_unique(root, outerrel, innerrel,
! 													JOIN_INNER, restrictlist);
  			break;
  		default:
! 			extra.inner_unique = innerrel_is_unique(root, outerrel, innerrel,
! 													jointype, restrictlist);
  			break;
  	}
  
--- 144,165 ----
  			extra.inner_unique = false; /* well, unproven */
  			break;
  		case JOIN_UNIQUE_INNER:
! 			extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
! 											   outerrel->relids);
  			break;
  		case JOIN_UNIQUE_OUTER:
! 			extra.inner_unique = innerrel_is_unique(root,
! 													outerrel->relids,
! 													innerrel,
! 													JOIN_INNER,
! 													restrictlist);
  			break;
  		default:
! 			extra.inner_unique = innerrel_is_unique(root,
! 													outerrel->relids,
! 													innerrel,
! 													jointype,
! 													restrictlist);
  			break;
  	}
  
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 69b9be4..dfcc930 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** static bool rel_is_distinct_for(PlannerI
*** 42,48 ****
  					List *clause_list);
  static Oid	distinct_col_search(int colno, List *colnos, List *opids);
  static bool is_innerrel_unique_for(PlannerInfo *root,
! 					   RelOptInfo *outerrel,
  					   RelOptInfo *innerrel,
  					   JoinType jointype,
  					   List *restrictlist);
--- 42,48 ----
  					List *clause_list);
  static Oid	distinct_col_search(int colno, List *colnos, List *opids);
  static bool is_innerrel_unique_for(PlannerInfo *root,
! 					   Relids outerrelids,
  					   RelOptInfo *innerrel,
  					   JoinType jointype,
  					   List *restrictlist);
*************** remove_rel_from_joinlist(List *joinlist,
*** 496,501 ****
--- 496,583 ----
  
  
  /*
+  * reduce_unique_semijoins
+  *		Check for semijoins that can be simplified to plain inner joins
+  *		because the inner relation is provably unique for the join clauses.
+  *
+  * Ideally this would happen during reduce_outer_joins, but we don't have
+  * enough information at that point.
+  *
+  * To perform the strength reduction when applicable, we need only delete
+  * the semijoin's SpecialJoinInfo from root->join_info_list.  (We don't
+  * bother fixing the join type attributed to it in the query jointree,
+  * since that won't be consulted again.)
+  */
+ void
+ reduce_unique_semijoins(PlannerInfo *root)
+ {
+ 	ListCell   *lc;
+ 	ListCell   *next;
+ 
+ 	/*
+ 	 * Scan the join_info_list to find semijoins.  We can't use foreach
+ 	 * because we may delete the current cell.
+ 	 */
+ 	for (lc = list_head(root->join_info_list); lc != NULL; lc = next)
+ 	{
+ 		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+ 		int			innerrelid;
+ 		RelOptInfo *innerrel;
+ 		Relids		joinrelids;
+ 		List	   *restrictlist;
+ 
+ 		next = lnext(lc);
+ 
+ 		/*
+ 		 * Must be a non-delaying semijoin to a single baserel, else we aren't
+ 		 * going to be able to do anything with it.  (It's probably not
+ 		 * possible for delay_upper_joins to be set on a semijoin, but we
+ 		 * might as well check.)
+ 		 */
+ 		if (sjinfo->jointype != JOIN_SEMI ||
+ 			sjinfo->delay_upper_joins)
+ 			continue;
+ 
+ 		if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
+ 			continue;
+ 
+ 		innerrel = find_base_rel(root, innerrelid);
+ 
+ 		/*
+ 		 * Before we trouble to run generate_join_implied_equalities, make a
+ 		 * quick check to eliminate cases in which we will surely be unable to
+ 		 * prove uniqueness of the innerrel.
+ 		 */
+ 		if (!rel_supports_distinctness(root, innerrel))
+ 			continue;
+ 
+ 		/* Compute the relid set for the join we are considering */
+ 		joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+ 
+ 		/*
+ 		 * Since we're only considering a single-rel RHS, any join clauses it
+ 		 * has must be clauses linking it to the semijoin's min_lefthand.  We
+ 		 * can also consider EC-derived join clauses.
+ 		 */
+ 		restrictlist =
+ 			list_concat(generate_join_implied_equalities(root,
+ 														 joinrelids,
+ 														 sjinfo->min_lefthand,
+ 														 innerrel),
+ 						innerrel->joininfo);
+ 
+ 		/* Test whether the innerrel is unique for those clauses. */
+ 		if (!innerrel_is_unique(root, sjinfo->min_lefthand, innerrel,
+ 								JOIN_SEMI, restrictlist))
+ 			continue;
+ 
+ 		/* OK, remove the SpecialJoinInfo from the list. */
+ 		root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
+ 	}
+ }
+ 
+ 
+ /*
   * rel_supports_distinctness
   *		Could the relation possibly be proven distinct on some set of columns?
   *
*************** distinct_col_search(int colno, List *col
*** 857,862 ****
--- 939,948 ----
   *	  Check if the innerrel provably contains at most one tuple matching any
   *	  tuple from the outerrel, based on join clauses in the 'restrictlist'.
   *
+  * We need an actual RelOptInfo for the innerrel, but it's sufficient to
+  * identify the outerrel by its Relids.  This asymmetry supports use of this
+  * function before joinrels have been built.
+  *
   * The proof must be made based only on clauses that will be "joinquals"
   * rather than "otherquals" at execution.  For an inner join there's no
   * difference; but if the join is outer, we must ignore pushed-down quals,
*************** distinct_col_search(int colno, List *col
*** 870,876 ****
   */
  bool
  innerrel_is_unique(PlannerInfo *root,
! 				   RelOptInfo *outerrel,
  				   RelOptInfo *innerrel,
  				   JoinType jointype,
  				   List *restrictlist)
--- 956,962 ----
   */
  bool
  innerrel_is_unique(PlannerInfo *root,
! 				   Relids outerrelids,
  				   RelOptInfo *innerrel,
  				   JoinType jointype,
  				   List *restrictlist)
*************** innerrel_is_unique(PlannerInfo *root,
*** 900,906 ****
  	{
  		Relids		unique_for_rels = (Relids) lfirst(lc);
  
! 		if (bms_is_subset(unique_for_rels, outerrel->relids))
  			return true;		/* Success! */
  	}
  
--- 986,992 ----
  	{
  		Relids		unique_for_rels = (Relids) lfirst(lc);
  
! 		if (bms_is_subset(unique_for_rels, outerrelids))
  			return true;		/* Success! */
  	}
  
*************** innerrel_is_unique(PlannerInfo *root,
*** 912,923 ****
  	{
  		Relids		unique_for_rels = (Relids) lfirst(lc);
  
! 		if (bms_is_subset(outerrel->relids, unique_for_rels))
  			return false;
  	}
  
  	/* No cached information, so try to make the proof. */
! 	if (is_innerrel_unique_for(root, outerrel, innerrel,
  							   jointype, restrictlist))
  	{
  		/*
--- 998,1009 ----
  	{
  		Relids		unique_for_rels = (Relids) lfirst(lc);
  
! 		if (bms_is_subset(outerrelids, unique_for_rels))
  			return false;
  	}
  
  	/* No cached information, so try to make the proof. */
! 	if (is_innerrel_unique_for(root, outerrelids, innerrel,
  							   jointype, restrictlist))
  	{
  		/*
*************** innerrel_is_unique(PlannerInfo *root,
*** 932,938 ****
  		 */
  		old_context = MemoryContextSwitchTo(root->planner_cxt);
  		innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
! 											bms_copy(outerrel->relids));
  		MemoryContextSwitchTo(old_context);
  
  		return true;			/* Success! */
--- 1018,1024 ----
  		 */
  		old_context = MemoryContextSwitchTo(root->planner_cxt);
  		innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
! 											bms_copy(outerrelids));
  		MemoryContextSwitchTo(old_context);
  
  		return true;			/* Success! */
*************** innerrel_is_unique(PlannerInfo *root,
*** 957,963 ****
  			old_context = MemoryContextSwitchTo(root->planner_cxt);
  			innerrel->non_unique_for_rels =
  				lappend(innerrel->non_unique_for_rels,
! 						bms_copy(outerrel->relids));
  			MemoryContextSwitchTo(old_context);
  		}
  
--- 1043,1049 ----
  			old_context = MemoryContextSwitchTo(root->planner_cxt);
  			innerrel->non_unique_for_rels =
  				lappend(innerrel->non_unique_for_rels,
! 						bms_copy(outerrelids));
  			MemoryContextSwitchTo(old_context);
  		}
  
*************** innerrel_is_unique(PlannerInfo *root,
*** 972,978 ****
   */
  static bool
  is_innerrel_unique_for(PlannerInfo *root,
! 					   RelOptInfo *outerrel,
  					   RelOptInfo *innerrel,
  					   JoinType jointype,
  					   List *restrictlist)
--- 1058,1064 ----
   */
  static bool
  is_innerrel_unique_for(PlannerInfo *root,
! 					   Relids outerrelids,
  					   RelOptInfo *innerrel,
  					   JoinType jointype,
  					   List *restrictlist)
*************** is_innerrel_unique_for(PlannerInfo *root
*** 1007,1013 ****
  		 * 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, outerrel->relids,
  									 innerrel->relids))
  			continue;			/* no good for these input relations */
  
--- 1093,1099 ----
  		 * 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, outerrelids,
  									 innerrel->relids))
  			continue;			/* no good for these input relations */
  
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index ef0de3f..74de3b8 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 193,198 ****
--- 193,204 ----
  	joinlist = remove_useless_joins(root, joinlist);
  
  	/*
+ 	 * Also, reduce any semijoins with unique inner rels to plain inner joins.
+ 	 * Likewise, this can't be done until now for lack of needed info.
+ 	 */
+ 	reduce_unique_semijoins(root);
+ 
+ 	/*
  	 * Now distribute "placeholders" to base rels as needed.  This has to be
  	 * done after join removal because removal could change whether a
  	 * placeholder is evaluable at a base rel.
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 5df68a2..88ac97e 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern void match_foreign_keys_to_quals(
*** 103,112 ****
   * prototypes for plan/analyzejoins.c
   */
  extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
  extern bool query_supports_distinctness(Query *query);
  extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
  extern bool innerrel_is_unique(PlannerInfo *root,
! 				   RelOptInfo *outerrel, RelOptInfo *innerrel,
  				   JoinType jointype, List *restrictlist);
  
  /*
--- 103,113 ----
   * prototypes for plan/analyzejoins.c
   */
  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 innerrel_is_unique(PlannerInfo *root,
! 				   Relids outerrelids, RelOptInfo *innerrel,
  				   JoinType jointype, List *restrictlist);
  
  /*
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 69ce7aa..d08b1e1 100644
*** a/src/test/regress/expected/join.out
--- b/src/test/regress/expected/join.out
*************** reset enable_sort;
*** 5634,5636 ****
--- 5634,5693 ----
  drop table j1;
  drop table j2;
  drop table j3;
+ -- check that semijoin inner is not seen as unique for a portion of the outerrel
+ explain (verbose, costs off)
+ select t1.unique1, t2.hundred
+ from onek t1, tenk1 t2
+ where exists (select 1 from tenk1 t3
+               where t3.thousand = t1.unique1 and t3.tenthous = t2.hundred)
+       and t1.unique1 < 1;
+                                    QUERY PLAN                                    
+ ---------------------------------------------------------------------------------
+  Nested Loop
+    Output: t1.unique1, t2.hundred
+    ->  Hash Join
+          Output: t1.unique1, t3.tenthous
+          Hash Cond: (t3.thousand = t1.unique1)
+          ->  HashAggregate
+                Output: t3.thousand, t3.tenthous
+                Group Key: t3.thousand, t3.tenthous
+                ->  Index Only Scan using tenk1_thous_tenthous on public.tenk1 t3
+                      Output: t3.thousand, t3.tenthous
+          ->  Hash
+                Output: t1.unique1
+                ->  Index Only Scan using onek_unique1 on public.onek t1
+                      Output: t1.unique1
+                      Index Cond: (t1.unique1 < 1)
+    ->  Index Only Scan using tenk1_hundred on public.tenk1 t2
+          Output: t2.hundred
+          Index Cond: (t2.hundred = t3.tenthous)
+ (18 rows)
+ 
+ -- ... unless it actually is unique
+ create table j3 as select unique1, tenthous from onek;
+ vacuum analyze j3;
+ create unique index on j3(unique1, tenthous);
+ explain (verbose, costs off)
+ select t1.unique1, t2.hundred
+ from onek t1, tenk1 t2
+ where exists (select 1 from j3
+               where j3.unique1 = t1.unique1 and j3.tenthous = t2.hundred)
+       and t1.unique1 < 1;
+                                QUERY PLAN                               
+ ------------------------------------------------------------------------
+  Nested Loop
+    Output: t1.unique1, t2.hundred
+    ->  Nested Loop
+          Output: t1.unique1, j3.tenthous
+          ->  Index Only Scan using onek_unique1 on public.onek t1
+                Output: t1.unique1
+                Index Cond: (t1.unique1 < 1)
+          ->  Index Only Scan using j3_unique1_tenthous_idx on public.j3
+                Output: j3.unique1, j3.tenthous
+                Index Cond: (j3.unique1 = t1.unique1)
+    ->  Index Only Scan using tenk1_hundred on public.tenk1 t2
+          Output: t2.hundred
+          Index Cond: (t2.hundred = j3.tenthous)
+ (13 rows)
+ 
+ drop table j3;
diff --git a/src/test/regress/expected/updatable_views.out b/src/test/regress/expected/updatable_views.out
index aa06d1d..f6b51a5 100644
*** a/src/test/regress/expected/updatable_views.out
--- b/src/test/regress/expected/updatable_views.out
*************** EXPLAIN (costs off) UPDATE rw_view1 SET 
*** 1673,1679 ****
                             QUERY PLAN                            
  -----------------------------------------------------------------
   Update on base_tbl b
!    ->  Hash Semi Join
           Hash Cond: (b.a = r.a)
           ->  Seq Scan on base_tbl b
           ->  Hash
--- 1673,1679 ----
                             QUERY PLAN                            
  -----------------------------------------------------------------
   Update on base_tbl b
!    ->  Hash Join
           Hash Cond: (b.a = r.a)
           ->  Seq Scan on base_tbl b
           ->  Hash
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 4fc8fd5..c3994ea 100644
*** a/src/test/regress/sql/join.sql
--- b/src/test/regress/sql/join.sql
*************** reset enable_sort;
*** 1856,1858 ****
--- 1856,1880 ----
  drop table j1;
  drop table j2;
  drop table j3;
+ 
+ -- check that semijoin inner is not seen as unique for a portion of the outerrel
+ explain (verbose, costs off)
+ select t1.unique1, t2.hundred
+ from onek t1, tenk1 t2
+ where exists (select 1 from tenk1 t3
+               where t3.thousand = t1.unique1 and t3.tenthous = t2.hundred)
+       and t1.unique1 < 1;
+ 
+ -- ... unless it actually is unique
+ create table j3 as select unique1, tenthous from onek;
+ vacuum analyze j3;
+ create unique index on j3(unique1, tenthous);
+ 
+ explain (verbose, costs off)
+ select t1.unique1, t2.hundred
+ from onek t1, tenk1 t2
+ where exists (select 1 from j3
+               where j3.unique1 = t1.unique1 and j3.tenthous = t2.hundred)
+       and t1.unique1 < 1;
+ 
+ drop table j3;