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.29 1998/10/01 02:03:59 tgl 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., retrieve, 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
 138                 switch (command_type)
 139                 {
 140                         case CMD_SELECT:
 141                         case CMD_INSERT:
 142                                 return ((Plan *) make_result(tlist,
 143                                                                                          (Node *) constant_qual,
 144                                                                                          (Plan *) NULL));
 145                                 break;
 146
 147                         case CMD_DELETE:
 148                         case CMD_UPDATE:
 149                                 {
 150                                         SeqScan    *scan = make_seqscan(tlist,
 151                                                                                                         (List *) NULL,
 152                                                                                                         root->resultRelation,
 153                                                                                                         (Plan *) NULL);
 154
 155                                         if (constant_qual != NULL)
 156                                         {
 157                                                 return ((Plan *) make_result(tlist,
 158                                                                                                   (Node *) constant_qual,
 159                                                                                                          (Plan *) scan));
 160                                         }
 161                                         else
 162                                                 return (Plan *) scan;
 163                                 }
 164                                 break;
 165
 166                         default:
 167                                 return (Plan *) NULL;
 168                 }
 169         }
 170
 171         /*
 172          * Find the subplan (access path) and destructively modify the target
 173          * list of the newly created subplan to contain the appropriate join
 174          * references.
 175          */
 176         subplan = subplanner(root, level_tlist, qual);
 177
 178         set_tlist_references(subplan);
 179
 180         /*
 181          * Build a result node linking the plan if we have constant quals
 182          */
 183         if (constant_qual)
 184         {
 185                 subplan = (Plan *) make_result((!root->hasAggs &&
 186                                                                                 !root->groupClause &&
 187                                                                                 !root->havingQual)
 188                                                                            ? tlist : subplan->targetlist,
 189                                                                            (Node *) constant_qual,
 190                                                                            subplan);
 191
 192                 /*
 193                  * Change all varno's of the Result's node target list.
 194                  */
 195                 if (!root->hasAggs && !root->groupClause && !root->havingQual)
 196                         set_tlist_references(subplan);
 197
 198                 return subplan;
 199         }
 200
 201         /*
 202          * fix up the flattened target list of the plan root node so that
 203          * expressions are evaluated.  this forces expression evaluations that
 204          * may involve expensive function calls to be delayed to the very last
 205          * stage of query execution.  this could be bad. but it is joey's
 206          * responsibility to optimally push these expressions down the plan
 207          * tree.  -- Wei
 208          *
 209          * But now nothing to do if there are GroupBy and/or Aggregates: 1.
 210          * make_groupPlan fixes tlist; 2. flatten_tlist_vars does nothing with
 211          * aggregates fixing only other entries (i.e. - GroupBy-ed and so
 212          * fixed by make_groupPlan).     - vadim 04/05/97
 213          */
 214         else
 215         {
 216                 if (!root->hasAggs && !root->groupClause && !root->havingQual)
 217                         subplan->targetlist = flatten_tlist_vars(tlist,
 218                                                                                                          subplan->targetlist);
 219                 return subplan;
 220         }
 221
 222 #ifdef NOT_USED
 223
 224         /*
 225          * Destructively modify the query plan's targetlist to add fjoin lists
 226          * to flatten functions that return sets of base types
 227          */
 228         subplan->targetlist = generate_fjoin(subplan->targetlist);
 229 #endif
 230
 231 }
 232
 233 /*
 234  * subplanner
 235  *
 236  *       Subplanner creates an entire plan consisting of joins and scans
 237  *       for processing a single level of attributes.
 238  *
 239  *       flat-tlist is the flattened target list
 240  *       qual is the qualification to be satisfied
 241  *
 242  *       Returns a subplan.
 243  *
 244  */
 245 static Plan *
 246 subplanner(Query *root,
 247                    List *flat_tlist,
 248                    List *qual)
 249 {
 250         RelOptInfo *final_rel;
 251         List       *final_rel_list;
 252
 253         /*
 254          * Initialize the targetlist and qualification, adding entries to
 255          * base_rel_list as relation references are found (e.g., in the
 256          * qualification, the targetlist, etc.)
 257          */
 258         root->base_rel_list = NIL;
 259         root->join_rel_list = NIL;
 260
 261         init_base_rels_tlist(root, flat_tlist);
 262         init_base_rels_qual(root, qual);
 263         add_missing_vars_to_tlist(root, flat_tlist);
 264
 265         /*
 266          * Find all possible scan and join paths. Mark all the clauses and
 267          * relations that can be processed using special join methods, then do
 268          * the exhaustive path search.
 269          */
 270         init_join_info(root->base_rel_list);
 271
 272         final_rel_list = find_paths(root, root->base_rel_list);
 273
 274         if (final_rel_list)
 275                 final_rel = (RelOptInfo *) lfirst(final_rel_list);
 276         else
 277                 final_rel = (RelOptInfo *) NIL;
 278
 279 #if 0                                                   /* fix xfunc */
 280
 281         /*
 282          * Perform Predicate Migration on each path, to optimize and correctly
 283          * assess the cost of each before choosing the cheapest one. -- JMH,
 284          * 11/16/92
 285          *
 286          * Needn't do so if the top rel is pruneable: that means there's no
 287          * expensive functions left to pull up.  -- JMH, 11/22/92
 288          */
 289         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 290                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 291         {
 292                 List       *pathnode;
 293
 294                 foreach(pathnode, final_rel->pathlist)
 295                 {
 296                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 297                                 set_cheapest(final_rel, final_rel->pathlist);
 298                 }
 299         }
 300 #endif
 301
 302         /*
 303          * Determine the cheapest path and create a subplan corresponding to
 304          * it.
 305          */
 306         if (final_rel)
 307                 return create_plan((Path *) final_rel->cheapestpath);
 308         else
 309         {
 310                 elog(NOTICE, "final relation is nil");
 311                 return create_plan((Path *) NULL);
 312         }
 313
 314 }
 315
 316 /*****************************************************************************
 317  *
 318  *****************************************************************************/
 319
 320 static Result *
 321 make_result(List *tlist,
 322                         Node *resconstantqual,
 323                         Plan *subplan)
 324 {
 325         Result     *node = makeNode(Result);
 326         Plan       *plan = &node->plan;
 327
 328 #ifdef NOT_USED
 329         tlist = generate_fjoin(tlist);
 330 #endif
 331         plan->cost = (subplan ? subplan->cost : 0);
 332         plan->state = (EState *) NULL;
 333         plan->targetlist = tlist;
 334         plan->lefttree = subplan;
 335         plan->righttree = NULL;
 336         node->resconstantqual = resconstantqual;
 337         node->resstate = NULL;
 338
 339         return node;
 340 }
 341
 342 /*****************************************************************************
 343  *
 344  *****************************************************************************/
 345
 346 Plan *
 347 make_groupPlan(List **tlist,
 348                            bool tuplePerGroup,
 349                            List *groupClause,
 350                            Plan *subplan)
 351 {
 352         List       *sort_tlist;
 353         List       *sl,
 354                            *gl;
 355         List       *glc = listCopy(groupClause);
 356         List       *otles = NIL;        /* list of removed non-GroupBy entries */
 357         List       *otlvars = NIL;      /* list of var in them */
 358         int                     otlvcnt;
 359         Sort       *sortplan;
 360         Group      *grpplan;
 361         int                     numCols;
 362         AttrNumber *grpColIdx;
 363         int                     last_resno = 1;
 364
 365         numCols = length(groupClause);
 366         grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 367
 368         sort_tlist = new_unsorted_tlist(*tlist);        /* it's copy */
 369
 370         /*
 371          * Make template TL for subplan, Sort & Group: 1. If there are
 372          * aggregates (tuplePerGroup is true) then take away non-GroupBy
 373          * entries and re-set resno-s accordantly. 2. Make grpColIdx
 374          *
 375          * Note: we assume that TLEs in *tlist are ordered in accordance with
 376          * their resdom->resno.
 377          */
 378         foreach(sl, sort_tlist)
 379         {
 380                 Resdom     *resdom = NULL;
 381                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 382                 int                     keyno = 0;
 383
 384                 foreach(gl, groupClause)
 385                 {
 386                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
 387
 388                         keyno++;
 389                         if (grpcl->entry->resdom->resno == te->resdom->resno)
 390                         {
 391
 392                                 resdom = te->resdom;
 393                                 resdom->reskey = keyno;
 394                                 resdom->reskeyop = get_opcode(grpcl->grpOpoid);
 395                                 resdom->resno = last_resno;             /* re-set */
 396                                 grpColIdx[keyno - 1] = last_resno++;
 397                                 glc = lremove(lfirst(gl), glc); /* TLE found for it */
 398                                 break;
 399                         }
 400                 }
 401
 402                 /*
 403                  * Non-GroupBy entry: remove it from Group/Sort TL if there are
 404                  * aggregates in query - it will be evaluated by Aggregate plan
 405                  */
 406                 if (resdom == NULL)
 407                 {
 408                         if (tuplePerGroup)
 409                         {
 410                                 otlvars = nconc(otlvars, pull_var_clause(te->expr));
 411                                 otles = lcons(te, otles);
 412                                 sort_tlist = lremove(te, sort_tlist);
 413                         }
 414                         else
 415                                 te->resdom->resno = last_resno++;
 416                 }
 417         }
 418
 419         if (length(glc) != 0)
 420                 elog(ERROR, "group attribute disappeared from target list");
 421
 422         /*
 423          * If non-GroupBy entries were removed from TL - we are to add Vars
 424          * for them to the end of TL if there are no such Vars in TL already.
 425          */
 426
 427         otlvcnt = length(otlvars);
 428         foreach(gl, otlvars)
 429         {
 430                 Var                *v = (Var *) lfirst(gl);
 431
 432                 if (tlist_member(v, sort_tlist) == NULL)
 433                 {
 434                         sort_tlist = lappend(sort_tlist,
 435                                                                  create_tl_element(v, last_resno));
 436                         last_resno++;
 437                 }
 438                 else
 439 /* already in TL */
 440                         otlvcnt--;
 441         }
 442         /* Now otlvcnt is number of Vars added in TL for non-GroupBy entries */
 443
 444         /* Make TL for subplan: substitute Vars from subplan TL into new TL */
 445         sl = flatten_tlist_vars(sort_tlist, subplan->targetlist);
 446
 447         subplan->targetlist = new_unsorted_tlist(sl);           /* there */
 448
 449         /*
 450          * Make Sort/Group TL : 1. make Var nodes (with varno = 1 and varnoold
 451          * = -1) for all functions, 'couse they will be evaluated by subplan;
 452          * 2. for real Vars: set varno = 1 and varattno to its resno in
 453          * subplan
 454          */
 455         foreach(sl, sort_tlist)
 456         {
 457                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 458                 Resdom     *resdom = te->resdom;
 459                 Node       *expr = te->expr;
 460
 461                 if (IsA(expr, Var))
 462                 {
 463 #if 0                                                   /* subplanVar->resdom->resno expected to
 464                                                                  * be = te->resdom->resno */
 465                         TargetEntry *subplanVar;
 466
 467                         subplanVar = match_varid((Var *) expr, subplan->targetlist);
 468                         ((Var *) expr)->varattno = subplanVar->resdom->resno;
 469 #endif
 470                         ((Var *) expr)->varattno = te->resdom->resno;
 471                         ((Var *) expr)->varno = 1;
 472                 }
 473                 else
 474                         te->expr = (Node *) makeVar(1, resdom->resno,
 475                                                                                 resdom->restype,
 476                                                                                 resdom->restypmod,
 477                                                                                 0, -1, resdom->resno);
 478         }
 479
 480         sortplan = make_sort(sort_tlist,
 481                                                  _TEMP_RELATION_ID_,
 482                                                  subplan,
 483                                                  numCols);
 484         sortplan->plan.cost = subplan->cost;            /* XXX assume no cost */
 485
 486         /*
 487          * make the Group node
 488          */
 489         sort_tlist = copyObject(sort_tlist);
 490         grpplan = make_group(sort_tlist, tuplePerGroup, numCols,
 491                                                  grpColIdx, sortplan);
 492
 493         /*
 494          * Make TL for parent: "restore" non-GroupBy entries (if they were
 495          * removed) and set resno-s of others accordantly.
 496          */
 497         sl = sort_tlist;
 498         sort_tlist = NIL;                       /* to be new parent TL */
 499         foreach(gl, *tlist)
 500         {
 501                 List       *temp = NIL;
 502                 TargetEntry *te = (TargetEntry *) lfirst(gl);
 503
 504                 foreach(temp, otles)    /* Is it removed non-GroupBy entry ? */
 505                 {
 506                         TargetEntry *ote = (TargetEntry *) lfirst(temp);
 507
 508                         if (ote->resdom->resno == te->resdom->resno)
 509                         {
 510                                 otles = lremove(ote, otles);
 511                                 break;
 512                         }
 513                 }
 514                 if (temp == NIL)                /* It's "our" TLE - we're to return */
 515                 {                                               /* it from Sort/Group plans */
 516                         TargetEntry *my = (TargetEntry *) lfirst(sl);           /* get it */
 517
 518                         sl = sl->next;          /* prepare for the next "our" */
 519                         my = copyObject(my);
 520                         my->resdom->resno = te->resdom->resno;          /* order of parent TL */
 521                         sort_tlist = lappend(sort_tlist, my);
 522                         continue;
 523                 }
 524                 /* else - it's TLE of an non-GroupBy entry */
 525                 sort_tlist = lappend(sort_tlist, copyObject(te));
 526         }
 527
 528         /*
 529          * Pure non-GroupBy entries Vars were at the end of Group' TL. They
 530          * shouldn't appear in parent TL, all others shouldn't disappear.
 531          */
 532         Assert(otlvcnt == length(sl));
 533         Assert(length(otles) == 0);
 534
 535         *tlist = sort_tlist;
 536
 537         return (Plan *) grpplan;
 538 }