Add a concept of "placeholder" variables to the planner. These are variables

that represent some expression that we desire to compute below the top level
of the plan, and then let that value "bubble up" as though it were a plain
Var (ie, a column value).

The immediate application is to allow sub-selects to be flattened even when
they are below an outer join and have non-nullable output expressions.
Formerly we couldn't flatten because such an expression wouldn't properly
go to NULL when evaluated above the outer join.  Now, we wrap it in a
PlaceHolderVar and arrange for the actual evaluation to occur below the outer
join.  When the resulting Var bubbles up through the join, it will be set to
NULL if necessary, yielding the correct results.  This fixes a planner
limitation that's existed since 7.1.

In future we might want to use this mechanism to re-introduce some form of
Hellerstein's "expensive functions" optimization, ie place the evaluation of
an expensive function at the most suitable point in the plan tree.

4 files changed, 91 insertions, 8 deletions

diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 4aa5ce43458..ddd9934cf1e 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.213 2008/10/04 21:56:55 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.214 2008/10/21 20:42:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -213,8 +213,10 @@ typedef enum NodeTag
 	T_RestrictInfo,
 	T_InnerIndexscanInfo,
 	T_FlattenedSubLink,
+	T_PlaceHolderVar,
 	T_SpecialJoinInfo,
 	T_AppendRelInfo,
+	T_PlaceHolderInfo,
 	T_PlannerParamItem,
 
 	/*
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 9934daa64a8..b5eb00a7a67 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.161 2008/10/17 20:23:45 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.162 2008/10/21 20:42:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -76,6 +76,8 @@ typedef struct PlannerGlobal
 
 	List	   *invalItems;		/* other dependencies, as PlanInvalItems */
 
+	Index		lastPHId;		/* highest PlaceHolderVar ID assigned */
+
 	bool		transientPlan;	/* redo plan when TransactionXmin changes? */
 } PlannerGlobal;
 
@@ -163,6 +165,8 @@ typedef struct PlannerInfo
 
 	List	   *append_rel_list;	/* list of AppendRelInfos */
 
+	List	   *placeholder_list;	/* list of PlaceHolderInfos */
+
 	List	   *query_pathkeys; /* desired pathkeys for query_planner(), and
 								 * actual pathkeys afterwards */
 
@@ -243,11 +247,12 @@ typedef struct PlannerInfo
  *			   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)
- *		reltargetlist - List of Var nodes for the attributes we need to
- *						output from this relation (in no particular order,
- *						but all rels of an appendrel set must use same order)
+ *		reltargetlist - List of Var and PlaceHolderVar nodes for the values
+ *						we need to output from this relation.
+ *						List is in no particular order, but all rels of an
+ *						appendrel set must use corresponding orders.
  *						NOTE: in a child relation, may contain RowExpr or
- *						ConvertRowtypeExpr representing a whole-row Var
+ *						ConvertRowtypeExpr representing a whole-row Var.
  *		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
@@ -1090,6 +1095,29 @@ typedef struct FlattenedSubLink
 } FlattenedSubLink;
 
 /*
+ * Placeholder node for an expression to be evaluated below the top level
+ * of a plan tree.  This is used during planning to represent the contained
+ * expression.  At the end of the planning process it is replaced by either
+ * the contained expression or a Var referring to a lower-level evaluation of
+ * the contained expression.  Typically the evaluation occurs below an outer
+ * join, and Var references above the outer join might thereby yield NULL
+ * instead of the expression value.
+ *
+ * Although the planner treats this as an expression node type, it is not
+ * recognized by the parser or executor, so we declare it here rather than
+ * in primnodes.h.
+ */
+
+typedef struct PlaceHolderVar
+{
+	Expr		xpr;
+	Expr	   *phexpr;			/* the represented expression */
+	Relids		phrels;			/* base relids syntactically within expr src */
+	Index		phid;			/* ID for PHV (unique within planner run) */
+	Index		phlevelsup;		/* > 0 if PHV belongs to outer query */
+} PlaceHolderVar;
+
+/*
  * "Special join" info.
  *
  * One-sided outer joins constrain the order of joining partially but not
@@ -1251,6 +1279,31 @@ typedef struct AppendRelInfo
 } AppendRelInfo;
 
 /*
+ * For each distinct placeholder expression generated during planning, we
+ * store a PlaceHolderInfo node in the PlannerInfo node's placeholder_list.
+ * This stores info that is needed centrally rather than in each copy of the
+ * PlaceHolderVar.  The phid fields identify which PlaceHolderInfo goes with
+ * each PlaceHolderVar.  Note that phid is unique throughout a planner run,
+ * not just within a query level --- this is so that we need not reassign ID's
+ * when pulling a subquery into its parent.
+ *
+ * The idea is to evaluate the expression at (only) the ph_eval_at join level,
+ * then allow it to bubble up like a Var until the ph_needed join level.
+ * ph_needed has the same definition as attr_needed for a regular Var.
+ */
+
+typedef struct PlaceHolderInfo
+{
+	NodeTag		type;
+
+	Index		phid;			/* ID for PH (unique within planner run) */
+	PlaceHolderVar *ph_var;		/* copy of PlaceHolderVar tree */
+	Relids		ph_eval_at;		/* lowest level we can evaluate value at */
+	Relids		ph_needed;		/* highest level the value is needed at */
+	int32		ph_width;		/* estimated attribute width */
+} PlaceHolderInfo;
+
+/*
  * glob->paramlist keeps track of the PARAM_EXEC slots that we have decided
  * we need for the query.  At runtime these slots are used to pass values
  * either down into subqueries (for outer references in subqueries) or up out
diff --git a/src/include/optimizer/placeholder.h b/src/include/optimizer/placeholder.h
new file mode 100644
index 00000000000..4f39aedcfed
--- /dev/null
+++ b/src/include/optimizer/placeholder.h
@@ -0,0 +1,28 @@
+/*-------------------------------------------------------------------------
+ *
+ * placeholder.h
+ *	  prototypes for optimizer/util/placeholder.c.
+ *
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/optimizer/placeholder.h,v 1.1 2008/10/21 20:42:53 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef PLACEHOLDER_H
+#define PLACEHOLDER_H
+
+#include "nodes/relation.h"
+
+
+extern PlaceHolderVar *make_placeholder_expr(PlannerInfo *root, Expr *expr,
+											 Relids phrels);
+extern PlaceHolderInfo *find_placeholder_info(PlannerInfo *root,
+											  PlaceHolderVar *phv);
+extern void fix_placeholder_eval_levels(PlannerInfo *root);
+extern void add_placeholders_to_joinrel(PlannerInfo *root,
+										RelOptInfo *joinrel);
+
+#endif   /* PLACEHOLDER_H */
diff --git a/src/include/optimizer/var.h b/src/include/optimizer/var.h
index 4a8f84e5532..c478259bcdb 100644
--- a/src/include/optimizer/var.h
+++ b/src/include/optimizer/var.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/var.h,v 1.38 2008/09/01 20:42:45 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/var.h,v 1.39 2008/10/21 20:42:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -24,7 +24,7 @@ extern bool contain_vars_of_level(Node *node, int levelsup);
 extern int	locate_var_of_level(Node *node, int levelsup);
 extern int	locate_var_of_relation(Node *node, int relid, int levelsup);
 extern int	find_minimum_var_level(Node *node);
-extern List *pull_var_clause(Node *node, bool includeUpperVars);
+extern List *pull_var_clause(Node *node, bool includePlaceHolderVars);
 extern Node *flatten_join_alias_vars(PlannerInfo *root, Node *node);
 
 #endif   /* VAR_H */