LCOV - code coverage report
Current view: top level - src/backend/optimizer/util - placeholder.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 118 128 92.2 %
Date: 2024-07-19 16:11:31 Functions: 10 10 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * placeholder.c
       4             :  *    PlaceHolderVar and PlaceHolderInfo manipulation routines
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  *
      11             :  * IDENTIFICATION
      12             :  *    src/backend/optimizer/util/placeholder.c
      13             :  *
      14             :  *-------------------------------------------------------------------------
      15             :  */
      16             : #include "postgres.h"
      17             : 
      18             : #include "nodes/nodeFuncs.h"
      19             : #include "optimizer/cost.h"
      20             : #include "optimizer/optimizer.h"
      21             : #include "optimizer/pathnode.h"
      22             : #include "optimizer/placeholder.h"
      23             : #include "optimizer/planmain.h"
      24             : #include "utils/lsyscache.h"
      25             : 
      26             : 
      27             : typedef struct contain_placeholder_references_context
      28             : {
      29             :     int         relid;
      30             :     int         sublevels_up;
      31             : } contain_placeholder_references_context;
      32             : 
      33             : /* Local functions */
      34             : static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
      35             : static void find_placeholders_in_expr(PlannerInfo *root, Node *expr);
      36             : static bool contain_placeholder_references_walker(Node *node,
      37             :                                                   contain_placeholder_references_context *context);
      38             : 
      39             : 
      40             : /*
      41             :  * make_placeholder_expr
      42             :  *      Make a PlaceHolderVar for the given expression.
      43             :  *
      44             :  * phrels is the syntactic location (as a set of relids) to attribute
      45             :  * to the expression.
      46             :  *
      47             :  * The caller is responsible for adjusting phlevelsup and phnullingrels
      48             :  * as needed.  Because we do not know here which query level the PHV
      49             :  * will be associated with, it's important that this function touches
      50             :  * only root->glob; messing with other parts of PlannerInfo would be
      51             :  * likely to do the wrong thing.
      52             :  */
      53             : PlaceHolderVar *
      54        1608 : make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
      55             : {
      56        1608 :     PlaceHolderVar *phv = makeNode(PlaceHolderVar);
      57             : 
      58        1608 :     phv->phexpr = expr;
      59        1608 :     phv->phrels = phrels;
      60        1608 :     phv->phnullingrels = NULL;   /* caller may change this later */
      61        1608 :     phv->phid = ++(root->glob->lastPHId);
      62        1608 :     phv->phlevelsup = 0;     /* caller may change this later */
      63             : 
      64        1608 :     return phv;
      65             : }
      66             : 
      67             : /*
      68             :  * find_placeholder_info
      69             :  *      Fetch the PlaceHolderInfo for the given PHV
      70             :  *
      71             :  * If the PlaceHolderInfo doesn't exist yet, create it if we haven't yet
      72             :  * frozen the set of PlaceHolderInfos for the query; else throw an error.
      73             :  *
      74             :  * This is separate from make_placeholder_expr because subquery pullup has
      75             :  * to make PlaceHolderVars for expressions that might not be used at all in
      76             :  * the upper query, or might not remain after const-expression simplification.
      77             :  * We build PlaceHolderInfos only for PHVs that are still present in the
      78             :  * simplified query passed to query_planner().
      79             :  *
      80             :  * Note: this should only be called after query_planner() has started.
      81             :  */
      82             : PlaceHolderInfo *
      83        6260 : find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
      84             : {
      85             :     PlaceHolderInfo *phinfo;
      86             :     Relids      rels_used;
      87             : 
      88             :     /* if this ever isn't true, we'd need to be able to look in parent lists */
      89             :     Assert(phv->phlevelsup == 0);
      90             : 
      91             :     /* Use placeholder_array to look up existing PlaceHolderInfo quickly */
      92        6260 :     if (phv->phid < root->placeholder_array_size)
      93        5368 :         phinfo = root->placeholder_array[phv->phid];
      94             :     else
      95         892 :         phinfo = NULL;
      96        6260 :     if (phinfo != NULL)
      97             :     {
      98             :         Assert(phinfo->phid == phv->phid);
      99        5084 :         return phinfo;
     100             :     }
     101             : 
     102             :     /* Not found, so create it */
     103        1176 :     if (root->placeholdersFrozen)
     104           0 :         elog(ERROR, "too late to create a new PlaceHolderInfo");
     105             : 
     106        1176 :     phinfo = makeNode(PlaceHolderInfo);
     107             : 
     108        1176 :     phinfo->phid = phv->phid;
     109        1176 :     phinfo->ph_var = copyObject(phv);
     110             : 
     111             :     /*
     112             :      * By convention, phinfo->ph_var->phnullingrels is always empty, since the
     113             :      * PlaceHolderInfo represents the initially-calculated state of the
     114             :      * PlaceHolderVar.  PlaceHolderVars appearing in the query tree might have
     115             :      * varying values of phnullingrels, reflecting outer joins applied above
     116             :      * the calculation level.
     117             :      */
     118        1176 :     phinfo->ph_var->phnullingrels = NULL;
     119             : 
     120             :     /*
     121             :      * Any referenced rels that are outside the PHV's syntactic scope are
     122             :      * LATERAL references, which should be included in ph_lateral but not in
     123             :      * ph_eval_at.  If no referenced rels are within the syntactic scope,
     124             :      * force evaluation at the syntactic location.
     125             :      */
     126        1176 :     rels_used = pull_varnos(root, (Node *) phv->phexpr);
     127        1176 :     phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
     128        1176 :     phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
     129             :     /* If no contained vars, force evaluation at syntactic location */
     130        1176 :     if (bms_is_empty(phinfo->ph_eval_at))
     131             :     {
     132         864 :         phinfo->ph_eval_at = bms_copy(phv->phrels);
     133             :         Assert(!bms_is_empty(phinfo->ph_eval_at));
     134             :     }
     135        1176 :     phinfo->ph_needed = NULL;    /* initially it's unused */
     136             :     /* for the moment, estimate width using just the datatype info */
     137        1176 :     phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
     138        1176 :                                        exprTypmod((Node *) phv->phexpr));
     139             : 
     140             :     /*
     141             :      * Add to both placeholder_list and placeholder_array.  Note: because we
     142             :      * store pointers to the PlaceHolderInfos in two data structures, it'd be
     143             :      * unsafe to pass the whole placeholder_list structure through
     144             :      * expression_tree_mutator or the like --- or at least, you'd have to
     145             :      * rebuild the placeholder_array afterwards.
     146             :      */
     147        1176 :     root->placeholder_list = lappend(root->placeholder_list, phinfo);
     148             : 
     149        1176 :     if (phinfo->phid >= root->placeholder_array_size)
     150             :     {
     151             :         /* Must allocate or enlarge placeholder_array */
     152             :         int         new_size;
     153             : 
     154         892 :         new_size = root->placeholder_array_size ? root->placeholder_array_size * 2 : 8;
     155         892 :         while (phinfo->phid >= new_size)
     156           0 :             new_size *= 2;
     157         892 :         if (root->placeholder_array)
     158           0 :             root->placeholder_array =
     159           0 :                 repalloc0_array(root->placeholder_array, PlaceHolderInfo *, root->placeholder_array_size, new_size);
     160             :         else
     161         892 :             root->placeholder_array =
     162         892 :                 palloc0_array(PlaceHolderInfo *, new_size);
     163         892 :         root->placeholder_array_size = new_size;
     164             :     }
     165        1176 :     root->placeholder_array[phinfo->phid] = phinfo;
     166             : 
     167             :     /*
     168             :      * The PHV's contained expression may contain other, lower-level PHVs.  We
     169             :      * now know we need to get those into the PlaceHolderInfo list, too, so we
     170             :      * may as well do that immediately.
     171             :      */
     172        1176 :     find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
     173             : 
     174        1176 :     return phinfo;
     175             : }
     176             : 
     177             : /*
     178             :  * find_placeholders_in_jointree
     179             :  *      Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
     180             :  *
     181             :  * We don't need to look at the targetlist because build_base_rel_tlists()
     182             :  * will already have made entries for any PHVs in the tlist.
     183             :  */
     184             : void
     185      275226 : find_placeholders_in_jointree(PlannerInfo *root)
     186             : {
     187             :     /* This must be done before freezing the set of PHIs */
     188             :     Assert(!root->placeholdersFrozen);
     189             : 
     190             :     /* We need do nothing if the query contains no PlaceHolderVars */
     191      275226 :     if (root->glob->lastPHId != 0)
     192             :     {
     193             :         /* Start recursion at top of jointree */
     194             :         Assert(root->parse->jointree != NULL &&
     195             :                IsA(root->parse->jointree, FromExpr));
     196        1224 :         find_placeholders_recurse(root, (Node *) root->parse->jointree);
     197             :     }
     198      275226 : }
     199             : 
     200             : /*
     201             :  * find_placeholders_recurse
     202             :  *    One recursion level of find_placeholders_in_jointree.
     203             :  *
     204             :  * jtnode is the current jointree node to examine.
     205             :  */
     206             : static void
     207        6550 : find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
     208             : {
     209        6550 :     if (jtnode == NULL)
     210           0 :         return;
     211        6550 :     if (IsA(jtnode, RangeTblRef))
     212             :     {
     213             :         /* No quals to deal with here */
     214             :     }
     215        3296 :     else if (IsA(jtnode, FromExpr))
     216             :     {
     217        1444 :         FromExpr   *f = (FromExpr *) jtnode;
     218             :         ListCell   *l;
     219             : 
     220             :         /*
     221             :          * First, recurse to handle child joins.
     222             :          */
     223        3066 :         foreach(l, f->fromlist)
     224             :         {
     225        1622 :             find_placeholders_recurse(root, lfirst(l));
     226             :         }
     227             : 
     228             :         /*
     229             :          * Now process the top-level quals.
     230             :          */
     231        1444 :         find_placeholders_in_expr(root, f->quals);
     232             :     }
     233        1852 :     else if (IsA(jtnode, JoinExpr))
     234             :     {
     235        1852 :         JoinExpr   *j = (JoinExpr *) jtnode;
     236             : 
     237             :         /*
     238             :          * First, recurse to handle child joins.
     239             :          */
     240        1852 :         find_placeholders_recurse(root, j->larg);
     241        1852 :         find_placeholders_recurse(root, j->rarg);
     242             : 
     243             :         /* Process the qual clauses */
     244        1852 :         find_placeholders_in_expr(root, j->quals);
     245             :     }
     246             :     else
     247           0 :         elog(ERROR, "unrecognized node type: %d",
     248             :              (int) nodeTag(jtnode));
     249             : }
     250             : 
     251             : /*
     252             :  * find_placeholders_in_expr
     253             :  *      Find all PlaceHolderVars in the given expression, and create
     254             :  *      PlaceHolderInfo entries for them.
     255             :  */
     256             : static void
     257        4472 : find_placeholders_in_expr(PlannerInfo *root, Node *expr)
     258             : {
     259             :     List       *vars;
     260             :     ListCell   *vl;
     261             : 
     262             :     /*
     263             :      * pull_var_clause does more than we need here, but it'll do and it's
     264             :      * convenient to use.
     265             :      */
     266        4472 :     vars = pull_var_clause(expr,
     267             :                            PVC_RECURSE_AGGREGATES |
     268             :                            PVC_RECURSE_WINDOWFUNCS |
     269             :                            PVC_INCLUDE_PLACEHOLDERS);
     270        9658 :     foreach(vl, vars)
     271             :     {
     272        5186 :         PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
     273             : 
     274             :         /* Ignore any plain Vars */
     275        5186 :         if (!IsA(phv, PlaceHolderVar))
     276        4518 :             continue;
     277             : 
     278             :         /* Create a PlaceHolderInfo entry if there's not one already */
     279         668 :         (void) find_placeholder_info(root, phv);
     280             :     }
     281        4472 :     list_free(vars);
     282        4472 : }
     283             : 
     284             : /*
     285             :  * fix_placeholder_input_needed_levels
     286             :  *      Adjust the "needed at" levels for placeholder inputs
     287             :  *
     288             :  * This is called after we've finished determining the eval_at levels for
     289             :  * all placeholders.  We need to make sure that all vars and placeholders
     290             :  * needed to evaluate each placeholder will be available at the scan or join
     291             :  * level where the evaluation will be done.  (It might seem that scan-level
     292             :  * evaluations aren't interesting, but that's not so: a LATERAL reference
     293             :  * within a placeholder's expression needs to cause the referenced var or
     294             :  * placeholder to be marked as needed in the scan where it's evaluated.)
     295             :  * Note that this loop can have side-effects on the ph_needed sets of other
     296             :  * PlaceHolderInfos; that's okay because we don't examine ph_needed here, so
     297             :  * there are no ordering issues to worry about.
     298             :  */
     299             : void
     300      275226 : fix_placeholder_input_needed_levels(PlannerInfo *root)
     301             : {
     302             :     ListCell   *lc;
     303             : 
     304      276402 :     foreach(lc, root->placeholder_list)
     305             :     {
     306        1176 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     307        1176 :         List       *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
     308             :                                            PVC_RECURSE_AGGREGATES |
     309             :                                            PVC_RECURSE_WINDOWFUNCS |
     310             :                                            PVC_INCLUDE_PLACEHOLDERS);
     311             : 
     312        1176 :         add_vars_to_targetlist(root, vars, phinfo->ph_eval_at);
     313        1176 :         list_free(vars);
     314             :     }
     315      275226 : }
     316             : 
     317             : /*
     318             :  * add_placeholders_to_base_rels
     319             :  *      Add any required PlaceHolderVars to base rels' targetlists.
     320             :  *
     321             :  * If any placeholder can be computed at a base rel and is needed above it,
     322             :  * add it to that rel's targetlist.  This might look like it could be merged
     323             :  * with fix_placeholder_input_needed_levels, but it must be separate because
     324             :  * join removal happens in between, and can change the ph_eval_at sets.  There
     325             :  * is essentially the same logic in add_placeholders_to_joinrel, but we can't
     326             :  * do that part until joinrels are formed.
     327             :  */
     328             : void
     329      275226 : add_placeholders_to_base_rels(PlannerInfo *root)
     330             : {
     331             :     ListCell   *lc;
     332             : 
     333      276396 :     foreach(lc, root->placeholder_list)
     334             :     {
     335        1170 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     336        1170 :         Relids      eval_at = phinfo->ph_eval_at;
     337             :         int         varno;
     338             : 
     339        2012 :         if (bms_get_singleton_member(eval_at, &varno) &&
     340         842 :             bms_nonempty_difference(phinfo->ph_needed, eval_at))
     341             :         {
     342         776 :             RelOptInfo *rel = find_base_rel(root, varno);
     343             : 
     344             :             /*
     345             :              * As in add_vars_to_targetlist(), a value computed at scan level
     346             :              * has not yet been nulled by any outer join, so its phnullingrels
     347             :              * should be empty.
     348             :              */
     349             :             Assert(phinfo->ph_var->phnullingrels == NULL);
     350             : 
     351             :             /* Copying the PHV might be unnecessary here, but be safe */
     352         776 :             rel->reltarget->exprs = lappend(rel->reltarget->exprs,
     353         776 :                                             copyObject(phinfo->ph_var));
     354             :             /* reltarget's cost and width fields will be updated later */
     355             :         }
     356             :     }
     357      275226 : }
     358             : 
     359             : /*
     360             :  * add_placeholders_to_joinrel
     361             :  *      Add any newly-computable PlaceHolderVars to a join rel's targetlist;
     362             :  *      and if computable PHVs contain lateral references, add those
     363             :  *      references to the joinrel's direct_lateral_relids.
     364             :  *
     365             :  * A join rel should emit a PlaceHolderVar if (a) the PHV can be computed
     366             :  * at or below this join level and (b) the PHV is needed above this level.
     367             :  * Our caller build_join_rel() has already added any PHVs that were computed
     368             :  * in either join input rel, so we need add only newly-computable ones to
     369             :  * the targetlist.  However, direct_lateral_relids must be updated for every
     370             :  * PHV computable at or below this join, as explained below.
     371             :  */
     372             : void
     373      166600 : add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
     374             :                             RelOptInfo *outer_rel, RelOptInfo *inner_rel,
     375             :                             SpecialJoinInfo *sjinfo)
     376             : {
     377      166600 :     Relids      relids = joinrel->relids;
     378      166600 :     int64       tuple_width = joinrel->reltarget->width;
     379             :     ListCell   *lc;
     380             : 
     381      170372 :     foreach(lc, root->placeholder_list)
     382             :     {
     383        3772 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     384             : 
     385             :         /* Is it computable here? */
     386        3772 :         if (bms_is_subset(phinfo->ph_eval_at, relids))
     387             :         {
     388             :             /* Is it still needed above this joinrel? */
     389        2594 :             if (bms_nonempty_difference(phinfo->ph_needed, relids))
     390             :             {
     391             :                 /*
     392             :                  * Yes, but only add to tlist if it wasn't computed in either
     393             :                  * input; otherwise it should be there already.  Also, we
     394             :                  * charge the cost of evaluating the contained expression if
     395             :                  * the PHV can be computed here but not in either input.  This
     396             :                  * is a bit bogus because we make the decision based on the
     397             :                  * first pair of possible input relations considered for the
     398             :                  * joinrel.  With other pairs, it might be possible to compute
     399             :                  * the PHV in one input or the other, and then we'd be double
     400             :                  * charging the PHV's cost for some join paths.  For now, live
     401             :                  * with that; but we might want to improve it later by
     402             :                  * refiguring the reltarget costs for each pair of inputs.
     403             :                  */
     404        1656 :                 if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
     405        1174 :                     !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
     406             :                 {
     407             :                     /* Copying might be unnecessary here, but be safe */
     408         368 :                     PlaceHolderVar *phv = copyObject(phinfo->ph_var);
     409             :                     QualCost    cost;
     410             : 
     411             :                     /*
     412             :                      * It'll start out not nulled by anything.  Joins above
     413             :                      * this one might add to its phnullingrels later, in much
     414             :                      * the same way as for Vars.
     415             :                      */
     416             :                     Assert(phv->phnullingrels == NULL);
     417             : 
     418         368 :                     joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
     419             :                                                         phv);
     420         368 :                     cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
     421         368 :                     joinrel->reltarget->cost.startup += cost.startup;
     422         368 :                     joinrel->reltarget->cost.per_tuple += cost.per_tuple;
     423         368 :                     tuple_width += phinfo->ph_width;
     424             :                 }
     425             :             }
     426             : 
     427             :             /*
     428             :              * Also adjust joinrel's direct_lateral_relids to include the
     429             :              * PHV's source rel(s).  We must do this even if we're not
     430             :              * actually going to emit the PHV, otherwise join_is_legal() will
     431             :              * reject valid join orderings.  (In principle maybe we could
     432             :              * instead remove the joinrel's lateral_relids dependency; but
     433             :              * that's complicated to get right, and cases where we're not
     434             :              * going to emit the PHV are too rare to justify the work.)
     435             :              *
     436             :              * In principle we should only do this if the join doesn't yet
     437             :              * include the PHV's source rel(s).  But our caller
     438             :              * build_join_rel() will clean things up by removing the join's
     439             :              * own relids from its direct_lateral_relids, so we needn't
     440             :              * account for that here.
     441             :              */
     442        2594 :             joinrel->direct_lateral_relids =
     443        2594 :                 bms_add_members(joinrel->direct_lateral_relids,
     444        2594 :                                 phinfo->ph_lateral);
     445             :         }
     446             :     }
     447             : 
     448      166600 :     joinrel->reltarget->width = clamp_width_est(tuple_width);
     449      166600 : }
     450             : 
     451             : /*
     452             :  * contain_placeholder_references_to
     453             :  *      Detect whether any PlaceHolderVars in the given clause contain
     454             :  *      references to the given relid (typically an OJ relid).
     455             :  *
     456             :  * "Contain" means that there's a use of the relid inside the PHV's
     457             :  * contained expression, so that changing the nullability status of
     458             :  * the rel might change what the PHV computes.
     459             :  *
     460             :  * The code here to cope with upper-level PHVs is likely dead, but keep it
     461             :  * anyway just in case.
     462             :  */
     463             : bool
     464       13446 : contain_placeholder_references_to(PlannerInfo *root, Node *clause,
     465             :                                   int relid)
     466             : {
     467             :     contain_placeholder_references_context context;
     468             : 
     469             :     /* We can answer quickly in the common case that there's no PHVs at all */
     470       13446 :     if (root->glob->lastPHId == 0)
     471       12844 :         return false;
     472             :     /* Else run the recursive search */
     473         602 :     context.relid = relid;
     474         602 :     context.sublevels_up = 0;
     475         602 :     return contain_placeholder_references_walker(clause, &context);
     476             : }
     477             : 
     478             : static bool
     479        2108 : contain_placeholder_references_walker(Node *node,
     480             :                                       contain_placeholder_references_context *context)
     481             : {
     482        2108 :     if (node == NULL)
     483         102 :         return false;
     484        2006 :     if (IsA(node, PlaceHolderVar))
     485             :     {
     486          42 :         PlaceHolderVar *phv = (PlaceHolderVar *) node;
     487             : 
     488             :         /* We should just look through PHVs of other query levels */
     489          42 :         if (phv->phlevelsup == context->sublevels_up)
     490             :         {
     491             :             /* If phrels matches, we found what we came for */
     492          42 :             if (bms_is_member(context->relid, phv->phrels))
     493          12 :                 return true;
     494             : 
     495             :             /*
     496             :              * We should not examine phnullingrels: what we are looking for is
     497             :              * references in the contained expression, not OJs that might null
     498             :              * the result afterwards.  Also, we don't need to recurse into the
     499             :              * contained expression, because phrels should adequately
     500             :              * summarize what's in there.  So we're done here.
     501             :              */
     502          30 :             return false;
     503             :         }
     504             :     }
     505        1964 :     else if (IsA(node, Query))
     506             :     {
     507             :         /* Recurse into RTE subquery or not-yet-planned sublink subquery */
     508             :         bool        result;
     509             : 
     510           0 :         context->sublevels_up++;
     511           0 :         result = query_tree_walker((Query *) node,
     512             :                                    contain_placeholder_references_walker,
     513             :                                    context,
     514             :                                    0);
     515           0 :         context->sublevels_up--;
     516           0 :         return result;
     517             :     }
     518        1964 :     return expression_tree_walker(node, contain_placeholder_references_walker,
     519             :                                   context);
     520             : }

Generated by: LCOV version 1.14