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