granicus.if.org Git - postgresql/blob - src/backend/optimizer/util/placeholder.c

   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/pathnode.h"
  21 #include "optimizer/placeholder.h"
  22 #include "optimizer/planmain.h"
  23 #include "optimizer/var.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 make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
  40 {
  41         PlaceHolderVar *phv = makeNode(PlaceHolderVar);
  42
  43         phv->phexpr = expr;
  44         phv->phrels = phrels;
  45         phv->phid = ++(root->glob->lastPHId);
  46         phv->phlevelsup = 0;
  47
  48         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 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         foreach(lc, root->placeholder_list)
  80         {
  81                 phinfo = (PlaceHolderInfo *) lfirst(lc);
  82                 if (phinfo->phid == phv->phid)
  83                         return phinfo;
  84         }
  85
  86         /* Not found, so create it */
  87         if (!create_new_ph)
  88                 elog(ERROR, "too late to create a new PlaceHolderInfo");
  89
  90         phinfo = makeNode(PlaceHolderInfo);
  91
  92         phinfo->phid = phv->phid;
  93         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         rels_used = pull_varnos((Node *) phv->phexpr);
 102         phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
 103         if (bms_is_empty(phinfo->ph_lateral))
 104                 phinfo->ph_lateral = NULL;      /* make it exactly NULL if empty */
 105         phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
 106         /* If no contained vars, force evaluation at syntactic location */
 107         if (bms_is_empty(phinfo->ph_eval_at))
 108         {
 109                 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         phinfo->ph_needed = NULL;       /* initially it's unused */
 114         /* for the moment, estimate width using just the datatype info */
 115         phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
 116                                                                            exprTypmod((Node *) phv->phexpr));
 117
 118         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         find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
 126
 127         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 find_placeholders_in_jointree(PlannerInfo *root)
 145 {
 146         /* We need do nothing if the query contains no PlaceHolderVars */
 147         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                 find_placeholders_recurse(root, (Node *) root->parse->jointree);
 153         }
 154 }
 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 find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
 164 {
 165         if (jtnode == NULL)
 166                 return;
 167         if (IsA(jtnode, RangeTblRef))
 168         {
 169                 /* No quals to deal with here */
 170         }
 171         else if (IsA(jtnode, FromExpr))
 172         {
 173                 FromExpr   *f = (FromExpr *) jtnode;
 174                 ListCell   *l;
 175
 176                 /*
 177                  * First, recurse to handle child joins.
 178                  */
 179                 foreach(l, f->fromlist)
 180                 {
 181                         find_placeholders_recurse(root, lfirst(l));
 182                 }
 183
 184                 /*
 185                  * Now process the top-level quals.
 186                  */
 187                 find_placeholders_in_expr(root, f->quals);
 188         }
 189         else if (IsA(jtnode, JoinExpr))
 190         {
 191                 JoinExpr   *j = (JoinExpr *) jtnode;
 192
 193                 /*
 194                  * First, recurse to handle child joins.
 195                  */
 196                 find_placeholders_recurse(root, j->larg);
 197                 find_placeholders_recurse(root, j->rarg);
 198
 199                 /* Process the qual clauses */
 200                 find_placeholders_in_expr(root, j->quals);
 201         }
 202         else
 203                 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 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         vars = pull_var_clause(expr,
 223                                                    PVC_RECURSE_AGGREGATES |
 224                                                    PVC_RECURSE_WINDOWFUNCS |
 225                                                    PVC_INCLUDE_PLACEHOLDERS);
 226         foreach(vl, vars)
 227         {
 228                 PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
 229
 230                 /* Ignore any plain Vars */
 231                 if (!IsA(phv, PlaceHolderVar))
 232                         continue;
 233
 234                 /* Create a PlaceHolderInfo entry if there's not one already */
 235                 (void) find_placeholder_info(root, phv, true);
 236         }
 237         list_free(vars);
 238 }
 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 update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
 266 {
 267         ListCell   *lc1;
 268
 269         foreach(lc1, root->placeholder_list)
 270         {
 271                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
 272                 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                 if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
 282                         !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
 283                         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                 eval_at = phinfo->ph_eval_at;
 293
 294                 do
 295                 {
 296                         found_some = false;
 297                         foreach(lc2, root->join_info_list)
 298                         {
 299                                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
 300
 301                                 /* disregard joins not within the PHV's sub-select */
 302                                 if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
 303                                         !bms_is_subset(sjinfo->syn_righthand, syn_level))
 304                                         continue;
 305
 306                                 /* do we reference any nullable rels of this OJ? */
 307                                 if (bms_overlap(eval_at, sjinfo->min_righthand) ||
 308                                         (sjinfo->jointype == JOIN_FULL &&
 309                                          bms_overlap(eval_at, sjinfo->min_lefthand)))
 310                                 {
 311                                         /* yes; have we included all its rels in eval_at? */
 312                                         if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
 313                                                 !bms_is_subset(sjinfo->min_righthand, eval_at))
 314                                         {
 315                                                 /* no, so add them in */
 316                                                 eval_at = bms_add_members(eval_at,
 317                                                                                                   sjinfo->min_lefthand);
 318                                                 eval_at = bms_add_members(eval_at,
 319                                                                                                   sjinfo->min_righthand);
 320                                                 /* we'll need another iteration */
 321                                                 found_some = true;
 322                                         }
 323                                 }
 324                         }
 325                 } 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                 phinfo->ph_eval_at = eval_at;
 331         }
 332 }
 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 fix_placeholder_input_needed_levels(PlannerInfo *root)
 351 {
 352         ListCell   *lc;
 353
 354         foreach(lc, root->placeholder_list)
 355         {
 356                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 357                 List       *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
 358                                                                                    PVC_RECURSE_AGGREGATES |
 359                                                                                    PVC_RECURSE_WINDOWFUNCS |
 360                                                                                    PVC_INCLUDE_PLACEHOLDERS);
 361
 362                 add_vars_to_targetlist(root, vars, phinfo->ph_eval_at, false);
 363                 list_free(vars);
 364         }
 365 }
 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 add_placeholders_to_base_rels(PlannerInfo *root)
 380 {
 381         ListCell   *lc;
 382
 383         foreach(lc, root->placeholder_list)
 384         {
 385                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 386                 Relids          eval_at = phinfo->ph_eval_at;
 387                 int                     varno;
 388
 389                 if (bms_get_singleton_member(eval_at, &varno) &&
 390                         bms_nonempty_difference(phinfo->ph_needed, eval_at))
 391                 {
 392                         RelOptInfo *rel = find_base_rel(root, varno);
 393
 394                         rel->reltarget->exprs = lappend(rel->reltarget->exprs,
 395                                                                                         copyObject(phinfo->ph_var));
 396                         /* reltarget's cost and width fields will be updated later */
 397                 }
 398         }
 399 }
 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 add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
 412                                                         RelOptInfo *outer_rel, RelOptInfo *inner_rel)
 413 {
 414         Relids          relids = joinrel->relids;
 415         ListCell   *lc;
 416
 417         foreach(lc, root->placeholder_list)
 418         {
 419                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 420
 421                 /* Is it still needed above this joinrel? */
 422                 if (bms_nonempty_difference(phinfo->ph_needed, relids))
 423                 {
 424                         /* Is it computable here? */
 425                         if (bms_is_subset(phinfo->ph_eval_at, relids))
 426                         {
 427                                 /* Yup, add it to the output */
 428                                 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
 429                                                                                                         phinfo->ph_var);
 430                                 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                                 if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
 444                                         !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
 445                                 {
 446                                         QualCost        cost;
 447
 448                                         cost_qual_eval_node(&cost, (Node *) phinfo->ph_var->phexpr,
 449                                                                                 root);
 450                                         joinrel->reltarget->cost.startup += cost.startup;
 451                                         joinrel->reltarget->cost.per_tuple += cost.per_tuple;
 452                                 }
 453
 454                                 /* Adjust joinrel's direct_lateral_relids as needed */
 455                                 joinrel->direct_lateral_relids =
 456                                         bms_add_members(joinrel->direct_lateral_relids,
 457                                                                         phinfo->ph_lateral);
 458                         }
 459                 }
 460         }
 461 }