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