Make PlaceHolderInfo lookup O(1).

Up to now we've just searched the placeholder_list when we want to
find the PlaceHolderInfo with a given ID.  While there's no evidence
of that being a problem in the field, an upcoming patch will add
find_placeholder_info() calls in build_joinrel_tlist(), which seems
likely to make it more of an issue: a joinrel emitting lots of
PlaceHolderVars would incur O(N^2) cost, and we might be building
a lot of joinrels in complex queries.  Hence, add an array that
can be indexed directly by phid to make the lookups constant-time.

Discussion: https://postgr.es/m/1405792.1660677844@sss.pgh.pa.us

1 files changed, 38 insertions, 5 deletions

diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 3b0f0584f01..0184e6d36c1 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -71,16 +71,19 @@ 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 */
@@ -115,8 +118,38 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 	phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
 									   exprTypmod((Node *) phv->phexpr));
 
+	/*
+	 * Add to both placeholder_list and placeholder_array.  Note: because we
+	 * store pointers to the PlaceHolderInfos in two data structures, it'd be
+	 * unsafe to pass the whole placeholder_list structure through
+	 * expression_tree_mutator or the like --- or at least, you'd have to
+	 * rebuild the placeholder_array afterwards.
+	 */
 	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