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.34 1999/02/21 03:48:49 scrappy 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          * Destructively modify the query plan's targetlist to add fjoin lists
 220          * to flatten functions that return sets of base types
 221          */
 222         subplan->targetlist = generate_fjoin(subplan->targetlist);
 223 #endif
 224
 225 }
 226
 227 /*
 228  * subplanner
 229  *
 230  *       Subplanner creates an entire plan consisting of joins and scans
 231  *       for processing a single level of attributes.
 232  *
 233  *       flat_tlist is the flattened target list
 234  *       qual is the qualification to be satisfied
 235  *
 236  *       Returns a subplan.
 237  *
 238  */
 239 static Plan *
 240 subplanner(Query *root,
 241                    List *flat_tlist,
 242                    List *qual)
 243 {
 244         RelOptInfo *final_rel;
 245
 246         /*
 247          * Initialize the targetlist and qualification, adding entries to
 248          * base_rel_list as relation references are found (e.g., in the
 249          * qualification, the targetlist, etc.)
 250          */
 251         root->base_rel_list = NIL;
 252         root->join_rel_list = NIL;
 253
 254         make_var_only_tlist(root, flat_tlist);
 255         add_restrict_and_join_to_rels(root, qual);
 256         add_missing_vars_to_tlist(root, flat_tlist);
 257
 258         set_joininfo_mergeable_hashable(root->base_rel_list);
 259
 260         final_rel = make_one_rel(root, root->base_rel_list);
 261
 262 #ifdef NOT_USED                                         /* fix xfunc */
 263
 264         /*
 265          * Perform Predicate Migration on each path, to optimize and correctly
 266          * assess the cost of each before choosing the cheapest one. -- JMH,
 267          * 11/16/92
 268          *
 269          * Needn't do so if the top rel is pruneable: that means there's no
 270          * expensive functions left to pull up.  -- JMH, 11/22/92
 271          */
 272         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 273                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 274         {
 275                 List       *pathnode;
 276
 277                 foreach(pathnode, final_rel->pathlist)
 278                 {
 279                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 280                                 set_cheapest(final_rel, final_rel->pathlist);
 281                 }
 282         }
 283 #endif
 284
 285         /*
 286          * Determine the cheapest path and create a subplan corresponding to
 287          * it.
 288          */
 289         if (final_rel)
 290                 return create_plan((Path *) final_rel->cheapestpath);
 291         else
 292         {
 293                 elog(NOTICE, "final relation is null");
 294                 return create_plan((Path *) NULL);
 295         }
 296
 297 }
 298
 299 /*****************************************************************************
 300  *
 301  *****************************************************************************/
 302
 303 static Result *
 304 make_result(List *tlist,
 305                         Node *resconstantqual,
 306                         Plan *subplan)
 307 {
 308         Result     *node = makeNode(Result);
 309         Plan       *plan = &node->plan;
 310
 311 #ifdef NOT_USED
 312         tlist = generate_fjoin(tlist);
 313 #endif
 314         plan->cost = (subplan ? subplan->cost : 0);
 315         plan->state = (EState *) NULL;
 316         plan->targetlist = tlist;
 317         plan->lefttree = subplan;
 318         plan->righttree = NULL;
 319         node->resconstantqual = resconstantqual;
 320         node->resstate = NULL;
 321
 322         return node;
 323 }
 324
 325 /*****************************************************************************
 326  *
 327  *****************************************************************************/
 328
 329 Plan *
 330 make_groupPlan(List **tlist,
 331                            bool tuplePerGroup,
 332                            List *groupClause,
 333                            Plan *subplan)
 334 {
 335         List       *sort_tlist;
 336         List       *sl,
 337                            *gl;
 338         List       *glc = listCopy(groupClause);
 339         List       *otles = NIL;        /* list of removed non-GroupBy entries */
 340         List       *otlvars = NIL;      /* list of var in them */
 341         int                     otlvcnt;
 342         Sort       *sortplan;
 343         Group      *grpplan;
 344         int                     numCols;
 345         AttrNumber *grpColIdx;
 346         int                     last_resno = 1;
 347
 348         numCols = length(groupClause);
 349         grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 350
 351         sort_tlist = new_unsorted_tlist(*tlist);        /* it's copy */
 352
 353         /*
 354          * Make template TL for subplan, Sort & Group: 1. If there are
 355          * aggregates (tuplePerGroup is true) then take away non-GroupBy
 356          * entries and re-set resno-s accordantly. 2. Make grpColIdx
 357          *
 358          * Note: we assume that TLEs in *tlist are ordered in accordance with
 359          * their resdom->resno.
 360          */
 361         foreach(sl, sort_tlist)
 362         {
 363                 Resdom     *resdom = NULL;
 364                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 365                 int                     keyno = 0;
 366
 367                 foreach(gl, groupClause)
 368                 {
 369                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
 370
 371                         keyno++;
 372                         if (grpcl->entry->resdom->resno == te->resdom->resno)
 373                         {
 374
 375                                 resdom = te->resdom;
 376                                 resdom->reskey = keyno;
 377                                 resdom->reskeyop = get_opcode(grpcl->grpOpoid);
 378                                 resdom->resno = last_resno;             /* re-set */
 379                                 grpColIdx[keyno - 1] = last_resno++;
 380                                 glc = lremove(lfirst(gl), glc); /* TLE found for it */
 381                                 break;
 382                         }
 383                 }
 384
 385                 /*
 386                  * Non-GroupBy entry: remove it from Group/Sort TL if there are
 387                  * aggregates in query - it will be evaluated by Aggregate plan
 388                  */
 389                 if (resdom == NULL)
 390                 {
 391                         if (tuplePerGroup)
 392                         {
 393                                 otlvars = nconc(otlvars, pull_var_clause(te->expr));
 394                                 otles = lcons(te, otles);
 395                                 sort_tlist = lremove(te, sort_tlist);
 396                         }
 397                         else
 398                                 te->resdom->resno = last_resno++;
 399                 }
 400         }
 401
 402         if (length(glc) != 0)
 403                 elog(ERROR, "group attribute disappeared from target list");
 404
 405         /*
 406          * If non-GroupBy entries were removed from TL - we are to add Vars
 407          * for them to the end of TL if there are no such Vars in TL already.
 408          */
 409
 410         otlvcnt = length(otlvars);
 411         foreach(gl, otlvars)
 412         {
 413                 Var                *v = (Var *) lfirst(gl);
 414
 415                 if (tlist_member(v, sort_tlist) == NULL)
 416                 {
 417                         sort_tlist = lappend(sort_tlist,
 418                                                                  create_tl_element(v, last_resno));
 419                         last_resno++;
 420                 }
 421                 else
 422 /* already in TL */
 423                         otlvcnt--;
 424         }
 425         /* Now otlvcnt is number of Vars added in TL for non-GroupBy entries */
 426
 427         /* Make TL for subplan: substitute Vars from subplan TL into new TL */
 428         sl = flatten_tlist_vars(sort_tlist, subplan->targetlist);
 429
 430         subplan->targetlist = new_unsorted_tlist(sl);           /* there */
 431
 432         /*
 433          * Make Sort/Group TL : 1. make Var nodes (with varno = 1 and varnoold
 434          * = -1) for all functions, 'couse they will be evaluated by subplan;
 435          * 2. for real Vars: set varno = 1 and varattno to its resno in
 436          * subplan
 437          */
 438         foreach(sl, sort_tlist)
 439         {
 440                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 441                 Resdom     *resdom = te->resdom;
 442                 Node       *expr = te->expr;
 443
 444                 if (IsA(expr, Var))
 445                 {
 446 #ifdef NOT_USED                                                 /* subplanVar->resdom->resno expected to
 447                                                                  * be = te->resdom->resno */
 448                         TargetEntry *subplanVar;
 449
 450                         subplanVar = match_varid((Var *) expr, subplan->targetlist);
 451                         ((Var *) expr)->varattno = subplanVar->resdom->resno;
 452 #endif
 453                         ((Var *) expr)->varattno = te->resdom->resno;
 454                         ((Var *) expr)->varno = 1;
 455                 }
 456                 else
 457                         te->expr = (Node *) makeVar(1, resdom->resno,
 458                                                                                 resdom->restype,
 459                                                                                 resdom->restypmod,
 460                                                                                 0, -1, resdom->resno);
 461         }
 462
 463         sortplan = make_sort(sort_tlist,
 464                                                  _NONAME_RELATION_ID_,
 465                                                  subplan,
 466                                                  numCols);
 467         sortplan->plan.cost = subplan->cost;            /* XXX assume no cost */
 468
 469         /*
 470          * make the Group node
 471          */
 472         sort_tlist = copyObject(sort_tlist);
 473         grpplan = make_group(sort_tlist, tuplePerGroup, numCols,
 474                                                  grpColIdx, sortplan);
 475
 476         /*
 477          * Make TL for parent: "restore" non-GroupBy entries (if they were
 478          * removed) and set resno-s of others accordantly.
 479          */
 480         sl = sort_tlist;
 481         sort_tlist = NIL;                       /* to be new parent TL */
 482         foreach(gl, *tlist)
 483         {
 484                 List       *temp = NIL;
 485                 TargetEntry *te = (TargetEntry *) lfirst(gl);
 486
 487                 foreach(temp, otles)    /* Is it removed non-GroupBy entry ? */
 488                 {
 489                         TargetEntry *ote = (TargetEntry *) lfirst(temp);
 490
 491                         if (ote->resdom->resno == te->resdom->resno)
 492                         {
 493                                 otles = lremove(ote, otles);
 494                                 break;
 495                         }
 496                 }
 497                 if (temp == NIL)                /* It's "our" TLE - we're to return */
 498                 {                                               /* it from Sort/Group plans */
 499                         TargetEntry *my = (TargetEntry *) lfirst(sl);           /* get it */
 500
 501                         sl = sl->next;          /* prepare for the next "our" */
 502                         my = copyObject(my);
 503                         my->resdom->resno = te->resdom->resno;          /* order of parent TL */
 504                         sort_tlist = lappend(sort_tlist, my);
 505                         continue;
 506                 }
 507                 /* else - it's TLE of an non-GroupBy entry */
 508                 sort_tlist = lappend(sort_tlist, copyObject(te));
 509         }
 510
 511         /*
 512          * Pure non-GroupBy entries Vars were at the end of Group' TL. They
 513          * shouldn't appear in parent TL, all others shouldn't disappear.
 514          */
 515         Assert(otlvcnt == length(sl));
 516         Assert(length(otles) == 0);
 517
 518         *tlist = sort_tlist;
 519
 520         return (Plan *) grpplan;
 521 }