Re: Making Vars outer-join aware - Mailing list pgsql-hackers

I wrote:
> ... We can fix
> that by adding an index array to go straight from phid to the
> PlaceHolderInfo.  While thinking about where to construct such
> an index array, I decided it'd be a good idea to have an explicit
> step to "freeze" the set of PlaceHolderInfos, at the start of
> deconstruct_jointree.

On further thought, it seems better to maintain the index array
from the start, allowing complete replacement of the linear list
searches.  We can add a separate bool flag to denote frozen-ness.
This does have minor downsides:

* Some fiddly code is needed to enlarge the index array at need.
But it's not different from that for, say, simple_rel_array.

* If we ever have a need to mutate the placeholder_list as a whole,
we'd have to reconstruct the index array to point to the new
objects.  We don't do that at present, except in one place in
analyzejoins.c, which is easily fixed.  While the same argument
could be raised against the v1 patch, it's not very likely that
we'd be doing such mutation beyond the start of deconstruct_jointree.

Hence, see v2 attached.

            regards, tom lane

diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 3b0f0584f0..f0e8cd9965 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -400,14 +400,16 @@ add_placeholders_to_base_rels(PlannerInfo *root)

 /*
  * add_placeholders_to_joinrel
- *        Add any required PlaceHolderVars to a join rel's targetlist;
- *        and if they contain lateral references, add those references to the
- *        joinrel's direct_lateral_relids.
+ *        Add any newly-computable PlaceHolderVars to a join rel's targetlist;
+ *        and if computable PHVs contain lateral references, add those
+ *        references to the joinrel's direct_lateral_relids.
  *
  * A join rel should emit a PlaceHolderVar if (a) the PHV can be computed
  * at or below this join level and (b) the PHV is needed above this level.
- * However, condition (a) is sufficient to add to direct_lateral_relids,
- * as explained below.
+ * Our caller build_join_rel() has already added any PHVs that were computed
+ * in either join input rel, so we need add only newly-computable ones to
+ * the targetlist.  However, direct_lateral_relids must be updated for every
+ * PHV computable at or below this join, as explained below.
  */
 void
 add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
@@ -426,13 +428,10 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
             /* Is it still needed above this joinrel? */
             if (bms_nonempty_difference(phinfo->ph_needed, relids))
             {
-                /* Yup, add it to the output */
-                joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
-                                                    phinfo->ph_var);
-                joinrel->reltarget->width += phinfo->ph_width;
-
                 /*
-                 * Charge the cost of evaluating the contained expression if
+                 * Yes, but only add to tlist if it wasn't computed in either
+                 * input; otherwise it should be there already.  Also, we
+                 * charge the cost of evaluating the contained expression if
                  * the PHV can be computed here but not in either input.  This
                  * is a bit bogus because we make the decision based on the
                  * first pair of possible input relations considered for the
@@ -445,12 +444,15 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
                 if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
                     !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
                 {
+                    PlaceHolderVar *phv = phinfo->ph_var;
                     QualCost    cost;

-                    cost_qual_eval_node(&cost, (Node *) phinfo->ph_var->phexpr,
-                                        root);
+                    joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
+                                                        phv);
+                    cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
                     joinrel->reltarget->cost.startup += cost.startup;
                     joinrel->reltarget->cost.per_tuple += cost.per_tuple;
+                    joinrel->reltarget->width += phinfo->ph_width;
                 }
             }

diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 520409f4ba..442c12acef 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -688,6 +688,8 @@ build_join_rel(PlannerInfo *root,
      */
     build_joinrel_tlist(root, joinrel, outer_rel);
     build_joinrel_tlist(root, joinrel, inner_rel);
+
+    /* Add any newly-computable PlaceHolderVars, too */
     add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel);

     /*
@@ -966,6 +968,7 @@ min_join_parameterization(PlannerInfo *root,
  * The join's targetlist includes all Vars of its member relations that
  * will still be needed above the join.  This subroutine adds all such
  * Vars from the specified input rel's tlist to the join rel's tlist.
+ * Likewise for any PlaceHolderVars emitted by the input rel.
  *
  * We also compute the expected width of the join's output, making use
  * of data that was cached at the baserel level by set_rel_width().
@@ -982,11 +985,24 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
         Var           *var = (Var *) lfirst(vars);

         /*
-         * Ignore PlaceHolderVars in the input tlists; we'll make our own
-         * decisions about whether to copy them.
+         * For a PlaceHolderVar, we have to look up the PlaceHolderInfo.
          */
         if (IsA(var, PlaceHolderVar))
+        {
+            PlaceHolderVar *phv = (PlaceHolderVar *) var;
+            PlaceHolderInfo *phinfo = find_placeholder_info(root, phv, false);
+
+            /* Is it still needed above this joinrel? */
+            if (bms_nonempty_difference(phinfo->ph_needed, relids))
+            {
+                /* Yup, add it to the output */
+                joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
+                                                    phv);
+                /* Bubbling up the precomputed result has cost zero */
+                joinrel->reltarget->width += phinfo->ph_width;
+            }
             continue;
+        }

         /*
          * Otherwise, anything in a baserel or joinrel targetlist ought to be
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index b9853af2dc..2ed2e542a4 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5793,10 +5793,10 @@ select * from
  Nested Loop
    Output: c.q1, c.q2, a.q1, a.q2, b.q1, (COALESCE(b.q2, '42'::bigint)), d.q1, (COALESCE((COALESCE(b.q2,
'42'::bigint)),d.q2)), ((COALESCE((COALESCE(b.q2, '42'::bigint)), d.q2))) 
    ->  Hash Right Join
-         Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, (COALESCE(b.q2, '42'::bigint)), (COALESCE((COALESCE(b.q2,
'42'::bigint)),d.q2)) 
+         Output: c.q1, c.q2, a.q1, a.q2, b.q1, (COALESCE(b.q2, '42'::bigint)), d.q1, (COALESCE((COALESCE(b.q2,
'42'::bigint)),d.q2)) 
          Hash Cond: (d.q1 = c.q2)
          ->  Nested Loop
-               Output: a.q1, a.q2, b.q1, d.q1, (COALESCE(b.q2, '42'::bigint)), (COALESCE((COALESCE(b.q2,
'42'::bigint)),d.q2)) 
+               Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, '42'::bigint)), d.q1, (COALESCE((COALESCE(b.q2,
'42'::bigint)),d.q2)) 
                ->  Hash Left Join
                      Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, '42'::bigint))
                      Hash Cond: (a.q2 = b.q1)
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);