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!

7 files changed, 240 insertions, 71 deletions

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;