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  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.78 2000/03/21 05:12:01 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include <sys/types.h>
  16
  17 #include "postgres.h"
  18
  19 #include "access/genam.h"
  20 #include "access/heapam.h"
  21 #include "catalog/pg_type.h"
  22 #include "executor/executor.h"
  23 #include "nodes/makefuncs.h"
  24 #include "optimizer/clauses.h"
  25 #include "optimizer/internal.h"
  26 #include "optimizer/paths.h"
  27 #include "optimizer/planmain.h"
  28 #include "optimizer/planner.h"
  29 #include "optimizer/prep.h"
  30 #include "optimizer/subselect.h"
  31 #include "optimizer/tlist.h"
  32 #include "optimizer/var.h"
  33 #include "parser/parse_expr.h"
  34 #include "parser/parse_oper.h"
  35 #include "utils/builtins.h"
  36 #include "utils/lsyscache.h"
  37 #include "utils/syscache.h"
  38
  39
  40 static List *make_subplanTargetList(Query *parse, List *tlist,
  41                                                                         AttrNumber **groupColIdx);
  42 static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
  43                                                         List *groupClause, AttrNumber *grpColIdx,
  44                                                         bool is_presorted, Plan *subplan);
  45 static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
  46
  47 /*****************************************************************************
  48  *
  49  *         Query optimizer entry point
  50  *
  51  *****************************************************************************/
  52 Plan *
  53 planner(Query *parse)
  54 {
  55         Plan       *result_plan;
  56
  57         /* Initialize state for subselects */
  58         PlannerQueryLevel = 1;
  59         PlannerInitPlan = NULL;
  60         PlannerParamVar = NULL;
  61         PlannerPlanId = 0;
  62
  63         /* this should go away sometime soon */
  64         transformKeySetQuery(parse);
  65
  66         /* primary planning entry point (may recurse for subplans) */
  67         result_plan = subquery_planner(parse, -1.0 /* default case */);
  68
  69         Assert(PlannerQueryLevel == 1);
  70
  71         /* if top-level query had subqueries, do housekeeping for them */
  72         if (PlannerPlanId > 0)
  73         {
  74                 (void) SS_finalize_plan(result_plan);
  75                 result_plan->initPlan = PlannerInitPlan;
  76         }
  77
  78         /* executor wants to know total number of Params used overall */
  79         result_plan->nParamExec = length(PlannerParamVar);
  80
  81         /* final cleanup of the plan */
  82         set_plan_references(result_plan);
  83
  84         return result_plan;
  85 }
  86
  87
  88 /*--------------------
  89  * subquery_planner
  90  *        Invokes the planner on a subquery.  We recurse to here for each
  91  *        sub-SELECT found in the query tree.
  92  *
  93  * parse is the querytree produced by the parser & rewriter.
  94  * tuple_fraction is the fraction of tuples we expect will be retrieved.
  95  * tuple_fraction is interpreted as explained for union_planner, below.
  96  *
  97  * Basically, this routine does the stuff that should only be done once
  98  * per Query object.  It then calls union_planner, which may be called
  99  * recursively on the same Query node in order to handle UNIONs and/or
 100  * inheritance.  subquery_planner is called recursively from subselect.c.
 101  *
 102  * prepunion.c uses an unholy combination of calling union_planner when
 103  * recursing on the primary Query node, or subquery_planner when recursing
 104  * on a UNION'd Query node that hasn't previously been seen by
 105  * subquery_planner.  That whole chunk of code needs rewritten from scratch.
 106  *
 107  * Returns a query plan.
 108  *--------------------
 109  */
 110 Plan *
 111 subquery_planner(Query *parse, double tuple_fraction)
 112 {
 113         /*
 114          * A HAVING clause without aggregates is equivalent to a WHERE clause
 115          * (except it can only refer to grouped fields).  If there are no
 116          * aggs anywhere in the query, then we don't want to create an Agg
 117          * plan node, so merge the HAVING condition into WHERE.  (We used to
 118          * consider this an error condition, but it seems to be legal SQL.)
 119          */
 120         if (parse->havingQual != NULL && ! parse->hasAggs)
 121         {
 122                 if (parse->qual == NULL)
 123                         parse->qual = parse->havingQual;
 124                 else
 125                         parse->qual = (Node *) make_andclause(lappend(lcons(parse->qual,
 126                                                                                                                                 NIL),
 127                                                                                                                   parse->havingQual));
 128                 parse->havingQual = NULL;
 129         }
 130
 131         /*
 132          * Simplify constant expressions in targetlist and quals.
 133          *
 134          * Note that at this point the qual has not yet been converted to
 135          * implicit-AND form, so we can apply eval_const_expressions directly.
 136          * Also note that we need to do this before SS_process_sublinks,
 137          * because that routine inserts bogus "Const" nodes.
 138          */
 139         parse->targetList = (List *)
 140                 eval_const_expressions((Node *) parse->targetList);
 141         parse->qual = eval_const_expressions(parse->qual);
 142         parse->havingQual = eval_const_expressions(parse->havingQual);
 143
 144         /*
 145          * Canonicalize the qual, and convert it to implicit-AND format.
 146          *
 147          * XXX Is there any value in re-applying eval_const_expressions
 148          * after canonicalize_qual?
 149          */
 150         parse->qual = (Node *) canonicalize_qual((Expr *) parse->qual, true);
 151 #ifdef OPTIMIZER_DEBUG
 152         printf("After canonicalize_qual()\n");
 153         pprint(parse->qual);
 154 #endif
 155
 156         /*
 157          * Ditto for the havingQual
 158          */
 159         parse->havingQual = (Node *) canonicalize_qual((Expr *) parse->havingQual,
 160                                                                                                    true);
 161
 162         /* Expand SubLinks to SubPlans */
 163         if (parse->hasSubLinks)
 164         {
 165                 parse->targetList = (List *)
 166                         SS_process_sublinks((Node *) parse->targetList);
 167                 parse->qual = SS_process_sublinks(parse->qual);
 168                 parse->havingQual = SS_process_sublinks(parse->havingQual);
 169
 170                 if (parse->groupClause != NIL)
 171                 {
 172                         /*
 173                          * Check for ungrouped variables passed to subplans.
 174                          * Note we do NOT do this for subplans in WHERE; it's legal
 175                          * there because WHERE is evaluated pre-GROUP.
 176                          *
 177                          * An interesting fine point: if we reassigned a HAVING qual
 178                          * into WHERE above, then we will accept references to ungrouped
 179                          * vars from subplans in the HAVING qual.  This is not entirely
 180                          * consistent, but it doesn't seem particularly harmful...
 181                          */
 182                         check_subplans_for_ungrouped_vars((Node *) parse->targetList,
 183                                                                                           parse);
 184                         check_subplans_for_ungrouped_vars(parse->havingQual, parse);
 185                 }
 186         }
 187
 188         /* Replace uplevel vars with Param nodes */
 189         if (PlannerQueryLevel > 1)
 190         {
 191                 parse->targetList = (List *)
 192                         SS_replace_correlation_vars((Node *) parse->targetList);
 193                 parse->qual = SS_replace_correlation_vars(parse->qual);
 194                 parse->havingQual = SS_replace_correlation_vars(parse->havingQual);
 195         }
 196
 197         /* Do the main planning (potentially recursive) */
 198
 199         return union_planner(parse, tuple_fraction);
 200
 201         /*
 202          * XXX should any more of union_planner's activity be moved here?
 203          *
 204          * That would take careful study of the interactions with prepunion.c,
 205          * but I suspect it would pay off in simplicity and avoidance of
 206          * wasted cycles.
 207          */
 208 }
 209
 210
 211 /*--------------------
 212  * union_planner
 213  *        Invokes the planner on union-type queries (both regular UNIONs and
 214  *        appends produced by inheritance), recursing if necessary to get them
 215  *        all, then processes normal plans.
 216  *
 217  * parse is the querytree produced by the parser & rewriter.
 218  * tuple_fraction is the fraction of tuples we expect will be retrieved
 219  *
 220  * tuple_fraction is interpreted as follows:
 221  *    < 0: determine fraction by inspection of query (normal case)
 222  *    0: expect all tuples to be retrieved
 223  *        0 < tuple_fraction < 1: expect the given fraction of tuples available
 224  *              from the plan to be retrieved
 225  *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
 226  *              expected to be retrieved (ie, a LIMIT specification)
 227  * The normal case is to pass -1, but some callers pass values >= 0 to
 228  * override this routine's determination of the appropriate fraction.
 229  *
 230  * Returns a query plan.
 231  *--------------------
 232  */
 233 Plan *
 234 union_planner(Query *parse,
 235                           double tuple_fraction)
 236 {
 237         List       *tlist = parse->targetList;
 238         List       *rangetable = parse->rtable;
 239         Plan       *result_plan = (Plan *) NULL;
 240         AttrNumber *groupColIdx = NULL;
 241         List       *current_pathkeys = NIL;
 242         List       *group_pathkeys;
 243         List       *sort_pathkeys;
 244         Index           rt_index;
 245
 246         if (parse->unionClause)
 247         {
 248                 result_plan = (Plan *) plan_union_queries(parse);
 249                 /* XXX do we need to do this? bjm 12/19/97 */
 250                 tlist = preprocess_targetlist(tlist,
 251                                                                           parse->commandType,
 252                                                                           parse->resultRelation,
 253                                                                           parse->rtable);
 254                 /*
 255                  * We leave current_pathkeys NIL indicating we do not know sort order.
 256                  * Actually, for a normal UNION we have done an explicit sort; ought
 257                  * to change interface to plan_union_queries to pass that info back!
 258                  */
 259
 260                 /* Calculate pathkeys that represent grouping/ordering requirements */
 261                 group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
 262                                                                                                            tlist);
 263                 sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
 264                                                                                                           tlist);
 265         }
 266         else if ((rt_index = first_inherit_rt_entry(rangetable)) != -1)
 267         {
 268                 List       *sub_tlist;
 269
 270                 /*
 271                  * Generate appropriate target list for subplan; may be different
 272                  * from tlist if grouping or aggregation is needed.
 273                  */
 274                 sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
 275
 276                 /*
 277                  * Recursively plan the subqueries needed for inheritance
 278                  */
 279                 result_plan = (Plan *) plan_inherit_queries(parse, sub_tlist,
 280                                                                                                         rt_index);
 281
 282                 /*
 283                  * Fix up outer target list.  NOTE: unlike the case for non-inherited
 284                  * query, we pass the unfixed tlist to subplans, which do their own
 285                  * fixing.  But we still want to fix the outer target list afterwards.
 286                  * I *think* this is correct --- doing the fix before recursing is
 287                  * definitely wrong, because preprocess_targetlist() will do the
 288                  * wrong thing if invoked twice on the same list. Maybe that is a bug?
 289                  * tgl 6/6/99
 290                  */
 291                 tlist = preprocess_targetlist(tlist,
 292                                                                           parse->commandType,
 293                                                                           parse->resultRelation,
 294                                                                           parse->rtable);
 295
 296                 if (parse->rowMark != NULL)
 297                         elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
 298                 /*
 299                  * We leave current_pathkeys NIL indicating we do not know sort order
 300                  * of the Append-ed results.
 301                  */
 302
 303                 /* Calculate pathkeys that represent grouping/ordering requirements */
 304                 group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
 305                                                                                                            tlist);
 306                 sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
 307                                                                                                           tlist);
 308         }
 309         else
 310         {
 311                 List       *sub_tlist;
 312
 313                 /* Preprocess targetlist in case we are inside an INSERT/UPDATE. */
 314                 tlist = preprocess_targetlist(tlist,
 315                                                                           parse->commandType,
 316                                                                           parse->resultRelation,
 317                                                                           parse->rtable);
 318
 319                 /*
 320                  * Add row-mark targets for UPDATE (should this be done in
 321                  * preprocess_targetlist?)
 322                  */
 323                 if (parse->rowMark != NULL)
 324                 {
 325                         List       *l;
 326
 327                         foreach(l, parse->rowMark)
 328                         {
 329                                 RowMark    *rowmark = (RowMark *) lfirst(l);
 330                                 TargetEntry *ctid;
 331                                 Resdom     *resdom;
 332                                 Var                *var;
 333                                 char       *resname;
 334
 335                                 if (!(rowmark->info & ROW_MARK_FOR_UPDATE))
 336                                         continue;
 337
 338                                 resname = (char *) palloc(32);
 339                                 sprintf(resname, "ctid%u", rowmark->rti);
 340                                 resdom = makeResdom(length(tlist) + 1,
 341                                                                         TIDOID,
 342                                                                         -1,
 343                                                                         resname,
 344                                                                         0,
 345                                                                         0,
 346                                                                         true);
 347
 348                                 var = makeVar(rowmark->rti, -1, TIDOID, -1, 0);
 349
 350                                 ctid = makeTargetEntry(resdom, (Node *) var);
 351                                 tlist = lappend(tlist, ctid);
 352                         }
 353                 }
 354
 355                 /*
 356                  * Generate appropriate target list for subplan; may be different
 357                  * from tlist if grouping or aggregation is needed.
 358                  */
 359                 sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
 360
 361                 /* Calculate pathkeys that represent grouping/ordering requirements */
 362                 group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
 363                                                                                                            tlist);
 364                 sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
 365                                                                                                           tlist);
 366
 367                 /*
 368                  * Figure out whether we need a sorted result from query_planner.
 369                  *
 370                  * If we have a GROUP BY clause, then we want a result sorted
 371                  * properly for grouping.  Otherwise, if there is an ORDER BY clause,
 372                  * we want to sort by the ORDER BY clause.  (Note: if we have both,
 373                  * and ORDER BY is a superset of GROUP BY, it would be tempting to
 374                  * request sort by ORDER BY --- but that might just leave us failing
 375                  * to exploit an available sort order at all.  Needs more thought...)
 376                  */
 377                 if (parse->groupClause)
 378                         parse->query_pathkeys = group_pathkeys;
 379                 else if (parse->sortClause)
 380                         parse->query_pathkeys = sort_pathkeys;
 381                 else
 382                         parse->query_pathkeys = NIL;
 383
 384                 /*
 385                  * Figure out whether we expect to retrieve all the tuples that the
 386                  * plan can generate, or to stop early due to a LIMIT or other
 387                  * factors.  If the caller passed a value >= 0, believe that value,
 388                  * else do our own examination of the query context.
 389                  */
 390                 if (tuple_fraction < 0.0)
 391                 {
 392                         /* Initial assumption is we need all the tuples */
 393                         tuple_fraction = 0.0;
 394                         /*
 395                          * Check for a LIMIT clause.
 396                          */
 397                         if (parse->limitCount != NULL)
 398                         {
 399                                 if (IsA(parse->limitCount, Const))
 400                                 {
 401                                         Const      *limitc = (Const *) parse->limitCount;
 402                                         int                     count = (int) (limitc->constvalue);
 403
 404                                         /*
 405                                          * The constant can legally be either 0 ("ALL") or a
 406                                          * positive integer.  If it is not ALL, we also need
 407                                          * to consider the OFFSET part of LIMIT.
 408                                          */
 409                                         if (count > 0)
 410                                         {
 411                                                 tuple_fraction = (double) count;
 412                                                 if (parse->limitOffset != NULL)
 413                                                 {
 414                                                         if (IsA(parse->limitOffset, Const))
 415                                                         {
 416                                                                 int                     offset;
 417
 418                                                                 limitc = (Const *) parse->limitOffset;
 419                                                                 offset = (int) (limitc->constvalue);
 420                                                                 if (offset > 0)
 421                                                                         tuple_fraction += (double) offset;
 422                                                         }
 423                                                         else
 424                                                         {
 425                                                                 /* It's a PARAM ... punt ... */
 426                                                                 tuple_fraction = 0.10;
 427                                                         }
 428                                                 }
 429                                         }
 430                                 }
 431                                 else
 432                                 {
 433                                         /*
 434                                          * COUNT is a PARAM ... don't know exactly what the limit
 435                                          * will be, but for lack of a better idea assume 10%
 436                                          * of the plan's result is wanted.
 437                                          */
 438                                         tuple_fraction = 0.10;
 439                                 }
 440                         }
 441                         /*
 442                          * Check for a retrieve-into-portal, ie DECLARE CURSOR.
 443                          *
 444                          * We have no real idea how many tuples the user will ultimately
 445                          * FETCH from a cursor, but it seems a good bet that he doesn't
 446                          * want 'em all.  Optimize for 10% retrieval (you gotta better
 447                          * number?)
 448                          */
 449                         if (parse->isPortal)
 450                                 tuple_fraction = 0.10;
 451                 }
 452                 /*
 453                  * Adjust tuple_fraction if we see that we are going to apply
 454                  * grouping/aggregation/etc.  This is not overridable by the
 455                  * caller, since it reflects plan actions that this routine
 456                  * will certainly take, not assumptions about context.
 457                  */
 458                 if (parse->groupClause)
 459                 {
 460                         /*
 461                          * In GROUP BY mode, we have the little problem that we don't
 462                          * really know how many input tuples will be needed to make a
 463                          * group, so we can't translate an output LIMIT count into an
 464                          * input count.  For lack of a better idea, assume 25% of the
 465                          * input data will be processed if there is any output limit.
 466                          * However, if the caller gave us a fraction rather than an
 467                          * absolute count, we can keep using that fraction (which amounts
 468                          * to assuming that all the groups are about the same size).
 469                          */
 470                         if (tuple_fraction >= 1.0)
 471                                 tuple_fraction = 0.25;
 472                         /*
 473                          * If both GROUP BY and ORDER BY are specified, we will need
 474                          * two levels of sort --- and, therefore, certainly need to
 475                          * read all the input tuples --- unless ORDER BY is a subset
 476                          * of GROUP BY.  (Although we are comparing non-canonicalized
 477                          * pathkeys here, it should be OK since they will both contain
 478                          * only single-element sublists at this point.  See pathkeys.c.)
 479                          */
 480                         if (parse->groupClause && parse->sortClause &&
 481                                 ! pathkeys_contained_in(sort_pathkeys, group_pathkeys))
 482                                 tuple_fraction = 0.0;
 483                 }
 484                 else if (parse->hasAggs)
 485                 {
 486                         /* Ungrouped aggregate will certainly want all the input tuples. */
 487                         tuple_fraction = 0.0;
 488                 }
 489                 else if (parse->distinctClause)
 490                 {
 491                         /*
 492                          * SELECT DISTINCT, like GROUP, will absorb an unpredictable
 493                          * number of input tuples per output tuple.  Handle the same way.
 494                          */
 495                         if (tuple_fraction >= 1.0)
 496                                 tuple_fraction = 0.25;
 497                 }
 498
 499                 /* Generate the (sub) plan */
 500                 result_plan = query_planner(parse,
 501                                                                         sub_tlist,
 502                                                                         (List *) parse->qual,
 503                                                                         tuple_fraction);
 504
 505                 /* query_planner returns actual sort order (which is not
 506                  * necessarily what we requested) in query_pathkeys.
 507                  */
 508                 current_pathkeys = parse->query_pathkeys;
 509         }
 510
 511         /* query_planner returns NULL if it thinks plan is bogus */
 512         if (! result_plan)
 513                 elog(ERROR, "union_planner: failed to create plan");
 514
 515         /*
 516          * We couldn't canonicalize group_pathkeys and sort_pathkeys before
 517          * running query_planner(), so do it now.
 518          */
 519         group_pathkeys = canonicalize_pathkeys(parse, group_pathkeys);
 520         sort_pathkeys = canonicalize_pathkeys(parse, sort_pathkeys);
 521
 522         /*
 523          * If we have a GROUP BY clause, insert a group node (plus the
 524          * appropriate sort node, if necessary).
 525          */
 526         if (parse->groupClause)
 527         {
 528                 bool            tuplePerGroup;
 529                 List       *group_tlist;
 530                 bool            is_sorted;
 531
 532                 /*
 533                  * Decide whether how many tuples per group the Group node needs
 534                  * to return. (Needs only one tuple per group if no aggregate is
 535                  * present. Otherwise, need every tuple from the group to do the
 536                  * aggregation.)  Note tuplePerGroup is named backwards :-(
 537                  */
 538                 tuplePerGroup = parse->hasAggs;
 539
 540                 /*
 541                  * If there are aggregates then the Group node should just return
 542                  * the same set of vars as the subplan did (but we can exclude
 543                  * any GROUP BY expressions).  If there are no aggregates
 544                  * then the Group node had better compute the final tlist.
 545                  */
 546                 if (parse->hasAggs)
 547                         group_tlist = flatten_tlist(result_plan->targetlist);
 548                 else
 549                         group_tlist = tlist;
 550
 551                 /*
 552                  * Figure out whether the path result is already ordered the way we
 553                  * need it --- if so, no need for an explicit sort step.
 554                  */
 555                 if (pathkeys_contained_in(group_pathkeys, current_pathkeys))
 556                 {
 557                         is_sorted = true;       /* no sort needed now */
 558                         /* current_pathkeys remains unchanged */
 559                 }
 560                 else
 561                 {
 562                         /* We will need to do an explicit sort by the GROUP BY clause.
 563                          * make_groupplan will do the work, but set current_pathkeys
 564                          * to indicate the resulting order.
 565                          */
 566                         is_sorted = false;
 567                         current_pathkeys = group_pathkeys;
 568                 }
 569
 570                 result_plan = make_groupplan(group_tlist,
 571                                                                          tuplePerGroup,
 572                                                                          parse->groupClause,
 573                                                                          groupColIdx,
 574                                                                          is_sorted,
 575                                                                          result_plan);
 576         }
 577
 578         /*
 579          * If aggregate is present, insert the Agg node
 580          *
 581          * HAVING clause, if any, becomes qual of the Agg node
 582          */
 583         if (parse->hasAggs)
 584         {
 585                 result_plan = (Plan *) make_agg(tlist,
 586                                                                                 (List *) parse->havingQual,
 587                                                                                 result_plan);
 588                 /* Note: Agg does not affect any existing sort order of the tuples */
 589         }
 590
 591         /*
 592          * If we were not able to make the plan come out in the right order,
 593          * add an explicit sort step.
 594          */
 595         if (parse->sortClause)
 596         {
 597                 if (! pathkeys_contained_in(sort_pathkeys, current_pathkeys))
 598                 {
 599                         result_plan = make_sortplan(tlist, parse->sortClause, result_plan);
 600                 }
 601         }
 602
 603         /*
 604          * Finally, if there is a DISTINCT clause, add the UNIQUE node.
 605          */
 606         if (parse->distinctClause)
 607         {
 608                 result_plan = (Plan *) make_unique(tlist, result_plan,
 609                                                                                    parse->distinctClause);
 610         }
 611
 612         return result_plan;
 613 }
 614
 615 /*---------------
 616  * make_subplanTargetList
 617  *        Generate appropriate target list when grouping is required.
 618  *
 619  * When union_planner inserts Aggregate and/or Group plan nodes above
 620  * the result of query_planner, we typically want to pass a different
 621  * target list to query_planner than the outer plan nodes should have.
 622  * This routine generates the correct target list for the subplan.
 623  *
 624  * The initial target list passed from the parser already contains entries
 625  * for all ORDER BY and GROUP BY expressions, but it will not have entries
 626  * for variables used only in HAVING clauses; so we need to add those
 627  * variables to the subplan target list.  Also, if we are doing either
 628  * grouping or aggregation, we flatten all expressions except GROUP BY items
 629  * into their component variables; the other expressions will be computed by
 630  * the inserted nodes rather than by the subplan.  For example,
 631  * given a query like
 632  *              SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
 633  * we want to pass this targetlist to the subplan:
 634  *              a,b,c,d,a+b
 635  * where the a+b target will be used by the Sort/Group steps, and the
 636  * other targets will be used for computing the final results.  (In the
 637  * above example we could theoretically suppress the a and b targets and
 638  * use only a+b, but it's not really worth the trouble.)
 639  *
 640  * 'parse' is the query being processed.
 641  * 'tlist' is the query's target list.
 642  * 'groupColIdx' receives an array of column numbers for the GROUP BY
 643  * expressions (if there are any) in the subplan's target list.
 644  *
 645  * The result is the targetlist to be passed to the subplan.
 646  *---------------
 647  */
 648 static List *
 649 make_subplanTargetList(Query *parse,
 650                                            List *tlist,
 651                                            AttrNumber **groupColIdx)
 652 {
 653         List       *sub_tlist;
 654         List       *extravars;
 655         int                     numCols;
 656
 657         *groupColIdx = NULL;
 658
 659         /*
 660          * If we're not grouping or aggregating, nothing to do here;
 661          * query_planner should receive the unmodified target list.
 662          */
 663         if (!parse->hasAggs && !parse->groupClause && !parse->havingQual)
 664                 return tlist;
 665
 666         /*
 667          * Otherwise, start with a "flattened" tlist (having just the vars
 668          * mentioned in the targetlist and HAVING qual --- but not upper-
 669          * level Vars; they will be replaced by Params later on).
 670          */
 671         sub_tlist = flatten_tlist(tlist);
 672         extravars = pull_var_clause(parse->havingQual, false);
 673         sub_tlist = add_to_flat_tlist(sub_tlist, extravars);
 674         freeList(extravars);
 675
 676         /*
 677          * If grouping, create sub_tlist entries for all GROUP BY expressions
 678          * (GROUP BY items that are simple Vars should be in the list already),
 679          * and make an array showing where the group columns are in the sub_tlist.
 680          */
 681         numCols = length(parse->groupClause);
 682         if (numCols > 0)
 683         {
 684                 int                     keyno = 0;
 685                 AttrNumber *grpColIdx;
 686                 List       *gl;
 687
 688                 grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 689                 *groupColIdx = grpColIdx;
 690
 691                 foreach(gl, parse->groupClause)
 692                 {
 693                         GroupClause        *grpcl = (GroupClause *) lfirst(gl);
 694                         Node               *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
 695                         TargetEntry        *te = NULL;
 696                         List               *sl;
 697
 698                         /* Find or make a matching sub_tlist entry */
 699                         foreach(sl, sub_tlist)
 700                         {
 701                                 te = (TargetEntry *) lfirst(sl);
 702                                 if (equal(groupexpr, te->expr))
 703                                         break;
 704                         }
 705                         if (! sl)
 706                         {
 707                                 te = makeTargetEntry(makeResdom(length(sub_tlist) + 1,
 708                                                                                                 exprType(groupexpr),
 709                                                                                                 exprTypmod(groupexpr),
 710                                                                                                 NULL,
 711                                                                                                 (Index) 0,
 712                                                                                                 (Oid) 0,
 713                                                                                                 false),
 714                                                                          groupexpr);
 715                                 sub_tlist = lappend(sub_tlist, te);
 716                         }
 717
 718                         /* and save its resno */
 719                         grpColIdx[keyno++] = te->resdom->resno;
 720                 }
 721         }
 722
 723         return sub_tlist;
 724 }
 725
 726 /*
 727  * make_groupplan
 728  *              Add a Group node for GROUP BY processing.
 729  *              If we couldn't make the subplan produce presorted output for grouping,
 730  *              first add an explicit Sort node.
 731  */
 732 static Plan *
 733 make_groupplan(List *group_tlist,
 734                            bool tuplePerGroup,
 735                            List *groupClause,
 736                            AttrNumber *grpColIdx,
 737                            bool is_presorted,
 738                            Plan *subplan)
 739 {
 740         int                     numCols = length(groupClause);
 741
 742         if (! is_presorted)
 743         {
 744                 /*
 745                  * The Sort node always just takes a copy of the subplan's tlist
 746                  * plus ordering information.  (This might seem inefficient if the
 747                  * subplan contains complex GROUP BY expressions, but in fact Sort
 748                  * does not evaluate its targetlist --- it only outputs the same
 749                  * tuples in a new order.  So the expressions we might be copying
 750                  * are just dummies with no extra execution cost.)
 751                  */
 752                 List       *sort_tlist = new_unsorted_tlist(subplan->targetlist);
 753                 int                     keyno = 0;
 754                 List       *gl;
 755
 756                 foreach(gl, groupClause)
 757                 {
 758                         GroupClause        *grpcl = (GroupClause *) lfirst(gl);
 759                         TargetEntry        *te = nth(grpColIdx[keyno]-1, sort_tlist);
 760                         Resdom             *resdom = te->resdom;
 761
 762                         /*
 763                          * Check for the possibility of duplicate group-by clauses --- the
 764                          * parser should have removed 'em, but the Sort executor will get
 765                          * terribly confused if any get through!
 766                          */
 767                         if (resdom->reskey == 0)
 768                         {
 769                                 /* OK, insert the ordering info needed by the executor. */
 770                                 resdom->reskey = ++keyno;
 771                                 resdom->reskeyop = get_opcode(grpcl->sortop);
 772                         }
 773                 }
 774
 775                 subplan = (Plan *) make_sort(sort_tlist,
 776                                                                          _NONAME_RELATION_ID_,
 777                                                                          subplan,
 778                                                                          keyno);
 779         }
 780
 781         return (Plan *) make_group(group_tlist, tuplePerGroup, numCols,
 782                                                            grpColIdx, subplan);
 783 }
 784
 785 /*
 786  * make_sortplan
 787  *        Add a Sort node to implement an explicit ORDER BY clause.
 788  */
 789 static Plan *
 790 make_sortplan(List *tlist, List *sortcls, Plan *plannode)
 791 {
 792         List       *temp_tlist;
 793         List       *i;
 794         int                     keyno = 0;
 795
 796         /*
 797          * First make a copy of the tlist so that we don't corrupt the
 798          * original.
 799          */
 800
 801         temp_tlist = new_unsorted_tlist(tlist);
 802
 803         foreach(i, sortcls)
 804         {
 805                 SortClause *sortcl = (SortClause *) lfirst(i);
 806                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, temp_tlist);
 807                 Resdom     *resdom = tle->resdom;
 808
 809                 /*
 810                  * Check for the possibility of duplicate order-by clauses --- the
 811                  * parser should have removed 'em, but the executor will get terribly
 812                  * confused if any get through!
 813                  */
 814                 if (resdom->reskey == 0)
 815                 {
 816                         /* OK, insert the ordering info needed by the executor. */
 817                         resdom->reskey = ++keyno;
 818                         resdom->reskeyop = get_opcode(sortcl->sortop);
 819                 }
 820         }
 821
 822         return (Plan *) make_sort(temp_tlist,
 823                                                           _NONAME_RELATION_ID_,
 824                                                           plannode,
 825                                                           keyno);
 826 }
 827
 828 /*
 829  * pg_checkretval() -- check return value of a list of sql parse
 830  *                                              trees.
 831  *
 832  * The return value of a sql function is the value returned by
 833  * the final query in the function.  We do some ad-hoc define-time
 834  * type checking here to be sure that the user is returning the
 835  * type he claims.
 836  *
 837  * XXX Why is this function in this module?
 838  */
 839 void
 840 pg_checkretval(Oid rettype, List *queryTreeList)
 841 {
 842         Query      *parse;
 843         List       *tlist;
 844         List       *rt;
 845         int                     cmd;
 846         Type            typ;
 847         Resdom     *resnode;
 848         Relation        reln;
 849         Oid                     relid;
 850         int                     relnatts;
 851         int                     i;
 852
 853         /* find the final query */
 854         parse = (Query *) nth(length(queryTreeList) - 1, queryTreeList);
 855
 856         /*
 857          * test 1:      if the last query is a utility invocation, then there had
 858          * better not be a return value declared.
 859          */
 860         if (parse->commandType == CMD_UTILITY)
 861         {
 862                 if (rettype == InvalidOid)
 863                         return;
 864                 else
 865                         elog(ERROR, "return type mismatch in function decl: final query is a catalog utility");
 866         }
 867
 868         /* okay, it's an ordinary query */
 869         tlist = parse->targetList;
 870         rt = parse->rtable;
 871         cmd = parse->commandType;
 872
 873         /*
 874          * test 2:      if the function is declared to return no value, then the
 875          * final query had better not be a retrieve.
 876          */
 877         if (rettype == InvalidOid)
 878         {
 879                 if (cmd == CMD_SELECT)
 880                         elog(ERROR,
 881                                  "function declared with no return type, but final query is a retrieve");
 882                 else
 883                         return;
 884         }
 885
 886         /* by here, the function is declared to return some type */
 887         if ((typ = typeidType(rettype)) == NULL)
 888                 elog(ERROR, "can't find return type %u for function\n", rettype);
 889
 890         /*
 891          * test 3:      if the function is declared to return a value, then the
 892          * final query had better be a retrieve.
 893          */
 894         if (cmd != CMD_SELECT)
 895                 elog(ERROR, "function declared to return type %s, but final query is not a retrieve", typeTypeName(typ));
 896
 897         /*
 898          * test 4:      for base type returns, the target list should have exactly
 899          * one entry, and its type should agree with what the user declared.
 900          */
 901
 902         if (typeTypeRelid(typ) == InvalidOid)
 903         {
 904                 if (ExecTargetListLength(tlist) > 1)
 905                         elog(ERROR, "function declared to return %s returns multiple values in final retrieve", typeTypeName(typ));
 906
 907                 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
 908                 if (resnode->restype != rettype)
 909                         elog(ERROR, "return type mismatch in function: declared to return %s, returns %s", typeTypeName(typ), typeidTypeName(resnode->restype));
 910
 911                 /* by here, base return types match */
 912                 return;
 913         }
 914
 915         /*
 916          * If the target list is of length 1, and the type of the varnode in
 917          * the target list is the same as the declared return type, this is
 918          * okay.  This can happen, for example, where the body of the function
 919          * is 'retrieve (x = func2())', where func2 has the same return type
 920          * as the function that's calling it.
 921          */
 922         if (ExecTargetListLength(tlist) == 1)
 923         {
 924                 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
 925                 if (resnode->restype == rettype)
 926                         return;
 927         }
 928
 929         /*
 930          * By here, the procedure returns a (set of) tuples.  This part of the
 931          * typechecking is a hack.      We look up the relation that is the
 932          * declared return type, and be sure that attributes 1 .. n in the
 933          * target list match the declared types.
 934          */
 935         reln = heap_open(typeTypeRelid(typ), AccessShareLock);
 936         relid = reln->rd_id;
 937         relnatts = reln->rd_rel->relnatts;
 938
 939         if (ExecTargetListLength(tlist) != relnatts)
 940                 elog(ERROR, "function declared to return type %s does not retrieve (%s.*)", typeTypeName(typ), typeTypeName(typ));
 941
 942         /* expect attributes 1 .. n in order */
 943         for (i = 1; i <= relnatts; i++)
 944         {
 945                 TargetEntry *tle = lfirst(tlist);
 946                 Node       *thenode = tle->expr;
 947                 Oid                     tletype = exprType(thenode);
 948
 949                 if (tletype != reln->rd_att->attrs[i - 1]->atttypid)
 950                         elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 951                 tlist = lnext(tlist);
 952         }
 953
 954         heap_close(reln, AccessShareLock);
 955 }