Teach planner how to rearrange join order for some classes of OUTER JOIN.

Per my recent proposal.  I ended up basing the implementation on the
existing mechanism for enforcing valid join orders of IN joins --- the
rules for valid outer-join orders are somewhat similar.

7 files changed, 52 insertions, 33 deletions

diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index e9ec4b8ad65..0d6a4871ac2 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.178 2005/11/22 18:17:30 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.179 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -186,6 +186,7 @@ typedef enum NodeTag
 	T_PathKeyItem,
 	T_RestrictInfo,
 	T_InnerIndexscanInfo,
+	T_OuterJoinInfo,
 	T_InClauseInfo,
 
 	/*
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 1cdd64b26eb..40fda441b97 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -10,7 +10,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.109 2005/10/15 02:49:45 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.110 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -845,12 +845,7 @@ typedef struct TargetEntry
  * or qualified join.  Also, FromExpr nodes can appear to denote an
  * ordinary cross-product join ("FROM foo, bar, baz WHERE ...").
  * FromExpr is like a JoinExpr of jointype JOIN_INNER, except that it
- * may have any number of child nodes, not just two.  Also, there is an
- * implementation-defined difference: the planner is allowed to join the
- * children of a FromExpr using whatever join order seems good to it.
- * At present, JoinExpr nodes are always joined in exactly the order
- * implied by the jointree structure (except the planner may choose to
- * swap inner and outer members of a join pair).
+ * may have any number of child nodes, not just two.
  *
  * NOTE: the top level of a Query's jointree is always a FromExpr.
  * Even if the jointree contains no rels, there will be a FromExpr.
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index aa6217d0313..1d490fc17bf 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.121 2005/11/26 22:14:57 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.122 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -97,6 +97,8 @@ typedef struct PlannerInfo
 	List	   *full_join_clauses;		/* list of RestrictInfos for full
 										 * outer join clauses */
 
+	List	   *oj_info_list;	/* list of OuterJoinInfos */
+
 	List	   *in_info_list;	/* list of InClauseInfos */
 
 	List	   *query_pathkeys; /* desired pathkeys for query_planner(), and
@@ -201,10 +203,6 @@ typedef struct PlannerInfo
  *					participates (only used for base rels)
  *		baserestrictcost - Estimated cost of evaluating the baserestrictinfo
  *					clauses at a single tuple (only used for base rels)
- *		outerjoinset - For a base rel: if the rel appears within the nullable
- *					side of an outer join, the set of all relids
- *					participating in the highest such outer join; else NULL.
- *					Otherwise, unused.
  *		joininfo  - List of RestrictInfo nodes, containing info about each
  *					join clause in which this relation participates
  *		index_outer_relids - only used for base rels; set of outer relids
@@ -228,10 +226,6 @@ typedef struct PlannerInfo
  * We store baserestrictcost in the RelOptInfo (for base relations) because
  * we know we will need it at least once (to price the sequential scan)
  * and may need it multiple times to price index scans.
- *
- * outerjoinset is used to ensure correct placement of WHERE clauses that
- * apply to outer-joined relations; we must not apply such WHERE clauses
- * until after the outer join is performed.
  *----------
  */
 typedef enum RelOptKind
@@ -277,7 +271,6 @@ typedef struct RelOptInfo
 	List	   *baserestrictinfo;		/* RestrictInfo structures (if base
 										 * rel) */
 	QualCost	baserestrictcost;		/* cost of evaluating the above */
-	Relids		outerjoinset;	/* set of base relids */
 	List	   *joininfo;		/* RestrictInfo structures for join clauses
 								 * involving this rel */
 
@@ -831,6 +824,40 @@ typedef struct InnerIndexscanInfo
 } InnerIndexscanInfo;
 
 /*
+ * Outer join info.
+ *
+ * One-sided outer joins constrain the order of joining partially but not
+ * completely.  We flatten such joins into the planner's top-level list of
+ * relations to join, but record information about each outer join in an
+ * OuterJoinInfo struct.  These structs are kept in the PlannerInfo node's
+ * oj_info_list.
+ *
+ * min_lefthand and min_righthand are the sets of base relids that must be
+ * available on each side when performing the outer join.  lhs_strict is
+ * true if the outer join's condition cannot succeed when the LHS variables
+ * are all NULL (this means that the outer join can commute with upper-level
+ * outer joins even if it appears in their RHS).  We don't bother to set
+ * lhs_strict for FULL JOINs, however.
+ *
+ * It is not valid for either min_lefthand or min_righthand to be empty sets;
+ * if they were, this would break the logic that enforces join order.
+ *
+ * Note: OuterJoinInfo directly represents only LEFT JOIN and FULL JOIN;
+ * RIGHT JOIN is handled by switching the inputs to make it a LEFT JOIN.
+ * We make an OuterJoinInfo for FULL JOINs even though there is no flexibility
+ * of planning for them, because this simplifies make_join_rel()'s API.
+ */
+
+typedef struct OuterJoinInfo
+{
+	NodeTag		type;
+	Relids		min_lefthand;	/* base relids in minimum LHS for join */
+	Relids		min_righthand;	/* base relids in minimum RHS for join */
+	bool		is_full_join;	/* it's a FULL OUTER JOIN */
+	bool		lhs_strict;		/* joinclause is strict for some LHS rel */
+} OuterJoinInfo;
+
+/*
  * IN clause info.
  *
  * When we convert top-level IN quals into join operations, we must restrict
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index bf00f2cc97e..0d3770dc5c4 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/clauses.h,v 1.80 2005/10/15 02:49:45 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/clauses.h,v 1.81 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -57,6 +57,7 @@ extern bool contain_subplans(Node *clause);
 extern bool contain_mutable_functions(Node *clause);
 extern bool contain_volatile_functions(Node *clause);
 extern bool contain_nonstrict_functions(Node *clause);
+extern Relids find_nonnullable_rels(Node *clause);
 
 extern bool is_pseudo_constant_clause(Node *clause);
 extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index eba65c699c0..afe3a70d71b 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.89 2005/11/25 19:47:50 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.90 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,8 +23,7 @@
 extern bool enable_geqo;
 extern int	geqo_threshold;
 
-extern RelOptInfo *make_one_rel(PlannerInfo *root);
-extern RelOptInfo *make_fromexpr_rel(PlannerInfo *root, FromExpr *from);
+extern RelOptInfo *make_one_rel(PlannerInfo *root, List *joinlist);
 
 #ifdef OPTIMIZER_DEBUG
 extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel);
@@ -88,10 +87,8 @@ extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
  *	  routines to determine which relations to join
  */
 extern List *make_rels_by_joins(PlannerInfo *root, int level, List **joinrels);
-extern RelOptInfo *make_jointree_rel(PlannerInfo *root, Node *jtnode);
 extern RelOptInfo *make_join_rel(PlannerInfo *root,
-			  RelOptInfo *rel1, RelOptInfo *rel2,
-			  JoinType jointype);
+			  RelOptInfo *rel1, RelOptInfo *rel2);
 
 /*
  * pathkeys.c
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 0e78933f792..97d2287b5c8 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.90 2005/10/15 02:49:45 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.91 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -65,10 +65,12 @@ extern bool is_projection_capable_plan(Plan *plan);
 /*
  * prototypes for plan/initsplan.c
  */
+extern int	from_collapse_limit;
+extern int	join_collapse_limit;
+
 extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
 extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
-extern Relids distribute_quals_to_rels(PlannerInfo *root, Node *jtnode,
-						 bool below_outer_join);
+extern List *deconstruct_jointree(PlannerInfo *root);
 extern void process_implied_equality(PlannerInfo *root,
 						 Node *item1, Node *item2,
 						 Oid sortop1, Oid sortop2,
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index c26e6491f34..ce89771b179 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/prep.h,v 1.52 2005/10/15 02:49:45 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/prep.h,v 1.53 2005/12/20 02:30:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,14 +21,10 @@
 /*
  * prototypes for prepjointree.c
  */
-extern int	from_collapse_limit;
-extern int	join_collapse_limit;
-
 extern Node *pull_up_IN_clauses(PlannerInfo *root, Node *node);
 extern Node *pull_up_subqueries(PlannerInfo *root, Node *jtnode,
 				   bool below_outer_join);
 extern void reduce_outer_joins(PlannerInfo *root);
-extern Node *simplify_jointree(PlannerInfo *root, Node *jtnode);
 extern Relids get_relids_in_jointree(Node *jtnode);
 extern Relids get_relids_for_join(PlannerInfo *root, int joinrelid);