Restructure building of join relation targetlists so that a join plan

node emits only those vars that are actually needed above it in the
plan tree.  (There were comments in the code suggesting that this was
done at some point in the dim past, but for a long time we have just
made join nodes emit everything that either input emitted.)  Aside from
being marginally more efficient, this fixes the problem noted by Peter
Eisentraut where a join above an IN-implemented-as-join might fail,
because the subplan targetlist constructed in the latter case didn't
meet the expectation of including everything.
Along the way, fix some places that were O(N^2) in the targetlist
length.  This is not all the trouble spots for wide queries by any
means, but it's a step forward.

5 files changed, 23 insertions, 12 deletions

diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 4e06d7a284..7974c44aae 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -13,7 +13,7 @@
  *
  * Copyright (c) 2003, PostgreSQL Global Development Group
  *
- * $Id: bitmapset.h,v 1.1 2003/02/08 20:20:55 tgl Exp $
+ * $Id: bitmapset.h,v 1.2 2003/06/29 23:05:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -59,6 +59,7 @@ extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
 extern bool bms_is_member(int x, const Bitmapset *a);
 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
+extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
 extern int	bms_singleton_member(const Bitmapset *a);
 extern int	bms_num_members(const Bitmapset *a);
 /* optimized tests when we don't need to know exact membership count: */
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 8392ab505b..2ab9e0f6e7 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.81 2003/06/15 22:51:45 tgl Exp $
+ * $Id: relation.h,v 1.82 2003/06/29 23:05:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -89,8 +89,8 @@ typedef struct QualCost
  *			   clauses have been applied (ie, output rows of a plan for it)
  *		width - avg. number of bytes per tuple in the relation after the
  *				appropriate projections have been done (ie, output width)
- *		targetlist - List of TargetEntry nodes for the attributes we need
- *					 to output from this relation
+ *		reltargetlist - List of Var nodes for the attributes we need to
+ *						output from this relation (in no particular order)
  *		pathlist - List of Path nodes, one for each potentially useful
  *				   method of generating the relation
  *		cheapest_startup_path - the pathlist member with lowest startup cost
@@ -107,7 +107,12 @@ typedef struct QualCost
  *		relid - RTE index (this is redundant with the relids field, but
  *				is provided for convenience of access)
  *		rtekind - distinguishes plain relation, subquery, or function RTE
- *		varlist - list of Vars for physical columns (only if table)
+ *		min_attr, max_attr - range of valid AttrNumbers for rel
+ *		attr_needed - array of bitmapsets indicating the highest joinrel
+ *				in which each attribute is needed; if bit 0 is set then
+ *				the attribute is needed as part of final targetlist
+ *		attr_widths - cache space for per-attribute width estimates;
+ *					  zero means not computed yet
  *		indexlist - list of IndexOptInfo nodes for relation's indexes
  *					(always NIL if it's not a table)
  *		pages - number of disk pages in relation (zero if not a table)
@@ -183,7 +188,7 @@ typedef struct RelOptInfo
 	int			width;			/* estimated avg width of result tuples */
 
 	/* materialization information */
-	List	   *targetlist;
+	FastList	reltargetlist;
 	List	   *pathlist;		/* Path structures */
 	struct Path *cheapest_startup_path;
 	struct Path *cheapest_total_path;
@@ -193,7 +198,10 @@ typedef struct RelOptInfo
 	/* information about a base rel (not set for join rels!) */
 	Index		relid;
 	RTEKind		rtekind;		/* RELATION, SUBQUERY, or FUNCTION */
-	List	   *varlist;
+	AttrNumber	min_attr;		/* smallest attrno of rel (often <0) */
+	AttrNumber	max_attr;		/* largest attrno of rel */
+	Relids	   *attr_needed;	/* array indexed [min_attr .. max_attr] */
+	int32	   *attr_widths;	/* array indexed [min_attr .. max_attr] */
 	List	   *indexlist;
 	long		pages;
 	double		tuples;
diff --git a/src/include/optimizer/plancat.h b/src/include/optimizer/plancat.h
index c6b18ab0da..8f7cfbe6ce 100644
--- a/src/include/optimizer/plancat.h
+++ b/src/include/optimizer/plancat.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: plancat.h,v 1.29 2003/02/03 15:07:08 tgl Exp $
+ * $Id: plancat.h,v 1.30 2003/06/29 23:05:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,6 +19,8 @@
 
 extern void get_relation_info(Oid relationObjectId, RelOptInfo *rel);
 
+extern List *build_physical_tlist(Query *root, RelOptInfo *rel);
+
 extern List *find_inheritance_children(Oid inhparent);
 
 extern bool has_subclass(Oid relationId);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 106e9d1ce4..99c9470493 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.71 2003/06/29 00:33:44 tgl Exp $
+ * $Id: planmain.h,v 1.72 2003/06/29 23:05:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -56,7 +56,7 @@ extern Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
  * prototypes for plan/initsplan.c
  */
 extern void add_base_rels_to_query(Query *root, Node *jtnode);
-extern void build_base_rel_tlists(Query *root, List *tlist);
+extern void build_base_rel_tlists(Query *root, List *final_tlist);
 extern Relids distribute_quals_to_rels(Query *root, Node *jtnode);
 extern void process_implied_equality(Query *root,
 									 Node *item1, Node *item2,
diff --git a/src/include/optimizer/tlist.h b/src/include/optimizer/tlist.h
index e2afc3ac82..d22c78f8d8 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.35 2003/05/06 00:20:33 tgl Exp $
+ * $Id: tlist.h,v 1.36 2003/06/29 23:05:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,10 +16,10 @@
 
 #include "nodes/relation.h"
 
+
 extern TargetEntry *tlistentry_member(Node *node, List *targetlist);
 extern Resdom *tlist_member(Node *node, List *targetlist);
 
-extern void add_var_to_tlist(RelOptInfo *rel, Var *var);
 extern TargetEntry *create_tl_element(Var *var, int resdomno);
 
 extern List *flatten_tlist(List *tlist);