Header And Logo

PostgreSQL
| The world's most advanced open source database.

placeholder.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * placeholder.c
00004  *    PlaceHolderVar and PlaceHolderInfo manipulation routines
00005  *
00006  *
00007  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00008  * Portions Copyright (c) 1994, Regents of the University of California
00009  *
00010  *
00011  * IDENTIFICATION
00012  *    src/backend/optimizer/util/placeholder.c
00013  *
00014  *-------------------------------------------------------------------------
00015  */
00016 #include "postgres.h"
00017 
00018 #include "nodes/nodeFuncs.h"
00019 #include "optimizer/pathnode.h"
00020 #include "optimizer/placeholder.h"
00021 #include "optimizer/planmain.h"
00022 #include "optimizer/var.h"
00023 #include "utils/lsyscache.h"
00024 
00025 /* Local functions */
00026 static Relids find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
00027 static void mark_placeholders_in_expr(PlannerInfo *root, Node *expr,
00028                           Relids relids);
00029 
00030 
00031 /*
00032  * make_placeholder_expr
00033  *      Make a PlaceHolderVar for the given expression.
00034  *
00035  * phrels is the syntactic location (as a set of baserels) to attribute
00036  * to the expression.
00037  */
00038 PlaceHolderVar *
00039 make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
00040 {
00041     PlaceHolderVar *phv = makeNode(PlaceHolderVar);
00042 
00043     phv->phexpr = expr;
00044     phv->phrels = phrels;
00045     phv->phid = ++(root->glob->lastPHId);
00046     phv->phlevelsup = 0;
00047 
00048     return phv;
00049 }
00050 
00051 /*
00052  * find_placeholder_info
00053  *      Fetch the PlaceHolderInfo for the given PHV
00054  *
00055  * If the PlaceHolderInfo doesn't exist yet, create it if create_new_ph is
00056  * true, else throw an error.
00057  *
00058  * This is separate from make_placeholder_expr because subquery pullup has
00059  * to make PlaceHolderVars for expressions that might not be used at all in
00060  * the upper query, or might not remain after const-expression simplification.
00061  * We build PlaceHolderInfos only for PHVs that are still present in the
00062  * simplified query passed to query_planner().
00063  *
00064  * Note: this should only be called after query_planner() has started.  Also,
00065  * create_new_ph must not be TRUE after deconstruct_jointree begins, because
00066  * make_outerjoininfo assumes that we already know about all placeholders.
00067  */
00068 PlaceHolderInfo *
00069 find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
00070                       bool create_new_ph)
00071 {
00072     PlaceHolderInfo *phinfo;
00073     ListCell   *lc;
00074 
00075     /* if this ever isn't true, we'd need to be able to look in parent lists */
00076     Assert(phv->phlevelsup == 0);
00077 
00078     foreach(lc, root->placeholder_list)
00079     {
00080         phinfo = (PlaceHolderInfo *) lfirst(lc);
00081         if (phinfo->phid == phv->phid)
00082             return phinfo;
00083     }
00084 
00085     /* Not found, so create it */
00086     if (!create_new_ph)
00087         elog(ERROR, "too late to create a new PlaceHolderInfo");
00088 
00089     phinfo = makeNode(PlaceHolderInfo);
00090 
00091     phinfo->phid = phv->phid;
00092     phinfo->ph_var = copyObject(phv);
00093     phinfo->ph_eval_at = pull_varnos((Node *) phv);
00094     /* ph_eval_at may change later, see update_placeholder_eval_levels */
00095     phinfo->ph_needed = NULL;   /* initially it's unused */
00096     phinfo->ph_may_need = NULL;
00097     /* for the moment, estimate width using just the datatype info */
00098     phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
00099                                        exprTypmod((Node *) phv->phexpr));
00100 
00101     root->placeholder_list = lappend(root->placeholder_list, phinfo);
00102 
00103     return phinfo;
00104 }
00105 
00106 /*
00107  * find_placeholders_in_jointree
00108  *      Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
00109  *
00110  * We don't need to look at the targetlist because build_base_rel_tlists()
00111  * will already have made entries for any PHVs in the tlist.
00112  */
00113 void
00114 find_placeholders_in_jointree(PlannerInfo *root)
00115 {
00116     /* We need do nothing if the query contains no PlaceHolderVars */
00117     if (root->glob->lastPHId != 0)
00118     {
00119         /* Start recursion at top of jointree */
00120         Assert(root->parse->jointree != NULL &&
00121                IsA(root->parse->jointree, FromExpr));
00122         (void) find_placeholders_recurse(root, (Node *) root->parse->jointree);
00123     }
00124 }
00125 
00126 /*
00127  * find_placeholders_recurse
00128  *    One recursion level of find_placeholders_in_jointree.
00129  *
00130  * jtnode is the current jointree node to examine.
00131  *
00132  * The result is the set of base Relids contained in or below jtnode.
00133  * This is just an internal convenience, it's not used at the top level.
00134  */
00135 static Relids
00136 find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
00137 {
00138     Relids      jtrelids;
00139 
00140     if (jtnode == NULL)
00141         return NULL;
00142     if (IsA(jtnode, RangeTblRef))
00143     {
00144         int         varno = ((RangeTblRef *) jtnode)->rtindex;
00145 
00146         /* No quals to deal with, just return correct result */
00147         jtrelids = bms_make_singleton(varno);
00148     }
00149     else if (IsA(jtnode, FromExpr))
00150     {
00151         FromExpr   *f = (FromExpr *) jtnode;
00152         ListCell   *l;
00153 
00154         /*
00155          * First, recurse to handle child joins, and form their relid set.
00156          */
00157         jtrelids = NULL;
00158         foreach(l, f->fromlist)
00159         {
00160             Relids      sub_relids;
00161 
00162             sub_relids = find_placeholders_recurse(root, lfirst(l));
00163             jtrelids = bms_join(jtrelids, sub_relids);
00164         }
00165 
00166         /*
00167          * Now process the top-level quals.
00168          */
00169         mark_placeholders_in_expr(root, f->quals, jtrelids);
00170     }
00171     else if (IsA(jtnode, JoinExpr))
00172     {
00173         JoinExpr   *j = (JoinExpr *) jtnode;
00174         Relids      leftids,
00175                     rightids;
00176 
00177         /*
00178          * First, recurse to handle child joins, and form their relid set.
00179          */
00180         leftids = find_placeholders_recurse(root, j->larg);
00181         rightids = find_placeholders_recurse(root, j->rarg);
00182         jtrelids = bms_join(leftids, rightids);
00183 
00184         /* Process the qual clauses */
00185         mark_placeholders_in_expr(root, j->quals, jtrelids);
00186     }
00187     else
00188     {
00189         elog(ERROR, "unrecognized node type: %d",
00190              (int) nodeTag(jtnode));
00191         jtrelids = NULL;        /* keep compiler quiet */
00192     }
00193     return jtrelids;
00194 }
00195 
00196 /*
00197  * mark_placeholders_in_expr
00198  *      Find all PlaceHolderVars in the given expression, and mark them
00199  *      as possibly needed at the specified join level.
00200  *
00201  * relids is the syntactic join level to mark as the "maybe needed" level
00202  * for each PlaceHolderVar found in the expression.
00203  */
00204 static void
00205 mark_placeholders_in_expr(PlannerInfo *root, Node *expr, Relids relids)
00206 {
00207     List       *vars;
00208     ListCell   *vl;
00209 
00210     /*
00211      * pull_var_clause does more than we need here, but it'll do and it's
00212      * convenient to use.
00213      */
00214     vars = pull_var_clause(expr,
00215                            PVC_RECURSE_AGGREGATES,
00216                            PVC_INCLUDE_PLACEHOLDERS);
00217     foreach(vl, vars)
00218     {
00219         PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
00220         PlaceHolderInfo *phinfo;
00221 
00222         /* Ignore any plain Vars */
00223         if (!IsA(phv, PlaceHolderVar))
00224             continue;
00225 
00226         /* Create a PlaceHolderInfo entry if there's not one already */
00227         phinfo = find_placeholder_info(root, phv, true);
00228 
00229         /* Mark it, and recursively process any contained placeholders */
00230         mark_placeholder_maybe_needed(root, phinfo, relids);
00231     }
00232     list_free(vars);
00233 }
00234 
00235 /*
00236  * mark_placeholder_maybe_needed
00237  *      Mark a placeholder as possibly needed at the specified join level.
00238  *
00239  * relids is the syntactic join level to mark as the "maybe needed" level
00240  * for the placeholder.
00241  *
00242  * This is called during an initial scan of the query's targetlist and quals
00243  * before we begin deconstruct_jointree.  Once we begin deconstruct_jointree,
00244  * all active placeholders must be present in root->placeholder_list with
00245  * their correct ph_may_need values, because make_outerjoininfo and
00246  * update_placeholder_eval_levels require this info to be available while
00247  * we crawl up the join tree.
00248  */
00249 void
00250 mark_placeholder_maybe_needed(PlannerInfo *root, PlaceHolderInfo *phinfo,
00251                               Relids relids)
00252 {
00253     Relids      est_eval_level;
00254 
00255     /* Mark the PHV as possibly needed at the given syntactic level */
00256     phinfo->ph_may_need = bms_add_members(phinfo->ph_may_need, relids);
00257 
00258     /*
00259      * This is a bit tricky: the PHV's contained expression may contain other,
00260      * lower-level PHVs.  We need to get those into the PlaceHolderInfo list,
00261      * but they aren't going to be needed where the outer PHV is referenced.
00262      * Rather, they'll be needed where the outer PHV is evaluated.  We can
00263      * estimate that conservatively as the syntactic location of the PHV's
00264      * expression, but not less than the level of any Vars it contains.
00265      * (Normally the Vars would come from below the syntactic location anyway,
00266      * but this might not be true if the PHV contains any LATERAL references.)
00267      */
00268     est_eval_level = bms_union(phinfo->ph_var->phrels, phinfo->ph_eval_at);
00269 
00270     /* Now recurse to take care of any such PHVs */
00271     mark_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr,
00272                               est_eval_level);
00273 
00274     bms_free(est_eval_level);
00275 }
00276 
00277 /*
00278  * update_placeholder_eval_levels
00279  *      Adjust the target evaluation levels for placeholders
00280  *
00281  * The initial eval_at level set by find_placeholder_info was the set of
00282  * rels used in the placeholder's expression (or the whole subselect below
00283  * the placeholder's syntactic location, if the expr is variable-free).
00284  * If the subselect contains any outer joins that can null any of those rels,
00285  * we must delay evaluation to above those joins.
00286  *
00287  * We repeat this operation each time we add another outer join to
00288  * root->join_info_list.  It's somewhat annoying to have to do that, but
00289  * since we don't have very much information on the placeholders' locations,
00290  * it's hard to avoid.  Each placeholder's eval_at level must be correct
00291  * by the time it starts to figure in outer-join delay decisions for higher
00292  * outer joins.
00293  *
00294  * In future we might want to put additional policy/heuristics here to
00295  * try to determine an optimal evaluation level.  The current rules will
00296  * result in evaluation at the lowest possible level.  However, pushing a
00297  * placeholder eval up the tree is likely to further constrain evaluation
00298  * order for outer joins, so it could easily be counterproductive; and we
00299  * don't have enough information at this point to make an intelligent choice.
00300  */
00301 void
00302 update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
00303 {
00304     ListCell   *lc1;
00305 
00306     foreach(lc1, root->placeholder_list)
00307     {
00308         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
00309         Relids      syn_level = phinfo->ph_var->phrels;
00310         Relids      eval_at;
00311         bool        found_some;
00312         ListCell   *lc2;
00313 
00314         /*
00315          * We don't need to do any work on this placeholder unless the
00316          * newly-added outer join is syntactically beneath its location.
00317          */
00318         if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
00319             !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
00320             continue;
00321 
00322         /*
00323          * Check for delays due to lower outer joins.  This is the same logic
00324          * as in check_outerjoin_delay in initsplan.c, except that we don't
00325          * have anything to do with the delay_upper_joins flags; delay of
00326          * upper outer joins will be handled later, based on the eval_at
00327          * values we compute now.
00328          */
00329         eval_at = phinfo->ph_eval_at;
00330 
00331         do
00332         {
00333             found_some = false;
00334             foreach(lc2, root->join_info_list)
00335             {
00336                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
00337 
00338                 /* disregard joins not within the PHV's sub-select */
00339                 if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
00340                     !bms_is_subset(sjinfo->syn_righthand, syn_level))
00341                     continue;
00342 
00343                 /* do we reference any nullable rels of this OJ? */
00344                 if (bms_overlap(eval_at, sjinfo->min_righthand) ||
00345                     (sjinfo->jointype == JOIN_FULL &&
00346                      bms_overlap(eval_at, sjinfo->min_lefthand)))
00347                 {
00348                     /* yes; have we included all its rels in eval_at? */
00349                     if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
00350                         !bms_is_subset(sjinfo->min_righthand, eval_at))
00351                     {
00352                         /* no, so add them in */
00353                         eval_at = bms_add_members(eval_at,
00354                                                   sjinfo->min_lefthand);
00355                         eval_at = bms_add_members(eval_at,
00356                                                   sjinfo->min_righthand);
00357                         /* we'll need another iteration */
00358                         found_some = true;
00359                     }
00360                 }
00361             }
00362         } while (found_some);
00363 
00364         phinfo->ph_eval_at = eval_at;
00365     }
00366 }
00367 
00368 /*
00369  * fix_placeholder_input_needed_levels
00370  *      Adjust the "needed at" levels for placeholder inputs
00371  *
00372  * This is called after we've finished determining the eval_at levels for
00373  * all placeholders.  We need to make sure that all vars and placeholders
00374  * needed to evaluate each placeholder will be available at the join level
00375  * where the evaluation will be done.  Note that this loop can have
00376  * side-effects on the ph_needed sets of other PlaceHolderInfos; that's okay
00377  * because we don't examine ph_needed here, so there are no ordering issues
00378  * to worry about.
00379  */
00380 void
00381 fix_placeholder_input_needed_levels(PlannerInfo *root)
00382 {
00383     ListCell   *lc;
00384 
00385     foreach(lc, root->placeholder_list)
00386     {
00387         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
00388         Relids      eval_at = phinfo->ph_eval_at;
00389 
00390         /* No work unless it'll be evaluated above baserel level */
00391         if (bms_membership(eval_at) == BMS_MULTIPLE)
00392         {
00393             List       *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
00394                                                PVC_RECURSE_AGGREGATES,
00395                                                PVC_INCLUDE_PLACEHOLDERS);
00396 
00397             add_vars_to_targetlist(root, vars, eval_at, false);
00398             list_free(vars);
00399         }
00400     }
00401 }
00402 
00403 /*
00404  * add_placeholders_to_base_rels
00405  *      Add any required PlaceHolderVars to base rels' targetlists.
00406  *
00407  * If any placeholder can be computed at a base rel and is needed above it,
00408  * add it to that rel's targetlist.  This might look like it could be merged
00409  * with fix_placeholder_input_needed_levels, but it must be separate because
00410  * join removal happens in between, and can change the ph_eval_at sets.  There
00411  * is essentially the same logic in add_placeholders_to_joinrel, but we can't
00412  * do that part until joinrels are formed.
00413  */
00414 void
00415 add_placeholders_to_base_rels(PlannerInfo *root)
00416 {
00417     ListCell   *lc;
00418 
00419     foreach(lc, root->placeholder_list)
00420     {
00421         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
00422         Relids      eval_at = phinfo->ph_eval_at;
00423 
00424         if (bms_membership(eval_at) == BMS_SINGLETON &&
00425             bms_nonempty_difference(phinfo->ph_needed, eval_at))
00426         {
00427             int         varno = bms_singleton_member(eval_at);
00428             RelOptInfo *rel = find_base_rel(root, varno);
00429 
00430             rel->reltargetlist = lappend(rel->reltargetlist,
00431                                          copyObject(phinfo->ph_var));
00432         }
00433     }
00434 }
00435 
00436 /*
00437  * add_placeholders_to_joinrel
00438  *      Add any required PlaceHolderVars to a join rel's targetlist.
00439  *
00440  * A join rel should emit a PlaceHolderVar if (a) the PHV is needed above
00441  * this join level and (b) the PHV can be computed at or below this level.
00442  * At this time we do not need to distinguish whether the PHV will be
00443  * computed here or copied up from below.
00444  */
00445 void
00446 add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel)
00447 {
00448     Relids      relids = joinrel->relids;
00449     ListCell   *lc;
00450 
00451     foreach(lc, root->placeholder_list)
00452     {
00453         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
00454 
00455         /* Is it still needed above this joinrel? */
00456         if (bms_nonempty_difference(phinfo->ph_needed, relids))
00457         {
00458             /* Is it computable here? */
00459             if (bms_is_subset(phinfo->ph_eval_at, relids))
00460             {
00461                 /* Yup, add it to the output */
00462                 joinrel->reltargetlist = lappend(joinrel->reltargetlist,
00463                                                  phinfo->ph_var);
00464                 joinrel->width += phinfo->ph_width;
00465             }
00466         }
00467     }
00468 }