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