alternative-join-removal-0.patch

Index: src/backend/optimizer/path/joinpath.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v
retrieving revision 1.131
diff -c -r1.131 joinpath.c
*** src/backend/optimizer/path/joinpath.c	22 Mar 2010 13:57:15 -0000	1.131
--- src/backend/optimizer/path/joinpath.c	28 Mar 2010 03:50:58 -0000
***************
*** 22,32 ****
  #include "optimizer/paths.h"
  
  
- static bool join_is_removable(PlannerInfo *root, RelOptInfo *joinrel,
- 				  RelOptInfo *outerrel, RelOptInfo *innerrel,
- 				  List *restrictlist, JoinType jointype);
- static void generate_outer_only(PlannerInfo *root, RelOptInfo *joinrel,
- 					RelOptInfo *outerrel);
  static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
  					 RelOptInfo *outerrel, RelOptInfo *innerrel,
  					 List *restrictlist, List *mergeclause_list,
--- 22,27 ----
***************
*** 84,109 ****
  	List	   *mergeclause_list = NIL;
  
  	/*
- 	 * 0. Consider join removal.  This is always the most efficient strategy,
- 	 * so if it works, there's no need to consider anything further.
- 	 */
- 	if (join_is_removable(root, joinrel, outerrel, innerrel,
- 						  restrictlist, jointype))
- 	{
- 		generate_outer_only(root, joinrel, outerrel);
- 		return;
- 	}
- 
- 	/*
  	 * Find potential mergejoin clauses.  We can skip this if we are not
  	 * interested in doing a mergejoin.  However, mergejoin is currently our
  	 * only way of implementing full outer joins, so override mergejoin
  	 * disable if it's a full join.
- 	 *
- 	 * Note: do this after join_is_removable(), because this sets the
- 	 * outer_is_left flags in the mergejoin clauses, while join_is_removable
- 	 * uses those flags for its own purposes.  Currently, they set the flags
- 	 * the same way anyway, but let's avoid unnecessary entanglement.
  	 */
  	if (enable_mergejoin || jointype == JOIN_FULL)
  		mergeclause_list = select_mergejoin_clauses(root,
--- 79,88 ----
***************
*** 165,182 ****
   * we set the transient flag outer_is_left to identify which side is which.
   */
  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;
--- 144,161 ----
   * 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;
***************
*** 187,193 ****
  
  /*
   * join_is_removable
!  *	  Determine whether we need not perform the join at all, because
   *	  it will just duplicate its left input.
   *
   * This is true for a left join for which the join condition cannot match
--- 166,172 ----
  
  /*
   * join_is_removable
!  *	  Determine whether we need not perform a special join at all, because
   *	  it will just duplicate its left input.
   *
   * This is true for a left join for which the join condition cannot match
***************
*** 195,213 ****
   * cases, but we don't have the infrastructure to prove them.)  We also
   * have to check that the inner side doesn't generate any variables needed
   * above the join.
-  *
-  * Note: there is no need to consider the symmetrical case of duplicating the
-  * right input, because add_paths_to_joinrel() will be called with each rel
-  * on the outer side.
   */
! static bool
! join_is_removable(PlannerInfo *root,
! 				  RelOptInfo *joinrel,
! 				  RelOptInfo *outerrel,
! 				  RelOptInfo *innerrel,
! 				  List *restrictlist,
! 				  JoinType jointype)
  {
  	List	   *clause_list = NIL;
  	ListCell   *l;
  	int			attroff;
--- 174,186 ----
   * cases, but we don't have the infrastructure to prove them.)  We also
   * have to check that the inner side doesn't generate any variables needed
   * above the join.
   */
! bool
! join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
  {
+ 	int			innerrelid;
+ 	RelOptInfo *innerrel;
+ 	Relids		joinrelids;
  	List	   *clause_list = NIL;
  	ListCell   *l;
  	int			attroff;
***************
*** 220,227 ****
  	 * now we just make sure there are indexes of some sort or other.  If none
  	 * of them are unique, join removal will still fail, just slightly later.
  	 */
! 	if (jointype != JOIN_LEFT ||
! 		innerrel->reloptkind == RELOPT_JOINREL ||
  		innerrel->rtekind != RTE_RELATION ||
  		innerrel->indexlist == NIL)
  		return false;
--- 193,207 ----
  	 * now we just make sure there are indexes of some sort or other.  If none
  	 * of them are unique, join removal will still fail, just slightly later.
  	 */
! 	if (sjinfo->jointype != JOIN_LEFT ||
! 		sjinfo->delay_upper_joins ||
! 		bms_membership(sjinfo->min_righthand) != BMS_SINGLETON)
! 		return false;
! 
! 	innerrelid = bms_singleton_member(sjinfo->min_righthand);
! 	innerrel = find_base_rel(root, innerrelid);
! 
! 	if (innerrel->reloptkind != RELOPT_BASEREL ||
  		innerrel->rtekind != RTE_RELATION ||
  		innerrel->indexlist == NIL)
  		return false;
***************
*** 239,249 ****
  	 * theory that the system attributes are somewhat less likely to be wanted
  	 * and should be tested last.
  	 */
  	for (attroff = innerrel->max_attr - innerrel->min_attr;
  		 attroff >= 0;
  		 attroff--)
  	{
! 		if (!bms_is_subset(innerrel->attr_needed[attroff], joinrel->relids))
  			return false;
  	}
  
--- 219,231 ----
  	 * theory that the system attributes are somewhat less likely to be wanted
  	 * and should be tested last.
  	 */
+ 	joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+ 
  	for (attroff = innerrel->max_attr - innerrel->min_attr;
  		 attroff >= 0;
  		 attroff--)
  	{
! 		if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
  			return false;
  	}
  
***************
*** 256,262 ****
  		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
  
  		if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) &&
! 			!bms_is_subset(phinfo->ph_needed, joinrel->relids))
  			return false;
  	}
  
--- 238,244 ----
  		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
  
  		if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) &&
! 			!bms_is_subset(phinfo->ph_needed, joinrelids))
  			return false;
  	}
  
***************
*** 267,282 ****
  	 * it's what we want.  The mergejoinability test also eliminates clauses
  	 * containing volatile functions, which we couldn't depend on.
  	 */
! 	foreach(l, restrictlist)
  	{
  		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
  
  		/*
  		 * If we find a pushed-down clause, it must have come from above the
  		 * outer join and it must contain references to the inner rel.	(If it
  		 * had only outer-rel variables, it'd have been pushed down into the
  		 * outer rel.)	Therefore, we can conclude that join removal is unsafe
  		 * without any examination of the clause contents.
  		 */
  		if (restrictinfo->is_pushed_down)
  			return false;
--- 249,270 ----
  	 * it's what we want.  The mergejoinability test also eliminates clauses
  	 * containing volatile functions, which we couldn't depend on.
  	 */
! 	foreach(l, innerrel->joininfo)
  	{
  		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
  
+ 		/* Ignore clauses not pertinent to this join */
+ 		if (!bms_is_subset(restrictinfo->required_relids, joinrelids))
+ 			continue;
+ 
  		/*
  		 * If we find a pushed-down clause, it must have come from above the
  		 * outer join and it must contain references to the inner rel.	(If it
  		 * had only outer-rel variables, it'd have been pushed down into the
  		 * outer rel.)	Therefore, we can conclude that join removal is unsafe
  		 * without any examination of the clause contents.
+ 		 *
+ 		 * XXX still appropriate?
  		 */
  		if (restrictinfo->is_pushed_down)
  			return false;
***************
*** 289,295 ****
  		/*
  		 * Check if clause has the form "outer op inner" or "inner op outer".
  		 */
! 		if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
  			continue;			/* no good for these input relations */
  
  		/* OK, add to list */
--- 277,284 ----
  		/*
  		 * Check if clause has the form "outer op inner" or "inner op outer".
  		 */
! 		if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
! 									 innerrel->relids))
  			continue;			/* no good for these input relations */
  
  		/* OK, add to list */
***************
*** 1031,1037 ****
  		/*
  		 * Check if clause has the form "outer op inner" or "inner op outer".
  		 */
! 		if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
  			continue;			/* no good for these input relations */
  
  		hashclauses = lappend(hashclauses, restrictinfo);
--- 1020,1027 ----
  		/*
  		 * Check if clause has the form "outer op inner" or "inner op outer".
  		 */
! 		if (!clause_sides_match_join(restrictinfo, outerrel->relids,
! 									 innerrel->relids))
  			continue;			/* no good for these input relations */
  
  		hashclauses = lappend(hashclauses, restrictinfo);
***************
*** 1216,1222 ****
  		/*
  		 * Check if clause has the form "outer op inner" or "inner op outer".
  		 */
! 		if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
  		{
  			have_nonmergeable_joinclause = true;
  			continue;			/* no good for these input relations */
--- 1206,1213 ----
  		/*
  		 * Check if clause has the form "outer op inner" or "inner op outer".
  		 */
! 		if (!clause_sides_match_join(restrictinfo, outerrel->relids,
! 									 innerrel->relids))
  		{
  			have_nonmergeable_joinclause = true;
  			continue;			/* no good for these input relations */
Index: src/backend/optimizer/plan/planmain.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v
retrieving revision 1.117
diff -c -r1.117 planmain.c
*** src/backend/optimizer/plan/planmain.c	2 Jan 2010 16:57:47 -0000	1.117
--- src/backend/optimizer/plan/planmain.c	28 Mar 2010 03:50:58 -0000
***************
*** 29,34 ****
--- 29,37 ----
  #include "utils/selfuncs.h"
  
  
+ static List *remove_useless_joins(PlannerInfo *root, List *joinlist);
+ 
+ 
  /*
   * query_planner
   *	  Generate a path (that is, a simplified plan) for a basic query,
***************
*** 249,254 ****
--- 252,264 ----
  	fix_placeholder_eval_levels(root);
  
  	/*
+ 	 * Remove any useless outer joins.  Ideally this would be done during
+ 	 * jointree preprocessing, but the necessary information isn't available
+ 	 * until now.
+ 	 */
+ 	joinlist = remove_useless_joins(root, joinlist);
+ 
+ 	/*
  	 * Ready to do the primary planning.
  	 */
  	final_rel = make_one_rel(root, joinlist);
***************
*** 404,406 ****
--- 414,579 ----
  	*cheapest_path = cheapestpath;
  	*sorted_path = sortedpath;
  }
+ 
+ extern bool
+ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
+ static void
+ remove_rel_from_query(PlannerInfo *root, int relid);
+ static List *
+ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
+ 
+ static List *
+ remove_useless_joins(PlannerInfo *root, List *joinlist)
+ {
+ 	ListCell   *lc;
+ 
+ restart:
+ 	foreach(lc, root->join_info_list)
+ 	{
+ 		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+ 		int innerrelid;
+ 		int nremoved;
+ 
+ 		if (!join_is_removable(root, sjinfo))
+ 			continue;
+ 
+ 		/*
+ 		 * Currently, join_is_removable can only succeed when the sjinfo's
+ 		 * righthand is a single baserel.  Remove that rel from the joinlist.
+ 		 */
+ 		innerrelid = bms_singleton_member(sjinfo->min_righthand);
+ 
+ 		remove_rel_from_query(root, innerrelid);
+ 
+ 		nremoved = 0;
+ 		joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
+ 		if (nremoved != 1)
+ 			elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
+ 
+ 		/*
+ 		 * We can delete this SpecialJoinInfo too, since it's no longer of
+ 		 * interest.
+ 		 */
+ 		root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
+ 
+ 		/*
+ 		 * Restart the scan.  This is necessary to ensure we find all removable
+ 		 * joins independently of ordering of the join_info_list (note that
+ 		 * removal of attr_needed bits may make a join appear removable that
+ 		 * did not before).  Also, since we just deleted the current list
+ 		 * cell, we'd have to have some hack to continue the list search
+ 		 * anyway.
+ 		 */
+ 		goto restart;
+ 	}
+ 
+ 	return joinlist;
+ }
+ 
+ /*
+  * Remove the target relid from the planner's data structures.
+  *
+  * We are not terribly thorough here.  We must make sure that the rel is
+  * no longer visible as a baserel, and that attributes of other baserels
+  * are no longer marked as being needed at joins involving this rel.
+  * We don't have to bother removing join quals involving the rel from the
+  * joininfo lists; they'll just get ignored since we will never form a
+  * join relation that appears to match them.
+  */
+ static void
+ remove_rel_from_query(PlannerInfo *root, int relid)
+ {
+ 	RelOptInfo *rel = find_base_rel(root, relid);
+ 	Index		rti;
+ 	ListCell   *l;
+ 
+ 	/*
+ 	 * Mark the rel as an "other" rel instead of a "base" rel, since it
+ 	 * is no longer part of the join tree.  (Could we remove it from
+ 	 * the baserel array altogether?  Or use a dedicated reloptkind?)
+ 	 */
+ 	rel->reloptkind = RELOPT_OTHER_MEMBER_REL;
+ 
+ 	/*
+ 	 * Remove references to the rel from other baserels' attr_needed arrays.
+ 	 */
+ 	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+ 	{
+ 		RelOptInfo *otherrel = root->simple_rel_array[rti];
+ 		int			attroff;
+ 
+ 		/* there may be empty slots corresponding to non-baserel RTEs */
+ 		if (otherrel == NULL)
+ 			continue;
+ 
+ 		Assert(otherrel->relid == rti);		/* sanity check on array */
+ 
+ 		for (attroff = otherrel->max_attr - otherrel->min_attr;
+ 			 attroff >= 0;
+ 			 attroff--)
+ 		{
+ 			otherrel->attr_needed[attroff] =
+ 				bms_del_member(otherrel->attr_needed[attroff], relid);
+ 		}
+ 	}
+ 
+ 	/*
+ 	 * Likewise remove references from PlaceHolderVar data structures.
+ 	 */
+ 	foreach(l, root->placeholder_list)
+ 	{
+ 		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
+ 
+ 		phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
+ 		phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
+ 	}
+ }
+ 
+ /*
+  * Remove any occurrences of the target relid from a joinlist structure.
+  *
+  * It's easiest to build a whole new list structure, so we handle it that
+  * way.  Efficiency is not a big deal here.
+  *
+  * *nremoved is incremented by the number of occurrences removed (there
+  * should be exactly one, but the caller checks that).
+  */
+ static List *
+ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
+ {
+ 	List	   *result = NIL;
+ 	ListCell   *jl;
+ 
+ 	foreach(jl, joinlist)
+ 	{
+ 		Node	   *jlnode = (Node *) lfirst(jl);
+ 
+ 		if (IsA(jlnode, RangeTblRef))
+ 		{
+ 			int			varno = ((RangeTblRef *) jlnode)->rtindex;
+ 
+ 			if (varno == relid)
+ 				(*nremoved)++;
+ 			else
+ 				result = lappend(result, jlnode);
+ 		}
+ 		else if (IsA(jlnode, List))
+ 		{
+ 			/* Recurse to handle subproblem */
+ 			List   *sublist;
+ 
+ 			sublist = remove_rel_from_joinlist((List *) jlnode,
+ 											   relid, nremoved);
+ 			/* Avoid including empty sub-lists in the result */
+ 			if (sublist)
+ 				result = lappend(result, sublist);
+ 		}
+ 		else
+ 		{
+ 			elog(ERROR, "unrecognized joinlist node type: %d",
+ 				 (int) nodeTag(jlnode));
+ 		}
+ 	}
+ 
+ 	return result;
+ }
Index: src/test/regress/expected/join.out
===================================================================
RCS file: /cvsroot/pgsql/src/test/regress/expected/join.out,v
retrieving revision 1.44
diff -c -r1.44 join.out
*** src/test/regress/expected/join.out	22 Mar 2010 13:57:16 -0000	1.44
--- src/test/regress/expected/join.out	28 Mar 2010 03:50:59 -0000
***************
*** 2494,2499 ****
--- 2494,2531 ----
  --
  -- test join removal
  --
+ begin;
+ CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a"
+ CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b"
+ CREATE TEMP TABLE c (id int PRIMARY KEY);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "c_pkey" for table "c"
+ INSERT INTO a VALUES (0, 0), (1, NULL);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ INSERT INTO c VALUES (0), (1);
+ -- all three cases should be optimizable into a simple seqscan
+ explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id;
+   QUERY PLAN   
+ ---------------
+  Seq Scan on a
+ (1 row)
+ 
+ explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id;
+   QUERY PLAN   
+ ---------------
+  Seq Scan on b
+ (1 row)
+ 
+ explain (costs off)
+   SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id)
+   ON (a.b_id = b.id);
+   QUERY PLAN   
+ ---------------
+  Seq Scan on a
+ (1 row)
+ 
+ rollback;
  create temp table parent (k int primary key, pd int);
  NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "parent_pkey" for table "parent"
  create temp table child (k int unique, cd int);
***************
*** 2540,2542 ****
--- 2572,2595 ----
           ->  Seq Scan on child c
  (5 rows)
  
+ -- bug 5255: this is not optimizable by join removal
+ begin;
+ CREATE TEMP TABLE a (id int PRIMARY KEY);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a"
+ CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b"
+ INSERT INTO a VALUES (0), (1);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+  id | a_id | id 
+ ----+------+----
+   1 |      |   
+ (1 row)
+ 
+ SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+  id | a_id 
+ ----+------
+   1 |     
+ (1 row)
+ 
+ rollback;
Index: src/test/regress/sql/join.sql
===================================================================
RCS file: /cvsroot/pgsql/src/test/regress/sql/join.sql,v
retrieving revision 1.33
diff -c -r1.33 join.sql
*** src/test/regress/sql/join.sql	22 Mar 2010 13:57:16 -0000	1.33
--- src/test/regress/sql/join.sql	28 Mar 2010 03:50:59 -0000
***************
*** 572,577 ****
--- 572,595 ----
  -- test join removal
  --
  
+ begin;
+ 
+ CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int);
+ CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int);
+ CREATE TEMP TABLE c (id int PRIMARY KEY);
+ INSERT INTO a VALUES (0, 0), (1, NULL);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ INSERT INTO c VALUES (0), (1);
+ 
+ -- all three cases should be optimizable into a simple seqscan
+ explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id;
+ explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id;
+ explain (costs off)
+   SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id)
+   ON (a.b_id = b.id);
+ 
+ rollback;
+ 
  create temp table parent (k int primary key, pd int);
  create temp table child (k int unique, cd int);
  insert into parent values (1, 10), (2, 20), (3, 30);
***************
*** 590,592 ****
--- 608,623 ----
    select p.*, linked from parent p
      left join (select c.*, true as linked from child c) as ss
      on (p.k = ss.k);
+ 
+ -- bug 5255: this is not optimizable by join removal
+ begin;
+ 
+ CREATE TEMP TABLE a (id int PRIMARY KEY);
+ CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int);
+ INSERT INTO a VALUES (0), (1);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ 
+ SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+ SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+ 
+ rollback;