Subselects in FROM clause, per ISO syntax: FROM (SELECT ...) [AS] alias.

(Don't forget that an alias is required.)  Views reimplemented as expanding
to subselect-in-FROM.  Grouping, aggregates, DISTINCT in views actually
work now (he says optimistically).  No UNION support in subselects/views
yet, but I have some ideas about that.  Rule-related permissions checking
moved out of rewriter and into executor.
INITDB REQUIRED!

23 files changed, 1072 insertions, 601 deletions

diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index 38901ede1fd..f0113dfaf50 100644
--- a/src/backend/optimizer/README
+++ b/src/backend/optimizer/README
@@ -9,23 +9,63 @@ stuff.  /geqo is the separate "genetic optimization" planner --- it does
 a semi-random search through the join tree space, rather than exhaustively
 considering all possible join trees.  (But each join considered by /geqo
 is given to /path to create paths for, so we consider all possible
-implementation paths for each specific join even in GEQO mode.)
+implementation paths for each specific join pair even in GEQO mode.)
+
+
+Paths and Join Pairs
+--------------------
+
+During the planning/optimizing process, we build "Path" trees representing
+the different ways of doing a query.  We select the cheapest Path that
+generates the desired relation and turn it into a Plan to pass to the
+executor.  (There is pretty much a one-to-one correspondence between the
+Path and Plan trees, but Path nodes omit info that won't be needed during
+planning, and include info needed for planning that won't be needed by the
+executor.)
+
+The optimizer builds a RelOptInfo structure for each base relation used in
+the query.  Base rels are either primitive tables, or subquery subselects
+that are planned via a separate recursive invocation of the planner.  A
+RelOptInfo is also built for each join relation that is considered during
+planning.  A join rel is simply a combination of base rels.  There is only
+one join RelOptInfo for any given set of baserels --- for example, the join
+{A B C} is represented by the same RelOptInfo no matter whether we build it
+by joining A and B first and then adding C, or joining B and C first and
+then adding A, etc.  These different means of building the joinrel are
+represented as Paths.  For each RelOptInfo we build a list of Paths that
+represent plausible ways to implement the scan or join of that relation.
+Once we've considered all the plausible Paths for a rel, we select the one
+that is cheapest according to the planner's cost estimates.  The final plan
+is derived from the cheapest Path for the RelOptInfo that includes all the
+base rels of the query.
+
+Possible Paths for a primitive table relation include plain old sequential
+scan, plus index scans for any indexes that exist on the table.  A subquery
+base relation just has one Path, a "SubqueryScan" path (which links to the
+subplan that was built by a recursive invocation of the planner).
+
+Joins always occur using two RelOptInfos.  One is outer, the other inner.
+Outers drive lookups of values in the inner.  In a nested loop, lookups of
+values in the inner occur by scanning the inner path once per outer tuple
+to find each matching inner row.  In a mergejoin, inner and outer rows are
+ordered, and are accessed in order, so only one scan is required to perform
+the entire join: both inner and outer paths are scanned in-sync.  (There's
+not a lot of difference between inner and outer in a mergejoin...)  In a
+hashjoin, the inner is scanned first and all its rows are entered in a
+hashtable, then the outer is scanned and for each row we lookup the join
+key in the hashtable.
+
+A Path for a join relation is actually a tree structure, with the top
+Path node representing the join method.  It has left and right subpaths
+that represent the scan or join methods used for the two input relations.
 
 
 Join Tree Construction
 ----------------------
 
 The optimizer generates optimal query plans by doing a more-or-less
-exhaustive search through the ways of executing the query.  During
-the planning/optimizing process, we build "Path" trees representing
-the different ways of doing a query.  We select the cheapest Path
-that generates the desired relation and turn it into a Plan to pass
-to the executor.  (There is pretty much a one-to-one correspondence
-between the Path and Plan trees, but Path nodes omit info that won't
-be needed during planning, and include info needed for planning that
-won't be needed by the executor.)
-
-The best Path tree is found by a recursive process:
+exhaustive search through the ways of executing the query.  The best Path
+tree is found by a recursive process:
 
 1) Take each base relation in the query, and make a RelOptInfo structure
 for it.  Find each potentially useful way of accessing the relation,
@@ -44,46 +84,40 @@ If we have only a single base relation in the query, we are done now.
 Otherwise we have to figure out how to join the base relations into a
 single join relation.
 
-2) Consider joining each RelOptInfo to each other RelOptInfo specified in
-its RelOptInfo.joininfo, and generate a Path for each possible join method.
-(If we have a RelOptInfo with no join clauses, we have no choice but to
-generate a clauseless Cartesian-product join; so we consider joining that
-rel to each other available rel.  But in the presence of join clauses we
-will only consider joins that use available join clauses.)
-
-At this stage each input RelOptInfo is a single relation, so we are joining
-every relation to the other relations as joined in the WHERE clause.  We
-generate a new "join" RelOptInfo for each possible combination of two
-"base" RelOptInfos, and put all the plausible paths for that combination
-into the join RelOptInfo's pathlist.  (As before, we keep only the cheapest
-alternative that generates any one sort ordering of the result.)
-
-Joins always occur using two RelOptInfos.  One is outer, the other inner.
-Outers drive lookups of values in the inner.  In a nested loop, lookups of
-values in the inner occur by scanning the inner path once per outer tuple
-to find each matching inner row.  In a mergejoin, inner and outer rows are
-ordered, and are accessed in order, so only one scan is required to perform
-the entire join: both inner and outer paths are scanned in-sync.  (There's
-not a lot of difference between inner and outer in a mergejoin...)  In a
-hashjoin, the inner is scanned first and all its rows are entered in a
-hashtable, then the outer is scanned and for each row we lookup the join
-key in the hashtable.
-
-A Path for a join relation is actually a tree structure, with the top
-Path node representing the join method.  It has left and right subpaths
-that represent the scan methods used for the two input relations.
-
-3) If we only had two base relations, we are done: we just pick the
-cheapest path for the join RelOptInfo.  If we had more than two, we now
+2) If the query's FROM clause contains explicit JOIN clauses, we join
+those pairs of relations in exactly the tree structure indicated by the
+JOIN clauses.  (This is absolutely necessary when dealing with outer JOINs.
+For inner JOINs we have more flexibility in theory, but don't currently
+exploit it in practice.)  For each such join pair, we generate a Path
+for each feasible join method, and select the cheapest Path.  Note that
+the JOIN clause structure determines the join Path structure, but it
+doesn't constrain the join implementation method at each join (nestloop,
+merge, hash), nor does it say which rel is considered outer or inner at
+each join.  We consider all these possibilities in building Paths.
+
+3) At the top level of the FROM clause we will have a list of relations
+that are either base rels or joinrels constructed per JOIN directives.
+We can join these rels together in any order the planner sees fit.
+The standard (non-GEQO) planner does this as follows:
+
+Consider joining each RelOptInfo to each other RelOptInfo specified in its
+RelOptInfo.joininfo, and generate a Path for each possible join method for
+each such pair.  (If we have a RelOptInfo with no join clauses, we have no
+choice but to generate a clauseless Cartesian-product join; so we consider
+joining that rel to each other available rel.  But in the presence of join
+clauses we will only consider joins that use available join clauses.)
+
+If we only had two relations in the FROM list, we are done: we just pick
+the cheapest path for the join RelOptInfo.  If we had more than two, we now
 need to consider ways of joining join RelOptInfos to each other to make
-join RelOptInfos that represent more than two base relations.
+join RelOptInfos that represent more than two FROM items.
 
 The join tree is constructed using a "dynamic programming" algorithm:
 in the first pass (already described) we consider ways to create join rels
-representing exactly two base relations.  The second pass considers ways
-to make join rels that represent exactly three base relations; the next pass,
-four relations, etc.  The last pass considers how to make the final join
-relation that includes all base rels --- obviously there can be only one
+representing exactly two FROM items.  The second pass considers ways
+to make join rels that represent exactly three FROM items; the next pass,
+four items, etc.  The last pass considers how to make the final join
+relation that includes all FROM items --- obviously there can be only one
 join rel at this top level, whereas there can be more than one join rel
 at lower levels.  At each level we use joins that follow available join
 clauses, if possible, just as described for the first level.
@@ -114,32 +148,45 @@ For example:
     {1 2 3 4}
 
 We consider left-handed plans (the outer rel of an upper join is a joinrel,
-but the inner is always a base rel); right-handed plans (outer rel is always
-a base rel); and bushy plans (both inner and outer can be joins themselves).
-For example, when building {1 2 3 4} we consider joining {1 2 3} to {4}
-(left-handed), {4} to {1 2 3} (right-handed), and {1 2} to {3 4} (bushy),
-among other choices.  Although the jointree scanning code produces these
-potential join combinations one at a time, all the ways to produce the
-same set of joined base rels will share the same RelOptInfo, so the paths
-produced from different join combinations that produce equivalent joinrels
-will compete in add_path.
+but the inner is always a single FROM item); right-handed plans (outer rel
+is always a single item); and bushy plans (both inner and outer can be
+joins themselves).  For example, when building {1 2 3 4} we consider
+joining {1 2 3} to {4} (left-handed), {4} to {1 2 3} (right-handed), and
+{1 2} to {3 4} (bushy), among other choices.  Although the jointree
+scanning code produces these potential join combinations one at a time,
+all the ways to produce the same set of joined base rels will share the
+same RelOptInfo, so the paths produced from different join combinations
+that produce equivalent joinrels will compete in add_path.
 
 Once we have built the final join rel, we use either the cheapest path
 for it or the cheapest path with the desired ordering (if that's cheaper
 than applying a sort to the cheapest other path).
 
-The above dynamic-programming search is only conducted for simple cross
-joins (ie, SELECT FROM tab1, tab2, ...).  When the FROM clause contains
-explicit JOIN clauses, we join rels in exactly the order implied by the
-join tree.  Searching for the best possible join order is done only at
-the top implicit-cross-join level.  For example, in
-	SELECT FROM tab1, tab2, (tab3 NATURAL JOIN tab4)
-we will always join tab3 to tab4 and then consider all ways to join that
-result to tab1 and tab2.  Note that the JOIN syntax only constrains the
-order of joining --- we will still consider all available Paths and
-join methods for each JOIN operator.  We also consider both sides of
-the JOIN operator as inner or outer (so that we can transform RIGHT JOIN
-into LEFT JOIN).
+
+Pulling up subqueries
+---------------------
+
+As we described above, a subquery appearing in the range table is planned
+independently and treated as a "black box" during planning of the outer
+query.  This is necessary when the subquery uses features such as
+aggregates, GROUP, or DISTINCT.  But if the subquery is just a simple
+scan or join, treating the subquery as a black box may produce a poor plan
+compared to considering it as part of the entire plan search space.
+Therefore, at the start of the planning process the planner looks for
+simple subqueries and pulls them up into the main query's jointree.
+
+Pulling up a subquery may result in FROM-list joins appearing below the top
+of the join tree.  Each FROM-list is planned using the dynamic-programming
+search method described above.
+
+If pulling up a subquery produces a FROM-list as a direct child of another
+FROM-list (with no explicit JOIN directives between), then we can merge the
+two FROM-lists together.  Once that's done, the subquery is an absolutely
+integral part of the outer query and will not constrain the join tree
+search space at all.  However, that could result in unpleasant growth of
+planning time, since the dynamic-programming search has runtime exponential
+in the number of FROM-items considered.  Therefore, we don't merge
+FROM-lists if the result would have too many FROM-items in one list.
 
 
 Optimizer Functions
@@ -151,6 +198,7 @@ planner()
  set up for recursive handling of subqueries
  do final cleanup after planning.
 -subquery_planner()
+ pull up subqueries from rangetable, if possible
  simplify constant expressions
  canonicalize qual
      Attempt to reduce WHERE clause to either CNF or DNF canonical form.
@@ -167,13 +215,14 @@ planner()
   preprocess target list
   handle GROUP BY, HAVING, aggregates, ORDER BY, DISTINCT
 --query_planner()
-   pull out constants from target list
-   get a target list that only contains column names, no expressions
-   if none, then return
+   pull out constant quals, which can be used to gate execution of the
+	whole plan (if any are found, we make a top-level Result node
+	to do the gating)
+   make a simplified target list that only contains Vars, no expressions
 ---subplanner()
     make list of base relations used in query
     split up the qual into restrictions (a=1) and joins (b=c)
-    find relation clauses that can do merge sort and hash joins
+    find qual clauses that enable merge and hash joins
 ----make_one_rel()
      set_base_rel_pathlist()
       find scan and all index paths for each base relation
@@ -188,10 +237,11 @@ planner()
       Back at make_one_rel_by_joins(), apply set_cheapest() to extract the
       cheapest path for each newly constructed joinrel.
       Loop back if this wasn't the top join level.
-   do group(GROUP)
-   do aggregate
-   put back constants
-   re-flatten target list
+   Back at query_planner:
+   put back constant quals and non-simplified target list
+ Back at union_planner:
+ do grouping(GROUP)
+ do aggregates
  make unique(DISTINCT)
  make sort(ORDER BY)
 
diff --git a/src/backend/optimizer/geqo/geqo_main.c b/src/backend/optimizer/geqo/geqo_main.c
index 755c33168d6..3428015f497 100644
--- a/src/backend/optimizer/geqo/geqo_main.c
+++ b/src/backend/optimizer/geqo/geqo_main.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: geqo_main.c,v 1.24 2000/09/19 18:42:33 tgl Exp $
+ * $Id: geqo_main.c,v 1.25 2000/09/29 18:21:31 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -245,9 +245,9 @@ geqo(Query *root, int number_of_rels, List *initial_rels)
 	best_tour = (Gene *) pool->data[0].string;
 
 /* root->join_rel_list will be modified during this ! */
-	best_rel = (RelOptInfo *) gimme_tree(root, initial_rels,
-										 best_tour, pool->string_length,
-										 0, NULL);
+	best_rel = gimme_tree(root, initial_rels,
+						  best_tour, pool->string_length,
+						  0, NULL);
 
 /* DBG: show the query plan
 print_plan(best_plan, root);
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index be4a5ca56a2..8ab2aeec918 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.64 2000/09/19 18:42:34 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.65 2000/09/29 18:21:31 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,6 +19,9 @@
 #include "optimizer/geqo.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "optimizer/plancat.h"
+#include "optimizer/planner.h"
+#include "parser/parsetree.h"
 
 
 bool		enable_geqo = true;
@@ -26,7 +29,6 @@ int			geqo_rels = DEFAULT_GEQO_RELS;
 
 
 static void set_base_rel_pathlist(Query *root);
-static List *build_jointree_rels(Query *root);
 static RelOptInfo *make_one_rel_by_joins(Query *root, int levels_needed,
 										 List *initial_rels);
 
@@ -44,20 +46,7 @@ static void debug_print_rel(Query *root, RelOptInfo *rel);
 RelOptInfo *
 make_one_rel(Query *root)
 {
-	int			levels_needed;
-	List	   *initial_rels;
-
-	/*
-	 * Count the number of top-level jointree nodes.  This is the depth
-	 * of the dynamic-programming algorithm we must employ to consider
-	 * all ways of joining the top-level nodes.  Currently, we build
-	 * JoinExpr joins in exactly the order implied by the join expression,
-	 * so no dynamic-programming search is needed within a JoinExpr.
-	 */
-	levels_needed = length(root->jointree);
-
-	if (levels_needed <= 0)
-		return NULL;			/* nothing to do? */
+	RelOptInfo *rel;
 
 	/*
 	 * Generate access paths for the base rels.
@@ -65,27 +54,18 @@ make_one_rel(Query *root)
 	set_base_rel_pathlist(root);
 
 	/*
-	 * Construct a list of rels corresponding to the toplevel jointree nodes.
-	 * This may contain both base rels and rels constructed according to
-	 * explicit JOIN directives.
+	 * Generate access paths for the entire join tree.
 	 */
-	initial_rels = build_jointree_rels(root);
+	Assert(root->jointree != NULL && IsA(root->jointree, FromExpr));
 
-	if (levels_needed == 1)
-	{
-		/*
-		 * Single jointree node, so we're done.
-		 */
-		return (RelOptInfo *) lfirst(initial_rels);
-	}
-	else
-	{
+	rel = make_fromexpr_rel(root, root->jointree);
 
-		/*
-		 * Generate join tree.
-		 */
-		return make_one_rel_by_joins(root, levels_needed, initial_rels);
-	}
+	/*
+	 * The result should join all the query's rels.
+	 */
+	Assert(length(rel->relids) == length(root->base_rel_list));
+
+	return rel;
 }
 
 /*
@@ -102,36 +82,67 @@ set_base_rel_pathlist(Query *root)
 	foreach(rellist, root->base_rel_list)
 	{
 		RelOptInfo *rel = (RelOptInfo *) lfirst(rellist);
-		List	   *indices = find_relation_indices(root, rel);
+		RangeTblEntry *rte;
 
-		/* Mark rel with estimated output rows, width, etc */
-		set_baserel_size_estimates(root, rel);
+		Assert(length(rel->relids) == 1); /* better be base rel */
+		rte = rt_fetch(lfirsti(rel->relids), root->rtable);
 
-		/*
-		 * Generate paths and add them to the rel's pathlist.
-		 *
-		 * Note: add_path() will discard any paths that are dominated by
-		 * another available path, keeping only those paths that are
-		 * superior along at least one dimension of cost or sortedness.
-		 */
+		if (rel->issubquery)
+		{
+			/* Subquery --- generate a separate plan for it */
 
-		/* Consider sequential scan */
-		add_path(rel, create_seqscan_path(rel));
+			/*
+			 * XXX for now, we just apply any restrict clauses that came
+			 * from the outer query as qpquals of the SubqueryScan node.
+			 * Later, think about pushing them down into the subquery itself.
+			 */
 
-		/* Consider TID scans */
-		create_tidscan_paths(root, rel);
+			/* Generate the plan for the subquery */
+			rel->subplan = planner(rte->subquery);
 
-		/* Consider index paths for both simple and OR index clauses */
-		create_index_paths(root, rel, indices,
-						   rel->baserestrictinfo,
-						   rel->joininfo);
+			/* Copy number of output rows from subplan */
+			rel->tuples = rel->subplan->plan_rows;
 
-		/*
-		 * Note: create_or_index_paths depends on create_index_paths to
-		 * have marked OR restriction clauses with relevant indices; this
-		 * is why it doesn't need to be given the list of indices.
-		 */
-		create_or_index_paths(root, rel, rel->baserestrictinfo);
+			/* Mark rel with estimated output rows, width, etc */
+			set_baserel_size_estimates(root, rel);
+
+			/* Generate appropriate path */
+			add_path(rel, create_subqueryscan_path(rel));
+		}
+		else
+		{
+			/* Plain relation */
+			List	   *indices = find_secondary_indexes(rte->relid);
+
+			/* Mark rel with estimated output rows, width, etc */
+			set_baserel_size_estimates(root, rel);
+
+			/*
+			 * Generate paths and add them to the rel's pathlist.
+			 *
+			 * Note: add_path() will discard any paths that are dominated by
+			 * another available path, keeping only those paths that are
+			 * superior along at least one dimension of cost or sortedness.
+			 */
+
+			/* Consider sequential scan */
+			add_path(rel, create_seqscan_path(rel));
+
+			/* Consider TID scans */
+			create_tidscan_paths(root, rel);
+
+			/* Consider index paths for both simple and OR index clauses */
+			create_index_paths(root, rel, indices,
+							   rel->baserestrictinfo,
+							   rel->joininfo);
+
+			/*
+			 * Note: create_or_index_paths depends on create_index_paths to
+			 * have marked OR restriction clauses with relevant indices; this
+			 * is why it doesn't need to be given the list of indices.
+			 */
+			create_or_index_paths(root, rel, rel->baserestrictinfo);
+		}
 
 		/* Now find the cheapest of the paths for this rel */
 		set_cheapest(rel);
@@ -139,26 +150,57 @@ set_base_rel_pathlist(Query *root)
 }
 
 /*
- * build_jointree_rels
- *	  Construct a RelOptInfo for each item in the query's jointree.
- *
- * At present, we handle explicit joins in the FROM clause exactly as
- * specified, with no search for other join orders.  Only the cross-product
- * joins at the top level are involved in the dynamic-programming search.
+ * make_fromexpr_rel
+ *	  Build access paths for a FromExpr jointree node.
  */
-static List *
-build_jointree_rels(Query *root)
+RelOptInfo *
+make_fromexpr_rel(Query *root, FromExpr *from)
 {
-	List	   *rels = NIL;
+	int			levels_needed;
+	List	   *initial_rels = NIL;
 	List	   *jt;
 
-	foreach(jt, root->jointree)
+	/*
+	 * Count the number of child jointree nodes.  This is the depth
+	 * of the dynamic-programming algorithm we must employ to consider
+	 * all ways of joining the child nodes.
+	 */
+	levels_needed = length(from->fromlist);
+
+	if (levels_needed <= 0)
+		return NULL;			/* nothing to do? */
+
+	/*
+	 * Construct a list of rels corresponding to the child jointree nodes.
+	 * This may contain both base rels and rels constructed according to
+	 * explicit JOIN directives.
+	 */
+	foreach(jt, from->fromlist)
 	{
 		Node	   *jtnode = (Node *) lfirst(jt);
 
-		rels = lappend(rels, make_rel_from_jointree(root, jtnode));
+		initial_rels = lappend(initial_rels,
+							   make_jointree_rel(root, jtnode));
+	}
+
+	if (levels_needed == 1)
+	{
+		/*
+		 * Single jointree node, so we're done.
+		 */
+		return (RelOptInfo *) lfirst(initial_rels);
+	}
+	else
+	{
+		/*
+		 * Consider the different orders in which we could join the rels,
+		 * using either GEQO or regular optimizer.
+		 */
+		if (enable_geqo && levels_needed >= geqo_rels)
+			return geqo(root, levels_needed, initial_rels);
+		else
+			return make_one_rel_by_joins(root, levels_needed, initial_rels);
 	}
-	return rels;
 }
 
 /*
@@ -182,14 +224,6 @@ make_one_rel_by_joins(Query *root, int levels_needed, List *initial_rels)
 	int			lev;
 	RelOptInfo *rel;
 
-	/*******************************************
-	 * genetic query optimizer entry point	   *
-	 *	  <[email protected]>		   *
-	 * rest will be skipped in case of GEQO    *
-	 *******************************************/
-	if (enable_geqo && levels_needed >= geqo_rels)
-		return geqo(root, levels_needed, initial_rels);
-
 	/*
 	 * We employ a simple "dynamic programming" algorithm: we first find
 	 * all ways to build joins of two jointree items, then all ways to
@@ -243,12 +277,11 @@ make_one_rel_by_joins(Query *root, int levels_needed, List *initial_rels)
 	}
 
 	/*
-	 * We should have a single rel at the final level,
-	 * representing the join of all the base rels.
+	 * We should have a single rel at the final level.
 	 */
 	Assert(length(joinitems[levels_needed]) == 1);
+
 	rel = (RelOptInfo *) lfirst(joinitems[levels_needed]);
-	Assert(length(rel->relids) == length(root->base_rel_list));
 
 	return rel;
 }
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 0f26dc78722..025f011657a 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -42,7 +42,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.62 2000/06/18 22:44:06 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.63 2000/09/29 18:21:32 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -115,6 +115,7 @@ cost_seqscan(Path *path, RelOptInfo *baserel)
 
 	/* Should only be applied to base relations */
 	Assert(length(baserel->relids) == 1);
+	Assert(!baserel->issubquery);
 
 	if (!enable_seqscan)
 		startup_cost += disable_cost;
@@ -223,6 +224,7 @@ cost_index(Path *path, Query *root,
 	/* Should only be applied to base relations */
 	Assert(IsA(baserel, RelOptInfo) &&IsA(index, IndexOptInfo));
 	Assert(length(baserel->relids) == 1);
+	Assert(!baserel->issubquery);
 
 	if (!enable_indexscan && !is_injoin)
 		startup_cost += disable_cost;
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 55bbd5f5983..5ed42accdb0 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.96 2000/09/15 18:45:25 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.97 2000/09/29 18:21:32 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -464,7 +464,7 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
 	else
 	{
 		/* we assume the caller passed a valid indexable qual */
-		quals = lcons(orsubclause, NIL);
+		quals = makeList1(orsubclause);
 	}
 
 	return expand_indexqual_conditions(quals);
@@ -1504,7 +1504,7 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
 			RestrictInfo *clause = (RestrictInfo *) lfirst(temp);
 
 			indexquals = lappend(indexquals, clause->clause);
-			if (! clause->isjoinqual)
+			if (clause->ispusheddown)
 				alljoinquals = false;
 		}
 
@@ -1516,8 +1516,8 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
 		 * therefore, both indexid and indexqual should be single-element
 		 * lists.
 		 */
-		pathnode->indexid = lconsi(index->indexoid, NIL);
-		pathnode->indexqual = lcons(indexquals, NIL);
+		pathnode->indexid = makeListi1(index->indexoid);
+		pathnode->indexqual = makeList1(indexquals);
 
 		/* We don't actually care what order the index scans in ... */
 		pathnode->indexscandir = NoMovementScanDirection;
@@ -1541,7 +1541,7 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
 		 */
 		pathnode->rows = rel->tuples *
 			restrictlist_selectivity(root,
-									 LispUnion(rel->baserestrictinfo,
+									 set_union(rel->baserestrictinfo,
 											   clausegroup),
 									 lfirsti(rel->relids));
 		/* Like costsize.c, force estimate to be at least one row */
@@ -2034,7 +2034,7 @@ prefix_quals(Var *leftop, Oid expr_op,
 		con = string_to_const(prefix, datatype);
 		op = makeOper(oproid, InvalidOid, BOOLOID);
 		expr = make_opclause(op, leftop, (Var *) con);
-		result = lcons(expr, NIL);
+		result = makeList1(expr);
 		return result;
 	}
 
@@ -2049,7 +2049,7 @@ prefix_quals(Var *leftop, Oid expr_op,
 	con = string_to_const(prefix, datatype);
 	op = makeOper(oproid, InvalidOid, BOOLOID);
 	expr = make_opclause(op, leftop, (Var *) con);
-	result = lcons(expr, NIL);
+	result = makeList1(expr);
 
 	/*
 	 * If we can create a string larger than the prefix, say "x <
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 367e1ac9767..d8bfe6270de 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.56 2000/09/12 21:06:53 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.57 2000/09/29 18:21:32 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -643,10 +643,10 @@ hash_inner_and_outer(Query *root,
 			continue;			/* not hashjoinable */
 
 		/*
-		 * If processing an outer join, only use explicit join clauses for
+		 * If processing an outer join, only use its own join clauses for
 		 * hashing.  For inner joins we need not be so picky.
 		 */
-		if (isouterjoin && !restrictinfo->isjoinqual)
+		if (isouterjoin && restrictinfo->ispusheddown)
 			continue;
 
 		clause = restrictinfo->clause;
@@ -665,7 +665,7 @@ hash_inner_and_outer(Query *root,
 			continue;			/* no good for these input relations */
 
 		/* always a one-element list of hash clauses */
-		hashclauses = lcons(restrictinfo, NIL);
+		hashclauses = makeList1(restrictinfo);
 
 		/* estimate disbursion of inner var for costing purposes */
 		innerdisbursion = estimate_disbursion(root, inner);
@@ -820,7 +820,7 @@ select_mergejoin_clauses(RelOptInfo *joinrel,
 				   *right;
 
 		/*
-		 * If processing an outer join, only use explicit join clauses in the
+		 * If processing an outer join, only use its own join clauses in the
 		 * merge.  For inner joins we need not be so picky.
 		 *
 		 * Furthermore, if it is a right/full join then *all* the explicit
@@ -832,7 +832,7 @@ select_mergejoin_clauses(RelOptInfo *joinrel,
 		 */
 		if (isouterjoin)
 		{
-			if (!restrictinfo->isjoinqual)
+			if (restrictinfo->ispusheddown)
 				continue;
 			switch (jointype)
 			{
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 3cab2daba5c..74cc0365bbd 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.47 2000/09/12 21:06:53 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.48 2000/09/29 18:21:32 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -307,13 +307,13 @@ make_rels_by_clauseless_joins(Query *root,
 
 
 /*
- * make_rel_from_jointree
+ * make_jointree_rel
  *		Find or build a RelOptInfojoin rel representing a specific
  *		jointree item.  For JoinExprs, we only consider the construction
  *		path that corresponds exactly to what the user wrote.
  */
 RelOptInfo *
-make_rel_from_jointree(Query *root, Node *jtnode)
+make_jointree_rel(Query *root, Node *jtnode)
 {
 	if (IsA(jtnode, RangeTblRef))
 	{
@@ -321,6 +321,13 @@ make_rel_from_jointree(Query *root, Node *jtnode)
 
 		return get_base_rel(root, varno);
 	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+
+		/* Recurse back to multi-way-join planner */
+		return make_fromexpr_rel(root, f);
+	}
 	else if (IsA(jtnode, JoinExpr))
 	{
 		JoinExpr   *j = (JoinExpr *) jtnode;
@@ -329,8 +336,8 @@ make_rel_from_jointree(Query *root, Node *jtnode)
 				   *rrel;
 
 		/* Recurse */
-		lrel = make_rel_from_jointree(root, j->larg);
-		rrel = make_rel_from_jointree(root, j->rarg);
+		lrel = make_jointree_rel(root, j->larg);
+		rrel = make_jointree_rel(root, j->rarg);
 
 		/* Make this join rel */
 		rel = make_join_rel(root, lrel, rrel, j->jointype);
@@ -346,7 +353,7 @@ make_rel_from_jointree(Query *root, Node *jtnode)
 		return rel;
 	}
 	else
-		elog(ERROR, "make_rel_from_jointree: unexpected node type %d",
+		elog(ERROR, "make_jointree_rel: unexpected node type %d",
 			 nodeTag(jtnode));
 	return NULL;				/* keep compiler quiet */
 }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index c6eccddab19..820492bd186 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -11,7 +11,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.25 2000/09/12 21:06:53 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.26 2000/09/29 18:21:32 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -122,7 +122,7 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
 				newset = lcons(item1, lcons(item2, NIL));
 
 			/* Found a set to merge into our new set */
-			newset = LispUnion(newset, curset);
+			newset = set_union(newset, curset);
 
 			/*
 			 * Remove old set from equi_key_list.  NOTE this does not
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 96dc3327b7f..cc308b4fc96 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.96 2000/09/12 21:06:53 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.97 2000/09/29 18:21:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -41,6 +41,8 @@ static IndexScan *create_indexscan_node(Query *root, IndexPath *best_path,
 					  List *tlist, List *scan_clauses);
 static TidScan *create_tidscan_node(TidPath *best_path, List *tlist,
 					List *scan_clauses);
+static SubqueryScan *create_subqueryscan_node(Path *best_path,
+					  List *tlist, List *scan_clauses);
 static NestLoop *create_nestloop_node(NestPath *best_path, List *tlist,
 									  List *joinclauses, List *otherclauses,
 									  Plan *outer_node, List *outer_tlist,
@@ -66,6 +68,8 @@ static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
 			   ScanDirection indexscandir);
 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
 			 List *tideval);
+static SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual,
+									   Index scanrelid, Plan *subplan);
 static NestLoop *make_nestloop(List *tlist,
 							   List *joinclauses, List *otherclauses,
 							   Plan *lefttree, Plan *righttree,
@@ -110,6 +114,7 @@ create_plan(Query *root, Path *best_path)
 		case T_IndexScan:
 		case T_SeqScan:
 		case T_TidScan:
+		case T_SubqueryScan:
 			plan_node = (Plan *) create_scan_node(root, best_path, tlist);
 			break;
 		case T_HashJoin:
@@ -164,7 +169,9 @@ create_scan_node(Query *root, Path *best_path, List *tlist)
 	switch (best_path->pathtype)
 	{
 		case T_SeqScan:
-			node = (Scan *) create_seqscan_node(best_path, tlist, scan_clauses);
+			node = (Scan *) create_seqscan_node(best_path,
+												tlist,
+												scan_clauses);
 			break;
 
 		case T_IndexScan:
@@ -180,6 +187,12 @@ create_scan_node(Query *root, Path *best_path, List *tlist)
 												scan_clauses);
 			break;
 
+		case T_SubqueryScan:
+			node = (Scan *) create_subqueryscan_node(best_path,
+													 tlist,
+													 scan_clauses);
+			break;
+
 		default:
 			elog(ERROR, "create_scan_node: unknown node type: %d",
 				 best_path->pathtype);
@@ -301,6 +314,7 @@ create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses)
 
 	/* there should be exactly one base rel involved... */
 	Assert(length(best_path->parent->relids) == 1);
+	Assert(! best_path->parent->issubquery);
 
 	scan_relid = (Index) lfirsti(best_path->parent->relids);
 
@@ -342,6 +356,8 @@ create_indexscan_node(Query *root,
 
 	/* there should be exactly one base rel involved... */
 	Assert(length(best_path->path.parent->relids) == 1);
+	Assert(! best_path->path.parent->issubquery);
+
 	baserelid = lfirsti(best_path->path.parent->relids);
 
 	/* check to see if any of the indices are lossy */
@@ -391,8 +407,7 @@ create_indexscan_node(Query *root,
 								make_ands_explicit(lfirst(orclause)));
 		indxqual_expr = make_orclause(orclauses);
 
-		qpqual = set_difference(scan_clauses,
-								lcons(indxqual_expr, NIL));
+		qpqual = set_difference(scan_clauses, makeList1(indxqual_expr));
 
 		if (lossy)
 			qpqual = lappend(qpqual, copyObject(indxqual_expr));
@@ -449,6 +464,7 @@ create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses)
 
 	/* there should be exactly one base rel involved... */
 	Assert(length(best_path->path.parent->relids) == 1);
+	Assert(! best_path->path.parent->issubquery);
 
 	scan_relid = (Index) lfirsti(best_path->path.parent->relids);
 
@@ -465,6 +481,34 @@ create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses)
 	return scan_node;
 }
 
+/*
+ * create_subqueryscan_node
+ *	 Returns a subqueryscan node for the base relation scanned by 'best_path'
+ *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
+ */
+static SubqueryScan *
+create_subqueryscan_node(Path *best_path, List *tlist, List *scan_clauses)
+{
+	SubqueryScan *scan_node;
+	Index		scan_relid;
+
+	/* there should be exactly one base rel involved... */
+	Assert(length(best_path->parent->relids) == 1);
+	/* and it must be a subquery */
+	Assert(best_path->parent->issubquery);
+
+	scan_relid = (Index) lfirsti(best_path->parent->relids);
+
+	scan_node = make_subqueryscan(tlist,
+								  scan_clauses,
+								  scan_relid,
+								  best_path->parent->subplan);
+
+	copy_path_costsize(&scan_node->scan.plan, best_path);
+
+	return scan_node;
+}
+
 /*****************************************************************************
  *
  *	JOIN METHODS
@@ -1162,6 +1206,28 @@ make_tidscan(List *qptlist,
 	return node;
 }
 
+static SubqueryScan *
+make_subqueryscan(List *qptlist,
+				  List *qpqual,
+				  Index scanrelid,
+				  Plan *subplan)
+{
+	SubqueryScan *node = makeNode(SubqueryScan);
+	Plan	   *plan = &node->scan.plan;
+
+	/* cost should be inserted by caller */
+	plan->state = (EState *) NULL;
+	plan->targetlist = qptlist;
+	plan->qual = qpqual;
+	plan->lefttree = NULL;
+	plan->righttree = NULL;
+	node->scan.scanrelid = scanrelid;
+	node->subplan = subplan;
+	node->scan.scanstate = (CommonScanState *) NULL;
+
+	return node;
+}
+
 
 static NestLoop *
 make_nestloop(List *tlist,
@@ -1405,7 +1471,11 @@ make_agg(List *tlist, List *qual, Plan *lefttree)
 	 * mode, so it didn't reduce its row count already.)
 	 */
 	if (IsA(lefttree, Group))
+	{
 		plan->plan_rows *= 0.1;
+		if (plan->plan_rows < 1)
+			plan->plan_rows = 1;
+	}
 	else
 	{
 		plan->plan_rows = 1;
@@ -1447,7 +1517,11 @@ make_group(List *tlist,
 	 * --- bogus, but how to do better?
 	 */
 	if (!tuplePerGroup)
+	{
 		plan->plan_rows *= 0.1;
+		if (plan->plan_rows < 1)
+			plan->plan_rows = 1;
+	}
 
 	plan->state = (EState *) NULL;
 	plan->qual = NULL;
@@ -1489,6 +1563,8 @@ make_unique(List *tlist, Plan *lefttree, List *distinctList)
 	 * 10% as many tuples out as in.
 	 */
 	plan->plan_rows *= 0.1;
+	if (plan->plan_rows < 1)
+		plan->plan_rows = 1;
 
 	plan->state = (EState *) NULL;
 	plan->targetlist = tlist;
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index bf728ca1bdc..acee58b7f07 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.50 2000/09/12 21:06:54 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.51 2000/09/29 18:21:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -35,9 +35,10 @@
 
 static void mark_baserels_for_outer_join(Query *root, Relids rels,
 										 Relids outerrels);
-static void add_restrict_and_join_to_rel(Query *root, Node *clause,
-										 bool isjoinqual,
-										 Relids outerjoinrelids);
+static void distribute_qual_to_rels(Query *root, Node *clause,
+									bool ispusheddown,
+									bool isouterjoin,
+									Relids qualscope);
 static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
 					  Relids join_relids);
 static void add_vars_to_targetlist(Query *root, List *vars);
@@ -93,15 +94,13 @@ add_vars_to_targetlist(Query *root, List *vars)
  *	  If we have a relation listed in the join tree that does not appear
  *	  in the target list nor qualifications, we must add it to the base
  *	  relation list so that it can be processed.  For instance,
+ *			select count(*) from foo;
+ *	  would fail to scan foo if this routine were not called.  More subtly,
  *			select f.x from foo f, foo f2
  *	  is a join of f and f2.  Note that if we have
  *			select foo.x from foo f
  *	  this also gets turned into a join (between foo as foo and foo as f).
  *
- *	  To avoid putting useless entries into the per-relation targetlists,
- *	  this should only be called after all the variables in the targetlist
- *	  and quals have been processed by the routines above.
- *
  *	  Returns a list of all the base relations (RelOptInfo nodes) that appear
  *	  in the join tree.  This list can be used for cross-checking in the
  *	  reverse direction, ie, that we have a join tree entry for every
@@ -115,34 +114,24 @@ add_missing_rels_to_query(Query *root, Node *jtnode)
 
 	if (jtnode == NULL)
 		return NIL;
-	if (IsA(jtnode, List))
+	if (IsA(jtnode, RangeTblRef))
 	{
-		List	   *l;
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+		/* This call to get_base_rel does the primary work... */
+		RelOptInfo *rel = get_base_rel(root, varno);
 
-		foreach(l, (List *) jtnode)
-		{
-			result = nconc(result,
-						   add_missing_rels_to_query(root, lfirst(l)));
-		}
+		result = makeList1(rel);
 	}
-	else if (IsA(jtnode, RangeTblRef))
+	else if (IsA(jtnode, FromExpr))
 	{
-		int			varno = ((RangeTblRef *) jtnode)->rtindex;
-		RelOptInfo *rel = get_base_rel(root, varno);
+		FromExpr   *f = (FromExpr *) jtnode;
+		List	   *l;
 
-		/*
-		 * If the rel isn't otherwise referenced, give it a dummy
-		 * targetlist consisting of its own OID.
-		 */
-		if (rel->targetlist == NIL)
+		foreach(l, f->fromlist)
 		{
-			Var		   *var = makeVar(varno, ObjectIdAttributeNumber,
-									  OIDOID, -1, 0);
-
-			add_var_to_tlist(rel, var);
+			result = nconc(result,
+						   add_missing_rels_to_query(root, lfirst(l)));
 		}
-
-		result = lcons(rel, NIL);
 	}
 	else if (IsA(jtnode, JoinExpr))
 	{
@@ -167,58 +156,74 @@ add_missing_rels_to_query(Query *root, Node *jtnode)
 
 
 /*
- * add_join_quals_to_rels
- *	  Recursively scan the join tree for JOIN/ON (and JOIN/USING) qual
- *	  clauses, and add these to the appropriate JoinInfo lists.  Also,
- *	  mark base RelOptInfos with outerjoinset information, which will
- *	  be needed for proper placement of WHERE clauses during
- *	  add_restrict_and_join_to_rels().
+ * distribute_quals_to_rels
+ *	  Recursively scan the query's join tree for WHERE and JOIN/ON qual
+ *	  clauses, and add these to the appropriate RestrictInfo and JoinInfo
+ *	  lists belonging to base RelOptInfos.  New base rel entries are created
+ *	  as needed.  Also, base RelOptInfos are marked with outerjoinset
+ *	  information, to aid in proper positioning of qual clauses that appear
+ *	  above outer joins.
  *
  * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
  * be evaluated at the lowest level where all the variables it mentions are
- * available.  However, we cannot do this within an outer join since the qual
- * might eliminate matching rows and cause a NULL row to be added improperly.
- * Therefore, rels appearing within (the nullable side of) an outer join
- * are marked with outerjoinset = list of Relids used at the outer join node.
- * This list will be added to the list of rels referenced by quals using
- * such a rel, thereby forcing them up the join tree to the right level.
+ * available.  However, we cannot push a qual down into the nullable side(s)
+ * of an outer join since the qual might eliminate matching rows and cause a
+ * NULL row to be incorrectly emitted by the join.  Therefore, rels appearing
+ * within the nullable side(s) of an outer join are marked with
+ * outerjoinset = list of Relids used at the outer join node.
+ * This list will be added to the list of rels referenced by quals using such
+ * a rel, thereby forcing them up the join tree to the right level.
  *
- * To ease the calculation of these values, add_join_quals_to_rels() returns
+ * To ease the calculation of these values, distribute_quals_to_rels() returns
  * the list of Relids involved in its own level of join.  This is just an
  * internal convenience; no outside callers pay attention to the result.
  */
 Relids
-add_join_quals_to_rels(Query *root, Node *jtnode)
+distribute_quals_to_rels(Query *root, Node *jtnode)
 {
 	Relids		result = NIL;
 
 	if (jtnode == NULL)
 		return result;
-	if (IsA(jtnode, List))
+	if (IsA(jtnode, RangeTblRef))
 	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		/* No quals to deal with, just return correct result */
+		result = makeListi1(varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
 		List	   *l;
+		List	   *qual;
 
 		/*
+		 * First, recurse to handle child joins.
+		 *
 		 * Note: we assume it's impossible to see same RT index from more
-		 * than one subtree, so nconc() is OK rather than LispUnioni().
+		 * than one subtree, so nconc() is OK rather than set_unioni().
 		 */
-		foreach(l, (List *) jtnode)
+		foreach(l, f->fromlist)
+		{
 			result = nconc(result,
-						   add_join_quals_to_rels(root, lfirst(l)));
-	}
-	else if (IsA(jtnode, RangeTblRef))
-	{
-		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+						   distribute_quals_to_rels(root, lfirst(l)));
+		}
 
-		/* No quals to deal with, just return correct result */
-		result = lconsi(varno, NIL);
+		/*
+		 * Now process the top-level quals.  These are always marked as
+		 * "pushed down", since they clearly didn't come from a JOIN expr.
+		 */
+		foreach(qual, (List *) f->quals)
+			distribute_qual_to_rels(root, (Node *) lfirst(qual),
+									true, false, result);
 	}
 	else if (IsA(jtnode, JoinExpr))
 	{
 		JoinExpr   *j = (JoinExpr *) jtnode;
 		Relids		leftids,
-					rightids,
-					outerjoinids;
+					rightids;
+		bool		isouterjoin;
 		List	   *qual;
 
 		/*
@@ -228,15 +233,15 @@ add_join_quals_to_rels(Query *root, Node *jtnode)
 		 * Then, if we are an outer join, we mark baserels contained within
 		 * the nullable side(s) with our own rel list; this will restrict
 		 * placement of subsequent quals using those rels, including our own
-		 * quals, quals above us in the join tree, and WHERE quals.
+		 * quals and quals above us in the join tree.
 		 * Finally we place our own join quals.
 		 */
-		leftids = add_join_quals_to_rels(root, j->larg);
-		rightids = add_join_quals_to_rels(root, j->rarg);
+		leftids = distribute_quals_to_rels(root, j->larg);
+		rightids = distribute_quals_to_rels(root, j->rarg);
 
 		result = nconc(listCopy(leftids), rightids);
 
-		outerjoinids = NIL;
+		isouterjoin = false;
 		switch (j->jointype)
 		{
 			case JOIN_INNER:
@@ -244,15 +249,15 @@ add_join_quals_to_rels(Query *root, Node *jtnode)
 				break;
 			case JOIN_LEFT:
 				mark_baserels_for_outer_join(root, rightids, result);
-				outerjoinids = result;
+				isouterjoin = true;
 				break;
 			case JOIN_FULL:
 				mark_baserels_for_outer_join(root, result, result);
-				outerjoinids = result;
+				isouterjoin = true;
 				break;
 			case JOIN_RIGHT:
 				mark_baserels_for_outer_join(root, leftids, result);
-				outerjoinids = result;
+				isouterjoin = true;
 				break;
 			case JOIN_UNION:
 				/*
@@ -262,17 +267,18 @@ add_join_quals_to_rels(Query *root, Node *jtnode)
 				elog(ERROR, "UNION JOIN is not implemented yet");
 				break;
 			default:
-				elog(ERROR, "add_join_quals_to_rels: unsupported join type %d",
+				elog(ERROR,
+					 "distribute_quals_to_rels: unsupported join type %d",
 					 (int) j->jointype);
 				break;
 		}
 
 		foreach(qual, (List *) j->quals)
-			add_restrict_and_join_to_rel(root, (Node *) lfirst(qual),
-										 true, outerjoinids);
+			distribute_qual_to_rels(root, (Node *) lfirst(qual),
+									false, isouterjoin, result);
 	}
 	else
-		elog(ERROR, "add_join_quals_to_rels: unexpected node type %d",
+		elog(ERROR, "distribute_quals_to_rels: unexpected node type %d",
 			 nodeTag(jtnode));
 	return result;
 }
@@ -301,25 +307,7 @@ mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels)
 }
 
 /*
- * add_restrict_and_join_to_rels
- *	  Fill RestrictInfo and JoinInfo lists of relation entries for all
- *	  relations appearing within clauses.  Creates new relation entries if
- *	  necessary, adding them to root->base_rel_list.
- *
- * 'clauses': the list of clauses in the cnfify'd query qualification.
- */
-void
-add_restrict_and_join_to_rels(Query *root, List *clauses)
-{
-	List	   *clause;
-
-	foreach(clause, clauses)
-		add_restrict_and_join_to_rel(root, (Node *) lfirst(clause),
-									 false, NIL);
-}
-
-/*
- * add_restrict_and_join_to_rel
+ * distribute_qual_to_rels
  *	  Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
  *	  (depending on whether the clause is a join) of each base relation
  *	  mentioned in the clause.	A RestrictInfo node is created and added to
@@ -327,20 +315,21 @@ add_restrict_and_join_to_rels(Query *root, List *clauses)
  *	  mergejoinable operator and is not an outer-join qual, enter the left-
  *	  and right-side expressions into the query's lists of equijoined vars.
  *
- * isjoinqual is true if the clause came from JOIN/ON or JOIN/USING;
- * we have to mark the created RestrictInfo accordingly.  If the JOIN
- * is an OUTER join, the caller must set outerjoinrelids = all relids of join,
- * which will override the joinrel identifiers extracted from the clause
- * itself.  For inner join quals and WHERE clauses, set outerjoinrelids = NIL.
- * (Passing the whole list, and not just an "isouterjoin" boolean, is simply
- * a speed optimization: we could extract the same list from the base rels'
- * outerjoinsets, but since add_join_quals_to_rels() already knows what we
- * should use, might as well pass it in instead of recalculating it.)
+ * 'clause': the qual clause to be distributed
+ * 'ispusheddown': if TRUE, force the clause to be marked 'ispusheddown'
+ *		(this indicates the clause came from a FromExpr, not a JoinExpr)
+ * 'isouterjoin': TRUE if the qual came from an OUTER JOIN's ON-clause
+ * 'qualscope': list of baserels the qual's syntactic scope covers
+ *
+ * 'qualscope' identifies what level of JOIN the qual came from.  For a top
+ * level qual (WHERE qual), qualscope lists all baserel ids and in addition
+ * 'ispusheddown' will be TRUE.
  */
 static void
-add_restrict_and_join_to_rel(Query *root, Node *clause,
-							 bool isjoinqual,
-							 Relids outerjoinrelids)
+distribute_qual_to_rels(Query *root, Node *clause,
+						bool ispusheddown,
+						bool isouterjoin,
+						Relids qualscope)
 {
 	RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 	Relids		relids;
@@ -348,7 +337,6 @@ add_restrict_and_join_to_rel(Query *root, Node *clause,
 	bool		can_be_equijoin;
 
 	restrictinfo->clause = (Expr *) clause;
-	restrictinfo->isjoinqual = isjoinqual;
 	restrictinfo->subclauseindices = NIL;
 	restrictinfo->mergejoinoperator = InvalidOid;
 	restrictinfo->left_sortop = InvalidOid;
@@ -361,17 +349,40 @@ add_restrict_and_join_to_rel(Query *root, Node *clause,
 	clause_get_relids_vars(clause, &relids, &vars);
 
 	/*
-	 * If caller has given us a join relid list, use it; otherwise, we must
-	 * scan the referenced base rels and add in any outer-join rel lists.
-	 * This prevents the clause from being applied at a lower level of joining
-	 * than any OUTER JOIN that should be evaluated before it.
+	 * Cross-check: clause should contain no relids not within its scope.
+	 * Otherwise the parser messed up.
 	 */
-	if (outerjoinrelids)
+	if (! is_subseti(relids, qualscope))
+		elog(ERROR, "JOIN qualification may not refer to other relations");
+
+	/*
+	 * If the clause is variable-free, we force it to be evaluated at its
+	 * original syntactic level.  Note that this should not happen for
+	 * top-level clauses, because query_planner() special-cases them.  But
+	 * it will happen for variable-free JOIN/ON clauses.  We don't have to
+	 * be real smart about such a case, we just have to be correct.
+	 */
+	if (relids == NIL)
+		relids = qualscope;
+
+	/*
+	 * For an outer-join qual, pretend that the clause references all rels
+	 * appearing within its syntactic scope, even if it really doesn't.
+	 * This ensures that the clause will be evaluated exactly at the level
+	 * of joining corresponding to the outer join.
+	 *
+	 * For a non-outer-join qual, we can evaluate the qual as soon as
+	 * (1) we have all the rels it mentions, and (2) we are at or above any
+	 * outer joins that can null any of these rels and are below the syntactic
+	 * location of the given qual.  To enforce the latter, scan the base rels
+	 * listed in relids, and merge their outer-join lists into the clause's
+	 * own reference list.  At the time we are called, the outerjoinset list
+	 * of each baserel will show exactly those outer joins that are below the
+	 * qual in the join tree.
+	 */
+	if (isouterjoin)
 	{
-		/* Safety check: parser should have enforced this to start with */
-		if (! is_subseti(relids, outerjoinrelids))
-			elog(ERROR, "JOIN qualification may not refer to other relations");
-		relids = outerjoinrelids;
+		relids = qualscope;
 		can_be_equijoin = false;
 	}
 	else
@@ -379,15 +390,16 @@ add_restrict_and_join_to_rel(Query *root, Node *clause,
 		Relids		newrelids = relids;
 		List	   *relid;
 
-		/* We rely on LispUnioni to be nondestructive of its input lists... */
+		/* We rely on set_unioni to be nondestructive of its input lists... */
 		can_be_equijoin = true;
 		foreach(relid, relids)
 		{
 			RelOptInfo *rel = get_base_rel(root, lfirsti(relid));
 
-			if (rel->outerjoinset)
+			if (rel->outerjoinset &&
+				! is_subseti(rel->outerjoinset, relids))
 			{
-				newrelids = LispUnioni(newrelids, rel->outerjoinset);
+				newrelids = set_unioni(newrelids, rel->outerjoinset);
 				/*
 				 * Because application of the qual will be delayed by outer
 				 * join, we mustn't assume its vars are equal everywhere.
@@ -396,8 +408,19 @@ add_restrict_and_join_to_rel(Query *root, Node *clause,
 			}
 		}
 		relids = newrelids;
+		/* Should still be a subset of current scope ... */
+		Assert(is_subseti(relids, qualscope));
 	}
 
+	/*
+	 * Mark the qual as "pushed down" if it can be applied at a level below
+	 * its original syntactic level.  This allows us to distinguish original
+	 * JOIN/ON quals from higher-level quals pushed down to the same joinrel.
+	 * A qual originating from WHERE is always considered "pushed down".
+	 */
+	restrictinfo->ispusheddown = ispusheddown || !sameseti(relids,
+														   qualscope);
+
 	if (length(relids) == 1)
 	{
 
@@ -454,10 +477,9 @@ add_restrict_and_join_to_rel(Query *root, Node *clause,
 	{
 		/*
 		 * 'clause' references no rels, and therefore we have no place to
-		 * attach it.  This means query_planner() screwed up --- it should
-		 * treat variable-less clauses separately.
+		 * attach it.  Shouldn't get here if callers are working properly.
 		 */
-		elog(ERROR, "add_restrict_and_join_to_rel: can't cope with variable-free clause");
+		elog(ERROR, "distribute_qual_to_rels: can't cope with variable-free clause");
 	}
 
 	/*
@@ -557,7 +579,7 @@ process_implied_equality(Query *root, Node *item1, Node *item2,
 	else
 	{
 		JoinInfo   *joininfo = find_joininfo_node(rel1,
-												  lconsi(irel2, NIL));
+												  makeListi1(irel2));
 
 		restrictlist = joininfo->jinfo_restrictinfo;
 	}
@@ -612,10 +634,20 @@ process_implied_equality(Query *root, Node *item1, Node *item2,
 	clause->oper = (Node *) makeOper(oprid(eq_operator), /* opno */
 									 InvalidOid, /* opid */
 									 BOOLOID); /* operator result type */
-	clause->args = lcons(item1, lcons(item2, NIL));
+	clause->args = makeList2(item1, item2);
 
-	add_restrict_and_join_to_rel(root, (Node *) clause,
-								 false, NIL);
+	/*
+	 * Note: we mark the qual "pushed down" to ensure that it can never be
+	 * taken for an original JOIN/ON clause.  We also claim it is an outer-
+	 * join clause, which it isn't, but that keeps distribute_qual_to_rels
+	 * from examining the outerjoinsets of the relevant rels (which are no
+	 * longer of interest, but could keep the qual from being pushed down
+	 * to where it should be).  It'll also save a useless call to
+	 * add_equijoined keys...
+	 */
+	distribute_qual_to_rels(root, (Node *) clause,
+							true, true,
+							pull_varnos((Node *) clause));
 }
 
 
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 1fcbe64e888..29cfccfef7b 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -14,7 +14,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.59 2000/09/12 21:06:54 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.60 2000/09/29 18:21:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -32,8 +32,8 @@
 #include "utils/memutils.h"
 
 
-static Plan *subplanner(Query *root, List *flat_tlist, List *qual,
-		   double tuple_fraction);
+static Plan *subplanner(Query *root, List *flat_tlist,
+						double tuple_fraction);
 
 
 /*--------------------
@@ -75,46 +75,36 @@ query_planner(Query *root,
 			  List *tlist,
 			  double tuple_fraction)
 {
-	List	   *normal_qual;
-	List	   *noncachable_qual;
-	List	   *constant_qual;
+	List	   *constant_quals;
 	List	   *var_only_tlist;
 	Plan	   *subplan;
 
 	/*
-	 * If the query contains no relation references at all, it must be
-	 * something like "SELECT 2+2;".  Build a trivial "Result" plan.
+	 * If the query has an empty join tree, then it's something easy like
+	 * "SELECT 2+2;" or "INSERT ... VALUES()".  Fall through quickly.
 	 */
-	if (root->rtable == NIL)
+	if (root->jointree->fromlist == NIL)
 	{
-		/* If it's not a select, it should have had a target relation... */
-		if (root->commandType != CMD_SELECT)
-			elog(ERROR, "Empty range table for non-SELECT query");
-
 		root->query_pathkeys = NIL;		/* signal unordered result */
 
 		/* Make childless Result node to evaluate given tlist. */
-		return (Plan *) make_result(tlist, root->qual, (Plan *) NULL);
+		return (Plan *) make_result(tlist, root->jointree->quals,
+									(Plan *) NULL);
 	}
 
 	/*
-	 * Pull out any non-variable qual clauses so these can be put in a
+	 * Pull out any non-variable WHERE clauses so these can be put in a
 	 * toplevel "Result" node, where they will gate execution of the whole
 	 * plan (the Result will not invoke its descendant plan unless the
 	 * quals are true).  Note that any *really* non-variable quals will
 	 * have been optimized away by eval_const_expressions().  What we're
 	 * mostly interested in here is quals that depend only on outer-level
 	 * vars, although if the qual reduces to "WHERE FALSE" this path will
-	 * also be taken.  We also need a special case for quals that contain
-	 * noncachable functions but no vars, such as "WHERE random() < 0.5".
-	 * These cannot be treated as normal restriction or join quals, but
-	 * they're not constants either.  Instead, attach them to the qpqual
-	 * of the top plan, so that they get evaluated once per potential
-	 * output tuple.
+	 * also be taken.
 	 */
-	normal_qual = pull_constant_clauses((List *) root->qual,
-										&noncachable_qual,
-										&constant_qual);
+	root->jointree->quals = (Node *)
+		pull_constant_clauses((List *) root->jointree->quals,
+							  &constant_quals);
 
 	/*
 	 * Create a target list that consists solely of (resdom var) target
@@ -132,18 +122,12 @@ query_planner(Query *root,
 	/*
 	 * Choose the best access path and build a plan for it.
 	 */
-	subplan = subplanner(root, var_only_tlist, normal_qual, tuple_fraction);
-
-	/*
-	 * Handle the noncachable quals.
-	 */
-	if (noncachable_qual)
-		subplan->qual = nconc(subplan->qual, noncachable_qual);
+	subplan = subplanner(root, var_only_tlist, tuple_fraction);
 
 	/*
 	 * Build a result node to control the plan if we have constant quals.
 	 */
-	if (constant_qual)
+	if (constant_quals)
 	{
 
 		/*
@@ -151,7 +135,7 @@ query_planner(Query *root,
 		 * originally requested tlist.
 		 */
 		subplan = (Plan *) make_result(tlist,
-									   (Node *) constant_qual,
+									   (Node *) constant_quals,
 									   subplan);
 	}
 	else
@@ -175,7 +159,6 @@ query_planner(Query *root,
  *	 for processing a single level of attributes.
  *
  * flat_tlist is the flattened target list
- * qual is the qualification to be satisfied (restrict and join quals only)
  * tuple_fraction is the fraction of tuples we expect will be retrieved
  *
  * See query_planner() comments about the interpretation of tuple_fraction.
@@ -185,7 +168,6 @@ query_planner(Query *root,
 static Plan *
 subplanner(Query *root,
 		   List *flat_tlist,
-		   List *qual,
 		   double tuple_fraction)
 {
 	List	   *joined_rels;
@@ -210,9 +192,8 @@ subplanner(Query *root,
 	root->equi_key_list = NIL;
 
 	build_base_rel_tlists(root, flat_tlist);
-	(void) add_join_quals_to_rels(root, (Node *) root->jointree);
-	/* this must happen after add_join_quals_to_rels: */
-	add_restrict_and_join_to_rels(root, qual);
+
+	(void) distribute_quals_to_rels(root, (Node *) root->jointree);
 
 	/*
 	 * Make sure we have RelOptInfo nodes for all relations to be joined.
@@ -270,26 +251,7 @@ subplanner(Query *root,
 	final_rel = make_one_rel(root);
 
 	if (!final_rel)
-	{
-
-		/*
-		 * We expect to end up here for a trivial INSERT ... VALUES query
-		 * (which will have a target relation, so it gets past
-		 * query_planner's check for empty range table; but the target rel
-		 * is not in the join tree, so we find there is nothing to join).
-		 *
-		 * It's also possible to get here if the query was rewritten by the
-		 * rule processor (creating dummy rangetable entries that are not in
-		 * the join tree) but the rules either did nothing or were simplified
-		 * to nothing by constant-expression folding.  So, don't complain.
-		 */
-		root->query_pathkeys = NIL;		/* signal unordered result */
-
-		/* Make childless Result node to evaluate given tlist. */
-		resultplan = (Plan *) make_result(flat_tlist, (Node *) qual,
-										  (Plan *) NULL);
-		goto plan_built;
-	}
+		elog(ERROR, "subplanner: failed to construct a relation");
 
 #ifdef NOT_USED					/* fix xfunc */
 
@@ -395,7 +357,10 @@ plan_built:
 
 	/*
 	 * Must copy the completed plan tree and its pathkeys out of temporary
-	 * context.
+	 * context.  We also have to copy the rtable in case it contains any
+	 * subqueries.  (If it does, they'll have been modified during the
+	 * recursive invocation of planner.c, and hence will contain substructure
+	 * allocated in my temporary context...)
 	 */
 	MemoryContextSwitchTo(oldcxt);
 
@@ -403,6 +368,8 @@ plan_built:
 
 	root->query_pathkeys = copyObject(root->query_pathkeys);
 
+	root->rtable = copyObject(root->rtable);
+
 	/*
 	 * Now we can release the Path storage.
 	 */
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6e2330cc8d..937628121b3 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.90 2000/09/25 18:09:28 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.91 2000/09/29 18:21:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -25,11 +25,24 @@
 #include "optimizer/subselect.h"
 #include "optimizer/tlist.h"
 #include "optimizer/var.h"
+#include "parser/parsetree.h"
 #include "parser/parse_expr.h"
+#include "rewrite/rewriteManip.h"
 #include "utils/lsyscache.h"
 
 
-static void preprocess_join_conditions(Query *parse, Node *jtnode);
+/* Expression kind codes for preprocess_expression */
+#define EXPRKIND_TARGET	0
+#define EXPRKIND_WHERE	1
+#define EXPRKIND_HAVING	2
+
+
+static Node *pull_up_subqueries(Query *parse, Node *jtnode);
+static bool is_simple_subquery(Query *subquery);
+static void resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist);
+static Node *preprocess_jointree(Query *parse, Node *jtnode);
+static Node *preprocess_expression(Query *parse, Node *expr, int kind);
+static void preprocess_qual_conditions(Query *parse, Node *jtnode);
 static List *make_subplanTargetList(Query *parse, List *tlist,
 					   AttrNumber **groupColIdx);
 static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
@@ -52,8 +65,9 @@ planner(Query *parse)
 	int			save_PlannerPlanId;
 
 	/*
-	 * The planner can be called recursively (an example is when
-	 * eval_const_expressions tries to simplify an SQL function).
+	 * The outer planner can be called recursively, for example to process
+	 * a subquery in the rangetable.  (A less obvious example occurs when
+	 * eval_const_expressions tries to simplify an SQL function.)
 	 * So, global state variables must be saved and restored.
 	 *
 	 * (Perhaps these should be moved into the Query structure instead?)
@@ -72,7 +86,7 @@ planner(Query *parse)
 	/* this should go away sometime soon */
 	transformKeySetQuery(parse);
 
-	/* primary planning entry point (may recurse for subplans) */
+	/* primary planning entry point (may recurse for sublinks) */
 	result_plan = subquery_planner(parse, -1.0 /* default case */ );
 
 	Assert(PlannerQueryLevel == 1);
@@ -127,6 +141,18 @@ Plan *
 subquery_planner(Query *parse, double tuple_fraction)
 {
 	/*
+	 * Check to see if any subqueries in the rangetable can be merged into
+	 * this query.
+	 */
+	parse->jointree = (FromExpr *)
+		pull_up_subqueries(parse, (Node *) parse->jointree);
+	/*
+	 * If so, we may have created opportunities to simplify the jointree.
+	 */
+	parse->jointree = (FromExpr *)
+		preprocess_jointree(parse, (Node *) parse->jointree);
+
+	/*
 	 * A HAVING clause without aggregates is equivalent to a WHERE clause
 	 * (except it can only refer to grouped fields).  If there are no aggs
 	 * anywhere in the query, then we don't want to create an Agg plan
@@ -135,150 +161,413 @@ subquery_planner(Query *parse, double tuple_fraction)
 	 */
 	if (parse->havingQual != NULL && !parse->hasAggs)
 	{
-		if (parse->qual == NULL)
-			parse->qual = parse->havingQual;
-		else
-			parse->qual = (Node *) make_andclause(lappend(lcons(parse->qual,
-																NIL),
-													 parse->havingQual));
+		parse->jointree->quals = make_and_qual(parse->jointree->quals,
+											   parse->havingQual);
 		parse->havingQual = NULL;
 	}
 
 	/*
-	 * Simplify constant expressions in targetlist and quals.
-	 *
-	 * Note that at this point the qual has not yet been converted to
-	 * implicit-AND form, so we can apply eval_const_expressions directly.
-	 * Also note that we need to do this before SS_process_sublinks,
-	 * because that routine inserts bogus "Const" nodes.
+	 * Do preprocessing on targetlist and quals.
 	 */
 	parse->targetList = (List *)
-		eval_const_expressions((Node *) parse->targetList);
-	parse->qual = eval_const_expressions(parse->qual);
-	parse->havingQual = eval_const_expressions(parse->havingQual);
+		preprocess_expression(parse, (Node *) parse->targetList,
+							  EXPRKIND_TARGET);
+
+	preprocess_qual_conditions(parse, (Node *) parse->jointree);
+
+	parse->havingQual = preprocess_expression(parse, parse->havingQual,
+											  EXPRKIND_HAVING);
 
 	/*
-	 * Canonicalize the qual, and convert it to implicit-AND format.
-	 *
-	 * XXX Is there any value in re-applying eval_const_expressions after
-	 * canonicalize_qual?
+	 * Do the main planning (potentially recursive)
 	 */
-	parse->qual = (Node *) canonicalize_qual((Expr *) parse->qual, true);
-
-#ifdef OPTIMIZER_DEBUG
-	printf("After canonicalize_qual()\n");
-	pprint(parse->qual);
-#endif
+	return union_planner(parse, tuple_fraction);
 
 	/*
-	 * Ditto for the havingQual
+	 * XXX should any more of union_planner's activity be moved here?
+	 *
+	 * That would take careful study of the interactions with prepunion.c,
+	 * but I suspect it would pay off in simplicity and avoidance of
+	 * wasted cycles.
 	 */
-	parse->havingQual = (Node *) canonicalize_qual((Expr *) parse->havingQual,
-												   true);
+}
 
-	/* Expand SubLinks to SubPlans */
-	if (parse->hasSubLinks)
+/*
+ * pull_up_subqueries
+ *		Look for subqueries in the rangetable that can be pulled up into
+ *		the parent query.  If the subquery has no special features like
+ *		grouping/aggregation then we can merge it into the parent's jointree.
+ *
+ * A tricky aspect of this code is that if we pull up a subquery we have
+ * to replace Vars that reference the subquery's outputs throughout the
+ * parent query, including quals attached to jointree nodes above the one
+ * we are currently processing!  We handle this by being careful not to
+ * change the jointree structure while recursing: no nodes other than
+ * subquery RangeTblRef entries will be replaced.  Also, we can't turn
+ * ResolveNew loose on the whole jointree, because it'll return a mutated
+ * copy of the tree; we have to invoke it just on the quals, instead.
+ */
+static Node *
+pull_up_subqueries(Query *parse, Node *jtnode)
+{
+	if (jtnode == NULL)
+		return NULL;
+	if (IsA(jtnode, RangeTblRef))
 	{
-		parse->targetList = (List *)
-			SS_process_sublinks((Node *) parse->targetList);
-		parse->qual = SS_process_sublinks(parse->qual);
-		parse->havingQual = SS_process_sublinks(parse->havingQual);
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+		RangeTblEntry *rte = rt_fetch(varno, parse->rtable);
+		Query	   *subquery = rte->subquery;
 
-		if (parse->groupClause != NIL || parse->hasAggs)
+		/*
+		 * Is this a subquery RTE, and if so, is the subquery simple enough
+		 * to pull up?  (If not, do nothing at this node.)
+		 */
+		if (subquery && is_simple_subquery(subquery))
 		{
+			int		rtoffset;
+			Node   *subjointree;
+			List   *subtlist;
 
 			/*
-			 * Check for ungrouped variables passed to subplans. Note we
-			 * do NOT do this for subplans in WHERE; it's legal there
-			 * because WHERE is evaluated pre-GROUP.
-			 *
-			 * An interesting fine point: if we reassigned a HAVING qual into
-			 * WHERE above, then we will accept references to ungrouped
-			 * vars from subplans in the HAVING qual.  This is not
-			 * entirely consistent, but it doesn't seem particularly
-			 * harmful...
+			 * First, recursively pull up the subquery's subqueries,
+			 * so that this routine's processing is complete for its
+			 * jointree and rangetable.
+			 */
+			subquery->jointree = (FromExpr *)
+				pull_up_subqueries(subquery, (Node *) subquery->jointree);
+			/*
+			 * Append the subquery's rangetable to mine (currently,
+			 * no adjustments will be needed in the subquery's rtable).
+			 */
+			rtoffset = length(parse->rtable);
+			parse->rtable = nconc(parse->rtable, subquery->rtable);
+			/*
+			 * Make copies of the subquery's jointree and targetlist
+			 * with varnos adjusted to match the merged rangetable.
+			 */
+			subjointree = copyObject(subquery->jointree);
+			OffsetVarNodes(subjointree, rtoffset, 0);
+			subtlist = copyObject(subquery->targetList);
+			OffsetVarNodes((Node *) subtlist, rtoffset, 0);
+			/*
+			 * Replace all of the top query's references to the subquery's
+			 * outputs with copies of the adjusted subtlist items, being
+			 * careful not to replace any of the jointree structure.
 			 */
-			check_subplans_for_ungrouped_vars((Node *) parse->targetList,
-											  parse);
-			check_subplans_for_ungrouped_vars(parse->havingQual, parse);
+			parse->targetList = (List *)
+				ResolveNew((Node *) parse->targetList,
+						   varno, 0, subtlist, CMD_SELECT, 0);
+			resolvenew_in_jointree((Node *) parse->jointree, varno, subtlist);
+			parse->havingQual =
+				ResolveNew(parse->havingQual,
+						   varno, 0, subtlist, CMD_SELECT, 0);
+			/*
+			 * Miscellaneous housekeeping.
+			 */
+			parse->hasSubLinks |= subquery->hasSubLinks;
+			/*
+			 * Return the adjusted subquery jointree to replace the
+			 * RangeTblRef entry in my jointree.
+			 */
+			return subjointree;
 		}
 	}
-
-	/* Replace uplevel vars with Param nodes */
-	if (PlannerQueryLevel > 1)
+	else if (IsA(jtnode, FromExpr))
 	{
-		parse->targetList = (List *)
-			SS_replace_correlation_vars((Node *) parse->targetList);
-		parse->qual = SS_replace_correlation_vars(parse->qual);
-		parse->havingQual = SS_replace_correlation_vars(parse->havingQual);
-	}
-
-	/* Do all the above for each qual condition (ON clause) in the join tree */
-	preprocess_join_conditions(parse, (Node *) parse->jointree);
+		FromExpr   *f = (FromExpr *) jtnode;
+		List	   *l;
 
-	/* Do the main planning (potentially recursive) */
+		foreach(l, f->fromlist)
+		{
+			lfirst(l) = pull_up_subqueries(parse, lfirst(l));
+		}
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
 
-	return union_planner(parse, tuple_fraction);
+		j->larg = pull_up_subqueries(parse, j->larg);
+		j->rarg = pull_up_subqueries(parse, j->rarg);
+	}
+	else
+		elog(ERROR, "pull_up_subqueries: unexpected node type %d",
+			 nodeTag(jtnode));
+	return jtnode;
+}
 
+/*
+ * is_simple_subquery
+ *	  Check a subquery in the range table to see if it's simple enough
+ *	  to pull up into the parent query.
+ */
+static bool
+is_simple_subquery(Query *subquery)
+{
 	/*
-	 * XXX should any more of union_planner's activity be moved here?
-	 *
-	 * That would take careful study of the interactions with prepunion.c,
-	 * but I suspect it would pay off in simplicity and avoidance of
-	 * wasted cycles.
+	 * Let's just make sure it's a valid subselect ...
+	 */
+	if (!IsA(subquery, Query) ||
+		subquery->commandType != CMD_SELECT ||
+		subquery->resultRelation != 0 ||
+		subquery->into != NULL ||
+		subquery->isPortal)
+		elog(ERROR, "is_simple_subquery: subquery is bogus");
+	/*
+	 * Also check for currently-unsupported features.
+	 */
+	if (subquery->rowMarks)
+		elog(ERROR, "FOR UPDATE is not supported in subselects");
+	if (subquery->limitOffset || subquery->limitCount)
+		elog(ERROR, "LIMIT is not supported in subselects");
+	/*
+	 * Can't currently pull up a union query.  Maybe after querytree redesign.
 	 */
+	if (subquery->unionClause)
+		return false;
+	/*
+	 * Can't pull up a subquery involving grouping, aggregation, or sorting.
+	 */
+	if (subquery->hasAggs ||
+		subquery->groupClause ||
+		subquery->havingQual ||
+		subquery->sortClause ||
+		subquery->distinctClause)
+		return false;
+	/*
+	 * Hack: don't try to pull up a subquery with an empty jointree.
+	 * query_planner() will correctly generate a Result plan for a
+	 * jointree that's totally empty, but I don't think the right things
+	 * happen if an empty FromExpr appears lower down in a jointree.
+	 * Not worth working hard on this, just to collapse SubqueryScan/Result
+	 * into Result...
+	 */
+	if (subquery->jointree->fromlist == NIL)
+		return false;
+
+	return true;
 }
 
 /*
- * preprocess_join_conditions
- *		Recursively scan the query's jointree and do subquery_planner's
- *		qual preprocessing work on each ON condition found therein.
+ * Helper routine for pull_up_subqueries: do ResolveNew on every expression
+ * in the jointree, without changing the jointree structure itself.  Ugly,
+ * but there's no other way...
  */
 static void
-preprocess_join_conditions(Query *parse, Node *jtnode)
+resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist)
 {
 	if (jtnode == NULL)
 		return;
-	if (IsA(jtnode, List))
+	if (IsA(jtnode, RangeTblRef))
 	{
+		/* nothing to do here */
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
 		List	   *l;
 
-		foreach(l, (List *) jtnode)
-			preprocess_join_conditions(parse, lfirst(l));
+		foreach(l, f->fromlist)
+			resolvenew_in_jointree(lfirst(l), varno, subtlist);
+		f->quals = ResolveNew(f->quals,
+							  varno, 0, subtlist, CMD_SELECT, 0);
 	}
-	else if (IsA(jtnode, RangeTblRef))
+	else if (IsA(jtnode, JoinExpr))
 	{
-		/* nothing to do here */
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		resolvenew_in_jointree(j->larg, varno, subtlist);
+		resolvenew_in_jointree(j->rarg, varno, subtlist);
+		j->quals = ResolveNew(j->quals,
+							  varno, 0, subtlist, CMD_SELECT, 0);
+		/* We don't bother to update the colvars list, since it won't be
+		 * used again ...
+		 */
+	}
+	else
+		elog(ERROR, "resolvenew_in_jointree: unexpected node type %d",
+			 nodeTag(jtnode));
+}
+
+/*
+ * preprocess_jointree
+ *		Attempt to simplify a query's jointree.
+ *
+ * If we succeed in pulling up a subquery then we might form a jointree
+ * in which a FromExpr is a direct child of another FromExpr.  In that
+ * 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.
+ *
+ * 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
+ * work reliably --- see comments for pull_up_subqueries().
+ */
+static Node *
+preprocess_jointree(Query *parse, Node *jtnode)
+{
+	if (jtnode == NULL)
+		return NULL;
+	if (IsA(jtnode, RangeTblRef))
+	{
+		/* nothing to do here... */
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		List	   *newlist = NIL;
+		List	   *l;
+
+		foreach(l, f->fromlist)
+		{
+			Node   *child = (Node *) lfirst(l);
+
+			/* Recursively simplify the child... */
+			child = preprocess_jointree(parse, child);
+			/* Now, is it a FromExpr? */
+			if (child && IsA(child, FromExpr))
+			{
+				/*
+				 * 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?)
+				 */
+				FromExpr   *subf = (FromExpr *) child;
+				int			childlen = length(subf->fromlist);
+				int			myothers = length(newlist) + length(lnext(l));
+
+				if (childlen <= 1 || (childlen+myothers) <= geqo_rels/2)
+				{
+					newlist = nconc(newlist, subf->fromlist);
+					f->quals = make_and_qual(f->quals, subf->quals);
+				}
+				else
+					newlist = lappend(newlist, child);
+			}
+			else
+				newlist = lappend(newlist, child);
+		}
+		f->fromlist = newlist;
 	}
 	else if (IsA(jtnode, JoinExpr))
 	{
 		JoinExpr   *j = (JoinExpr *) jtnode;
 
-		preprocess_join_conditions(parse, j->larg);
-		preprocess_join_conditions(parse, j->rarg);
+		/* Can't usefully change the JoinExpr, but recurse on children */
+		j->larg = preprocess_jointree(parse, j->larg);
+		j->rarg = preprocess_jointree(parse, j->rarg);
+	}
+	else
+		elog(ERROR, "preprocess_jointree: unexpected node type %d",
+			 nodeTag(jtnode));
+	return jtnode;
+}
 
-		/* Simplify constant expressions */
-		j->quals = eval_const_expressions(j->quals);
+/*
+ * preprocess_expression
+ *		Do subquery_planner's preprocessing work for an expression,
+ *		which can be a targetlist, a WHERE clause (including JOIN/ON
+ *		conditions), or a HAVING clause.
+ */
+static Node *
+preprocess_expression(Query *parse, Node *expr, int kind)
+{
+	/*
+	 * Simplify constant expressions.
+	 *
+	 * Note that at this point quals have not yet been converted to
+	 * implicit-AND form, so we can apply eval_const_expressions directly.
+	 * Also note that we need to do this before SS_process_sublinks,
+	 * because that routine inserts bogus "Const" nodes.
+	 */
+	expr = eval_const_expressions(expr);
 
-		/* Canonicalize the qual, and convert it to implicit-AND format */
-		j->quals = (Node *) canonicalize_qual((Expr *) j->quals, true);
+	/*
+	 * If it's a qual or havingQual, canonicalize it, and convert it
+	 * to implicit-AND format.
+	 *
+	 * XXX Is there any value in re-applying eval_const_expressions after
+	 * canonicalize_qual?
+	 */
+	if (kind != EXPRKIND_TARGET)
+	{
+		expr = (Node *) canonicalize_qual((Expr *) expr, true);
+
+#ifdef OPTIMIZER_DEBUG
+		printf("After canonicalize_qual()\n");
+		pprint(expr);
+#endif
+	}
 
+	if (parse->hasSubLinks)
+	{
 		/* Expand SubLinks to SubPlans */
-		if (parse->hasSubLinks)
+		expr = SS_process_sublinks(expr);
+
+		if (kind != EXPRKIND_WHERE &&
+			(parse->groupClause != NIL || parse->hasAggs))
 		{
-			j->quals = SS_process_sublinks(j->quals);
 			/*
-			 * ON conditions, like WHERE clauses, are evaluated pre-GROUP;
-			 * so we allow ungrouped vars in them.
+			 * Check for ungrouped variables passed to subplans.  Note we
+			 * do NOT do this for subplans in WHERE (or JOIN/ON); it's legal
+			 * there because WHERE is evaluated pre-GROUP.
+			 *
+			 * An interesting fine point: if subquery_planner reassigned a
+			 * HAVING qual into WHERE, then we will accept references to
+			 * ungrouped vars from subplans in the HAVING qual.  This is not
+			 * entirely consistent, but it doesn't seem particularly
+			 * harmful...
 			 */
+			check_subplans_for_ungrouped_vars(expr, parse);
 		}
+	}
+
+	/* Replace uplevel vars with Param nodes */
+	if (PlannerQueryLevel > 1)
+		expr = SS_replace_correlation_vars(expr);
 
-		/* Replace uplevel vars with Param nodes */
-		if (PlannerQueryLevel > 1)
-			j->quals = SS_replace_correlation_vars(j->quals);
+	return expr;
+}
+
+/*
+ * preprocess_qual_conditions
+ *		Recursively scan the query's jointree and do subquery_planner's
+ *		preprocessing work on each qual condition found therein.
+ */
+static void
+preprocess_qual_conditions(Query *parse, Node *jtnode)
+{
+	if (jtnode == NULL)
+		return;
+	if (IsA(jtnode, RangeTblRef))
+	{
+		/* nothing to do here */
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		List	   *l;
+
+		foreach(l, f->fromlist)
+			preprocess_qual_conditions(parse, lfirst(l));
+
+		f->quals = preprocess_expression(parse, f->quals, EXPRKIND_WHERE);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		preprocess_qual_conditions(parse, j->larg);
+		preprocess_qual_conditions(parse, j->rarg);
+
+		j->quals = preprocess_expression(parse, j->quals, EXPRKIND_WHERE);
 	}
 	else
-		elog(ERROR, "preprocess_join_conditions: unexpected node type %d",
+		elog(ERROR, "preprocess_qual_conditions: unexpected node type %d",
 			 nodeTag(jtnode));
 }
 
@@ -309,7 +598,6 @@ union_planner(Query *parse,
 			  double tuple_fraction)
 {
 	List	   *tlist = parse->targetList;
-	List	   *rangetable = parse->rtable;
 	Plan	   *result_plan = (Plan *) NULL;
 	AttrNumber *groupColIdx = NULL;
 	List	   *current_pathkeys = NIL;
@@ -342,7 +630,7 @@ union_planner(Query *parse,
 		sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
 													  tlist);
 	}
-	else if (find_inheritable_rt_entry(rangetable,
+	else if (find_inheritable_rt_entry(parse->rtable,
 									   &rt_index, &inheritors))
 	{
 		List	   *sub_tlist;
@@ -373,7 +661,7 @@ union_planner(Query *parse,
 									  parse->resultRelation,
 									  parse->rtable);
 
-		if (parse->rowMark != NULL)
+		if (parse->rowMarks)
 			elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
 
 		/*
@@ -401,33 +689,35 @@ union_planner(Query *parse,
 									  parse->rtable);
 
 		/*
-		 * Add row-mark targets for UPDATE (should this be done in
-		 * preprocess_targetlist?)
+		 * Add TID targets for rels selected FOR UPDATE (should this be
+		 * done in preprocess_targetlist?).  The executor uses the TID
+		 * to know which rows to lock, much as for UPDATE or DELETE.
 		 */
-		if (parse->rowMark != NULL)
+		if (parse->rowMarks)
 		{
 			List	   *l;
 
-			foreach(l, parse->rowMark)
+			foreach(l, parse->rowMarks)
 			{
-				RowMark    *rowmark = (RowMark *) lfirst(l);
-				TargetEntry *ctid;
+				Index		rti = lfirsti(l);
+				char	   *resname;
 				Resdom	   *resdom;
 				Var		   *var;
-				char	   *resname;
-
-				if (!(rowmark->info & ROW_MARK_FOR_UPDATE))
-					continue;
+				TargetEntry *ctid;
 
 				resname = (char *) palloc(32);
-				sprintf(resname, "ctid%u", rowmark->rti);
+				sprintf(resname, "ctid%u", rti);
 				resdom = makeResdom(length(tlist) + 1,
 									TIDOID,
 									-1,
 									resname,
 									true);
 
-				var = makeVar(rowmark->rti, -1, TIDOID, -1, 0);
+				var = makeVar(rti,
+							  SelfItemPointerAttributeNumber,
+							  TIDOID,
+							  -1,
+							  0);
 
 				ctid = makeTargetEntry(resdom, (Node *) var);
 				tlist = lappend(tlist, ctid);
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index d30636c185e..ad1b47aaeb6 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.65 2000/09/12 21:06:54 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.66 2000/09/29 18:21:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -102,6 +102,11 @@ set_plan_references(Plan *plan)
 			fix_expr_references(plan, (Node *) plan->targetlist);
 			fix_expr_references(plan, (Node *) plan->qual);
 			break;
+		case T_SubqueryScan:
+			fix_expr_references(plan, (Node *) plan->targetlist);
+			fix_expr_references(plan, (Node *) plan->qual);
+			/* No need to recurse into the subplan, it's fixed already */
+			break;
 		case T_NestLoop:
 			set_join_references((Join *) plan);
 			fix_expr_references(plan, (Node *) plan->targetlist);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 24a0aae55cd..182d1384aa1 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.41 2000/09/12 21:06:54 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.42 2000/09/29 18:21:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -453,19 +453,6 @@ make_subplan(SubLink *slink)
 	return result;
 }
 
-/* this oughta be merged with LispUnioni */
-
-static List *
-set_unioni(List *l1, List *l2)
-{
-	if (l1 == NULL)
-		return l2;
-	if (l2 == NULL)
-		return l1;
-
-	return nconc(l1, set_differencei(l2, l1));
-}
-
 /*
  * finalize_primnode: build lists of subplans and params appearing
  * in the given expression tree.  NOTE: items are added to lists passed in,
@@ -680,6 +667,7 @@ SS_finalize_plan(Plan *plan)
 
 		case T_Agg:
 		case T_SeqScan:
+		case T_SubqueryScan:
 		case T_Material:
 		case T_Sort:
 		case T_Unique:
diff --git a/src/backend/optimizer/prep/prepkeyset.c b/src/backend/optimizer/prep/prepkeyset.c
index a28e329e537..60166289a59 100644
--- a/src/backend/optimizer/prep/prepkeyset.c
+++ b/src/backend/optimizer/prep/prepkeyset.c
@@ -85,19 +85,14 @@ transformKeySetQuery(Query *origNode)
 	/*************************/
 	/* Qualify where clause */
 	/*************************/
-	if (!inspectOrNode((Expr *) origNode->qual) || TotalExpr < 9)
+	if (!inspectOrNode((Expr *) origNode->jointree->quals) || TotalExpr < 9)
 		return;
 
 	/* Copy essential elements into a union node */
-	while (((Expr *) origNode->qual)->opType == OR_EXPR)
+	while (((Expr *) origNode->jointree->quals)->opType == OR_EXPR)
 	{
 		Query	   *unionNode = makeNode(Query);
-
-		/* Pull up Expr =  */
-		unionNode->qual = lsecond(((Expr *) origNode->qual)->args);
-
-		/* Pull up balance of tree	*/
-		origNode->qual = lfirst(((Expr *) origNode->qual)->args);
+		List	   *qualargs = ((Expr *) origNode->jointree->quals)->args;
 
 		unionNode->commandType = origNode->commandType;
 		unionNode->resultRelation = origNode->resultRelation;
@@ -107,9 +102,16 @@ transformKeySetQuery(Query *origNode)
 		Node_Copy(origNode, unionNode, distinctClause);
 		Node_Copy(origNode, unionNode, sortClause);
 		Node_Copy(origNode, unionNode, rtable);
+		origNode->jointree->quals = NULL; /* avoid unnecessary copying */
 		Node_Copy(origNode, unionNode, jointree);
 		Node_Copy(origNode, unionNode, targetList);
 
+		/* Pull up Expr =  */
+		unionNode->jointree->quals = lsecond(qualargs);
+
+		/* Pull up balance of tree	*/
+		origNode->jointree->quals = lfirst(qualargs);
+
 		origNode->unionClause = lappend(origNode->unionClause, unionNode);
 	}
 	return;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index d284dd51e02..d3df8863270 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.52 2000/09/12 21:06:57 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.53 2000/09/29 18:21:34 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -411,7 +411,7 @@ find_all_inheritors(Oid parentrel)
 		 * there can't be any cycles in the inheritance graph anyway.)
 		 */
 		currentchildren = set_differencei(currentchildren, examined_relids);
-		unexamined_relids = LispUnioni(unexamined_relids, currentchildren);
+		unexamined_relids = set_unioni(unexamined_relids, currentchildren);
 	}
 
 	return examined_relids;
diff --git a/src/backend/optimizer/util/Makefile b/src/backend/optimizer/util/Makefile
index c6160103370..471cfdf6b9b 100644
--- a/src/backend/optimizer/util/Makefile
+++ b/src/backend/optimizer/util/Makefile
@@ -4,7 +4,7 @@
 #    Makefile for optimizer/util
 #
 # IDENTIFICATION
-#    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Makefile,v 1.13 2000/08/31 16:10:14 petere Exp $
+#    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Makefile,v 1.14 2000/09/29 18:21:23 tgl Exp $
 #
 #-------------------------------------------------------------------------
 
@@ -12,7 +12,7 @@ subdir = src/backend/optimizer/util
 top_builddir = ../../../..
 include $(top_builddir)/src/Makefile.global
 
-OBJS = restrictinfo.o clauses.o indexnode.o plancat.o \
+OBJS = restrictinfo.o clauses.o plancat.o \
        joininfo.o pathnode.o relnode.o tlist.o var.o
 
 all: SUBSYS.o
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 9f371ff739f..06c67daebfc 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.75 2000/09/25 18:14:55 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.76 2000/09/29 18:21:23 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -119,9 +119,9 @@ make_opclause(Oper *op, Var *leftop, Var *rightop)
 	expr->opType = OP_EXPR;
 	expr->oper = (Node *) op;
 	if (rightop)
-		expr->args = lcons(leftop, lcons(rightop, NIL));
+		expr->args = makeList2(leftop, rightop);
 	else
-		expr->args = lcons(leftop, NIL);
+		expr->args = makeList1(leftop);
 	return expr;
 }
 
@@ -264,7 +264,7 @@ make_notclause(Expr *notclause)
 	expr->typeOid = BOOLOID;
 	expr->opType = NOT_EXPR;
 	expr->oper = NULL;
-	expr->args = lcons(notclause, NIL);
+	expr->args = makeList1(notclause);
 	return expr;
 }
 
@@ -303,7 +303,6 @@ and_clause(Node *clause)
  * make_andclause
  *
  * Create an 'and' clause given its arguments in a list.
- *
  */
 Expr *
 make_andclause(List *andclauses)
@@ -318,6 +317,23 @@ make_andclause(List *andclauses)
 }
 
 /*
+ * make_and_qual
+ *
+ * Variant of make_andclause for ANDing two qual conditions together.
+ * Qual conditions have the property that a NULL nodetree is interpreted
+ * as 'true'.
+ */
+Node *
+make_and_qual(Node *qual1, Node *qual2)
+{
+	if (qual1 == NULL)
+		return qual2;
+	if (qual2 == NULL)
+		return qual1;
+	return (Node *) make_andclause(makeList2(qual1, qual2));
+}
+
+/*
  * Sometimes (such as in the result of canonicalize_qual or the input of
  * ExecQual), we use lists of expression nodes with implicit AND semantics.
  *
@@ -356,7 +372,7 @@ make_ands_implicit(Expr *clause)
 			 DatumGetBool(((Const *) clause)->constvalue))
 		return NIL;				/* constant TRUE input -> NIL list */
 	else
-		return lcons(clause, NIL);
+		return makeList1(clause);
 }
 
 
@@ -676,49 +692,32 @@ is_pseudo_constant_clause(Node *clause)
 	return false;
 }
 
-/*----------
+/*
  * pull_constant_clauses
  *		Scan through a list of qualifications and separate "constant" quals
  *		from those that are not.
  *
- * The input qual list is divided into three parts:
- *	* The function's return value is a list of all those quals that contain
- *	  variable(s) of the current query level.  (These quals will become
- *	  restrict and join quals.)
- *	* *noncachableQual receives a list of quals that have no Vars, yet
- *	  cannot be treated as constants because they contain noncachable
- *	  function calls.  (Example: WHERE random() < 0.5)
- *	* *constantQual receives a list of the remaining quals, which can be
- *	  treated as constants for any one scan of the current query level.
- *	  (They are really only pseudo-constant, since they may contain
- *	  Params or outer-level Vars.)
- *----------
+ * Returns a list of the pseudo-constant clauses in constantQual and the
+ * remaining quals as the return value.
  */
 List *
-pull_constant_clauses(List *quals,
-					  List **noncachableQual,
-					  List **constantQual)
+pull_constant_clauses(List *quals, List **constantQual)
 {
-	List	   *q;
-	List	   *normqual = NIL;
-	List	   *noncachequal = NIL;
 	List	   *constqual = NIL;
+	List	   *restqual = NIL;
+	List	   *q;
 
 	foreach(q, quals)
 	{
-		Node	   *qual = (Node *) lfirst(q);
+		Node   *qual = (Node *) lfirst(q);
 
-		if (contain_var_clause(qual))
-			normqual = lappend(normqual, qual);
-		else if (contain_noncachable_functions(qual))
-			noncachequal = lappend(noncachequal, qual);
-		else
+		if (is_pseudo_constant_clause(qual))
 			constqual = lappend(constqual, qual);
+		else
+			restqual = lappend(restqual, qual);
 	}
-
-	*noncachableQual = noncachequal;
 	*constantQual = constqual;
-	return normqual;
+	return restqual;
 }
 
 
@@ -1636,9 +1635,9 @@ simplify_op_or_func(Expr *expr, List *args)
  * will have List structure at the top level, and it handles TargetEntry nodes
  * so that a scan of a target list can be handled without additional code.
  * (But only the "expr" part of a TargetEntry is examined, unless the walker
- * chooses to process TargetEntry nodes specially.)  Also, RangeTblRef and
- * JoinExpr nodes are handled, so that qual expressions in a jointree can be
- * processed without additional code.
+ * chooses to process TargetEntry nodes specially.)  Also, RangeTblRef,
+ * FromExpr, and JoinExpr nodes are handled, so that qual expressions in a
+ * jointree can be processed without additional code.
  *
  * expression_tree_walker will handle SubLink and SubPlan nodes by recursing
  * normally into the "lefthand" arguments (which belong to the outer plan).
@@ -1801,6 +1800,16 @@ expression_tree_walker(Node *node,
 			break;
 		case T_TargetEntry:
 			return walker(((TargetEntry *) node)->expr, context);
+		case T_FromExpr:
+			{
+				FromExpr    *from = (FromExpr *) node;
+
+				if (walker(from->fromlist, context))
+					return true;
+				if (walker(from->quals, context))
+					return true;
+			}
+			break;
 		case T_JoinExpr:
 			{
 				JoinExpr    *join = (JoinExpr *) node;
@@ -1844,14 +1853,12 @@ query_tree_walker(Query *query,
 
 	if (walker((Node *) query->targetList, context))
 		return true;
-	if (walker(query->qual, context))
+	if (walker((Node *) query->jointree, context))
 		return true;
 	if (walker(query->havingQual, context))
 		return true;
-	if (walker((Node *) query->jointree, context))
-		return true;
 	/*
-	 * XXX for subselect-in-FROM, may need to examine rtable as well
+	 * XXX for subselect-in-FROM, may need to examine rtable as well?
 	 */
 	return false;
 }
@@ -2126,6 +2133,17 @@ expression_tree_mutator(Node *node,
 				return (Node *) newnode;
 			}
 			break;
+		case T_FromExpr:
+			{
+				FromExpr *from = (FromExpr *) node;
+				FromExpr *newnode;
+
+				FLATCOPY(newnode, from, FromExpr);
+				MUTATE(newnode->fromlist, from->fromlist, List *);
+				MUTATE(newnode->quals, from->quals, Node *);
+				return (Node *) newnode;
+			}
+			break;
 		case T_JoinExpr:
 			{
 				JoinExpr *join = (JoinExpr *) node;
diff --git a/src/backend/optimizer/util/indexnode.c b/src/backend/optimizer/util/indexnode.c
deleted file mode 100644
index e8d97aae7cf..00000000000
--- a/src/backend/optimizer/util/indexnode.c
+++ /dev/null
@@ -1,34 +0,0 @@
-/*-------------------------------------------------------------------------
- *
- * indexnode.c
- *	  Routines to find all indices on a relation
- *
- * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
- * Portions Copyright (c) 1994, Regents of the University of California
- *
- *
- * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/indexnode.c,v 1.22 2000/01/26 05:56:40 momjian Exp $
- *
- *-------------------------------------------------------------------------
- */
-#include "postgres.h"
-
-#include "optimizer/pathnode.h"
-#include "optimizer/plancat.h"
-
-
-/*
- * find_relation_indices
- *	  Returns a list of index nodes containing appropriate information for
- *	  each (secondary) index defined on a relation.
- *
- */
-List *
-find_relation_indices(Query *root, RelOptInfo *rel)
-{
-	if (rel->indexed)
-		return find_secondary_indexes(root, lfirsti(rel->relids));
-	else
-		return NIL;
-}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index fc73bb2b664..737b4db2d3d 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.65 2000/09/12 21:06:58 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.66 2000/09/29 18:21:23 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,6 +16,7 @@
 
 #include "postgres.h"
 
+#include "nodes/plannodes.h"
 #include "optimizer/cost.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
@@ -272,7 +273,6 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
  * create_seqscan_path
  *	  Creates a path corresponding to a sequential scan, returning the
  *	  pathnode.
- *
  */
 Path *
 create_seqscan_path(RelOptInfo *rel)
@@ -343,8 +343,8 @@ create_index_path(Query *root,
 	 * We are making a pathnode for a single-scan indexscan; therefore,
 	 * both indexid and indexqual should be single-element lists.
 	 */
-	pathnode->indexid = lconsi(index->indexoid, NIL);
-	pathnode->indexqual = lcons(indexquals, NIL);
+	pathnode->indexid = makeListi1(index->indexoid);
+	pathnode->indexqual = makeList1(indexquals);
 
 	pathnode->indexscandir = indexscandir;
 
@@ -391,6 +391,27 @@ create_tidscan_path(RelOptInfo *rel, List *tideval)
 }
 
 /*
+ * create_subqueryscan_path
+ *	  Creates a path corresponding to a sequential scan of a subquery,
+ *	  returning the pathnode.
+ */
+Path *
+create_subqueryscan_path(RelOptInfo *rel)
+{
+	Path	   *pathnode = makeNode(Path);
+
+	pathnode->pathtype = T_SubqueryScan;
+	pathnode->parent = rel;
+	pathnode->pathkeys = NIL;	/* for now, assume unordered result */
+
+	/* just copy the subplan's cost estimates */
+	pathnode->startup_cost = rel->subplan->startup_cost;
+	pathnode->total_cost = rel->subplan->total_cost;
+
+	return pathnode;
+}
+
+/*
  * create_nestloop_path
  *	  Creates a pathnode corresponding to a nestloop join between two
  *	  relations.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 750a463122f..0d32e82ed9a 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.60 2000/07/27 23:16:04 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.61 2000/09/29 18:21:23 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -25,7 +25,6 @@
 #include "catalog/pg_inherits.h"
 #include "catalog/pg_index.h"
 #include "optimizer/plancat.h"
-#include "parser/parsetree.h"
 #include "utils/builtins.h"
 #include "utils/fmgroids.h"
 #include "utils/relcache.h"
@@ -37,16 +36,15 @@
 /*
  * relation_info -
  *	  Retrieves catalog information for a given relation.
- *	  Given the rangetable index of the relation, return the following info:
+ *	  Given the Oid of the relation, return the following info:
  *				whether the relation has secondary indices
  *				number of pages
  *				number of tuples
  */
 void
-relation_info(Query *root, Index relid,
+relation_info(Oid relationObjectId,
 			  bool *hasindex, long *pages, double *tuples)
 {
-	Oid			relationObjectId = getrelid(relid, root->rtable);
 	HeapTuple	relationTuple;
 	Form_pg_class relation;
 
@@ -69,19 +67,18 @@ relation_info(Query *root, Index relid,
 /*
  * find_secondary_indexes
  *	  Creates a list of IndexOptInfo nodes containing information for each
- *	  secondary index defined on the given relation.
+ *	  secondary index defined on the specified relation.
  *
- * 'relid' is the RT index of the relation for which indices are being located
+ * 'relationObjectId' is the OID of the relation for which indices are wanted
  *
  * Returns a list of new IndexOptInfo nodes.
  */
 List *
-find_secondary_indexes(Query *root, Index relid)
+find_secondary_indexes(Oid relationObjectId)
 {
 	List	   *indexinfos = NIL;
 	List	   *indexoidlist,
 			   *indexoidscan;
-	Oid			indrelid = getrelid(relid, root->rtable);
 	Relation	relation;
 
 	/*
@@ -89,12 +86,12 @@ find_secondary_indexes(Query *root, Index relid)
 	 * a cached list of OID indexes for each relation.  So, get that list
 	 * and then use the syscache to obtain pg_index entries.
 	 */
-	relation = heap_open(indrelid, AccessShareLock);
+	relation = heap_open(relationObjectId, AccessShareLock);
 	indexoidlist = RelationGetIndexList(relation);
 
 	foreach(indexoidscan, indexoidlist)
 	{
-		Oid		indexoid = lfirsti(indexoidscan);
+		Oid			indexoid = lfirsti(indexoidscan);
 		HeapTuple	indexTuple;
 		Form_pg_index index;
 		IndexOptInfo *info;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 87e87597d11..86258b0f644 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.28 2000/09/12 21:06:58 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.29 2000/09/29 18:21:23 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,6 +19,7 @@
 #include "optimizer/pathnode.h"
 #include "optimizer/plancat.h"
 #include "optimizer/tlist.h"
+#include "parser/parsetree.h"
 
 
 static List *new_join_tlist(List *tlist, int first_resdomno);
@@ -44,6 +45,7 @@ get_base_rel(Query *root, int relid)
 {
 	List	   *baserels;
 	RelOptInfo *rel;
+	Oid			relationObjectId;
 
 	foreach(baserels, root->base_rel_list)
 	{
@@ -59,7 +61,7 @@ get_base_rel(Query *root, int relid)
 
 	/* No existing RelOptInfo for this base rel, so make a new one */
 	rel = makeNode(RelOptInfo);
-	rel->relids = lconsi(relid, NIL);
+	rel->relids = makeListi1(relid);
 	rel->rows = 0;
 	rel->width = 0;
 	rel->targetlist = NIL;
@@ -67,18 +69,31 @@ get_base_rel(Query *root, int relid)
 	rel->cheapest_startup_path = NULL;
 	rel->cheapest_total_path = NULL;
 	rel->pruneable = true;
+	rel->issubquery = false;
 	rel->indexed = false;
 	rel->pages = 0;
 	rel->tuples = 0;
+	rel->subplan = NULL;
 	rel->baserestrictinfo = NIL;
 	rel->baserestrictcost = 0;
 	rel->outerjoinset = NIL;
 	rel->joininfo = NIL;
 	rel->innerjoin = NIL;
 
-	/* Retrieve relation statistics from the system catalogs. */
-	relation_info(root, relid,
-				  &rel->indexed, &rel->pages, &rel->tuples);
+	/* Check rtable to see if it's a plain relation or a subquery */
+	relationObjectId = getrelid(relid, root->rtable);
+
+	if (relationObjectId != InvalidOid)
+	{
+		/* Plain relation --- retrieve statistics from the system catalogs */
+		relation_info(relationObjectId,
+					  &rel->indexed, &rel->pages, &rel->tuples);
+	}
+	else
+	{
+		/* subquery --- mark it as such for later processing */
+		rel->issubquery = true;
+	}
 
 	root->base_rel_list = lcons(rel, root->base_rel_list);
 
@@ -174,9 +189,11 @@ get_join_rel(Query *root,
 	joinrel->cheapest_startup_path = NULL;
 	joinrel->cheapest_total_path = NULL;
 	joinrel->pruneable = true;
+	joinrel->issubquery = false;
 	joinrel->indexed = false;
 	joinrel->pages = 0;
 	joinrel->tuples = 0;
+	joinrel->subplan = NULL;
 	joinrel->baserestrictinfo = NIL;
 	joinrel->baserestrictcost = 0;
 	joinrel->outerjoinset = NIL;
@@ -310,7 +327,7 @@ build_joinrel_restrictlist(RelOptInfo *joinrel,
 	 * We must eliminate duplicates, since we will see the same clauses
 	 * arriving from both input relations...
 	 */
-	return LispUnion(subbuild_joinrel_restrictlist(joinrel,
+	return set_union(subbuild_joinrel_restrictlist(joinrel,
 												   outer_rel->joininfo),
 					 subbuild_joinrel_restrictlist(joinrel,
 												   inner_rel->joininfo));
@@ -396,7 +413,7 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel,
 
 			new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids);
 			new_joininfo->jinfo_restrictinfo =
-				LispUnion(new_joininfo->jinfo_restrictinfo,
+				set_union(new_joininfo->jinfo_restrictinfo,
 						  joininfo->jinfo_restrictinfo);
 		}
 	}
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index adbfd884c36..318c789c4af 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.11 2000/09/12 21:06:58 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.12 2000/09/29 18:21:23 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -59,7 +59,7 @@ get_actual_clauses(List *restrictinfo_list)
  * get_actual_join_clauses
  *
  * Extract clauses from 'restrictinfo_list', separating those that
- * came from JOIN/ON conditions from those that didn't.
+ * syntactically match the join level from those that were pushed down.
  */
 void
 get_actual_join_clauses(List *restrictinfo_list,
@@ -74,9 +74,9 @@ get_actual_join_clauses(List *restrictinfo_list,
 	{
 		RestrictInfo *clause = (RestrictInfo *) lfirst(temp);
 
-		if (clause->isjoinqual)
-			*joinquals = lappend(*joinquals, clause->clause);
-		else
+		if (clause->ispusheddown)
 			*otherquals = lappend(*otherquals, clause->clause);
+		else
+			*joinquals = lappend(*joinquals, clause->clause);
 	}
 }