granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/setrefs.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * setrefs.c
   4  *        Post-processing of a completed plan tree: fix references to subplan
   5  *        vars, and compute regproc values for operators
   6  *
   7  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.84 2002/12/05 15:50:35 tgl Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18
  19 #include "nodes/makefuncs.h"
  20 #include "nodes/nodeFuncs.h"
  21 #include "optimizer/clauses.h"
  22 #include "optimizer/planmain.h"
  23 #include "optimizer/tlist.h"
  24 #include "optimizer/var.h"
  25 #include "parser/parsetree.h"
  26
  27
  28 typedef struct
  29 {
  30         List       *rtable;
  31         List       *outer_tlist;
  32         List       *inner_tlist;
  33         Index           acceptable_rel;
  34 } join_references_context;
  35
  36 typedef struct
  37 {
  38         Index           subvarno;
  39         List       *subplan_targetlist;
  40         bool            tlist_has_non_vars;
  41 } replace_vars_with_subplan_refs_context;
  42
  43 static void fix_expr_references(Plan *plan, Node *node);
  44 static bool fix_expr_references_walker(Node *node, void *context);
  45 static void set_join_references(Join *join, List *rtable);
  46 static void set_uppernode_references(Plan *plan, Index subvarno);
  47 static Node *join_references_mutator(Node *node,
  48                                                 join_references_context *context);
  49 static Node *replace_vars_with_subplan_refs(Node *node,
  50                                                            Index subvarno,
  51                                                            List *subplan_targetlist,
  52                                                            bool tlist_has_non_vars);
  53 static Node *replace_vars_with_subplan_refs_mutator(Node *node,
  54                                                 replace_vars_with_subplan_refs_context *context);
  55 static bool fix_opids_walker(Node *node, void *context);
  56
  57 /*****************************************************************************
  58  *
  59  *              SUBPLAN REFERENCES
  60  *
  61  *****************************************************************************/
  62
  63 /*
  64  * set_plan_references
  65  *        This is the final processing pass of the planner/optimizer.  The plan
  66  *        tree is complete; we just have to adjust some representational details
  67  *        for the convenience of the executor.  We update Vars in upper plan nodes
  68  *        to refer to the outputs of their subplans, and we compute regproc OIDs
  69  *        for operators (ie, we look up the function that implements each op).
  70  *
  71  *        set_plan_references recursively traverses the whole plan tree.
  72  *
  73  * Returns nothing of interest, but modifies internal fields of nodes.
  74  */
  75 void
  76 set_plan_references(Plan *plan, List *rtable)
  77 {
  78         List       *pl;
  79
  80         if (plan == NULL)
  81                 return;
  82
  83         /*
  84          * Plan-type-specific fixes
  85          */
  86         switch (nodeTag(plan))
  87         {
  88                 case T_SeqScan:
  89                         fix_expr_references(plan, (Node *) plan->targetlist);
  90                         fix_expr_references(plan, (Node *) plan->qual);
  91                         break;
  92                 case T_IndexScan:
  93                         fix_expr_references(plan, (Node *) plan->targetlist);
  94                         fix_expr_references(plan, (Node *) plan->qual);
  95                         fix_expr_references(plan,
  96                                                                 (Node *) ((IndexScan *) plan)->indxqual);
  97                         fix_expr_references(plan,
  98                                                         (Node *) ((IndexScan *) plan)->indxqualorig);
  99                         break;
 100                 case T_TidScan:
 101                         fix_expr_references(plan, (Node *) plan->targetlist);
 102                         fix_expr_references(plan, (Node *) plan->qual);
 103                         fix_expr_references(plan,
 104                                                                 (Node *) ((TidScan *) plan)->tideval);
 105                         break;
 106                 case T_SubqueryScan:
 107                         {
 108                                 RangeTblEntry *rte;
 109
 110                                 /*
 111                                  * We do not do set_uppernode_references() here, because a
 112                                  * SubqueryScan will always have been created with correct
 113                                  * references to its subplan's outputs to begin with.
 114                                  */
 115                                 fix_expr_references(plan, (Node *) plan->targetlist);
 116                                 fix_expr_references(plan, (Node *) plan->qual);
 117
 118                                 /* Recurse into subplan too */
 119                                 rte = rt_fetch(((SubqueryScan *) plan)->scan.scanrelid,
 120                                                            rtable);
 121                                 Assert(rte->rtekind == RTE_SUBQUERY);
 122                                 set_plan_references(((SubqueryScan *) plan)->subplan,
 123                                                                         rte->subquery->rtable);
 124                         }
 125                         break;
 126                 case T_FunctionScan:
 127                         {
 128                                 RangeTblEntry *rte;
 129
 130                                 fix_expr_references(plan, (Node *) plan->targetlist);
 131                                 fix_expr_references(plan, (Node *) plan->qual);
 132                                 rte = rt_fetch(((FunctionScan *) plan)->scan.scanrelid,
 133                                                            rtable);
 134                                 Assert(rte->rtekind == RTE_FUNCTION);
 135                                 fix_expr_references(plan, rte->funcexpr);
 136                         }
 137                         break;
 138                 case T_NestLoop:
 139                         set_join_references((Join *) plan, rtable);
 140                         fix_expr_references(plan, (Node *) plan->targetlist);
 141                         fix_expr_references(plan, (Node *) plan->qual);
 142                         fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual);
 143                         break;
 144                 case T_MergeJoin:
 145                         set_join_references((Join *) plan, rtable);
 146                         fix_expr_references(plan, (Node *) plan->targetlist);
 147                         fix_expr_references(plan, (Node *) plan->qual);
 148                         fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual);
 149                         fix_expr_references(plan,
 150                                                         (Node *) ((MergeJoin *) plan)->mergeclauses);
 151                         break;
 152                 case T_HashJoin:
 153                         set_join_references((Join *) plan, rtable);
 154                         fix_expr_references(plan, (Node *) plan->targetlist);
 155                         fix_expr_references(plan, (Node *) plan->qual);
 156                         fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual);
 157                         fix_expr_references(plan,
 158                                                           (Node *) ((HashJoin *) plan)->hashclauses);
 159                         break;
 160                 case T_Material:
 161                 case T_Sort:
 162                 case T_Unique:
 163                 case T_SetOp:
 164                 case T_Limit:
 165                 case T_Hash:
 166
 167                         /*
 168                          * These plan types don't actually bother to evaluate their
 169                          * targetlists or quals (because they just return their
 170                          * unmodified input tuples).  The optimizer is lazy about
 171                          * creating really valid targetlists for them.  Best to just
 172                          * leave the targetlist alone.  In particular, we do not want
 173                          * to process subplans for them, since we will likely end
 174                          * up reprocessing subplans that also appear in lower levels
 175                          * of the plan tree!
 176                          */
 177                         break;
 178                 case T_Agg:
 179                 case T_Group:
 180                         set_uppernode_references(plan, (Index) 0);
 181                         fix_expr_references(plan, (Node *) plan->targetlist);
 182                         fix_expr_references(plan, (Node *) plan->qual);
 183                         break;
 184                 case T_Result:
 185
 186                         /*
 187                          * Result may or may not have a subplan; no need to fix up
 188                          * subplan references if it hasn't got one...
 189                          *
 190                          * XXX why does Result use a different subvarno from Agg/Group?
 191                          */
 192                         if (plan->lefttree != NULL)
 193                                 set_uppernode_references(plan, (Index) OUTER);
 194                         fix_expr_references(plan, (Node *) plan->targetlist);
 195                         fix_expr_references(plan, (Node *) plan->qual);
 196                         fix_expr_references(plan, ((Result *) plan)->resconstantqual);
 197                         break;
 198                 case T_Append:
 199
 200                         /*
 201                          * Append, like Sort et al, doesn't actually evaluate its
 202                          * targetlist or quals, and we haven't bothered to give it its
 203                          * own tlist copy.      So, don't fix targetlist/qual. But do
 204                          * recurse into child plans.
 205                          */
 206                         foreach(pl, ((Append *) plan)->appendplans)
 207                                 set_plan_references((Plan *) lfirst(pl), rtable);
 208                         break;
 209                 default:
 210                         elog(ERROR, "set_plan_references: unknown plan type %d",
 211                                  nodeTag(plan));
 212                         break;
 213         }
 214
 215         /*
 216          * Now recurse into child plans and initplans, if any
 217          *
 218          * NOTE: it is essential that we recurse into child plans AFTER we set
 219          * subplan references in this plan's tlist and quals.  If we did the
 220          * reference-adjustments bottom-up, then we would fail to match this
 221          * plan's var nodes against the already-modified nodes of the
 222          * children.  Fortunately, that consideration doesn't apply to SubPlan
 223          * nodes; else we'd need two passes over the expression trees.
 224          */
 225         set_plan_references(plan->lefttree, rtable);
 226         set_plan_references(plan->righttree, rtable);
 227
 228         foreach(pl, plan->initPlan)
 229         {
 230                 SubPlan    *sp = (SubPlan *) lfirst(pl);
 231
 232                 Assert(IsA(sp, SubPlan));
 233                 set_plan_references(sp->plan, sp->rtable);
 234         }
 235 }
 236
 237 /*
 238  * fix_expr_references
 239  *        Do final cleanup on expressions (targetlists or quals).
 240  *
 241  * This consists of looking up operator opcode info for Oper nodes
 242  * and recursively performing set_plan_references on SubPlans.
 243  *
 244  * The Plan argument is currently unused, but might be needed again someday.
 245  */
 246 static void
 247 fix_expr_references(Plan *plan, Node *node)
 248 {
 249         /* This tree walk requires no special setup, so away we go... */
 250         fix_expr_references_walker(node, NULL);
 251 }
 252
 253 static bool
 254 fix_expr_references_walker(Node *node, void *context)
 255 {
 256         if (node == NULL)
 257                 return false;
 258         if (IsA(node, Expr))
 259         {
 260                 Expr   *expr = (Expr *) node;
 261
 262                 if (expr->opType == OP_EXPR ||
 263                         expr->opType == DISTINCT_EXPR)
 264                         replace_opid((Oper *) expr->oper);
 265                 else if (expr->opType == SUBPLAN_EXPR)
 266                 {
 267                         SubPlan    *sp = (SubPlan *) expr->oper;
 268
 269                         Assert(IsA(sp, SubPlan));
 270                         set_plan_references(sp->plan, sp->rtable);
 271                 }
 272         }
 273         return expression_tree_walker(node, fix_expr_references_walker, context);
 274 }
 275
 276 /*
 277  * set_join_references
 278  *        Modifies the target list of a join node to reference its subplans,
 279  *        by setting the varnos to OUTER or INNER and setting attno values to the
 280  *        result domain number of either the corresponding outer or inner join
 281  *        tuple item.
 282  *
 283  * Note: this same transformation has already been applied to the quals
 284  * of the join by createplan.c.  It's a little odd to do it here for the
 285  * targetlist and there for the quals, but it's easier that way.  (Look
 286  * at switch_outer() and the handling of nestloop inner indexscans to
 287  * see why.)
 288  *
 289  * Because the quals are reference-adjusted sooner, we cannot do equal()
 290  * comparisons between qual and tlist var nodes during the time between
 291  * creation of a plan node by createplan.c and its fixing by this module.
 292  * Fortunately, there doesn't seem to be any need to do that.
 293  *
 294  *      'join' is a join plan node
 295  *      'rtable' is the associated range table
 296  */
 297 static void
 298 set_join_references(Join *join, List *rtable)
 299 {
 300         Plan       *outer = join->plan.lefttree;
 301         Plan       *inner = join->plan.righttree;
 302         List       *outer_tlist = ((outer == NULL) ? NIL : outer->targetlist);
 303         List       *inner_tlist = ((inner == NULL) ? NIL : inner->targetlist);
 304
 305         join->plan.targetlist = join_references(join->plan.targetlist,
 306                                                                                         rtable,
 307                                                                                         outer_tlist,
 308                                                                                         inner_tlist,
 309                                                                                         (Index) 0);
 310 }
 311
 312 /*
 313  * set_uppernode_references
 314  *        Update the targetlist and quals of an upper-level plan node
 315  *        to refer to the tuples returned by its lefttree subplan.
 316  *
 317  * This is used for single-input plan types like Agg, Group, Result.
 318  *
 319  * In most cases, we have to match up individual Vars in the tlist and
 320  * qual expressions with elements of the subplan's tlist (which was
 321  * generated by flatten_tlist() from these selfsame expressions, so it
 322  * should have all the required variables).  There is an important exception,
 323  * however: GROUP BY and ORDER BY expressions will have been pushed into the
 324  * subplan tlist unflattened.  If these values are also needed in the output
 325  * then we want to reference the subplan tlist element rather than recomputing
 326  * the expression.
 327  */
 328 static void
 329 set_uppernode_references(Plan *plan, Index subvarno)
 330 {
 331         Plan       *subplan = plan->lefttree;
 332         List       *subplan_targetlist,
 333                            *output_targetlist,
 334                            *l;
 335         bool            tlist_has_non_vars;
 336
 337         if (subplan != NULL)
 338                 subplan_targetlist = subplan->targetlist;
 339         else
 340                 subplan_targetlist = NIL;
 341
 342         /*
 343          * Detect whether subplan tlist has any non-Vars (typically it won't
 344          * because it's been flattened).  This allows us to save comparisons
 345          * in common cases.
 346          */
 347         tlist_has_non_vars = false;
 348         foreach(l, subplan_targetlist)
 349         {
 350                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 351
 352                 if (tle->expr && !IsA(tle->expr, Var))
 353                 {
 354                         tlist_has_non_vars = true;
 355                         break;
 356                 }
 357         }
 358
 359         output_targetlist = NIL;
 360         foreach(l, plan->targetlist)
 361         {
 362                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 363                 Node       *newexpr;
 364
 365                 newexpr = replace_vars_with_subplan_refs(tle->expr,
 366                                                                                                  subvarno,
 367                                                                                                  subplan_targetlist,
 368                                                                                                  tlist_has_non_vars);
 369                 output_targetlist = lappend(output_targetlist,
 370                                                                   makeTargetEntry(tle->resdom, newexpr));
 371         }
 372         plan->targetlist = output_targetlist;
 373
 374         plan->qual = (List *)
 375                 replace_vars_with_subplan_refs((Node *) plan->qual,
 376                                                                            subvarno,
 377                                                                            subplan_targetlist,
 378                                                                            tlist_has_non_vars);
 379 }
 380
 381 /*
 382  * join_references
 383  *         Creates a new set of targetlist entries or join qual clauses by
 384  *         changing the varno/varattno values of variables in the clauses
 385  *         to reference target list values from the outer and inner join
 386  *         relation target lists.  Also, any join alias variables in the
 387  *         clauses are expanded into references to their component variables.
 388  *
 389  * This is used in two different scenarios: a normal join clause, where
 390  * all the Vars in the clause *must* be replaced by OUTER or INNER references;
 391  * and an indexscan being used on the inner side of a nestloop join.
 392  * In the latter case we want to replace the outer-relation Vars by OUTER
 393  * references, but not touch the Vars of the inner relation.
 394  *
 395  * For a normal join, acceptable_rel should be zero so that any failure to
 396  * match a Var will be reported as an error.  For the indexscan case,
 397  * pass inner_tlist = NIL and acceptable_rel = the ID of the inner relation.
 398  *
 399  * 'clauses' is the targetlist or list of join clauses
 400  * 'rtable' is the current range table
 401  * 'outer_tlist' is the target list of the outer join relation
 402  * 'inner_tlist' is the target list of the inner join relation, or NIL
 403  * 'acceptable_rel' is either zero or the rangetable index of a relation
 404  *              whose Vars may appear in the clause without provoking an error.
 405  *
 406  * Returns the new expression tree.  The original clause structure is
 407  * not modified.
 408  */
 409 List *
 410 join_references(List *clauses,
 411                                 List *rtable,
 412                                 List *outer_tlist,
 413                                 List *inner_tlist,
 414                                 Index acceptable_rel)
 415 {
 416         join_references_context context;
 417
 418         context.rtable = rtable;
 419         context.outer_tlist = outer_tlist;
 420         context.inner_tlist = inner_tlist;
 421         context.acceptable_rel = acceptable_rel;
 422         return (List *) join_references_mutator((Node *) clauses, &context);
 423 }
 424
 425 static Node *
 426 join_references_mutator(Node *node,
 427                                                 join_references_context *context)
 428 {
 429         if (node == NULL)
 430                 return NULL;
 431         if (IsA(node, Var))
 432         {
 433                 Var                *var = (Var *) node;
 434                 Resdom     *resdom;
 435                 Node       *newnode;
 436
 437                 /* First look for the var in the input tlists */
 438                 resdom = tlist_member((Node *) var, context->outer_tlist);
 439                 if (resdom)
 440                 {
 441                         Var                *newvar = (Var *) copyObject(var);
 442
 443                         newvar->varno = OUTER;
 444                         newvar->varattno = resdom->resno;
 445                         return (Node *) newvar;
 446                 }
 447                 resdom = tlist_member((Node *) var, context->inner_tlist);
 448                 if (resdom)
 449                 {
 450                         Var                *newvar = (Var *) copyObject(var);
 451
 452                         newvar->varno = INNER;
 453                         newvar->varattno = resdom->resno;
 454                         return (Node *) newvar;
 455                 }
 456
 457                 /* Return the Var unmodified, if it's for acceptable_rel */
 458                 if (var->varno == context->acceptable_rel)
 459                         return (Node *) copyObject(var);
 460
 461                 /*
 462                  * Perhaps it's a join alias that can be resolved to input vars?
 463                  * We try this last since it's relatively slow.
 464                  */
 465                 newnode = flatten_join_alias_vars((Node *) var,
 466                                                                                   context->rtable,
 467                                                                                   true);
 468                 if (!equal(newnode, (Node *) var))
 469                 {
 470                         /* Must now resolve the input vars... */
 471                         newnode = join_references_mutator(newnode, context);
 472                         return newnode;
 473                 }
 474
 475                 /* No referent found for Var */
 476                 elog(ERROR, "join_references: variable not in subplan target lists");
 477         }
 478         return expression_tree_mutator(node,
 479                                                                    join_references_mutator,
 480                                                                    (void *) context);
 481 }
 482
 483 /*
 484  * replace_vars_with_subplan_refs
 485  *              This routine modifies an expression tree so that all Var nodes
 486  *              reference target nodes of a subplan.  It is used to fix up
 487  *              target and qual expressions of non-join upper-level plan nodes.
 488  *
 489  * An error is raised if no matching var can be found in the subplan tlist
 490  * --- so this routine should only be applied to nodes whose subplans'
 491  * targetlists were generated via flatten_tlist() or some such method.
 492  *
 493  * If tlist_has_non_vars is true, then we try to match whole subexpressions
 494  * against elements of the subplan tlist, so that we can avoid recomputing
 495  * expressions that were already computed by the subplan.  (This is relatively
 496  * expensive, so we don't want to try it in the common case where the
 497  * subplan tlist is just a flattened list of Vars.)
 498  *
 499  * 'node': the tree to be fixed (a target item or qual)
 500  * 'subvarno': varno to be assigned to all Vars
 501  * 'subplan_targetlist': target list for subplan
 502  * 'tlist_has_non_vars': true if subplan_targetlist contains non-Var exprs
 503  *
 504  * The resulting tree is a copy of the original in which all Var nodes have
 505  * varno = subvarno, varattno = resno of corresponding subplan target.
 506  * The original tree is not modified.
 507  */
 508 static Node *
 509 replace_vars_with_subplan_refs(Node *node,
 510                                                            Index subvarno,
 511                                                            List *subplan_targetlist,
 512                                                            bool tlist_has_non_vars)
 513 {
 514         replace_vars_with_subplan_refs_context context;
 515
 516         context.subvarno = subvarno;
 517         context.subplan_targetlist = subplan_targetlist;
 518         context.tlist_has_non_vars = tlist_has_non_vars;
 519         return replace_vars_with_subplan_refs_mutator(node, &context);
 520 }
 521
 522 static Node *
 523 replace_vars_with_subplan_refs_mutator(Node *node,
 524                                                  replace_vars_with_subplan_refs_context *context)
 525 {
 526         if (node == NULL)
 527                 return NULL;
 528         if (IsA(node, Var))
 529         {
 530                 Var                *var = (Var *) node;
 531                 Resdom     *resdom;
 532                 Var                *newvar;
 533
 534                 resdom = tlist_member((Node *) var, context->subplan_targetlist);
 535                 if (!resdom)
 536                         elog(ERROR, "replace_vars_with_subplan_refs: variable not in subplan target list");
 537                 newvar = (Var *) copyObject(var);
 538                 newvar->varno = context->subvarno;
 539                 newvar->varattno = resdom->resno;
 540                 return (Node *) newvar;
 541         }
 542         /* Try matching more complex expressions too, if tlist has any */
 543         if (context->tlist_has_non_vars)
 544         {
 545                 Resdom     *resdom;
 546
 547                 resdom = tlist_member(node, context->subplan_targetlist);
 548                 if (resdom)
 549                 {
 550                         /* Found a matching subplan output expression */
 551                         Var                *newvar;
 552
 553                         newvar = makeVar(context->subvarno,
 554                                                          resdom->resno,
 555                                                          resdom->restype,
 556                                                          resdom->restypmod,
 557                                                          0);
 558                         newvar->varnoold = 0;           /* wasn't ever a plain Var */
 559                         newvar->varoattno = 0;
 560                         return (Node *) newvar;
 561                 }
 562         }
 563         return expression_tree_mutator(node,
 564                                                                    replace_vars_with_subplan_refs_mutator,
 565                                                                    (void *) context);
 566 }
 567
 568 /*****************************************************************************
 569  *                                      OPERATOR REGPROC LOOKUP
 570  *****************************************************************************/
 571
 572 /*
 573  * fix_opids
 574  *        Calculate opid field from opno for each Oper node in given tree.
 575  *        The given tree can be anything expression_tree_walker handles.
 576  *
 577  * The argument is modified in-place.  (This is OK since we'd want the
 578  * same change for any node, even if it gets visited more than once due to
 579  * shared structure.)
 580  */
 581 void
 582 fix_opids(Node *node)
 583 {
 584         /* This tree walk requires no special setup, so away we go... */
 585         fix_opids_walker(node, NULL);
 586 }
 587
 588 static bool
 589 fix_opids_walker(Node *node, void *context)
 590 {
 591         if (node == NULL)
 592                 return false;
 593         if (IsA(node, Expr))
 594         {
 595                 Expr   *expr = (Expr *) node;
 596
 597                 if (expr->opType == OP_EXPR ||
 598                         expr->opType == DISTINCT_EXPR)
 599                         replace_opid((Oper *) expr->oper);
 600         }
 601         return expression_tree_walker(node, fix_opids_walker, context);
 602 }