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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * planner.c--
   4  *        The query optimizer external interface.
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.31 1998/09/01 03:23:39 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <sys/types.h>
  15 #include <string.h>
  16
  17 #include "postgres.h"
  18
  19 #include "nodes/pg_list.h"
  20 #include "nodes/plannodes.h"
  21 #include "nodes/parsenodes.h"
  22 #include "nodes/relation.h"
  23 #include "parser/parse_expr.h"
  24
  25 #include "utils/elog.h"
  26 #include "utils/lsyscache.h"
  27 #include "access/heapam.h"
  28
  29 #include "optimizer/internal.h"
  30 #include "optimizer/planner.h"
  31 #include "optimizer/plancat.h"
  32 #include "optimizer/prep.h"
  33 #include "optimizer/planmain.h"
  34 #include "optimizer/subselect.h"
  35 #include "optimizer/paths.h"
  36 #include "optimizer/cost.h"
  37
  38 /* DATA STRUCTURE CREATION/MANIPULATION ROUTINES */
  39 #include "nodes/relation.h"
  40 #include "optimizer/clauseinfo.h"
  41 #include "optimizer/joininfo.h"
  42 #include "optimizer/keys.h"
  43 #include "optimizer/ordering.h"
  44 #include "optimizer/pathnode.h"
  45 #include "optimizer/clauses.h"
  46 #include "optimizer/tlist.h"
  47 #include "optimizer/var.h"
  48
  49 #include "executor/executor.h"
  50
  51 static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
  52 extern Plan *
  53 make_groupPlan(List **tlist, bool tuplePerGroup,
  54                            List *groupClause, Plan *subplan);
  55
  56 /*****************************************************************************
  57  *
  58  *         Query optimizer entry point
  59  *
  60  *****************************************************************************/
  61 Plan *
  62 planner(Query *parse)
  63 {
  64         Plan       *result_plan;
  65
  66         PlannerQueryLevel = 1;
  67         PlannerVarParam = NULL;
  68         PlannerParamVar = NULL;
  69         PlannerInitPlan = NULL;
  70         PlannerPlanId = 0;
  71
  72         result_plan = union_planner(parse);
  73
  74         Assert(PlannerQueryLevel == 1);
  75         if (PlannerPlanId > 0)
  76         {
  77                 result_plan->initPlan = PlannerInitPlan;
  78                 (void) SS_finalize_plan(result_plan);
  79         }
  80         result_plan->nParamExec = length(PlannerParamVar);
  81
  82         return result_plan;
  83 }
  84
  85 /*
  86  * union_planner--
  87  *
  88  *        Invokes the planner on union queries if there are any left,
  89  *        recursing if necessary to get them all, then processes normal plans.
  90  *
  91  * Returns a query plan.
  92  *
  93  */
  94 Plan *
  95 union_planner(Query *parse)
  96 {
  97         List       *tlist = parse->targetList;
  98
  99         /* copy the original tlist, we will need the original one
 100          * for the AGG node later on */
 101         List    *new_tlist = new_unsorted_tlist(tlist);
 102
 103         List       *rangetable = parse->rtable;
 104
 105         Plan       *result_plan = (Plan *) NULL;
 106
 107         Index           rt_index;
 108
 109
 110         if (parse->unionClause)
 111         {
 112           result_plan = (Plan *) plan_union_queries(parse);
 113           /* XXX do we need to do this? bjm 12/19/97 */
 114           tlist = preprocess_targetlist(tlist,
 115                                         parse->commandType,
 116                                         parse->resultRelation,
 117                                         parse->rtable);
 118         }
 119         else if ((rt_index =
 120                           first_inherit_rt_entry(rangetable)) != -1)
 121         {
 122                 result_plan = (Plan *) plan_inherit_queries(parse, rt_index);
 123                 /* XXX do we need to do this? bjm 12/19/97 */
 124                 tlist = preprocess_targetlist(tlist,
 125                                               parse->commandType,
 126                                               parse->resultRelation,
 127                                               parse->rtable);
 128         }
 129         else
 130         {
 131           List  **vpm = NULL;
 132
 133           /* This is only necessary if aggregates are in use in queries like:
 134            * SELECT sid
 135            * FROM part
 136            * GROUP BY sid
 137            * HAVING MIN(pid) > 1;  (pid is used but never selected for!!!)
 138            * because the function 'query_planner' creates the plan for the lefttree
 139            * of the 'GROUP' node and returns only those attributes contained in 'tlist'.
 140            * The original 'tlist' contains only 'sid' here and that's why we have to
 141            * to extend it to attributes which are not selected but are used in the
 142            * havingQual. */
 143
 144           /* 'check_having_qual_for_vars' takes the havingQual and the actual 'tlist'
 145            * as arguments and recursively scans the havingQual for attributes
 146            * (VAR nodes) that are not contained in 'tlist' yet. If so, it creates
 147            * a new entry and attaches it to the list 'new_tlist' (consisting of the
 148            * VAR node and the RESDOM node as usual with tlists :-)  ) */
 149           if (parse->hasAggs)
 150             {
 151               if (parse->havingQual != NULL)
 152                 {
 153                   new_tlist = check_having_qual_for_vars(parse->havingQual,new_tlist);
 154                 }
 155             }
 156
 157           new_tlist = preprocess_targetlist(new_tlist,
 158                                             parse->commandType,
 159                                             parse->resultRelation,
 160                                             parse->rtable);
 161
 162           /* Here starts the original (pre having) code */
 163           tlist = preprocess_targetlist(tlist,
 164                                         parse->commandType,
 165                                         parse->resultRelation,
 166                                         parse->rtable);
 167
 168           if (parse->rtable != NULL)
 169             {
 170               vpm = (List **) palloc(length(parse->rtable) * sizeof(List *));
 171               memset(vpm, 0, length(parse->rtable) * sizeof(List *));
 172             }
 173           PlannerVarParam = lcons(vpm, PlannerVarParam);
 174           result_plan = query_planner(parse,
 175                                       parse->commandType,
 176                                       new_tlist,
 177                                       (List *) parse->qual);
 178           PlannerVarParam = lnext(PlannerVarParam);
 179           if (vpm != NULL)
 180             pfree(vpm);
 181         }
 182
 183         /*
 184          * If we have a GROUP BY clause, insert a group node (with the
 185          * appropriate sort node.)
 186          */
 187         if (parse->groupClause)
 188         {
 189                 bool            tuplePerGroup;
 190
 191                 /*
 192                  * decide whether how many tuples per group the Group node needs
 193                  * to return. (Needs only one tuple per group if no aggregate is
 194                  * present. Otherwise, need every tuple from the group to do the
 195                  * aggregation.)
 196                  */
 197                 tuplePerGroup = parse->hasAggs;
 198
 199                 /* Use 'new_tlist' instead of 'tlist' */
 200                 result_plan =
 201                         make_groupPlan(&new_tlist,
 202                                                    tuplePerGroup,
 203                                                    parse->groupClause,
 204                                                    result_plan);
 205         }
 206
 207         /*
 208          * If aggregate is present, insert the agg node
 209          */
 210         if (parse->hasAggs)
 211         {
 212                 int old_length=0, new_length=0;
 213
 214                 /* Create the AGG node but use 'tlist' not 'new_tlist' as target list because we
 215                  * don't want the additional attributes (only used for the havingQual, see above)
 216                  * to show up in the result */
 217                 result_plan = (Plan *) make_agg(tlist, result_plan);
 218
 219                 /*
 220                  * set the varno/attno entries to the appropriate references to
 221                  * the result tuple of the subplans.
 222                  */
 223                 ((Agg *) result_plan)->aggs =
 224                   set_agg_tlist_references((Agg *) result_plan);
 225
 226
 227                 if(parse->havingQual!=NULL)
 228                   {
 229                     List           *clause;
 230                     List          **vpm = NULL;
 231
 232
 233                     /* stuff copied from above to handle the use of attributes from outside
 234                      * in subselects */
 235
 236                     if (parse->rtable != NULL)
 237                       {
 238                         vpm = (List **) palloc(length(parse->rtable) * sizeof(List *));
 239                         memset(vpm, 0, length(parse->rtable) * sizeof(List *));
 240                       }
 241                     PlannerVarParam = lcons(vpm, PlannerVarParam);
 242
 243                     /* There is a subselect in the havingQual, so we have to process it
 244                      * using the same function as for a subselect in 'where' */
 245                     if (parse->hasSubLinks)
 246                       {
 247                         parse->havingQual = SS_process_sublinks((Node *) parse->havingQual);
 248                       }
 249
 250                     /* convert the havingQual to conjunctive normal form (cnf) */
 251                     parse->havingQual = (Node * ) cnfify((Expr *)(Node *) parse->havingQual,true);
 252
 253                     /* Calculate the opfids from the opnos (=select the correct functions for
 254                      * the used VAR datatypes) */
 255                     parse->havingQual = (Node * ) fix_opids((List *) parse->havingQual);
 256
 257                     ((Agg *) result_plan)->plan.qual=(List *) parse->havingQual;
 258
 259                     /* Check every clause of the havingQual for aggregates used and append
 260                      * them to result_plan->aggs */
 261                     foreach(clause, ((Agg *) result_plan)->plan.qual)
 262                       {
 263                         /* Make sure there are aggregates in the havingQual
 264                          * if so, the list must be longer after check_having_qual_for_aggs */
 265                         old_length=length(((Agg *) result_plan)->aggs);
 266
 267                         ((Agg *) result_plan)->aggs = nconc(((Agg *) result_plan)->aggs,
 268                             check_having_qual_for_aggs((Node *) lfirst(clause),
 269                                        ((Agg *) result_plan)->plan.lefttree->targetlist,
 270                                        ((List *) parse->groupClause)));
 271
 272                         /* Have a look at the length of the returned list. If there is no
 273                          * difference, no aggregates have been found and that means, that
 274                          * the Qual belongs to the where clause */
 275                         if (((new_length=length(((Agg *) result_plan)->aggs)) == old_length) ||
 276                             (new_length == 0))
 277                           {
 278                             elog(ERROR,"This could have been done in a where clause!!");
 279                             return (Plan *)NIL;
 280                           }
 281                       }
 282                     PlannerVarParam = lnext(PlannerVarParam);
 283                     if (vpm != NULL)
 284                       pfree(vpm);
 285                   }
 286         }
 287
 288         /*
 289          * For now, before we hand back the plan, check to see if there is a
 290          * user-specified sort that needs to be done.  Eventually, this will
 291          * be moved into the guts of the planner s.t. user specified sorts
 292          * will be considered as part of the planning process. Since we can
 293          * only make use of user-specified sorts in special cases, we can do
 294          * the optimization step later.
 295          */
 296
 297         if (parse->uniqueFlag)
 298         {
 299                 Plan       *sortplan = make_sortplan(tlist, parse->sortClause, result_plan);
 300
 301                 return (Plan *) make_unique(tlist, sortplan, parse->uniqueFlag);
 302         }
 303         else
 304         {
 305                 if (parse->sortClause)
 306                         return make_sortplan(tlist, parse->sortClause, result_plan);
 307                 else
 308                         return (Plan *) result_plan;
 309         }
 310
 311 }
 312
 313 /*
 314  * make_sortplan--
 315  *        Returns a sortplan which is basically a SORT node attached to the
 316  *        top of the plan returned from the planner.  It also adds the
 317  *         cost of sorting into the plan.
 318  *
 319  * sortkeys: ( resdom1 resdom2 resdom3 ...)
 320  * sortops:  (sortop1 sortop2 sortop3 ...)
 321  */
 322 static Plan *
 323 make_sortplan(List *tlist, List *sortcls, Plan *plannode)
 324 {
 325         Plan       *sortplan = (Plan *) NULL;
 326         List       *temp_tlist = NIL;
 327         List       *i = NIL;
 328         Resdom     *resnode = (Resdom *) NULL;
 329         Resdom     *resdom = (Resdom *) NULL;
 330         int                     keyno = 1;
 331
 332         /*
 333          * First make a copy of the tlist so that we don't corrupt the the
 334          * original .
 335          */
 336
 337         temp_tlist = new_unsorted_tlist(tlist);
 338
 339         foreach(i, sortcls)
 340         {
 341                 SortClause *sortcl = (SortClause *) lfirst(i);
 342
 343                 resnode = sortcl->resdom;
 344                 resdom = tlist_resdom(temp_tlist, resnode);
 345
 346                 /*
 347                  * Order the resdom keys and replace the operator OID for each key
 348                  * with the regproc OID.
 349                  */
 350                 resdom->reskey = keyno;
 351                 resdom->reskeyop = get_opcode(sortcl->opoid);
 352                 keyno += 1;
 353         }
 354
 355         sortplan = (Plan *) make_sort(temp_tlist,
 356                                                                   _TEMP_RELATION_ID_,
 357                                                                   (Plan *) plannode,
 358                                                                   length(sortcls));
 359
 360         /*
 361          * XXX Assuming that an internal sort has no. cost. This is wrong, but
 362          * given that at this point, we don't know the no. of tuples returned,
 363          * etc, we can't do better than to add a constant cost. This will be
 364          * fixed once we move the sort further into the planner, but for now
 365          * ... functionality....
 366          */
 367
 368         sortplan->cost = plannode->cost;
 369
 370         return sortplan;
 371 }
 372
 373 /*
 374  * pg_checkretval() -- check return value of a list of sql parse
 375  *                                              trees.
 376  *
 377  * The return value of a sql function is the value returned by
 378  * the final query in the function.  We do some ad-hoc define-time
 379  * type checking here to be sure that the user is returning the
 380  * type he claims.
 381  */
 382 void
 383 pg_checkretval(Oid rettype, QueryTreeList *queryTreeList)
 384 {
 385         Query      *parse;
 386         List       *tlist;
 387         List       *rt;
 388         int                     cmd;
 389         Type            typ;
 390         Resdom     *resnode;
 391         Relation        reln;
 392         Oid                     relid;
 393         Oid                     tletype;
 394         int                     relnatts;
 395         int                     i;
 396
 397         /* find the final query */
 398         parse = queryTreeList->qtrees[queryTreeList->len - 1];
 399
 400         /*
 401          * test 1:      if the last query is a utility invocation, then there had
 402          * better not be a return value declared.
 403          */
 404         if (parse->commandType == CMD_UTILITY)
 405         {
 406                 if (rettype == InvalidOid)
 407                         return;
 408                 else
 409                         elog(ERROR, "return type mismatch in function decl: final query is a catalog utility");
 410         }
 411
 412         /* okay, it's an ordinary query */
 413         tlist = parse->targetList;
 414         rt = parse->rtable;
 415         cmd = parse->commandType;
 416
 417         /*
 418          * test 2:      if the function is declared to return no value, then the
 419          * final query had better not be a retrieve.
 420          */
 421         if (rettype == InvalidOid)
 422         {
 423                 if (cmd == CMD_SELECT)
 424                         elog(ERROR,
 425                                  "function declared with no return type, but final query is a retrieve");
 426                 else
 427                         return;
 428         }
 429
 430         /* by here, the function is declared to return some type */
 431         if ((typ = typeidType(rettype)) == NULL)
 432                 elog(ERROR, "can't find return type %d for function\n", rettype);
 433
 434         /*
 435          * test 3:      if the function is declared to return a value, then the
 436          * final query had better be a retrieve.
 437          */
 438         if (cmd != CMD_SELECT)
 439                 elog(ERROR, "function declared to return type %s, but final query is not a retrieve", typeTypeName(typ));
 440
 441         /*
 442          * test 4:      for base type returns, the target list should have exactly
 443          * one entry, and its type should agree with what the user declared.
 444          */
 445
 446         if (typeTypeRelid(typ) == InvalidOid)
 447         {
 448                 if (ExecTargetListLength(tlist) > 1)
 449                         elog(ERROR, "function declared to return %s returns multiple values in final retrieve", typeTypeName(typ));
 450
 451                 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
 452                 if (resnode->restype != rettype)
 453                         elog(ERROR, "return type mismatch in function: declared to return %s, returns %s", typeTypeName(typ), typeidTypeName(resnode->restype));
 454
 455                 /* by here, base return types match */
 456                 return;
 457         }
 458
 459         /*
 460          * If the target list is of length 1, and the type of the varnode in
 461          * the target list is the same as the declared return type, this is
 462          * okay.  This can happen, for example, where the body of the function
 463          * is 'retrieve (x = func2())', where func2 has the same return type
 464          * as the function that's calling it.
 465          */
 466         if (ExecTargetListLength(tlist) == 1)
 467         {
 468                 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
 469                 if (resnode->restype == rettype)
 470                         return;
 471         }
 472
 473         /*
 474          * By here, the procedure returns a (set of) tuples.  This part of the
 475          * typechecking is a hack.      We look up the relation that is the
 476          * declared return type, and be sure that attributes 1 .. n in the
 477          * target list match the declared types.
 478          */
 479         reln = heap_open(typeTypeRelid(typ));
 480
 481         if (!RelationIsValid(reln))
 482                 elog(ERROR, "cannot open relation relid %d", typeTypeRelid(typ));
 483
 484         relid = reln->rd_id;
 485         relnatts = reln->rd_rel->relnatts;
 486
 487         if (ExecTargetListLength(tlist) != relnatts)
 488                 elog(ERROR, "function declared to return type %s does not retrieve (%s.*)", typeTypeName(typ), typeTypeName(typ));
 489
 490         /* expect attributes 1 .. n in order */
 491         for (i = 1; i <= relnatts; i++)
 492         {
 493                 TargetEntry *tle = lfirst(tlist);
 494                 Node       *thenode = tle->expr;
 495
 496                 tlist = lnext(tlist);
 497                 tletype = exprType(thenode);
 498
 499 #if 0                                                   /* fix me */
 500                 /* this is tedious */
 501                 if (IsA(thenode, Var))
 502                         tletype = (Oid) ((Var *) thenode)->vartype;
 503                 else if (IsA(thenode, Const))
 504                         tletype = (Oid) ((Const *) thenode)->consttype;
 505                 else if (IsA(thenode, Param))
 506                         tletype = (Oid) ((Param *) thenode)->paramtype;
 507                 else if (IsA(thenode, Expr))
 508                         tletype = Expr;
 509
 510                 else if (IsA(thenode, LispList))
 511                 {
 512                         thenode = lfirst(thenode);
 513                         if (IsA(thenode, Oper))
 514                                 tletype = (Oid) get_opresulttype((Oper *) thenode);
 515                         else if (IsA(thenode, Func))
 516                                 tletype = (Oid) get_functype((Func *) thenode);
 517                         else
 518                                 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 519                 }
 520                 else
 521                         elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 522 #endif
 523                 /* reach right in there, why don't you? */
 524                 if (tletype != reln->rd_att->attrs[i - 1]->atttypid)
 525                         elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 526         }
 527
 528         heap_close(reln);
 529
 530         /* success */
 531         return;
 532 }
 533
 534
 535