Allow the planner to collapse explicit inner JOINs together, rather than

necessarily following the JOIN syntax to develop the query plan.  The old
behavior is still available by setting GUC variable JOIN_COLLAPSE_LIMIT
to 1.  Also create a GUC variable FROM_COLLAPSE_LIMIT to control the
similar decision about when to collapse sub-SELECT lists into their parent
lists.  (This behavior existed already, but the limit was always
GEQO_THRESHOLD/2; now it's separately adjustable.)

5 files changed, 119 insertions, 28 deletions

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index f85144b8184..6c40a16e32a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.94 2003/01/20 18:54:49 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.95 2003/01/25 23:10:27 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -30,8 +30,9 @@
 #include "rewrite/rewriteManip.h"
 
 
-bool		enable_geqo = true;
-int			geqo_rels = DEFAULT_GEQO_RELS;
+/* These parameters are set by GUC */
+bool		enable_geqo = false;	/* just in case GUC doesn't set it */
+int			geqo_threshold;
 
 
 static void set_base_rel_pathlists(Query *root);
@@ -422,7 +423,7 @@ make_fromexpr_rel(Query *root, FromExpr *from)
 		 * Consider the different orders in which we could join the rels,
 		 * using either GEQO or regular optimizer.
 		 */
-		if (enable_geqo && levels_needed >= geqo_rels)
+		if (enable_geqo && levels_needed >= geqo_threshold)
 			return geqo(root, levels_needed, initial_rels);
 		else
 			return make_one_rel_by_joins(root, levels_needed, initial_rels);
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 388380f8843..1b481ccbd25 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.141 2003/01/20 18:54:52 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.142 2003/01/25 23:10:27 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -167,12 +167,6 @@ subquery_planner(Query *parse, double tuple_fraction)
 		pull_up_subqueries(parse, (Node *) parse->jointree, false);
 
 	/*
-	 * If so, we may have created opportunities to simplify the jointree.
-	 */
-	parse->jointree = (FromExpr *)
-		preprocess_jointree(parse, (Node *) parse->jointree);
-
-	/*
 	 * Detect whether any rangetable entries are RTE_JOIN kind; if not,
 	 * we can avoid the expense of doing flatten_join_alias_vars().
 	 * This must be done after we have done pull_up_subqueries, of course.
@@ -247,6 +241,16 @@ subquery_planner(Query *parse, double tuple_fraction)
 	parse->havingQual = (Node *) newHaving;
 
 	/*
+	 * See if we can simplify the jointree; opportunities for this may come
+	 * from having pulled up subqueries, or from flattening explicit JOIN
+	 * syntax.  We must do this after flattening JOIN alias variables, since
+	 * eliminating explicit JOIN nodes from the jointree will cause
+	 * get_relids_for_join() to fail.
+	 */
+	parse->jointree = (FromExpr *)
+		preprocess_jointree(parse, (Node *) parse->jointree);
+
+	/*
 	 * Do the main planning.  If we have an inherited target relation,
 	 * that needs special processing, else go straight to
 	 * grouping_planner.
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 083528c0490..68fbb1e1f53 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -9,14 +9,13 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.1 2003/01/20 18:54:54 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.2 2003/01/25 23:10:27 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #include "postgres.h"
 
 #include "optimizer/clauses.h"
-#include "optimizer/paths.h"
 #include "optimizer/prep.h"
 #include "optimizer/subselect.h"
 #include "optimizer/var.h"
@@ -24,6 +23,11 @@
 #include "rewrite/rewriteManip.h"
 
 
+/* These parameters are set by GUC */
+int		from_collapse_limit;
+int		join_collapse_limit;
+
+
 static bool is_simple_subquery(Query *subquery);
 static bool has_nullable_targetlist(Query *subquery);
 static void resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist);
@@ -467,7 +471,16 @@ resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist)
  * case we can consider collapsing the two FromExprs into one.	This is
  * an optional conversion, since the planner will work correctly either
  * way.  But we may find a better plan (at the cost of more planning time)
- * if we merge the two nodes.
+ * if we merge the two nodes, creating a single join search space out of
+ * two.  To allow the user to trade off planning time against plan quality,
+ * we provide a control parameter from_collapse_limit that limits the size
+ * of the join search space that can be created this way.
+ *
+ * We also consider flattening explicit inner JOINs into FromExprs (which
+ * will in turn allow them to be merged into parent FromExprs).  The tradeoffs
+ * here are the same as for flattening FromExprs, but we use a different
+ * control parameter so that the user can use explicit JOINs to control the
+ * join order even when they are inner JOINs.
  *
  * NOTE: don't try to do this in the same jointree scan that does subquery
  * pullup!	Since we're changing the jointree structure here, that wouldn't
@@ -492,7 +505,7 @@ preprocess_jointree(Query *parse, Node *jtnode)
 		{
 			Node	   *child = (Node *) lfirst(l);
 
-			/* Recursively simplify the child... */
+			/* Recursively simplify this child... */
 			child = preprocess_jointree(parse, child);
 			/* Now, is it a FromExpr? */
 			if (child && IsA(child, FromExpr))
@@ -500,21 +513,25 @@ preprocess_jointree(Query *parse, Node *jtnode)
 				/*
 				 * Yes, so do we want to merge it into parent?	Always do
 				 * so if child has just one element (since that doesn't
-				 * make the parent's list any longer).  Otherwise we have
-				 * to be careful about the increase in planning time
-				 * caused by combining the two join search spaces into
-				 * one.  Our heuristic is to merge if the merge will
-				 * produce a join list no longer than GEQO_RELS/2.
-				 * (Perhaps need an additional user parameter?)
+				 * make the parent's list any longer).  Otherwise merge if
+				 * the resulting join list would be no longer than
+				 * from_collapse_limit.
 				 */
 				FromExpr   *subf = (FromExpr *) child;
 				int			childlen = length(subf->fromlist);
 				int			myothers = length(newlist) + length(lnext(l));
 
-				if (childlen <= 1 || (childlen + myothers) <= geqo_rels / 2)
+				if (childlen <= 1 ||
+					(childlen + myothers) <= from_collapse_limit)
 				{
 					newlist = nconc(newlist, subf->fromlist);
-					f->quals = make_and_qual(subf->quals, f->quals);
+					/*
+					 * By now, the quals have been converted to implicit-AND
+					 * lists, so we just need to join the lists.  NOTE: we
+					 * put the pulled-up quals first.
+					 */
+					f->quals = (Node *) nconc((List *) subf->quals,
+											  (List *) f->quals);
 				}
 				else
 					newlist = lappend(newlist, child);
@@ -528,9 +545,64 @@ preprocess_jointree(Query *parse, Node *jtnode)
 	{
 		JoinExpr   *j = (JoinExpr *) jtnode;
 
-		/* Can't usefully change the JoinExpr, but recurse on children */
+		/* Recursively simplify the children... */
 		j->larg = preprocess_jointree(parse, j->larg);
 		j->rarg = preprocess_jointree(parse, j->rarg);
+		/*
+		 * If it is an outer join, we must not flatten it.  An inner join
+		 * is semantically equivalent to a FromExpr; we convert it to one,
+		 * allowing it to be flattened into its parent, if the resulting
+		 * FromExpr would have no more than join_collapse_limit members.
+		 */
+		if (j->jointype == JOIN_INNER && join_collapse_limit > 1)
+		{
+			int		leftlen,
+					rightlen;
+
+			if (j->larg && IsA(j->larg, FromExpr))
+				leftlen = length(((FromExpr *) j->larg)->fromlist);
+			else
+				leftlen = 1;
+			if (j->rarg && IsA(j->rarg, FromExpr))
+				rightlen = length(((FromExpr *) j->rarg)->fromlist);
+			else
+				rightlen = 1;
+			if ((leftlen + rightlen) <= join_collapse_limit)
+			{
+				FromExpr   *f = makeNode(FromExpr);
+
+				f->fromlist = NIL;
+				f->quals = NULL;
+
+				if (j->larg && IsA(j->larg, FromExpr))
+				{
+					FromExpr   *subf = (FromExpr *) j->larg;
+
+					f->fromlist = subf->fromlist;
+					f->quals = subf->quals;
+				}
+				else
+					f->fromlist = makeList1(j->larg);
+
+				if (j->rarg && IsA(j->rarg, FromExpr))
+				{
+					FromExpr   *subf = (FromExpr *) j->rarg;
+
+					f->fromlist = nconc(f->fromlist,
+										subf->fromlist);
+					f->quals = (Node *) nconc((List *) f->quals,
+											  (List *) subf->quals);
+				}
+				else
+					f->fromlist = lappend(f->fromlist, j->rarg);
+
+				/* pulled-up quals first */
+				f->quals = (Node *) nconc((List *) f->quals,
+										  (List *) j->quals);
+
+				return (Node *) f;
+			}
+		}
 	}
 	else
 		elog(ERROR, "preprocess_jointree: unexpected node type %d",
@@ -615,6 +687,9 @@ get_relids_in_jointree(Node *jtnode)
 
 /*
  * get_relids_for_join: get list of base RT indexes making up a join
+ *
+ * NB: this will not work reliably after preprocess_jointree() is run,
+ * since that may eliminate join nodes from the jointree.
  */
 List *
 get_relids_for_join(Query *parse, int joinrelid)
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 471d895ea72..9b726dcfe32 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -5,7 +5,7 @@
  * command, configuration file, and command line options.
  * See src/backend/utils/misc/README for more information.
  *
- * $Header: /cvsroot/pgsql/src/backend/utils/misc/guc.c,v 1.110 2003/01/10 22:03:29 petere Exp $
+ * $Header: /cvsroot/pgsql/src/backend/utils/misc/guc.c,v 1.111 2003/01/25 23:10:27 tgl Exp $
  *
  * Copyright 2000 by PostgreSQL Global Development Group
  * Written by Peter Eisentraut <peter_e@gmx.net>.
@@ -37,7 +37,7 @@
 #include "optimizer/cost.h"
 #include "optimizer/geqo.h"
 #include "optimizer/paths.h"
-#include "optimizer/planmain.h"
+#include "optimizer/prep.h"
 #include "parser/parse_expr.h"
 #include "storage/fd.h"
 #include "storage/freespace.h"
@@ -539,8 +539,16 @@ static struct config_int
 		10, 1, 1000, NULL, NULL
 	},
 	{
-		{"geqo_threshold", PGC_USERSET}, &geqo_rels,
-		DEFAULT_GEQO_RELS, 2, INT_MAX, NULL, NULL
+		{"from_collapse_limit", PGC_USERSET}, &from_collapse_limit,
+		8, 1, INT_MAX, NULL, NULL
+	},
+	{
+		{"join_collapse_limit", PGC_USERSET}, &join_collapse_limit,
+		8, 1, INT_MAX, NULL, NULL
+	},
+	{
+		{"geqo_threshold", PGC_USERSET}, &geqo_threshold,
+		11, 2, INT_MAX, NULL, NULL
 	},
 	{
 		{"geqo_pool_size", PGC_USERSET}, &Geqo_pool_size,
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 41750b9e229..515eec9acae 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -94,6 +94,9 @@
 #cpu_index_tuple_cost = 0.001	# (same)
 #cpu_operator_cost = 0.0025	# (same)
 
+#from_collapse_limit = 8
+#join_collapse_limit = 8	# 1 disables collapsing of explicit JOINs
+
 #default_statistics_target = 10	# range 1-1000
 
 #