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