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