Header And Logo

PostgreSQL
| The world's most advanced open source database.

planner.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * planner.c
00004  *    The query optimizer external interface.
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/optimizer/plan/planner.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 
00016 #include "postgres.h"
00017 
00018 #include <limits.h>
00019 
00020 #include "access/htup_details.h"
00021 #include "executor/executor.h"
00022 #include "executor/nodeAgg.h"
00023 #include "miscadmin.h"
00024 #include "nodes/makefuncs.h"
00025 #ifdef OPTIMIZER_DEBUG
00026 #include "nodes/print.h"
00027 #endif
00028 #include "optimizer/clauses.h"
00029 #include "optimizer/cost.h"
00030 #include "optimizer/pathnode.h"
00031 #include "optimizer/paths.h"
00032 #include "optimizer/plancat.h"
00033 #include "optimizer/planmain.h"
00034 #include "optimizer/planner.h"
00035 #include "optimizer/prep.h"
00036 #include "optimizer/subselect.h"
00037 #include "optimizer/tlist.h"
00038 #include "parser/analyze.h"
00039 #include "parser/parsetree.h"
00040 #include "rewrite/rewriteManip.h"
00041 #include "utils/rel.h"
00042 
00043 
00044 /* GUC parameter */
00045 double      cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
00046 
00047 /* Hook for plugins to get control in planner() */
00048 planner_hook_type planner_hook = NULL;
00049 
00050 
00051 /* Expression kind codes for preprocess_expression */
00052 #define EXPRKIND_QUAL           0
00053 #define EXPRKIND_TARGET         1
00054 #define EXPRKIND_RTFUNC         2
00055 #define EXPRKIND_RTFUNC_LATERAL 3
00056 #define EXPRKIND_VALUES         4
00057 #define EXPRKIND_VALUES_LATERAL 5
00058 #define EXPRKIND_LIMIT          6
00059 #define EXPRKIND_APPINFO        7
00060 #define EXPRKIND_PHV            8
00061 
00062 /* Passthrough data for standard_qp_callback */
00063 typedef struct
00064 {
00065     List       *tlist;          /* preprocessed query targetlist */
00066     List       *activeWindows;  /* active windows, if any */
00067 } standard_qp_extra;
00068 
00069 /* Local functions */
00070 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
00071 static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
00072 static Plan *inheritance_planner(PlannerInfo *root);
00073 static Plan *grouping_planner(PlannerInfo *root, double tuple_fraction);
00074 static void preprocess_rowmarks(PlannerInfo *root);
00075 static double preprocess_limit(PlannerInfo *root,
00076                  double tuple_fraction,
00077                  int64 *offset_est, int64 *count_est);
00078 static bool limit_needed(Query *parse);
00079 static void preprocess_groupclause(PlannerInfo *root);
00080 static void standard_qp_callback(PlannerInfo *root, void *extra);
00081 static bool choose_hashed_grouping(PlannerInfo *root,
00082                        double tuple_fraction, double limit_tuples,
00083                        double path_rows, int path_width,
00084                        Path *cheapest_path, Path *sorted_path,
00085                        double dNumGroups, AggClauseCosts *agg_costs);
00086 static bool choose_hashed_distinct(PlannerInfo *root,
00087                        double tuple_fraction, double limit_tuples,
00088                        double path_rows, int path_width,
00089                        Cost cheapest_startup_cost, Cost cheapest_total_cost,
00090                        Cost sorted_startup_cost, Cost sorted_total_cost,
00091                        List *sorted_pathkeys,
00092                        double dNumDistinctRows);
00093 static List *make_subplanTargetList(PlannerInfo *root, List *tlist,
00094                        AttrNumber **groupColIdx, bool *need_tlist_eval);
00095 static int  get_grouping_column_index(Query *parse, TargetEntry *tle);
00096 static void locate_grouping_columns(PlannerInfo *root,
00097                         List *tlist,
00098                         List *sub_tlist,
00099                         AttrNumber *groupColIdx);
00100 static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
00101 static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
00102 static List *make_windowInputTargetList(PlannerInfo *root,
00103                            List *tlist, List *activeWindows);
00104 static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
00105                          List *tlist);
00106 static void get_column_info_for_window(PlannerInfo *root, WindowClause *wc,
00107                            List *tlist,
00108                            int numSortCols, AttrNumber *sortColIdx,
00109                            int *partNumCols,
00110                            AttrNumber **partColIdx,
00111                            Oid **partOperators,
00112                            int *ordNumCols,
00113                            AttrNumber **ordColIdx,
00114                            Oid **ordOperators);
00115 
00116 
00117 /*****************************************************************************
00118  *
00119  *     Query optimizer entry point
00120  *
00121  * To support loadable plugins that monitor or modify planner behavior,
00122  * we provide a hook variable that lets a plugin get control before and
00123  * after the standard planning process.  The plugin would normally call
00124  * standard_planner().
00125  *
00126  * Note to plugin authors: standard_planner() scribbles on its Query input,
00127  * so you'd better copy that data structure if you want to plan more than once.
00128  *
00129  *****************************************************************************/
00130 PlannedStmt *
00131 planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
00132 {
00133     PlannedStmt *result;
00134 
00135     if (planner_hook)
00136         result = (*planner_hook) (parse, cursorOptions, boundParams);
00137     else
00138         result = standard_planner(parse, cursorOptions, boundParams);
00139     return result;
00140 }
00141 
00142 PlannedStmt *
00143 standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
00144 {
00145     PlannedStmt *result;
00146     PlannerGlobal *glob;
00147     double      tuple_fraction;
00148     PlannerInfo *root;
00149     Plan       *top_plan;
00150     ListCell   *lp,
00151                *lr;
00152 
00153     /* Cursor options may come from caller or from DECLARE CURSOR stmt */
00154     if (parse->utilityStmt &&
00155         IsA(parse->utilityStmt, DeclareCursorStmt))
00156         cursorOptions |= ((DeclareCursorStmt *) parse->utilityStmt)->options;
00157 
00158     /*
00159      * Set up global state for this planner invocation.  This data is needed
00160      * across all levels of sub-Query that might exist in the given command,
00161      * so we keep it in a separate struct that's linked to by each per-Query
00162      * PlannerInfo.
00163      */
00164     glob = makeNode(PlannerGlobal);
00165 
00166     glob->boundParams = boundParams;
00167     glob->subplans = NIL;
00168     glob->subroots = NIL;
00169     glob->rewindPlanIDs = NULL;
00170     glob->finalrtable = NIL;
00171     glob->finalrowmarks = NIL;
00172     glob->resultRelations = NIL;
00173     glob->relationOids = NIL;
00174     glob->invalItems = NIL;
00175     glob->nParamExec = 0;
00176     glob->lastPHId = 0;
00177     glob->lastRowMarkId = 0;
00178     glob->transientPlan = false;
00179 
00180     /* Determine what fraction of the plan is likely to be scanned */
00181     if (cursorOptions & CURSOR_OPT_FAST_PLAN)
00182     {
00183         /*
00184          * We have no real idea how many tuples the user will ultimately FETCH
00185          * from a cursor, but it is often the case that he doesn't want 'em
00186          * all, or would prefer a fast-start plan anyway so that he can
00187          * process some of the tuples sooner.  Use a GUC parameter to decide
00188          * what fraction to optimize for.
00189          */
00190         tuple_fraction = cursor_tuple_fraction;
00191 
00192         /*
00193          * We document cursor_tuple_fraction as simply being a fraction, which
00194          * means the edge cases 0 and 1 have to be treated specially here.  We
00195          * convert 1 to 0 ("all the tuples") and 0 to a very small fraction.
00196          */
00197         if (tuple_fraction >= 1.0)
00198             tuple_fraction = 0.0;
00199         else if (tuple_fraction <= 0.0)
00200             tuple_fraction = 1e-10;
00201     }
00202     else
00203     {
00204         /* Default assumption is we need all the tuples */
00205         tuple_fraction = 0.0;
00206     }
00207 
00208     /* primary planning entry point (may recurse for subqueries) */
00209     top_plan = subquery_planner(glob, parse, NULL,
00210                                 false, tuple_fraction, &root);
00211 
00212     /*
00213      * If creating a plan for a scrollable cursor, make sure it can run
00214      * backwards on demand.  Add a Material node at the top at need.
00215      */
00216     if (cursorOptions & CURSOR_OPT_SCROLL)
00217     {
00218         if (!ExecSupportsBackwardScan(top_plan))
00219             top_plan = materialize_finished_plan(top_plan);
00220     }
00221 
00222     /* final cleanup of the plan */
00223     Assert(glob->finalrtable == NIL);
00224     Assert(glob->finalrowmarks == NIL);
00225     Assert(glob->resultRelations == NIL);
00226     top_plan = set_plan_references(root, top_plan);
00227     /* ... and the subplans (both regular subplans and initplans) */
00228     Assert(list_length(glob->subplans) == list_length(glob->subroots));
00229     forboth(lp, glob->subplans, lr, glob->subroots)
00230     {
00231         Plan       *subplan = (Plan *) lfirst(lp);
00232         PlannerInfo *subroot = (PlannerInfo *) lfirst(lr);
00233 
00234         lfirst(lp) = set_plan_references(subroot, subplan);
00235     }
00236 
00237     /* build the PlannedStmt result */
00238     result = makeNode(PlannedStmt);
00239 
00240     result->commandType = parse->commandType;
00241     result->queryId = parse->queryId;
00242     result->hasReturning = (parse->returningList != NIL);
00243     result->hasModifyingCTE = parse->hasModifyingCTE;
00244     result->canSetTag = parse->canSetTag;
00245     result->transientPlan = glob->transientPlan;
00246     result->planTree = top_plan;
00247     result->rtable = glob->finalrtable;
00248     result->resultRelations = glob->resultRelations;
00249     result->utilityStmt = parse->utilityStmt;
00250     result->subplans = glob->subplans;
00251     result->rewindPlanIDs = glob->rewindPlanIDs;
00252     result->rowMarks = glob->finalrowmarks;
00253     result->relationOids = glob->relationOids;
00254     result->invalItems = glob->invalItems;
00255     result->nParamExec = glob->nParamExec;
00256 
00257     return result;
00258 }
00259 
00260 
00261 /*--------------------
00262  * subquery_planner
00263  *    Invokes the planner on a subquery.  We recurse to here for each
00264  *    sub-SELECT found in the query tree.
00265  *
00266  * glob is the global state for the current planner run.
00267  * parse is the querytree produced by the parser & rewriter.
00268  * parent_root is the immediate parent Query's info (NULL at the top level).
00269  * hasRecursion is true if this is a recursive WITH query.
00270  * tuple_fraction is the fraction of tuples we expect will be retrieved.
00271  * tuple_fraction is interpreted as explained for grouping_planner, below.
00272  *
00273  * If subroot isn't NULL, we pass back the query's final PlannerInfo struct;
00274  * among other things this tells the output sort ordering of the plan.
00275  *
00276  * Basically, this routine does the stuff that should only be done once
00277  * per Query object.  It then calls grouping_planner.  At one time,
00278  * grouping_planner could be invoked recursively on the same Query object;
00279  * that's not currently true, but we keep the separation between the two
00280  * routines anyway, in case we need it again someday.
00281  *
00282  * subquery_planner will be called recursively to handle sub-Query nodes
00283  * found within the query's expressions and rangetable.
00284  *
00285  * Returns a query plan.
00286  *--------------------
00287  */
00288 Plan *
00289 subquery_planner(PlannerGlobal *glob, Query *parse,
00290                  PlannerInfo *parent_root,
00291                  bool hasRecursion, double tuple_fraction,
00292                  PlannerInfo **subroot)
00293 {
00294     int         num_old_subplans = list_length(glob->subplans);
00295     PlannerInfo *root;
00296     Plan       *plan;
00297     List       *newHaving;
00298     bool        hasOuterJoins;
00299     ListCell   *l;
00300 
00301     /* Create a PlannerInfo data structure for this subquery */
00302     root = makeNode(PlannerInfo);
00303     root->parse = parse;
00304     root->glob = glob;
00305     root->query_level = parent_root ? parent_root->query_level + 1 : 1;
00306     root->parent_root = parent_root;
00307     root->plan_params = NIL;
00308     root->planner_cxt = CurrentMemoryContext;
00309     root->init_plans = NIL;
00310     root->cte_plan_ids = NIL;
00311     root->eq_classes = NIL;
00312     root->append_rel_list = NIL;
00313     root->rowMarks = NIL;
00314     root->hasInheritedTarget = false;
00315 
00316     root->hasRecursion = hasRecursion;
00317     if (hasRecursion)
00318         root->wt_param_id = SS_assign_special_param(root);
00319     else
00320         root->wt_param_id = -1;
00321     root->non_recursive_plan = NULL;
00322 
00323     /*
00324      * If there is a WITH list, process each WITH query and build an initplan
00325      * SubPlan structure for it.
00326      */
00327     if (parse->cteList)
00328         SS_process_ctes(root);
00329 
00330     /*
00331      * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
00332      * to transform them into joins.  Note that this step does not descend
00333      * into subqueries; if we pull up any subqueries below, their SubLinks are
00334      * processed just before pulling them up.
00335      */
00336     if (parse->hasSubLinks)
00337         pull_up_sublinks(root);
00338 
00339     /*
00340      * Scan the rangetable for set-returning functions, and inline them if
00341      * possible (producing subqueries that might get pulled up next).
00342      * Recursion issues here are handled in the same way as for SubLinks.
00343      */
00344     inline_set_returning_functions(root);
00345 
00346     /*
00347      * Check to see if any subqueries in the jointree can be merged into this
00348      * query.
00349      */
00350     parse->jointree = (FromExpr *)
00351         pull_up_subqueries(root, (Node *) parse->jointree);
00352 
00353     /*
00354      * If this is a simple UNION ALL query, flatten it into an appendrel. We
00355      * do this now because it requires applying pull_up_subqueries to the leaf
00356      * queries of the UNION ALL, which weren't touched above because they
00357      * weren't referenced by the jointree (they will be after we do this).
00358      */
00359     if (parse->setOperations)
00360         flatten_simple_union_all(root);
00361 
00362     /*
00363      * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
00364      * avoid the expense of doing flatten_join_alias_vars().  Also check for
00365      * outer joins --- if none, we can skip reduce_outer_joins().  And check
00366      * for LATERAL RTEs, too.  This must be done after we have done
00367      * pull_up_subqueries(), of course.
00368      */
00369     root->hasJoinRTEs = false;
00370     root->hasLateralRTEs = false;
00371     hasOuterJoins = false;
00372     foreach(l, parse->rtable)
00373     {
00374         RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
00375 
00376         if (rte->rtekind == RTE_JOIN)
00377         {
00378             root->hasJoinRTEs = true;
00379             if (IS_OUTER_JOIN(rte->jointype))
00380                 hasOuterJoins = true;
00381         }
00382         if (rte->lateral)
00383             root->hasLateralRTEs = true;
00384     }
00385 
00386     /*
00387      * Preprocess RowMark information.  We need to do this after subquery
00388      * pullup (so that all non-inherited RTEs are present) and before
00389      * inheritance expansion (so that the info is available for
00390      * expand_inherited_tables to examine and modify).
00391      */
00392     preprocess_rowmarks(root);
00393 
00394     /*
00395      * Expand any rangetable entries that are inheritance sets into "append
00396      * relations".  This can add entries to the rangetable, but they must be
00397      * plain base relations not joins, so it's OK (and marginally more
00398      * efficient) to do it after checking for join RTEs.  We must do it after
00399      * pulling up subqueries, else we'd fail to handle inherited tables in
00400      * subqueries.
00401      */
00402     expand_inherited_tables(root);
00403 
00404     /*
00405      * Set hasHavingQual to remember if HAVING clause is present.  Needed
00406      * because preprocess_expression will reduce a constant-true condition to
00407      * an empty qual list ... but "HAVING TRUE" is not a semantic no-op.
00408      */
00409     root->hasHavingQual = (parse->havingQual != NULL);
00410 
00411     /* Clear this flag; might get set in distribute_qual_to_rels */
00412     root->hasPseudoConstantQuals = false;
00413 
00414     /*
00415      * Do expression preprocessing on targetlist and quals, as well as other
00416      * random expressions in the querytree.  Note that we do not need to
00417      * handle sort/group expressions explicitly, because they are actually
00418      * part of the targetlist.
00419      */
00420     parse->targetList = (List *)
00421         preprocess_expression(root, (Node *) parse->targetList,
00422                               EXPRKIND_TARGET);
00423 
00424     parse->returningList = (List *)
00425         preprocess_expression(root, (Node *) parse->returningList,
00426                               EXPRKIND_TARGET);
00427 
00428     preprocess_qual_conditions(root, (Node *) parse->jointree);
00429 
00430     parse->havingQual = preprocess_expression(root, parse->havingQual,
00431                                               EXPRKIND_QUAL);
00432 
00433     foreach(l, parse->windowClause)
00434     {
00435         WindowClause *wc = (WindowClause *) lfirst(l);
00436 
00437         /* partitionClause/orderClause are sort/group expressions */
00438         wc->startOffset = preprocess_expression(root, wc->startOffset,
00439                                                 EXPRKIND_LIMIT);
00440         wc->endOffset = preprocess_expression(root, wc->endOffset,
00441                                               EXPRKIND_LIMIT);
00442     }
00443 
00444     parse->limitOffset = preprocess_expression(root, parse->limitOffset,
00445                                                EXPRKIND_LIMIT);
00446     parse->limitCount = preprocess_expression(root, parse->limitCount,
00447                                               EXPRKIND_LIMIT);
00448 
00449     root->append_rel_list = (List *)
00450         preprocess_expression(root, (Node *) root->append_rel_list,
00451                               EXPRKIND_APPINFO);
00452 
00453     /* Also need to preprocess expressions within RTEs */
00454     foreach(l, parse->rtable)
00455     {
00456         RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
00457         int         kind;
00458 
00459         if (rte->rtekind == RTE_SUBQUERY)
00460         {
00461             /*
00462              * We don't want to do all preprocessing yet on the subquery's
00463              * expressions, since that will happen when we plan it.  But if it
00464              * contains any join aliases of our level, those have to get
00465              * expanded now, because planning of the subquery won't do it.
00466              * That's only possible if the subquery is LATERAL.
00467              */
00468             if (rte->lateral && root->hasJoinRTEs)
00469                 rte->subquery = (Query *)
00470                     flatten_join_alias_vars(root, (Node *) rte->subquery);
00471         }
00472         else if (rte->rtekind == RTE_FUNCTION)
00473         {
00474             /* Preprocess the function expression fully */
00475             kind = rte->lateral ? EXPRKIND_RTFUNC_LATERAL : EXPRKIND_RTFUNC;
00476             rte->funcexpr = preprocess_expression(root, rte->funcexpr, kind);
00477         }
00478         else if (rte->rtekind == RTE_VALUES)
00479         {
00480             /* Preprocess the values lists fully */
00481             kind = rte->lateral ? EXPRKIND_VALUES_LATERAL : EXPRKIND_VALUES;
00482             rte->values_lists = (List *)
00483                 preprocess_expression(root, (Node *) rte->values_lists, kind);
00484         }
00485     }
00486 
00487     /*
00488      * In some cases we may want to transfer a HAVING clause into WHERE. We
00489      * cannot do so if the HAVING clause contains aggregates (obviously) or
00490      * volatile functions (since a HAVING clause is supposed to be executed
00491      * only once per group).  Also, it may be that the clause is so expensive
00492      * to execute that we're better off doing it only once per group, despite
00493      * the loss of selectivity.  This is hard to estimate short of doing the
00494      * entire planning process twice, so we use a heuristic: clauses
00495      * containing subplans are left in HAVING.  Otherwise, we move or copy the
00496      * HAVING clause into WHERE, in hopes of eliminating tuples before
00497      * aggregation instead of after.
00498      *
00499      * If the query has explicit grouping then we can simply move such a
00500      * clause into WHERE; any group that fails the clause will not be in the
00501      * output because none of its tuples will reach the grouping or
00502      * aggregation stage.  Otherwise we must have a degenerate (variable-free)
00503      * HAVING clause, which we put in WHERE so that query_planner() can use it
00504      * in a gating Result node, but also keep in HAVING to ensure that we
00505      * don't emit a bogus aggregated row. (This could be done better, but it
00506      * seems not worth optimizing.)
00507      *
00508      * Note that both havingQual and parse->jointree->quals are in
00509      * implicitly-ANDed-list form at this point, even though they are declared
00510      * as Node *.
00511      */
00512     newHaving = NIL;
00513     foreach(l, (List *) parse->havingQual)
00514     {
00515         Node       *havingclause = (Node *) lfirst(l);
00516 
00517         if (contain_agg_clause(havingclause) ||
00518             contain_volatile_functions(havingclause) ||
00519             contain_subplans(havingclause))
00520         {
00521             /* keep it in HAVING */
00522             newHaving = lappend(newHaving, havingclause);
00523         }
00524         else if (parse->groupClause)
00525         {
00526             /* move it to WHERE */
00527             parse->jointree->quals = (Node *)
00528                 lappend((List *) parse->jointree->quals, havingclause);
00529         }
00530         else
00531         {
00532             /* put a copy in WHERE, keep it in HAVING */
00533             parse->jointree->quals = (Node *)
00534                 lappend((List *) parse->jointree->quals,
00535                         copyObject(havingclause));
00536             newHaving = lappend(newHaving, havingclause);
00537         }
00538     }
00539     parse->havingQual = (Node *) newHaving;
00540 
00541     /*
00542      * If we have any outer joins, try to reduce them to plain inner joins.
00543      * This step is most easily done after we've done expression
00544      * preprocessing.
00545      */
00546     if (hasOuterJoins)
00547         reduce_outer_joins(root);
00548 
00549     /*
00550      * Do the main planning.  If we have an inherited target relation, that
00551      * needs special processing, else go straight to grouping_planner.
00552      */
00553     if (parse->resultRelation &&
00554         rt_fetch(parse->resultRelation, parse->rtable)->inh)
00555         plan = inheritance_planner(root);
00556     else
00557     {
00558         plan = grouping_planner(root, tuple_fraction);
00559         /* If it's not SELECT, we need a ModifyTable node */
00560         if (parse->commandType != CMD_SELECT)
00561         {
00562             List       *returningLists;
00563             List       *rowMarks;
00564 
00565             /*
00566              * Set up the RETURNING list-of-lists, if needed.
00567              */
00568             if (parse->returningList)
00569                 returningLists = list_make1(parse->returningList);
00570             else
00571                 returningLists = NIL;
00572 
00573             /*
00574              * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node will
00575              * have dealt with fetching non-locked marked rows, else we need
00576              * to have ModifyTable do that.
00577              */
00578             if (parse->rowMarks)
00579                 rowMarks = NIL;
00580             else
00581                 rowMarks = root->rowMarks;
00582 
00583             plan = (Plan *) make_modifytable(root,
00584                                              parse->commandType,
00585                                              parse->canSetTag,
00586                                        list_make1_int(parse->resultRelation),
00587                                              list_make1(plan),
00588                                              returningLists,
00589                                              rowMarks,
00590                                              SS_assign_special_param(root));
00591         }
00592     }
00593 
00594     /*
00595      * If any subplans were generated, or if there are any parameters to worry
00596      * about, build initPlan list and extParam/allParam sets for plan nodes,
00597      * and attach the initPlans to the top plan node.
00598      */
00599     if (list_length(glob->subplans) != num_old_subplans ||
00600         root->glob->nParamExec > 0)
00601         SS_finalize_plan(root, plan, true);
00602 
00603     /* Return internal info if caller wants it */
00604     if (subroot)
00605         *subroot = root;
00606 
00607     return plan;
00608 }
00609 
00610 /*
00611  * preprocess_expression
00612  *      Do subquery_planner's preprocessing work for an expression,
00613  *      which can be a targetlist, a WHERE clause (including JOIN/ON
00614  *      conditions), a HAVING clause, or a few other things.
00615  */
00616 static Node *
00617 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
00618 {
00619     /*
00620      * Fall out quickly if expression is empty.  This occurs often enough to
00621      * be worth checking.  Note that null->null is the correct conversion for
00622      * implicit-AND result format, too.
00623      */
00624     if (expr == NULL)
00625         return NULL;
00626 
00627     /*
00628      * If the query has any join RTEs, replace join alias variables with
00629      * base-relation variables.  We must do this before sublink processing,
00630      * else sublinks expanded out from join aliases would not get processed.
00631      * We can skip it in non-lateral RTE functions and VALUES lists, however,
00632      * since they can't contain any Vars of the current query level.
00633      */
00634     if (root->hasJoinRTEs &&
00635         !(kind == EXPRKIND_RTFUNC || kind == EXPRKIND_VALUES))
00636         expr = flatten_join_alias_vars(root, expr);
00637 
00638     /*
00639      * Simplify constant expressions.
00640      *
00641      * Note: an essential effect of this is to convert named-argument function
00642      * calls to positional notation and insert the current actual values of
00643      * any default arguments for functions.  To ensure that happens, we *must*
00644      * process all expressions here.  Previous PG versions sometimes skipped
00645      * const-simplification if it didn't seem worth the trouble, but we can't
00646      * do that anymore.
00647      *
00648      * Note: this also flattens nested AND and OR expressions into N-argument
00649      * form.  All processing of a qual expression after this point must be
00650      * careful to maintain AND/OR flatness --- that is, do not generate a tree
00651      * with AND directly under AND, nor OR directly under OR.
00652      */
00653     expr = eval_const_expressions(root, expr);
00654 
00655     /*
00656      * If it's a qual or havingQual, canonicalize it.
00657      */
00658     if (kind == EXPRKIND_QUAL)
00659     {
00660         expr = (Node *) canonicalize_qual((Expr *) expr);
00661 
00662 #ifdef OPTIMIZER_DEBUG
00663         printf("After canonicalize_qual()\n");
00664         pprint(expr);
00665 #endif
00666     }
00667 
00668     /* Expand SubLinks to SubPlans */
00669     if (root->parse->hasSubLinks)
00670         expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));
00671 
00672     /*
00673      * XXX do not insert anything here unless you have grokked the comments in
00674      * SS_replace_correlation_vars ...
00675      */
00676 
00677     /* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
00678     if (root->query_level > 1)
00679         expr = SS_replace_correlation_vars(root, expr);
00680 
00681     /*
00682      * If it's a qual or havingQual, convert it to implicit-AND format. (We
00683      * don't want to do this before eval_const_expressions, since the latter
00684      * would be unable to simplify a top-level AND correctly. Also,
00685      * SS_process_sublinks expects explicit-AND format.)
00686      */
00687     if (kind == EXPRKIND_QUAL)
00688         expr = (Node *) make_ands_implicit((Expr *) expr);
00689 
00690     return expr;
00691 }
00692 
00693 /*
00694  * preprocess_qual_conditions
00695  *      Recursively scan the query's jointree and do subquery_planner's
00696  *      preprocessing work on each qual condition found therein.
00697  */
00698 static void
00699 preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
00700 {
00701     if (jtnode == NULL)
00702         return;
00703     if (IsA(jtnode, RangeTblRef))
00704     {
00705         /* nothing to do here */
00706     }
00707     else if (IsA(jtnode, FromExpr))
00708     {
00709         FromExpr   *f = (FromExpr *) jtnode;
00710         ListCell   *l;
00711 
00712         foreach(l, f->fromlist)
00713             preprocess_qual_conditions(root, lfirst(l));
00714 
00715         f->quals = preprocess_expression(root, f->quals, EXPRKIND_QUAL);
00716     }
00717     else if (IsA(jtnode, JoinExpr))
00718     {
00719         JoinExpr   *j = (JoinExpr *) jtnode;
00720 
00721         preprocess_qual_conditions(root, j->larg);
00722         preprocess_qual_conditions(root, j->rarg);
00723 
00724         j->quals = preprocess_expression(root, j->quals, EXPRKIND_QUAL);
00725     }
00726     else
00727         elog(ERROR, "unrecognized node type: %d",
00728              (int) nodeTag(jtnode));
00729 }
00730 
00731 /*
00732  * preprocess_phv_expression
00733  *    Do preprocessing on a PlaceHolderVar expression that's been pulled up.
00734  *
00735  * If a LATERAL subquery references an output of another subquery, and that
00736  * output must be wrapped in a PlaceHolderVar because of an intermediate outer
00737  * join, then we'll push the PlaceHolderVar expression down into the subquery
00738  * and later pull it back up during find_lateral_references, which runs after
00739  * subquery_planner has preprocessed all the expressions that were in the
00740  * current query level to start with.  So we need to preprocess it then.
00741  */
00742 Expr *
00743 preprocess_phv_expression(PlannerInfo *root, Expr *expr)
00744 {
00745     return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
00746 }
00747 
00748 /*
00749  * inheritance_planner
00750  *    Generate a plan in the case where the result relation is an
00751  *    inheritance set.
00752  *
00753  * We have to handle this case differently from cases where a source relation
00754  * is an inheritance set. Source inheritance is expanded at the bottom of the
00755  * plan tree (see allpaths.c), but target inheritance has to be expanded at
00756  * the top.  The reason is that for UPDATE, each target relation needs a
00757  * different targetlist matching its own column set.  Fortunately,
00758  * the UPDATE/DELETE target can never be the nullable side of an outer join,
00759  * so it's OK to generate the plan this way.
00760  *
00761  * Returns a query plan.
00762  */
00763 static Plan *
00764 inheritance_planner(PlannerInfo *root)
00765 {
00766     Query      *parse = root->parse;
00767     int         parentRTindex = parse->resultRelation;
00768     List       *final_rtable = NIL;
00769     int         save_rel_array_size = 0;
00770     RelOptInfo **save_rel_array = NULL;
00771     List       *subplans = NIL;
00772     List       *resultRelations = NIL;
00773     List       *returningLists = NIL;
00774     List       *rowMarks;
00775     ListCell   *lc;
00776 
00777     /*
00778      * We generate a modified instance of the original Query for each target
00779      * relation, plan that, and put all the plans into a list that will be
00780      * controlled by a single ModifyTable node.  All the instances share the
00781      * same rangetable, but each instance must have its own set of subquery
00782      * RTEs within the finished rangetable because (1) they are likely to get
00783      * scribbled on during planning, and (2) it's not inconceivable that
00784      * subqueries could get planned differently in different cases.  We need
00785      * not create duplicate copies of other RTE kinds, in particular not the
00786      * target relations, because they don't have either of those issues.  Not
00787      * having to duplicate the target relations is important because doing so
00788      * (1) would result in a rangetable of length O(N^2) for N targets, with
00789      * at least O(N^3) work expended here; and (2) would greatly complicate
00790      * management of the rowMarks list.
00791      */
00792     foreach(lc, root->append_rel_list)
00793     {
00794         AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
00795         PlannerInfo subroot;
00796         Plan       *subplan;
00797         Index       rti;
00798 
00799         /* append_rel_list contains all append rels; ignore others */
00800         if (appinfo->parent_relid != parentRTindex)
00801             continue;
00802 
00803         /*
00804          * We need a working copy of the PlannerInfo so that we can control
00805          * propagation of information back to the main copy.
00806          */
00807         memcpy(&subroot, root, sizeof(PlannerInfo));
00808 
00809         /*
00810          * Generate modified query with this rel as target.  We first apply
00811          * adjust_appendrel_attrs, which copies the Query and changes
00812          * references to the parent RTE to refer to the current child RTE,
00813          * then fool around with subquery RTEs.
00814          */
00815         subroot.parse = (Query *)
00816             adjust_appendrel_attrs(root,
00817                                    (Node *) parse,
00818                                    appinfo);
00819 
00820         /*
00821          * The rowMarks list might contain references to subquery RTEs, so
00822          * make a copy that we can apply ChangeVarNodes to.  (Fortunately, the
00823          * executor doesn't need to see the modified copies --- we can just
00824          * pass it the original rowMarks list.)
00825          */
00826         subroot.rowMarks = (List *) copyObject(root->rowMarks);
00827 
00828         /*
00829          * Add placeholders to the child Query's rangetable list to fill the
00830          * RT indexes already reserved for subqueries in previous children.
00831          * These won't be referenced, so there's no need to make them very
00832          * valid-looking.
00833          */
00834         while (list_length(subroot.parse->rtable) < list_length(final_rtable))
00835             subroot.parse->rtable = lappend(subroot.parse->rtable,
00836                                             makeNode(RangeTblEntry));
00837 
00838         /*
00839          * If this isn't the first child Query, generate duplicates of all
00840          * subquery RTEs, and adjust Var numbering to reference the
00841          * duplicates. To simplify the loop logic, we scan the original rtable
00842          * not the copy just made by adjust_appendrel_attrs; that should be OK
00843          * since subquery RTEs couldn't contain any references to the target
00844          * rel.
00845          */
00846         if (final_rtable != NIL)
00847         {
00848             ListCell   *lr;
00849 
00850             rti = 1;
00851             foreach(lr, parse->rtable)
00852             {
00853                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(lr);
00854 
00855                 if (rte->rtekind == RTE_SUBQUERY)
00856                 {
00857                     Index       newrti;
00858 
00859                     /*
00860                      * The RTE can't contain any references to its own RT
00861                      * index, so we can save a few cycles by applying
00862                      * ChangeVarNodes before we append the RTE to the
00863                      * rangetable.
00864                      */
00865                     newrti = list_length(subroot.parse->rtable) + 1;
00866                     ChangeVarNodes((Node *) subroot.parse, rti, newrti, 0);
00867                     ChangeVarNodes((Node *) subroot.rowMarks, rti, newrti, 0);
00868                     rte = copyObject(rte);
00869                     subroot.parse->rtable = lappend(subroot.parse->rtable,
00870                                                     rte);
00871                 }
00872                 rti++;
00873             }
00874         }
00875 
00876         /* We needn't modify the child's append_rel_list */
00877         /* There shouldn't be any OJ or LATERAL info to translate, as yet */
00878         Assert(subroot.join_info_list == NIL);
00879         Assert(subroot.lateral_info_list == NIL);
00880         /* and we haven't created PlaceHolderInfos, either */
00881         Assert(subroot.placeholder_list == NIL);
00882         /* hack to mark target relation as an inheritance partition */
00883         subroot.hasInheritedTarget = true;
00884 
00885         /* Generate plan */
00886         subplan = grouping_planner(&subroot, 0.0 /* retrieve all tuples */ );
00887 
00888         /*
00889          * If this child rel was excluded by constraint exclusion, exclude it
00890          * from the result plan.
00891          */
00892         if (is_dummy_plan(subplan))
00893             continue;
00894 
00895         subplans = lappend(subplans, subplan);
00896 
00897         /*
00898          * If this is the first non-excluded child, its post-planning rtable
00899          * becomes the initial contents of final_rtable; otherwise, append
00900          * just its modified subquery RTEs to final_rtable.
00901          */
00902         if (final_rtable == NIL)
00903             final_rtable = subroot.parse->rtable;
00904         else
00905             final_rtable = list_concat(final_rtable,
00906                                        list_copy_tail(subroot.parse->rtable,
00907                                                  list_length(final_rtable)));
00908 
00909         /*
00910          * We need to collect all the RelOptInfos from all child plans into
00911          * the main PlannerInfo, since setrefs.c will need them.  We use the
00912          * last child's simple_rel_array (previous ones are too short), so we
00913          * have to propagate forward the RelOptInfos that were already built
00914          * in previous children.
00915          */
00916         Assert(subroot.simple_rel_array_size >= save_rel_array_size);
00917         for (rti = 1; rti < save_rel_array_size; rti++)
00918         {
00919             RelOptInfo *brel = save_rel_array[rti];
00920 
00921             if (brel)
00922                 subroot.simple_rel_array[rti] = brel;
00923         }
00924         save_rel_array_size = subroot.simple_rel_array_size;
00925         save_rel_array = subroot.simple_rel_array;
00926 
00927         /* Make sure any initplans from this rel get into the outer list */
00928         root->init_plans = subroot.init_plans;
00929 
00930         /* Build list of target-relation RT indexes */
00931         resultRelations = lappend_int(resultRelations, appinfo->child_relid);
00932 
00933         /* Build list of per-relation RETURNING targetlists */
00934         if (parse->returningList)
00935             returningLists = lappend(returningLists,
00936                                      subroot.parse->returningList);
00937     }
00938 
00939     /* Mark result as unordered (probably unnecessary) */
00940     root->query_pathkeys = NIL;
00941 
00942     /*
00943      * If we managed to exclude every child rel, return a dummy plan; it
00944      * doesn't even need a ModifyTable node.
00945      */
00946     if (subplans == NIL)
00947     {
00948         /* although dummy, it must have a valid tlist for executor */
00949         List       *tlist;
00950 
00951         tlist = preprocess_targetlist(root, parse->targetList);
00952         return (Plan *) make_result(root,
00953                                     tlist,
00954                                     (Node *) list_make1(makeBoolConst(false,
00955                                                                       false)),
00956                                     NULL);
00957     }
00958 
00959     /*
00960      * Put back the final adjusted rtable into the master copy of the Query.
00961      */
00962     parse->rtable = final_rtable;
00963     root->simple_rel_array_size = save_rel_array_size;
00964     root->simple_rel_array = save_rel_array;
00965 
00966     /*
00967      * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node will have
00968      * dealt with fetching non-locked marked rows, else we need to have
00969      * ModifyTable do that.
00970      */
00971     if (parse->rowMarks)
00972         rowMarks = NIL;
00973     else
00974         rowMarks = root->rowMarks;
00975 
00976     /* And last, tack on a ModifyTable node to do the UPDATE/DELETE work */
00977     return (Plan *) make_modifytable(root,
00978                                      parse->commandType,
00979                                      parse->canSetTag,
00980                                      resultRelations,
00981                                      subplans,
00982                                      returningLists,
00983                                      rowMarks,
00984                                      SS_assign_special_param(root));
00985 }
00986 
00987 /*--------------------
00988  * grouping_planner
00989  *    Perform planning steps related to grouping, aggregation, etc.
00990  *    This primarily means adding top-level processing to the basic
00991  *    query plan produced by query_planner.
00992  *
00993  * tuple_fraction is the fraction of tuples we expect will be retrieved
00994  *
00995  * tuple_fraction is interpreted as follows:
00996  *    0: expect all tuples to be retrieved (normal case)
00997  *    0 < tuple_fraction < 1: expect the given fraction of tuples available
00998  *      from the plan to be retrieved
00999  *    tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
01000  *      expected to be retrieved (ie, a LIMIT specification)
01001  *
01002  * Returns a query plan.  Also, root->query_pathkeys is returned as the
01003  * actual output ordering of the plan (in pathkey format).
01004  *--------------------
01005  */
01006 static Plan *
01007 grouping_planner(PlannerInfo *root, double tuple_fraction)
01008 {
01009     Query      *parse = root->parse;
01010     List       *tlist = parse->targetList;
01011     int64       offset_est = 0;
01012     int64       count_est = 0;
01013     double      limit_tuples = -1.0;
01014     Plan       *result_plan;
01015     List       *current_pathkeys;
01016     double      dNumGroups = 0;
01017     bool        use_hashed_distinct = false;
01018     bool        tested_hashed_distinct = false;
01019 
01020     /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
01021     if (parse->limitCount || parse->limitOffset)
01022     {
01023         tuple_fraction = preprocess_limit(root, tuple_fraction,
01024                                           &offset_est, &count_est);
01025 
01026         /*
01027          * If we have a known LIMIT, and don't have an unknown OFFSET, we can
01028          * estimate the effects of using a bounded sort.
01029          */
01030         if (count_est > 0 && offset_est >= 0)
01031             limit_tuples = (double) count_est + (double) offset_est;
01032     }
01033 
01034     if (parse->setOperations)
01035     {
01036         List       *set_sortclauses;
01037 
01038         /*
01039          * If there's a top-level ORDER BY, assume we have to fetch all the
01040          * tuples.  This might be too simplistic given all the hackery below
01041          * to possibly avoid the sort; but the odds of accurate estimates here
01042          * are pretty low anyway.
01043          */
01044         if (parse->sortClause)
01045             tuple_fraction = 0.0;
01046 
01047         /*
01048          * Construct the plan for set operations.  The result will not need
01049          * any work except perhaps a top-level sort and/or LIMIT.  Note that
01050          * any special work for recursive unions is the responsibility of
01051          * plan_set_operations.
01052          */
01053         result_plan = plan_set_operations(root, tuple_fraction,
01054                                           &set_sortclauses);
01055 
01056         /*
01057          * Calculate pathkeys representing the sort order (if any) of the set
01058          * operation's result.  We have to do this before overwriting the sort
01059          * key information...
01060          */
01061         current_pathkeys = make_pathkeys_for_sortclauses(root,
01062                                                          set_sortclauses,
01063                                                      result_plan->targetlist);
01064 
01065         /*
01066          * We should not need to call preprocess_targetlist, since we must be
01067          * in a SELECT query node.  Instead, use the targetlist returned by
01068          * plan_set_operations (since this tells whether it returned any
01069          * resjunk columns!), and transfer any sort key information from the
01070          * original tlist.
01071          */
01072         Assert(parse->commandType == CMD_SELECT);
01073 
01074         tlist = postprocess_setop_tlist(copyObject(result_plan->targetlist),
01075                                         tlist);
01076 
01077         /*
01078          * Can't handle FOR [KEY] UPDATE/SHARE here (parser should have checked
01079          * already, but let's make sure).
01080          */
01081         if (parse->rowMarks)
01082             ereport(ERROR,
01083                     (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
01084                      errmsg("row-level locks are not allowed with UNION/INTERSECT/EXCEPT")));
01085 
01086         /*
01087          * Calculate pathkeys that represent result ordering requirements
01088          */
01089         Assert(parse->distinctClause == NIL);
01090         root->sort_pathkeys = make_pathkeys_for_sortclauses(root,
01091                                                             parse->sortClause,
01092                                                             tlist);
01093     }
01094     else
01095     {
01096         /* No set operations, do regular planning */
01097         List       *sub_tlist;
01098         double      sub_limit_tuples;
01099         AttrNumber *groupColIdx = NULL;
01100         bool        need_tlist_eval = true;
01101         standard_qp_extra qp_extra;
01102         Path       *cheapest_path;
01103         Path       *sorted_path;
01104         Path       *best_path;
01105         long        numGroups = 0;
01106         AggClauseCosts agg_costs;
01107         int         numGroupCols;
01108         double      path_rows;
01109         int         path_width;
01110         bool        use_hashed_grouping = false;
01111         WindowFuncLists *wflists = NULL;
01112         List       *activeWindows = NIL;
01113 
01114         MemSet(&agg_costs, 0, sizeof(AggClauseCosts));
01115 
01116         /* A recursive query should always have setOperations */
01117         Assert(!root->hasRecursion);
01118 
01119         /* Preprocess GROUP BY clause, if any */
01120         if (parse->groupClause)
01121             preprocess_groupclause(root);
01122         numGroupCols = list_length(parse->groupClause);
01123 
01124         /* Preprocess targetlist */
01125         tlist = preprocess_targetlist(root, tlist);
01126 
01127         /*
01128          * Locate any window functions in the tlist.  (We don't need to look
01129          * anywhere else, since expressions used in ORDER BY will be in there
01130          * too.)  Note that they could all have been eliminated by constant
01131          * folding, in which case we don't need to do any more work.
01132          */
01133         if (parse->hasWindowFuncs)
01134         {
01135             wflists = find_window_functions((Node *) tlist,
01136                                             list_length(parse->windowClause));
01137             if (wflists->numWindowFuncs > 0)
01138                 activeWindows = select_active_windows(root, wflists);
01139             else
01140                 parse->hasWindowFuncs = false;
01141         }
01142 
01143         /*
01144          * Generate appropriate target list for subplan; may be different from
01145          * tlist if grouping or aggregation is needed.
01146          */
01147         sub_tlist = make_subplanTargetList(root, tlist,
01148                                            &groupColIdx, &need_tlist_eval);
01149 
01150         /*
01151          * Do aggregate preprocessing, if the query has any aggs.
01152          *
01153          * Note: think not that we can turn off hasAggs if we find no aggs. It
01154          * is possible for constant-expression simplification to remove all
01155          * explicit references to aggs, but we still have to follow the
01156          * aggregate semantics (eg, producing only one output row).
01157          */
01158         if (parse->hasAggs)
01159         {
01160             /*
01161              * Collect statistics about aggregates for estimating costs. Note:
01162              * we do not attempt to detect duplicate aggregates here; a
01163              * somewhat-overestimated cost is okay for our present purposes.
01164              */
01165             count_agg_clauses(root, (Node *) tlist, &agg_costs);
01166             count_agg_clauses(root, parse->havingQual, &agg_costs);
01167 
01168             /*
01169              * Preprocess MIN/MAX aggregates, if any.  Note: be careful about
01170              * adding logic between here and the optimize_minmax_aggregates
01171              * call.  Anything that is needed in MIN/MAX-optimizable cases
01172              * will have to be duplicated in planagg.c.
01173              */
01174             preprocess_minmax_aggregates(root, tlist);
01175         }
01176 
01177         /*
01178          * Figure out whether there's a hard limit on the number of rows that
01179          * query_planner's result subplan needs to return.  Even if we know a
01180          * hard limit overall, it doesn't apply if the query has any
01181          * grouping/aggregation operations.
01182          */
01183         if (parse->groupClause ||
01184             parse->distinctClause ||
01185             parse->hasAggs ||
01186             parse->hasWindowFuncs ||
01187             root->hasHavingQual)
01188             sub_limit_tuples = -1.0;
01189         else
01190             sub_limit_tuples = limit_tuples;
01191 
01192         /* Set up data needed by standard_qp_callback */
01193         qp_extra.tlist = tlist;
01194         qp_extra.activeWindows = activeWindows;
01195 
01196         /*
01197          * Generate the best unsorted and presorted paths for this Query (but
01198          * note there may not be any presorted path).  We also generate (in
01199          * standard_qp_callback) pathkey representations of the query's sort
01200          * clause, distinct clause, etc.  query_planner will also estimate the
01201          * number of groups in the query.
01202          */
01203         query_planner(root, sub_tlist, tuple_fraction, sub_limit_tuples,
01204                       standard_qp_callback, &qp_extra,
01205                       &cheapest_path, &sorted_path, &dNumGroups);
01206 
01207         /*
01208          * Extract rowcount and width estimates for possible use in grouping
01209          * decisions.  Beware here of the possibility that
01210          * cheapest_path->parent is NULL (ie, there is no FROM clause).
01211          */
01212         if (cheapest_path->parent)
01213         {
01214             path_rows = cheapest_path->parent->rows;
01215             path_width = cheapest_path->parent->width;
01216         }
01217         else
01218         {
01219             path_rows = 1;      /* assume non-set result */
01220             path_width = 100;   /* arbitrary */
01221         }
01222 
01223         if (parse->groupClause)
01224         {
01225             /*
01226              * If grouping, decide whether to use sorted or hashed grouping.
01227              */
01228             use_hashed_grouping =
01229                 choose_hashed_grouping(root,
01230                                        tuple_fraction, limit_tuples,
01231                                        path_rows, path_width,
01232                                        cheapest_path, sorted_path,
01233                                        dNumGroups, &agg_costs);
01234             /* Also convert # groups to long int --- but 'ware overflow! */
01235             numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
01236         }
01237         else if (parse->distinctClause && sorted_path &&
01238                  !root->hasHavingQual && !parse->hasAggs && !activeWindows)
01239         {
01240             /*
01241              * We'll reach the DISTINCT stage without any intermediate
01242              * processing, so figure out whether we will want to hash or not
01243              * so we can choose whether to use cheapest or sorted path.
01244              */
01245             use_hashed_distinct =
01246                 choose_hashed_distinct(root,
01247                                        tuple_fraction, limit_tuples,
01248                                        path_rows, path_width,
01249                                        cheapest_path->startup_cost,
01250                                        cheapest_path->total_cost,
01251                                        sorted_path->startup_cost,
01252                                        sorted_path->total_cost,
01253                                        sorted_path->pathkeys,
01254                                        dNumGroups);
01255             tested_hashed_distinct = true;
01256         }
01257 
01258         /*
01259          * Select the best path.  If we are doing hashed grouping, we will
01260          * always read all the input tuples, so use the cheapest-total path.
01261          * Otherwise, trust query_planner's decision about which to use.
01262          */
01263         if (use_hashed_grouping || use_hashed_distinct || !sorted_path)
01264             best_path = cheapest_path;
01265         else
01266             best_path = sorted_path;
01267 
01268         /*
01269          * Check to see if it's possible to optimize MIN/MAX aggregates. If
01270          * so, we will forget all the work we did so far to choose a "regular"
01271          * path ... but we had to do it anyway to be able to tell which way is
01272          * cheaper.
01273          */
01274         result_plan = optimize_minmax_aggregates(root,
01275                                                  tlist,
01276                                                  &agg_costs,
01277                                                  best_path);
01278         if (result_plan != NULL)
01279         {
01280             /*
01281              * optimize_minmax_aggregates generated the full plan, with the
01282              * right tlist, and it has no sort order.
01283              */
01284             current_pathkeys = NIL;
01285         }
01286         else
01287         {
01288             /*
01289              * Normal case --- create a plan according to query_planner's
01290              * results.
01291              */
01292             bool        need_sort_for_grouping = false;
01293 
01294             result_plan = create_plan(root, best_path);
01295             current_pathkeys = best_path->pathkeys;
01296 
01297             /* Detect if we'll need an explicit sort for grouping */
01298             if (parse->groupClause && !use_hashed_grouping &&
01299               !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
01300             {
01301                 need_sort_for_grouping = true;
01302 
01303                 /*
01304                  * Always override create_plan's tlist, so that we don't sort
01305                  * useless data from a "physical" tlist.
01306                  */
01307                 need_tlist_eval = true;
01308             }
01309 
01310             /*
01311              * create_plan returns a plan with just a "flat" tlist of required
01312              * Vars.  Usually we need to insert the sub_tlist as the tlist of
01313              * the top plan node.  However, we can skip that if we determined
01314              * that whatever create_plan chose to return will be good enough.
01315              */
01316             if (need_tlist_eval)
01317             {
01318                 /*
01319                  * If the top-level plan node is one that cannot do expression
01320                  * evaluation and its existing target list isn't already what
01321                  * we need, we must insert a Result node to project the
01322                  * desired tlist.
01323                  */
01324                 if (!is_projection_capable_plan(result_plan) &&
01325                     !tlist_same_exprs(sub_tlist, result_plan->targetlist))
01326                 {
01327                     result_plan = (Plan *) make_result(root,
01328                                                        sub_tlist,
01329                                                        NULL,
01330                                                        result_plan);
01331                 }
01332                 else
01333                 {
01334                     /*
01335                      * Otherwise, just replace the subplan's flat tlist with
01336                      * the desired tlist.
01337                      */
01338                     result_plan->targetlist = sub_tlist;
01339                 }
01340 
01341                 /*
01342                  * Also, account for the cost of evaluation of the sub_tlist.
01343                  * See comments for add_tlist_costs_to_plan() for more info.
01344                  */
01345                 add_tlist_costs_to_plan(root, result_plan, sub_tlist);
01346             }
01347             else
01348             {
01349                 /*
01350                  * Since we're using create_plan's tlist and not the one
01351                  * make_subplanTargetList calculated, we have to refigure any
01352                  * grouping-column indexes make_subplanTargetList computed.
01353                  */
01354                 locate_grouping_columns(root, tlist, result_plan->targetlist,
01355                                         groupColIdx);
01356             }
01357 
01358             /*
01359              * Insert AGG or GROUP node if needed, plus an explicit sort step
01360              * if necessary.
01361              *
01362              * HAVING clause, if any, becomes qual of the Agg or Group node.
01363              */
01364             if (use_hashed_grouping)
01365             {
01366                 /* Hashed aggregate plan --- no sort needed */
01367                 result_plan = (Plan *) make_agg(root,
01368                                                 tlist,
01369                                                 (List *) parse->havingQual,
01370                                                 AGG_HASHED,
01371                                                 &agg_costs,
01372                                                 numGroupCols,
01373                                                 groupColIdx,
01374                                     extract_grouping_ops(parse->groupClause),
01375                                                 numGroups,
01376                                                 result_plan);
01377                 /* Hashed aggregation produces randomly-ordered results */
01378                 current_pathkeys = NIL;
01379             }
01380             else if (parse->hasAggs)
01381             {
01382                 /* Plain aggregate plan --- sort if needed */
01383                 AggStrategy aggstrategy;
01384 
01385                 if (parse->groupClause)
01386                 {
01387                     if (need_sort_for_grouping)
01388                     {
01389                         result_plan = (Plan *)
01390                             make_sort_from_groupcols(root,
01391                                                      parse->groupClause,
01392                                                      groupColIdx,
01393                                                      result_plan);
01394                         current_pathkeys = root->group_pathkeys;
01395                     }
01396                     aggstrategy = AGG_SORTED;
01397 
01398                     /*
01399                      * The AGG node will not change the sort ordering of its
01400                      * groups, so current_pathkeys describes the result too.
01401                      */
01402                 }
01403                 else
01404                 {
01405                     aggstrategy = AGG_PLAIN;
01406                     /* Result will be only one row anyway; no sort order */
01407                     current_pathkeys = NIL;
01408                 }
01409 
01410                 result_plan = (Plan *) make_agg(root,
01411                                                 tlist,
01412                                                 (List *) parse->havingQual,
01413                                                 aggstrategy,
01414                                                 &agg_costs,
01415                                                 numGroupCols,
01416                                                 groupColIdx,
01417                                     extract_grouping_ops(parse->groupClause),
01418                                                 numGroups,
01419                                                 result_plan);
01420             }
01421             else if (parse->groupClause)
01422             {
01423                 /*
01424                  * GROUP BY without aggregation, so insert a group node (plus
01425                  * the appropriate sort node, if necessary).
01426                  *
01427                  * Add an explicit sort if we couldn't make the path come out
01428                  * the way the GROUP node needs it.
01429                  */
01430                 if (need_sort_for_grouping)
01431                 {
01432                     result_plan = (Plan *)
01433                         make_sort_from_groupcols(root,
01434                                                  parse->groupClause,
01435                                                  groupColIdx,
01436                                                  result_plan);
01437                     current_pathkeys = root->group_pathkeys;
01438                 }
01439 
01440                 result_plan = (Plan *) make_group(root,
01441                                                   tlist,
01442                                                   (List *) parse->havingQual,
01443                                                   numGroupCols,
01444                                                   groupColIdx,
01445                                     extract_grouping_ops(parse->groupClause),
01446                                                   dNumGroups,
01447                                                   result_plan);
01448                 /* The Group node won't change sort ordering */
01449             }
01450             else if (root->hasHavingQual)
01451             {
01452                 /*
01453                  * No aggregates, and no GROUP BY, but we have a HAVING qual.
01454                  * This is a degenerate case in which we are supposed to emit
01455                  * either 0 or 1 row depending on whether HAVING succeeds.
01456                  * Furthermore, there cannot be any variables in either HAVING
01457                  * or the targetlist, so we actually do not need the FROM
01458                  * table at all!  We can just throw away the plan-so-far and
01459                  * generate a Result node.  This is a sufficiently unusual
01460                  * corner case that it's not worth contorting the structure of
01461                  * this routine to avoid having to generate the plan in the
01462                  * first place.
01463                  */
01464                 result_plan = (Plan *) make_result(root,
01465                                                    tlist,
01466                                                    parse->havingQual,
01467                                                    NULL);
01468             }
01469         }                       /* end of non-minmax-aggregate case */
01470 
01471         /*
01472          * Since each window function could require a different sort order, we
01473          * stack up a WindowAgg node for each window, with sort steps between
01474          * them as needed.
01475          */
01476         if (activeWindows)
01477         {
01478             List       *window_tlist;
01479             ListCell   *l;
01480 
01481             /*
01482              * If the top-level plan node is one that cannot do expression
01483              * evaluation, we must insert a Result node to project the desired
01484              * tlist.  (In some cases this might not really be required, but
01485              * it's not worth trying to avoid it.  In particular, think not to
01486              * skip adding the Result if the initial window_tlist matches the
01487              * top-level plan node's output, because we might change the tlist
01488              * inside the following loop.)  Note that on second and subsequent
01489              * passes through the following loop, the top-level node will be a
01490              * WindowAgg which we know can project; so we only need to check
01491              * once.
01492              */
01493             if (!is_projection_capable_plan(result_plan))
01494             {
01495                 result_plan = (Plan *) make_result(root,
01496                                                    NIL,
01497                                                    NULL,
01498                                                    result_plan);
01499             }
01500 
01501             /*
01502              * The "base" targetlist for all steps of the windowing process is
01503              * a flat tlist of all Vars and Aggs needed in the result.  (In
01504              * some cases we wouldn't need to propagate all of these all the
01505              * way to the top, since they might only be needed as inputs to
01506              * WindowFuncs.  It's probably not worth trying to optimize that
01507              * though.)  We also add window partitioning and sorting
01508              * expressions to the base tlist, to ensure they're computed only
01509              * once at the bottom of the stack (that's critical for volatile
01510              * functions).  As we climb up the stack, we'll add outputs for
01511              * the WindowFuncs computed at each level.
01512              */
01513             window_tlist = make_windowInputTargetList(root,
01514                                                       tlist,
01515                                                       activeWindows);
01516 
01517             /*
01518              * The copyObject steps here are needed to ensure that each plan
01519              * node has a separately modifiable tlist.  (XXX wouldn't a
01520              * shallow list copy do for that?)
01521              */
01522             result_plan->targetlist = (List *) copyObject(window_tlist);
01523 
01524             foreach(l, activeWindows)
01525             {
01526                 WindowClause *wc = (WindowClause *) lfirst(l);
01527                 List       *window_pathkeys;
01528                 int         partNumCols;
01529                 AttrNumber *partColIdx;
01530                 Oid        *partOperators;
01531                 int         ordNumCols;
01532                 AttrNumber *ordColIdx;
01533                 Oid        *ordOperators;
01534 
01535                 window_pathkeys = make_pathkeys_for_window(root,
01536                                                            wc,
01537                                                            tlist);
01538 
01539                 /*
01540                  * This is a bit tricky: we build a sort node even if we don't
01541                  * really have to sort.  Even when no explicit sort is needed,
01542                  * we need to have suitable resjunk items added to the input
01543                  * plan's tlist for any partitioning or ordering columns that
01544                  * aren't plain Vars.  (In theory, make_windowInputTargetList
01545                  * should have provided all such columns, but let's not assume
01546                  * that here.)  Furthermore, this way we can use existing
01547                  * infrastructure to identify which input columns are the
01548                  * interesting ones.
01549                  */
01550                 if (window_pathkeys)
01551                 {
01552                     Sort       *sort_plan;
01553 
01554                     sort_plan = make_sort_from_pathkeys(root,
01555                                                         result_plan,
01556                                                         window_pathkeys,
01557                                                         -1.0);
01558                     if (!pathkeys_contained_in(window_pathkeys,
01559                                                current_pathkeys))
01560                     {
01561                         /* we do indeed need to sort */
01562                         result_plan = (Plan *) sort_plan;
01563                         current_pathkeys = window_pathkeys;
01564                     }
01565                     /* In either case, extract the per-column information */
01566                     get_column_info_for_window(root, wc, tlist,
01567                                                sort_plan->numCols,
01568                                                sort_plan->sortColIdx,
01569                                                &partNumCols,
01570                                                &partColIdx,
01571                                                &partOperators,
01572                                                &ordNumCols,
01573                                                &ordColIdx,
01574                                                &ordOperators);
01575                 }
01576                 else
01577                 {
01578                     /* empty window specification, nothing to sort */
01579                     partNumCols = 0;
01580                     partColIdx = NULL;
01581                     partOperators = NULL;
01582                     ordNumCols = 0;
01583                     ordColIdx = NULL;
01584                     ordOperators = NULL;
01585                 }
01586 
01587                 if (lnext(l))
01588                 {
01589                     /* Add the current WindowFuncs to the running tlist */
01590                     window_tlist = add_to_flat_tlist(window_tlist,
01591                                            wflists->windowFuncs[wc->winref]);
01592                 }
01593                 else
01594                 {
01595                     /* Install the original tlist in the topmost WindowAgg */
01596                     window_tlist = tlist;
01597                 }
01598 
01599                 /* ... and make the WindowAgg plan node */
01600                 result_plan = (Plan *)
01601                     make_windowagg(root,
01602                                    (List *) copyObject(window_tlist),
01603                                    wflists->windowFuncs[wc->winref],
01604                                    wc->winref,
01605                                    partNumCols,
01606                                    partColIdx,
01607                                    partOperators,
01608                                    ordNumCols,
01609                                    ordColIdx,
01610                                    ordOperators,
01611                                    wc->frameOptions,
01612                                    wc->startOffset,
01613                                    wc->endOffset,
01614                                    result_plan);
01615             }
01616         }
01617     }                           /* end of if (setOperations) */
01618 
01619     /*
01620      * If there is a DISTINCT clause, add the necessary node(s).
01621      */
01622     if (parse->distinctClause)
01623     {
01624         double      dNumDistinctRows;
01625         long        numDistinctRows;
01626 
01627         /*
01628          * If there was grouping or aggregation, use the current number of
01629          * rows as the estimated number of DISTINCT rows (ie, assume the
01630          * result was already mostly unique).  If not, use the number of
01631          * distinct-groups calculated by query_planner.
01632          */
01633         if (parse->groupClause || root->hasHavingQual || parse->hasAggs)
01634             dNumDistinctRows = result_plan->plan_rows;
01635         else
01636             dNumDistinctRows = dNumGroups;
01637 
01638         /* Also convert to long int --- but 'ware overflow! */
01639         numDistinctRows = (long) Min(dNumDistinctRows, (double) LONG_MAX);
01640 
01641         /* Choose implementation method if we didn't already */
01642         if (!tested_hashed_distinct)
01643         {
01644             /*
01645              * At this point, either hashed or sorted grouping will have to
01646              * work from result_plan, so we pass that as both "cheapest" and
01647              * "sorted".
01648              */
01649             use_hashed_distinct =
01650                 choose_hashed_distinct(root,
01651                                        tuple_fraction, limit_tuples,
01652                                        result_plan->plan_rows,
01653                                        result_plan->plan_width,
01654                                        result_plan->startup_cost,
01655                                        result_plan->total_cost,
01656                                        result_plan->startup_cost,
01657                                        result_plan->total_cost,
01658                                        current_pathkeys,
01659                                        dNumDistinctRows);
01660         }
01661 
01662         if (use_hashed_distinct)
01663         {
01664             /* Hashed aggregate plan --- no sort needed */
01665             result_plan = (Plan *) make_agg(root,
01666                                             result_plan->targetlist,
01667                                             NIL,
01668                                             AGG_HASHED,
01669                                             NULL,
01670                                           list_length(parse->distinctClause),
01671                                  extract_grouping_cols(parse->distinctClause,
01672                                                     result_plan->targetlist),
01673                                  extract_grouping_ops(parse->distinctClause),
01674                                             numDistinctRows,
01675                                             result_plan);
01676             /* Hashed aggregation produces randomly-ordered results */
01677             current_pathkeys = NIL;
01678         }
01679         else
01680         {
01681             /*
01682              * Use a Unique node to implement DISTINCT.  Add an explicit sort
01683              * if we couldn't make the path come out the way the Unique node
01684              * needs it.  If we do have to sort, always sort by the more
01685              * rigorous of DISTINCT and ORDER BY, to avoid a second sort
01686              * below.  However, for regular DISTINCT, don't sort now if we
01687              * don't have to --- sorting afterwards will likely be cheaper,
01688              * and also has the possibility of optimizing via LIMIT.  But for
01689              * DISTINCT ON, we *must* force the final sort now, else it won't
01690              * have the desired behavior.
01691              */
01692             List       *needed_pathkeys;
01693 
01694             if (parse->hasDistinctOn &&
01695                 list_length(root->distinct_pathkeys) <
01696                 list_length(root->sort_pathkeys))
01697                 needed_pathkeys = root->sort_pathkeys;
01698             else
01699                 needed_pathkeys = root->distinct_pathkeys;
01700 
01701             if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
01702             {
01703                 if (list_length(root->distinct_pathkeys) >=
01704                     list_length(root->sort_pathkeys))
01705                     current_pathkeys = root->distinct_pathkeys;
01706                 else
01707                 {
01708                     current_pathkeys = root->sort_pathkeys;
01709                     /* Assert checks that parser didn't mess up... */
01710                     Assert(pathkeys_contained_in(root->distinct_pathkeys,
01711                                                  current_pathkeys));
01712                 }
01713 
01714                 result_plan = (Plan *) make_sort_from_pathkeys(root,
01715                                                                result_plan,
01716                                                             current_pathkeys,
01717                                                                -1.0);
01718             }
01719 
01720             result_plan = (Plan *) make_unique(result_plan,
01721                                                parse->distinctClause);
01722             result_plan->plan_rows = dNumDistinctRows;
01723             /* The Unique node won't change sort ordering */
01724         }
01725     }
01726 
01727     /*
01728      * If ORDER BY was given and we were not able to make the plan come out in
01729      * the right order, add an explicit sort step.
01730      */
01731     if (parse->sortClause)
01732     {
01733         if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
01734         {
01735             result_plan = (Plan *) make_sort_from_pathkeys(root,
01736                                                            result_plan,
01737                                                          root->sort_pathkeys,
01738                                                            limit_tuples);
01739             current_pathkeys = root->sort_pathkeys;
01740         }
01741     }
01742 
01743     /*
01744      * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node. (Note: we
01745      * intentionally test parse->rowMarks not root->rowMarks here. If there
01746      * are only non-locking rowmarks, they should be handled by the
01747      * ModifyTable node instead.)
01748      */
01749     if (parse->rowMarks)
01750     {
01751         result_plan = (Plan *) make_lockrows(result_plan,
01752                                              root->rowMarks,
01753                                              SS_assign_special_param(root));
01754 
01755         /*
01756          * The result can no longer be assumed sorted, since locking might
01757          * cause the sort key columns to be replaced with new values.
01758          */
01759         current_pathkeys = NIL;
01760     }
01761 
01762     /*
01763      * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node.
01764      */
01765     if (limit_needed(parse))
01766     {
01767         result_plan = (Plan *) make_limit(result_plan,
01768                                           parse->limitOffset,
01769                                           parse->limitCount,
01770                                           offset_est,
01771                                           count_est);
01772     }
01773 
01774     /*
01775      * Return the actual output ordering in query_pathkeys for possible use by
01776      * an outer query level.
01777      */
01778     root->query_pathkeys = current_pathkeys;
01779 
01780     return result_plan;
01781 }
01782 
01783 /*
01784  * add_tlist_costs_to_plan
01785  *
01786  * Estimate the execution costs associated with evaluating the targetlist
01787  * expressions, and add them to the cost estimates for the Plan node.
01788  *
01789  * If the tlist contains set-returning functions, also inflate the Plan's cost
01790  * and plan_rows estimates accordingly.  (Hence, this must be called *after*
01791  * any logic that uses plan_rows to, eg, estimate qual evaluation costs.)
01792  *
01793  * Note: during initial stages of planning, we mostly consider plan nodes with
01794  * "flat" tlists, containing just Vars.  So their evaluation cost is zero
01795  * according to the model used by cost_qual_eval() (or if you prefer, the cost
01796  * is factored into cpu_tuple_cost).  Thus we can avoid accounting for tlist
01797  * cost throughout query_planner() and subroutines.  But once we apply a
01798  * tlist that might contain actual operators, sub-selects, etc, we'd better
01799  * account for its cost.  Any set-returning functions in the tlist must also
01800  * affect the estimated rowcount.
01801  *
01802  * Once grouping_planner() has applied a general tlist to the topmost
01803  * scan/join plan node, any tlist eval cost for added-on nodes should be
01804  * accounted for as we create those nodes.  Presently, of the node types we
01805  * can add on later, only Agg, WindowAgg, and Group project new tlists (the
01806  * rest just copy their input tuples) --- so make_agg(), make_windowagg() and
01807  * make_group() are responsible for calling this function to account for their
01808  * tlist costs.
01809  */
01810 void
01811 add_tlist_costs_to_plan(PlannerInfo *root, Plan *plan, List *tlist)
01812 {
01813     QualCost    tlist_cost;
01814     double      tlist_rows;
01815 
01816     cost_qual_eval(&tlist_cost, tlist, root);
01817     plan->startup_cost += tlist_cost.startup;
01818     plan->total_cost += tlist_cost.startup +
01819         tlist_cost.per_tuple * plan->plan_rows;
01820 
01821     tlist_rows = tlist_returns_set_rows(tlist);
01822     if (tlist_rows > 1)
01823     {
01824         /*
01825          * We assume that execution costs of the tlist proper were all
01826          * accounted for by cost_qual_eval.  However, it still seems
01827          * appropriate to charge something more for the executor's general
01828          * costs of processing the added tuples.  The cost is probably less
01829          * than cpu_tuple_cost, though, so we arbitrarily use half of that.
01830          */
01831         plan->total_cost += plan->plan_rows * (tlist_rows - 1) *
01832             cpu_tuple_cost / 2;
01833 
01834         plan->plan_rows *= tlist_rows;
01835     }
01836 }
01837 
01838 /*
01839  * Detect whether a plan node is a "dummy" plan created when a relation
01840  * is deemed not to need scanning due to constraint exclusion.
01841  *
01842  * Currently, such dummy plans are Result nodes with constant FALSE
01843  * filter quals (see set_dummy_rel_pathlist and create_append_plan).
01844  *
01845  * XXX this probably ought to be somewhere else, but not clear where.
01846  */
01847 bool
01848 is_dummy_plan(Plan *plan)
01849 {
01850     if (IsA(plan, Result))
01851     {
01852         List       *rcqual = (List *) ((Result *) plan)->resconstantqual;
01853 
01854         if (list_length(rcqual) == 1)
01855         {
01856             Const      *constqual = (Const *) linitial(rcqual);
01857 
01858             if (constqual && IsA(constqual, Const))
01859             {
01860                 if (!constqual->constisnull &&
01861                     !DatumGetBool(constqual->constvalue))
01862                     return true;
01863             }
01864         }
01865     }
01866     return false;
01867 }
01868 
01869 /*
01870  * Create a bitmapset of the RT indexes of live base relations
01871  *
01872  * Helper for preprocess_rowmarks ... at this point in the proceedings,
01873  * the only good way to distinguish baserels from appendrel children
01874  * is to see what is in the join tree.
01875  */
01876 static Bitmapset *
01877 get_base_rel_indexes(Node *jtnode)
01878 {
01879     Bitmapset  *result;
01880 
01881     if (jtnode == NULL)
01882         return NULL;
01883     if (IsA(jtnode, RangeTblRef))
01884     {
01885         int         varno = ((RangeTblRef *) jtnode)->rtindex;
01886 
01887         result = bms_make_singleton(varno);
01888     }
01889     else if (IsA(jtnode, FromExpr))
01890     {
01891         FromExpr   *f = (FromExpr *) jtnode;
01892         ListCell   *l;
01893 
01894         result = NULL;
01895         foreach(l, f->fromlist)
01896             result = bms_join(result,
01897                               get_base_rel_indexes(lfirst(l)));
01898     }
01899     else if (IsA(jtnode, JoinExpr))
01900     {
01901         JoinExpr   *j = (JoinExpr *) jtnode;
01902 
01903         result = bms_join(get_base_rel_indexes(j->larg),
01904                           get_base_rel_indexes(j->rarg));
01905     }
01906     else
01907     {
01908         elog(ERROR, "unrecognized node type: %d",
01909              (int) nodeTag(jtnode));
01910         result = NULL;          /* keep compiler quiet */
01911     }
01912     return result;
01913 }
01914 
01915 /*
01916  * preprocess_rowmarks - set up PlanRowMarks if needed
01917  */
01918 static void
01919 preprocess_rowmarks(PlannerInfo *root)
01920 {
01921     Query      *parse = root->parse;
01922     Bitmapset  *rels;
01923     List       *prowmarks;
01924     ListCell   *l;
01925     int         i;
01926 
01927     if (parse->rowMarks)
01928     {
01929         /*
01930          * We've got trouble if FOR [KEY] UPDATE/SHARE appears inside grouping,
01931          * since grouping renders a reference to individual tuple CTIDs
01932          * invalid.  This is also checked at parse time, but that's
01933          * insufficient because of rule substitution, query pullup, etc.
01934          */
01935         CheckSelectLocking(parse);
01936     }
01937     else
01938     {
01939         /*
01940          * We only need rowmarks for UPDATE, DELETE, or FOR [KEY] UPDATE/SHARE.
01941          */
01942         if (parse->commandType != CMD_UPDATE &&
01943             parse->commandType != CMD_DELETE)
01944             return;
01945     }
01946 
01947     /*
01948      * We need to have rowmarks for all base relations except the target. We
01949      * make a bitmapset of all base rels and then remove the items we don't
01950      * need or have FOR [KEY] UPDATE/SHARE marks for.
01951      */
01952     rels = get_base_rel_indexes((Node *) parse->jointree);
01953     if (parse->resultRelation)
01954         rels = bms_del_member(rels, parse->resultRelation);
01955 
01956     /*
01957      * Convert RowMarkClauses to PlanRowMark representation.
01958      */
01959     prowmarks = NIL;
01960     foreach(l, parse->rowMarks)
01961     {
01962         RowMarkClause *rc = (RowMarkClause *) lfirst(l);
01963         RangeTblEntry *rte = rt_fetch(rc->rti, parse->rtable);
01964         PlanRowMark *newrc;
01965 
01966         /*
01967          * Currently, it is syntactically impossible to have FOR UPDATE et al
01968          * applied to an update/delete target rel.  If that ever becomes
01969          * possible, we should drop the target from the PlanRowMark list.
01970          */
01971         Assert(rc->rti != parse->resultRelation);
01972 
01973         /*
01974          * Ignore RowMarkClauses for subqueries; they aren't real tables and
01975          * can't support true locking.  Subqueries that got flattened into the
01976          * main query should be ignored completely.  Any that didn't will get
01977          * ROW_MARK_COPY items in the next loop.
01978          */
01979         if (rte->rtekind != RTE_RELATION)
01980             continue;
01981 
01982         /*
01983          * Similarly, ignore RowMarkClauses for foreign tables; foreign tables
01984          * will instead get ROW_MARK_COPY items in the next loop.  (FDWs might
01985          * choose to do something special while fetching their rows, but that
01986          * is of no concern here.)
01987          */
01988         if (rte->relkind == RELKIND_FOREIGN_TABLE)
01989             continue;
01990 
01991         rels = bms_del_member(rels, rc->rti);
01992 
01993         newrc = makeNode(PlanRowMark);
01994         newrc->rti = newrc->prti = rc->rti;
01995         newrc->rowmarkId = ++(root->glob->lastRowMarkId);
01996         switch (rc->strength)
01997         {
01998             case LCS_FORUPDATE:
01999                 newrc->markType = ROW_MARK_EXCLUSIVE;
02000                 break;
02001             case LCS_FORNOKEYUPDATE:
02002                 newrc->markType = ROW_MARK_NOKEYEXCLUSIVE;
02003                 break;
02004             case LCS_FORSHARE:
02005                 newrc->markType = ROW_MARK_SHARE;
02006                 break;
02007             case LCS_FORKEYSHARE:
02008                 newrc->markType = ROW_MARK_KEYSHARE;
02009                 break;
02010         }
02011         newrc->noWait = rc->noWait;
02012         newrc->isParent = false;
02013 
02014         prowmarks = lappend(prowmarks, newrc);
02015     }
02016 
02017     /*
02018      * Now, add rowmarks for any non-target, non-locked base relations.
02019      */
02020     i = 0;
02021     foreach(l, parse->rtable)
02022     {
02023         RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
02024         PlanRowMark *newrc;
02025 
02026         i++;
02027         if (!bms_is_member(i, rels))
02028             continue;
02029 
02030         newrc = makeNode(PlanRowMark);
02031         newrc->rti = newrc->prti = i;
02032         newrc->rowmarkId = ++(root->glob->lastRowMarkId);
02033         /* real tables support REFERENCE, anything else needs COPY */
02034         if (rte->rtekind == RTE_RELATION &&
02035             rte->relkind != RELKIND_FOREIGN_TABLE)
02036             newrc->markType = ROW_MARK_REFERENCE;
02037         else
02038             newrc->markType = ROW_MARK_COPY;
02039         newrc->noWait = false;  /* doesn't matter */
02040         newrc->isParent = false;
02041 
02042         prowmarks = lappend(prowmarks, newrc);
02043     }
02044 
02045     root->rowMarks = prowmarks;
02046 }
02047 
02048 /*
02049  * preprocess_limit - do pre-estimation for LIMIT and/or OFFSET clauses
02050  *
02051  * We try to estimate the values of the LIMIT/OFFSET clauses, and pass the
02052  * results back in *count_est and *offset_est.  These variables are set to
02053  * 0 if the corresponding clause is not present, and -1 if it's present
02054  * but we couldn't estimate the value for it.  (The "0" convention is OK
02055  * for OFFSET but a little bit bogus for LIMIT: effectively we estimate
02056  * LIMIT 0 as though it were LIMIT 1.  But this is in line with the planner's
02057  * usual practice of never estimating less than one row.)  These values will
02058  * be passed to make_limit, which see if you change this code.
02059  *
02060  * The return value is the suitably adjusted tuple_fraction to use for
02061  * planning the query.  This adjustment is not overridable, since it reflects
02062  * plan actions that grouping_planner() will certainly take, not assumptions
02063  * about context.
02064  */
02065 static double
02066 preprocess_limit(PlannerInfo *root, double tuple_fraction,
02067                  int64 *offset_est, int64 *count_est)
02068 {
02069     Query      *parse = root->parse;
02070     Node       *est;
02071     double      limit_fraction;
02072 
02073     /* Should not be called unless LIMIT or OFFSET */
02074     Assert(parse->limitCount || parse->limitOffset);
02075 
02076     /*
02077      * Try to obtain the clause values.  We use estimate_expression_value
02078      * primarily because it can sometimes do something useful with Params.
02079      */
02080     if (parse->limitCount)
02081     {
02082         est = estimate_expression_value(root, parse->limitCount);
02083         if (est && IsA(est, Const))
02084         {
02085             if (((Const *) est)->constisnull)
02086             {
02087                 /* NULL indicates LIMIT ALL, ie, no limit */
02088                 *count_est = 0; /* treat as not present */
02089             }
02090             else
02091             {
02092                 *count_est = DatumGetInt64(((Const *) est)->constvalue);
02093                 if (*count_est <= 0)
02094                     *count_est = 1;     /* force to at least 1 */
02095             }
02096         }
02097         else
02098             *count_est = -1;    /* can't estimate */
02099     }
02100     else
02101         *count_est = 0;         /* not present */
02102 
02103     if (parse->limitOffset)
02104     {
02105         est = estimate_expression_value(root, parse->limitOffset);
02106         if (est && IsA(est, Const))
02107         {
02108             if (((Const *) est)->constisnull)
02109             {
02110                 /* Treat NULL as no offset; the executor will too */
02111                 *offset_est = 0;    /* treat as not present */
02112             }
02113             else
02114             {
02115                 *offset_est = DatumGetInt64(((Const *) est)->constvalue);
02116                 if (*offset_est < 0)
02117                     *offset_est = 0;    /* less than 0 is same as 0 */
02118             }
02119         }
02120         else
02121             *offset_est = -1;   /* can't estimate */
02122     }
02123     else
02124         *offset_est = 0;        /* not present */
02125 
02126     if (*count_est != 0)
02127     {
02128         /*
02129          * A LIMIT clause limits the absolute number of tuples returned.
02130          * However, if it's not a constant LIMIT then we have to guess; for
02131          * lack of a better idea, assume 10% of the plan's result is wanted.
02132          */
02133         if (*count_est < 0 || *offset_est < 0)
02134         {
02135             /* LIMIT or OFFSET is an expression ... punt ... */
02136             limit_fraction = 0.10;
02137         }
02138         else
02139         {
02140             /* LIMIT (plus OFFSET, if any) is max number of tuples needed */
02141             limit_fraction = (double) *count_est + (double) *offset_est;
02142         }
02143 
02144         /*
02145          * If we have absolute limits from both caller and LIMIT, use the
02146          * smaller value; likewise if they are both fractional.  If one is
02147          * fractional and the other absolute, we can't easily determine which
02148          * is smaller, but we use the heuristic that the absolute will usually
02149          * be smaller.
02150          */
02151         if (tuple_fraction >= 1.0)
02152         {
02153             if (limit_fraction >= 1.0)
02154             {
02155                 /* both absolute */
02156                 tuple_fraction = Min(tuple_fraction, limit_fraction);
02157             }
02158             else
02159             {
02160                 /* caller absolute, limit fractional; use caller's value */
02161             }
02162         }
02163         else if (tuple_fraction > 0.0)
02164         {
02165             if (limit_fraction >= 1.0)
02166             {
02167                 /* caller fractional, limit absolute; use limit */
02168                 tuple_fraction = limit_fraction;
02169             }
02170             else
02171             {
02172                 /* both fractional */
02173                 tuple_fraction = Min(tuple_fraction, limit_fraction);
02174             }
02175         }
02176         else
02177         {
02178             /* no info from caller, just use limit */
02179             tuple_fraction = limit_fraction;
02180         }
02181     }
02182     else if (*offset_est != 0 && tuple_fraction > 0.0)
02183     {
02184         /*
02185          * We have an OFFSET but no LIMIT.  This acts entirely differently
02186          * from the LIMIT case: here, we need to increase rather than decrease
02187          * the caller's tuple_fraction, because the OFFSET acts to cause more
02188          * tuples to be fetched instead of fewer.  This only matters if we got
02189          * a tuple_fraction > 0, however.
02190          *
02191          * As above, use 10% if OFFSET is present but unestimatable.
02192          */
02193         if (*offset_est < 0)
02194             limit_fraction = 0.10;
02195         else
02196             limit_fraction = (double) *offset_est;
02197 
02198         /*
02199          * If we have absolute counts from both caller and OFFSET, add them
02200          * together; likewise if they are both fractional.  If one is
02201          * fractional and the other absolute, we want to take the larger, and
02202          * we heuristically assume that's the fractional one.
02203          */
02204         if (tuple_fraction >= 1.0)
02205         {
02206             if (limit_fraction >= 1.0)
02207             {
02208                 /* both absolute, so add them together */
02209                 tuple_fraction += limit_fraction;
02210             }
02211             else
02212             {
02213                 /* caller absolute, limit fractional; use limit */
02214                 tuple_fraction = limit_fraction;
02215             }
02216         }
02217         else
02218         {
02219             if (limit_fraction >= 1.0)
02220             {
02221                 /* caller fractional, limit absolute; use caller's value */
02222             }
02223             else
02224             {
02225                 /* both fractional, so add them together */
02226                 tuple_fraction += limit_fraction;
02227                 if (tuple_fraction >= 1.0)
02228                     tuple_fraction = 0.0;       /* assume fetch all */
02229             }
02230         }
02231     }
02232 
02233     return tuple_fraction;
02234 }
02235 
02236 /*
02237  * limit_needed - do we actually need a Limit plan node?
02238  *
02239  * If we have constant-zero OFFSET and constant-null LIMIT, we can skip adding
02240  * a Limit node.  This is worth checking for because "OFFSET 0" is a common
02241  * locution for an optimization fence.  (Because other places in the planner
02242  * merely check whether parse->limitOffset isn't NULL, it will still work as
02243  * an optimization fence --- we're just suppressing unnecessary run-time
02244  * overhead.)
02245  *
02246  * This might look like it could be merged into preprocess_limit, but there's
02247  * a key distinction: here we need hard constants in OFFSET/LIMIT, whereas
02248  * in preprocess_limit it's good enough to consider estimated values.
02249  */
02250 static bool
02251 limit_needed(Query *parse)
02252 {
02253     Node       *node;
02254 
02255     node = parse->limitCount;
02256     if (node)
02257     {
02258         if (IsA(node, Const))
02259         {
02260             /* NULL indicates LIMIT ALL, ie, no limit */
02261             if (!((Const *) node)->constisnull)
02262                 return true;    /* LIMIT with a constant value */
02263         }
02264         else
02265             return true;        /* non-constant LIMIT */
02266     }
02267 
02268     node = parse->limitOffset;
02269     if (node)
02270     {
02271         if (IsA(node, Const))
02272         {
02273             /* Treat NULL as no offset; the executor would too */
02274             if (!((Const *) node)->constisnull)
02275             {
02276                 int64   offset = DatumGetInt64(((Const *) node)->constvalue);
02277 
02278                 /* Executor would treat less-than-zero same as zero */
02279                 if (offset > 0)
02280                     return true;    /* OFFSET with a positive value */
02281             }
02282         }
02283         else
02284             return true;        /* non-constant OFFSET */
02285     }
02286 
02287     return false;               /* don't need a Limit plan node */
02288 }
02289 
02290 
02291 /*
02292  * preprocess_groupclause - do preparatory work on GROUP BY clause
02293  *
02294  * The idea here is to adjust the ordering of the GROUP BY elements
02295  * (which in itself is semantically insignificant) to match ORDER BY,
02296  * thereby allowing a single sort operation to both implement the ORDER BY
02297  * requirement and set up for a Unique step that implements GROUP BY.
02298  *
02299  * In principle it might be interesting to consider other orderings of the
02300  * GROUP BY elements, which could match the sort ordering of other
02301  * possible plans (eg an indexscan) and thereby reduce cost.  We don't
02302  * bother with that, though.  Hashed grouping will frequently win anyway.
02303  *
02304  * Note: we need no comparable processing of the distinctClause because
02305  * the parser already enforced that that matches ORDER BY.
02306  */
02307 static void
02308 preprocess_groupclause(PlannerInfo *root)
02309 {
02310     Query      *parse = root->parse;
02311     List       *new_groupclause;
02312     bool        partial_match;
02313     ListCell   *sl;
02314     ListCell   *gl;
02315 
02316     /* If no ORDER BY, nothing useful to do here */
02317     if (parse->sortClause == NIL)
02318         return;
02319 
02320     /*
02321      * Scan the ORDER BY clause and construct a list of matching GROUP BY
02322      * items, but only as far as we can make a matching prefix.
02323      *
02324      * This code assumes that the sortClause contains no duplicate items.
02325      */
02326     new_groupclause = NIL;
02327     foreach(sl, parse->sortClause)
02328     {
02329         SortGroupClause *sc = (SortGroupClause *) lfirst(sl);
02330 
02331         foreach(gl, parse->groupClause)
02332         {
02333             SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
02334 
02335             if (equal(gc, sc))
02336             {
02337                 new_groupclause = lappend(new_groupclause, gc);
02338                 break;
02339             }
02340         }
02341         if (gl == NULL)
02342             break;              /* no match, so stop scanning */
02343     }
02344 
02345     /* Did we match all of the ORDER BY list, or just some of it? */
02346     partial_match = (sl != NULL);
02347 
02348     /* If no match at all, no point in reordering GROUP BY */
02349     if (new_groupclause == NIL)
02350         return;
02351 
02352     /*
02353      * Add any remaining GROUP BY items to the new list, but only if we were
02354      * able to make a complete match.  In other words, we only rearrange the
02355      * GROUP BY list if the result is that one list is a prefix of the other
02356      * --- otherwise there's no possibility of a common sort.  Also, give up
02357      * if there are any non-sortable GROUP BY items, since then there's no
02358      * hope anyway.
02359      */
02360     foreach(gl, parse->groupClause)
02361     {
02362         SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
02363 
02364         if (list_member_ptr(new_groupclause, gc))
02365             continue;           /* it matched an ORDER BY item */
02366         if (partial_match)
02367             return;             /* give up, no common sort possible */
02368         if (!OidIsValid(gc->sortop))
02369             return;             /* give up, GROUP BY can't be sorted */
02370         new_groupclause = lappend(new_groupclause, gc);
02371     }
02372 
02373     /* Success --- install the rearranged GROUP BY list */
02374     Assert(list_length(parse->groupClause) == list_length(new_groupclause));
02375     parse->groupClause = new_groupclause;
02376 }
02377 
02378 /*
02379  * Compute query_pathkeys and other pathkeys during plan generation
02380  */
02381 static void
02382 standard_qp_callback(PlannerInfo *root, void *extra)
02383 {
02384     Query      *parse = root->parse;
02385     standard_qp_extra *qp_extra = (standard_qp_extra *) extra;
02386     List       *tlist = qp_extra->tlist;
02387     List       *activeWindows = qp_extra->activeWindows;
02388 
02389     /*
02390      * Calculate pathkeys that represent grouping/ordering requirements.  The
02391      * sortClause is certainly sort-able, but GROUP BY and DISTINCT might not
02392      * be, in which case we just leave their pathkeys empty.
02393      */
02394     if (parse->groupClause &&
02395         grouping_is_sortable(parse->groupClause))
02396         root->group_pathkeys =
02397             make_pathkeys_for_sortclauses(root,
02398                                           parse->groupClause,
02399                                           tlist);
02400     else
02401         root->group_pathkeys = NIL;
02402 
02403     /* We consider only the first (bottom) window in pathkeys logic */
02404     if (activeWindows != NIL)
02405     {
02406         WindowClause *wc = (WindowClause *) linitial(activeWindows);
02407 
02408         root->window_pathkeys = make_pathkeys_for_window(root,
02409                                                          wc,
02410                                                          tlist);
02411     }
02412     else
02413         root->window_pathkeys = NIL;
02414 
02415     if (parse->distinctClause &&
02416         grouping_is_sortable(parse->distinctClause))
02417         root->distinct_pathkeys =
02418             make_pathkeys_for_sortclauses(root,
02419                                           parse->distinctClause,
02420                                           tlist);
02421     else
02422         root->distinct_pathkeys = NIL;
02423 
02424     root->sort_pathkeys =
02425         make_pathkeys_for_sortclauses(root,
02426                                       parse->sortClause,
02427                                       tlist);
02428 
02429     /*
02430      * Figure out whether we want a sorted result from query_planner.
02431      *
02432      * If we have a sortable GROUP BY clause, then we want a result sorted
02433      * properly for grouping.  Otherwise, if we have window functions to
02434      * evaluate, we try to sort for the first window.  Otherwise, if there's a
02435      * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
02436      * we try to produce output that's sufficiently well sorted for the
02437      * DISTINCT.  Otherwise, if there is an ORDER BY clause, we want to sort
02438      * by the ORDER BY clause.
02439      *
02440      * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
02441      * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
02442      * that might just leave us failing to exploit an available sort order at
02443      * all.  Needs more thought.  The choice for DISTINCT versus ORDER BY is
02444      * much easier, since we know that the parser ensured that one is a
02445      * superset of the other.
02446      */
02447     if (root->group_pathkeys)
02448         root->query_pathkeys = root->group_pathkeys;
02449     else if (root->window_pathkeys)
02450         root->query_pathkeys = root->window_pathkeys;
02451     else if (list_length(root->distinct_pathkeys) >
02452              list_length(root->sort_pathkeys))
02453         root->query_pathkeys = root->distinct_pathkeys;
02454     else if (root->sort_pathkeys)
02455         root->query_pathkeys = root->sort_pathkeys;
02456     else
02457         root->query_pathkeys = NIL;
02458 }
02459 
02460 /*
02461  * choose_hashed_grouping - should we use hashed grouping?
02462  *
02463  * Returns TRUE to select hashing, FALSE to select sorting.
02464  */
02465 static bool
02466 choose_hashed_grouping(PlannerInfo *root,
02467                        double tuple_fraction, double limit_tuples,
02468                        double path_rows, int path_width,
02469                        Path *cheapest_path, Path *sorted_path,
02470                        double dNumGroups, AggClauseCosts *agg_costs)
02471 {
02472     Query      *parse = root->parse;
02473     int         numGroupCols = list_length(parse->groupClause);
02474     bool        can_hash;
02475     bool        can_sort;
02476     Size        hashentrysize;
02477     List       *target_pathkeys;
02478     List       *current_pathkeys;
02479     Path        hashed_p;
02480     Path        sorted_p;
02481 
02482     /*
02483      * Executor doesn't support hashed aggregation with DISTINCT or ORDER BY
02484      * aggregates.  (Doing so would imply storing *all* the input values in
02485      * the hash table, and/or running many sorts in parallel, either of which
02486      * seems like a certain loser.)
02487      */
02488     can_hash = (agg_costs->numOrderedAggs == 0 &&
02489                 grouping_is_hashable(parse->groupClause));
02490     can_sort = grouping_is_sortable(parse->groupClause);
02491 
02492     /* Quick out if only one choice is workable */
02493     if (!(can_hash && can_sort))
02494     {
02495         if (can_hash)
02496             return true;
02497         else if (can_sort)
02498             return false;
02499         else
02500             ereport(ERROR,
02501                     (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
02502                      errmsg("could not implement GROUP BY"),
02503                      errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
02504     }
02505 
02506     /* Prefer sorting when enable_hashagg is off */
02507     if (!enable_hashagg)
02508         return false;
02509 
02510     /*
02511      * Don't do it if it doesn't look like the hashtable will fit into
02512      * work_mem.
02513      */
02514 
02515     /* Estimate per-hash-entry space at tuple width... */
02516     hashentrysize = MAXALIGN(path_width) + MAXALIGN(sizeof(MinimalTupleData));
02517     /* plus space for pass-by-ref transition values... */
02518     hashentrysize += agg_costs->transitionSpace;
02519     /* plus the per-hash-entry overhead */
02520     hashentrysize += hash_agg_entry_size(agg_costs->numAggs);
02521 
02522     if (hashentrysize * dNumGroups > work_mem * 1024L)
02523         return false;
02524 
02525     /*
02526      * When we have both GROUP BY and DISTINCT, use the more-rigorous of
02527      * DISTINCT and ORDER BY as the assumed required output sort order. This
02528      * is an oversimplification because the DISTINCT might get implemented via
02529      * hashing, but it's not clear that the case is common enough (or that our
02530      * estimates are good enough) to justify trying to solve it exactly.
02531      */
02532     if (list_length(root->distinct_pathkeys) >
02533         list_length(root->sort_pathkeys))
02534         target_pathkeys = root->distinct_pathkeys;
02535     else
02536         target_pathkeys = root->sort_pathkeys;
02537 
02538     /*
02539      * See if the estimated cost is no more than doing it the other way. While
02540      * avoiding the need for sorted input is usually a win, the fact that the
02541      * output won't be sorted may be a loss; so we need to do an actual cost
02542      * comparison.
02543      *
02544      * We need to consider cheapest_path + hashagg [+ final sort] versus
02545      * either cheapest_path [+ sort] + group or agg [+ final sort] or
02546      * presorted_path + group or agg [+ final sort] where brackets indicate a
02547      * step that may not be needed. We assume query_planner() will have
02548      * returned a presorted path only if it's a winner compared to
02549      * cheapest_path for this purpose.
02550      *
02551      * These path variables are dummies that just hold cost fields; we don't
02552      * make actual Paths for these steps.
02553      */
02554     cost_agg(&hashed_p, root, AGG_HASHED, agg_costs,
02555              numGroupCols, dNumGroups,
02556              cheapest_path->startup_cost, cheapest_path->total_cost,
02557              path_rows);
02558     /* Result of hashed agg is always unsorted */
02559     if (target_pathkeys)
02560         cost_sort(&hashed_p, root, target_pathkeys, hashed_p.total_cost,
02561                   dNumGroups, path_width,
02562                   0.0, work_mem, limit_tuples);
02563 
02564     if (sorted_path)
02565     {
02566         sorted_p.startup_cost = sorted_path->startup_cost;
02567         sorted_p.total_cost = sorted_path->total_cost;
02568         current_pathkeys = sorted_path->pathkeys;
02569     }
02570     else
02571     {
02572         sorted_p.startup_cost = cheapest_path->startup_cost;
02573         sorted_p.total_cost = cheapest_path->total_cost;
02574         current_pathkeys = cheapest_path->pathkeys;
02575     }
02576     if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
02577     {
02578         cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost,
02579                   path_rows, path_width,
02580                   0.0, work_mem, -1.0);
02581         current_pathkeys = root->group_pathkeys;
02582     }
02583 
02584     if (parse->hasAggs)
02585         cost_agg(&sorted_p, root, AGG_SORTED, agg_costs,
02586                  numGroupCols, dNumGroups,
02587                  sorted_p.startup_cost, sorted_p.total_cost,
02588                  path_rows);
02589     else
02590         cost_group(&sorted_p, root, numGroupCols, dNumGroups,
02591                    sorted_p.startup_cost, sorted_p.total_cost,
02592                    path_rows);
02593     /* The Agg or Group node will preserve ordering */
02594     if (target_pathkeys &&
02595         !pathkeys_contained_in(target_pathkeys, current_pathkeys))
02596         cost_sort(&sorted_p, root, target_pathkeys, sorted_p.total_cost,
02597                   dNumGroups, path_width,
02598                   0.0, work_mem, limit_tuples);
02599 
02600     /*
02601      * Now make the decision using the top-level tuple fraction.  First we
02602      * have to convert an absolute count (LIMIT) into fractional form.
02603      */
02604     if (tuple_fraction >= 1.0)
02605         tuple_fraction /= dNumGroups;
02606 
02607     if (compare_fractional_path_costs(&hashed_p, &sorted_p,
02608                                       tuple_fraction) < 0)
02609     {
02610         /* Hashed is cheaper, so use it */
02611         return true;
02612     }
02613     return false;
02614 }
02615 
02616 /*
02617  * choose_hashed_distinct - should we use hashing for DISTINCT?
02618  *
02619  * This is fairly similar to choose_hashed_grouping, but there are enough
02620  * differences that it doesn't seem worth trying to unify the two functions.
02621  * (One difference is that we sometimes apply this after forming a Plan,
02622  * so the input alternatives can't be represented as Paths --- instead we
02623  * pass in the costs as individual variables.)
02624  *
02625  * But note that making the two choices independently is a bit bogus in
02626  * itself.  If the two could be combined into a single choice operation
02627  * it'd probably be better, but that seems far too unwieldy to be practical,
02628  * especially considering that the combination of GROUP BY and DISTINCT
02629  * isn't very common in real queries.  By separating them, we are giving
02630  * extra preference to using a sorting implementation when a common sort key
02631  * is available ... and that's not necessarily wrong anyway.
02632  *
02633  * Returns TRUE to select hashing, FALSE to select sorting.
02634  */
02635 static bool
02636 choose_hashed_distinct(PlannerInfo *root,
02637                        double tuple_fraction, double limit_tuples,
02638                        double path_rows, int path_width,
02639                        Cost cheapest_startup_cost, Cost cheapest_total_cost,
02640                        Cost sorted_startup_cost, Cost sorted_total_cost,
02641                        List *sorted_pathkeys,
02642                        double dNumDistinctRows)
02643 {
02644     Query      *parse = root->parse;
02645     int         numDistinctCols = list_length(parse->distinctClause);
02646     bool        can_sort;
02647     bool        can_hash;
02648     Size        hashentrysize;
02649     List       *current_pathkeys;
02650     List       *needed_pathkeys;
02651     Path        hashed_p;
02652     Path        sorted_p;
02653 
02654     /*
02655      * If we have a sortable DISTINCT ON clause, we always use sorting. This
02656      * enforces the expected behavior of DISTINCT ON.
02657      */
02658     can_sort = grouping_is_sortable(parse->distinctClause);
02659     if (can_sort && parse->hasDistinctOn)
02660         return false;
02661 
02662     can_hash = grouping_is_hashable(parse->distinctClause);
02663 
02664     /* Quick out if only one choice is workable */
02665     if (!(can_hash && can_sort))
02666     {
02667         if (can_hash)
02668             return true;
02669         else if (can_sort)
02670             return false;
02671         else
02672             ereport(ERROR,
02673                     (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
02674                      errmsg("could not implement DISTINCT"),
02675                      errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
02676     }
02677 
02678     /* Prefer sorting when enable_hashagg is off */
02679     if (!enable_hashagg)
02680         return false;
02681 
02682     /*
02683      * Don't do it if it doesn't look like the hashtable will fit into
02684      * work_mem.
02685      */
02686     hashentrysize = MAXALIGN(path_width) + MAXALIGN(sizeof(MinimalTupleData));
02687 
02688     if (hashentrysize * dNumDistinctRows > work_mem * 1024L)
02689         return false;
02690 
02691     /*
02692      * See if the estimated cost is no more than doing it the other way. While
02693      * avoiding the need for sorted input is usually a win, the fact that the
02694      * output won't be sorted may be a loss; so we need to do an actual cost
02695      * comparison.
02696      *
02697      * We need to consider cheapest_path + hashagg [+ final sort] versus
02698      * sorted_path [+ sort] + group [+ final sort] where brackets indicate a
02699      * step that may not be needed.
02700      *
02701      * These path variables are dummies that just hold cost fields; we don't
02702      * make actual Paths for these steps.
02703      */
02704     cost_agg(&hashed_p, root, AGG_HASHED, NULL,
02705              numDistinctCols, dNumDistinctRows,
02706              cheapest_startup_cost, cheapest_total_cost,
02707              path_rows);
02708 
02709     /*
02710      * Result of hashed agg is always unsorted, so if ORDER BY is present we
02711      * need to charge for the final sort.
02712      */
02713     if (parse->sortClause)
02714         cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost,
02715                   dNumDistinctRows, path_width,
02716                   0.0, work_mem, limit_tuples);
02717 
02718     /*
02719      * Now for the GROUP case.  See comments in grouping_planner about the
02720      * sorting choices here --- this code should match that code.
02721      */
02722     sorted_p.startup_cost = sorted_startup_cost;
02723     sorted_p.total_cost = sorted_total_cost;
02724     current_pathkeys = sorted_pathkeys;
02725     if (parse->hasDistinctOn &&
02726         list_length(root->distinct_pathkeys) <
02727         list_length(root->sort_pathkeys))
02728         needed_pathkeys = root->sort_pathkeys;
02729     else
02730         needed_pathkeys = root->distinct_pathkeys;
02731     if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
02732     {
02733         if (list_length(root->distinct_pathkeys) >=
02734             list_length(root->sort_pathkeys))
02735             current_pathkeys = root->distinct_pathkeys;
02736         else
02737             current_pathkeys = root->sort_pathkeys;
02738         cost_sort(&sorted_p, root, current_pathkeys, sorted_p.total_cost,
02739                   path_rows, path_width,
02740                   0.0, work_mem, -1.0);
02741     }
02742     cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows,
02743                sorted_p.startup_cost, sorted_p.total_cost,
02744                path_rows);
02745     if (parse->sortClause &&
02746         !pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
02747         cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost,
02748                   dNumDistinctRows, path_width,
02749                   0.0, work_mem, limit_tuples);
02750 
02751     /*
02752      * Now make the decision using the top-level tuple fraction.  First we
02753      * have to convert an absolute count (LIMIT) into fractional form.
02754      */
02755     if (tuple_fraction >= 1.0)
02756         tuple_fraction /= dNumDistinctRows;
02757 
02758     if (compare_fractional_path_costs(&hashed_p, &sorted_p,
02759                                       tuple_fraction) < 0)
02760     {
02761         /* Hashed is cheaper, so use it */
02762         return true;
02763     }
02764     return false;
02765 }
02766 
02767 /*
02768  * make_subplanTargetList
02769  *    Generate appropriate target list when grouping is required.
02770  *
02771  * When grouping_planner inserts grouping or aggregation plan nodes
02772  * above the scan/join plan constructed by query_planner+create_plan,
02773  * we typically want the scan/join plan to emit a different target list
02774  * than the outer plan nodes should have.  This routine generates the
02775  * correct target list for the scan/join subplan.
02776  *
02777  * The initial target list passed from the parser already contains entries
02778  * for all ORDER BY and GROUP BY expressions, but it will not have entries
02779  * for variables used only in HAVING clauses; so we need to add those
02780  * variables to the subplan target list.  Also, we flatten all expressions
02781  * except GROUP BY items into their component variables; the other expressions
02782  * will be computed by the inserted nodes rather than by the subplan.
02783  * For example, given a query like
02784  *      SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
02785  * we want to pass this targetlist to the subplan:
02786  *      a+b,c,d
02787  * where the a+b target will be used by the Sort/Group steps, and the
02788  * other targets will be used for computing the final results.
02789  *
02790  * If we are grouping or aggregating, *and* there are no non-Var grouping
02791  * expressions, then the returned tlist is effectively dummy; we do not
02792  * need to force it to be evaluated, because all the Vars it contains
02793  * should be present in the "flat" tlist generated by create_plan, though
02794  * possibly in a different order.  In that case we'll use create_plan's tlist,
02795  * and the tlist made here is only needed as input to query_planner to tell
02796  * it which Vars are needed in the output of the scan/join plan.
02797  *
02798  * 'tlist' is the query's target list.
02799  * 'groupColIdx' receives an array of column numbers for the GROUP BY
02800  *          expressions (if there are any) in the returned target list.
02801  * 'need_tlist_eval' is set true if we really need to evaluate the
02802  *          returned tlist as-is.
02803  *
02804  * The result is the targetlist to be passed to query_planner.
02805  */
02806 static List *
02807 make_subplanTargetList(PlannerInfo *root,
02808                        List *tlist,
02809                        AttrNumber **groupColIdx,
02810                        bool *need_tlist_eval)
02811 {
02812     Query      *parse = root->parse;
02813     List       *sub_tlist;
02814     List       *non_group_cols;
02815     List       *non_group_vars;
02816     int         numCols;
02817 
02818     *groupColIdx = NULL;
02819 
02820     /*
02821      * If we're not grouping or aggregating, there's nothing to do here;
02822      * query_planner should receive the unmodified target list.
02823      */
02824     if (!parse->hasAggs && !parse->groupClause && !root->hasHavingQual &&
02825         !parse->hasWindowFuncs)
02826     {
02827         *need_tlist_eval = true;
02828         return tlist;
02829     }
02830 
02831     /*
02832      * Otherwise, we must build a tlist containing all grouping columns, plus
02833      * any other Vars mentioned in the targetlist and HAVING qual.
02834      */
02835     sub_tlist = NIL;
02836     non_group_cols = NIL;
02837     *need_tlist_eval = false;   /* only eval if not flat tlist */
02838 
02839     numCols = list_length(parse->groupClause);
02840     if (numCols > 0)
02841     {
02842         /*
02843          * If grouping, create sub_tlist entries for all GROUP BY columns, and
02844          * make an array showing where the group columns are in the sub_tlist.
02845          *
02846          * Note: with this implementation, the array entries will always be
02847          * 1..N, but we don't want callers to assume that.
02848          */
02849         AttrNumber *grpColIdx;
02850         ListCell   *tl;
02851 
02852         grpColIdx = (AttrNumber *) palloc0(sizeof(AttrNumber) * numCols);
02853         *groupColIdx = grpColIdx;
02854 
02855         foreach(tl, tlist)
02856         {
02857             TargetEntry *tle = (TargetEntry *) lfirst(tl);
02858             int         colno;
02859 
02860             colno = get_grouping_column_index(parse, tle);
02861             if (colno >= 0)
02862             {
02863                 /*
02864                  * It's a grouping column, so add it to the result tlist and
02865                  * remember its resno in grpColIdx[].
02866                  */
02867                 TargetEntry *newtle;
02868 
02869                 newtle = makeTargetEntry(tle->expr,
02870                                          list_length(sub_tlist) + 1,
02871                                          NULL,
02872                                          false);
02873                 sub_tlist = lappend(sub_tlist, newtle);
02874 
02875                 Assert(grpColIdx[colno] == 0);  /* no dups expected */
02876                 grpColIdx[colno] = newtle->resno;
02877 
02878                 if (!(newtle->expr && IsA(newtle->expr, Var)))
02879                     *need_tlist_eval = true;    /* tlist contains non Vars */
02880             }
02881             else
02882             {
02883                 /*
02884                  * Non-grouping column, so just remember the expression for
02885                  * later call to pull_var_clause.  There's no need for
02886                  * pull_var_clause to examine the TargetEntry node itself.
02887                  */
02888                 non_group_cols = lappend(non_group_cols, tle->expr);
02889             }
02890         }
02891     }
02892     else
02893     {
02894         /*
02895          * With no grouping columns, just pass whole tlist to pull_var_clause.
02896          * Need (shallow) copy to avoid damaging input tlist below.
02897          */
02898         non_group_cols = list_copy(tlist);
02899     }
02900 
02901     /*
02902      * If there's a HAVING clause, we'll need the Vars it uses, too.
02903      */
02904     if (parse->havingQual)
02905         non_group_cols = lappend(non_group_cols, parse->havingQual);
02906 
02907     /*
02908      * Pull out all the Vars mentioned in non-group cols (plus HAVING), and
02909      * add them to the result tlist if not already present.  (A Var used
02910      * directly as a GROUP BY item will be present already.)  Note this
02911      * includes Vars used in resjunk items, so we are covering the needs of
02912      * ORDER BY and window specifications.  Vars used within Aggrefs will be
02913      * pulled out here, too.
02914      */
02915     non_group_vars = pull_var_clause((Node *) non_group_cols,
02916                                      PVC_RECURSE_AGGREGATES,
02917                                      PVC_INCLUDE_PLACEHOLDERS);
02918     sub_tlist = add_to_flat_tlist(sub_tlist, non_group_vars);
02919 
02920     /* clean up cruft */
02921     list_free(non_group_vars);
02922     list_free(non_group_cols);
02923 
02924     return sub_tlist;
02925 }
02926 
02927 /*
02928  * get_grouping_column_index
02929  *      Get the GROUP BY column position, if any, of a targetlist entry.
02930  *
02931  * Returns the index (counting from 0) of the TLE in the GROUP BY list, or -1
02932  * if it's not a grouping column.  Note: the result is unique because the
02933  * parser won't make multiple groupClause entries for the same TLE.
02934  */
02935 static int
02936 get_grouping_column_index(Query *parse, TargetEntry *tle)
02937 {
02938     int         colno = 0;
02939     Index       ressortgroupref = tle->ressortgroupref;
02940     ListCell   *gl;
02941 
02942     /* No need to search groupClause if TLE hasn't got a sortgroupref */
02943     if (ressortgroupref == 0)
02944         return -1;
02945 
02946     foreach(gl, parse->groupClause)
02947     {
02948         SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
02949 
02950         if (grpcl->tleSortGroupRef == ressortgroupref)
02951             return colno;
02952         colno++;
02953     }
02954 
02955     return -1;
02956 }
02957 
02958 /*
02959  * locate_grouping_columns
02960  *      Locate grouping columns in the tlist chosen by create_plan.
02961  *
02962  * This is only needed if we don't use the sub_tlist chosen by
02963  * make_subplanTargetList.  We have to forget the column indexes found
02964  * by that routine and re-locate the grouping exprs in the real sub_tlist.
02965  */
02966 static void
02967 locate_grouping_columns(PlannerInfo *root,
02968                         List *tlist,
02969                         List *sub_tlist,
02970                         AttrNumber *groupColIdx)
02971 {
02972     int         keyno = 0;
02973     ListCell   *gl;
02974 
02975     /*
02976      * No work unless grouping.
02977      */
02978     if (!root->parse->groupClause)
02979     {
02980         Assert(groupColIdx == NULL);
02981         return;
02982     }
02983     Assert(groupColIdx != NULL);
02984 
02985     foreach(gl, root->parse->groupClause)
02986     {
02987         SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
02988         Node       *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
02989         TargetEntry *te = tlist_member(groupexpr, sub_tlist);
02990 
02991         if (!te)
02992             elog(ERROR, "failed to locate grouping columns");
02993         groupColIdx[keyno++] = te->resno;
02994     }
02995 }
02996 
02997 /*
02998  * postprocess_setop_tlist
02999  *    Fix up targetlist returned by plan_set_operations().
03000  *
03001  * We need to transpose sort key info from the orig_tlist into new_tlist.
03002  * NOTE: this would not be good enough if we supported resjunk sort keys
03003  * for results of set operations --- then, we'd need to project a whole
03004  * new tlist to evaluate the resjunk columns.  For now, just ereport if we
03005  * find any resjunk columns in orig_tlist.
03006  */
03007 static List *
03008 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
03009 {
03010     ListCell   *l;
03011     ListCell   *orig_tlist_item = list_head(orig_tlist);
03012 
03013     foreach(l, new_tlist)
03014     {
03015         TargetEntry *new_tle = (TargetEntry *) lfirst(l);
03016         TargetEntry *orig_tle;
03017 
03018         /* ignore resjunk columns in setop result */
03019         if (new_tle->resjunk)
03020             continue;
03021 
03022         Assert(orig_tlist_item != NULL);
03023         orig_tle = (TargetEntry *) lfirst(orig_tlist_item);
03024         orig_tlist_item = lnext(orig_tlist_item);
03025         if (orig_tle->resjunk)  /* should not happen */
03026             elog(ERROR, "resjunk output columns are not implemented");
03027         Assert(new_tle->resno == orig_tle->resno);
03028         new_tle->ressortgroupref = orig_tle->ressortgroupref;
03029     }
03030     if (orig_tlist_item != NULL)
03031         elog(ERROR, "resjunk output columns are not implemented");
03032     return new_tlist;
03033 }
03034 
03035 /*
03036  * select_active_windows
03037  *      Create a list of the "active" window clauses (ie, those referenced
03038  *      by non-deleted WindowFuncs) in the order they are to be executed.
03039  */
03040 static List *
03041 select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
03042 {
03043     List       *result;
03044     List       *actives;
03045     ListCell   *lc;
03046 
03047     /* First, make a list of the active windows */
03048     actives = NIL;
03049     foreach(lc, root->parse->windowClause)
03050     {
03051         WindowClause *wc = (WindowClause *) lfirst(lc);
03052 
03053         /* It's only active if wflists shows some related WindowFuncs */
03054         Assert(wc->winref <= wflists->maxWinRef);
03055         if (wflists->windowFuncs[wc->winref] != NIL)
03056             actives = lappend(actives, wc);
03057     }
03058 
03059     /*
03060      * Now, ensure that windows with identical partitioning/ordering clauses
03061      * are adjacent in the list.  This is required by the SQL standard, which
03062      * says that only one sort is to be used for such windows, even if they
03063      * are otherwise distinct (eg, different names or framing clauses).
03064      *
03065      * There is room to be much smarter here, for example detecting whether
03066      * one window's sort keys are a prefix of another's (so that sorting for
03067      * the latter would do for the former), or putting windows first that
03068      * match a sort order available for the underlying query.  For the moment
03069      * we are content with meeting the spec.
03070      */
03071     result = NIL;
03072     while (actives != NIL)
03073     {
03074         WindowClause *wc = (WindowClause *) linitial(actives);
03075         ListCell   *prev;
03076         ListCell   *next;
03077 
03078         /* Move wc from actives to result */
03079         actives = list_delete_first(actives);
03080         result = lappend(result, wc);
03081 
03082         /* Now move any matching windows from actives to result */
03083         prev = NULL;
03084         for (lc = list_head(actives); lc; lc = next)
03085         {
03086             WindowClause *wc2 = (WindowClause *) lfirst(lc);
03087 
03088             next = lnext(lc);
03089             /* framing options are NOT to be compared here! */
03090             if (equal(wc->partitionClause, wc2->partitionClause) &&
03091                 equal(wc->orderClause, wc2->orderClause))
03092             {
03093                 actives = list_delete_cell(actives, lc, prev);
03094                 result = lappend(result, wc2);
03095             }
03096             else
03097                 prev = lc;
03098         }
03099     }
03100 
03101     return result;
03102 }
03103 
03104 /*
03105  * make_windowInputTargetList
03106  *    Generate appropriate target list for initial input to WindowAgg nodes.
03107  *
03108  * When grouping_planner inserts one or more WindowAgg nodes into the plan,
03109  * this function computes the initial target list to be computed by the node
03110  * just below the first WindowAgg.  This list must contain all values needed
03111  * to evaluate the window functions, compute the final target list, and
03112  * perform any required final sort step.  If multiple WindowAggs are needed,
03113  * each intermediate one adds its window function results onto this tlist;
03114  * only the topmost WindowAgg computes the actual desired target list.
03115  *
03116  * This function is much like make_subplanTargetList, though not quite enough
03117  * like it to share code.  As in that function, we flatten most expressions
03118  * into their component variables.  But we do not want to flatten window
03119  * PARTITION BY/ORDER BY clauses, since that might result in multiple
03120  * evaluations of them, which would be bad (possibly even resulting in
03121  * inconsistent answers, if they contain volatile functions).  Also, we must
03122  * not flatten GROUP BY clauses that were left unflattened by
03123  * make_subplanTargetList, because we may no longer have access to the
03124  * individual Vars in them.
03125  *
03126  * Another key difference from make_subplanTargetList is that we don't flatten
03127  * Aggref expressions, since those are to be computed below the window
03128  * functions and just referenced like Vars above that.
03129  *
03130  * 'tlist' is the query's final target list.
03131  * 'activeWindows' is the list of active windows previously identified by
03132  *          select_active_windows.
03133  *
03134  * The result is the targetlist to be computed by the plan node immediately
03135  * below the first WindowAgg node.
03136  */
03137 static List *
03138 make_windowInputTargetList(PlannerInfo *root,
03139                            List *tlist,
03140                            List *activeWindows)
03141 {
03142     Query      *parse = root->parse;
03143     Bitmapset  *sgrefs;
03144     List       *new_tlist;
03145     List       *flattenable_cols;
03146     List       *flattenable_vars;
03147     ListCell   *lc;
03148 
03149     Assert(parse->hasWindowFuncs);
03150 
03151     /*
03152      * Collect the sortgroupref numbers of window PARTITION/ORDER BY clauses
03153      * into a bitmapset for convenient reference below.
03154      */
03155     sgrefs = NULL;
03156     foreach(lc, activeWindows)
03157     {
03158         WindowClause *wc = (WindowClause *) lfirst(lc);
03159         ListCell   *lc2;
03160 
03161         foreach(lc2, wc->partitionClause)
03162         {
03163             SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
03164 
03165             sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
03166         }
03167         foreach(lc2, wc->orderClause)
03168         {
03169             SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
03170 
03171             sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
03172         }
03173     }
03174 
03175     /* Add in sortgroupref numbers of GROUP BY clauses, too */
03176     foreach(lc, parse->groupClause)
03177     {
03178         SortGroupClause *grpcl = (SortGroupClause *) lfirst(lc);
03179 
03180         sgrefs = bms_add_member(sgrefs, grpcl->tleSortGroupRef);
03181     }
03182 
03183     /*
03184      * Construct a tlist containing all the non-flattenable tlist items, and
03185      * save aside the others for a moment.
03186      */
03187     new_tlist = NIL;
03188     flattenable_cols = NIL;
03189 
03190     foreach(lc, tlist)
03191     {
03192         TargetEntry *tle = (TargetEntry *) lfirst(lc);
03193 
03194         /*
03195          * Don't want to deconstruct window clauses or GROUP BY items.  (Note
03196          * that such items can't contain window functions, so it's okay to
03197          * compute them below the WindowAgg nodes.)
03198          */
03199         if (tle->ressortgroupref != 0 &&
03200             bms_is_member(tle->ressortgroupref, sgrefs))
03201         {
03202             /* Don't want to deconstruct this value, so add to new_tlist */
03203             TargetEntry *newtle;
03204 
03205             newtle = makeTargetEntry(tle->expr,
03206                                      list_length(new_tlist) + 1,
03207                                      NULL,
03208                                      false);
03209             /* Preserve its sortgroupref marking, in case it's volatile */
03210             newtle->ressortgroupref = tle->ressortgroupref;
03211             new_tlist = lappend(new_tlist, newtle);
03212         }
03213         else
03214         {
03215             /*
03216              * Column is to be flattened, so just remember the expression for
03217              * later call to pull_var_clause.  There's no need for
03218              * pull_var_clause to examine the TargetEntry node itself.
03219              */
03220             flattenable_cols = lappend(flattenable_cols, tle->expr);
03221         }
03222     }
03223 
03224     /*
03225      * Pull out all the Vars and Aggrefs mentioned in flattenable columns, and
03226      * add them to the result tlist if not already present.  (Some might be
03227      * there already because they're used directly as window/group clauses.)
03228      *
03229      * Note: it's essential to use PVC_INCLUDE_AGGREGATES here, so that the
03230      * Aggrefs are placed in the Agg node's tlist and not left to be computed
03231      * at higher levels.
03232      */
03233     flattenable_vars = pull_var_clause((Node *) flattenable_cols,
03234                                        PVC_INCLUDE_AGGREGATES,
03235                                        PVC_INCLUDE_PLACEHOLDERS);
03236     new_tlist = add_to_flat_tlist(new_tlist, flattenable_vars);
03237 
03238     /* clean up cruft */
03239     list_free(flattenable_vars);
03240     list_free(flattenable_cols);
03241 
03242     return new_tlist;
03243 }
03244 
03245 /*
03246  * make_pathkeys_for_window
03247  *      Create a pathkeys list describing the required input ordering
03248  *      for the given WindowClause.
03249  *
03250  * The required ordering is first the PARTITION keys, then the ORDER keys.
03251  * In the future we might try to implement windowing using hashing, in which
03252  * case the ordering could be relaxed, but for now we always sort.
03253  */
03254 static List *
03255 make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
03256                          List *tlist)
03257 {
03258     List       *window_pathkeys;
03259     List       *window_sortclauses;
03260 
03261     /* Throw error if can't sort */
03262     if (!grouping_is_sortable(wc->partitionClause))
03263         ereport(ERROR,
03264                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
03265                  errmsg("could not implement window PARTITION BY"),
03266                  errdetail("Window partitioning columns must be of sortable datatypes.")));
03267     if (!grouping_is_sortable(wc->orderClause))
03268         ereport(ERROR,
03269                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
03270                  errmsg("could not implement window ORDER BY"),
03271         errdetail("Window ordering columns must be of sortable datatypes.")));
03272 
03273     /* Okay, make the combined pathkeys */
03274     window_sortclauses = list_concat(list_copy(wc->partitionClause),
03275                                      list_copy(wc->orderClause));
03276     window_pathkeys = make_pathkeys_for_sortclauses(root,
03277                                                     window_sortclauses,
03278                                                     tlist);
03279     list_free(window_sortclauses);
03280     return window_pathkeys;
03281 }
03282 
03283 /*----------
03284  * get_column_info_for_window
03285  *      Get the partitioning/ordering column numbers and equality operators
03286  *      for a WindowAgg node.
03287  *
03288  * This depends on the behavior of make_pathkeys_for_window()!
03289  *
03290  * We are given the target WindowClause and an array of the input column
03291  * numbers associated with the resulting pathkeys.  In the easy case, there
03292  * are the same number of pathkey columns as partitioning + ordering columns
03293  * and we just have to copy some data around.  However, it's possible that
03294  * some of the original partitioning + ordering columns were eliminated as
03295  * redundant during the transformation to pathkeys.  (This can happen even
03296  * though the parser gets rid of obvious duplicates.  A typical scenario is a
03297  * window specification "PARTITION BY x ORDER BY y" coupled with a clause
03298  * "WHERE x = y" that causes the two sort columns to be recognized as
03299  * redundant.)  In that unusual case, we have to work a lot harder to
03300  * determine which keys are significant.
03301  *
03302  * The method used here is a bit brute-force: add the sort columns to a list
03303  * one at a time and note when the resulting pathkey list gets longer.  But
03304  * it's a sufficiently uncommon case that a faster way doesn't seem worth
03305  * the amount of code refactoring that'd be needed.
03306  *----------
03307  */
03308 static void
03309 get_column_info_for_window(PlannerInfo *root, WindowClause *wc, List *tlist,
03310                            int numSortCols, AttrNumber *sortColIdx,
03311                            int *partNumCols,
03312                            AttrNumber **partColIdx,
03313                            Oid **partOperators,
03314                            int *ordNumCols,
03315                            AttrNumber **ordColIdx,
03316                            Oid **ordOperators)
03317 {
03318     int         numPart = list_length(wc->partitionClause);
03319     int         numOrder = list_length(wc->orderClause);
03320 
03321     if (numSortCols == numPart + numOrder)
03322     {
03323         /* easy case */
03324         *partNumCols = numPart;
03325         *partColIdx = sortColIdx;
03326         *partOperators = extract_grouping_ops(wc->partitionClause);
03327         *ordNumCols = numOrder;
03328         *ordColIdx = sortColIdx + numPart;
03329         *ordOperators = extract_grouping_ops(wc->orderClause);
03330     }
03331     else
03332     {
03333         List       *sortclauses;
03334         List       *pathkeys;
03335         int         scidx;
03336         ListCell   *lc;
03337 
03338         /* first, allocate what's certainly enough space for the arrays */
03339         *partNumCols = 0;
03340         *partColIdx = (AttrNumber *) palloc(numPart * sizeof(AttrNumber));
03341         *partOperators = (Oid *) palloc(numPart * sizeof(Oid));
03342         *ordNumCols = 0;
03343         *ordColIdx = (AttrNumber *) palloc(numOrder * sizeof(AttrNumber));
03344         *ordOperators = (Oid *) palloc(numOrder * sizeof(Oid));
03345         sortclauses = NIL;
03346         pathkeys = NIL;
03347         scidx = 0;
03348         foreach(lc, wc->partitionClause)
03349         {
03350             SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
03351             List       *new_pathkeys;
03352 
03353             sortclauses = lappend(sortclauses, sgc);
03354             new_pathkeys = make_pathkeys_for_sortclauses(root,
03355                                                          sortclauses,
03356                                                          tlist);
03357             if (list_length(new_pathkeys) > list_length(pathkeys))
03358             {
03359                 /* this sort clause is actually significant */
03360                 (*partColIdx)[*partNumCols] = sortColIdx[scidx++];
03361                 (*partOperators)[*partNumCols] = sgc->eqop;
03362                 (*partNumCols)++;
03363                 pathkeys = new_pathkeys;
03364             }
03365         }
03366         foreach(lc, wc->orderClause)
03367         {
03368             SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
03369             List       *new_pathkeys;
03370 
03371             sortclauses = lappend(sortclauses, sgc);
03372             new_pathkeys = make_pathkeys_for_sortclauses(root,
03373                                                          sortclauses,
03374                                                          tlist);
03375             if (list_length(new_pathkeys) > list_length(pathkeys))
03376             {
03377                 /* this sort clause is actually significant */
03378                 (*ordColIdx)[*ordNumCols] = sortColIdx[scidx++];
03379                 (*ordOperators)[*ordNumCols] = sgc->eqop;
03380                 (*ordNumCols)++;
03381                 pathkeys = new_pathkeys;
03382             }
03383         }
03384         /* complain if we didn't eat exactly the right number of sort cols */
03385         if (scidx != numSortCols)
03386             elog(ERROR, "failed to deconstruct sort operators into partitioning/ordering operators");
03387     }
03388 }
03389 
03390 
03391 /*
03392  * expression_planner
03393  *      Perform planner's transformations on a standalone expression.
03394  *
03395  * Various utility commands need to evaluate expressions that are not part
03396  * of a plannable query.  They can do so using the executor's regular
03397  * expression-execution machinery, but first the expression has to be fed
03398  * through here to transform it from parser output to something executable.
03399  *
03400  * Currently, we disallow sublinks in standalone expressions, so there's no
03401  * real "planning" involved here.  (That might not always be true though.)
03402  * What we must do is run eval_const_expressions to ensure that any function
03403  * calls are converted to positional notation and function default arguments
03404  * get inserted.  The fact that constant subexpressions get simplified is a
03405  * side-effect that is useful when the expression will get evaluated more than
03406  * once.  Also, we must fix operator function IDs.
03407  *
03408  * Note: this must not make any damaging changes to the passed-in expression
03409  * tree.  (It would actually be okay to apply fix_opfuncids to it, but since
03410  * we first do an expression_tree_mutator-based walk, what is returned will
03411  * be a new node tree.)
03412  */
03413 Expr *
03414 expression_planner(Expr *expr)
03415 {
03416     Node       *result;
03417 
03418     /*
03419      * Convert named-argument function calls, insert default arguments and
03420      * simplify constant subexprs
03421      */
03422     result = eval_const_expressions(NULL, (Node *) expr);
03423 
03424     /* Fill in opfuncid values if missing */
03425     fix_opfuncids(result);
03426 
03427     return (Expr *) result;
03428 }
03429 
03430 
03431 /*
03432  * plan_cluster_use_sort
03433  *      Use the planner to decide how CLUSTER should implement sorting
03434  *
03435  * tableOid is the OID of a table to be clustered on its index indexOid
03436  * (which is already known to be a btree index).  Decide whether it's
03437  * cheaper to do an indexscan or a seqscan-plus-sort to execute the CLUSTER.
03438  * Return TRUE to use sorting, FALSE to use an indexscan.
03439  *
03440  * Note: caller had better already hold some type of lock on the table.
03441  */
03442 bool
03443 plan_cluster_use_sort(Oid tableOid, Oid indexOid)
03444 {
03445     PlannerInfo *root;
03446     Query      *query;
03447     PlannerGlobal *glob;
03448     RangeTblEntry *rte;
03449     RelOptInfo *rel;
03450     IndexOptInfo *indexInfo;
03451     QualCost    indexExprCost;
03452     Cost        comparisonCost;
03453     Path       *seqScanPath;
03454     Path        seqScanAndSortPath;
03455     IndexPath  *indexScanPath;
03456     ListCell   *lc;
03457 
03458     /* Set up mostly-dummy planner state */
03459     query = makeNode(Query);
03460     query->commandType = CMD_SELECT;
03461 
03462     glob = makeNode(PlannerGlobal);
03463 
03464     root = makeNode(PlannerInfo);
03465     root->parse = query;
03466     root->glob = glob;
03467     root->query_level = 1;
03468     root->planner_cxt = CurrentMemoryContext;
03469     root->wt_param_id = -1;
03470 
03471     /* Build a minimal RTE for the rel */
03472     rte = makeNode(RangeTblEntry);
03473     rte->rtekind = RTE_RELATION;
03474     rte->relid = tableOid;
03475     rte->relkind = RELKIND_RELATION;  /* Don't be too picky. */
03476     rte->lateral = false;
03477     rte->inh = false;
03478     rte->inFromCl = true;
03479     query->rtable = list_make1(rte);
03480 
03481     /* Set up RTE/RelOptInfo arrays */
03482     setup_simple_rel_arrays(root);
03483 
03484     /* Build RelOptInfo */
03485     rel = build_simple_rel(root, 1, RELOPT_BASEREL);
03486 
03487     /* Locate IndexOptInfo for the target index */
03488     indexInfo = NULL;
03489     foreach(lc, rel->indexlist)
03490     {
03491         indexInfo = (IndexOptInfo *) lfirst(lc);
03492         if (indexInfo->indexoid == indexOid)
03493             break;
03494     }
03495 
03496     /*
03497      * It's possible that get_relation_info did not generate an IndexOptInfo
03498      * for the desired index; this could happen if it's not yet reached its
03499      * indcheckxmin usability horizon, or if it's a system index and we're
03500      * ignoring system indexes.  In such cases we should tell CLUSTER to not
03501      * trust the index contents but use seqscan-and-sort.
03502      */
03503     if (lc == NULL)             /* not in the list? */
03504         return true;            /* use sort */
03505 
03506     /*
03507      * Rather than doing all the pushups that would be needed to use
03508      * set_baserel_size_estimates, just do a quick hack for rows and width.
03509      */
03510     rel->rows = rel->tuples;
03511     rel->width = get_relation_data_width(tableOid, NULL);
03512 
03513     root->total_table_pages = rel->pages;
03514 
03515     /*
03516      * Determine eval cost of the index expressions, if any.  We need to
03517      * charge twice that amount for each tuple comparison that happens during
03518      * the sort, since tuplesort.c will have to re-evaluate the index
03519      * expressions each time.  (XXX that's pretty inefficient...)
03520      */
03521     cost_qual_eval(&indexExprCost, indexInfo->indexprs, root);
03522     comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple);
03523 
03524     /* Estimate the cost of seq scan + sort */
03525     seqScanPath = create_seqscan_path(root, rel, NULL);
03526     cost_sort(&seqScanAndSortPath, root, NIL,
03527               seqScanPath->total_cost, rel->tuples, rel->width,
03528               comparisonCost, maintenance_work_mem, -1.0);
03529 
03530     /* Estimate the cost of index scan */
03531     indexScanPath = create_index_path(root, indexInfo,
03532                                       NIL, NIL, NIL, NIL, NIL,
03533                                       ForwardScanDirection, false,
03534                                       NULL, 1.0);
03535 
03536     return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
03537 }