IN clauses appearing at top level of WHERE can now be handled as joins.

There are two implementation techniques: the executor understands a new
JOIN_IN jointype, which emits at most one matching row per left-hand row,
or the result of the IN's sub-select can be fed through a DISTINCT filter
and then joined as an ordinary relation.
Along the way, some minor code cleanup in the optimizer; notably, break
out most of the jointree-rearrangement preprocessing in planner.c and
put it in a new file prep/prepjointree.c.

13 files changed, 100 insertions, 23 deletions

diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index f119b5111db..bf8bb1719ed 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nodes.h,v 1.134 2002/12/16 16:22:46 tgl Exp $
+ * $Id: nodes.h,v 1.135 2003/01/20 18:55:00 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -152,10 +152,12 @@ typedef enum NodeTag
 	T_AppendPath,
 	T_ResultPath,
 	T_MaterialPath,
+	T_UniquePath,
 	T_PathKeyItem,
 	T_RestrictInfo,
 	T_JoinInfo,
 	T_InnerIndexscanInfo,
+	T_InClauseInfo,
 
 	/*
 	 * TAGS FOR MEMORY NODES (memnodes.h)
@@ -408,11 +410,20 @@ typedef enum JoinType
 	 * join in the executor.  (The planner must convert it to an Append
 	 * plan.)
 	 */
-	JOIN_UNION
+	JOIN_UNION,
 
 	/*
-	 * Eventually we will have some additional join types for efficient
-	 * support of queries like WHERE foo IN (SELECT bar FROM ...).
+	 * These are used for queries like WHERE foo IN (SELECT bar FROM ...).
+	 * Only JOIN_IN is actually implemented in the executor; the others
+	 * are defined for internal use in the planner.
+	 */
+	JOIN_IN,					/* at most one result per outer row */
+	JOIN_REVERSE_IN,			/* at most one result per inner row */
+	JOIN_UNIQUE_OUTER,			/* outer path must be made unique */
+	JOIN_UNIQUE_INNER			/* inner path must be made unique */
+
+	/*
+	 * We might need additional join types someday.
 	 */
 } JoinType;
 
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 6ca3894b0da..9bbee593bf4 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parsenodes.h,v 1.225 2003/01/06 00:31:45 tgl Exp $
+ * $Id: parsenodes.h,v 1.226 2003/01/20 18:55:00 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -101,6 +101,7 @@ typedef struct Query
 	List	   *join_rel_list;	/* list of join-relation RelOptInfos */
 	List	   *equi_key_list;	/* list of lists of equijoined
 								 * PathKeyItems */
+	List	   *in_info_list;	/* list of InClauseInfos */
 	List	   *query_pathkeys; /* desired pathkeys for query_planner() */
 	bool		hasJoinRTEs;	/* true if any RTEs are RTE_JOIN kind */
 } Query;
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 9ef4fab957e..d3b01b7fed0 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pg_list.h,v 1.30 2002/11/24 21:52:15 tgl Exp $
+ * $Id: pg_list.h,v 1.31 2003/01/20 18:55:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -145,7 +145,8 @@ extern List *set_intersecti(List *list1, List *list2);
 
 extern bool equali(List *list1, List *list2);
 extern bool sameseti(List *list1, List *list2);
-extern bool nonoverlap_setsi(List *list1, List *list2);
+extern bool overlap_setsi(List *list1, List *list2);
+#define nonoverlap_setsi(list1, list2) (!overlap_setsi(list1, list2))
 extern bool is_subseti(List *list1, List *list2);
 
 extern void freeList(List *list);
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a21debe02f9..c2d8970234f 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.76 2003/01/15 19:35:44 tgl Exp $
+ * $Id: relation.h,v 1.77 2003/01/20 18:55:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -97,6 +97,8 @@ typedef struct QualCost
  *								(regardless of its ordering)
  *		cheapest_total_path - the pathlist member with lowest total cost
  *							  (regardless of its ordering)
+ *		cheapest_unique_path - for caching cheapest path to produce unique
+ *							   (no duplicates) output from relation
  *		pruneable - flag to let the planner know whether it can prune the
  *					pathlist of this RelOptInfo or not.
  *
@@ -183,6 +185,7 @@ typedef struct RelOptInfo
 	List	   *pathlist;		/* Path structures */
 	struct Path *cheapest_startup_path;
 	struct Path *cheapest_total_path;
+	struct Path *cheapest_unique_path;
 	bool		pruneable;
 
 	/* information about a base rel (not set for join rels!) */
@@ -404,6 +407,23 @@ typedef struct MaterialPath
 } MaterialPath;
 
 /*
+ * UniquePath represents elimination of distinct rows from the output of
+ * its subpath.
+ *
+ * This is unlike the other Path nodes in that it can actually generate
+ * two different plans: either hash-based or sort-based implementation.
+ * The decision is sufficiently localized that it's not worth having two
+ * separate Path node types.
+ */
+typedef struct UniquePath
+{
+	Path		path;
+	Path	   *subpath;
+	bool		use_hash;
+	double		rows;			/* estimated number of result tuples */
+} UniquePath;
+
+/*
  * All join-type paths share these fields.
  */
 
@@ -649,4 +669,25 @@ typedef struct InnerIndexscanInfo
 	Path	   *best_innerpath;	/* best inner indexscan, or NULL if none */
 } InnerIndexscanInfo;
 
+/*
+ * IN clause info.
+ *
+ * When we convert top-level IN quals into join operations, we must restrict
+ * the order of joining and use special join methods at some join points.
+ * We record information about each such IN clause in an InClauseInfo struct.
+ * These structs are kept in the Query node's in_info_list.
+ */
+
+typedef struct InClauseInfo
+{
+	NodeTag		type;
+	List	   *lefthand;		/* base relids in lefthand expressions */
+	List	   *righthand;		/* base relids coming from the subselect */
+	List	   *sub_targetlist;	/* targetlist of original RHS subquery */
+	/*
+	 * Note: sub_targetlist is just a list of Vars or expressions;
+	 * it does not contain TargetEntry nodes.
+	 */
+} InClauseInfo;
+
 #endif   /* RELATION_H */
diff --git a/src/include/optimizer/joininfo.h b/src/include/optimizer/joininfo.h
index f17e278238c..37131b722d2 100644
--- a/src/include/optimizer/joininfo.h
+++ b/src/include/optimizer/joininfo.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: joininfo.h,v 1.21 2002/06/20 20:29:51 momjian Exp $
+ * $Id: joininfo.h,v 1.22 2003/01/20 18:55:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,5 +17,6 @@
 #include "nodes/relation.h"
 
 extern JoinInfo *find_joininfo_node(RelOptInfo *this_rel, List *join_relids);
+extern JoinInfo *make_joininfo_node(RelOptInfo *this_rel, List *join_relids);
 
 #endif   /* JOININFO_H */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 77ed27e7e55..759b18c2499 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pathnode.h,v 1.47 2003/01/15 19:35:47 tgl Exp $
+ * $Id: pathnode.h,v 1.48 2003/01/20 18:55:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -38,6 +38,8 @@ extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);
 extern ResultPath *create_result_path(RelOptInfo *rel, Path *subpath,
 									  List *constantqual);
 extern MaterialPath *create_material_path(RelOptInfo *rel, Path *subpath);
+extern UniquePath *create_unique_path(Query *root, RelOptInfo *rel,
+									  Path *subpath);
 extern Path *create_subqueryscan_path(RelOptInfo *rel);
 extern Path *create_functionscan_path(Query *root, RelOptInfo *rel);
 
@@ -75,6 +77,7 @@ extern void build_base_rel(Query *root, int relid);
 extern RelOptInfo *build_other_rel(Query *root, int relid);
 extern RelOptInfo *find_base_rel(Query *root, int relid);
 extern RelOptInfo *build_join_rel(Query *root,
+			   List *joinrelids,
 			   RelOptInfo *outer_rel,
 			   RelOptInfo *inner_rel,
 			   JoinType jointype,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 66925931609..cf9c2ddeb64 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planmain.h,v 1.66 2003/01/15 23:10:32 tgl Exp $
+ * $Id: planmain.h,v 1.67 2003/01/20 18:55:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -32,6 +32,8 @@ extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual,
 extern Append *make_append(List *appendplans, bool isTarget, List *tlist);
 extern Sort *make_sort(Query *root, List *tlist,
 		  Plan *lefttree, int keycount);
+extern Sort *make_sort_from_sortclauses(Query *root, List *tlist,
+										Plan *lefttree, List *sortcls);
 extern Agg *make_agg(Query *root, List *tlist, List *qual,
 					 AggStrategy aggstrategy,
 					 int numGroupCols, AttrNumber *grpColIdx,
diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h
index f49583a7ef3..16885b2f138 100644
--- a/src/include/optimizer/planner.h
+++ b/src/include/optimizer/planner.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planner.h,v 1.24 2002/06/20 20:29:51 momjian Exp $
+ * $Id: planner.h,v 1.25 2003/01/20 18:55:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,7 +21,4 @@
 extern Plan *planner(Query *parse);
 extern Plan *subquery_planner(Query *parse, double tuple_fraction);
 
-extern Plan *make_sortplan(Query *parse, List *tlist,
-			  Plan *plannode, List *sortcls);
-
 #endif   /* PLANNER_H */
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index 1bb64af3ae5..17ecb4d593f 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: prep.h,v 1.33 2002/08/29 16:03:49 tgl Exp $
+ * $Id: prep.h,v 1.34 2003/01/20 18:55:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -18,6 +18,16 @@
 #include "nodes/plannodes.h"
 
 /*
+ * prototypes for prepjointree.c
+ */
+extern Node *pull_up_IN_clauses(Query *parse, Node *node);
+extern Node *pull_up_subqueries(Query *parse, Node *jtnode,
+				   bool below_outer_join);
+extern Node *preprocess_jointree(Query *parse, Node *jtnode);
+extern List *get_relids_in_jointree(Node *jtnode);
+extern List *get_relids_for_join(Query *parse, int joinrelid);
+
+/*
  * prototypes for prepqual.c
  */
 extern List *canonicalize_qual(Expr *qual, bool removeAndFlag);
diff --git a/src/include/optimizer/subselect.h b/src/include/optimizer/subselect.h
index 8fead9929f6..2e6a4640684 100644
--- a/src/include/optimizer/subselect.h
+++ b/src/include/optimizer/subselect.h
@@ -2,6 +2,11 @@
  *
  * subselect.h
  *
+ * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $Id: subselect.h,v 1.17 2003/01/20 18:55:05 tgl Exp $
+ *
  *-------------------------------------------------------------------------
  */
 #ifndef SUBSELECT_H
@@ -14,8 +19,9 @@ extern List *PlannerInitPlan;	/* init subplans for current query */
 extern List *PlannerParamVar;	/* to get Var from Param->paramid */
 extern int	PlannerPlanId;		/* to assign unique ID to subquery plans */
 
-extern List *SS_finalize_plan(Plan *plan, List *rtable);
+extern Node *convert_IN_to_join(Query *parse, SubLink *sublink);
 extern Node *SS_replace_correlation_vars(Node *expr);
 extern Node *SS_process_sublinks(Node *expr, bool isQual);
+extern List *SS_finalize_plan(Plan *plan, List *rtable);
 
 #endif   /* SUBSELECT_H */
diff --git a/src/include/optimizer/tlist.h b/src/include/optimizer/tlist.h
index 7b82b5ae291..b38f4016f98 100644
--- a/src/include/optimizer/tlist.h
+++ b/src/include/optimizer/tlist.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: tlist.h,v 1.32 2002/06/20 20:29:51 momjian Exp $
+ * $Id: tlist.h,v 1.33 2003/01/20 18:55:06 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -32,5 +32,7 @@ extern TargetEntry *get_sortgroupclause_tle(SortClause *sortClause,
 						List *targetList);
 extern Node *get_sortgroupclause_expr(SortClause *sortClause,
 						 List *targetList);
+extern List *get_sortgrouplist_exprs(List *sortClauses,
+						 List *targetList);
 
 #endif   /* TLIST_H */
diff --git a/src/include/optimizer/var.h b/src/include/optimizer/var.h
index 07b8b311d07..b207acac593 100644
--- a/src/include/optimizer/var.h
+++ b/src/include/optimizer/var.h
@@ -7,14 +7,14 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: var.h,v 1.24 2003/01/15 19:35:47 tgl Exp $
+ * $Id: var.h,v 1.25 2003/01/20 18:55:06 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #ifndef VAR_H
 #define VAR_H
 
-#include "nodes/primnodes.h"
+#include "nodes/parsenodes.h"
 
 
 extern List *pull_varnos(Node *node);
@@ -22,7 +22,9 @@ extern bool contain_var_reference(Node *node, int varno, int varattno,
 					  int levelsup);
 extern bool contain_whole_tuple_var(Node *node, int varno, int levelsup);
 extern bool contain_var_clause(Node *node);
+extern bool contain_vars_of_level(Node *node, int levelsup);
+extern bool contain_vars_above_level(Node *node, int levelsup);
 extern List *pull_var_clause(Node *node, bool includeUpperVars);
-extern Node *flatten_join_alias_vars(Node *node, List *rtable);
+extern Node *flatten_join_alias_vars(Query *root, Node *node);
 
 #endif   /* VAR_H */
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index 49f3bc7e005..037c2b2f5e3 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: selfuncs.h,v 1.10 2002/11/19 23:22:00 tgl Exp $
+ * $Id: selfuncs.h,v 1.11 2003/01/20 18:55:07 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -75,7 +75,7 @@ extern void mergejoinscansel(Query *root, Node *clause,
 				 Selectivity *leftscan,
 				 Selectivity *rightscan);
 
-extern double estimate_num_groups(Query *root, List *groupClauses,
+extern double estimate_num_groups(Query *root, List *groupExprs,
 								  double input_rows);
 
 extern Datum btcostestimate(PG_FUNCTION_ARGS);