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