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/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..1867a097fd 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.
+	 */
+	freeze_placeholder_set(root);
+
 	/* 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/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..e34402523d 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,13 +61,10 @@ 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;
@@ -76,6 +73,23 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 	/* if this ever isn't true, we'd need to be able to look in parent lists */
 	Assert(phv->phlevelsup == 0);
 
+	/* Use the index array if it exists */
+	if (root->placeholder_array != NULL)
+	{
+		if (phv->phid < root->placeholder_array_size)
+			phinfo = root->placeholder_array[phv->phid];
+		else
+			phinfo = NULL;
+		if (phinfo != NULL)
+		{
+			Assert(phinfo->phid == phv->phid);
+			return phinfo;
+		}
+		/* Existence of the array means we've frozen the PHI set */
+		elog(ERROR, "too late to create a new PlaceHolderInfo");
+	}
+
+	/* Otherwise, find it the hard way in placeholder_list */
 	foreach(lc, root->placeholder_list)
 	{
 		phinfo = (PlaceHolderInfo *) lfirst(lc);
@@ -84,9 +98,6 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 	}
 
 	/* Not found, so create it */
-	if (!create_new_ph)
-		elog(ERROR, "too late to create a new PlaceHolderInfo");
-
 	phinfo = makeNode(PlaceHolderInfo);
 
 	phinfo->phid = phv->phid;
@@ -133,16 +144,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->placeholder_array == NULL);
+
 	/* We need do nothing if the query contains no PlaceHolderVars */
 	if (root->glob->lastPHId != 0)
 	{
@@ -232,11 +240,37 @@ 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);
 }
 
+/*
+ * freeze_placeholder_set
+ *		Mark that no more PlaceHolderInfos may be created for this query
+ *
+ * We do this by creating an index array root->placeholder_array[],
+ * which also serves to speed up future find_placeholder_info() lookups.
+ */
+void
+freeze_placeholder_set(PlannerInfo *root)
+{
+	ListCell   *lc;
+
+	/* The global lastPHId may be an overestimate, but it's safe */
+	root->placeholder_array_size = root->glob->lastPHId + 1;
+	root->placeholder_array = (PlaceHolderInfo **)
+		palloc0(root->placeholder_array_size * sizeof(PlaceHolderInfo *));
+
+	foreach(lc, root->placeholder_list)
+	{
+		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
+
+		Assert(phinfo->phid < root->placeholder_array_size);
+		root->placeholder_array[phinfo->phid] = phinfo;
+	}
+}
+
 /*
  * update_placeholder_eval_levels
  *		Adjust the target evaluation levels for placeholders
@@ -359,7 +393,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..ee915546ac 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -212,6 +212,7 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
 			{
 				ListCell   *lc;
 
+				/* can't rely on placeholder_array[] yet */
 				foreach(lc, context->root->placeholder_list)
 				{
 					phinfo = (PlaceHolderInfo *) lfirst(lc);
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3b065139e6..4c8fe28bfc 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -357,6 +357,15 @@ struct PlannerInfo
 	/* list of PlaceHolderInfos */
 	List	   *placeholder_list;
 
+	/*
+	 * array of PlaceHolderInfos indexed by phid.  We create this in
+	 * freeze_placeholder_set(); it serves both to speed up later lookups by
+	 * phid, and to signal that no more PlaceHolderInfos can be made.
+	 */
+	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;
 
diff --git a/src/include/optimizer/placeholder.h b/src/include/optimizer/placeholder.h
index 39803ea41f..a5153c707b 100644
--- a/src/include/optimizer/placeholder.h
+++ b/src/include/optimizer/placeholder.h
@@ -20,8 +20,9 @@
 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 freeze_placeholder_set(PlannerInfo *root);
 extern void update_placeholder_eval_levels(PlannerInfo *root,
 										   SpecialJoinInfo *new_sjinfo);
 extern void fix_placeholder_input_needed_levels(PlannerInfo *root);
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);