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-2001, PostgreSQL Global Development Group
   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.116 2002/04/28 19:54:28 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "catalog/pg_type.h"
  19 #include "nodes/makefuncs.h"
  20 #ifdef OPTIMIZER_DEBUG
  21 #include "nodes/print.h"
  22 #endif
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/paths.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/planner.h"
  27 #include "optimizer/prep.h"
  28 #include "optimizer/subselect.h"
  29 #include "optimizer/tlist.h"
  30 #include "optimizer/var.h"
  31 #include "parser/analyze.h"
  32 #include "parser/parsetree.h"
  33 #include "parser/parse_expr.h"
  34 #include "rewrite/rewriteManip.h"
  35 #include "utils/lsyscache.h"
  36
  37
  38 /* Expression kind codes for preprocess_expression */
  39 #define EXPRKIND_TARGET 0
  40 #define EXPRKIND_WHERE  1
  41 #define EXPRKIND_HAVING 2
  42
  43
  44 static Node *pull_up_subqueries(Query *parse, Node *jtnode,
  45                                                                 bool below_outer_join);
  46 static bool is_simple_subquery(Query *subquery);
  47 static bool has_nullable_targetlist(Query *subquery);
  48 static void resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist);
  49 static Node *preprocess_jointree(Query *parse, Node *jtnode);
  50 static Node *preprocess_expression(Query *parse, Node *expr, int kind);
  51 static void preprocess_qual_conditions(Query *parse, Node *jtnode);
  52 static Plan *inheritance_planner(Query *parse, List *inheritlist);
  53 static Plan *grouping_planner(Query *parse, double tuple_fraction);
  54 static List *make_subplanTargetList(Query *parse, List *tlist,
  55                                            AttrNumber **groupColIdx);
  56 static Plan *make_groupplan(Query *parse,
  57                            List *group_tlist, bool tuplePerGroup,
  58                            List *groupClause, AttrNumber *grpColIdx,
  59                            bool is_presorted, Plan *subplan);
  60 static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
  61
  62
  63 /*****************************************************************************
  64  *
  65  *         Query optimizer entry point
  66  *
  67  *****************************************************************************/
  68 Plan *
  69 planner(Query *parse)
  70 {
  71         Plan       *result_plan;
  72         Index           save_PlannerQueryLevel;
  73         List       *save_PlannerParamVar;
  74
  75         /*
  76          * The planner can be called recursively (an example is when
  77          * eval_const_expressions tries to pre-evaluate an SQL function). So,
  78          * these global state variables must be saved and restored.
  79          *
  80          * These vars cannot be moved into the Query structure since their whole
  81          * purpose is communication across multiple sub-Queries.
  82          *
  83          * Note we do NOT save and restore PlannerPlanId: it exists to assign
  84          * unique IDs to SubPlan nodes, and we want those IDs to be unique for
  85          * the life of a backend.  Also, PlannerInitPlan is saved/restored in
  86          * subquery_planner, not here.
  87          */
  88         save_PlannerQueryLevel = PlannerQueryLevel;
  89         save_PlannerParamVar = PlannerParamVar;
  90
  91         /* Initialize state for handling outer-level references and params */
  92         PlannerQueryLevel = 0;          /* will be 1 in top-level subquery_planner */
  93         PlannerParamVar = NIL;
  94
  95         /* primary planning entry point (may recurse for subqueries) */
  96         result_plan = subquery_planner(parse, -1.0 /* default case */ );
  97
  98         Assert(PlannerQueryLevel == 0);
  99
 100         /* executor wants to know total number of Params used overall */
 101         result_plan->nParamExec = length(PlannerParamVar);
 102
 103         /* final cleanup of the plan */
 104         set_plan_references(parse, result_plan);
 105
 106         /* restore state for outer planner, if any */
 107         PlannerQueryLevel = save_PlannerQueryLevel;
 108         PlannerParamVar = save_PlannerParamVar;
 109
 110         return result_plan;
 111 }
 112
 113
 114 /*--------------------
 115  * subquery_planner
 116  *        Invokes the planner on a subquery.  We recurse to here for each
 117  *        sub-SELECT found in the query tree.
 118  *
 119  * parse is the querytree produced by the parser & rewriter.
 120  * tuple_fraction is the fraction of tuples we expect will be retrieved.
 121  * tuple_fraction is interpreted as explained for grouping_planner, below.
 122  *
 123  * Basically, this routine does the stuff that should only be done once
 124  * per Query object.  It then calls grouping_planner.  At one time,
 125  * grouping_planner could be invoked recursively on the same Query object;
 126  * that's not currently true, but we keep the separation between the two
 127  * routines anyway, in case we need it again someday.
 128  *
 129  * subquery_planner will be called recursively to handle sub-Query nodes
 130  * found within the query's expressions and rangetable.
 131  *
 132  * Returns a query plan.
 133  *--------------------
 134  */
 135 Plan *
 136 subquery_planner(Query *parse, double tuple_fraction)
 137 {
 138         List       *saved_initplan = PlannerInitPlan;
 139         int                     saved_planid = PlannerPlanId;
 140         Plan       *plan;
 141         List       *newHaving;
 142         List       *lst;
 143
 144         /* Set up for a new level of subquery */
 145         PlannerQueryLevel++;
 146         PlannerInitPlan = NIL;
 147
 148 #ifdef ENABLE_KEY_SET_QUERY
 149         /* this should go away sometime soon */
 150         transformKeySetQuery(parse);
 151 #endif
 152
 153         /*
 154          * Check to see if any subqueries in the rangetable can be merged into
 155          * this query.
 156          */
 157         parse->jointree = (FromExpr *)
 158                 pull_up_subqueries(parse, (Node *) parse->jointree, false);
 159
 160         /*
 161          * If so, we may have created opportunities to simplify the jointree.
 162          */
 163         parse->jointree = (FromExpr *)
 164                 preprocess_jointree(parse, (Node *) parse->jointree);
 165
 166         /*
 167          * Do expression preprocessing on targetlist and quals.
 168          */
 169         parse->targetList = (List *)
 170                 preprocess_expression(parse, (Node *) parse->targetList,
 171                                                           EXPRKIND_TARGET);
 172
 173         preprocess_qual_conditions(parse, (Node *) parse->jointree);
 174
 175         parse->havingQual = preprocess_expression(parse, parse->havingQual,
 176                                                                                           EXPRKIND_HAVING);
 177
 178         /*
 179          * Check for ungrouped variables passed to subplans in targetlist and
 180          * HAVING clause (but not in WHERE or JOIN/ON clauses, since those are
 181          * evaluated before grouping).  We can't do this any earlier because
 182          * we must use the preprocessed targetlist for comparisons of grouped
 183          * expressions.
 184          */
 185         if (parse->hasSubLinks &&
 186                 (parse->groupClause != NIL || parse->hasAggs))
 187                 check_subplans_for_ungrouped_vars(parse);
 188
 189         /*
 190          * A HAVING clause without aggregates is equivalent to a WHERE clause
 191          * (except it can only refer to grouped fields).  Transfer any
 192          * agg-free clauses of the HAVING qual into WHERE.      This may seem like
 193          * wasting cycles to cater to stupidly-written queries, but there are
 194          * other reasons for doing it.  Firstly, if the query contains no aggs
 195          * at all, then we aren't going to generate an Agg plan node, and so
 196          * there'll be no place to execute HAVING conditions; without this
 197          * transfer, we'd lose the HAVING condition entirely, which is wrong.
 198          * Secondly, when we push down a qual condition into a sub-query, it's
 199          * easiest to push the qual into HAVING always, in case it contains
 200          * aggs, and then let this code sort it out.
 201          *
 202          * Note that both havingQual and parse->jointree->quals are in
 203          * implicitly-ANDed-list form at this point, even though they are
 204          * declared as Node *.  Also note that contain_agg_clause does not
 205          * recurse into sub-selects, which is exactly what we need here.
 206          */
 207         newHaving = NIL;
 208         foreach(lst, (List *) parse->havingQual)
 209         {
 210                 Node       *havingclause = (Node *) lfirst(lst);
 211
 212                 if (contain_agg_clause(havingclause))
 213                         newHaving = lappend(newHaving, havingclause);
 214                 else
 215                         parse->jointree->quals = (Node *)
 216                                 lappend((List *) parse->jointree->quals, havingclause);
 217         }
 218         parse->havingQual = (Node *) newHaving;
 219
 220         /*
 221          * Do the main planning.  If we have an inherited target relation,
 222          * that needs special processing, else go straight to
 223          * grouping_planner.
 224          */
 225         if (parse->resultRelation &&
 226          (lst = expand_inherted_rtentry(parse, parse->resultRelation, false))
 227                 != NIL)
 228                 plan = inheritance_planner(parse, lst);
 229         else
 230                 plan = grouping_planner(parse, tuple_fraction);
 231
 232         /*
 233          * If any subplans were generated, or if we're inside a subplan, build
 234          * subPlan, extParam and locParam lists for plan nodes.
 235          */
 236         if (PlannerPlanId != saved_planid || PlannerQueryLevel > 1)
 237         {
 238                 (void) SS_finalize_plan(plan);
 239
 240                 /*
 241                  * At the moment, SS_finalize_plan doesn't handle initPlans and so
 242                  * we assign them to the topmost plan node.
 243                  */
 244                 plan->initPlan = PlannerInitPlan;
 245                 /* Must add the initPlans' extParams to the topmost node's, too */
 246                 foreach(lst, plan->initPlan)
 247                 {
 248                         SubPlan    *subplan = (SubPlan *) lfirst(lst);
 249
 250                         plan->extParam = set_unioni(plan->extParam,
 251                                                                                 subplan->plan->extParam);
 252                 }
 253         }
 254
 255         /* Return to outer subquery context */
 256         PlannerQueryLevel--;
 257         PlannerInitPlan = saved_initplan;
 258         /* we do NOT restore PlannerPlanId; that's not an oversight! */
 259
 260         return plan;
 261 }
 262
 263 /*
 264  * pull_up_subqueries
 265  *              Look for subqueries in the rangetable that can be pulled up into
 266  *              the parent query.  If the subquery has no special features like
 267  *              grouping/aggregation then we can merge it into the parent's jointree.
 268  *
 269  * below_outer_join is true if this jointree node is within the nullable
 270  * side of an outer join.  This restricts what we can do.
 271  *
 272  * A tricky aspect of this code is that if we pull up a subquery we have
 273  * to replace Vars that reference the subquery's outputs throughout the
 274  * parent query, including quals attached to jointree nodes above the one
 275  * we are currently processing!  We handle this by being careful not to
 276  * change the jointree structure while recursing: no nodes other than
 277  * subquery RangeTblRef entries will be replaced.  Also, we can't turn
 278  * ResolveNew loose on the whole jointree, because it'll return a mutated
 279  * copy of the tree; we have to invoke it just on the quals, instead.
 280  */
 281 static Node *
 282 pull_up_subqueries(Query *parse, Node *jtnode, bool below_outer_join)
 283 {
 284         if (jtnode == NULL)
 285                 return NULL;
 286         if (IsA(jtnode, RangeTblRef))
 287         {
 288                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 289                 RangeTblEntry *rte = rt_fetch(varno, parse->rtable);
 290                 Query      *subquery = rte->subquery;
 291
 292                 /*
 293                  * Is this a subquery RTE, and if so, is the subquery simple
 294                  * enough to pull up?  (If not, do nothing at this node.)
 295                  *
 296                  * If we are inside an outer join, only pull up subqueries whose
 297                  * targetlists are nullable --- otherwise substituting their tlist
 298                  * entries for upper Var references would do the wrong thing
 299                  * (the results wouldn't become NULL when they're supposed to).
 300                  * XXX This could be improved by generating pseudo-variables for
 301                  * such expressions; we'd have to figure out how to get the pseudo-
 302                  * variables evaluated at the right place in the modified plan tree.
 303                  * Fix it someday.
 304                  *
 305                  * Note: even if the subquery itself is simple enough, we can't pull
 306                  * it up if there is a reference to its whole tuple result.  Perhaps
 307                  * a pseudo-variable is the answer here too.
 308                  */
 309                 if (rte->rtekind == RTE_SUBQUERY && is_simple_subquery(subquery) &&
 310                         (!below_outer_join || has_nullable_targetlist(subquery)) &&
 311                         !contain_whole_tuple_var((Node *) parse, varno, 0))
 312                 {
 313                         int                     rtoffset;
 314                         List       *subtlist;
 315                         List       *rt;
 316
 317                         /*
 318                          * First, recursively pull up the subquery's subqueries, so
 319                          * that this routine's processing is complete for its jointree
 320                          * and rangetable.      NB: if the same subquery is referenced
 321                          * from multiple jointree items (which can't happen normally,
 322                          * but might after rule rewriting), then we will invoke this
 323                          * processing multiple times on that subquery.  OK because
 324                          * nothing will happen after the first time.  We do have to be
 325                          * careful to copy everything we pull up, however, or risk
 326                          * having chunks of structure multiply linked.
 327                          */
 328                         subquery->jointree = (FromExpr *)
 329                                 pull_up_subqueries(subquery, (Node *) subquery->jointree,
 330                                                                    below_outer_join);
 331
 332                         /*
 333                          * Now make a modifiable copy of the subquery that we can
 334                          * run OffsetVarNodes on.
 335                          */
 336                         subquery = copyObject(subquery);
 337
 338                         /*
 339                          * Adjust varnos in subquery so that we can append its
 340                          * rangetable to upper query's.
 341                          */
 342                         rtoffset = length(parse->rtable);
 343                         OffsetVarNodes((Node *) subquery, rtoffset, 0);
 344
 345                         /*
 346                          * Replace all of the top query's references to the subquery's
 347                          * outputs with copies of the adjusted subtlist items, being
 348                          * careful not to replace any of the jointree structure.
 349                          * (This'd be a lot cleaner if we could use query_tree_mutator.)
 350                          */
 351                         subtlist = subquery->targetList;
 352                         parse->targetList = (List *)
 353                                 ResolveNew((Node *) parse->targetList,
 354                                                    varno, 0, subtlist, CMD_SELECT, 0);
 355                         resolvenew_in_jointree((Node *) parse->jointree, varno, subtlist);
 356                         Assert(parse->setOperations == NULL);
 357                         parse->havingQual =
 358                                 ResolveNew(parse->havingQual,
 359                                                    varno, 0, subtlist, CMD_SELECT, 0);
 360
 361                         foreach(rt, parse->rtable)
 362                         {
 363                                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
 364
 365                                 if (rte->rtekind == RTE_JOIN)
 366                                         rte->joinaliasvars = (List *)
 367                                                 ResolveNew((Node *) rte->joinaliasvars,
 368                                                                    varno, 0, subtlist, CMD_SELECT, 0);
 369                         }
 370
 371                         /*
 372                          * Now append the adjusted rtable entries to upper query.
 373                          * (We hold off until after fixing the upper rtable entries;
 374                          * no point in running that code on the subquery ones too.)
 375                          */
 376                         parse->rtable = nconc(parse->rtable, subquery->rtable);
 377
 378                         /*
 379                          * Pull up any FOR UPDATE markers, too.  (OffsetVarNodes
 380                          * already adjusted the marker values, so just nconc the list.)
 381                          */
 382                         parse->rowMarks = nconc(parse->rowMarks, subquery->rowMarks);
 383
 384                         /*
 385                          * Miscellaneous housekeeping.
 386                          */
 387                         parse->hasSubLinks |= subquery->hasSubLinks;
 388                         /* subquery won't be pulled up if it hasAggs, so no work there */
 389
 390                         /*
 391                          * Return the adjusted subquery jointree to replace the
 392                          * RangeTblRef entry in my jointree.
 393                          */
 394                         return (Node *) subquery->jointree;
 395                 }
 396         }
 397         else if (IsA(jtnode, FromExpr))
 398         {
 399                 FromExpr   *f = (FromExpr *) jtnode;
 400                 List       *l;
 401
 402                 foreach(l, f->fromlist)
 403                         lfirst(l) = pull_up_subqueries(parse, lfirst(l),
 404                                                                                    below_outer_join);
 405         }
 406         else if (IsA(jtnode, JoinExpr))
 407         {
 408                 JoinExpr   *j = (JoinExpr *) jtnode;
 409
 410                 /* Recurse, being careful to tell myself when inside outer join */
 411                 switch (j->jointype)
 412                 {
 413                         case JOIN_INNER:
 414                                 j->larg = pull_up_subqueries(parse, j->larg,
 415                                                                                          below_outer_join);
 416                                 j->rarg = pull_up_subqueries(parse, j->rarg,
 417                                                                                          below_outer_join);
 418                                 break;
 419                         case JOIN_LEFT:
 420                                 j->larg = pull_up_subqueries(parse, j->larg,
 421                                                                                          below_outer_join);
 422                                 j->rarg = pull_up_subqueries(parse, j->rarg,
 423                                                                                          true);
 424                                 break;
 425                         case JOIN_FULL:
 426                                 j->larg = pull_up_subqueries(parse, j->larg,
 427                                                                                          true);
 428                                 j->rarg = pull_up_subqueries(parse, j->rarg,
 429                                                                                          true);
 430                                 break;
 431                         case JOIN_RIGHT:
 432                                 j->larg = pull_up_subqueries(parse, j->larg,
 433                                                                                          true);
 434                                 j->rarg = pull_up_subqueries(parse, j->rarg,
 435                                                                                          below_outer_join);
 436                                 break;
 437                         case JOIN_UNION:
 438
 439                                 /*
 440                                  * This is where we fail if upper levels of planner
 441                                  * haven't rewritten UNION JOIN as an Append ...
 442                                  */
 443                                 elog(ERROR, "UNION JOIN is not implemented yet");
 444                                 break;
 445                         default:
 446                                 elog(ERROR, "pull_up_subqueries: unexpected join type %d",
 447                                          j->jointype);
 448                                 break;
 449                 }
 450         }
 451         else
 452                 elog(ERROR, "pull_up_subqueries: unexpected node type %d",
 453                          nodeTag(jtnode));
 454         return jtnode;
 455 }
 456
 457 /*
 458  * is_simple_subquery
 459  *        Check a subquery in the range table to see if it's simple enough
 460  *        to pull up into the parent query.
 461  */
 462 static bool
 463 is_simple_subquery(Query *subquery)
 464 {
 465         /*
 466          * Let's just make sure it's a valid subselect ...
 467          */
 468         if (!IsA(subquery, Query) ||
 469                 subquery->commandType != CMD_SELECT ||
 470                 subquery->resultRelation != 0 ||
 471                 subquery->into != NULL ||
 472                 subquery->isPortal)
 473                 elog(ERROR, "is_simple_subquery: subquery is bogus");
 474
 475         /*
 476          * Can't currently pull up a query with setops. Maybe after querytree
 477          * redesign...
 478          */
 479         if (subquery->setOperations)
 480                 return false;
 481
 482         /*
 483          * Can't pull up a subquery involving grouping, aggregation, sorting,
 484          * or limiting.
 485          */
 486         if (subquery->hasAggs ||
 487                 subquery->groupClause ||
 488                 subquery->havingQual ||
 489                 subquery->sortClause ||
 490                 subquery->distinctClause ||
 491                 subquery->limitOffset ||
 492                 subquery->limitCount)
 493                 return false;
 494
 495         /*
 496          * Don't pull up a subquery that has any set-returning functions in
 497          * its targetlist.  Otherwise we might well wind up inserting
 498          * set-returning functions into places where they mustn't go,
 499          * such as quals of higher queries.
 500          */
 501         if (contain_iter_clause((Node *) subquery->targetList))
 502                 return false;
 503
 504         /*
 505          * Hack: don't try to pull up a subquery with an empty jointree.
 506          * query_planner() will correctly generate a Result plan for a
 507          * jointree that's totally empty, but I don't think the right things
 508          * happen if an empty FromExpr appears lower down in a jointree. Not
 509          * worth working hard on this, just to collapse SubqueryScan/Result
 510          * into Result...
 511          */
 512         if (subquery->jointree->fromlist == NIL)
 513                 return false;
 514
 515         return true;
 516 }
 517
 518 /*
 519  * has_nullable_targetlist
 520  *        Check a subquery in the range table to see if all the non-junk
 521  *        targetlist items are simple variables (and, hence, will correctly
 522  *        go to NULL when examined above the point of an outer join).
 523  *
 524  * A possible future extension is to accept strict functions of simple
 525  * variables, eg, "x + 1".
 526  */
 527 static bool
 528 has_nullable_targetlist(Query *subquery)
 529 {
 530         List       *l;
 531
 532         foreach(l, subquery->targetList)
 533         {
 534                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 535
 536                 /* ignore resjunk columns */
 537                 if (tle->resdom->resjunk)
 538                         continue;
 539
 540                 /* Okay if tlist item is a simple Var */
 541                 if (tle->expr && IsA(tle->expr, Var))
 542                         continue;
 543
 544                 return false;
 545         }
 546         return true;
 547 }
 548
 549 /*
 550  * Helper routine for pull_up_subqueries: do ResolveNew on every expression
 551  * in the jointree, without changing the jointree structure itself.  Ugly,
 552  * but there's no other way...
 553  */
 554 static void
 555 resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist)
 556 {
 557         if (jtnode == NULL)
 558                 return;
 559         if (IsA(jtnode, RangeTblRef))
 560         {
 561                 /* nothing to do here */
 562         }
 563         else if (IsA(jtnode, FromExpr))
 564         {
 565                 FromExpr   *f = (FromExpr *) jtnode;
 566                 List       *l;
 567
 568                 foreach(l, f->fromlist)
 569                         resolvenew_in_jointree(lfirst(l), varno, subtlist);
 570                 f->quals = ResolveNew(f->quals,
 571                                                           varno, 0, subtlist, CMD_SELECT, 0);
 572         }
 573         else if (IsA(jtnode, JoinExpr))
 574         {
 575                 JoinExpr   *j = (JoinExpr *) jtnode;
 576
 577                 resolvenew_in_jointree(j->larg, varno, subtlist);
 578                 resolvenew_in_jointree(j->rarg, varno, subtlist);
 579                 j->quals = ResolveNew(j->quals,
 580                                                           varno, 0, subtlist, CMD_SELECT, 0);
 581
 582                 /*
 583                  * We don't bother to update the colvars list, since it won't be
 584                  * used again ...
 585                  */
 586         }
 587         else
 588                 elog(ERROR, "resolvenew_in_jointree: unexpected node type %d",
 589                          nodeTag(jtnode));
 590 }
 591
 592 /*
 593  * preprocess_jointree
 594  *              Attempt to simplify a query's jointree.
 595  *
 596  * If we succeed in pulling up a subquery then we might form a jointree
 597  * in which a FromExpr is a direct child of another FromExpr.  In that
 598  * case we can consider collapsing the two FromExprs into one.  This is
 599  * an optional conversion, since the planner will work correctly either
 600  * way.  But we may find a better plan (at the cost of more planning time)
 601  * if we merge the two nodes.
 602  *
 603  * NOTE: don't try to do this in the same jointree scan that does subquery
 604  * pullup!      Since we're changing the jointree structure here, that wouldn't
 605  * work reliably --- see comments for pull_up_subqueries().
 606  */
 607 static Node *
 608 preprocess_jointree(Query *parse, Node *jtnode)
 609 {
 610         if (jtnode == NULL)
 611                 return NULL;
 612         if (IsA(jtnode, RangeTblRef))
 613         {
 614                 /* nothing to do here... */
 615         }
 616         else if (IsA(jtnode, FromExpr))
 617         {
 618                 FromExpr   *f = (FromExpr *) jtnode;
 619                 List       *newlist = NIL;
 620                 List       *l;
 621
 622                 foreach(l, f->fromlist)
 623                 {
 624                         Node       *child = (Node *) lfirst(l);
 625
 626                         /* Recursively simplify the child... */
 627                         child = preprocess_jointree(parse, child);
 628                         /* Now, is it a FromExpr? */
 629                         if (child && IsA(child, FromExpr))
 630                         {
 631                                 /*
 632                                  * Yes, so do we want to merge it into parent?  Always do
 633                                  * so if child has just one element (since that doesn't
 634                                  * make the parent's list any longer).  Otherwise we have
 635                                  * to be careful about the increase in planning time
 636                                  * caused by combining the two join search spaces into
 637                                  * one.  Our heuristic is to merge if the merge will
 638                                  * produce a join list no longer than GEQO_RELS/2.
 639                                  * (Perhaps need an additional user parameter?)
 640                                  */
 641                                 FromExpr   *subf = (FromExpr *) child;
 642                                 int                     childlen = length(subf->fromlist);
 643                                 int                     myothers = length(newlist) + length(lnext(l));
 644
 645                                 if (childlen <= 1 || (childlen + myothers) <= geqo_rels / 2)
 646                                 {
 647                                         newlist = nconc(newlist, subf->fromlist);
 648                                         f->quals = make_and_qual(f->quals, subf->quals);
 649                                 }
 650                                 else
 651                                         newlist = lappend(newlist, child);
 652                         }
 653                         else
 654                                 newlist = lappend(newlist, child);
 655                 }
 656                 f->fromlist = newlist;
 657         }
 658         else if (IsA(jtnode, JoinExpr))
 659         {
 660                 JoinExpr   *j = (JoinExpr *) jtnode;
 661
 662                 /* Can't usefully change the JoinExpr, but recurse on children */
 663                 j->larg = preprocess_jointree(parse, j->larg);
 664                 j->rarg = preprocess_jointree(parse, j->rarg);
 665         }
 666         else
 667                 elog(ERROR, "preprocess_jointree: unexpected node type %d",
 668                          nodeTag(jtnode));
 669         return jtnode;
 670 }
 671
 672 /*
 673  * preprocess_expression
 674  *              Do subquery_planner's preprocessing work for an expression,
 675  *              which can be a targetlist, a WHERE clause (including JOIN/ON
 676  *              conditions), or a HAVING clause.
 677  */
 678 static Node *
 679 preprocess_expression(Query *parse, Node *expr, int kind)
 680 {
 681         bool            has_join_rtes;
 682         List       *rt;
 683
 684         /*
 685          * Simplify constant expressions.
 686          *
 687          * Note that at this point quals have not yet been converted to
 688          * implicit-AND form, so we can apply eval_const_expressions directly.
 689          * Also note that we need to do this before SS_process_sublinks,
 690          * because that routine inserts bogus "Const" nodes.
 691          */
 692         expr = eval_const_expressions(expr);
 693
 694         /*
 695          * If it's a qual or havingQual, canonicalize it, and convert it to
 696          * implicit-AND format.
 697          *
 698          * XXX Is there any value in re-applying eval_const_expressions after
 699          * canonicalize_qual?
 700          */
 701         if (kind != EXPRKIND_TARGET)
 702         {
 703                 expr = (Node *) canonicalize_qual((Expr *) expr, true);
 704
 705 #ifdef OPTIMIZER_DEBUG
 706                 printf("After canonicalize_qual()\n");
 707                 pprint(expr);
 708 #endif
 709         }
 710
 711         /* Expand SubLinks to SubPlans */
 712         if (parse->hasSubLinks)
 713                 expr = SS_process_sublinks(expr);
 714
 715         /* Replace uplevel vars with Param nodes */
 716         if (PlannerQueryLevel > 1)
 717                 expr = SS_replace_correlation_vars(expr);
 718
 719         /*
 720          * If the query has any join RTEs, try to replace join alias variables
 721          * with base-relation variables, to allow quals to be pushed down.
 722          * We must do this after sublink processing, since it does not recurse
 723          * into sublinks.
 724          *
 725          * The flattening pass is expensive enough that it seems worthwhile to
 726          * scan the rangetable to see if we can avoid it.
 727          */
 728         has_join_rtes = false;
 729         foreach(rt, parse->rtable)
 730         {
 731                 RangeTblEntry *rte = lfirst(rt);
 732
 733                 if (rte->rtekind == RTE_JOIN)
 734                 {
 735                         has_join_rtes = true;
 736                         break;
 737                 }
 738         }
 739         if (has_join_rtes)
 740                 expr = flatten_join_alias_vars(expr, parse, false);
 741
 742         return expr;
 743 }
 744
 745 /*
 746  * preprocess_qual_conditions
 747  *              Recursively scan the query's jointree and do subquery_planner's
 748  *              preprocessing work on each qual condition found therein.
 749  */
 750 static void
 751 preprocess_qual_conditions(Query *parse, Node *jtnode)
 752 {
 753         if (jtnode == NULL)
 754                 return;
 755         if (IsA(jtnode, RangeTblRef))
 756         {
 757                 /* nothing to do here */
 758         }
 759         else if (IsA(jtnode, FromExpr))
 760         {
 761                 FromExpr   *f = (FromExpr *) jtnode;
 762                 List       *l;
 763
 764                 foreach(l, f->fromlist)
 765                         preprocess_qual_conditions(parse, lfirst(l));
 766
 767                 f->quals = preprocess_expression(parse, f->quals, EXPRKIND_WHERE);
 768         }
 769         else if (IsA(jtnode, JoinExpr))
 770         {
 771                 JoinExpr   *j = (JoinExpr *) jtnode;
 772
 773                 preprocess_qual_conditions(parse, j->larg);
 774                 preprocess_qual_conditions(parse, j->rarg);
 775
 776                 j->quals = preprocess_expression(parse, j->quals, EXPRKIND_WHERE);
 777         }
 778         else
 779                 elog(ERROR, "preprocess_qual_conditions: unexpected node type %d",
 780                          nodeTag(jtnode));
 781 }
 782
 783 /*--------------------
 784  * inheritance_planner
 785  *        Generate a plan in the case where the result relation is an
 786  *        inheritance set.
 787  *
 788  * We have to handle this case differently from cases where a source
 789  * relation is an inheritance set.      Source inheritance is expanded at
 790  * the bottom of the plan tree (see allpaths.c), but target inheritance
 791  * has to be expanded at the top.  The reason is that for UPDATE, each
 792  * target relation needs a different targetlist matching its own column
 793  * set.  (This is not so critical for DELETE, but for simplicity we treat
 794  * inherited DELETE the same way.)      Fortunately, the UPDATE/DELETE target
 795  * can never be the nullable side of an outer join, so it's OK to generate
 796  * the plan this way.
 797  *
 798  * parse is the querytree produced by the parser & rewriter.
 799  * inheritlist is an integer list of RT indexes for the result relation set.
 800  *
 801  * Returns a query plan.
 802  *--------------------
 803  */
 804 static Plan *
 805 inheritance_planner(Query *parse, List *inheritlist)
 806 {
 807         int                     parentRTindex = parse->resultRelation;
 808         Oid                     parentOID = getrelid(parentRTindex, parse->rtable);
 809         List       *subplans = NIL;
 810         List       *tlist = NIL;
 811         List       *l;
 812
 813         foreach(l, inheritlist)
 814         {
 815                 int                     childRTindex = lfirsti(l);
 816                 Oid                     childOID = getrelid(childRTindex, parse->rtable);
 817                 Query      *subquery;
 818                 Plan       *subplan;
 819
 820                 /* Generate modified query with this rel as target */
 821                 subquery = (Query *) adjust_inherited_attrs((Node *) parse,
 822                                                                                                 parentRTindex, parentOID,
 823                                                                                                  childRTindex, childOID);
 824                 /* Generate plan */
 825                 subplan = grouping_planner(subquery, 0.0 /* retrieve all tuples */ );
 826                 subplans = lappend(subplans, subplan);
 827                 /* Save preprocessed tlist from first rel for use in Append */
 828                 if (tlist == NIL)
 829                         tlist = subplan->targetlist;
 830         }
 831
 832         /* Save the target-relations list for the executor, too */
 833         parse->resultRelations = inheritlist;
 834
 835         return (Plan *) make_append(subplans, true, tlist);
 836 }
 837
 838 /*--------------------
 839  * grouping_planner
 840  *        Perform planning steps related to grouping, aggregation, etc.
 841  *        This primarily means adding top-level processing to the basic
 842  *        query plan produced by query_planner.
 843  *
 844  * parse is the querytree produced by the parser & rewriter.
 845  * tuple_fraction is the fraction of tuples we expect will be retrieved
 846  *
 847  * tuple_fraction is interpreted as follows:
 848  *        < 0: determine fraction by inspection of query (normal case)
 849  *        0: expect all tuples to be retrieved
 850  *        0 < tuple_fraction < 1: expect the given fraction of tuples available
 851  *              from the plan to be retrieved
 852  *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
 853  *              expected to be retrieved (ie, a LIMIT specification)
 854  * The normal case is to pass -1, but some callers pass values >= 0 to
 855  * override this routine's determination of the appropriate fraction.
 856  *
 857  * Returns a query plan.
 858  *--------------------
 859  */
 860 static Plan *
 861 grouping_planner(Query *parse, double tuple_fraction)
 862 {
 863         List       *tlist = parse->targetList;
 864         Plan       *result_plan;
 865         List       *current_pathkeys;
 866         List       *group_pathkeys;
 867         List       *sort_pathkeys;
 868         AttrNumber *groupColIdx = NULL;
 869
 870         if (parse->setOperations)
 871         {
 872                 /*
 873                  * Construct the plan for set operations.  The result will not
 874                  * need any work except perhaps a top-level sort and/or LIMIT.
 875                  */
 876                 result_plan = plan_set_operations(parse);
 877
 878                 /*
 879                  * We should not need to call preprocess_targetlist, since we must
 880                  * be in a SELECT query node.  Instead, use the targetlist
 881                  * returned by plan_set_operations (since this tells whether it
 882                  * returned any resjunk columns!), and transfer any sort key
 883                  * information from the original tlist.
 884                  */
 885                 Assert(parse->commandType == CMD_SELECT);
 886
 887                 tlist = postprocess_setop_tlist(result_plan->targetlist, tlist);
 888
 889                 /*
 890                  * Can't handle FOR UPDATE here (parser should have checked
 891                  * already, but let's make sure).
 892                  */
 893                 if (parse->rowMarks)
 894                         elog(ERROR, "SELECT FOR UPDATE is not allowed with UNION/INTERSECT/EXCEPT");
 895
 896                 /*
 897                  * We set current_pathkeys NIL indicating we do not know sort
 898                  * order.  This is correct when the top set operation is UNION
 899                  * ALL, since the appended-together results are unsorted even if
 900                  * the subplans were sorted.  For other set operations we could be
 901                  * smarter --- room for future improvement!
 902                  */
 903                 current_pathkeys = NIL;
 904
 905                 /*
 906                  * Calculate pathkeys that represent grouping/ordering
 907                  * requirements (grouping should always be null, but...)
 908                  */
 909                 group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
 910                                                                                                            tlist);
 911                 sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
 912                                                                                                           tlist);
 913         }
 914         else
 915         {
 916                 List       *sub_tlist;
 917
 918                 /* Preprocess targetlist in case we are inside an INSERT/UPDATE. */
 919                 tlist = preprocess_targetlist(tlist,
 920                                                                           parse->commandType,
 921                                                                           parse->resultRelation,
 922                                                                           parse->rtable);
 923
 924                 /*
 925                  * Add TID targets for rels selected FOR UPDATE (should this be
 926                  * done in preprocess_targetlist?).  The executor uses the TID to
 927                  * know which rows to lock, much as for UPDATE or DELETE.
 928                  */
 929                 if (parse->rowMarks)
 930                 {
 931                         List       *l;
 932
 933                         /*
 934                          * We've got trouble if the FOR UPDATE appears inside
 935                          * grouping, since grouping renders a reference to individual
 936                          * tuple CTIDs invalid.  This is also checked at parse time,
 937                          * but that's insufficient because of rule substitution, query
 938                          * pullup, etc.
 939                          */
 940                         CheckSelectForUpdate(parse);
 941
 942                         /*
 943                          * Currently the executor only supports FOR UPDATE at top
 944                          * level
 945                          */
 946                         if (PlannerQueryLevel > 1)
 947                                 elog(ERROR, "SELECT FOR UPDATE is not allowed in subselects");
 948
 949                         foreach(l, parse->rowMarks)
 950                         {
 951                                 Index           rti = lfirsti(l);
 952                                 char       *resname;
 953                                 Resdom     *resdom;
 954                                 Var                *var;
 955                                 TargetEntry *ctid;
 956
 957                                 resname = (char *) palloc(32);
 958                                 sprintf(resname, "ctid%u", rti);
 959                                 resdom = makeResdom(length(tlist) + 1,
 960                                                                         TIDOID,
 961                                                                         -1,
 962                                                                         resname,
 963                                                                         true);
 964
 965                                 var = makeVar(rti,
 966                                                           SelfItemPointerAttributeNumber,
 967                                                           TIDOID,
 968                                                           -1,
 969                                                           0);
 970
 971                                 ctid = makeTargetEntry(resdom, (Node *) var);
 972                                 tlist = lappend(tlist, ctid);
 973                         }
 974                 }
 975
 976                 /*
 977                  * Generate appropriate target list for subplan; may be different
 978                  * from tlist if grouping or aggregation is needed.
 979                  */
 980                 sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
 981
 982                 /*
 983                  * Calculate pathkeys that represent grouping/ordering
 984                  * requirements
 985                  */
 986                 group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
 987                                                                                                            tlist);
 988                 sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
 989                                                                                                           tlist);
 990
 991                 /*
 992                  * Figure out whether we need a sorted result from query_planner.
 993                  *
 994                  * If we have a GROUP BY clause, then we want a result sorted
 995                  * properly for grouping.  Otherwise, if there is an ORDER BY
 996                  * clause, we want to sort by the ORDER BY clause.      (Note: if we
 997                  * have both, and ORDER BY is a superset of GROUP BY, it would be
 998                  * tempting to request sort by ORDER BY --- but that might just
 999                  * leave us failing to exploit an available sort order at all.
1000                  * Needs more thought...)
1001                  */
1002                 if (parse->groupClause)
1003                         parse->query_pathkeys = group_pathkeys;
1004                 else if (parse->sortClause)
1005                         parse->query_pathkeys = sort_pathkeys;
1006                 else
1007                         parse->query_pathkeys = NIL;
1008
1009                 /*
1010                  * Figure out whether we expect to retrieve all the tuples that
1011                  * the plan can generate, or to stop early due to outside factors
1012                  * such as a cursor.  If the caller passed a value >= 0, believe
1013                  * that value, else do our own examination of the query context.
1014                  */
1015                 if (tuple_fraction < 0.0)
1016                 {
1017                         /* Initial assumption is we need all the tuples */
1018                         tuple_fraction = 0.0;
1019
1020                         /*
1021                          * Check for retrieve-into-portal, ie DECLARE CURSOR.
1022                          *
1023                          * We have no real idea how many tuples the user will ultimately
1024                          * FETCH from a cursor, but it seems a good bet that he
1025                          * doesn't want 'em all.  Optimize for 10% retrieval (you
1026                          * gotta better number?  Should this be a SETtable parameter?)
1027                          */
1028                         if (parse->isPortal)
1029                                 tuple_fraction = 0.10;
1030                 }
1031
1032                 /*
1033                  * Adjust tuple_fraction if we see that we are going to apply
1034                  * limiting/grouping/aggregation/etc.  This is not overridable by
1035                  * the caller, since it reflects plan actions that this routine
1036                  * will certainly take, not assumptions about context.
1037                  */
1038                 if (parse->limitCount != NULL)
1039                 {
1040                         /*
1041                          * A LIMIT clause limits the absolute number of tuples
1042                          * returned. However, if it's not a constant LIMIT then we
1043                          * have to punt; for lack of a better idea, assume 10% of the
1044                          * plan's result is wanted.
1045                          */
1046                         double          limit_fraction = 0.0;
1047
1048                         if (IsA(parse->limitCount, Const))
1049                         {
1050                                 Const      *limitc = (Const *) parse->limitCount;
1051                                 int32           count = DatumGetInt32(limitc->constvalue);
1052
1053                                 /*
1054                                  * A NULL-constant LIMIT represents "LIMIT ALL", which we
1055                                  * treat the same as no limit (ie, expect to retrieve all
1056                                  * the tuples).
1057                                  */
1058                                 if (!limitc->constisnull && count > 0)
1059                                 {
1060                                         limit_fraction = (double) count;
1061                                         /* We must also consider the OFFSET, if present */
1062                                         if (parse->limitOffset != NULL)
1063                                         {
1064                                                 if (IsA(parse->limitOffset, Const))
1065                                                 {
1066                                                         int32           offset;
1067
1068                                                         limitc = (Const *) parse->limitOffset;
1069                                                         offset = DatumGetInt32(limitc->constvalue);
1070                                                         if (!limitc->constisnull && offset > 0)
1071                                                                 limit_fraction += (double) offset;
1072                                                 }
1073                                                 else
1074                                                 {
1075                                                         /* OFFSET is an expression ... punt ... */
1076                                                         limit_fraction = 0.10;
1077                                                 }
1078                                         }
1079                                 }
1080                         }
1081                         else
1082                         {
1083                                 /* LIMIT is an expression ... punt ... */
1084                                 limit_fraction = 0.10;
1085                         }
1086
1087                         if (limit_fraction > 0.0)
1088                         {
1089                                 /*
1090                                  * If we have absolute limits from both caller and LIMIT,
1091                                  * use the smaller value; if one is fractional and the
1092                                  * other absolute, treat the fraction as a fraction of the
1093                                  * absolute value; else we can multiply the two fractions
1094                                  * together.
1095                                  */
1096                                 if (tuple_fraction >= 1.0)
1097                                 {
1098                                         if (limit_fraction >= 1.0)
1099                                         {
1100                                                 /* both absolute */
1101                                                 tuple_fraction = Min(tuple_fraction, limit_fraction);
1102                                         }
1103                                         else
1104                                         {
1105                                                 /* caller absolute, limit fractional */
1106                                                 tuple_fraction *= limit_fraction;
1107                                                 if (tuple_fraction < 1.0)
1108                                                         tuple_fraction = 1.0;
1109                                         }
1110                                 }
1111                                 else if (tuple_fraction > 0.0)
1112                                 {
1113                                         if (limit_fraction >= 1.0)
1114                                         {
1115                                                 /* caller fractional, limit absolute */
1116                                                 tuple_fraction *= limit_fraction;
1117                                                 if (tuple_fraction < 1.0)
1118                                                         tuple_fraction = 1.0;
1119                                         }
1120                                         else
1121                                         {
1122                                                 /* both fractional */
1123                                                 tuple_fraction *= limit_fraction;
1124                                         }
1125                                 }
1126                                 else
1127                                 {
1128                                         /* no info from caller, just use limit */
1129                                         tuple_fraction = limit_fraction;
1130                                 }
1131                         }
1132                 }
1133
1134                 if (parse->groupClause)
1135                 {
1136                         /*
1137                          * In GROUP BY mode, we have the little problem that we don't
1138                          * really know how many input tuples will be needed to make a
1139                          * group, so we can't translate an output LIMIT count into an
1140                          * input count.  For lack of a better idea, assume 25% of the
1141                          * input data will be processed if there is any output limit.
1142                          * However, if the caller gave us a fraction rather than an
1143                          * absolute count, we can keep using that fraction (which
1144                          * amounts to assuming that all the groups are about the same
1145                          * size).
1146                          */
1147                         if (tuple_fraction >= 1.0)
1148                                 tuple_fraction = 0.25;
1149
1150                         /*
1151                          * If both GROUP BY and ORDER BY are specified, we will need
1152                          * two levels of sort --- and, therefore, certainly need to
1153                          * read all the input tuples --- unless ORDER BY is a subset
1154                          * of GROUP BY.  (We have not yet canonicalized the pathkeys,
1155                          * so must use the slower noncanonical comparison method.)
1156                          */
1157                         if (parse->groupClause && parse->sortClause &&
1158                                 !noncanonical_pathkeys_contained_in(sort_pathkeys,
1159                                                                                                         group_pathkeys))
1160                                 tuple_fraction = 0.0;
1161                 }
1162                 else if (parse->hasAggs)
1163                 {
1164                         /*
1165                          * Ungrouped aggregate will certainly want all the input
1166                          * tuples.
1167                          */
1168                         tuple_fraction = 0.0;
1169                 }
1170                 else if (parse->distinctClause)
1171                 {
1172                         /*
1173                          * SELECT DISTINCT, like GROUP, will absorb an unpredictable
1174                          * number of input tuples per output tuple.  Handle the same
1175                          * way.
1176                          */
1177                         if (tuple_fraction >= 1.0)
1178                                 tuple_fraction = 0.25;
1179                 }
1180
1181                 /* Generate the basic plan for this Query */
1182                 result_plan = query_planner(parse,
1183                                                                         sub_tlist,
1184                                                                         tuple_fraction);
1185
1186                 /*
1187                  * query_planner returns actual sort order (which is not
1188                  * necessarily what we requested) in query_pathkeys.
1189                  */
1190                 current_pathkeys = parse->query_pathkeys;
1191         }
1192
1193         /*
1194          * We couldn't canonicalize group_pathkeys and sort_pathkeys before
1195          * running query_planner(), so do it now.
1196          */
1197         group_pathkeys = canonicalize_pathkeys(parse, group_pathkeys);
1198         sort_pathkeys = canonicalize_pathkeys(parse, sort_pathkeys);
1199
1200         /*
1201          * If we have a GROUP BY clause, insert a group node (plus the
1202          * appropriate sort node, if necessary).
1203          */
1204         if (parse->groupClause)
1205         {
1206                 bool            tuplePerGroup;
1207                 List       *group_tlist;
1208                 bool            is_sorted;
1209
1210                 /*
1211                  * Decide whether how many tuples per group the Group node needs
1212                  * to return. (Needs only one tuple per group if no aggregate is
1213                  * present. Otherwise, need every tuple from the group to do the
1214                  * aggregation.)  Note tuplePerGroup is named backwards :-(
1215                  */
1216                 tuplePerGroup = parse->hasAggs;
1217
1218                 /*
1219                  * If there are aggregates then the Group node should just return
1220                  * the same set of vars as the subplan did.  If there are no aggs
1221                  * then the Group node had better compute the final tlist.
1222                  */
1223                 if (parse->hasAggs)
1224                         group_tlist = new_unsorted_tlist(result_plan->targetlist);
1225                 else
1226                         group_tlist = tlist;
1227
1228                 /*
1229                  * Figure out whether the path result is already ordered the way
1230                  * we need it --- if so, no need for an explicit sort step.
1231                  */
1232                 if (pathkeys_contained_in(group_pathkeys, current_pathkeys))
1233                 {
1234                         is_sorted = true;       /* no sort needed now */
1235                         /* current_pathkeys remains unchanged */
1236                 }
1237                 else
1238                 {
1239                         /*
1240                          * We will need to do an explicit sort by the GROUP BY clause.
1241                          * make_groupplan will do the work, but set current_pathkeys
1242                          * to indicate the resulting order.
1243                          */
1244                         is_sorted = false;
1245                         current_pathkeys = group_pathkeys;
1246                 }
1247
1248                 result_plan = make_groupplan(parse,
1249                                                                          group_tlist,
1250                                                                          tuplePerGroup,
1251                                                                          parse->groupClause,
1252                                                                          groupColIdx,
1253                                                                          is_sorted,
1254                                                                          result_plan);
1255         }
1256
1257         /*
1258          * If aggregate is present, insert the Agg node
1259          *
1260          * HAVING clause, if any, becomes qual of the Agg node
1261          */
1262         if (parse->hasAggs)
1263         {
1264                 result_plan = (Plan *) make_agg(tlist,
1265                                                                                 (List *) parse->havingQual,
1266                                                                                 result_plan);
1267                 /* Note: Agg does not affect any existing sort order of the tuples */
1268         }
1269         else
1270         {
1271                 /* If there are no Aggs, we shouldn't have any HAVING qual anymore */
1272                 Assert(parse->havingQual == NULL);
1273         }
1274
1275         /*
1276          * If we were not able to make the plan come out in the right order,
1277          * add an explicit sort step.
1278          */
1279         if (parse->sortClause)
1280         {
1281                 if (!pathkeys_contained_in(sort_pathkeys, current_pathkeys))
1282                         result_plan = make_sortplan(parse, tlist, result_plan,
1283                                                                                 parse->sortClause);
1284         }
1285
1286         /*
1287          * If there is a DISTINCT clause, add the UNIQUE node.
1288          */
1289         if (parse->distinctClause)
1290         {
1291                 result_plan = (Plan *) make_unique(tlist, result_plan,
1292                                                                                    parse->distinctClause);
1293         }
1294
1295         /*
1296          * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node.
1297          */
1298         if (parse->limitOffset || parse->limitCount)
1299         {
1300                 result_plan = (Plan *) make_limit(tlist, result_plan,
1301                                                                                   parse->limitOffset,
1302                                                                                   parse->limitCount);
1303         }
1304
1305         return result_plan;
1306 }
1307
1308 /*---------------
1309  * make_subplanTargetList
1310  *        Generate appropriate target list when grouping is required.
1311  *
1312  * When grouping_planner inserts Aggregate and/or Group plan nodes above
1313  * the result of query_planner, we typically want to pass a different
1314  * target list to query_planner than the outer plan nodes should have.
1315  * This routine generates the correct target list for the subplan.
1316  *
1317  * The initial target list passed from the parser already contains entries
1318  * for all ORDER BY and GROUP BY expressions, but it will not have entries
1319  * for variables used only in HAVING clauses; so we need to add those
1320  * variables to the subplan target list.  Also, if we are doing either
1321  * grouping or aggregation, we flatten all expressions except GROUP BY items
1322  * into their component variables; the other expressions will be computed by
1323  * the inserted nodes rather than by the subplan.  For example,
1324  * given a query like
1325  *              SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
1326  * we want to pass this targetlist to the subplan:
1327  *              a,b,c,d,a+b
1328  * where the a+b target will be used by the Sort/Group steps, and the
1329  * other targets will be used for computing the final results.  (In the
1330  * above example we could theoretically suppress the a and b targets and
1331  * pass down only c,d,a+b, but it's not really worth the trouble to
1332  * eliminate simple var references from the subplan.  We will avoid doing
1333  * the extra computation to recompute a+b at the outer level; see
1334  * replace_vars_with_subplan_refs() in setrefs.c.)
1335  *
1336  * 'parse' is the query being processed.
1337  * 'tlist' is the query's target list.
1338  * 'groupColIdx' receives an array of column numbers for the GROUP BY
1339  * expressions (if there are any) in the subplan's target list.
1340  *
1341  * The result is the targetlist to be passed to the subplan.
1342  *---------------
1343  */
1344 static List *
1345 make_subplanTargetList(Query *parse,
1346                                            List *tlist,
1347                                            AttrNumber **groupColIdx)
1348 {
1349         List       *sub_tlist;
1350         List       *extravars;
1351         int                     numCols;
1352
1353         *groupColIdx = NULL;
1354
1355         /*
1356          * If we're not grouping or aggregating, nothing to do here;
1357          * query_planner should receive the unmodified target list.
1358          */
1359         if (!parse->hasAggs && !parse->groupClause && !parse->havingQual)
1360                 return tlist;
1361
1362         /*
1363          * Otherwise, start with a "flattened" tlist (having just the vars
1364          * mentioned in the targetlist and HAVING qual --- but not upper-
1365          * level Vars; they will be replaced by Params later on).
1366          */
1367         sub_tlist = flatten_tlist(tlist);
1368         extravars = pull_var_clause(parse->havingQual, false);
1369         sub_tlist = add_to_flat_tlist(sub_tlist, extravars);
1370         freeList(extravars);
1371
1372         /*
1373          * If grouping, create sub_tlist entries for all GROUP BY expressions
1374          * (GROUP BY items that are simple Vars should be in the list
1375          * already), and make an array showing where the group columns are in
1376          * the sub_tlist.
1377          */
1378         numCols = length(parse->groupClause);
1379         if (numCols > 0)
1380         {
1381                 int                     keyno = 0;
1382                 AttrNumber *grpColIdx;
1383                 List       *gl;
1384
1385                 grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
1386                 *groupColIdx = grpColIdx;
1387
1388                 foreach(gl, parse->groupClause)
1389                 {
1390                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
1391                         Node       *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
1392                         TargetEntry *te = NULL;
1393                         List       *sl;
1394
1395                         /* Find or make a matching sub_tlist entry */
1396                         foreach(sl, sub_tlist)
1397                         {
1398                                 te = (TargetEntry *) lfirst(sl);
1399                                 if (equal(groupexpr, te->expr))
1400                                         break;
1401                         }
1402                         if (!sl)
1403                         {
1404                                 te = makeTargetEntry(makeResdom(length(sub_tlist) + 1,
1405                                                                                                 exprType(groupexpr),
1406                                                                                                 exprTypmod(groupexpr),
1407                                                                                                 NULL,
1408                                                                                                 false),
1409                                                                          groupexpr);
1410                                 sub_tlist = lappend(sub_tlist, te);
1411                         }
1412
1413                         /* and save its resno */
1414                         grpColIdx[keyno++] = te->resdom->resno;
1415                 }
1416         }
1417
1418         return sub_tlist;
1419 }
1420
1421 /*
1422  * make_groupplan
1423  *              Add a Group node for GROUP BY processing.
1424  *              If we couldn't make the subplan produce presorted output for grouping,
1425  *              first add an explicit Sort node.
1426  */
1427 static Plan *
1428 make_groupplan(Query *parse,
1429                            List *group_tlist,
1430                            bool tuplePerGroup,
1431                            List *groupClause,
1432                            AttrNumber *grpColIdx,
1433                            bool is_presorted,
1434                            Plan *subplan)
1435 {
1436         int                     numCols = length(groupClause);
1437
1438         if (!is_presorted)
1439         {
1440                 /*
1441                  * The Sort node always just takes a copy of the subplan's tlist
1442                  * plus ordering information.  (This might seem inefficient if the
1443                  * subplan contains complex GROUP BY expressions, but in fact Sort
1444                  * does not evaluate its targetlist --- it only outputs the same
1445                  * tuples in a new order.  So the expressions we might be copying
1446                  * are just dummies with no extra execution cost.)
1447                  */
1448                 List       *sort_tlist = new_unsorted_tlist(subplan->targetlist);
1449                 int                     keyno = 0;
1450                 List       *gl;
1451
1452                 foreach(gl, groupClause)
1453                 {
1454                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
1455                         TargetEntry *te = nth(grpColIdx[keyno] - 1, sort_tlist);
1456                         Resdom     *resdom = te->resdom;
1457
1458                         /*
1459                          * Check for the possibility of duplicate group-by clauses ---
1460                          * the parser should have removed 'em, but the Sort executor
1461                          * will get terribly confused if any get through!
1462                          */
1463                         if (resdom->reskey == 0)
1464                         {
1465                                 /* OK, insert the ordering info needed by the executor. */
1466                                 resdom->reskey = ++keyno;
1467                                 resdom->reskeyop = grpcl->sortop;
1468                         }
1469                 }
1470
1471                 Assert(keyno > 0);
1472
1473                 subplan = (Plan *) make_sort(parse, sort_tlist, subplan, keyno);
1474         }
1475
1476         return (Plan *) make_group(group_tlist, tuplePerGroup, numCols,
1477                                                            grpColIdx, subplan);
1478 }
1479
1480 /*
1481  * make_sortplan
1482  *        Add a Sort node to implement an explicit ORDER BY clause.
1483  */
1484 Plan *
1485 make_sortplan(Query *parse, List *tlist, Plan *plannode, List *sortcls)
1486 {
1487         List       *sort_tlist;
1488         List       *i;
1489         int                     keyno = 0;
1490
1491         /*
1492          * First make a copy of the tlist so that we don't corrupt the
1493          * original.
1494          */
1495         sort_tlist = new_unsorted_tlist(tlist);
1496
1497         foreach(i, sortcls)
1498         {
1499                 SortClause *sortcl = (SortClause *) lfirst(i);
1500                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sort_tlist);
1501                 Resdom     *resdom = tle->resdom;
1502
1503                 /*
1504                  * Check for the possibility of duplicate order-by clauses --- the
1505                  * parser should have removed 'em, but the executor will get
1506                  * terribly confused if any get through!
1507                  */
1508                 if (resdom->reskey == 0)
1509                 {
1510                         /* OK, insert the ordering info needed by the executor. */
1511                         resdom->reskey = ++keyno;
1512                         resdom->reskeyop = sortcl->sortop;
1513                 }
1514         }
1515
1516         Assert(keyno > 0);
1517
1518         return (Plan *) make_sort(parse, sort_tlist, plannode, keyno);
1519 }
1520
1521 /*
1522  * postprocess_setop_tlist
1523  *        Fix up targetlist returned by plan_set_operations().
1524  *
1525  * We need to transpose sort key info from the orig_tlist into new_tlist.
1526  * NOTE: this would not be good enough if we supported resjunk sort keys
1527  * for results of set operations --- then, we'd need to project a whole
1528  * new tlist to evaluate the resjunk columns.  For now, just elog if we
1529  * find any resjunk columns in orig_tlist.
1530  */
1531 static List *
1532 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
1533 {
1534         List       *l;
1535
1536         foreach(l, new_tlist)
1537         {
1538                 TargetEntry *new_tle = (TargetEntry *) lfirst(l);
1539                 TargetEntry *orig_tle;
1540
1541                 /* ignore resjunk columns in setop result */
1542                 if (new_tle->resdom->resjunk)
1543                         continue;
1544
1545                 Assert(orig_tlist != NIL);
1546                 orig_tle = (TargetEntry *) lfirst(orig_tlist);
1547                 orig_tlist = lnext(orig_tlist);
1548                 if (orig_tle->resdom->resjunk)
1549                         elog(ERROR, "postprocess_setop_tlist: resjunk output columns not implemented");
1550                 Assert(new_tle->resdom->resno == orig_tle->resdom->resno);
1551                 Assert(new_tle->resdom->restype == orig_tle->resdom->restype);
1552                 new_tle->resdom->ressortgroupref = orig_tle->resdom->ressortgroupref;
1553         }
1554         if (orig_tlist != NIL)
1555                 elog(ERROR, "postprocess_setop_tlist: resjunk output columns not implemented");
1556         return new_tlist;
1557 }