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