First cut at full support for OUTER JOINs. There are still a few loose

ends to clean up (see my message of same date to pghackers), but mostly
it works.  INITDB REQUIRED!

24 files changed, 381 insertions, 212 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index b73ea0e6136..eb067fe5057 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -37,7 +37,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: catversion.h,v 1.44 2000/09/12 04:49:15 momjian Exp $
+ * $Id: catversion.h,v 1.45 2000/09/12 21:07:06 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	200009111
+#define CATALOG_VERSION_NO	200009121
 
 #endif
diff --git a/src/include/executor/execdebug.h b/src/include/executor/execdebug.h
index 7eb6667da03..c4ba3d1f5b6 100644
--- a/src/include/executor/execdebug.h
+++ b/src/include/executor/execdebug.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execdebug.h,v 1.13 2000/06/15 00:52:07 momjian Exp $
+ * $Id: execdebug.h,v 1.14 2000/09/12 21:07:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -129,16 +129,6 @@
  */
 
 /* ----------------
- *		EXEC_MERGEJOINPFREE is a flag which causes merge joins
- *		to pfree intermittant tuples (which is the proper thing)
- *		Not defining this means we avoid menory management problems
- *		at the cost of doing deallocation of stuff only at the
- *		end of the transaction
- * ----------------
-#undef EXEC_MERGEJOINPFREE
- */
-
-/* ----------------
  *		EXEC_DEBUGINTERACTIVE is a flag which enables the
  *		user to issue "DEBUG" commands from an interactive
  *		backend.
@@ -170,11 +160,10 @@
  *			  only as necessary -cim 10/26/89
  * ----------------------------------------------------------------
  */
-#define T_OR_F(b)				(b ? "true" : "false")
+#define T_OR_F(b)				((b) ? "true" : "false")
 #define NULL_OR_TUPLE(slot)		(TupIsNull(slot) ? "null" : "a tuple")
 
 
-/* #define EXEC_TUPLECOUNT - XXX take out for now for executor stubbing -- jolly*/
 /* ----------------
  *		tuple count debugging defines
  * ----------------
@@ -326,28 +315,31 @@ extern int	NIndexTupleInserted;
 #define MJ1_printf(s, p)				printf(s, p)
 #define MJ2_printf(s, p1, p2)			printf(s, p1, p2)
 #define MJ_debugtup(tuple, type)		debugtup(tuple, type, NULL)
-#define MJ_dump(context, state)			ExecMergeTupleDump(econtext, state)
+#define MJ_dump(state)					ExecMergeTupleDump(state)
 #define MJ_DEBUG_QUAL(clause, res) \
   MJ2_printf("  ExecQual(%s, econtext) returns %s\n", \
 			 CppAsString(clause), T_OR_F(res));
 
 #define MJ_DEBUG_MERGE_COMPARE(qual, res) \
-  MJ2_printf("  MergeCompare(mergeclauses, %s, ..) returns %s\n", \
+  MJ2_printf("  MergeCompare(mergeclauses, %s, ...) returns %s\n", \
 			 CppAsString(qual), T_OR_F(res));
 
 #define MJ_DEBUG_PROC_NODE(slot) \
-  MJ2_printf("  %s = ExecProcNode(innerPlan) returns %s\n", \
+  MJ2_printf("  %s = ExecProcNode(...) returns %s\n", \
 			 CppAsString(slot), NULL_OR_TUPLE(slot));
+
 #else
+
 #define MJ_nodeDisplay(l)
 #define MJ_printf(s)
 #define MJ1_printf(s, p)
 #define MJ2_printf(s, p1, p2)
 #define MJ_debugtup(tuple, type)
-#define MJ_dump(context, state)
+#define MJ_dump(state)
 #define MJ_DEBUG_QUAL(clause, res)
 #define MJ_DEBUG_MERGE_COMPARE(qual, res)
 #define MJ_DEBUG_PROC_NODE(slot)
+
 #endif	 /* EXEC_MERGEJOINDEBUG */
 
 /* ----------------------------------------------------------------
diff --git a/src/include/executor/execdefs.h b/src/include/executor/execdefs.h
index 89fed192cdd..6b9457969b1 100644
--- a/src/include/executor/execdefs.h
+++ b/src/include/executor/execdefs.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execdefs.h,v 1.6 2000/01/26 05:58:05 momjian Exp $
+ * $Id: execdefs.h,v 1.7 2000/09/12 21:07:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -42,9 +42,13 @@
 #define EXEC_MJ_NEXTOUTER				5
 #define EXEC_MJ_TESTOUTER				6
 #define EXEC_MJ_NEXTINNER				7
-#define EXEC_MJ_SKIPINNER				8
-#define EXEC_MJ_SKIPOUTER				9
-#define EXEC_MJ_FILLINNER			   10
-#define EXEC_MJ_FILLOUTER			   11
+#define EXEC_MJ_SKIPOUTER_BEGIN			8
+#define EXEC_MJ_SKIPOUTER_TEST			9
+#define EXEC_MJ_SKIPOUTER_ADVANCE		10
+#define EXEC_MJ_SKIPINNER_BEGIN			11
+#define EXEC_MJ_SKIPINNER_TEST			12
+#define EXEC_MJ_SKIPINNER_ADVANCE		13
+#define EXEC_MJ_ENDOUTER				14
+#define EXEC_MJ_ENDINNER				15
 
 #endif	 /* EXECDEFS_H */
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 5eb7cbb93ba..5c330915e75 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: executor.h,v 1.50 2000/08/24 23:34:09 tgl Exp $
+ * $Id: executor.h,v 1.51 2000/09/12 21:07:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -117,7 +117,9 @@ extern void ExecSetSlotDescriptorIsNew(TupleTableSlot *slot, bool isNew);
 extern void ExecInitResultTupleSlot(EState *estate, CommonState *commonstate);
 extern void ExecInitScanTupleSlot(EState *estate,
 					  CommonScanState *commonscanstate);
-extern void ExecInitOuterTupleSlot(EState *estate, HashJoinState *hashstate);
+extern TupleTableSlot *ExecInitExtraTupleSlot(EState *estate);
+extern TupleTableSlot *ExecInitNullTupleSlot(EState *estate,
+											 TupleDesc tupType);
 
 extern TupleDesc ExecGetTupType(Plan *node);
 extern TupleDesc ExecTypeFromTL(List *targetList);
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 9626dbf8b1c..83ed6c5234b 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execnodes.h,v 1.48 2000/08/24 03:29:13 tgl Exp $
+ * $Id: execnodes.h,v 1.49 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -469,11 +469,18 @@ typedef CommonState JoinState;
 
 /* ----------------
  *	 NestLoopState information
+ *
+ *		NeedNewOuter       true if need new outer tuple on next call
+ *		MatchedOuter       true if found a join match for current outer tuple
+ *		NullInnerTupleSlot prepared null tuple for left outer joins
  * ----------------
  */
 typedef struct NestLoopState
 {
 	JoinState	jstate;			/* its first field is NodeTag */
+	bool		nl_NeedNewOuter;
+	bool		nl_MatchedOuter;
+	TupleTableSlot *nl_NullInnerTupleSlot;
 } NestLoopState;
 
 /* ----------------
@@ -482,7 +489,13 @@ typedef struct NestLoopState
  *		OuterSkipQual	   outerKey1 < innerKey1 ...
  *		InnerSkipQual	   outerKey1 > innerKey1 ...
  *		JoinState		   current "state" of join. see executor.h
+ *		MatchedOuter       true if found a join match for current outer tuple
+ *		MatchedInner       true if found a join match for current inner tuple
+ *		OuterTupleSlot     pointer to slot in tuple table for cur outer tuple
+ *		InnerTupleSlot     pointer to slot in tuple table for cur inner tuple
  *		MarkedTupleSlot    pointer to slot in tuple table for marked tuple
+ *		NullOuterTupleSlot prepared null tuple for right outer joins
+ *		NullInnerTupleSlot prepared null tuple for left outer joins
  * ----------------
  */
 typedef struct MergeJoinState
@@ -491,7 +504,13 @@ typedef struct MergeJoinState
 	List	   *mj_OuterSkipQual;
 	List	   *mj_InnerSkipQual;
 	int			mj_JoinState;
+	bool		mj_MatchedOuter;
+	bool		mj_MatchedInner;
+	TupleTableSlot *mj_OuterTupleSlot;
+	TupleTableSlot *mj_InnerTupleSlot;
 	TupleTableSlot *mj_MarkedTupleSlot;
+	TupleTableSlot *mj_NullOuterTupleSlot;
+	TupleTableSlot *mj_NullInnerTupleSlot;
 } MergeJoinState;
 
 /* ----------------
@@ -506,6 +525,10 @@ typedef struct MergeJoinState
  *		hj_InnerHashKey			the inner hash key in the hashjoin condition
  *		hj_OuterTupleSlot		tuple slot for outer tuples
  *		hj_HashTupleSlot		tuple slot for hashed tuples
+ *		hj_NullInnerTupleSlot   prepared null tuple for left outer joins
+ *		hj_NeedNewOuter         true if need new outer tuple on next call
+ *		hj_MatchedOuter         true if found a join match for current outer
+ *		hj_hashdone				true if hash-table-build phase is done
  * ----------------
  */
 typedef struct HashJoinState
@@ -517,6 +540,10 @@ typedef struct HashJoinState
 	Node	   *hj_InnerHashKey;
 	TupleTableSlot *hj_OuterTupleSlot;
 	TupleTableSlot *hj_HashTupleSlot;
+	TupleTableSlot *hj_NullInnerTupleSlot;
+	bool		hj_NeedNewOuter;
+	bool		hj_MatchedOuter;
+	bool		hj_hashdone;
 } HashJoinState;
 
 
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index d825c8fe395..f3929d8b2c6 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nodes.h,v 1.75 2000/08/24 03:29:13 tgl Exp $
+ * $Id: nodes.h,v 1.76 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -68,6 +68,8 @@ typedef enum NodeTag
 	T_ArrayRef,
 	T_Iter,
 	T_RelabelType,
+	T_RangeTblRef,
+	T_JoinExpr,
 
 	/*---------------------
 	 * TAGS FOR PLANNER NODES (relation.h)
@@ -204,7 +206,7 @@ typedef enum NodeTag
 	T_A_Indices,
 	T_ResTarget,
 	T_TypeCast,
-	T_RelExpr,
+	T_RangeSubselect,
 	T_SortGroupBy,
 	T_RangeVar,
 	T_TypeName,
@@ -217,14 +219,14 @@ typedef enum NodeTag
 	T_SortClause,
 	T_GroupClause,
 	T_SubSelectXXX,				/* not used anymore; this tag# is available */
-	T_JoinExpr,
+	T_oldJoinExprXXX,			/* not used anymore; this tag# is available */
 	T_CaseExpr,
 	T_CaseWhen,
 	T_RowMark,
 	T_FkConstraint,
 
 	/*---------------------
-	 * TAGS FOR FUNCTION-CALL CONTEXT AND RESULTINFO NODES (cf. fmgr.h)
+	 * TAGS FOR FUNCTION-CALL CONTEXT AND RESULTINFO NODES (see fmgr.h)
 	 *---------------------
 	 */
 	T_TriggerData = 800,		/* in commands/trigger.h */
@@ -310,7 +312,7 @@ typedef double Cost;			/* execution cost (in page-access units) */
 
 /*
  * CmdType -
- *	  enums for type of operation to aid debugging
+ *	  enums for type of operation represented by a Query
  *
  * ??? could have put this in parsenodes.h but many files not in the
  *	  optimizer also need this...
@@ -329,4 +331,40 @@ typedef enum CmdType
 } CmdType;
 
 
+/*
+ * JoinType -
+ *	  enums for types of relation joins
+ *
+ * JoinType determines the exact semantics of joining two relations using
+ * a matching qualification.  For example, it tells what to do with a tuple
+ * that has no match in the other relation.
+ *
+ * This is needed in both parsenodes.h and plannodes.h, so put it here...
+ */
+typedef enum JoinType
+{
+	/*
+	 * The canonical kinds of joins
+	 */
+	JOIN_INNER,					/* matching tuple pairs only */
+	JOIN_LEFT,					/* pairs + unmatched outer tuples */
+	JOIN_FULL,					/* pairs + unmatched outer + unmatched inner */
+	JOIN_RIGHT,					/* pairs + unmatched inner tuples */
+	/*
+	 * SQL92 considers UNION JOIN to be a kind of join, so list it here for
+	 * parser convenience, even though it's not implemented like a join in
+	 * the executor.  (The planner must convert it to an Append plan.)
+	 */
+	JOIN_UNION
+	/*
+	 * Eventually we will have some additional join types for efficient
+	 * support of queries like WHERE foo IN (SELECT bar FROM ...).
+	 */
+} JoinType;
+
+#define IS_OUTER_JOIN(jointype) \
+	((jointype) == JOIN_LEFT || \
+	 (jointype) == JOIN_FULL || \
+	 (jointype) == JOIN_RIGHT)
+
 #endif	 /* NODES_H */
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index f6c75c19781..440a7609d83 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parsenodes.h,v 1.112 2000/09/12 05:09:50 momjian Exp $
+ * $Id: parsenodes.h,v 1.113 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -40,7 +40,7 @@ typedef struct Query
 	Node	   *utilityStmt;	/* non-null if this is a non-optimizable
 								 * statement */
 
-	int			resultRelation; /* target relation (index to rtable) */
+	int			resultRelation; /* target relation (index into rtable) */
 	char	   *into;			/* portal (cursor) name */
 	bool		isPortal;		/* is this a retrieve into portal? */
 	bool		isBinary;		/* binary portal? */
@@ -50,6 +50,8 @@ typedef struct Query
 	bool		hasSubLinks;	/* has subquery SubLink */
 
 	List	   *rtable;			/* list of range table entries */
+	List	   *jointree;		/* table join tree (from the FROM clause) */
+
 	List	   *targetList;		/* target list (of TargetEntry) */
 	Node	   *qual;			/* qualifications applied to tuples */
 	List	   *rowMark;		/* list of RowMark entries */
@@ -1058,16 +1060,6 @@ typedef struct ResTarget
 } ResTarget;
 
 /*
- * RelExpr - relation expressions
- */
-typedef struct RelExpr
-{
-	NodeTag		type;
-	char	   *relname;		/* the relation name */
-	bool		inh;			/* inheritance query */
-} RelExpr;
-
-/*
  * SortGroupBy - for ORDER BY clause
  */
 typedef struct SortGroupBy
@@ -1083,11 +1075,22 @@ typedef struct SortGroupBy
 typedef struct RangeVar
 {
 	NodeTag		type;
-	RelExpr    *relExpr;		/* the relation expression */
-	Attr	   *name;			/* the name to be referenced (optional) */
+	char	   *relname;		/* the relation name */
+	bool		inh;			/* expand rel by inheritance? */
+	Attr	   *name;			/* optional table alias & column aliases */
 } RangeVar;
 
 /*
+ * RangeSubselect - subquery appearing in a FROM clause
+ */
+typedef struct RangeSubselect
+{
+	NodeTag		type;
+	Node	   *subquery;		/* the untransformed sub-select clause */
+	Attr	   *name;			/* optional table alias & column aliases */
+} RangeSubselect;
+
+/*
  * IndexElem - index parameters (used in CREATE INDEX)
  *
  * For a plain index, each 'name' is an attribute name in the heap relation,
@@ -1114,20 +1117,6 @@ typedef struct DefElem
 	Node	   *arg;			/* a (Value *) or a (TypeName *) */
 } DefElem;
 
-/*
- * JoinExpr - for JOIN expressions
- */
-typedef struct JoinExpr
-{
-	NodeTag		type;
-	int			jointype;
-	bool		isNatural;		/* Natural join? Will need to shape table */
-	Node	   *larg;			/* RangeVar or join expression */
-	Node	   *rarg;			/* RangeVar or join expression */
-	Attr	   *alias;			/* table and column aliases, if any */
-	List	   *quals;			/* qualifiers on join, if any */
-} JoinExpr;
-
 
 /****************************************************************************
  *	Nodes for a Query tree
@@ -1155,11 +1144,12 @@ typedef struct TargetEntry
  *	  Some of the following are only used in one of
  *	  the parsing, optimizing, execution stages.
  *
- *	  eref is the expanded table name and columns for the underlying
- *	  relation. Note that for outer join syntax, allowed reference names
- *	  could be modified as one evaluates the nested clauses (e.g.
- *	  "SELECT ... FROM t1 NATURAL JOIN t2 WHERE ..." forbids explicit mention
- *	  of a table name in any reference to the join column.
+ *	  alias is an Attr node representing the AS alias-clause attached to the
+ *	  FROM expression, or NULL if no clause.
+ *
+ *	  eref is the table reference name and column reference names (either
+ *	  real or aliases).  This is filled in during parse analysis.  Note that
+ *	  system columns (OID etc) are not included in the column list.
  *
  *	  inFromCl marks those range variables that are listed in the FROM clause.
  *	  In SQL, the query can only refer to range variables listed in the
@@ -1170,29 +1160,17 @@ typedef struct TargetEntry
  *	  implicitly-added RTE shouldn't change the namespace for unqualified
  *	  column names processed later, and it also shouldn't affect the
  *	  expansion of '*'.
- *
- *	  inJoinSet marks those range variables that the planner should join
- *	  over even if they aren't explicitly referred to in the query.  For
- *	  example, "SELECT COUNT(1) FROM tx" should produce the number of rows
- *	  in tx.  A more subtle example uses a POSTQUEL implicit RTE:
- *			SELECT COUNT(1) FROM tx WHERE TRUE OR (tx.f1 = ty.f2)
- *	  Here we should get the product of the sizes of tx and ty.  However,
- *	  the query optimizer can simplify the WHERE clause to "TRUE", so
- *	  ty will no longer be referred to explicitly; without a flag forcing
- *	  it to be included in the join, we will get the wrong answer.	So,
- *	  a POSTQUEL implicit RTE must be marked inJoinSet but not inFromCl.
  *--------------------
  */
 typedef struct RangeTblEntry
 {
 	NodeTag		type;
 	char	   *relname;		/* real name of the relation */
-	Attr	   *ref;			/* reference names (given in FROM clause) */
-	Attr	   *eref;			/* expanded reference names */
 	Oid			relid;			/* OID of the relation */
+	Attr	   *alias;			/* user-written alias clause, if any */
+	Attr	   *eref;			/* expanded reference names */
 	bool		inh;			/* inheritance requested? */
 	bool		inFromCl;		/* present in FROM clause */
-	bool		inJoinSet;		/* planner must include this rel */
 	bool		skipAcl;		/* skip ACL check in executor */
 } RangeTblEntry;
 
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index a0e9881dc87..4e0bcfc7053 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pg_list.h,v 1.18 2000/06/09 01:44:26 momjian Exp $
+ * $Id: pg_list.h,v 1.19 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -101,6 +101,7 @@ extern List *nconc(List *list1, List *list2);
 extern List *lcons(void *datum, List *list);
 extern List *lconsi(int datum, List *list);
 extern bool member(void *datum, List *list);
+extern bool ptrMember(void *datum, List *list);
 extern bool intMember(int datum, List *list);
 extern Value *makeInteger(long i);
 extern Value *makeFloat(char *numericStr);
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index e348d25b2ba..cf93b9dee17 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: plannodes.h,v 1.41 2000/07/12 02:37:33 tgl Exp $
+ * $Id: plannodes.h,v 1.42 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -82,7 +82,7 @@ typedef struct Plan
 								 * individual nodes point to one EState
 								 * for the whole top-level plan */
 	List	   *targetlist;
-	List	   *qual;			/* Node* or List* ?? */
+	List	   *qual;			/* implicitly-ANDed qual conditions */
 	struct Plan *lefttree;
 	struct Plan *righttree;
 	List	   *extParam;		/* indices of _all_ _external_ PARAM_EXEC
@@ -210,9 +210,26 @@ typedef struct TidScan
 
 /* ----------------
  *		Join node
+ *
+ * jointype:	rule for joining tuples from left and right subtrees
+ * joinqual:	qual conditions that came from JOIN/ON or JOIN/USING
+ *				(plan.qual contains conditions that came from WHERE)
+ *
+ * When jointype is INNER, joinqual and plan.qual are semantically
+ * interchangeable.  For OUTER jointypes, the two are *not* interchangeable;
+ * only joinqual is used to determine whether a match has been found for
+ * the purpose of deciding whether to generate null-extended tuples.
+ * (But plan.qual is still applied before actually returning a tuple.)
+ * For an outer join, only joinquals are allowed to be used as the merge
+ * or hash condition of a merge or hash join.
  * ----------------
  */
-typedef Plan Join;
+typedef struct Join
+{
+	Plan		plan;
+	JoinType	jointype;
+	List	   *joinqual;		/* JOIN quals (in addition to plan.qual) */
+} Join;
 
 /* ----------------
  *		nest loop join node
@@ -245,7 +262,6 @@ typedef struct HashJoin
 	List	   *hashclauses;
 	Oid			hashjoinop;
 	HashJoinState *hashjoinstate;
-	bool		hashdone;
 } HashJoin;
 
 /* ---------------
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 0ef350687dc..bc17773642c 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -1,13 +1,16 @@
 /*-------------------------------------------------------------------------
  *
  * primnodes.h
- *	  Definitions for parse tree/query tree ("primitive") nodes.
+ *	  Definitions for "primitive" node types, those that are used in more
+ *	  than one of the parse/plan/execute stages of the query pipeline.
+ *	  Currently, these are mostly nodes for executable expressions
+ *	  and join trees.
  *
  *
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: primnodes.h,v 1.47 2000/08/24 03:29:13 tgl Exp $
+ * $Id: primnodes.h,v 1.48 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -98,6 +101,12 @@ typedef struct Fjoin
 	BoolPtr		fj_alwaysDone;
 } Fjoin;
 
+
+/* ----------------------------------------------------------------
+ *					node types for executable expressions
+ * ----------------------------------------------------------------
+ */
+
 /* ----------------
  * Expr
  *		typeOid			- oid of the type of this expression
@@ -155,7 +164,7 @@ typedef struct Var
 	AttrNumber	varattno;
 	Oid			vartype;
 	int32		vartypmod;
-	Index		varlevelsup;	/* erased by upper optimizer */
+	Index		varlevelsup;
 	Index		varnoold;		/* mainly for debugging --- see above */
 	AttrNumber	varoattno;
 } Var;
@@ -480,4 +489,76 @@ typedef struct RelabelType
 	int32		resulttypmod;
 } RelabelType;
 
+
+/* ----------------------------------------------------------------
+ *					node types for join trees
+ *
+ * The leaves of a join tree structure are RangeTblRef nodes.  Above
+ * these, JoinExpr nodes can appear to denote a specific kind of join
+ * or qualified join.  A join tree can also contain List nodes --- a list
+ * implies an unqualified cross-product join of its members.  The planner
+ * is allowed to combine the elements of a list using whatever join order
+ * seems good to it.  At present, JoinExpr nodes are always joined in
+ * exactly the order implied by the tree structure (except the planner
+ * may choose to swap inner and outer members of a join pair).
+ *
+ * NOTE: currently, the planner only supports a List at the top level of
+ * a join tree.  Should generalize this to allow Lists at lower levels.
+ *
+ * NOTE: the qualification expressions present in JoinExpr nodes are
+ * *in addition to* the query's main WHERE clause.  For outer joins there
+ * is a real semantic difference between a join qual and a WHERE clause,
+ * though if all joins are inner joins they are interchangeable.
+ *
+ * NOTE: in the raw output of gram.y, a join tree contains RangeVar and
+ * RangeSubselect nodes, which are both replaced by RangeTblRef nodes
+ * during the parse analysis phase.
+ * ----------------------------------------------------------------
+ */
+
+/*
+ * RangeTblRef - reference to an entry in the query's rangetable
+ *
+ * We could use direct pointers to the RT entries and skip having these
+ * nodes, but multiple pointers to the same node in a querytree cause
+ * lots of headaches, so it seems better to store an index into the RT.
+ */
+typedef struct RangeTblRef
+{
+	NodeTag		type;
+	int			rtindex;
+} RangeTblRef;
+
+/*----------
+ * JoinExpr - for SQL JOIN expressions
+ *
+ * isNatural, using, and quals are interdependent.  The user can write only
+ * one of NATURAL, USING(), or ON() (this is enforced by the grammar).
+ * If he writes NATURAL then parse analysis generates the equivalent USING()
+ * list, and from that fills in "quals" with the right equality comparisons.
+ * If he writes USING() then "quals" is filled with equality comparisons.
+ * If he writes ON() then only "quals" is set.  Note that NATURAL/USING
+ * are not equivalent to ON() since they also affect the output column list.
+ *
+ * alias is an Attr node representing the AS alias-clause attached to the
+ * join expression, or NULL if no clause.  During parse analysis, colnames
+ * is filled with a list of String nodes giving the column names (real or
+ * alias) of the output of the join, and colvars is filled with a list of
+ * expressions that can be copied to reference the output columns.
+ *----------
+ */
+typedef struct JoinExpr
+{
+	NodeTag		type;
+	JoinType	jointype;		/* type of join */
+	bool		isNatural;		/* Natural join? Will need to shape table */
+	Node	   *larg;			/* left subtree */
+	Node	   *rarg;			/* right subtree */
+	List	   *using;			/* USING clause, if any (list of String) */
+	Node	   *quals;			/* qualifiers on join, if any */
+	struct Attr *alias;			/* user-written alias clause, if any */
+	List	   *colnames;		/* output column names (list of String) */
+	List	   *colvars;		/* output column nodes (list of expressions) */
+} JoinExpr;
+
 #endif	 /* PRIMNODES_H */
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index b7d65131066..767e2e114e0 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.47 2000/04/12 17:16:40 momjian Exp $
+ * $Id: relation.h,v 1.48 2000/09/12 21:07:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -73,6 +73,9 @@ typedef enum CostSelector
  *					participates (only used for base rels)
  *		baserestrictcost - Estimated cost of evaluating the baserestrictinfo
  *					clauses at a single tuple (only used for base rels)
+ *		outerjoinset - If the rel appears within the nullable side of an outer
+ *					join, the list of all relids participating in the highest
+ *					such outer join; else NIL (only used for base rels)
  *		joininfo  - List of JoinInfo nodes, containing info about each join
  *					clause in which this relation participates
  *		innerjoin - List of Path nodes that represent indices that may be used
@@ -94,6 +97,10 @@ typedef enum CostSelector
  * We store baserestrictcost in the RelOptInfo (for base relations) because
  * we know we will need it at least once (to price the sequential scan)
  * and may need it multiple times to price index scans.
+ *
+ * outerjoinset is used to ensure correct placement of WHERE clauses that
+ * apply to outer-joined relations; we must not apply such WHERE clauses
+ * until after the outer join is performed.
  */
 
 typedef struct RelOptInfo
@@ -124,6 +131,7 @@ typedef struct RelOptInfo
 	List	   *baserestrictinfo;		/* RestrictInfo structures (if
 										 * base rel) */
 	Cost		baserestrictcost;		/* cost of evaluating the above */
+	Relids		outerjoinset;			/* integer list of base relids */
 	List	   *joininfo;		/* JoinInfo structures */
 	List	   *innerjoin;		/* potential indexscans for nestloop joins */
 
@@ -263,6 +271,9 @@ typedef struct Path
  * that refer to values of other rels, so those other rels must be
  * included in the outer joinrel in order to make a usable join.
  *
+ * 'alljoinquals' is also used only for inner paths of nestloop joins.
+ * This flag is TRUE iff all the indexquals came from JOIN/ON conditions.
+ *
  * 'rows' is the estimated result tuple count for the indexscan.  This
  * is the same as path.parent->rows for a simple indexscan, but it is
  * different for a nestloop inner path, because the additional indexquals
@@ -277,6 +288,7 @@ typedef struct IndexPath
 	List	   *indexqual;
 	ScanDirection indexscandir;
 	Relids		joinrelids;		/* other rels mentioned in indexqual */
+	bool		alljoinquals;	/* all indexquals derived from JOIN conds? */
 	double		rows;			/* estimated number of result tuples */
 } IndexPath;
 
@@ -295,8 +307,11 @@ typedef struct JoinPath
 {
 	Path		path;
 
+	JoinType	jointype;
+
 	Path	   *outerjoinpath;	/* path for the outer side of the join */
 	Path	   *innerjoinpath;	/* path for the inner side of the join */
+
 	List	   *joinrestrictinfo;		/* RestrictInfos to apply to join */
 
 	/*
@@ -375,11 +390,12 @@ typedef struct HashPath
  * The clause cannot actually be applied until we have built a join rel
  * containing all the base rels it references, however.
  *
- * When we construct a join rel that describes exactly the set of base rels
- * referenced in a multi-relation restriction clause, we place that clause
- * into the joinrestrictinfo lists of paths for the join rel.  It will be
- * applied at that join level, and will not propagate any further up the
- * join tree.  (Note: the "predicate migration" code was once intended to
+ * When we construct a join rel that includes all the base rels referenced
+ * in a multi-relation restriction clause, we place that clause into the
+ * joinrestrictinfo lists of paths for the join rel, if neither left nor
+ * right sub-path includes all base rels referenced in the clause.  The clause
+ * will be applied at that join level, and will not propagate any further up
+ * the join tree.  (Note: the "predicate migration" code was once intended to
  * push restriction clauses up and down the plan tree based on evaluation
  * costs, but it's dead code and is unlikely to be resurrected in the
  * foreseeable future.)
@@ -394,18 +410,30 @@ typedef struct HashPath
  * or hashjoin clauses are fairly limited --- the code for each kind of
  * path is responsible for identifying the restrict clauses it can use
  * and ignoring the rest.  Clauses not implemented by an indexscan,
- * mergejoin, or hashjoin will be placed in the qpqual field of the
- * final Plan node, where they will be enforced by general-purpose
+ * mergejoin, or hashjoin will be placed in the plan qual or joinqual field
+ * of the final Plan node, where they will be enforced by general-purpose
  * qual-expression-evaluation code.  (But we are still entitled to count
  * their selectivity when estimating the result tuple count, if we
  * can guess what it is...)
+ *
+ * When dealing with outer joins we must distinguish between qual clauses
+ * that came from WHERE and those that came from JOIN/ON or JOIN/USING.
+ * (For inner joins there's no semantic difference and we can treat the
+ * clauses interchangeably.)  Both kinds of quals are stored as RestrictInfo
+ * nodes during planning, but there's a flag to indicate where they came from.
+ * Note also that when outer joins are present, a qual clause may be treated
+ * as referencing more rels than it really does.  This trick ensures that the
+ * qual will be evaluated at the right level of the join tree --- we don't
+ * want quals from WHERE to be evaluated until after the outer join is done.
  */
 
 typedef struct RestrictInfo
 {
 	NodeTag		type;
 
-	Expr	   *clause;			/* the represented clause of WHERE cond */
+	Expr	   *clause;			/* the represented clause of WHERE or JOIN */
+
+	bool		isjoinqual;		/* TRUE if clause came from JOIN/ON */
 
 	/* only used if clause is an OR clause: */
 	List	   *subclauseindices;		/* indexes matching subclauses */
@@ -437,7 +465,7 @@ typedef struct RestrictInfo
 typedef struct JoinInfo
 {
 	NodeTag		type;
-	Relids		unjoined_relids;/* some rels not yet part of my RelOptInfo */
+	Relids		unjoined_relids; /* some rels not yet part of my RelOptInfo */
 	List	   *jinfo_restrictinfo;		/* relevant RestrictInfos */
 } JoinInfo;
 
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index 1b2bcd92055..62bb401193d 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: clauses.h,v 1.38 2000/08/13 02:50:26 tgl Exp $
+ * $Id: clauses.h,v 1.39 2000/09/12 21:07:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -73,9 +73,11 @@ extern void CommuteClause(Expr *clause);
 extern Node *eval_const_expressions(Node *node);
 
 extern bool expression_tree_walker(Node *node, bool (*walker) (),
-											   void *context);
+								   void *context);
 extern Node *expression_tree_mutator(Node *node, Node *(*mutator) (),
-												 void *context);
+									 void *context);
+extern bool query_tree_walker(Query *query, bool (*walker) (),
+							  void *context);
 
 #define is_subplan(clause)	((clause) != NULL && \
 							 IsA(clause, Expr) && \
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index b8788851e2b..0bf57ef0cc5 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pathnode.h,v 1.27 2000/04/12 17:16:42 momjian Exp $
+ * $Id: pathnode.h,v 1.28 2000/09/12 21:07:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -34,26 +34,29 @@ extern IndexPath *create_index_path(Query *root, RelOptInfo *rel,
 extern TidPath *create_tidscan_path(RelOptInfo *rel, List *tideval);
 
 extern NestPath *create_nestloop_path(RelOptInfo *joinrel,
-					 Path *outer_path,
-					 Path *inner_path,
-					 List *restrict_clauses,
-					 List *pathkeys);
+									  JoinType jointype,
+									  Path *outer_path,
+									  Path *inner_path,
+									  List *restrict_clauses,
+									  List *pathkeys);
 
 extern MergePath *create_mergejoin_path(RelOptInfo *joinrel,
-					  Path *outer_path,
-					  Path *inner_path,
-					  List *restrict_clauses,
-					  List *pathkeys,
-					  List *mergeclauses,
-					  List *outersortkeys,
-					  List *innersortkeys);
+										JoinType jointype,
+										Path *outer_path,
+										Path *inner_path,
+										List *restrict_clauses,
+										List *pathkeys,
+										List *mergeclauses,
+										List *outersortkeys,
+										List *innersortkeys);
 
 extern HashPath *create_hashjoin_path(RelOptInfo *joinrel,
-					 Path *outer_path,
-					 Path *inner_path,
-					 List *restrict_clauses,
-					 List *hashclauses,
-					 Selectivity innerdisbursion);
+									  JoinType jointype,
+									  Path *outer_path,
+									  Path *inner_path,
+									  List *restrict_clauses,
+									  List *hashclauses,
+									  Selectivity innerdisbursion);
 
 /*
  * prototypes for relnode.c
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 66520d6a897..35eb3190f1c 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: paths.h,v 1.46 2000/07/24 03:10:54 tgl Exp $
+ * $Id: paths.h,v 1.47 2000/09/12 21:07:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -61,21 +61,23 @@ extern void create_tidscan_paths(Query *root, RelOptInfo *rel);
  *	   routines to create join paths
  */
 extern void add_paths_to_joinrel(Query *root, RelOptInfo *joinrel,
-					 RelOptInfo *outerrel,
-					 RelOptInfo *innerrel,
-					 List *restrictlist);
+								 RelOptInfo *outerrel,
+								 RelOptInfo *innerrel,
+								 JoinType jointype,
+								 List *restrictlist);
 
 /*
  * joinrels.c
  *	  routines to determine which relations to join
  */
-extern void make_rels_by_joins(Query *root, int level);
-extern RelOptInfo *make_rels_by_clause_joins(Query *root,
-						  RelOptInfo *old_rel,
-						  List *other_rels);
-extern RelOptInfo *make_rels_by_clauseless_joins(Query *root,
-							  RelOptInfo *old_rel,
-							  List *other_rels);
+extern List *make_rels_by_joins(Query *root, int level, List **joinrels);
+extern List *make_rels_by_clause_joins(Query *root,
+									   RelOptInfo *old_rel,
+									   List *other_rels);
+extern List *make_rels_by_clauseless_joins(Query *root,
+										   RelOptInfo *old_rel,
+										   List *other_rels);
+extern RelOptInfo *make_rel_from_jointree(Query *root, Node *jtnode);
 
 /*
  * pathkeys.c
@@ -110,7 +112,7 @@ extern List *make_pathkeys_for_sortclauses(List *sortclauses,
 extern List *find_mergeclauses_for_pathkeys(List *pathkeys,
 							   List *restrictinfos);
 extern List *make_pathkeys_for_mergeclauses(Query *root,
-							   List *mergeclauses,
-							   List *tlist);
+											List *mergeclauses,
+											RelOptInfo *rel);
 
 #endif	 /* PATHS_H */
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 723543c437c..43c93978cdf 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planmain.h,v 1.43 2000/07/24 03:10:54 tgl Exp $
+ * $Id: planmain.h,v 1.44 2000/09/12 21:07:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,8 +20,7 @@
 /*
  * prototypes for plan/planmain.c
  */
-extern Plan *query_planner(Query *root, List *tlist, List *qual,
-			  double tuple_fraction);
+extern Plan *query_planner(Query *root, List *tlist, double tuple_fraction);
 
 /*
  * prototypes for plan/createplan.c
@@ -40,9 +39,10 @@ extern Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
 /*
  * prototypes for plan/initsplan.c
  */
-extern void make_var_only_tlist(Query *root, List *tlist);
+extern void build_base_rel_tlists(Query *root, List *tlist);
+extern Relids add_join_quals_to_rels(Query *root, Node *jtnode);
 extern void add_restrict_and_join_to_rels(Query *root, List *clauses);
-extern void add_missing_rels_to_query(Query *root);
+extern List *add_missing_rels_to_query(Query *root, Node *jtnode);
 extern void process_implied_equality(Query *root, Node *item1, Node *item2,
 									 Oid sortop1, Oid sortop2);
 
@@ -58,6 +58,7 @@ extern void fix_opids(Node *node);
  * prep/prepkeyset.c
  */
 extern bool _use_keyset_query_optimizer;
+
 extern void transformKeySetQuery(Query *origNode);
 
 #endif	 /* PLANMAIN_H */
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 3d94854e03b..2e1d4d66f99 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: restrictinfo.h,v 1.8 2000/01/26 05:58:21 momjian Exp $
+ * $Id: restrictinfo.h,v 1.9 2000/09/12 21:07:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -18,5 +18,7 @@
 
 extern bool restriction_is_or_clause(RestrictInfo *restrictinfo);
 extern List *get_actual_clauses(List *restrictinfo_list);
+extern void get_actual_join_clauses(List *restrictinfo_list,
+									List **joinquals, List **otherquals);
 
 #endif	 /* RESTRICTINFO_H */
diff --git a/src/include/parser/gramparse.h b/src/include/parser/gramparse.h
index 02c95745fee..54d6e869ad9 100644
--- a/src/include/parser/gramparse.h
+++ b/src/include/parser/gramparse.h
@@ -1,28 +1,31 @@
 /*-------------------------------------------------------------------------
  *
  * gramparse.h
- *	  scanner support routines.  used by both the bootstrap lexer
- * as well as the normal lexer
+ *	  Declarations for routines exported from lexer and parser files.
+ *
  *
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: gramparse.h,v 1.12 2000/04/12 17:16:44 momjian Exp $
+ * $Id: gramparse.h,v 1.13 2000/09/12 21:07:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 
 #ifndef GRAMPARSE_H
-#define GRAMPARSE_H				/* include once only */
+#define GRAMPARSE_H
 
-/* from scan.l */
-extern void init_io(void);
+/* from parser.c */
 extern int	yylex(void);
+
+/* from scan.l */
+extern void scanner_init(void);
+extern int	base_yylex(void);
 extern void yyerror(const char *message);
 
 /* from gram.y */
-extern Oid	param_type(int t);
 extern void parser_init(Oid *typev, int nargs);
+extern Oid	param_type(int t);
 extern int	yyparse(void);
 
 #endif	 /* GRAMPARSE_H */
diff --git a/src/include/parser/parse_clause.h b/src/include/parser/parse_clause.h
index b9a868d4420..fd1cfdb3604 100644
--- a/src/include/parser/parse_clause.h
+++ b/src/include/parser/parse_clause.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parse_clause.h,v 1.18 2000/06/09 01:44:29 momjian Exp $
+ * $Id: parse_clause.h,v 1.19 2000/09/12 21:07:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,7 +17,8 @@
 #include "parser/parse_node.h"
 
 extern void makeRangeTable(ParseState *pstate, List *frmList);
-extern void setTargetTable(ParseState *pstate, char *relname, bool inh);
+extern void setTargetTable(ParseState *pstate, char *relname,
+						   bool inh, bool inJoinSet);
 extern Node *transformWhereClause(ParseState *pstate, Node *where);
 extern List *transformGroupClause(ParseState *pstate, List *grouplist,
 					 List *targetlist);
diff --git a/src/include/parser/parse_func.h b/src/include/parser/parse_func.h
index be96652cfb2..d221c600c8e 100644
--- a/src/include/parser/parse_func.h
+++ b/src/include/parser/parse_func.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parse_func.h,v 1.26 2000/08/20 00:44:17 tgl Exp $
+ * $Id: parse_func.h,v 1.27 2000/09/12 21:07:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -39,11 +39,11 @@ typedef struct _CandidateList
 }		   *CandidateList;
 
 extern Node *ParseNestedFuncOrColumn(ParseState *pstate, Attr *attr,
-						int *curr_resno, int precedence);
+									 int precedence);
 extern Node *ParseFuncOrColumn(ParseState *pstate,
-				  char *funcname, List *fargs,
-				  bool agg_star, bool agg_distinct,
-				  int *curr_resno, int precedence);
+							   char *funcname, List *fargs,
+							   bool agg_star, bool agg_distinct,
+							   int precedence);
 
 extern bool func_get_detail(char *funcname, int nargs, Oid *argtypes,
 							Oid *funcid, Oid *rettype,
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index d4231e8819d..002391d6530 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parse_node.h,v 1.20 2000/05/12 01:33:52 tgl Exp $
+ * $Id: parse_node.h,v 1.21 2000/09/12 21:07:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,36 +16,28 @@
 #include "nodes/parsenodes.h"
 #include "utils/rel.h"
 
-/* State information used during parse analysis
- * p_join_quals is a list of untransformed qualification expressions
- * (implicitly ANDed together) found in the FROM clause.
- * Needs to be available later to merge with other qualifiers from the
- * WHERE clause.
+/*
+ * State information used during parse analysis
  */
 typedef struct ParseState
 {
-	int			p_last_resno;
-	List	   *p_rtable;
-	struct ParseState *parentParseState;
+	struct ParseState *parentParseState; /* stack link */
+	List	   *p_rtable;		/* range table so far */
+	List	   *p_jointree;		/* join tree so far */
+	int			p_last_resno;	/* last targetlist resno assigned */
 	bool		p_hasAggs;
 	bool		p_hasSubLinks;
 	bool		p_is_insert;
 	bool		p_is_update;
-	bool		p_is_rule;
-	bool		p_in_where_clause;
 	Relation	p_target_relation;
 	RangeTblEntry *p_target_rangetblentry;
-	List	   *p_shape;
-	List	   *p_alias;
-	List	   *p_join_quals;
 } ParseState;
 
 extern ParseState *make_parsestate(ParseState *parentParseState);
 extern Expr *make_op(char *opname, Node *ltree, Node *rtree);
 extern Node *make_operand(char *opname, Node *tree,
 			 Oid orig_typeId, Oid target_typeId);
-extern Var *make_var(ParseState *pstate, Oid relid, char *refname,
-		 char *attrname);
+extern Var *make_var(ParseState *pstate, RangeTblEntry *rte, int attrno);
 extern ArrayRef *transformArraySubscripts(ParseState *pstate,
 						 Node *arrayBase,
 						 List *indirection,
diff --git a/src/include/parser/parse_relation.h b/src/include/parser/parse_relation.h
index 4f89bcc65c3..7c7a04844e4 100644
--- a/src/include/parser/parse_relation.h
+++ b/src/include/parser/parse_relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parse_relation.h,v 1.18 2000/06/08 22:37:53 momjian Exp $
+ * $Id: parse_relation.h,v 1.19 2000/09/12 21:07:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,23 +16,35 @@
 
 #include "parser/parse_node.h"
 
-extern RangeTblEntry *refnameRangeTableEntry(ParseState *pstate, char *refname);
+extern Node *refnameRangeOrJoinEntry(ParseState *pstate,
+									 char *refname,
+									 int *sublevels_up);
+extern RangeTblEntry *refnameRangeTableEntry(ParseState *pstate,
+											 char *refname);
 extern int refnameRangeTablePosn(ParseState *pstate,
-					  char *refname,
-					  int *sublevels_up);
-extern RangeTblEntry *colnameRangeTableEntry(ParseState *pstate, char *colname);
+								 char *refname,
+								 int *sublevels_up);
+extern int RTERangeTablePosn(ParseState *pstate,
+							 RangeTblEntry *rte,
+							 int *sublevels_up);
+extern JoinExpr *scanJoinTreeForRefname(Node *jtnode, char *refname);
+extern Node *colnameToVar(ParseState *pstate, char *colname);
+extern Node *qualifiedNameToVar(ParseState *pstate, char *refname,
+								char *colname, bool implicitRTEOK);
 extern RangeTblEntry *addRangeTableEntry(ParseState *pstate,
-				   char *relname,
-				   Attr *ref,
-				   bool inh,
-				   bool inFromCl,
-				   bool inJoinSet);
-extern Attr *expandTable(ParseState *pstate, char *refname, bool getaliases);
-extern List *expandAll(ParseState *pstate, char *relname, Attr *ref,
-		  int *this_resno);
+										 char *relname,
+										 Attr *alias,
+										 bool inh,
+										 bool inFromCl);
+extern void addRTEtoJoinTree(ParseState *pstate, RangeTblEntry *rte);
+extern RangeTblEntry *addImplicitRTE(ParseState *pstate, char *relname);
+extern void expandRTE(ParseState *pstate, RangeTblEntry *rte,
+					  List **colnames, List **colvars);
+extern List *expandRelAttrs(ParseState *pstate, RangeTblEntry *rte);
+extern List *expandJoinAttrs(ParseState *pstate, JoinExpr *join,
+							 int sublevels_up);
 extern int	attnameAttNum(Relation rd, char *a);
 extern int	specialAttNum(char *a);
 extern Oid	attnumTypeId(Relation rd, int attid);
-extern void warnAutoRange(ParseState *pstate, char *refname);
 
 #endif	 /* PARSE_RELATION_H */
diff --git a/src/include/parser/parsetree.h b/src/include/parser/parsetree.h
index 277bc32a504..ff727cfd07a 100644
--- a/src/include/parser/parsetree.h
+++ b/src/include/parser/parsetree.h
@@ -8,41 +8,26 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parsetree.h,v 1.10 2000/06/12 19:40:51 momjian Exp $
+ * $Id: parsetree.h,v 1.11 2000/09/12 21:07:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #ifndef PARSETREE_H
-#define PARSETREE_H				/* include once only */
+#define PARSETREE_H
 
 #include "nodes/parsenodes.h"
 #include "nodes/pg_list.h"
 
 /* ----------------
- *		need pg_list.h for definitions of CAR(), etc. macros
+ *		need pg_list.h for definitions of nth(), etc.
  * ----------------
  */
 
 /* ----------------
  *		range table macros
- *
- *	parse tree:
- *		(root targetlist qual)
- *		 ^^^^
- *	parse root:
- *		(numlevels cmdtype resrel rangetable priority ruleinfo nestdotinfo)
- *								  ^^^^^^^^^^
- *	range table:
- *		(rtentry ...)
- *	rtentry:
  * ----------------
  */
 
-#define rt_relname(rt_entry) \
-	  ((!strcmp(((rt_entry)->ref->relname),"*OLD*") ||\
-		!strcmp(((rt_entry)->ref->relname),"*NEW*")) ? ((rt_entry)->ref->relname) : \
-		((char *)(rt_entry)->relname))
-
 /*
  *		rt_fetch
  *		rt_store
@@ -51,22 +36,18 @@
  *
  */
 #define rt_fetch(rangetable_index, rangetable) \
-	((RangeTblEntry*)nth((rangetable_index)-1, rangetable))
+	((RangeTblEntry*) nth((rangetable_index)-1, rangetable))
 
 #define rt_store(rangetable_index, rangetable, rt) \
 	set_nth(rangetable, (rangetable_index)-1, rt)
 
 /*
  *		getrelid
- *		getrelname
  *
  *		Given the range index of a relation, return the corresponding
- *		relation id or relation name.
+ *		relation OID.
  */
 #define getrelid(rangeindex,rangetable) \
-	((RangeTblEntry*)nth((rangeindex)-1, rangetable))->relid
-
-#define getrelname(rangeindex, rangetable) \
-	rt_relname((RangeTblEntry*)nth((rangeindex)-1, rangetable))
+	(rt_fetch(rangeindex, rangetable)->relid)
 
 #endif	 /* PARSETREE_H */
diff --git a/src/include/rewrite/rewriteHandler.h b/src/include/rewrite/rewriteHandler.h
index 7af0f3932ec..5271d78717c 100644
--- a/src/include/rewrite/rewriteHandler.h
+++ b/src/include/rewrite/rewriteHandler.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: rewriteHandler.h,v 1.12 2000/01/26 05:58:30 momjian Exp $
+ * $Id: rewriteHandler.h,v 1.13 2000/09/12 21:07:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,9 +16,8 @@
 
 #include "nodes/parsenodes.h"
 
-struct _rewrite_meta_knowledge
+typedef struct RewriteInfo
 {
-	List	   *rt;
 	int			rt_index;
 	bool		instead_flag;
 	int			event;
@@ -28,9 +27,7 @@ struct _rewrite_meta_knowledge
 	Query	   *rule_action;
 	Node	   *rule_qual;
 	bool		nothing;
-};
-
-typedef struct _rewrite_meta_knowledge RewriteInfo;
+} RewriteInfo;
 
 
 extern List *QueryRewrite(Query *parsetree);
diff --git a/src/include/rewrite/rewriteManip.h b/src/include/rewrite/rewriteManip.h
index af052a65510..c41519acb8c 100644
--- a/src/include/rewrite/rewriteManip.h
+++ b/src/include/rewrite/rewriteManip.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: rewriteManip.h,v 1.21 2000/04/12 17:16:50 momjian Exp $
+ * $Id: rewriteManip.h,v 1.22 2000/09/12 21:07:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -22,6 +22,12 @@ extern void ChangeVarNodes(Node *node, int old_varno, int new_varno,
 			   int sublevels_up);
 extern void IncrementVarSublevelsUp(Node *node, int delta_sublevels_up,
 						int min_sublevels_up);
+
+extern bool rangeTableEntry_used(Node *node, int rt_index,
+								 int sublevels_up);
+extern bool attribute_used(Node *node, int rt_index, int attno,
+						   int sublevels_up);
+
 extern void AddQual(Query *parsetree, Node *qual);
 extern void AddHavingQual(Query *parsetree, Node *havingQual);
 extern void AddNotQual(Query *parsetree, Node *qual);