LCOV - code coverage report
Current view: top level - src/backend/optimizer/util - placeholder.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 115 120 95.8 %
Date: 2019-09-22 08:06:49 Functions: 9 9 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-2019, 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             : /* Local functions */
      27             : static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
      28             : static void find_placeholders_in_expr(PlannerInfo *root, Node *expr);
      29             : 
      30             : 
      31             : /*
      32             :  * make_placeholder_expr
      33             :  *      Make a PlaceHolderVar for the given expression.
      34             :  *
      35             :  * phrels is the syntactic location (as a set of baserels) to attribute
      36             :  * to the expression.
      37             :  */
      38             : PlaceHolderVar *
      39         640 : make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
      40             : {
      41         640 :     PlaceHolderVar *phv = makeNode(PlaceHolderVar);
      42             : 
      43         640 :     phv->phexpr = expr;
      44         640 :     phv->phrels = phrels;
      45         640 :     phv->phid = ++(root->glob->lastPHId);
      46         640 :     phv->phlevelsup = 0;
      47             : 
      48         640 :     return phv;
      49             : }
      50             : 
      51             : /*
      52             :  * find_placeholder_info
      53             :  *      Fetch the PlaceHolderInfo for the given PHV
      54             :  *
      55             :  * If the PlaceHolderInfo doesn't exist yet, create it if create_new_ph is
      56             :  * true, else throw an error.
      57             :  *
      58             :  * This is separate from make_placeholder_expr because subquery pullup has
      59             :  * to make PlaceHolderVars for expressions that might not be used at all in
      60             :  * the upper query, or might not remain after const-expression simplification.
      61             :  * We build PlaceHolderInfos only for PHVs that are still present in the
      62             :  * simplified query passed to query_planner().
      63             :  *
      64             :  * Note: this should only be called after query_planner() has started.  Also,
      65             :  * create_new_ph must not be true after deconstruct_jointree begins, because
      66             :  * make_outerjoininfo assumes that we already know about all placeholders.
      67             :  */
      68             : PlaceHolderInfo *
      69        1532 : find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
      70             :                       bool create_new_ph)
      71             : {
      72             :     PlaceHolderInfo *phinfo;
      73             :     Relids      rels_used;
      74             :     ListCell   *lc;
      75             : 
      76             :     /* if this ever isn't true, we'd need to be able to look in parent lists */
      77             :     Assert(phv->phlevelsup == 0);
      78             : 
      79        2140 :     foreach(lc, root->placeholder_list)
      80             :     {
      81        1688 :         phinfo = (PlaceHolderInfo *) lfirst(lc);
      82        1688 :         if (phinfo->phid == phv->phid)
      83        1080 :             return phinfo;
      84             :     }
      85             : 
      86             :     /* Not found, so create it */
      87         452 :     if (!create_new_ph)
      88           0 :         elog(ERROR, "too late to create a new PlaceHolderInfo");
      89             : 
      90         452 :     phinfo = makeNode(PlaceHolderInfo);
      91             : 
      92         452 :     phinfo->phid = phv->phid;
      93         452 :     phinfo->ph_var = copyObject(phv);
      94             : 
      95             :     /*
      96             :      * Any referenced rels that are outside the PHV's syntactic scope are
      97             :      * LATERAL references, which should be included in ph_lateral but not in
      98             :      * ph_eval_at.  If no referenced rels are within the syntactic scope,
      99             :      * force evaluation at the syntactic location.
     100             :      */
     101         452 :     rels_used = pull_varnos((Node *) phv->phexpr);
     102         452 :     phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
     103         452 :     if (bms_is_empty(phinfo->ph_lateral))
     104         376 :         phinfo->ph_lateral = NULL;   /* make it exactly NULL if empty */
     105         452 :     phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
     106             :     /* If no contained vars, force evaluation at syntactic location */
     107         452 :     if (bms_is_empty(phinfo->ph_eval_at))
     108             :     {
     109         280 :         phinfo->ph_eval_at = bms_copy(phv->phrels);
     110             :         Assert(!bms_is_empty(phinfo->ph_eval_at));
     111             :     }
     112             :     /* ph_eval_at may change later, see update_placeholder_eval_levels */
     113         452 :     phinfo->ph_needed = NULL;    /* initially it's unused */
     114             :     /* for the moment, estimate width using just the datatype info */
     115         452 :     phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
     116         452 :                                        exprTypmod((Node *) phv->phexpr));
     117             : 
     118         452 :     root->placeholder_list = lappend(root->placeholder_list, phinfo);
     119             : 
     120             :     /*
     121             :      * The PHV's contained expression may contain other, lower-level PHVs.  We
     122             :      * now know we need to get those into the PlaceHolderInfo list, too, so we
     123             :      * may as well do that immediately.
     124             :      */
     125         452 :     find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
     126             : 
     127         452 :     return phinfo;
     128             : }
     129             : 
     130             : /*
     131             :  * find_placeholders_in_jointree
     132             :  *      Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
     133             :  *
     134             :  * We don't need to look at the targetlist because build_base_rel_tlists()
     135             :  * will already have made entries for any PHVs in the tlist.
     136             :  *
     137             :  * This is called before we begin deconstruct_jointree.  Once we begin
     138             :  * deconstruct_jointree, all active placeholders must be present in
     139             :  * root->placeholder_list, because make_outerjoininfo and
     140             :  * update_placeholder_eval_levels require this info to be available
     141             :  * while we crawl up the join tree.
     142             :  */
     143             : void
     144      187136 : find_placeholders_in_jointree(PlannerInfo *root)
     145             : {
     146             :     /* We need do nothing if the query contains no PlaceHolderVars */
     147      187136 :     if (root->glob->lastPHId != 0)
     148             :     {
     149             :         /* Start recursion at top of jointree */
     150             :         Assert(root->parse->jointree != NULL &&
     151             :                IsA(root->parse->jointree, FromExpr));
     152         424 :         find_placeholders_recurse(root, (Node *) root->parse->jointree);
     153             :     }
     154      187136 : }
     155             : 
     156             : /*
     157             :  * find_placeholders_recurse
     158             :  *    One recursion level of find_placeholders_in_jointree.
     159             :  *
     160             :  * jtnode is the current jointree node to examine.
     161             :  */
     162             : static void
     163        2672 : find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
     164             : {
     165        2672 :     if (jtnode == NULL)
     166           0 :         return;
     167        2672 :     if (IsA(jtnode, RangeTblRef))
     168             :     {
     169             :         /* No quals to deal with here */
     170             :     }
     171        1376 :     else if (IsA(jtnode, FromExpr))
     172             :     {
     173         572 :         FromExpr   *f = (FromExpr *) jtnode;
     174             :         ListCell   *l;
     175             : 
     176             :         /*
     177             :          * First, recurse to handle child joins.
     178             :          */
     179        1212 :         foreach(l, f->fromlist)
     180             :         {
     181         640 :             find_placeholders_recurse(root, lfirst(l));
     182             :         }
     183             : 
     184             :         /*
     185             :          * Now process the top-level quals.
     186             :          */
     187         572 :         find_placeholders_in_expr(root, f->quals);
     188             :     }
     189         804 :     else if (IsA(jtnode, JoinExpr))
     190             :     {
     191         804 :         JoinExpr   *j = (JoinExpr *) jtnode;
     192             : 
     193             :         /*
     194             :          * First, recurse to handle child joins.
     195             :          */
     196         804 :         find_placeholders_recurse(root, j->larg);
     197         804 :         find_placeholders_recurse(root, j->rarg);
     198             : 
     199             :         /* Process the qual clauses */
     200         804 :         find_placeholders_in_expr(root, j->quals);
     201             :     }
     202             :     else
     203           0 :         elog(ERROR, "unrecognized node type: %d",
     204             :              (int) nodeTag(jtnode));
     205             : }
     206             : 
     207             : /*
     208             :  * find_placeholders_in_expr
     209             :  *      Find all PlaceHolderVars in the given expression, and create
     210             :  *      PlaceHolderInfo entries for them.
     211             :  */
     212             : static void
     213        1828 : find_placeholders_in_expr(PlannerInfo *root, Node *expr)
     214             : {
     215             :     List       *vars;
     216             :     ListCell   *vl;
     217             : 
     218             :     /*
     219             :      * pull_var_clause does more than we need here, but it'll do and it's
     220             :      * convenient to use.
     221             :      */
     222        1828 :     vars = pull_var_clause(expr,
     223             :                            PVC_RECURSE_AGGREGATES |
     224             :                            PVC_RECURSE_WINDOWFUNCS |
     225             :                            PVC_INCLUDE_PLACEHOLDERS);
     226        4048 :     foreach(vl, vars)
     227             :     {
     228        2220 :         PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
     229             : 
     230             :         /* Ignore any plain Vars */
     231        2220 :         if (!IsA(phv, PlaceHolderVar))
     232        1984 :             continue;
     233             : 
     234             :         /* Create a PlaceHolderInfo entry if there's not one already */
     235         236 :         (void) find_placeholder_info(root, phv, true);
     236             :     }
     237        1828 :     list_free(vars);
     238        1828 : }
     239             : 
     240             : /*
     241             :  * update_placeholder_eval_levels
     242             :  *      Adjust the target evaluation levels for placeholders
     243             :  *
     244             :  * The initial eval_at level set by find_placeholder_info was the set of
     245             :  * rels used in the placeholder's expression (or the whole subselect below
     246             :  * the placeholder's syntactic location, if the expr is variable-free).
     247             :  * If the query contains any outer joins that can null any of those rels,
     248             :  * we must delay evaluation to above those joins.
     249             :  *
     250             :  * We repeat this operation each time we add another outer join to
     251             :  * root->join_info_list.  It's somewhat annoying to have to do that, but
     252             :  * since we don't have very much information on the placeholders' locations,
     253             :  * it's hard to avoid.  Each placeholder's eval_at level must be correct
     254             :  * by the time it starts to figure in outer-join delay decisions for higher
     255             :  * outer joins.
     256             :  *
     257             :  * In future we might want to put additional policy/heuristics here to
     258             :  * try to determine an optimal evaluation level.  The current rules will
     259             :  * result in evaluation at the lowest possible level.  However, pushing a
     260             :  * placeholder eval up the tree is likely to further constrain evaluation
     261             :  * order for outer joins, so it could easily be counterproductive; and we
     262             :  * don't have enough information at this point to make an intelligent choice.
     263             :  */
     264             : void
     265       42686 : update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
     266             : {
     267             :     ListCell   *lc1;
     268             : 
     269       43310 :     foreach(lc1, root->placeholder_list)
     270             :     {
     271         624 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
     272         624 :         Relids      syn_level = phinfo->ph_var->phrels;
     273             :         Relids      eval_at;
     274             :         bool        found_some;
     275             :         ListCell   *lc2;
     276             : 
     277             :         /*
     278             :          * We don't need to do any work on this placeholder unless the
     279             :          * newly-added outer join is syntactically beneath its location.
     280             :          */
     281         746 :         if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
     282         122 :             !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
     283         544 :             continue;
     284             : 
     285             :         /*
     286             :          * Check for delays due to lower outer joins.  This is the same logic
     287             :          * as in check_outerjoin_delay in initsplan.c, except that we don't
     288             :          * have anything to do with the delay_upper_joins flags; delay of
     289             :          * upper outer joins will be handled later, based on the eval_at
     290             :          * values we compute now.
     291             :          */
     292          80 :         eval_at = phinfo->ph_eval_at;
     293             : 
     294             :         do
     295             :         {
     296         108 :             found_some = false;
     297         240 :             foreach(lc2, root->join_info_list)
     298             :             {
     299         132 :                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
     300             : 
     301             :                 /* disregard joins not within the PHV's sub-select */
     302         264 :                 if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
     303         132 :                     !bms_is_subset(sjinfo->syn_righthand, syn_level))
     304           0 :                     continue;
     305             : 
     306             :                 /* do we reference any nullable rels of this OJ? */
     307         140 :                 if (bms_overlap(eval_at, sjinfo->min_righthand) ||
     308           8 :                     (sjinfo->jointype == JOIN_FULL &&
     309           0 :                      bms_overlap(eval_at, sjinfo->min_lefthand)))
     310             :                 {
     311             :                     /* yes; have we included all its rels in eval_at? */
     312         220 :                     if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
     313          96 :                         !bms_is_subset(sjinfo->min_righthand, eval_at))
     314             :                     {
     315             :                         /* no, so add them in */
     316          28 :                         eval_at = bms_add_members(eval_at,
     317          28 :                                                   sjinfo->min_lefthand);
     318          28 :                         eval_at = bms_add_members(eval_at,
     319          28 :                                                   sjinfo->min_righthand);
     320             :                         /* we'll need another iteration */
     321          28 :                         found_some = true;
     322             :                     }
     323             :                 }
     324             :             }
     325         108 :         } while (found_some);
     326             : 
     327             :         /* Can't move the PHV's eval_at level to above its syntactic level */
     328             :         Assert(bms_is_subset(eval_at, syn_level));
     329             : 
     330          80 :         phinfo->ph_eval_at = eval_at;
     331             :     }
     332       42686 : }
     333             : 
     334             : /*
     335             :  * fix_placeholder_input_needed_levels
     336             :  *      Adjust the "needed at" levels for placeholder inputs
     337             :  *
     338             :  * This is called after we've finished determining the eval_at levels for
     339             :  * all placeholders.  We need to make sure that all vars and placeholders
     340             :  * needed to evaluate each placeholder will be available at the scan or join
     341             :  * level where the evaluation will be done.  (It might seem that scan-level
     342             :  * evaluations aren't interesting, but that's not so: a LATERAL reference
     343             :  * within a placeholder's expression needs to cause the referenced var or
     344             :  * placeholder to be marked as needed in the scan where it's evaluated.)
     345             :  * Note that this loop can have side-effects on the ph_needed sets of other
     346             :  * PlaceHolderInfos; that's okay because we don't examine ph_needed here, so
     347             :  * there are no ordering issues to worry about.
     348             :  */
     349             : void
     350      187136 : fix_placeholder_input_needed_levels(PlannerInfo *root)
     351             : {
     352             :     ListCell   *lc;
     353             : 
     354      187588 :     foreach(lc, root->placeholder_list)
     355             :     {
     356         452 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     357         452 :         List       *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
     358             :                                            PVC_RECURSE_AGGREGATES |
     359             :                                            PVC_RECURSE_WINDOWFUNCS |
     360             :                                            PVC_INCLUDE_PLACEHOLDERS);
     361             : 
     362         452 :         add_vars_to_targetlist(root, vars, phinfo->ph_eval_at, false);
     363         452 :         list_free(vars);
     364             :     }
     365      187136 : }
     366             : 
     367             : /*
     368             :  * add_placeholders_to_base_rels
     369             :  *      Add any required PlaceHolderVars to base rels' targetlists.
     370             :  *
     371             :  * If any placeholder can be computed at a base rel and is needed above it,
     372             :  * add it to that rel's targetlist.  This might look like it could be merged
     373             :  * with fix_placeholder_input_needed_levels, but it must be separate because
     374             :  * join removal happens in between, and can change the ph_eval_at sets.  There
     375             :  * is essentially the same logic in add_placeholders_to_joinrel, but we can't
     376             :  * do that part until joinrels are formed.
     377             :  */
     378             : void
     379      187136 : add_placeholders_to_base_rels(PlannerInfo *root)
     380             : {
     381             :     ListCell   *lc;
     382             : 
     383      187584 :     foreach(lc, root->placeholder_list)
     384             :     {
     385         448 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     386         448 :         Relids      eval_at = phinfo->ph_eval_at;
     387             :         int         varno;
     388             : 
     389         752 :         if (bms_get_singleton_member(eval_at, &varno) &&
     390         304 :             bms_nonempty_difference(phinfo->ph_needed, eval_at))
     391             :         {
     392         296 :             RelOptInfo *rel = find_base_rel(root, varno);
     393             : 
     394         592 :             rel->reltarget->exprs = lappend(rel->reltarget->exprs,
     395         296 :                                             copyObject(phinfo->ph_var));
     396             :             /* reltarget's cost and width fields will be updated later */
     397             :         }
     398             :     }
     399      187136 : }
     400             : 
     401             : /*
     402             :  * add_placeholders_to_joinrel
     403             :  *      Add any required PlaceHolderVars to a join rel's targetlist;
     404             :  *      and if they contain lateral references, add those references to the
     405             :  *      joinrel's direct_lateral_relids.
     406             :  *
     407             :  * A join rel should emit a PlaceHolderVar if (a) the PHV is needed above
     408             :  * this join level and (b) the PHV can be computed at or below this level.
     409             :  */
     410             : void
     411       93180 : add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
     412             :                             RelOptInfo *outer_rel, RelOptInfo *inner_rel)
     413             : {
     414       93180 :     Relids      relids = joinrel->relids;
     415             :     ListCell   *lc;
     416             : 
     417       94792 :     foreach(lc, root->placeholder_list)
     418             :     {
     419        1612 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     420             : 
     421             :         /* Is it still needed above this joinrel? */
     422        1612 :         if (bms_nonempty_difference(phinfo->ph_needed, relids))
     423             :         {
     424             :             /* Is it computable here? */
     425        1184 :             if (bms_is_subset(phinfo->ph_eval_at, relids))
     426             :             {
     427             :                 /* Yup, add it to the output */
     428        1504 :                 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
     429         752 :                                                     phinfo->ph_var);
     430         752 :                 joinrel->reltarget->width += phinfo->ph_width;
     431             : 
     432             :                 /*
     433             :                  * Charge the cost of evaluating the contained expression if
     434             :                  * the PHV can be computed here but not in either input.  This
     435             :                  * is a bit bogus because we make the decision based on the
     436             :                  * first pair of possible input relations considered for the
     437             :                  * joinrel.  With other pairs, it might be possible to compute
     438             :                  * the PHV in one input or the other, and then we'd be double
     439             :                  * charging the PHV's cost for some join paths.  For now, live
     440             :                  * with that; but we might want to improve it later by
     441             :                  * refiguring the reltarget costs for each pair of inputs.
     442             :                  */
     443        1350 :                 if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
     444         598 :                     !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
     445             :                 {
     446             :                     QualCost    cost;
     447             : 
     448         196 :                     cost_qual_eval_node(&cost, (Node *) phinfo->ph_var->phexpr,
     449             :                                         root);
     450         196 :                     joinrel->reltarget->cost.startup += cost.startup;
     451         196 :                     joinrel->reltarget->cost.per_tuple += cost.per_tuple;
     452             :                 }
     453             : 
     454             :                 /* Adjust joinrel's direct_lateral_relids as needed */
     455         752 :                 joinrel->direct_lateral_relids =
     456         752 :                     bms_add_members(joinrel->direct_lateral_relids,
     457         752 :                                     phinfo->ph_lateral);
     458             :             }
     459             :         }
     460             :     }
     461       93180 : }

Generated by: LCOV version 1.13