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-2001, 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.71 2001/03/22 03:59:37 momjian Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include <sys/types.h>
  17
  18 #include "postgres.h"
  19
  20 #include "nodes/makefuncs.h"
  21 #include "nodes/nodeFuncs.h"
  22 #include "optimizer/clauses.h"
  23 #include "optimizer/planmain.h"
  24 #include "optimizer/tlist.h"
  25
  26 typedef struct
  27 {
  28         List       *outer_tlist;
  29         List       *inner_tlist;
  30         Index           acceptable_rel;
  31 } join_references_context;
  32
  33 typedef struct
  34 {
  35         Index           subvarno;
  36         List       *subplanTargetList;
  37 } replace_vars_with_subplan_refs_context;
  38
  39 static void fix_expr_references(Plan *plan, Node *node);
  40 static void set_join_references(Join *join);
  41 static void set_uppernode_references(Plan *plan, Index subvarno);
  42 static Node *join_references_mutator(Node *node,
  43                                                 join_references_context *context);
  44 static Node *replace_vars_with_subplan_refs(Node *node,
  45                                                            Index subvarno,
  46                                                            List *subplanTargetList);
  47 static Node *replace_vars_with_subplan_refs_mutator(Node *node,
  48                                                 replace_vars_with_subplan_refs_context *context);
  49 static bool fix_opids_walker(Node *node, void *context);
  50
  51 /*****************************************************************************
  52  *
  53  *              SUBPLAN REFERENCES
  54  *
  55  *****************************************************************************/
  56
  57 /*
  58  * set_plan_references
  59  *        This is the final processing pass of the planner/optimizer.  The plan
  60  *        tree is complete; we just have to adjust some representational details
  61  *        for the convenience of the executor.  We update Vars in upper plan nodes
  62  *        to refer to the outputs of their subplans, and we compute regproc OIDs
  63  *        for operators (ie, we look up the function that implements each op).
  64  *        We must also build lists of all the subplan nodes present in each
  65  *        plan node's expression trees.
  66  *
  67  *        set_plan_references recursively traverses the whole plan tree.
  68  *
  69  * Returns nothing of interest, but modifies internal fields of nodes.
  70  */
  71 void
  72 set_plan_references(Plan *plan)
  73 {
  74         List       *pl;
  75
  76         if (plan == NULL)
  77                 return;
  78
  79         /*
  80          * We must rebuild the plan's list of subplan nodes, since we are
  81          * copying/mutating its expression trees.
  82          */
  83         plan->subPlan = NIL;
  84
  85         /*
  86          * Plan-type-specific fixes
  87          */
  88         switch (nodeTag(plan))
  89         {
  90                 case T_SeqScan:
  91                         fix_expr_references(plan, (Node *) plan->targetlist);
  92                         fix_expr_references(plan, (Node *) plan->qual);
  93                         break;
  94                 case T_IndexScan:
  95                         fix_expr_references(plan, (Node *) plan->targetlist);
  96                         fix_expr_references(plan, (Node *) plan->qual);
  97                         fix_expr_references(plan,
  98                                                                 (Node *) ((IndexScan *) plan)->indxqual);
  99                         fix_expr_references(plan,
 100                                                         (Node *) ((IndexScan *) plan)->indxqualorig);
 101                         break;
 102                 case T_TidScan:
 103                         fix_expr_references(plan, (Node *) plan->targetlist);
 104                         fix_expr_references(plan, (Node *) plan->qual);
 105                         break;
 106                 case T_SubqueryScan:
 107
 108                         /*
 109                          * We do not do set_uppernode_references() here, because a
 110                          * SubqueryScan will always have been created with correct
 111                          * references to its subplan's outputs to begin with.
 112                          */
 113                         fix_expr_references(plan, (Node *) plan->targetlist);
 114                         fix_expr_references(plan, (Node *) plan->qual);
 115                         /* Recurse into subplan too */
 116                         set_plan_references(((SubqueryScan *) plan)->subplan);
 117                         break;
 118                 case T_NestLoop:
 119                         set_join_references((Join *) plan);
 120                         fix_expr_references(plan, (Node *) plan->targetlist);
 121                         fix_expr_references(plan, (Node *) plan->qual);
 122                         fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual);
 123                         break;
 124                 case T_MergeJoin:
 125                         set_join_references((Join *) plan);
 126                         fix_expr_references(plan, (Node *) plan->targetlist);
 127                         fix_expr_references(plan, (Node *) plan->qual);
 128                         fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual);
 129                         fix_expr_references(plan,
 130                                                         (Node *) ((MergeJoin *) plan)->mergeclauses);
 131                         break;
 132                 case T_HashJoin:
 133                         set_join_references((Join *) plan);
 134                         fix_expr_references(plan, (Node *) plan->targetlist);
 135                         fix_expr_references(plan, (Node *) plan->qual);
 136                         fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual);
 137                         fix_expr_references(plan,
 138                                                           (Node *) ((HashJoin *) plan)->hashclauses);
 139                         break;
 140                 case T_Material:
 141                 case T_Sort:
 142                 case T_Unique:
 143                 case T_SetOp:
 144                 case T_Limit:
 145                 case T_Hash:
 146
 147                         /*
 148                          * These plan types don't actually bother to evaluate their
 149                          * targetlists or quals (because they just return their
 150                          * unmodified input tuples).  The optimizer is lazy about
 151                          * creating really valid targetlists for them.  Best to just
 152                          * leave the targetlist alone.  In particular, we do not want
 153                          * to pull a subplan list for them, since we will likely end
 154                          * up with duplicate list entries for subplans that also
 155                          * appear in lower levels of the plan tree!
 156                          */
 157                         break;
 158                 case T_Agg:
 159                 case T_Group:
 160                         set_uppernode_references(plan, (Index) 0);
 161                         fix_expr_references(plan, (Node *) plan->targetlist);
 162                         fix_expr_references(plan, (Node *) plan->qual);
 163                         break;
 164                 case T_Result:
 165
 166                         /*
 167                          * Result may or may not have a subplan; no need to fix up
 168                          * subplan references if it hasn't got one...
 169                          *
 170                          * XXX why does Result use a different subvarno from Agg/Group?
 171                          */
 172                         if (plan->lefttree != NULL)
 173                                 set_uppernode_references(plan, (Index) OUTER);
 174                         fix_expr_references(plan, (Node *) plan->targetlist);
 175                         fix_expr_references(plan, (Node *) plan->qual);
 176                         fix_expr_references(plan, ((Result *) plan)->resconstantqual);
 177                         break;
 178                 case T_Append:
 179
 180                         /*
 181                          * Append, like Sort et al, doesn't actually evaluate its
 182                          * targetlist or quals, and we haven't bothered to give it its
 183                          * own tlist copy.      So, don't fix targetlist/qual. But do
 184                          * recurse into subplans.
 185                          */
 186                         foreach(pl, ((Append *) plan)->appendplans)
 187                                 set_plan_references((Plan *) lfirst(pl));
 188                         break;
 189                 default:
 190                         elog(ERROR, "set_plan_references: unknown plan type %d",
 191                                  nodeTag(plan));
 192                         break;
 193         }
 194
 195         /*
 196          * Now recurse into subplans, if any
 197          *
 198          * NOTE: it is essential that we recurse into subplans AFTER we set
 199          * subplan references in this plan's tlist and quals.  If we did the
 200          * reference-adjustments bottom-up, then we would fail to match this
 201          * plan's var nodes against the already-modified nodes of the
 202          * subplans.
 203          */
 204         set_plan_references(plan->lefttree);
 205         set_plan_references(plan->righttree);
 206         foreach(pl, plan->initPlan)
 207         {
 208                 SubPlan    *sp = (SubPlan *) lfirst(pl);
 209
 210                 Assert(IsA(sp, SubPlan));
 211                 set_plan_references(sp->plan);
 212         }
 213         foreach(pl, plan->subPlan)
 214         {
 215                 SubPlan    *sp = (SubPlan *) lfirst(pl);
 216
 217                 Assert(IsA(sp, SubPlan));
 218                 set_plan_references(sp->plan);
 219         }
 220 }
 221
 222 /*
 223  * fix_expr_references
 224  *        Do final cleanup on expressions (targetlists or quals).
 225  *
 226  * This consists of looking up operator opcode info for Oper nodes
 227  * and adding subplans to the Plan node's list of contained subplans.
 228  */
 229 static void
 230 fix_expr_references(Plan *plan, Node *node)
 231 {
 232         fix_opids(node);
 233         plan->subPlan = nconc(plan->subPlan, pull_subplans(node));
 234 }
 235
 236 /*
 237  * set_join_references
 238  *        Modifies the target list of a join node to reference its subplans,
 239  *        by setting the varnos to OUTER or INNER and setting attno values to the
 240  *        result domain number of either the corresponding outer or inner join
 241  *        tuple item.
 242  *
 243  * Note: this same transformation has already been applied to the quals
 244  * of the join by createplan.c.  It's a little odd to do it here for the
 245  * targetlist and there for the quals, but it's easier that way.  (Look
 246  * at switch_outer() and the handling of nestloop inner indexscans to
 247  * see why.)
 248  *
 249  * Because the quals are reference-adjusted sooner, we cannot do equal()
 250  * comparisons between qual and tlist var nodes during the time between
 251  * creation of a plan node by createplan.c and its fixing by this module.
 252  * Fortunately, there doesn't seem to be any need to do that.
 253  *
 254  * 'join' is a join plan node
 255  */
 256 static void
 257 set_join_references(Join *join)
 258 {
 259         Plan       *outer = join->plan.lefttree;
 260         Plan       *inner = join->plan.righttree;
 261         List       *outer_tlist = ((outer == NULL) ? NIL : outer->targetlist);
 262         List       *inner_tlist = ((inner == NULL) ? NIL : inner->targetlist);
 263
 264         join->plan.targetlist = join_references(join->plan.targetlist,
 265                                                                                         outer_tlist,
 266                                                                                         inner_tlist,
 267                                                                                         (Index) 0);
 268 }
 269
 270 /*
 271  * set_uppernode_references
 272  *        Update the targetlist and quals of an upper-level plan node
 273  *        to refer to the tuples returned by its lefttree subplan.
 274  *
 275  * This is used for single-input plan types like Agg, Group, Result.
 276  *
 277  * In most cases, we have to match up individual Vars in the tlist and
 278  * qual expressions with elements of the subplan's tlist (which was
 279  * generated by flatten_tlist() from these selfsame expressions, so it
 280  * should have all the required variables).  There is an important exception,
 281  * however: a GROUP BY expression that is also an output expression will
 282  * have been pushed into the subplan tlist unflattened.  We want to detect
 283  * this case and reference the subplan output directly.  Therefore, check
 284  * for equality of the whole tlist expression to any subplan element before
 285  * we resort to picking the expression apart for individual Vars.
 286  */
 287 static void
 288 set_uppernode_references(Plan *plan, Index subvarno)
 289 {
 290         Plan       *subplan = plan->lefttree;
 291         List       *subplanTargetList,
 292                            *outputTargetList,
 293                            *l;
 294
 295         if (subplan != NULL)
 296                 subplanTargetList = subplan->targetlist;
 297         else
 298                 subplanTargetList = NIL;
 299
 300         outputTargetList = NIL;
 301         foreach(l, plan->targetlist)
 302         {
 303                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 304                 TargetEntry *subplantle;
 305                 Node       *newexpr;
 306
 307                 subplantle = tlistentry_member(tle->expr, subplanTargetList);
 308                 if (subplantle)
 309                 {
 310                         /* Found a matching subplan output expression */
 311                         Resdom     *resdom = subplantle->resdom;
 312                         Var                *newvar;
 313
 314                         newvar = makeVar(subvarno,
 315                                                          resdom->resno,
 316                                                          resdom->restype,
 317                                                          resdom->restypmod,
 318                                                          0);
 319                         /* If we're just copying a simple Var, copy up original info */
 320                         if (subplantle->expr && IsA(subplantle->expr, Var))
 321                         {
 322                                 Var                *subvar = (Var *) subplantle->expr;
 323
 324                                 newvar->varnoold = subvar->varnoold;
 325                                 newvar->varoattno = subvar->varoattno;
 326                         }
 327                         else
 328                         {
 329                                 newvar->varnoold = 0;
 330                                 newvar->varoattno = 0;
 331                         }
 332                         newexpr = (Node *) newvar;
 333                 }
 334                 else
 335                 {
 336                         /* No matching expression, so replace individual Vars */
 337                         newexpr = replace_vars_with_subplan_refs(tle->expr,
 338                                                                                                          subvarno,
 339                                                                                                          subplanTargetList);
 340                 }
 341                 outputTargetList = lappend(outputTargetList,
 342                                                                    makeTargetEntry(tle->resdom, newexpr));
 343         }
 344         plan->targetlist = outputTargetList;
 345
 346         plan->qual = (List *)
 347                 replace_vars_with_subplan_refs((Node *) plan->qual,
 348                                                                            subvarno,
 349                                                                            subplanTargetList);
 350 }
 351
 352 /*
 353  * join_references
 354  *         Creates a new set of targetlist entries or join qual clauses by
 355  *         changing the varno/varattno values of variables in the clauses
 356  *         to reference target list values from the outer and inner join
 357  *         relation target lists.
 358  *
 359  * This is used in two different scenarios: a normal join clause, where
 360  * all the Vars in the clause *must* be replaced by OUTER or INNER references;
 361  * and an indexscan being used on the inner side of a nestloop join.
 362  * In the latter case we want to replace the outer-relation Vars by OUTER
 363  * references, but not touch the Vars of the inner relation.
 364  *
 365  * For a normal join, acceptable_rel should be zero so that any failure to
 366  * match a Var will be reported as an error.  For the indexscan case,
 367  * pass inner_tlist = NIL and acceptable_rel = the ID of the inner relation.
 368  *
 369  * 'clauses' is the targetlist or list of join clauses
 370  * 'outer_tlist' is the target list of the outer join relation
 371  * 'inner_tlist' is the target list of the inner join relation, or NIL
 372  * 'acceptable_rel' is either zero or the rangetable index of a relation
 373  *              whose Vars may appear in the clause without provoking an error.
 374  *
 375  * Returns the new expression tree.  The original clause structure is
 376  * not modified.
 377  */
 378 List *
 379 join_references(List *clauses,
 380                                 List *outer_tlist,
 381                                 List *inner_tlist,
 382                                 Index acceptable_rel)
 383 {
 384         join_references_context context;
 385
 386         context.outer_tlist = outer_tlist;
 387         context.inner_tlist = inner_tlist;
 388         context.acceptable_rel = acceptable_rel;
 389         return (List *) join_references_mutator((Node *) clauses, &context);
 390 }
 391
 392 static Node *
 393 join_references_mutator(Node *node,
 394                                                 join_references_context *context)
 395 {
 396         if (node == NULL)
 397                 return NULL;
 398         if (IsA(node, Var))
 399         {
 400                 Var                *var = (Var *) node;
 401                 Var                *newvar = (Var *) copyObject(var);
 402                 Resdom     *resdom;
 403
 404                 resdom = tlist_member((Node *) var, context->outer_tlist);
 405                 if (resdom)
 406                 {
 407                         newvar->varno = OUTER;
 408                         newvar->varattno = resdom->resno;
 409                         return (Node *) newvar;
 410                 }
 411                 resdom = tlist_member((Node *) var, context->inner_tlist);
 412                 if (resdom)
 413                 {
 414                         newvar->varno = INNER;
 415                         newvar->varattno = resdom->resno;
 416                         return (Node *) newvar;
 417                 }
 418
 419                 /*
 420                  * Var not in either tlist --- either raise an error, or return
 421                  * the Var unmodified.
 422                  */
 423                 if (var->varno != context->acceptable_rel)
 424                         elog(ERROR, "join_references: variable not in subplan target lists");
 425                 return (Node *) newvar;
 426         }
 427         return expression_tree_mutator(node,
 428                                                                    join_references_mutator,
 429                                                                    (void *) context);
 430 }
 431
 432 /*
 433  * replace_vars_with_subplan_refs
 434  *              This routine modifies an expression tree so that all Var nodes
 435  *              reference target nodes of a subplan.  It is used to fix up
 436  *              target and qual expressions of non-join upper-level plan nodes.
 437  *
 438  * An error is raised if no matching var can be found in the subplan tlist
 439  * --- so this routine should only be applied to nodes whose subplans'
 440  * targetlists were generated via flatten_tlist() or some such method.
 441  *
 442  * 'node': the tree to be fixed (a targetlist or qual list)
 443  * 'subvarno': varno to be assigned to all Vars
 444  * 'subplanTargetList': target list for subplan
 445  *
 446  * The resulting tree is a copy of the original in which all Var nodes have
 447  * varno = subvarno, varattno = resno of corresponding subplan target.
 448  * The original tree is not modified.
 449  */
 450 static Node *
 451 replace_vars_with_subplan_refs(Node *node,
 452                                                            Index subvarno,
 453                                                            List *subplanTargetList)
 454 {
 455         replace_vars_with_subplan_refs_context context;
 456
 457         context.subvarno = subvarno;
 458         context.subplanTargetList = subplanTargetList;
 459         return replace_vars_with_subplan_refs_mutator(node, &context);
 460 }
 461
 462 static Node *
 463 replace_vars_with_subplan_refs_mutator(Node *node,
 464                                                  replace_vars_with_subplan_refs_context *context)
 465 {
 466         if (node == NULL)
 467                 return NULL;
 468         if (IsA(node, Var))
 469         {
 470                 Var                *var = (Var *) node;
 471                 Var                *newvar = (Var *) copyObject(var);
 472                 Resdom     *resdom;
 473
 474                 resdom = tlist_member((Node *) var, context->subplanTargetList);
 475                 if (!resdom)
 476                         elog(ERROR, "replace_vars_with_subplan_refs: variable not in subplan target list");
 477
 478                 newvar->varno = context->subvarno;
 479                 newvar->varattno = resdom->resno;
 480                 return (Node *) newvar;
 481         }
 482         return expression_tree_mutator(node,
 483                                                                    replace_vars_with_subplan_refs_mutator,
 484                                                                    (void *) context);
 485 }
 486
 487 /*****************************************************************************
 488  *                                      OPERATOR REGPROC LOOKUP
 489  *****************************************************************************/
 490
 491 /*
 492  * fix_opids
 493  *        Calculate opid field from opno for each Oper node in given tree.
 494  *        The given tree can be anything expression_tree_walker handles.
 495  *
 496  * The argument is modified in-place.  (This is OK since we'd want the
 497  * same change for any node, even if it gets visited more than once due to
 498  * shared structure.)
 499  */
 500 void
 501 fix_opids(Node *node)
 502 {
 503         /* This tree walk requires no special setup, so away we go... */
 504         fix_opids_walker(node, NULL);
 505 }
 506
 507 static bool
 508 fix_opids_walker(Node *node, void *context)
 509 {
 510         if (node == NULL)
 511                 return false;
 512         if (is_opclause(node))
 513                 replace_opid((Oper *) ((Expr *) node)->oper);
 514         return expression_tree_walker(node, fix_opids_walker, context);
 515 }