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