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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * planmain.c
   4  *        Routines to plan a single query
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.32 1999/02/14 04:56:50 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <sys/types.h>
  15
  16 #include "postgres.h"
  17
  18 #include "nodes/pg_list.h"
  19 #include "nodes/plannodes.h"
  20 #include "nodes/parsenodes.h"
  21 #include "nodes/print.h"
  22 #include "nodes/relation.h"
  23 #include "nodes/makefuncs.h"
  24
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/subselect.h"
  27 #include "optimizer/internal.h"
  28 #include "optimizer/prep.h"
  29 #include "optimizer/paths.h"
  30 #include "optimizer/clauses.h"
  31 #include "optimizer/keys.h"
  32 #include "optimizer/tlist.h"
  33 #include "optimizer/var.h"
  34 #include "optimizer/xfunc.h"
  35 #include "optimizer/cost.h"
  36
  37 #include "tcop/dest.h"
  38 #include "utils/elog.h"
  39 #include "utils/palloc.h"
  40 #include "nodes/memnodes.h"
  41 #include "utils/mcxt.h"
  42 #include "utils/lsyscache.h"
  43
  44 static Plan *subplanner(Query *root, List *flat_tlist, List *qual);
  45 static Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
  46
  47 extern Plan *make_groupPlan(List **tlist, bool tuplePerGroup,
  48                            List *groupClause, Plan *subplan);
  49
  50 /*
  51  * query_planner
  52  *        Routine to create a query plan.  It does so by first creating a
  53  *        subplan for the topmost level of attributes in the query.  Then,
  54  *        it modifies all target list and qualifications to consider the next
  55  *        level of nesting and creates a plan for this modified query by
  56  *        recursively calling itself.  The two pieces are then merged together
  57  *        by creating a result node that indicates which attributes should
  58  *        be placed where and any relation level qualifications to be
  59  *        satisfied.
  60  *
  61  *        command-type is the query command, e.g., select, delete, etc.
  62  *        tlist is the target list of the query
  63  *        qual is the qualification of the query
  64  *
  65  *        Returns a query plan.
  66  */
  67 Plan *
  68 query_planner(Query *root,
  69                           int command_type,
  70                           List *tlist,
  71                           List *qual)
  72 {
  73         List       *constant_qual = NIL;
  74         List       *var_only_tlist = NIL;
  75         List       *level_tlist = NIL;
  76         Plan       *subplan = NULL;
  77
  78         if (PlannerQueryLevel > 1)
  79         {
  80                 /* should copy be made ? */
  81                 tlist = (List *) SS_replace_correlation_vars((Node *) tlist);
  82                 qual = (List *) SS_replace_correlation_vars((Node *) qual);
  83         }
  84         if (root->hasSubLinks)
  85                 qual = (List *) SS_process_sublinks((Node *) qual);
  86
  87         qual = cnfify((Expr *) qual, true);
  88 #ifdef OPTIMIZER_DEBUG
  89         printf("After cnfify()\n");
  90         pprint(qual);
  91 #endif
  92
  93         /*
  94          * A command without a target list or qualification is an error,
  95          * except for "delete foo".
  96          */
  97         if (tlist == NIL && qual == NULL)
  98         {
  99                 if (command_type == CMD_DELETE)
 100                 {
 101                         return ((Plan *) make_seqscan(NIL,
 102                                                                                   NIL,
 103                                                                                   root->resultRelation,
 104                                                                                   (Plan *) NULL));
 105                 }
 106                 else
 107                         return (Plan *) NULL;
 108         }
 109
 110         /*
 111          * Pull out any non-variable qualifications so these can be put in the
 112          * topmost result node.  The opids for the remaining qualifications
 113          * will be changed to regprocs later.
 114          */
 115         qual = pull_constant_clauses(qual, &constant_qual);
 116         fix_opids(constant_qual);
 117
 118         /*
 119          * Create a target list that consists solely of (resdom var) target
 120          * list entries, i.e., contains no arbitrary expressions.
 121          */
 122         var_only_tlist = flatten_tlist(tlist);
 123         if (var_only_tlist)
 124                 level_tlist = var_only_tlist;
 125         else
 126                 /* from old code. the logic is beyond me. - ay 2/95 */
 127                 level_tlist = tlist;
 128
 129         /*
 130          * A query may have a non-variable target list and a non-variable
 131          * qualification only under certain conditions: - the query creates
 132          * all-new tuples, or - the query is a replace (a scan must still be
 133          * done in this case).
 134          */
 135         if (var_only_tlist == NULL && qual == NULL)
 136         {
 137                 switch (command_type)
 138                 {
 139                         case CMD_SELECT:
 140                         case CMD_INSERT:
 141                                 return ((Plan *) make_result(tlist,
 142                                                                                          (Node *) constant_qual,
 143                                                                                          (Plan *) NULL));
 144                                 break;
 145                         case CMD_DELETE:
 146                         case CMD_UPDATE:
 147                                 {
 148                                         SeqScan    *scan = make_seqscan(tlist,
 149                                                                                                         (List *) NULL,
 150                                                                                                         root->resultRelation,
 151                                                                                                         (Plan *) NULL);
 152
 153                                         if (constant_qual != NULL)
 154                                                 return ((Plan *) make_result(tlist,
 155                                                                                                   (Node *) constant_qual,
 156                                                                                                          (Plan *) scan));
 157                                         else
 158                                                 return (Plan *) scan;
 159                                 }
 160                                 break;
 161                         default:
 162                                 return (Plan *) NULL;
 163                 }
 164         }
 165
 166         /*
 167          * Find the subplan (access path) and destructively modify the target
 168          * list of the newly created subplan to contain the appropriate join
 169          * references.
 170          */
 171         subplan = subplanner(root, level_tlist, qual);
 172
 173         set_tlist_references(subplan);
 174
 175         /*
 176          * Build a result node linking the plan if we have constant quals
 177          */
 178         if (constant_qual)
 179         {
 180                 subplan = (Plan *) make_result((!root->hasAggs &&
 181                                                                                 !root->groupClause &&
 182                                                                                 !root->havingQual)
 183                                                                            ? tlist : subplan->targetlist,
 184                                                                            (Node *) constant_qual,
 185                                                                            subplan);
 186
 187                 /*
 188                  * Change all varno's of the Result's node target list.
 189                  */
 190                 if (!root->hasAggs && !root->groupClause && !root->havingQual)
 191                         set_tlist_references(subplan);
 192
 193                 return subplan;
 194         }
 195
 196         /*
 197          * fix up the flattened target list of the plan root node so that
 198          * expressions are evaluated.  this forces expression evaluations that
 199          * may involve expensive function calls to be delayed to the very last
 200          * stage of query execution.  this could be bad. but it is joey's
 201          * responsibility to optimally push these expressions down the plan
 202          * tree.  -- Wei
 203          *
 204          * But now nothing to do if there are GroupBy and/or Aggregates: 1.
 205          * make_groupPlan fixes tlist; 2. flatten_tlist_vars does nothing with
 206          * aggregates fixing only other entries (i.e. - GroupBy-ed and so
 207          * fixed by make_groupPlan).     - vadim 04/05/97
 208          */
 209         else
 210         {
 211                 if (!root->hasAggs && !root->groupClause && !root->havingQual)
 212                         subplan->targetlist = flatten_tlist_vars(tlist,
 213                                                                                                          subplan->targetlist);
 214                 return subplan;
 215         }
 216
 217 #ifdef NOT_USED
 218
 219         /*
 220          * Destructively modify the query plan's targetlist to add fjoin lists
 221          * to flatten functions that return sets of base types
 222          */
 223         subplan->targetlist = generate_fjoin(subplan->targetlist);
 224 #endif
 225
 226 }
 227
 228 /*
 229  * subplanner
 230  *
 231  *       Subplanner creates an entire plan consisting of joins and scans
 232  *       for processing a single level of attributes.
 233  *
 234  *       flat_tlist is the flattened target list
 235  *       qual is the qualification to be satisfied
 236  *
 237  *       Returns a subplan.
 238  *
 239  */
 240 static Plan *
 241 subplanner(Query *root,
 242                    List *flat_tlist,
 243                    List *qual)
 244 {
 245         RelOptInfo *final_rel;
 246         List       *final_rel_list;
 247
 248         /*
 249          * Initialize the targetlist and qualification, adding entries to
 250          * base_rel_list as relation references are found (e.g., in the
 251          * qualification, the targetlist, etc.)
 252          */
 253         root->base_rel_list = NIL;
 254         root->join_rel_list = NIL;
 255
 256         make_var_only_tlist(root, flat_tlist);
 257         add_restrict_and_join_to_rels(root, qual);
 258         add_missing_vars_to_tlist(root, flat_tlist);
 259
 260         set_joininfo_mergeable_hashable(root->base_rel_list);
 261
 262         final_rel_list = find_paths(root, root->base_rel_list);
 263
 264         if (final_rel_list)
 265                 final_rel = (RelOptInfo *) lfirst(final_rel_list);
 266         else
 267                 final_rel = (RelOptInfo *) NIL;
 268
 269 #if 0                                                   /* fix xfunc */
 270
 271         /*
 272          * Perform Predicate Migration on each path, to optimize and correctly
 273          * assess the cost of each before choosing the cheapest one. -- JMH,
 274          * 11/16/92
 275          *
 276          * Needn't do so if the top rel is pruneable: that means there's no
 277          * expensive functions left to pull up.  -- JMH, 11/22/92
 278          */
 279         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 280                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 281         {
 282                 List       *pathnode;
 283
 284                 foreach(pathnode, final_rel->pathlist)
 285                 {
 286                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 287                                 set_cheapest(final_rel, final_rel->pathlist);
 288                 }
 289         }
 290 #endif
 291
 292         /*
 293          * Determine the cheapest path and create a subplan corresponding to
 294          * it.
 295          */
 296         if (final_rel)
 297                 return create_plan((Path *) final_rel->cheapestpath);
 298         else
 299         {
 300                 elog(NOTICE, "final relation is nil");
 301                 return create_plan((Path *) NULL);
 302         }
 303
 304 }
 305
 306 /*****************************************************************************
 307  *
 308  *****************************************************************************/
 309
 310 static Result *
 311 make_result(List *tlist,
 312                         Node *resconstantqual,
 313                         Plan *subplan)
 314 {
 315         Result     *node = makeNode(Result);
 316         Plan       *plan = &node->plan;
 317
 318 #ifdef NOT_USED
 319         tlist = generate_fjoin(tlist);
 320 #endif
 321         plan->cost = (subplan ? subplan->cost : 0);
 322         plan->state = (EState *) NULL;
 323         plan->targetlist = tlist;
 324         plan->lefttree = subplan;
 325         plan->righttree = NULL;
 326         node->resconstantqual = resconstantqual;
 327         node->resstate = NULL;
 328
 329         return node;
 330 }
 331
 332 /*****************************************************************************
 333  *
 334  *****************************************************************************/
 335
 336 Plan *
 337 make_groupPlan(List **tlist,
 338                            bool tuplePerGroup,
 339                            List *groupClause,
 340                            Plan *subplan)
 341 {
 342         List       *sort_tlist;
 343         List       *sl,
 344                            *gl;
 345         List       *glc = listCopy(groupClause);
 346         List       *otles = NIL;        /* list of removed non-GroupBy entries */
 347         List       *otlvars = NIL;      /* list of var in them */
 348         int                     otlvcnt;
 349         Sort       *sortplan;
 350         Group      *grpplan;
 351         int                     numCols;
 352         AttrNumber *grpColIdx;
 353         int                     last_resno = 1;
 354
 355         numCols = length(groupClause);
 356         grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 357
 358         sort_tlist = new_unsorted_tlist(*tlist);        /* it's copy */
 359
 360         /*
 361          * Make template TL for subplan, Sort & Group: 1. If there are
 362          * aggregates (tuplePerGroup is true) then take away non-GroupBy
 363          * entries and re-set resno-s accordantly. 2. Make grpColIdx
 364          *
 365          * Note: we assume that TLEs in *tlist are ordered in accordance with
 366          * their resdom->resno.
 367          */
 368         foreach(sl, sort_tlist)
 369         {
 370                 Resdom     *resdom = NULL;
 371                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 372                 int                     keyno = 0;
 373
 374                 foreach(gl, groupClause)
 375                 {
 376                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
 377
 378                         keyno++;
 379                         if (grpcl->entry->resdom->resno == te->resdom->resno)
 380                         {
 381
 382                                 resdom = te->resdom;
 383                                 resdom->reskey = keyno;
 384                                 resdom->reskeyop = get_opcode(grpcl->grpOpoid);
 385                                 resdom->resno = last_resno;             /* re-set */
 386                                 grpColIdx[keyno - 1] = last_resno++;
 387                                 glc = lremove(lfirst(gl), glc); /* TLE found for it */
 388                                 break;
 389                         }
 390                 }
 391
 392                 /*
 393                  * Non-GroupBy entry: remove it from Group/Sort TL if there are
 394                  * aggregates in query - it will be evaluated by Aggregate plan
 395                  */
 396                 if (resdom == NULL)
 397                 {
 398                         if (tuplePerGroup)
 399                         {
 400                                 otlvars = nconc(otlvars, pull_var_clause(te->expr));
 401                                 otles = lcons(te, otles);
 402                                 sort_tlist = lremove(te, sort_tlist);
 403                         }
 404                         else
 405                                 te->resdom->resno = last_resno++;
 406                 }
 407         }
 408
 409         if (length(glc) != 0)
 410                 elog(ERROR, "group attribute disappeared from target list");
 411
 412         /*
 413          * If non-GroupBy entries were removed from TL - we are to add Vars
 414          * for them to the end of TL if there are no such Vars in TL already.
 415          */
 416
 417         otlvcnt = length(otlvars);
 418         foreach(gl, otlvars)
 419         {
 420                 Var                *v = (Var *) lfirst(gl);
 421
 422                 if (tlist_member(v, sort_tlist) == NULL)
 423                 {
 424                         sort_tlist = lappend(sort_tlist,
 425                                                                  create_tl_element(v, last_resno));
 426                         last_resno++;
 427                 }
 428                 else
 429 /* already in TL */
 430                         otlvcnt--;
 431         }
 432         /* Now otlvcnt is number of Vars added in TL for non-GroupBy entries */
 433
 434         /* Make TL for subplan: substitute Vars from subplan TL into new TL */
 435         sl = flatten_tlist_vars(sort_tlist, subplan->targetlist);
 436
 437         subplan->targetlist = new_unsorted_tlist(sl);           /* there */
 438
 439         /*
 440          * Make Sort/Group TL : 1. make Var nodes (with varno = 1 and varnoold
 441          * = -1) for all functions, 'couse they will be evaluated by subplan;
 442          * 2. for real Vars: set varno = 1 and varattno to its resno in
 443          * subplan
 444          */
 445         foreach(sl, sort_tlist)
 446         {
 447                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 448                 Resdom     *resdom = te->resdom;
 449                 Node       *expr = te->expr;
 450
 451                 if (IsA(expr, Var))
 452                 {
 453 #if 0                                                   /* subplanVar->resdom->resno expected to
 454                                                                  * be = te->resdom->resno */
 455                         TargetEntry *subplanVar;
 456
 457                         subplanVar = match_varid((Var *) expr, subplan->targetlist);
 458                         ((Var *) expr)->varattno = subplanVar->resdom->resno;
 459 #endif
 460                         ((Var *) expr)->varattno = te->resdom->resno;
 461                         ((Var *) expr)->varno = 1;
 462                 }
 463                 else
 464                         te->expr = (Node *) makeVar(1, resdom->resno,
 465                                                                                 resdom->restype,
 466                                                                                 resdom->restypmod,
 467                                                                                 0, -1, resdom->resno);
 468         }
 469
 470         sortplan = make_sort(sort_tlist,
 471                                                  _NONAME_RELATION_ID_,
 472                                                  subplan,
 473                                                  numCols);
 474         sortplan->plan.cost = subplan->cost;            /* XXX assume no cost */
 475
 476         /*
 477          * make the Group node
 478          */
 479         sort_tlist = copyObject(sort_tlist);
 480         grpplan = make_group(sort_tlist, tuplePerGroup, numCols,
 481                                                  grpColIdx, sortplan);
 482
 483         /*
 484          * Make TL for parent: "restore" non-GroupBy entries (if they were
 485          * removed) and set resno-s of others accordantly.
 486          */
 487         sl = sort_tlist;
 488         sort_tlist = NIL;                       /* to be new parent TL */
 489         foreach(gl, *tlist)
 490         {
 491                 List       *temp = NIL;
 492                 TargetEntry *te = (TargetEntry *) lfirst(gl);
 493
 494                 foreach(temp, otles)    /* Is it removed non-GroupBy entry ? */
 495                 {
 496                         TargetEntry *ote = (TargetEntry *) lfirst(temp);
 497
 498                         if (ote->resdom->resno == te->resdom->resno)
 499                         {
 500                                 otles = lremove(ote, otles);
 501                                 break;
 502                         }
 503                 }
 504                 if (temp == NIL)                /* It's "our" TLE - we're to return */
 505                 {                                               /* it from Sort/Group plans */
 506                         TargetEntry *my = (TargetEntry *) lfirst(sl);           /* get it */
 507
 508                         sl = sl->next;          /* prepare for the next "our" */
 509                         my = copyObject(my);
 510                         my->resdom->resno = te->resdom->resno;          /* order of parent TL */
 511                         sort_tlist = lappend(sort_tlist, my);
 512                         continue;
 513                 }
 514                 /* else - it's TLE of an non-GroupBy entry */
 515                 sort_tlist = lappend(sort_tlist, copyObject(te));
 516         }
 517
 518         /*
 519          * Pure non-GroupBy entries Vars were at the end of Group' TL. They
 520          * shouldn't appear in parent TL, all others shouldn't disappear.
 521          */
 522         Assert(otlvcnt == length(sl));
 523         Assert(length(otles) == 0);
 524
 525         *tlist = sort_tlist;
 526
 527         return (Plan *) grpplan;
 528 }