v2-0002-speed-up-PHI-lookups.patch

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index fb28e6411a..bf2586a341 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -6245,7 +6245,7 @@ set_rel_width(PlannerInfo *root, RelOptInfo *rel)
 			 * scanning this rel, so be sure to include it in reltarget->cost.
 			 */
 			PlaceHolderVar *phv = (PlaceHolderVar *) node;
-			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv, false);
+			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
 			QualCost	cost;
 
 			tuple_width += phinfo->ph_width;
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 7991295548..2c900e6b12 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1323,7 +1323,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 										   PVC_RECURSE_WINDOWFUNCS |
 										   PVC_INCLUDE_PLACEHOLDERS);
 
-		add_vars_to_targetlist(root, vars, ec->ec_relids, false);
+		add_vars_to_targetlist(root, vars, ec->ec_relids);
 		list_free(vars);
 	}
 }
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 337f470d58..bbeca9a9ab 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -388,8 +388,11 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 		Assert(!bms_is_member(relid, phinfo->ph_lateral));
 		if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
 			bms_is_member(relid, phinfo->ph_eval_at))
+		{
 			root->placeholder_list = foreach_delete_current(root->placeholder_list,
 															l);
+			root->placeholder_array[phinfo->phid] = NULL;
+		}
 		else
 		{
 			phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index e37f2933eb..f138f93509 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -4915,13 +4915,8 @@ replace_nestloop_params_mutator(Node *node, PlannerInfo *root)
 		/* Upper-level PlaceHolderVars should be long gone at this point */
 		Assert(phv->phlevelsup == 0);
 
-		/*
-		 * Check whether we need to replace the PHV.  We use bms_overlap as a
-		 * cheap/quick test to see if the PHV might be evaluated in the outer
-		 * rels, and then grab its PlaceHolderInfo to tell for sure.
-		 */
-		if (!bms_overlap(phv->phrels, root->curOuterRels) ||
-			!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
+		/* Check whether we need to replace the PHV */
+		if (!bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at,
 						   root->curOuterRels))
 		{
 			/*
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 023efbaf09..fd8cbb1dc7 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -189,7 +189,7 @@ build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
 
 	if (tlist_vars != NIL)
 	{
-		add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0), true);
+		add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
 		list_free(tlist_vars);
 	}
 
@@ -206,7 +206,7 @@ build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
 		if (having_vars != NIL)
 		{
 			add_vars_to_targetlist(root, having_vars,
-								   bms_make_singleton(0), true);
+								   bms_make_singleton(0));
 			list_free(having_vars);
 		}
 	}
@@ -221,14 +221,12 @@ build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
  *
  *	  The list may also contain PlaceHolderVars.  These don't necessarily
  *	  have a single owning relation; we keep their attr_needed info in
- *	  root->placeholder_list instead.  If create_new_ph is true, it's OK
- *	  to create new PlaceHolderInfos; otherwise, the PlaceHolderInfos must
- *	  already exist, and we should only update their ph_needed.  (This should
- *	  be true before deconstruct_jointree begins, and false after that.)
+ *	  root->placeholder_list instead.  Find or create the associated
+ *	  PlaceHolderInfo entry, and update its ph_needed.
  */
 void
 add_vars_to_targetlist(PlannerInfo *root, List *vars,
-					   Relids where_needed, bool create_new_ph)
+					   Relids where_needed)
 {
 	ListCell   *temp;
 
@@ -262,8 +260,7 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars,
 		else if (IsA(node, PlaceHolderVar))
 		{
 			PlaceHolderVar *phv = (PlaceHolderVar *) node;
-			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
-															create_new_ph);
+			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
 
 			phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
 												where_needed);
@@ -432,7 +429,7 @@ extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
 	 * Push Vars into their source relations' targetlists, and PHVs into
 	 * root->placeholder_list.
 	 */
-	add_vars_to_targetlist(root, newvars, where_needed, true);
+	add_vars_to_targetlist(root, newvars, where_needed);
 
 	/* Remember the lateral references for create_lateral_join_info */
 	brel->lateral_vars = newvars;
@@ -493,8 +490,7 @@ create_lateral_join_info(PlannerInfo *root)
 			else if (IsA(node, PlaceHolderVar))
 			{
 				PlaceHolderVar *phv = (PlaceHolderVar *) node;
-				PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
-																false);
+				PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
 
 				found_laterals = true;
 				lateral_relids = bms_add_members(lateral_relids,
@@ -691,6 +687,14 @@ deconstruct_jointree(PlannerInfo *root)
 	Relids		inner_join_rels;
 	List	   *postponed_qual_list = NIL;
 
+	/*
+	 * After this point, no more PlaceHolderInfos may be made, because
+	 * make_outerjoininfo and update_placeholder_eval_levels require all
+	 * active placeholders to be present in root->placeholder_list while we
+	 * crawl up the join tree.
+	 */
+	root->placeholdersFrozen = true;
+
 	/* Start recursion at top of jointree */
 	Assert(root->parse->jointree != NULL &&
 		   IsA(root->parse->jointree, FromExpr));
@@ -1866,7 +1870,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 										   PVC_RECURSE_WINDOWFUNCS |
 										   PVC_INCLUDE_PLACEHOLDERS);
 
-		add_vars_to_targetlist(root, vars, relids, false);
+		add_vars_to_targetlist(root, vars, relids);
 		list_free(vars);
 	}
 
@@ -2380,7 +2384,7 @@ process_implied_equality(PlannerInfo *root,
 										   PVC_RECURSE_WINDOWFUNCS |
 										   PVC_INCLUDE_PLACEHOLDERS);
 
-		add_vars_to_targetlist(root, vars, relids, false);
+		add_vars_to_targetlist(root, vars, relids);
 		list_free(vars);
 	}
 
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index c92ddd27ed..248cde4d9b 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -75,6 +75,8 @@ query_planner(PlannerInfo *root,
 	root->full_join_clauses = NIL;
 	root->join_info_list = NIL;
 	root->placeholder_list = NIL;
+	root->placeholder_array = NULL;
+	root->placeholder_array_size = 0;
 	root->fkey_list = NIL;
 	root->initial_rels = NIL;
 
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 64632db73c..b27cd28338 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -635,6 +635,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->qual_security_level = 0;
 	root->hasPseudoConstantQuals = false;
 	root->hasAlternativeSubPlans = false;
+	root->placeholdersFrozen = false;
 	root->hasRecursion = hasRecursion;
 	if (hasRecursion)
 		root->wt_param_id = assign_special_exec_param(root);
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 0bd99acf83..41c7066d90 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -1011,6 +1011,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->grouping_map = NULL;
 	subroot->minmax_aggs = NIL;
 	subroot->qual_security_level = 0;
+	subroot->placeholdersFrozen = false;
 	subroot->hasRecursion = false;
 	subroot->wt_param_id = -1;
 	subroot->non_recursive_path = NULL;
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 7e134822f3..cf7691a474 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -291,7 +291,7 @@ expand_inherited_rtentry(PlannerInfo *root, RelOptInfo *rel,
 		 * Add the newly added Vars to parent's reltarget.  We needn't worry
 		 * about the children's reltargets, they'll be made later.
 		 */
-		add_vars_to_targetlist(root, newvars, bms_make_singleton(0), false);
+		add_vars_to_targetlist(root, newvars, bms_make_singleton(0));
 	}
 
 	table_close(oldrelation, NoLock);
diff --git a/src/backend/optimizer/util/paramassign.c b/src/backend/optimizer/util/paramassign.c
index 12486cb067..8e2d4bf515 100644
--- a/src/backend/optimizer/util/paramassign.c
+++ b/src/backend/optimizer/util/paramassign.c
@@ -470,7 +470,7 @@ process_subquery_nestloop_params(PlannerInfo *root, List *subplan_params)
 			ListCell   *lc;
 
 			/* If not from a nestloop outer rel, complain */
-			if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
+			if (!bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at,
 							   root->curOuterRels))
 				elog(ERROR, "non-LATERAL parameter required by subquery");
 
@@ -517,8 +517,7 @@ identify_current_nestloop_params(PlannerInfo *root, Relids leftrelids)
 
 		/*
 		 * We are looking for Vars and PHVs that can be supplied by the
-		 * lefthand rels.  The "bms_overlap" test is just an optimization to
-		 * allow skipping find_placeholder_info() if the PHV couldn't match.
+		 * lefthand rels.
 		 */
 		if (IsA(nlp->paramval, Var) &&
 			bms_is_member(nlp->paramval->varno, leftrelids))
@@ -528,11 +527,8 @@ identify_current_nestloop_params(PlannerInfo *root, Relids leftrelids)
 			result = lappend(result, nlp);
 		}
 		else if (IsA(nlp->paramval, PlaceHolderVar) &&
-				 bms_overlap(((PlaceHolderVar *) nlp->paramval)->phrels,
-							 leftrelids) &&
 				 bms_is_subset(find_placeholder_info(root,
-													 (PlaceHolderVar *) nlp->paramval,
-													 false)->ph_eval_at,
+													 (PlaceHolderVar *) nlp->paramval)->ph_eval_at,
 							   leftrelids))
 		{
 			root->curOuterParams = foreach_delete_current(root->curOuterParams,
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index f0e8cd9965..44284b42a9 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -52,8 +52,8 @@ make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
  * find_placeholder_info
  *		Fetch the PlaceHolderInfo for the given PHV
  *
- * If the PlaceHolderInfo doesn't exist yet, create it if create_new_ph is
- * true, else throw an error.
+ * If the PlaceHolderInfo doesn't exist yet, create it if we haven't yet
+ * frozen the set of PlaceHolderInfos for the query; else throw an error.
  *
  * This is separate from make_placeholder_expr because subquery pullup has
  * to make PlaceHolderVars for expressions that might not be used at all in
@@ -61,30 +61,30 @@ make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
  * We build PlaceHolderInfos only for PHVs that are still present in the
  * simplified query passed to query_planner().
  *
- * Note: this should only be called after query_planner() has started.  Also,
- * create_new_ph must not be true after deconstruct_jointree begins, because
- * make_outerjoininfo assumes that we already know about all placeholders.
+ * Note: this should only be called after query_planner() has started.
  */
 PlaceHolderInfo *
-find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
-					  bool create_new_ph)
+find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
 {
 	PlaceHolderInfo *phinfo;
 	Relids		rels_used;
-	ListCell   *lc;
 
 	/* if this ever isn't true, we'd need to be able to look in parent lists */
 	Assert(phv->phlevelsup == 0);
 
-	foreach(lc, root->placeholder_list)
+	/* Use placeholder_array to look up existing PlaceHolderInfo quickly */
+	if (phv->phid < root->placeholder_array_size)
+		phinfo = root->placeholder_array[phv->phid];
+	else
+		phinfo = NULL;
+	if (phinfo != NULL)
 	{
-		phinfo = (PlaceHolderInfo *) lfirst(lc);
-		if (phinfo->phid == phv->phid)
-			return phinfo;
+		Assert(phinfo->phid == phv->phid);
+		return phinfo;
 	}
 
 	/* Not found, so create it */
-	if (!create_new_ph)
+	if (root->placeholdersFrozen)
 		elog(ERROR, "too late to create a new PlaceHolderInfo");
 
 	phinfo = makeNode(PlaceHolderInfo);
@@ -115,8 +115,32 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 	phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
 									   exprTypmod((Node *) phv->phexpr));
 
+	/* Add to placeholder_list and placeholder_array */
 	root->placeholder_list = lappend(root->placeholder_list, phinfo);
 
+	if (phinfo->phid >= root->placeholder_array_size)
+	{
+		/* Must allocate or enlarge placeholder_array */
+		int			new_size;
+
+		new_size = root->placeholder_array_size ? root->placeholder_array_size * 2 : 8;
+		while (phinfo->phid >= new_size)
+			new_size *= 2;
+		if (root->placeholder_array)
+		{
+			root->placeholder_array = (PlaceHolderInfo **)
+				repalloc(root->placeholder_array,
+						 sizeof(PlaceHolderInfo *) * new_size);
+			MemSet(root->placeholder_array + root->placeholder_array_size, 0,
+				   sizeof(PlaceHolderInfo *) * (new_size - root->placeholder_array_size));
+		}
+		else
+			root->placeholder_array = (PlaceHolderInfo **)
+				palloc0(new_size * sizeof(PlaceHolderInfo *));
+		root->placeholder_array_size = new_size;
+	}
+	root->placeholder_array[phinfo->phid] = phinfo;
+
 	/*
 	 * The PHV's contained expression may contain other, lower-level PHVs.  We
 	 * now know we need to get those into the PlaceHolderInfo list, too, so we
@@ -133,16 +157,13 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
  *
  * We don't need to look at the targetlist because build_base_rel_tlists()
  * will already have made entries for any PHVs in the tlist.
- *
- * This is called before we begin deconstruct_jointree.  Once we begin
- * deconstruct_jointree, all active placeholders must be present in
- * root->placeholder_list, because make_outerjoininfo and
- * update_placeholder_eval_levels require this info to be available
- * while we crawl up the join tree.
  */
 void
 find_placeholders_in_jointree(PlannerInfo *root)
 {
+	/* This must be done before freezing the set of PHIs */
+	Assert(!root->placeholdersFrozen);
+
 	/* We need do nothing if the query contains no PlaceHolderVars */
 	if (root->glob->lastPHId != 0)
 	{
@@ -232,7 +253,7 @@ find_placeholders_in_expr(PlannerInfo *root, Node *expr)
 			continue;
 
 		/* Create a PlaceHolderInfo entry if there's not one already */
-		(void) find_placeholder_info(root, phv, true);
+		(void) find_placeholder_info(root, phv);
 	}
 	list_free(vars);
 }
@@ -359,7 +380,7 @@ fix_placeholder_input_needed_levels(PlannerInfo *root)
 										   PVC_RECURSE_WINDOWFUNCS |
 										   PVC_INCLUDE_PLACEHOLDERS);
 
-		add_vars_to_targetlist(root, vars, phinfo->ph_eval_at, false);
+		add_vars_to_targetlist(root, vars, phinfo->ph_eval_at);
 		list_free(vars);
 	}
 }
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 442c12acef..13e36dd0e1 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -990,7 +990,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 		if (IsA(var, PlaceHolderVar))
 		{
 			PlaceHolderVar *phv = (PlaceHolderVar *) var;
-			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv, false);
+			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
 
 			/* Is it still needed above this joinrel? */
 			if (bms_nonempty_difference(phinfo->ph_needed, relids))
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index ebc6ce84b0..7db86c39ef 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -210,15 +210,8 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
 
 			if (phv->phlevelsup == 0)
 			{
-				ListCell   *lc;
-
-				foreach(lc, context->root->placeholder_list)
-				{
-					phinfo = (PlaceHolderInfo *) lfirst(lc);
-					if (phinfo->phid == phv->phid)
-						break;
-					phinfo = NULL;
-				}
+				if (phv->phid < context->root->placeholder_array_size)
+					phinfo = context->root->placeholder_array[phv->phid];
 			}
 			if (phinfo == NULL)
 			{
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3b065139e6..bdc7b50db9 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -357,6 +357,11 @@ struct PlannerInfo
 	/* list of PlaceHolderInfos */
 	List	   *placeholder_list;
 
+	/* array of PlaceHolderInfos indexed by phid */
+	struct PlaceHolderInfo **placeholder_array pg_node_attr(read_write_ignore, array_size(placeholder_array_size));
+	/* allocated size of array */
+	int			placeholder_array_size pg_node_attr(read_write_ignore);
+
 	/* list of ForeignKeyOptInfos */
 	List	   *fkey_list;
 
@@ -449,6 +454,8 @@ struct PlannerInfo
 	bool		hasPseudoConstantQuals;
 	/* true if we've made any of those */
 	bool		hasAlternativeSubPlans;
+	/* true once we're no longer allowed to add PlaceHolderInfos */
+	bool		placeholdersFrozen;
 	/* true if planning a recursive WITH item */
 	bool		hasRecursion;
 
diff --git a/src/include/optimizer/placeholder.h b/src/include/optimizer/placeholder.h
index 39803ea41f..507dbc6175 100644
--- a/src/include/optimizer/placeholder.h
+++ b/src/include/optimizer/placeholder.h
@@ -20,7 +20,7 @@
 extern PlaceHolderVar *make_placeholder_expr(PlannerInfo *root, Expr *expr,
 											 Relids phrels);
 extern PlaceHolderInfo *find_placeholder_info(PlannerInfo *root,
-											  PlaceHolderVar *phv, bool create_new_ph);
+											  PlaceHolderVar *phv);
 extern void find_placeholders_in_jointree(PlannerInfo *root);
 extern void update_placeholder_eval_levels(PlannerInfo *root,
 										   SpecialJoinInfo *new_sjinfo);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index c4f61c1a09..1566f435b3 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -71,7 +71,7 @@ extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
 extern void add_other_rels_to_query(PlannerInfo *root);
 extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
 extern void add_vars_to_targetlist(PlannerInfo *root, List *vars,
-								   Relids where_needed, bool create_new_ph);
+								   Relids where_needed);
 extern void find_lateral_references(PlannerInfo *root);
 extern void create_lateral_join_info(PlannerInfo *root);
 extern List *deconstruct_jointree(PlannerInfo *root);