]> granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/planner.c
Revert incorrect memory-conservation hack in inheritance_planner().
[postgresql] / src / backend / optimizer / plan / planner.c
1 /*-------------------------------------------------------------------------
2  *
3  * planner.c
4  *        The query optimizer external interface.
5  *
6  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  *        src/backend/optimizer/plan/planner.c
12  *
13  *-------------------------------------------------------------------------
14  */
15
16 #include "postgres.h"
17
18 #include <limits.h>
19
20 #include "catalog/pg_operator.h"
21 #include "executor/executor.h"
22 #include "executor/nodeAgg.h"
23 #include "miscadmin.h"
24 #include "nodes/makefuncs.h"
25 #include "optimizer/clauses.h"
26 #include "optimizer/cost.h"
27 #include "optimizer/pathnode.h"
28 #include "optimizer/paths.h"
29 #include "optimizer/plancat.h"
30 #include "optimizer/planmain.h"
31 #include "optimizer/planner.h"
32 #include "optimizer/prep.h"
33 #include "optimizer/subselect.h"
34 #include "optimizer/tlist.h"
35 #include "optimizer/var.h"
36 #ifdef OPTIMIZER_DEBUG
37 #include "nodes/print.h"
38 #endif
39 #include "parser/analyze.h"
40 #include "parser/parse_expr.h"
41 #include "parser/parse_oper.h"
42 #include "parser/parsetree.h"
43 #include "utils/lsyscache.h"
44 #include "utils/syscache.h"
45
46
47 /* GUC parameter */
48 double          cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
49
50 /* Hook for plugins to get control in planner() */
51 planner_hook_type planner_hook = NULL;
52
53
54 /* Expression kind codes for preprocess_expression */
55 #define EXPRKIND_QUAL           0
56 #define EXPRKIND_TARGET         1
57 #define EXPRKIND_RTFUNC         2
58 #define EXPRKIND_VALUES         3
59 #define EXPRKIND_LIMIT          4
60 #define EXPRKIND_APPINFO        5
61
62
63 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
64 static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
65 static Plan *inheritance_planner(PlannerInfo *root);
66 static Plan *grouping_planner(PlannerInfo *root, double tuple_fraction);
67 static bool is_dummy_plan(Plan *plan);
68 static void preprocess_rowmarks(PlannerInfo *root);
69 static double preprocess_limit(PlannerInfo *root,
70                                  double tuple_fraction,
71                                  int64 *offset_est, int64 *count_est);
72 static void preprocess_groupclause(PlannerInfo *root);
73 static bool choose_hashed_grouping(PlannerInfo *root,
74                                            double tuple_fraction, double limit_tuples,
75                                            double path_rows, int path_width,
76                                            Path *cheapest_path, Path *sorted_path,
77                                            double dNumGroups, AggClauseCounts *agg_counts);
78 static bool choose_hashed_distinct(PlannerInfo *root,
79                                            double tuple_fraction, double limit_tuples,
80                                            double path_rows, int path_width,
81                                            Cost cheapest_startup_cost, Cost cheapest_total_cost,
82                                            Cost sorted_startup_cost, Cost sorted_total_cost,
83                                            List *sorted_pathkeys,
84                                            double dNumDistinctRows);
85 static List *make_subplanTargetList(PlannerInfo *root, List *tlist,
86                                            AttrNumber **groupColIdx, bool *need_tlist_eval);
87 static void locate_grouping_columns(PlannerInfo *root,
88                                                 List *tlist,
89                                                 List *sub_tlist,
90                                                 AttrNumber *groupColIdx);
91 static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
92 static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
93 static List *add_volatile_sort_exprs(List *window_tlist, List *tlist,
94                                                 List *activeWindows);
95 static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
96                                                  List *tlist, bool canonicalize);
97 static void get_column_info_for_window(PlannerInfo *root, WindowClause *wc,
98                                                    List *tlist,
99                                                    int numSortCols, AttrNumber *sortColIdx,
100                                                    int *partNumCols,
101                                                    AttrNumber **partColIdx,
102                                                    Oid **partOperators,
103                                                    int *ordNumCols,
104                                                    AttrNumber **ordColIdx,
105                                                    Oid **ordOperators);
106
107
108 /*****************************************************************************
109  *
110  *         Query optimizer entry point
111  *
112  * To support loadable plugins that monitor or modify planner behavior,
113  * we provide a hook variable that lets a plugin get control before and
114  * after the standard planning process.  The plugin would normally call
115  * standard_planner().
116  *
117  * Note to plugin authors: standard_planner() scribbles on its Query input,
118  * so you'd better copy that data structure if you want to plan more than once.
119  *
120  *****************************************************************************/
121 PlannedStmt *
122 planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
123 {
124         PlannedStmt *result;
125
126         if (planner_hook)
127                 result = (*planner_hook) (parse, cursorOptions, boundParams);
128         else
129                 result = standard_planner(parse, cursorOptions, boundParams);
130         return result;
131 }
132
133 PlannedStmt *
134 standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
135 {
136         PlannedStmt *result;
137         PlannerGlobal *glob;
138         double          tuple_fraction;
139         PlannerInfo *root;
140         Plan       *top_plan;
141         ListCell   *lp,
142                            *lrt,
143                            *lrm;
144
145         /* Cursor options may come from caller or from DECLARE CURSOR stmt */
146         if (parse->utilityStmt &&
147                 IsA(parse->utilityStmt, DeclareCursorStmt))
148                 cursorOptions |= ((DeclareCursorStmt *) parse->utilityStmt)->options;
149
150         /*
151          * Set up global state for this planner invocation.  This data is needed
152          * across all levels of sub-Query that might exist in the given command,
153          * so we keep it in a separate struct that's linked to by each per-Query
154          * PlannerInfo.
155          */
156         glob = makeNode(PlannerGlobal);
157
158         glob->boundParams = boundParams;
159         glob->paramlist = NIL;
160         glob->subplans = NIL;
161         glob->subrtables = NIL;
162         glob->subrowmarks = NIL;
163         glob->rewindPlanIDs = NULL;
164         glob->finalrtable = NIL;
165         glob->finalrowmarks = NIL;
166         glob->relationOids = NIL;
167         glob->invalItems = NIL;
168         glob->lastPHId = 0;
169         glob->transientPlan = false;
170
171         /* Determine what fraction of the plan is likely to be scanned */
172         if (cursorOptions & CURSOR_OPT_FAST_PLAN)
173         {
174                 /*
175                  * We have no real idea how many tuples the user will ultimately FETCH
176                  * from a cursor, but it is often the case that he doesn't want 'em
177                  * all, or would prefer a fast-start plan anyway so that he can
178                  * process some of the tuples sooner.  Use a GUC parameter to decide
179                  * what fraction to optimize for.
180                  */
181                 tuple_fraction = cursor_tuple_fraction;
182
183                 /*
184                  * We document cursor_tuple_fraction as simply being a fraction, which
185                  * means the edge cases 0 and 1 have to be treated specially here.      We
186                  * convert 1 to 0 ("all the tuples") and 0 to a very small fraction.
187                  */
188                 if (tuple_fraction >= 1.0)
189                         tuple_fraction = 0.0;
190                 else if (tuple_fraction <= 0.0)
191                         tuple_fraction = 1e-10;
192         }
193         else
194         {
195                 /* Default assumption is we need all the tuples */
196                 tuple_fraction = 0.0;
197         }
198
199         /* primary planning entry point (may recurse for subqueries) */
200         top_plan = subquery_planner(glob, parse, NULL,
201                                                                 false, tuple_fraction, &root);
202
203         /*
204          * If creating a plan for a scrollable cursor, make sure it can run
205          * backwards on demand.  Add a Material node at the top at need.
206          */
207         if (cursorOptions & CURSOR_OPT_SCROLL)
208         {
209                 if (!ExecSupportsBackwardScan(top_plan))
210                         top_plan = materialize_finished_plan(top_plan);
211         }
212
213         /* final cleanup of the plan */
214         Assert(glob->finalrtable == NIL);
215         Assert(glob->finalrowmarks == NIL);
216         top_plan = set_plan_references(glob, top_plan,
217                                                                    root->parse->rtable,
218                                                                    root->rowMarks);
219         /* ... and the subplans (both regular subplans and initplans) */
220         Assert(list_length(glob->subplans) == list_length(glob->subrtables));
221         Assert(list_length(glob->subplans) == list_length(glob->subrowmarks));
222         lrt = list_head(glob->subrtables);
223         lrm = list_head(glob->subrowmarks);
224         foreach(lp, glob->subplans)
225         {
226                 Plan       *subplan = (Plan *) lfirst(lp);
227                 List       *subrtable = (List *) lfirst(lrt);
228                 List       *subrowmark = (List *) lfirst(lrm);
229
230                 lfirst(lp) = set_plan_references(glob, subplan,
231                                                                                  subrtable, subrowmark);
232                 lrt = lnext(lrt);
233                 lrm = lnext(lrm);
234         }
235
236         /* build the PlannedStmt result */
237         result = makeNode(PlannedStmt);
238
239         result->commandType = parse->commandType;
240         result->hasReturning = (parse->returningList != NIL);
241         result->canSetTag = parse->canSetTag;
242         result->transientPlan = glob->transientPlan;
243         result->planTree = top_plan;
244         result->rtable = glob->finalrtable;
245         result->resultRelations = root->resultRelations;
246         result->utilityStmt = parse->utilityStmt;
247         result->intoClause = parse->intoClause;
248         result->subplans = glob->subplans;
249         result->rewindPlanIDs = glob->rewindPlanIDs;
250         result->rowMarks = glob->finalrowmarks;
251         result->relationOids = glob->relationOids;
252         result->invalItems = glob->invalItems;
253         result->nParamExec = list_length(glob->paramlist);
254
255         return result;
256 }
257
258
259 /*--------------------
260  * subquery_planner
261  *        Invokes the planner on a subquery.  We recurse to here for each
262  *        sub-SELECT found in the query tree.
263  *
264  * glob is the global state for the current planner run.
265  * parse is the querytree produced by the parser & rewriter.
266  * parent_root is the immediate parent Query's info (NULL at the top level).
267  * hasRecursion is true if this is a recursive WITH query.
268  * tuple_fraction is the fraction of tuples we expect will be retrieved.
269  * tuple_fraction is interpreted as explained for grouping_planner, below.
270  *
271  * If subroot isn't NULL, we pass back the query's final PlannerInfo struct;
272  * among other things this tells the output sort ordering of the plan.
273  *
274  * Basically, this routine does the stuff that should only be done once
275  * per Query object.  It then calls grouping_planner.  At one time,
276  * grouping_planner could be invoked recursively on the same Query object;
277  * that's not currently true, but we keep the separation between the two
278  * routines anyway, in case we need it again someday.
279  *
280  * subquery_planner will be called recursively to handle sub-Query nodes
281  * found within the query's expressions and rangetable.
282  *
283  * Returns a query plan.
284  *--------------------
285  */
286 Plan *
287 subquery_planner(PlannerGlobal *glob, Query *parse,
288                                  PlannerInfo *parent_root,
289                                  bool hasRecursion, double tuple_fraction,
290                                  PlannerInfo **subroot)
291 {
292         int                     num_old_subplans = list_length(glob->subplans);
293         PlannerInfo *root;
294         Plan       *plan;
295         List       *newHaving;
296         bool            hasOuterJoins;
297         ListCell   *l;
298
299         /* Create a PlannerInfo data structure for this subquery */
300         root = makeNode(PlannerInfo);
301         root->parse = parse;
302         root->glob = glob;
303         root->query_level = parent_root ? parent_root->query_level + 1 : 1;
304         root->parent_root = parent_root;
305         root->planner_cxt = CurrentMemoryContext;
306         root->init_plans = NIL;
307         root->cte_plan_ids = NIL;
308         root->eq_classes = NIL;
309         root->append_rel_list = NIL;
310         root->rowMarks = NIL;
311         root->hasInheritedTarget = false;
312
313         root->hasRecursion = hasRecursion;
314         if (hasRecursion)
315                 root->wt_param_id = SS_assign_special_param(root);
316         else
317                 root->wt_param_id = -1;
318         root->non_recursive_plan = NULL;
319
320         /*
321          * If there is a WITH list, process each WITH query and build an initplan
322          * SubPlan structure for it.
323          */
324         if (parse->cteList)
325                 SS_process_ctes(root);
326
327         /*
328          * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
329          * to transform them into joins.  Note that this step does not descend
330          * into subqueries; if we pull up any subqueries below, their SubLinks are
331          * processed just before pulling them up.
332          */
333         if (parse->hasSubLinks)
334                 pull_up_sublinks(root);
335
336         /*
337          * Scan the rangetable for set-returning functions, and inline them if
338          * possible (producing subqueries that might get pulled up next).
339          * Recursion issues here are handled in the same way as for SubLinks.
340          */
341         inline_set_returning_functions(root);
342
343         /*
344          * Check to see if any subqueries in the jointree can be merged into
345          * this query.
346          */
347         parse->jointree = (FromExpr *)
348                 pull_up_subqueries(root, (Node *) parse->jointree, NULL, NULL);
349
350         /*
351          * If this is a simple UNION ALL query, flatten it into an appendrel.
352          * We do this now because it requires applying pull_up_subqueries to the
353          * leaf queries of the UNION ALL, which weren't touched above because they
354          * weren't referenced by the jointree (they will be after we do this).
355          */
356         if (parse->setOperations)
357                 flatten_simple_union_all(root);
358
359         /*
360          * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
361          * avoid the expense of doing flatten_join_alias_vars().  Also check for
362          * outer joins --- if none, we can skip reduce_outer_joins(). This must be
363          * done after we have done pull_up_subqueries, of course.
364          */
365         root->hasJoinRTEs = false;
366         hasOuterJoins = false;
367         foreach(l, parse->rtable)
368         {
369                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
370
371                 if (rte->rtekind == RTE_JOIN)
372                 {
373                         root->hasJoinRTEs = true;
374                         if (IS_OUTER_JOIN(rte->jointype))
375                         {
376                                 hasOuterJoins = true;
377                                 /* Can quit scanning once we find an outer join */
378                                 break;
379                         }
380                 }
381         }
382
383         /*
384          * Preprocess RowMark information.      We need to do this after subquery
385          * pullup (so that all non-inherited RTEs are present) and before
386          * inheritance expansion (so that the info is available for
387          * expand_inherited_tables to examine and modify).
388          */
389         preprocess_rowmarks(root);
390
391         /*
392          * Expand any rangetable entries that are inheritance sets into "append
393          * relations".  This can add entries to the rangetable, but they must be
394          * plain base relations not joins, so it's OK (and marginally more
395          * efficient) to do it after checking for join RTEs.  We must do it after
396          * pulling up subqueries, else we'd fail to handle inherited tables in
397          * subqueries.
398          */
399         expand_inherited_tables(root);
400
401         /*
402          * Set hasHavingQual to remember if HAVING clause is present.  Needed
403          * because preprocess_expression will reduce a constant-true condition to
404          * an empty qual list ... but "HAVING TRUE" is not a semantic no-op.
405          */
406         root->hasHavingQual = (parse->havingQual != NULL);
407
408         /* Clear this flag; might get set in distribute_qual_to_rels */
409         root->hasPseudoConstantQuals = false;
410
411         /*
412          * Do expression preprocessing on targetlist and quals, as well as other
413          * random expressions in the querytree.  Note that we do not need to
414          * handle sort/group expressions explicitly, because they are actually
415          * part of the targetlist.
416          */
417         parse->targetList = (List *)
418                 preprocess_expression(root, (Node *) parse->targetList,
419                                                           EXPRKIND_TARGET);
420
421         parse->returningList = (List *)
422                 preprocess_expression(root, (Node *) parse->returningList,
423                                                           EXPRKIND_TARGET);
424
425         preprocess_qual_conditions(root, (Node *) parse->jointree);
426
427         parse->havingQual = preprocess_expression(root, parse->havingQual,
428                                                                                           EXPRKIND_QUAL);
429
430         foreach(l, parse->windowClause)
431         {
432                 WindowClause *wc = (WindowClause *) lfirst(l);
433
434                 /* partitionClause/orderClause are sort/group expressions */
435                 wc->startOffset = preprocess_expression(root, wc->startOffset,
436                                                                                                 EXPRKIND_LIMIT);
437                 wc->endOffset = preprocess_expression(root, wc->endOffset,
438                                                                                           EXPRKIND_LIMIT);
439         }
440
441         parse->limitOffset = preprocess_expression(root, parse->limitOffset,
442                                                                                            EXPRKIND_LIMIT);
443         parse->limitCount = preprocess_expression(root, parse->limitCount,
444                                                                                           EXPRKIND_LIMIT);
445
446         root->append_rel_list = (List *)
447                 preprocess_expression(root, (Node *) root->append_rel_list,
448                                                           EXPRKIND_APPINFO);
449
450         /* Also need to preprocess expressions for function and values RTEs */
451         foreach(l, parse->rtable)
452         {
453                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
454
455                 if (rte->rtekind == RTE_FUNCTION)
456                         rte->funcexpr = preprocess_expression(root, rte->funcexpr,
457                                                                                                   EXPRKIND_RTFUNC);
458                 else if (rte->rtekind == RTE_VALUES)
459                         rte->values_lists = (List *)
460                                 preprocess_expression(root, (Node *) rte->values_lists,
461                                                                           EXPRKIND_VALUES);
462         }
463
464         /*
465          * In some cases we may want to transfer a HAVING clause into WHERE. We
466          * cannot do so if the HAVING clause contains aggregates (obviously) or
467          * volatile functions (since a HAVING clause is supposed to be executed
468          * only once per group).  Also, it may be that the clause is so expensive
469          * to execute that we're better off doing it only once per group, despite
470          * the loss of selectivity.  This is hard to estimate short of doing the
471          * entire planning process twice, so we use a heuristic: clauses
472          * containing subplans are left in HAVING.      Otherwise, we move or copy the
473          * HAVING clause into WHERE, in hopes of eliminating tuples before
474          * aggregation instead of after.
475          *
476          * If the query has explicit grouping then we can simply move such a
477          * clause into WHERE; any group that fails the clause will not be in the
478          * output because none of its tuples will reach the grouping or
479          * aggregation stage.  Otherwise we must have a degenerate (variable-free)
480          * HAVING clause, which we put in WHERE so that query_planner() can use it
481          * in a gating Result node, but also keep in HAVING to ensure that we
482          * don't emit a bogus aggregated row. (This could be done better, but it
483          * seems not worth optimizing.)
484          *
485          * Note that both havingQual and parse->jointree->quals are in
486          * implicitly-ANDed-list form at this point, even though they are declared
487          * as Node *.
488          */
489         newHaving = NIL;
490         foreach(l, (List *) parse->havingQual)
491         {
492                 Node       *havingclause = (Node *) lfirst(l);
493
494                 if (contain_agg_clause(havingclause) ||
495                         contain_volatile_functions(havingclause) ||
496                         contain_subplans(havingclause))
497                 {
498                         /* keep it in HAVING */
499                         newHaving = lappend(newHaving, havingclause);
500                 }
501                 else if (parse->groupClause)
502                 {
503                         /* move it to WHERE */
504                         parse->jointree->quals = (Node *)
505                                 lappend((List *) parse->jointree->quals, havingclause);
506                 }
507                 else
508                 {
509                         /* put a copy in WHERE, keep it in HAVING */
510                         parse->jointree->quals = (Node *)
511                                 lappend((List *) parse->jointree->quals,
512                                                 copyObject(havingclause));
513                         newHaving = lappend(newHaving, havingclause);
514                 }
515         }
516         parse->havingQual = (Node *) newHaving;
517
518         /*
519          * If we have any outer joins, try to reduce them to plain inner joins.
520          * This step is most easily done after we've done expression
521          * preprocessing.
522          */
523         if (hasOuterJoins)
524                 reduce_outer_joins(root);
525
526         /*
527          * Do the main planning.  If we have an inherited target relation, that
528          * needs special processing, else go straight to grouping_planner.
529          */
530         if (parse->resultRelation &&
531                 rt_fetch(parse->resultRelation, parse->rtable)->inh)
532                 plan = inheritance_planner(root);
533         else
534         {
535                 plan = grouping_planner(root, tuple_fraction);
536                 /* If it's not SELECT, we need a ModifyTable node */
537                 if (parse->commandType != CMD_SELECT)
538                 {
539                         List       *returningLists;
540                         List       *rowMarks;
541
542                         /*
543                          * Deal with the RETURNING clause if any.  It's convenient to pass
544                          * the returningList through setrefs.c now rather than at top
545                          * level (if we waited, handling inherited UPDATE/DELETE would be
546                          * much harder).
547                          */
548                         if (parse->returningList)
549                         {
550                                 List       *rlist;
551
552                                 Assert(parse->resultRelation);
553                                 rlist = set_returning_clause_references(root->glob,
554                                                                                                                 parse->returningList,
555                                                                                                                 plan,
556                                                                                                           parse->resultRelation);
557                                 returningLists = list_make1(rlist);
558                         }
559                         else
560                                 returningLists = NIL;
561
562                         /*
563                          * If there was a FOR UPDATE/SHARE clause, the LockRows node will
564                          * have dealt with fetching non-locked marked rows, else we need
565                          * to have ModifyTable do that.
566                          */
567                         if (parse->rowMarks)
568                                 rowMarks = NIL;
569                         else
570                                 rowMarks = root->rowMarks;
571
572                         plan = (Plan *) make_modifytable(parse->commandType,
573                                                                                    copyObject(root->resultRelations),
574                                                                                          list_make1(plan),
575                                                                                          returningLists,
576                                                                                          rowMarks,
577                                                                                          SS_assign_special_param(root));
578                 }
579         }
580
581         /*
582          * If any subplans were generated, or if there are any parameters to worry
583          * about, build initPlan list and extParam/allParam sets for plan nodes,
584          * and attach the initPlans to the top plan node.
585          */
586         if (list_length(glob->subplans) != num_old_subplans ||
587                 root->glob->paramlist != NIL)
588                 SS_finalize_plan(root, plan, true);
589
590         /* Return internal info if caller wants it */
591         if (subroot)
592                 *subroot = root;
593
594         return plan;
595 }
596
597 /*
598  * preprocess_expression
599  *              Do subquery_planner's preprocessing work for an expression,
600  *              which can be a targetlist, a WHERE clause (including JOIN/ON
601  *              conditions), or a HAVING clause.
602  */
603 static Node *
604 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
605 {
606         /*
607          * Fall out quickly if expression is empty.  This occurs often enough to
608          * be worth checking.  Note that null->null is the correct conversion for
609          * implicit-AND result format, too.
610          */
611         if (expr == NULL)
612                 return NULL;
613
614         /*
615          * If the query has any join RTEs, replace join alias variables with
616          * base-relation variables. We must do this before sublink processing,
617          * else sublinks expanded out from join aliases wouldn't get processed. We
618          * can skip it in VALUES lists, however, since they can't contain any Vars
619          * at all.
620          */
621         if (root->hasJoinRTEs && kind != EXPRKIND_VALUES)
622                 expr = flatten_join_alias_vars(root, expr);
623
624         /*
625          * Simplify constant expressions.
626          *
627          * Note: an essential effect of this is to convert named-argument function
628          * calls to positional notation and insert the current actual values of
629          * any default arguments for functions.  To ensure that happens, we *must*
630          * process all expressions here.  Previous PG versions sometimes skipped
631          * const-simplification if it didn't seem worth the trouble, but we can't
632          * do that anymore.
633          *
634          * Note: this also flattens nested AND and OR expressions into N-argument
635          * form.  All processing of a qual expression after this point must be
636          * careful to maintain AND/OR flatness --- that is, do not generate a tree
637          * with AND directly under AND, nor OR directly under OR.
638          */
639         expr = eval_const_expressions(root, expr);
640
641         /*
642          * If it's a qual or havingQual, canonicalize it.
643          */
644         if (kind == EXPRKIND_QUAL)
645         {
646                 expr = (Node *) canonicalize_qual((Expr *) expr);
647
648 #ifdef OPTIMIZER_DEBUG
649                 printf("After canonicalize_qual()\n");
650                 pprint(expr);
651 #endif
652         }
653
654         /* Expand SubLinks to SubPlans */
655         if (root->parse->hasSubLinks)
656                 expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));
657
658         /*
659          * XXX do not insert anything here unless you have grokked the comments in
660          * SS_replace_correlation_vars ...
661          */
662
663         /* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
664         if (root->query_level > 1)
665                 expr = SS_replace_correlation_vars(root, expr);
666
667         /*
668          * If it's a qual or havingQual, convert it to implicit-AND format. (We
669          * don't want to do this before eval_const_expressions, since the latter
670          * would be unable to simplify a top-level AND correctly. Also,
671          * SS_process_sublinks expects explicit-AND format.)
672          */
673         if (kind == EXPRKIND_QUAL)
674                 expr = (Node *) make_ands_implicit((Expr *) expr);
675
676         return expr;
677 }
678
679 /*
680  * preprocess_qual_conditions
681  *              Recursively scan the query's jointree and do subquery_planner's
682  *              preprocessing work on each qual condition found therein.
683  */
684 static void
685 preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
686 {
687         if (jtnode == NULL)
688                 return;
689         if (IsA(jtnode, RangeTblRef))
690         {
691                 /* nothing to do here */
692         }
693         else if (IsA(jtnode, FromExpr))
694         {
695                 FromExpr   *f = (FromExpr *) jtnode;
696                 ListCell   *l;
697
698                 foreach(l, f->fromlist)
699                         preprocess_qual_conditions(root, lfirst(l));
700
701                 f->quals = preprocess_expression(root, f->quals, EXPRKIND_QUAL);
702         }
703         else if (IsA(jtnode, JoinExpr))
704         {
705                 JoinExpr   *j = (JoinExpr *) jtnode;
706
707                 preprocess_qual_conditions(root, j->larg);
708                 preprocess_qual_conditions(root, j->rarg);
709
710                 j->quals = preprocess_expression(root, j->quals, EXPRKIND_QUAL);
711         }
712         else
713                 elog(ERROR, "unrecognized node type: %d",
714                          (int) nodeTag(jtnode));
715 }
716
717 /*
718  * inheritance_planner
719  *        Generate a plan in the case where the result relation is an
720  *        inheritance set.
721  *
722  * We have to handle this case differently from cases where a source relation
723  * is an inheritance set. Source inheritance is expanded at the bottom of the
724  * plan tree (see allpaths.c), but target inheritance has to be expanded at
725  * the top.  The reason is that for UPDATE, each target relation needs a
726  * different targetlist matching its own column set.  Fortunately,
727  * the UPDATE/DELETE target can never be the nullable side of an outer join,
728  * so it's OK to generate the plan this way.
729  *
730  * Returns a query plan.
731  */
732 static Plan *
733 inheritance_planner(PlannerInfo *root)
734 {
735         Query      *parse = root->parse;
736         int                     parentRTindex = parse->resultRelation;
737         List       *subplans = NIL;
738         List       *resultRelations = NIL;
739         List       *returningLists = NIL;
740         List       *rtable = NIL;
741         List       *rowMarks;
742         List       *tlist;
743         PlannerInfo subroot;
744         ListCell   *l;
745
746         foreach(l, root->append_rel_list)
747         {
748                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
749                 Plan       *subplan;
750
751                 /* append_rel_list contains all append rels; ignore others */
752                 if (appinfo->parent_relid != parentRTindex)
753                         continue;
754
755                 /*
756                  * Generate modified query with this rel as target.
757                  */
758                 memcpy(&subroot, root, sizeof(PlannerInfo));
759                 subroot.parse = (Query *)
760                         adjust_appendrel_attrs((Node *) parse,
761                                                                    appinfo);
762                 subroot.init_plans = NIL;
763                 subroot.hasInheritedTarget = true;
764                 /* We needn't modify the child's append_rel_list */
765                 /* There shouldn't be any OJ info to translate, as yet */
766                 Assert(subroot.join_info_list == NIL);
767                 /* and we haven't created PlaceHolderInfos, either */
768                 Assert(subroot.placeholder_list == NIL);
769
770                 /* Generate plan */
771                 subplan = grouping_planner(&subroot, 0.0 /* retrieve all tuples */ );
772
773                 /*
774                  * If this child rel was excluded by constraint exclusion, exclude it
775                  * from the plan.
776                  */
777                 if (is_dummy_plan(subplan))
778                         continue;
779
780                 /* Save rtable from first rel for use below */
781                 if (subplans == NIL)
782                         rtable = subroot.parse->rtable;
783
784                 subplans = lappend(subplans, subplan);
785
786                 /* Make sure any initplans from this rel get into the outer list */
787                 root->init_plans = list_concat(root->init_plans, subroot.init_plans);
788
789                 /* Build target-relations list for the executor */
790                 resultRelations = lappend_int(resultRelations, appinfo->child_relid);
791
792                 /* Build list of per-relation RETURNING targetlists */
793                 if (parse->returningList)
794                 {
795                         List       *rlist;
796
797                         rlist = set_returning_clause_references(root->glob,
798                                                                                                 subroot.parse->returningList,
799                                                                                                         subplan,
800                                                                                                         appinfo->child_relid);
801                         returningLists = lappend(returningLists, rlist);
802                 }
803         }
804
805         root->resultRelations = resultRelations;
806
807         /* Mark result as unordered (probably unnecessary) */
808         root->query_pathkeys = NIL;
809
810         /*
811          * If we managed to exclude every child rel, return a dummy plan; it
812          * doesn't even need a ModifyTable node.
813          */
814         if (subplans == NIL)
815         {
816                 root->resultRelations = list_make1_int(parentRTindex);
817                 /* although dummy, it must have a valid tlist for executor */
818                 tlist = preprocess_targetlist(root, parse->targetList);
819                 return (Plan *) make_result(root,
820                                                                         tlist,
821                                                                         (Node *) list_make1(makeBoolConst(false,
822                                                                                                                                           false)),
823                                                                         NULL);
824         }
825
826         /*
827          * Planning might have modified the rangetable, due to changes of the
828          * Query structures inside subquery RTEs.  We have to ensure that this
829          * gets propagated back to the master copy.  But can't do this until we
830          * are done planning, because all the calls to grouping_planner need
831          * virgin sub-Queries to work from.  (We are effectively assuming that
832          * sub-Queries will get planned identically each time, or at least that
833          * the impacts on their rangetables will be the same each time.)
834          *
835          * XXX should clean this up someday
836          */
837         parse->rtable = rtable;
838
839         /*
840          * If there was a FOR UPDATE/SHARE clause, the LockRows node will have
841          * dealt with fetching non-locked marked rows, else we need to have
842          * ModifyTable do that.
843          */
844         if (parse->rowMarks)
845                 rowMarks = NIL;
846         else
847                 rowMarks = root->rowMarks;
848
849         /* And last, tack on a ModifyTable node to do the UPDATE/DELETE work */
850         return (Plan *) make_modifytable(parse->commandType,
851                                                                          copyObject(root->resultRelations),
852                                                                          subplans,
853                                                                          returningLists,
854                                                                          rowMarks,
855                                                                          SS_assign_special_param(root));
856 }
857
858 /*--------------------
859  * grouping_planner
860  *        Perform planning steps related to grouping, aggregation, etc.
861  *        This primarily means adding top-level processing to the basic
862  *        query plan produced by query_planner.
863  *
864  * tuple_fraction is the fraction of tuples we expect will be retrieved
865  *
866  * tuple_fraction is interpreted as follows:
867  *        0: expect all tuples to be retrieved (normal case)
868  *        0 < tuple_fraction < 1: expect the given fraction of tuples available
869  *              from the plan to be retrieved
870  *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
871  *              expected to be retrieved (ie, a LIMIT specification)
872  *
873  * Returns a query plan.  Also, root->query_pathkeys is returned as the
874  * actual output ordering of the plan (in pathkey format).
875  *--------------------
876  */
877 static Plan *
878 grouping_planner(PlannerInfo *root, double tuple_fraction)
879 {
880         Query      *parse = root->parse;
881         List       *tlist = parse->targetList;
882         int64           offset_est = 0;
883         int64           count_est = 0;
884         double          limit_tuples = -1.0;
885         Plan       *result_plan;
886         List       *current_pathkeys;
887         double          dNumGroups = 0;
888         bool            use_hashed_distinct = false;
889         bool            tested_hashed_distinct = false;
890
891         /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
892         if (parse->limitCount || parse->limitOffset)
893         {
894                 tuple_fraction = preprocess_limit(root, tuple_fraction,
895                                                                                   &offset_est, &count_est);
896
897                 /*
898                  * If we have a known LIMIT, and don't have an unknown OFFSET, we can
899                  * estimate the effects of using a bounded sort.
900                  */
901                 if (count_est > 0 && offset_est >= 0)
902                         limit_tuples = (double) count_est + (double) offset_est;
903         }
904
905         if (parse->setOperations)
906         {
907                 List       *set_sortclauses;
908
909                 /*
910                  * If there's a top-level ORDER BY, assume we have to fetch all the
911                  * tuples.      This might be too simplistic given all the hackery below
912                  * to possibly avoid the sort; but the odds of accurate estimates here
913                  * are pretty low anyway.
914                  */
915                 if (parse->sortClause)
916                         tuple_fraction = 0.0;
917
918                 /*
919                  * Construct the plan for set operations.  The result will not need
920                  * any work except perhaps a top-level sort and/or LIMIT.  Note that
921                  * any special work for recursive unions is the responsibility of
922                  * plan_set_operations.
923                  */
924                 result_plan = plan_set_operations(root, tuple_fraction,
925                                                                                   &set_sortclauses);
926
927                 /*
928                  * Calculate pathkeys representing the sort order (if any) of the set
929                  * operation's result.  We have to do this before overwriting the sort
930                  * key information...
931                  */
932                 current_pathkeys = make_pathkeys_for_sortclauses(root,
933                                                                                                                  set_sortclauses,
934                                                                                                          result_plan->targetlist,
935                                                                                                                  true);
936
937                 /*
938                  * We should not need to call preprocess_targetlist, since we must be
939                  * in a SELECT query node.      Instead, use the targetlist returned by
940                  * plan_set_operations (since this tells whether it returned any
941                  * resjunk columns!), and transfer any sort key information from the
942                  * original tlist.
943                  */
944                 Assert(parse->commandType == CMD_SELECT);
945
946                 tlist = postprocess_setop_tlist(copyObject(result_plan->targetlist),
947                                                                                 tlist);
948
949                 /*
950                  * Can't handle FOR UPDATE/SHARE here (parser should have checked
951                  * already, but let's make sure).
952                  */
953                 if (parse->rowMarks)
954                         ereport(ERROR,
955                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
956                                          errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT")));
957
958                 /*
959                  * Calculate pathkeys that represent result ordering requirements
960                  */
961                 Assert(parse->distinctClause == NIL);
962                 root->sort_pathkeys = make_pathkeys_for_sortclauses(root,
963                                                                                                                         parse->sortClause,
964                                                                                                                         tlist,
965                                                                                                                         true);
966         }
967         else
968         {
969                 /* No set operations, do regular planning */
970                 List       *sub_tlist;
971                 double          sub_limit_tuples;
972                 AttrNumber *groupColIdx = NULL;
973                 bool            need_tlist_eval = true;
974                 QualCost        tlist_cost;
975                 Path       *cheapest_path;
976                 Path       *sorted_path;
977                 Path       *best_path;
978                 long            numGroups = 0;
979                 AggClauseCounts agg_counts;
980                 int                     numGroupCols;
981                 double          path_rows;
982                 int                     path_width;
983                 bool            use_hashed_grouping = false;
984                 WindowFuncLists *wflists = NULL;
985                 List       *activeWindows = NIL;
986
987                 MemSet(&agg_counts, 0, sizeof(AggClauseCounts));
988
989                 /* A recursive query should always have setOperations */
990                 Assert(!root->hasRecursion);
991
992                 /* Preprocess GROUP BY clause, if any */
993                 if (parse->groupClause)
994                         preprocess_groupclause(root);
995                 numGroupCols = list_length(parse->groupClause);
996
997                 /* Preprocess targetlist */
998                 tlist = preprocess_targetlist(root, tlist);
999
1000                 /*
1001                  * Locate any window functions in the tlist.  (We don't need to look
1002                  * anywhere else, since expressions used in ORDER BY will be in there
1003                  * too.)  Note that they could all have been eliminated by constant
1004                  * folding, in which case we don't need to do any more work.
1005                  */
1006                 if (parse->hasWindowFuncs)
1007                 {
1008                         wflists = find_window_functions((Node *) tlist,
1009                                                                                         list_length(parse->windowClause));
1010                         if (wflists->numWindowFuncs > 0)
1011                                 activeWindows = select_active_windows(root, wflists);
1012                         else
1013                                 parse->hasWindowFuncs = false;
1014                 }
1015
1016                 /*
1017                  * Generate appropriate target list for subplan; may be different from
1018                  * tlist if grouping or aggregation is needed.
1019                  */
1020                 sub_tlist = make_subplanTargetList(root, tlist,
1021                                                                                    &groupColIdx, &need_tlist_eval);
1022
1023                 /*
1024                  * Do aggregate preprocessing, if the query has any aggs.
1025                  *
1026                  * Note: think not that we can turn off hasAggs if we find no aggs. It
1027                  * is possible for constant-expression simplification to remove all
1028                  * explicit references to aggs, but we still have to follow the
1029                  * aggregate semantics (eg, producing only one output row).
1030                  */
1031                 if (parse->hasAggs)
1032                 {
1033                         /*
1034                          * Will need actual number of aggregates for estimating costs.
1035                          * Note: we do not attempt to detect duplicate aggregates here; a
1036                          * somewhat-overestimated count is okay for our present purposes.
1037                          */
1038                         count_agg_clauses((Node *) tlist, &agg_counts);
1039                         count_agg_clauses(parse->havingQual, &agg_counts);
1040
1041                         /*
1042                          * Preprocess MIN/MAX aggregates, if any.
1043                          */
1044                         preprocess_minmax_aggregates(root, tlist);
1045                 }
1046
1047                 /*
1048                  * Calculate pathkeys that represent grouping/ordering requirements.
1049                  * Stash them in PlannerInfo so that query_planner can canonicalize
1050                  * them after EquivalenceClasses have been formed.      The sortClause is
1051                  * certainly sort-able, but GROUP BY and DISTINCT might not be, in
1052                  * which case we just leave their pathkeys empty.
1053                  */
1054                 if (parse->groupClause &&
1055                         grouping_is_sortable(parse->groupClause))
1056                         root->group_pathkeys =
1057                                 make_pathkeys_for_sortclauses(root,
1058                                                                                           parse->groupClause,
1059                                                                                           tlist,
1060                                                                                           false);
1061                 else
1062                         root->group_pathkeys = NIL;
1063
1064                 /* We consider only the first (bottom) window in pathkeys logic */
1065                 if (activeWindows != NIL)
1066                 {
1067                         WindowClause *wc = (WindowClause *) linitial(activeWindows);
1068
1069                         root->window_pathkeys = make_pathkeys_for_window(root,
1070                                                                                                                          wc,
1071                                                                                                                          tlist,
1072                                                                                                                          false);
1073                 }
1074                 else
1075                         root->window_pathkeys = NIL;
1076
1077                 if (parse->distinctClause &&
1078                         grouping_is_sortable(parse->distinctClause))
1079                         root->distinct_pathkeys =
1080                                 make_pathkeys_for_sortclauses(root,
1081                                                                                           parse->distinctClause,
1082                                                                                           tlist,
1083                                                                                           false);
1084                 else
1085                         root->distinct_pathkeys = NIL;
1086
1087                 root->sort_pathkeys =
1088                         make_pathkeys_for_sortclauses(root,
1089                                                                                   parse->sortClause,
1090                                                                                   tlist,
1091                                                                                   false);
1092
1093                 /*
1094                  * Figure out whether we want a sorted result from query_planner.
1095                  *
1096                  * If we have a sortable GROUP BY clause, then we want a result sorted
1097                  * properly for grouping.  Otherwise, if we have window functions to
1098                  * evaluate, we try to sort for the first window.  Otherwise, if
1099                  * there's a sortable DISTINCT clause that's more rigorous than the
1100                  * ORDER BY clause, we try to produce output that's sufficiently well
1101                  * sorted for the DISTINCT.  Otherwise, if there is an ORDER BY
1102                  * clause, we want to sort by the ORDER BY clause.
1103                  *
1104                  * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a
1105                  * superset of GROUP BY, it would be tempting to request sort by ORDER
1106                  * BY --- but that might just leave us failing to exploit an available
1107                  * sort order at all.  Needs more thought.      The choice for DISTINCT
1108                  * versus ORDER BY is much easier, since we know that the parser
1109                  * ensured that one is a superset of the other.
1110                  */
1111                 if (root->group_pathkeys)
1112                         root->query_pathkeys = root->group_pathkeys;
1113                 else if (root->window_pathkeys)
1114                         root->query_pathkeys = root->window_pathkeys;
1115                 else if (list_length(root->distinct_pathkeys) >
1116                                  list_length(root->sort_pathkeys))
1117                         root->query_pathkeys = root->distinct_pathkeys;
1118                 else if (root->sort_pathkeys)
1119                         root->query_pathkeys = root->sort_pathkeys;
1120                 else
1121                         root->query_pathkeys = NIL;
1122
1123                 /*
1124                  * Figure out whether there's a hard limit on the number of rows that
1125                  * query_planner's result subplan needs to return.  Even if we know a
1126                  * hard limit overall, it doesn't apply if the query has any
1127                  * grouping/aggregation operations.
1128                  */
1129                 if (parse->groupClause ||
1130                         parse->distinctClause ||
1131                         parse->hasAggs ||
1132                         parse->hasWindowFuncs ||
1133                         root->hasHavingQual)
1134                         sub_limit_tuples = -1.0;
1135                 else
1136                         sub_limit_tuples = limit_tuples;
1137
1138                 /*
1139                  * Generate the best unsorted and presorted paths for this Query (but
1140                  * note there may not be any presorted path).  query_planner will also
1141                  * estimate the number of groups in the query, and canonicalize all
1142                  * the pathkeys.
1143                  */
1144                 query_planner(root, sub_tlist, tuple_fraction, sub_limit_tuples,
1145                                           &cheapest_path, &sorted_path, &dNumGroups);
1146
1147                 /*
1148                  * Extract rowcount and width estimates for possible use in grouping
1149                  * decisions.  Beware here of the possibility that
1150                  * cheapest_path->parent is NULL (ie, there is no FROM clause).
1151                  */
1152                 if (cheapest_path->parent)
1153                 {
1154                         path_rows = cheapest_path->parent->rows;
1155                         path_width = cheapest_path->parent->width;
1156                 }
1157                 else
1158                 {
1159                         path_rows = 1;          /* assume non-set result */
1160                         path_width = 100;       /* arbitrary */
1161                 }
1162
1163                 if (parse->groupClause)
1164                 {
1165                         /*
1166                          * If grouping, decide whether to use sorted or hashed grouping.
1167                          */
1168                         use_hashed_grouping =
1169                                 choose_hashed_grouping(root,
1170                                                                            tuple_fraction, limit_tuples,
1171                                                                            path_rows, path_width,
1172                                                                            cheapest_path, sorted_path,
1173                                                                            dNumGroups, &agg_counts);
1174                         /* Also convert # groups to long int --- but 'ware overflow! */
1175                         numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
1176                 }
1177                 else if (parse->distinctClause && sorted_path &&
1178                                  !root->hasHavingQual && !parse->hasAggs && !activeWindows)
1179                 {
1180                         /*
1181                          * We'll reach the DISTINCT stage without any intermediate
1182                          * processing, so figure out whether we will want to hash or not
1183                          * so we can choose whether to use cheapest or sorted path.
1184                          */
1185                         use_hashed_distinct =
1186                                 choose_hashed_distinct(root,
1187                                                                            tuple_fraction, limit_tuples,
1188                                                                            path_rows, path_width,
1189                                                                            cheapest_path->startup_cost,
1190                                                                            cheapest_path->total_cost,
1191                                                                            sorted_path->startup_cost,
1192                                                                            sorted_path->total_cost,
1193                                                                            sorted_path->pathkeys,
1194                                                                            dNumGroups);
1195                         tested_hashed_distinct = true;
1196                 }
1197
1198                 /*
1199                  * Select the best path.  If we are doing hashed grouping, we will
1200                  * always read all the input tuples, so use the cheapest-total path.
1201                  * Otherwise, trust query_planner's decision about which to use.
1202                  */
1203                 if (use_hashed_grouping || use_hashed_distinct || !sorted_path)
1204                         best_path = cheapest_path;
1205                 else
1206                         best_path = sorted_path;
1207
1208                 /*
1209                  * Check to see if it's possible to optimize MIN/MAX aggregates. If
1210                  * so, we will forget all the work we did so far to choose a "regular"
1211                  * path ... but we had to do it anyway to be able to tell which way is
1212                  * cheaper.
1213                  */
1214                 result_plan = optimize_minmax_aggregates(root,
1215                                                                                                  tlist,
1216                                                                                                  best_path);
1217                 if (result_plan != NULL)
1218                 {
1219                         /*
1220                          * optimize_minmax_aggregates generated the full plan, with the
1221                          * right tlist, and it has no sort order.
1222                          */
1223                         current_pathkeys = NIL;
1224                 }
1225                 else
1226                 {
1227                         /*
1228                          * Normal case --- create a plan according to query_planner's
1229                          * results.
1230                          */
1231                         bool            need_sort_for_grouping = false;
1232
1233                         result_plan = create_plan(root, best_path);
1234                         current_pathkeys = best_path->pathkeys;
1235
1236                         /* Detect if we'll need an explicit sort for grouping */
1237                         if (parse->groupClause && !use_hashed_grouping &&
1238                           !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
1239                         {
1240                                 need_sort_for_grouping = true;
1241
1242                                 /*
1243                                  * Always override query_planner's tlist, so that we don't
1244                                  * sort useless data from a "physical" tlist.
1245                                  */
1246                                 need_tlist_eval = true;
1247                         }
1248
1249                         /*
1250                          * create_plan() returns a plan with just a "flat" tlist of
1251                          * required Vars.  Usually we need to insert the sub_tlist as the
1252                          * tlist of the top plan node.  However, we can skip that if we
1253                          * determined that whatever query_planner chose to return will be
1254                          * good enough.
1255                          */
1256                         if (need_tlist_eval)
1257                         {
1258                                 /*
1259                                  * If the top-level plan node is one that cannot do expression
1260                                  * evaluation, we must insert a Result node to project the
1261                                  * desired tlist.
1262                                  */
1263                                 if (!is_projection_capable_plan(result_plan))
1264                                 {
1265                                         result_plan = (Plan *) make_result(root,
1266                                                                                                            sub_tlist,
1267                                                                                                            NULL,
1268                                                                                                            result_plan);
1269                                 }
1270                                 else
1271                                 {
1272                                         /*
1273                                          * Otherwise, just replace the subplan's flat tlist with
1274                                          * the desired tlist.
1275                                          */
1276                                         result_plan->targetlist = sub_tlist;
1277                                 }
1278
1279                                 /*
1280                                  * Also, account for the cost of evaluation of the sub_tlist.
1281                                  *
1282                                  * Up to now, we have only been dealing with "flat" tlists,
1283                                  * containing just Vars.  So their evaluation cost is zero
1284                                  * according to the model used by cost_qual_eval() (or if you
1285                                  * prefer, the cost is factored into cpu_tuple_cost).  Thus we
1286                                  * can avoid accounting for tlist cost throughout
1287                                  * query_planner() and subroutines.  But now we've inserted a
1288                                  * tlist that might contain actual operators, sub-selects, etc
1289                                  * --- so we'd better account for its cost.
1290                                  *
1291                                  * Below this point, any tlist eval cost for added-on nodes
1292                                  * should be accounted for as we create those nodes.
1293                                  * Presently, of the node types we can add on, only Agg,
1294                                  * WindowAgg, and Group project new tlists (the rest just copy
1295                                  * their input tuples) --- so make_agg(), make_windowagg() and
1296                                  * make_group() are responsible for computing the added cost.
1297                                  */
1298                                 cost_qual_eval(&tlist_cost, sub_tlist, root);
1299                                 result_plan->startup_cost += tlist_cost.startup;
1300                                 result_plan->total_cost += tlist_cost.startup +
1301                                         tlist_cost.per_tuple * result_plan->plan_rows;
1302                         }
1303                         else
1304                         {
1305                                 /*
1306                                  * Since we're using query_planner's tlist and not the one
1307                                  * make_subplanTargetList calculated, we have to refigure any
1308                                  * grouping-column indexes make_subplanTargetList computed.
1309                                  */
1310                                 locate_grouping_columns(root, tlist, result_plan->targetlist,
1311                                                                                 groupColIdx);
1312                         }
1313
1314                         /*
1315                          * Insert AGG or GROUP node if needed, plus an explicit sort step
1316                          * if necessary.
1317                          *
1318                          * HAVING clause, if any, becomes qual of the Agg or Group node.
1319                          */
1320                         if (use_hashed_grouping)
1321                         {
1322                                 /* Hashed aggregate plan --- no sort needed */
1323                                 result_plan = (Plan *) make_agg(root,
1324                                                                                                 tlist,
1325                                                                                                 (List *) parse->havingQual,
1326                                                                                                 AGG_HASHED,
1327                                                                                                 numGroupCols,
1328                                                                                                 groupColIdx,
1329                                                                         extract_grouping_ops(parse->groupClause),
1330                                                                                                 numGroups,
1331                                                                                                 agg_counts.numAggs,
1332                                                                                                 result_plan);
1333                                 /* Hashed aggregation produces randomly-ordered results */
1334                                 current_pathkeys = NIL;
1335                         }
1336                         else if (parse->hasAggs)
1337                         {
1338                                 /* Plain aggregate plan --- sort if needed */
1339                                 AggStrategy aggstrategy;
1340
1341                                 if (parse->groupClause)
1342                                 {
1343                                         if (need_sort_for_grouping)
1344                                         {
1345                                                 result_plan = (Plan *)
1346                                                         make_sort_from_groupcols(root,
1347                                                                                                          parse->groupClause,
1348                                                                                                          groupColIdx,
1349                                                                                                          result_plan);
1350                                                 current_pathkeys = root->group_pathkeys;
1351                                         }
1352                                         aggstrategy = AGG_SORTED;
1353
1354                                         /*
1355                                          * The AGG node will not change the sort ordering of its
1356                                          * groups, so current_pathkeys describes the result too.
1357                                          */
1358                                 }
1359                                 else
1360                                 {
1361                                         aggstrategy = AGG_PLAIN;
1362                                         /* Result will be only one row anyway; no sort order */
1363                                         current_pathkeys = NIL;
1364                                 }
1365
1366                                 result_plan = (Plan *) make_agg(root,
1367                                                                                                 tlist,
1368                                                                                                 (List *) parse->havingQual,
1369                                                                                                 aggstrategy,
1370                                                                                                 numGroupCols,
1371                                                                                                 groupColIdx,
1372                                                                         extract_grouping_ops(parse->groupClause),
1373                                                                                                 numGroups,
1374                                                                                                 agg_counts.numAggs,
1375                                                                                                 result_plan);
1376                         }
1377                         else if (parse->groupClause)
1378                         {
1379                                 /*
1380                                  * GROUP BY without aggregation, so insert a group node (plus
1381                                  * the appropriate sort node, if necessary).
1382                                  *
1383                                  * Add an explicit sort if we couldn't make the path come out
1384                                  * the way the GROUP node needs it.
1385                                  */
1386                                 if (need_sort_for_grouping)
1387                                 {
1388                                         result_plan = (Plan *)
1389                                                 make_sort_from_groupcols(root,
1390                                                                                                  parse->groupClause,
1391                                                                                                  groupColIdx,
1392                                                                                                  result_plan);
1393                                         current_pathkeys = root->group_pathkeys;
1394                                 }
1395
1396                                 result_plan = (Plan *) make_group(root,
1397                                                                                                   tlist,
1398                                                                                                   (List *) parse->havingQual,
1399                                                                                                   numGroupCols,
1400                                                                                                   groupColIdx,
1401                                                                         extract_grouping_ops(parse->groupClause),
1402                                                                                                   dNumGroups,
1403                                                                                                   result_plan);
1404                                 /* The Group node won't change sort ordering */
1405                         }
1406                         else if (root->hasHavingQual)
1407                         {
1408                                 /*
1409                                  * No aggregates, and no GROUP BY, but we have a HAVING qual.
1410                                  * This is a degenerate case in which we are supposed to emit
1411                                  * either 0 or 1 row depending on whether HAVING succeeds.
1412                                  * Furthermore, there cannot be any variables in either HAVING
1413                                  * or the targetlist, so we actually do not need the FROM
1414                                  * table at all!  We can just throw away the plan-so-far and
1415                                  * generate a Result node.      This is a sufficiently unusual
1416                                  * corner case that it's not worth contorting the structure of
1417                                  * this routine to avoid having to generate the plan in the
1418                                  * first place.
1419                                  */
1420                                 result_plan = (Plan *) make_result(root,
1421                                                                                                    tlist,
1422                                                                                                    parse->havingQual,
1423                                                                                                    NULL);
1424                         }
1425                 }                                               /* end of non-minmax-aggregate case */
1426
1427                 /*
1428                  * Since each window function could require a different sort order, we
1429                  * stack up a WindowAgg node for each window, with sort steps between
1430                  * them as needed.
1431                  */
1432                 if (activeWindows)
1433                 {
1434                         List       *window_tlist;
1435                         ListCell   *l;
1436
1437                         /*
1438                          * If the top-level plan node is one that cannot do expression
1439                          * evaluation, we must insert a Result node to project the desired
1440                          * tlist.  (In some cases this might not really be required, but
1441                          * it's not worth trying to avoid it.)  Note that on second and
1442                          * subsequent passes through the following loop, the top-level
1443                          * node will be a WindowAgg which we know can project; so we only
1444                          * need to check once.
1445                          */
1446                         if (!is_projection_capable_plan(result_plan))
1447                         {
1448                                 result_plan = (Plan *) make_result(root,
1449                                                                                                    NIL,
1450                                                                                                    NULL,
1451                                                                                                    result_plan);
1452                         }
1453
1454                         /*
1455                          * The "base" targetlist for all steps of the windowing process is
1456                          * a flat tlist of all Vars and Aggs needed in the result. (In
1457                          * some cases we wouldn't need to propagate all of these all the
1458                          * way to the top, since they might only be needed as inputs to
1459                          * WindowFuncs.  It's probably not worth trying to optimize that
1460                          * though.)  We also need any volatile sort expressions, because
1461                          * make_sort_from_pathkeys won't add those on its own, and anyway
1462                          * we want them evaluated only once at the bottom of the stack. As
1463                          * we climb up the stack, we add outputs for the WindowFuncs
1464                          * computed at each level.      Also, each input tlist has to present
1465                          * all the columns needed to sort the data for the next WindowAgg
1466                          * step.  That's handled internally by make_sort_from_pathkeys,
1467                          * but we need the copyObject steps here to ensure that each plan
1468                          * node has a separately modifiable tlist.
1469                          */
1470                         window_tlist = flatten_tlist(tlist);
1471                         if (parse->hasAggs)
1472                                 window_tlist = add_to_flat_tlist(window_tlist,
1473                                                                                         pull_agg_clause((Node *) tlist));
1474                         window_tlist = add_volatile_sort_exprs(window_tlist, tlist,
1475                                                                                                    activeWindows);
1476                         result_plan->targetlist = (List *) copyObject(window_tlist);
1477
1478                         foreach(l, activeWindows)
1479                         {
1480                                 WindowClause *wc = (WindowClause *) lfirst(l);
1481                                 List       *window_pathkeys;
1482                                 int                     partNumCols;
1483                                 AttrNumber *partColIdx;
1484                                 Oid                *partOperators;
1485                                 int                     ordNumCols;
1486                                 AttrNumber *ordColIdx;
1487                                 Oid                *ordOperators;
1488
1489                                 window_pathkeys = make_pathkeys_for_window(root,
1490                                                                                                                    wc,
1491                                                                                                                    tlist,
1492                                                                                                                    true);
1493
1494                                 /*
1495                                  * This is a bit tricky: we build a sort node even if we don't
1496                                  * really have to sort.  Even when no explicit sort is needed,
1497                                  * we need to have suitable resjunk items added to the input
1498                                  * plan's tlist for any partitioning or ordering columns that
1499                                  * aren't plain Vars.  Furthermore, this way we can use
1500                                  * existing infrastructure to identify which input columns are
1501                                  * the interesting ones.
1502                                  */
1503                                 if (window_pathkeys)
1504                                 {
1505                                         Sort       *sort_plan;
1506
1507                                         sort_plan = make_sort_from_pathkeys(root,
1508                                                                                                                 result_plan,
1509                                                                                                                 window_pathkeys,
1510                                                                                                                 -1.0);
1511                                         if (!pathkeys_contained_in(window_pathkeys,
1512                                                                                            current_pathkeys))
1513                                         {
1514                                                 /* we do indeed need to sort */
1515                                                 result_plan = (Plan *) sort_plan;
1516                                                 current_pathkeys = window_pathkeys;
1517                                         }
1518                                         /* In either case, extract the per-column information */
1519                                         get_column_info_for_window(root, wc, tlist,
1520                                                                                            sort_plan->numCols,
1521                                                                                            sort_plan->sortColIdx,
1522                                                                                            &partNumCols,
1523                                                                                            &partColIdx,
1524                                                                                            &partOperators,
1525                                                                                            &ordNumCols,
1526                                                                                            &ordColIdx,
1527                                                                                            &ordOperators);
1528                                 }
1529                                 else
1530                                 {
1531                                         /* empty window specification, nothing to sort */
1532                                         partNumCols = 0;
1533                                         partColIdx = NULL;
1534                                         partOperators = NULL;
1535                                         ordNumCols = 0;
1536                                         ordColIdx = NULL;
1537                                         ordOperators = NULL;
1538                                 }
1539
1540                                 if (lnext(l))
1541                                 {
1542                                         /* Add the current WindowFuncs to the running tlist */
1543                                         window_tlist = add_to_flat_tlist(window_tlist,
1544                                                                                    wflists->windowFuncs[wc->winref]);
1545                                 }
1546                                 else
1547                                 {
1548                                         /* Install the original tlist in the topmost WindowAgg */
1549                                         window_tlist = tlist;
1550                                 }
1551
1552                                 /* ... and make the WindowAgg plan node */
1553                                 result_plan = (Plan *)
1554                                         make_windowagg(root,
1555                                                                    (List *) copyObject(window_tlist),
1556                                                            list_length(wflists->windowFuncs[wc->winref]),
1557                                                                    wc->winref,
1558                                                                    partNumCols,
1559                                                                    partColIdx,
1560                                                                    partOperators,
1561                                                                    ordNumCols,
1562                                                                    ordColIdx,
1563                                                                    ordOperators,
1564                                                                    wc->frameOptions,
1565                                                                    wc->startOffset,
1566                                                                    wc->endOffset,
1567                                                                    result_plan);
1568                         }
1569                 }
1570         }                                                       /* end of if (setOperations) */
1571
1572         /*
1573          * If there is a DISTINCT clause, add the necessary node(s).
1574          */
1575         if (parse->distinctClause)
1576         {
1577                 double          dNumDistinctRows;
1578                 long            numDistinctRows;
1579
1580                 /*
1581                  * If there was grouping or aggregation, use the current number of
1582                  * rows as the estimated number of DISTINCT rows (ie, assume the
1583                  * result was already mostly unique).  If not, use the number of
1584                  * distinct-groups calculated by query_planner.
1585                  */
1586                 if (parse->groupClause || root->hasHavingQual || parse->hasAggs)
1587                         dNumDistinctRows = result_plan->plan_rows;
1588                 else
1589                         dNumDistinctRows = dNumGroups;
1590
1591                 /* Also convert to long int --- but 'ware overflow! */
1592                 numDistinctRows = (long) Min(dNumDistinctRows, (double) LONG_MAX);
1593
1594                 /* Choose implementation method if we didn't already */
1595                 if (!tested_hashed_distinct)
1596                 {
1597                         /*
1598                          * At this point, either hashed or sorted grouping will have to
1599                          * work from result_plan, so we pass that as both "cheapest" and
1600                          * "sorted".
1601                          */
1602                         use_hashed_distinct =
1603                                 choose_hashed_distinct(root,
1604                                                                            tuple_fraction, limit_tuples,
1605                                                                            result_plan->plan_rows,
1606                                                                            result_plan->plan_width,
1607                                                                            result_plan->startup_cost,
1608                                                                            result_plan->total_cost,
1609                                                                            result_plan->startup_cost,
1610                                                                            result_plan->total_cost,
1611                                                                            current_pathkeys,
1612                                                                            dNumDistinctRows);
1613                 }
1614
1615                 if (use_hashed_distinct)
1616                 {
1617                         /* Hashed aggregate plan --- no sort needed */
1618                         result_plan = (Plan *) make_agg(root,
1619                                                                                         result_plan->targetlist,
1620                                                                                         NIL,
1621                                                                                         AGG_HASHED,
1622                                                                                   list_length(parse->distinctClause),
1623                                                                  extract_grouping_cols(parse->distinctClause,
1624                                                                                                         result_plan->targetlist),
1625                                                                  extract_grouping_ops(parse->distinctClause),
1626                                                                                         numDistinctRows,
1627                                                                                         0,
1628                                                                                         result_plan);
1629                         /* Hashed aggregation produces randomly-ordered results */
1630                         current_pathkeys = NIL;
1631                 }
1632                 else
1633                 {
1634                         /*
1635                          * Use a Unique node to implement DISTINCT.  Add an explicit sort
1636                          * if we couldn't make the path come out the way the Unique node
1637                          * needs it.  If we do have to sort, always sort by the more
1638                          * rigorous of DISTINCT and ORDER BY, to avoid a second sort
1639                          * below.  However, for regular DISTINCT, don't sort now if we
1640                          * don't have to --- sorting afterwards will likely be cheaper,
1641                          * and also has the possibility of optimizing via LIMIT.  But for
1642                          * DISTINCT ON, we *must* force the final sort now, else it won't
1643                          * have the desired behavior.
1644                          */
1645                         List       *needed_pathkeys;
1646
1647                         if (parse->hasDistinctOn &&
1648                                 list_length(root->distinct_pathkeys) <
1649                                 list_length(root->sort_pathkeys))
1650                                 needed_pathkeys = root->sort_pathkeys;
1651                         else
1652                                 needed_pathkeys = root->distinct_pathkeys;
1653
1654                         if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
1655                         {
1656                                 if (list_length(root->distinct_pathkeys) >=
1657                                         list_length(root->sort_pathkeys))
1658                                         current_pathkeys = root->distinct_pathkeys;
1659                                 else
1660                                 {
1661                                         current_pathkeys = root->sort_pathkeys;
1662                                         /* Assert checks that parser didn't mess up... */
1663                                         Assert(pathkeys_contained_in(root->distinct_pathkeys,
1664                                                                                                  current_pathkeys));
1665                                 }
1666
1667                                 result_plan = (Plan *) make_sort_from_pathkeys(root,
1668                                                                                                                            result_plan,
1669                                                                                                                         current_pathkeys,
1670                                                                                                                            -1.0);
1671                         }
1672
1673                         result_plan = (Plan *) make_unique(result_plan,
1674                                                                                            parse->distinctClause);
1675                         result_plan->plan_rows = dNumDistinctRows;
1676                         /* The Unique node won't change sort ordering */
1677                 }
1678         }
1679
1680         /*
1681          * If ORDER BY was given and we were not able to make the plan come out in
1682          * the right order, add an explicit sort step.
1683          */
1684         if (parse->sortClause)
1685         {
1686                 if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
1687                 {
1688                         result_plan = (Plan *) make_sort_from_pathkeys(root,
1689                                                                                                                    result_plan,
1690                                                                                                                  root->sort_pathkeys,
1691                                                                                                                    limit_tuples);
1692                         current_pathkeys = root->sort_pathkeys;
1693                 }
1694         }
1695
1696         /*
1697          * If there is a FOR UPDATE/SHARE clause, add the LockRows node. (Note: we
1698          * intentionally test parse->rowMarks not root->rowMarks here. If there
1699          * are only non-locking rowmarks, they should be handled by the
1700          * ModifyTable node instead.)
1701          */
1702         if (parse->rowMarks)
1703         {
1704                 result_plan = (Plan *) make_lockrows(result_plan,
1705                                                                                          root->rowMarks,
1706                                                                                          SS_assign_special_param(root));
1707
1708                 /*
1709                  * The result can no longer be assumed sorted, since locking might
1710                  * cause the sort key columns to be replaced with new values.
1711                  */
1712                 current_pathkeys = NIL;
1713         }
1714
1715         /*
1716          * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node.
1717          */
1718         if (parse->limitCount || parse->limitOffset)
1719         {
1720                 result_plan = (Plan *) make_limit(result_plan,
1721                                                                                   parse->limitOffset,
1722                                                                                   parse->limitCount,
1723                                                                                   offset_est,
1724                                                                                   count_est);
1725         }
1726
1727         /* Compute result-relations list if needed */
1728         if (parse->resultRelation)
1729                 root->resultRelations = list_make1_int(parse->resultRelation);
1730         else
1731                 root->resultRelations = NIL;
1732
1733         /*
1734          * Return the actual output ordering in query_pathkeys for possible use by
1735          * an outer query level.
1736          */
1737         root->query_pathkeys = current_pathkeys;
1738
1739         return result_plan;
1740 }
1741
1742 /*
1743  * Detect whether a plan node is a "dummy" plan created when a relation
1744  * is deemed not to need scanning due to constraint exclusion.
1745  *
1746  * Currently, such dummy plans are Result nodes with constant FALSE
1747  * filter quals.
1748  */
1749 static bool
1750 is_dummy_plan(Plan *plan)
1751 {
1752         if (IsA(plan, Result))
1753         {
1754                 List       *rcqual = (List *) ((Result *) plan)->resconstantqual;
1755
1756                 if (list_length(rcqual) == 1)
1757                 {
1758                         Const      *constqual = (Const *) linitial(rcqual);
1759
1760                         if (constqual && IsA(constqual, Const))
1761                         {
1762                                 if (!constqual->constisnull &&
1763                                         !DatumGetBool(constqual->constvalue))
1764                                         return true;
1765                         }
1766                 }
1767         }
1768         return false;
1769 }
1770
1771 /*
1772  * Create a bitmapset of the RT indexes of live base relations
1773  *
1774  * Helper for preprocess_rowmarks ... at this point in the proceedings,
1775  * the only good way to distinguish baserels from appendrel children
1776  * is to see what is in the join tree.
1777  */
1778 static Bitmapset *
1779 get_base_rel_indexes(Node *jtnode)
1780 {
1781         Bitmapset  *result;
1782
1783         if (jtnode == NULL)
1784                 return NULL;
1785         if (IsA(jtnode, RangeTblRef))
1786         {
1787                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1788
1789                 result = bms_make_singleton(varno);
1790         }
1791         else if (IsA(jtnode, FromExpr))
1792         {
1793                 FromExpr   *f = (FromExpr *) jtnode;
1794                 ListCell   *l;
1795
1796                 result = NULL;
1797                 foreach(l, f->fromlist)
1798                         result = bms_join(result,
1799                                                           get_base_rel_indexes(lfirst(l)));
1800         }
1801         else if (IsA(jtnode, JoinExpr))
1802         {
1803                 JoinExpr   *j = (JoinExpr *) jtnode;
1804
1805                 result = bms_join(get_base_rel_indexes(j->larg),
1806                                                   get_base_rel_indexes(j->rarg));
1807         }
1808         else
1809         {
1810                 elog(ERROR, "unrecognized node type: %d",
1811                          (int) nodeTag(jtnode));
1812                 result = NULL;                  /* keep compiler quiet */
1813         }
1814         return result;
1815 }
1816
1817 /*
1818  * preprocess_rowmarks - set up PlanRowMarks if needed
1819  */
1820 static void
1821 preprocess_rowmarks(PlannerInfo *root)
1822 {
1823         Query      *parse = root->parse;
1824         Bitmapset  *rels;
1825         List       *prowmarks;
1826         ListCell   *l;
1827         int                     i;
1828
1829         if (parse->rowMarks)
1830         {
1831                 /*
1832                  * We've got trouble if FOR UPDATE/SHARE appears inside grouping,
1833                  * since grouping renders a reference to individual tuple CTIDs
1834                  * invalid.  This is also checked at parse time, but that's
1835                  * insufficient because of rule substitution, query pullup, etc.
1836                  */
1837                 CheckSelectLocking(parse);
1838         }
1839         else
1840         {
1841                 /*
1842                  * We only need rowmarks for UPDATE, DELETE, or FOR UPDATE/SHARE.
1843                  */
1844                 if (parse->commandType != CMD_UPDATE &&
1845                         parse->commandType != CMD_DELETE)
1846                         return;
1847         }
1848
1849         /*
1850          * We need to have rowmarks for all base relations except the target. We
1851          * make a bitmapset of all base rels and then remove the items we don't
1852          * need or have FOR UPDATE/SHARE marks for.
1853          */
1854         rels = get_base_rel_indexes((Node *) parse->jointree);
1855         if (parse->resultRelation)
1856                 rels = bms_del_member(rels, parse->resultRelation);
1857
1858         /*
1859          * Convert RowMarkClauses to PlanRowMark representation.
1860          */
1861         prowmarks = NIL;
1862         foreach(l, parse->rowMarks)
1863         {
1864                 RowMarkClause *rc = (RowMarkClause *) lfirst(l);
1865                 RangeTblEntry *rte = rt_fetch(rc->rti, parse->rtable);
1866                 PlanRowMark *newrc;
1867
1868                 /*
1869                  * Currently, it is syntactically impossible to have FOR UPDATE
1870                  * applied to an update/delete target rel.      If that ever becomes
1871                  * possible, we should drop the target from the PlanRowMark list.
1872                  */
1873                 Assert(rc->rti != parse->resultRelation);
1874
1875                 /*
1876                  * Ignore RowMarkClauses for subqueries; they aren't real tables and
1877                  * can't support true locking.  Subqueries that got flattened into the
1878                  * main query should be ignored completely.  Any that didn't will get
1879                  * ROW_MARK_COPY items in the next loop.
1880                  */
1881                 if (rte->rtekind != RTE_RELATION)
1882                         continue;
1883
1884                 rels = bms_del_member(rels, rc->rti);
1885
1886                 newrc = makeNode(PlanRowMark);
1887                 newrc->rti = newrc->prti = rc->rti;
1888                 if (rc->forUpdate)
1889                         newrc->markType = ROW_MARK_EXCLUSIVE;
1890                 else
1891                         newrc->markType = ROW_MARK_SHARE;
1892                 newrc->noWait = rc->noWait;
1893                 newrc->isParent = false;
1894
1895                 prowmarks = lappend(prowmarks, newrc);
1896         }
1897
1898         /*
1899          * Now, add rowmarks for any non-target, non-locked base relations.
1900          */
1901         i = 0;
1902         foreach(l, parse->rtable)
1903         {
1904                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
1905                 PlanRowMark *newrc;
1906
1907                 i++;
1908                 if (!bms_is_member(i, rels))
1909                         continue;
1910
1911                 newrc = makeNode(PlanRowMark);
1912                 newrc->rti = newrc->prti = i;
1913                 /* real tables support REFERENCE, anything else needs COPY */
1914                 if (rte->rtekind == RTE_RELATION)
1915                         newrc->markType = ROW_MARK_REFERENCE;
1916                 else
1917                         newrc->markType = ROW_MARK_COPY;
1918                 newrc->noWait = false;  /* doesn't matter */
1919                 newrc->isParent = false;
1920
1921                 prowmarks = lappend(prowmarks, newrc);
1922         }
1923
1924         root->rowMarks = prowmarks;
1925 }
1926
1927 /*
1928  * preprocess_limit - do pre-estimation for LIMIT and/or OFFSET clauses
1929  *
1930  * We try to estimate the values of the LIMIT/OFFSET clauses, and pass the
1931  * results back in *count_est and *offset_est.  These variables are set to
1932  * 0 if the corresponding clause is not present, and -1 if it's present
1933  * but we couldn't estimate the value for it.  (The "0" convention is OK
1934  * for OFFSET but a little bit bogus for LIMIT: effectively we estimate
1935  * LIMIT 0 as though it were LIMIT 1.  But this is in line with the planner's
1936  * usual practice of never estimating less than one row.)  These values will
1937  * be passed to make_limit, which see if you change this code.
1938  *
1939  * The return value is the suitably adjusted tuple_fraction to use for
1940  * planning the query.  This adjustment is not overridable, since it reflects
1941  * plan actions that grouping_planner() will certainly take, not assumptions
1942  * about context.
1943  */
1944 static double
1945 preprocess_limit(PlannerInfo *root, double tuple_fraction,
1946                                  int64 *offset_est, int64 *count_est)
1947 {
1948         Query      *parse = root->parse;
1949         Node       *est;
1950         double          limit_fraction;
1951
1952         /* Should not be called unless LIMIT or OFFSET */
1953         Assert(parse->limitCount || parse->limitOffset);
1954
1955         /*
1956          * Try to obtain the clause values.  We use estimate_expression_value
1957          * primarily because it can sometimes do something useful with Params.
1958          */
1959         if (parse->limitCount)
1960         {
1961                 est = estimate_expression_value(root, parse->limitCount);
1962                 if (est && IsA(est, Const))
1963                 {
1964                         if (((Const *) est)->constisnull)
1965                         {
1966                                 /* NULL indicates LIMIT ALL, ie, no limit */
1967                                 *count_est = 0; /* treat as not present */
1968                         }
1969                         else
1970                         {
1971                                 *count_est = DatumGetInt64(((Const *) est)->constvalue);
1972                                 if (*count_est <= 0)
1973                                         *count_est = 1;         /* force to at least 1 */
1974                         }
1975                 }
1976                 else
1977                         *count_est = -1;        /* can't estimate */
1978         }
1979         else
1980                 *count_est = 0;                 /* not present */
1981
1982         if (parse->limitOffset)
1983         {
1984                 est = estimate_expression_value(root, parse->limitOffset);
1985                 if (est && IsA(est, Const))
1986                 {
1987                         if (((Const *) est)->constisnull)
1988                         {
1989                                 /* Treat NULL as no offset; the executor will too */
1990                                 *offset_est = 0;        /* treat as not present */
1991                         }
1992                         else
1993                         {
1994                                 *offset_est = DatumGetInt64(((Const *) est)->constvalue);
1995                                 if (*offset_est < 0)
1996                                         *offset_est = 0;        /* less than 0 is same as 0 */
1997                         }
1998                 }
1999                 else
2000                         *offset_est = -1;       /* can't estimate */
2001         }
2002         else
2003                 *offset_est = 0;                /* not present */
2004
2005         if (*count_est != 0)
2006         {
2007                 /*
2008                  * A LIMIT clause limits the absolute number of tuples returned.
2009                  * However, if it's not a constant LIMIT then we have to guess; for
2010                  * lack of a better idea, assume 10% of the plan's result is wanted.
2011                  */
2012                 if (*count_est < 0 || *offset_est < 0)
2013                 {
2014                         /* LIMIT or OFFSET is an expression ... punt ... */
2015                         limit_fraction = 0.10;
2016                 }
2017                 else
2018                 {
2019                         /* LIMIT (plus OFFSET, if any) is max number of tuples needed */
2020                         limit_fraction = (double) *count_est + (double) *offset_est;
2021                 }
2022
2023                 /*
2024                  * If we have absolute limits from both caller and LIMIT, use the
2025                  * smaller value; likewise if they are both fractional.  If one is
2026                  * fractional and the other absolute, we can't easily determine which
2027                  * is smaller, but we use the heuristic that the absolute will usually
2028                  * be smaller.
2029                  */
2030                 if (tuple_fraction >= 1.0)
2031                 {
2032                         if (limit_fraction >= 1.0)
2033                         {
2034                                 /* both absolute */
2035                                 tuple_fraction = Min(tuple_fraction, limit_fraction);
2036                         }
2037                         else
2038                         {
2039                                 /* caller absolute, limit fractional; use caller's value */
2040                         }
2041                 }
2042                 else if (tuple_fraction > 0.0)
2043                 {
2044                         if (limit_fraction >= 1.0)
2045                         {
2046                                 /* caller fractional, limit absolute; use limit */
2047                                 tuple_fraction = limit_fraction;
2048                         }
2049                         else
2050                         {
2051                                 /* both fractional */
2052                                 tuple_fraction = Min(tuple_fraction, limit_fraction);
2053                         }
2054                 }
2055                 else
2056                 {
2057                         /* no info from caller, just use limit */
2058                         tuple_fraction = limit_fraction;
2059                 }
2060         }
2061         else if (*offset_est != 0 && tuple_fraction > 0.0)
2062         {
2063                 /*
2064                  * We have an OFFSET but no LIMIT.      This acts entirely differently
2065                  * from the LIMIT case: here, we need to increase rather than decrease
2066                  * the caller's tuple_fraction, because the OFFSET acts to cause more
2067                  * tuples to be fetched instead of fewer.  This only matters if we got
2068                  * a tuple_fraction > 0, however.
2069                  *
2070                  * As above, use 10% if OFFSET is present but unestimatable.
2071                  */
2072                 if (*offset_est < 0)
2073                         limit_fraction = 0.10;
2074                 else
2075                         limit_fraction = (double) *offset_est;
2076
2077                 /*
2078                  * If we have absolute counts from both caller and OFFSET, add them
2079                  * together; likewise if they are both fractional.      If one is
2080                  * fractional and the other absolute, we want to take the larger, and
2081                  * we heuristically assume that's the fractional one.
2082                  */
2083                 if (tuple_fraction >= 1.0)
2084                 {
2085                         if (limit_fraction >= 1.0)
2086                         {
2087                                 /* both absolute, so add them together */
2088                                 tuple_fraction += limit_fraction;
2089                         }
2090                         else
2091                         {
2092                                 /* caller absolute, limit fractional; use limit */
2093                                 tuple_fraction = limit_fraction;
2094                         }
2095                 }
2096                 else
2097                 {
2098                         if (limit_fraction >= 1.0)
2099                         {
2100                                 /* caller fractional, limit absolute; use caller's value */
2101                         }
2102                         else
2103                         {
2104                                 /* both fractional, so add them together */
2105                                 tuple_fraction += limit_fraction;
2106                                 if (tuple_fraction >= 1.0)
2107                                         tuple_fraction = 0.0;           /* assume fetch all */
2108                         }
2109                 }
2110         }
2111
2112         return tuple_fraction;
2113 }
2114
2115
2116 /*
2117  * preprocess_groupclause - do preparatory work on GROUP BY clause
2118  *
2119  * The idea here is to adjust the ordering of the GROUP BY elements
2120  * (which in itself is semantically insignificant) to match ORDER BY,
2121  * thereby allowing a single sort operation to both implement the ORDER BY
2122  * requirement and set up for a Unique step that implements GROUP BY.
2123  *
2124  * In principle it might be interesting to consider other orderings of the
2125  * GROUP BY elements, which could match the sort ordering of other
2126  * possible plans (eg an indexscan) and thereby reduce cost.  We don't
2127  * bother with that, though.  Hashed grouping will frequently win anyway.
2128  *
2129  * Note: we need no comparable processing of the distinctClause because
2130  * the parser already enforced that that matches ORDER BY.
2131  */
2132 static void
2133 preprocess_groupclause(PlannerInfo *root)
2134 {
2135         Query      *parse = root->parse;
2136         List       *new_groupclause;
2137         bool            partial_match;
2138         ListCell   *sl;
2139         ListCell   *gl;
2140
2141         /* If no ORDER BY, nothing useful to do here */
2142         if (parse->sortClause == NIL)
2143                 return;
2144
2145         /*
2146          * Scan the ORDER BY clause and construct a list of matching GROUP BY
2147          * items, but only as far as we can make a matching prefix.
2148          *
2149          * This code assumes that the sortClause contains no duplicate items.
2150          */
2151         new_groupclause = NIL;
2152         foreach(sl, parse->sortClause)
2153         {
2154                 SortGroupClause *sc = (SortGroupClause *) lfirst(sl);
2155
2156                 foreach(gl, parse->groupClause)
2157                 {
2158                         SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
2159
2160                         if (equal(gc, sc))
2161                         {
2162                                 new_groupclause = lappend(new_groupclause, gc);
2163                                 break;
2164                         }
2165                 }
2166                 if (gl == NULL)
2167                         break;                          /* no match, so stop scanning */
2168         }
2169
2170         /* Did we match all of the ORDER BY list, or just some of it? */
2171         partial_match = (sl != NULL);
2172
2173         /* If no match at all, no point in reordering GROUP BY */
2174         if (new_groupclause == NIL)
2175                 return;
2176
2177         /*
2178          * Add any remaining GROUP BY items to the new list, but only if we were
2179          * able to make a complete match.  In other words, we only rearrange the
2180          * GROUP BY list if the result is that one list is a prefix of the other
2181          * --- otherwise there's no possibility of a common sort.  Also, give up
2182          * if there are any non-sortable GROUP BY items, since then there's no
2183          * hope anyway.
2184          */
2185         foreach(gl, parse->groupClause)
2186         {
2187                 SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
2188
2189                 if (list_member_ptr(new_groupclause, gc))
2190                         continue;                       /* it matched an ORDER BY item */
2191                 if (partial_match)
2192                         return;                         /* give up, no common sort possible */
2193                 if (!OidIsValid(gc->sortop))
2194                         return;                         /* give up, GROUP BY can't be sorted */
2195                 new_groupclause = lappend(new_groupclause, gc);
2196         }
2197
2198         /* Success --- install the rearranged GROUP BY list */
2199         Assert(list_length(parse->groupClause) == list_length(new_groupclause));
2200         parse->groupClause = new_groupclause;
2201 }
2202
2203 /*
2204  * choose_hashed_grouping - should we use hashed grouping?
2205  *
2206  * Returns TRUE to select hashing, FALSE to select sorting.
2207  */
2208 static bool
2209 choose_hashed_grouping(PlannerInfo *root,
2210                                            double tuple_fraction, double limit_tuples,
2211                                            double path_rows, int path_width,
2212                                            Path *cheapest_path, Path *sorted_path,
2213                                            double dNumGroups, AggClauseCounts *agg_counts)
2214 {
2215         Query      *parse = root->parse;
2216         int                     numGroupCols = list_length(parse->groupClause);
2217         bool            can_hash;
2218         bool            can_sort;
2219         Size            hashentrysize;
2220         List       *target_pathkeys;
2221         List       *current_pathkeys;
2222         Path            hashed_p;
2223         Path            sorted_p;
2224
2225         /*
2226          * Executor doesn't support hashed aggregation with DISTINCT or ORDER BY
2227          * aggregates.  (Doing so would imply storing *all* the input values in
2228          * the hash table, and/or running many sorts in parallel, either of which
2229          * seems like a certain loser.)
2230          */
2231         can_hash = (agg_counts->numOrderedAggs == 0 &&
2232                                 grouping_is_hashable(parse->groupClause));
2233         can_sort = grouping_is_sortable(parse->groupClause);
2234
2235         /* Quick out if only one choice is workable */
2236         if (!(can_hash && can_sort))
2237         {
2238                 if (can_hash)
2239                         return true;
2240                 else if (can_sort)
2241                         return false;
2242                 else
2243                         ereport(ERROR,
2244                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2245                                          errmsg("could not implement GROUP BY"),
2246                                          errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
2247         }
2248
2249         /* Prefer sorting when enable_hashagg is off */
2250         if (!enable_hashagg)
2251                 return false;
2252
2253         /*
2254          * Don't do it if it doesn't look like the hashtable will fit into
2255          * work_mem.
2256          */
2257
2258         /* Estimate per-hash-entry space at tuple width... */
2259         hashentrysize = MAXALIGN(path_width) + MAXALIGN(sizeof(MinimalTupleData));
2260         /* plus space for pass-by-ref transition values... */
2261         hashentrysize += agg_counts->transitionSpace;
2262         /* plus the per-hash-entry overhead */
2263         hashentrysize += hash_agg_entry_size(agg_counts->numAggs);
2264
2265         if (hashentrysize * dNumGroups > work_mem * 1024L)
2266                 return false;
2267
2268         /*
2269          * When we have both GROUP BY and DISTINCT, use the more-rigorous of
2270          * DISTINCT and ORDER BY as the assumed required output sort order. This
2271          * is an oversimplification because the DISTINCT might get implemented via
2272          * hashing, but it's not clear that the case is common enough (or that our
2273          * estimates are good enough) to justify trying to solve it exactly.
2274          */
2275         if (list_length(root->distinct_pathkeys) >
2276                 list_length(root->sort_pathkeys))
2277                 target_pathkeys = root->distinct_pathkeys;
2278         else
2279                 target_pathkeys = root->sort_pathkeys;
2280
2281         /*
2282          * See if the estimated cost is no more than doing it the other way. While
2283          * avoiding the need for sorted input is usually a win, the fact that the
2284          * output won't be sorted may be a loss; so we need to do an actual cost
2285          * comparison.
2286          *
2287          * We need to consider cheapest_path + hashagg [+ final sort] versus
2288          * either cheapest_path [+ sort] + group or agg [+ final sort] or
2289          * presorted_path + group or agg [+ final sort] where brackets indicate a
2290          * step that may not be needed. We assume query_planner() will have
2291          * returned a presorted path only if it's a winner compared to
2292          * cheapest_path for this purpose.
2293          *
2294          * These path variables are dummies that just hold cost fields; we don't
2295          * make actual Paths for these steps.
2296          */
2297         cost_agg(&hashed_p, root, AGG_HASHED, agg_counts->numAggs,
2298                          numGroupCols, dNumGroups,
2299                          cheapest_path->startup_cost, cheapest_path->total_cost,
2300                          path_rows);
2301         /* Result of hashed agg is always unsorted */
2302         if (target_pathkeys)
2303                 cost_sort(&hashed_p, root, target_pathkeys, hashed_p.total_cost,
2304                                   dNumGroups, path_width,
2305                                   0.0, work_mem, limit_tuples);
2306
2307         if (sorted_path)
2308         {
2309                 sorted_p.startup_cost = sorted_path->startup_cost;
2310                 sorted_p.total_cost = sorted_path->total_cost;
2311                 current_pathkeys = sorted_path->pathkeys;
2312         }
2313         else
2314         {
2315                 sorted_p.startup_cost = cheapest_path->startup_cost;
2316                 sorted_p.total_cost = cheapest_path->total_cost;
2317                 current_pathkeys = cheapest_path->pathkeys;
2318         }
2319         if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
2320         {
2321                 cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost,
2322                                   path_rows, path_width,
2323                                   0.0, work_mem, -1.0);
2324                 current_pathkeys = root->group_pathkeys;
2325         }
2326
2327         if (parse->hasAggs)
2328                 cost_agg(&sorted_p, root, AGG_SORTED, agg_counts->numAggs,
2329                                  numGroupCols, dNumGroups,
2330                                  sorted_p.startup_cost, sorted_p.total_cost,
2331                                  path_rows);
2332         else
2333                 cost_group(&sorted_p, root, numGroupCols, dNumGroups,
2334                                    sorted_p.startup_cost, sorted_p.total_cost,
2335                                    path_rows);
2336         /* The Agg or Group node will preserve ordering */
2337         if (target_pathkeys &&
2338                 !pathkeys_contained_in(target_pathkeys, current_pathkeys))
2339                 cost_sort(&sorted_p, root, target_pathkeys, sorted_p.total_cost,
2340                                   dNumGroups, path_width,
2341                                   0.0, work_mem, limit_tuples);
2342
2343         /*
2344          * Now make the decision using the top-level tuple fraction.  First we
2345          * have to convert an absolute count (LIMIT) into fractional form.
2346          */
2347         if (tuple_fraction >= 1.0)
2348                 tuple_fraction /= dNumGroups;
2349
2350         if (compare_fractional_path_costs(&hashed_p, &sorted_p,
2351                                                                           tuple_fraction) < 0)
2352         {
2353                 /* Hashed is cheaper, so use it */
2354                 return true;
2355         }
2356         return false;
2357 }
2358
2359 /*
2360  * choose_hashed_distinct - should we use hashing for DISTINCT?
2361  *
2362  * This is fairly similar to choose_hashed_grouping, but there are enough
2363  * differences that it doesn't seem worth trying to unify the two functions.
2364  * (One difference is that we sometimes apply this after forming a Plan,
2365  * so the input alternatives can't be represented as Paths --- instead we
2366  * pass in the costs as individual variables.)
2367  *
2368  * But note that making the two choices independently is a bit bogus in
2369  * itself.      If the two could be combined into a single choice operation
2370  * it'd probably be better, but that seems far too unwieldy to be practical,
2371  * especially considering that the combination of GROUP BY and DISTINCT
2372  * isn't very common in real queries.  By separating them, we are giving
2373  * extra preference to using a sorting implementation when a common sort key
2374  * is available ... and that's not necessarily wrong anyway.
2375  *
2376  * Returns TRUE to select hashing, FALSE to select sorting.
2377  */
2378 static bool
2379 choose_hashed_distinct(PlannerInfo *root,
2380                                            double tuple_fraction, double limit_tuples,
2381                                            double path_rows, int path_width,
2382                                            Cost cheapest_startup_cost, Cost cheapest_total_cost,
2383                                            Cost sorted_startup_cost, Cost sorted_total_cost,
2384                                            List *sorted_pathkeys,
2385                                            double dNumDistinctRows)
2386 {
2387         Query      *parse = root->parse;
2388         int                     numDistinctCols = list_length(parse->distinctClause);
2389         bool            can_sort;
2390         bool            can_hash;
2391         Size            hashentrysize;
2392         List       *current_pathkeys;
2393         List       *needed_pathkeys;
2394         Path            hashed_p;
2395         Path            sorted_p;
2396
2397         /*
2398          * If we have a sortable DISTINCT ON clause, we always use sorting. This
2399          * enforces the expected behavior of DISTINCT ON.
2400          */
2401         can_sort = grouping_is_sortable(parse->distinctClause);
2402         if (can_sort && parse->hasDistinctOn)
2403                 return false;
2404
2405         can_hash = grouping_is_hashable(parse->distinctClause);
2406
2407         /* Quick out if only one choice is workable */
2408         if (!(can_hash && can_sort))
2409         {
2410                 if (can_hash)
2411                         return true;
2412                 else if (can_sort)
2413                         return false;
2414                 else
2415                         ereport(ERROR,
2416                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2417                                          errmsg("could not implement DISTINCT"),
2418                                          errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
2419         }
2420
2421         /* Prefer sorting when enable_hashagg is off */
2422         if (!enable_hashagg)
2423                 return false;
2424
2425         /*
2426          * Don't do it if it doesn't look like the hashtable will fit into
2427          * work_mem.
2428          */
2429         hashentrysize = MAXALIGN(path_width) + MAXALIGN(sizeof(MinimalTupleData));
2430
2431         if (hashentrysize * dNumDistinctRows > work_mem * 1024L)
2432                 return false;
2433
2434         /*
2435          * See if the estimated cost is no more than doing it the other way. While
2436          * avoiding the need for sorted input is usually a win, the fact that the
2437          * output won't be sorted may be a loss; so we need to do an actual cost
2438          * comparison.
2439          *
2440          * We need to consider cheapest_path + hashagg [+ final sort] versus
2441          * sorted_path [+ sort] + group [+ final sort] where brackets indicate a
2442          * step that may not be needed.
2443          *
2444          * These path variables are dummies that just hold cost fields; we don't
2445          * make actual Paths for these steps.
2446          */
2447         cost_agg(&hashed_p, root, AGG_HASHED, 0,
2448                          numDistinctCols, dNumDistinctRows,
2449                          cheapest_startup_cost, cheapest_total_cost,
2450                          path_rows);
2451
2452         /*
2453          * Result of hashed agg is always unsorted, so if ORDER BY is present we
2454          * need to charge for the final sort.
2455          */
2456         if (parse->sortClause)
2457                 cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost,
2458                                   dNumDistinctRows, path_width,
2459                                   0.0, work_mem, limit_tuples);
2460
2461         /*
2462          * Now for the GROUP case.      See comments in grouping_planner about the
2463          * sorting choices here --- this code should match that code.
2464          */
2465         sorted_p.startup_cost = sorted_startup_cost;
2466         sorted_p.total_cost = sorted_total_cost;
2467         current_pathkeys = sorted_pathkeys;
2468         if (parse->hasDistinctOn &&
2469                 list_length(root->distinct_pathkeys) <
2470                 list_length(root->sort_pathkeys))
2471                 needed_pathkeys = root->sort_pathkeys;
2472         else
2473                 needed_pathkeys = root->distinct_pathkeys;
2474         if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
2475         {
2476                 if (list_length(root->distinct_pathkeys) >=
2477                         list_length(root->sort_pathkeys))
2478                         current_pathkeys = root->distinct_pathkeys;
2479                 else
2480                         current_pathkeys = root->sort_pathkeys;
2481                 cost_sort(&sorted_p, root, current_pathkeys, sorted_p.total_cost,
2482                                   path_rows, path_width,
2483                                   0.0, work_mem, -1.0);
2484         }
2485         cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows,
2486                            sorted_p.startup_cost, sorted_p.total_cost,
2487                            path_rows);
2488         if (parse->sortClause &&
2489                 !pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
2490                 cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost,
2491                                   dNumDistinctRows, path_width,
2492                                   0.0, work_mem, limit_tuples);
2493
2494         /*
2495          * Now make the decision using the top-level tuple fraction.  First we
2496          * have to convert an absolute count (LIMIT) into fractional form.
2497          */
2498         if (tuple_fraction >= 1.0)
2499                 tuple_fraction /= dNumDistinctRows;
2500
2501         if (compare_fractional_path_costs(&hashed_p, &sorted_p,
2502                                                                           tuple_fraction) < 0)
2503         {
2504                 /* Hashed is cheaper, so use it */
2505                 return true;
2506         }
2507         return false;
2508 }
2509
2510 /*
2511  * make_subplanTargetList
2512  *        Generate appropriate target list when grouping is required.
2513  *
2514  * When grouping_planner inserts Aggregate, Group, or Result plan nodes
2515  * above the result of query_planner, we typically want to pass a different
2516  * target list to query_planner than the outer plan nodes should have.
2517  * This routine generates the correct target list for the subplan.
2518  *
2519  * The initial target list passed from the parser already contains entries
2520  * for all ORDER BY and GROUP BY expressions, but it will not have entries
2521  * for variables used only in HAVING clauses; so we need to add those
2522  * variables to the subplan target list.  Also, we flatten all expressions
2523  * except GROUP BY items into their component variables; the other expressions
2524  * will be computed by the inserted nodes rather than by the subplan.
2525  * For example, given a query like
2526  *              SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
2527  * we want to pass this targetlist to the subplan:
2528  *              a,b,c,d,a+b
2529  * where the a+b target will be used by the Sort/Group steps, and the
2530  * other targets will be used for computing the final results.  (In the
2531  * above example we could theoretically suppress the a and b targets and
2532  * pass down only c,d,a+b, but it's not really worth the trouble to
2533  * eliminate simple var references from the subplan.  We will avoid doing
2534  * the extra computation to recompute a+b at the outer level; see
2535  * fix_upper_expr() in setrefs.c.)
2536  *
2537  * If we are grouping or aggregating, *and* there are no non-Var grouping
2538  * expressions, then the returned tlist is effectively dummy; we do not
2539  * need to force it to be evaluated, because all the Vars it contains
2540  * should be present in the output of query_planner anyway.
2541  *
2542  * 'tlist' is the query's target list.
2543  * 'groupColIdx' receives an array of column numbers for the GROUP BY
2544  *                      expressions (if there are any) in the subplan's target list.
2545  * 'need_tlist_eval' is set true if we really need to evaluate the
2546  *                      result tlist.
2547  *
2548  * The result is the targetlist to be passed to the subplan.
2549  */
2550 static List *
2551 make_subplanTargetList(PlannerInfo *root,
2552                                            List *tlist,
2553                                            AttrNumber **groupColIdx,
2554                                            bool *need_tlist_eval)
2555 {
2556         Query      *parse = root->parse;
2557         List       *sub_tlist;
2558         List       *extravars;
2559         int                     numCols;
2560
2561         *groupColIdx = NULL;
2562
2563         /*
2564          * If we're not grouping or aggregating, there's nothing to do here;
2565          * query_planner should receive the unmodified target list.
2566          */
2567         if (!parse->hasAggs && !parse->groupClause && !root->hasHavingQual &&
2568                 !parse->hasWindowFuncs)
2569         {
2570                 *need_tlist_eval = true;
2571                 return tlist;
2572         }
2573
2574         /*
2575          * Otherwise, start with a "flattened" tlist (having just the vars
2576          * mentioned in the targetlist and HAVING qual --- but not upper-level
2577          * Vars; they will be replaced by Params later on).  Note this includes
2578          * vars used in resjunk items, so we are covering the needs of ORDER BY
2579          * and window specifications.
2580          */
2581         sub_tlist = flatten_tlist(tlist);
2582         extravars = pull_var_clause(parse->havingQual, PVC_INCLUDE_PLACEHOLDERS);
2583         sub_tlist = add_to_flat_tlist(sub_tlist, extravars);
2584         list_free(extravars);
2585         *need_tlist_eval = false;       /* only eval if not flat tlist */
2586
2587         /*
2588          * If grouping, create sub_tlist entries for all GROUP BY expressions
2589          * (GROUP BY items that are simple Vars should be in the list already),
2590          * and make an array showing where the group columns are in the sub_tlist.
2591          */
2592         numCols = list_length(parse->groupClause);
2593         if (numCols > 0)
2594         {
2595                 int                     keyno = 0;
2596                 AttrNumber *grpColIdx;
2597                 ListCell   *gl;
2598
2599                 grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2600                 *groupColIdx = grpColIdx;
2601
2602                 foreach(gl, parse->groupClause)
2603                 {
2604                         SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
2605                         Node       *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
2606                         TargetEntry *te;
2607
2608                         /*
2609                          * Find or make a matching sub_tlist entry.  If the groupexpr
2610                          * isn't a Var, no point in searching.  (Note that the parser
2611                          * won't make multiple groupClause entries for the same TLE.)
2612                          */
2613                         if (groupexpr && IsA(groupexpr, Var))
2614                                 te = tlist_member(groupexpr, sub_tlist);
2615                         else
2616                                 te = NULL;
2617
2618                         if (!te)
2619                         {
2620                                 te = makeTargetEntry((Expr *) groupexpr,
2621                                                                          list_length(sub_tlist) + 1,
2622                                                                          NULL,
2623                                                                          false);
2624                                 sub_tlist = lappend(sub_tlist, te);
2625                                 *need_tlist_eval = true;                /* it's not flat anymore */
2626                         }
2627
2628                         /* and save its resno */
2629                         grpColIdx[keyno++] = te->resno;
2630                 }
2631         }
2632
2633         return sub_tlist;
2634 }
2635
2636 /*
2637  * locate_grouping_columns
2638  *              Locate grouping columns in the tlist chosen by query_planner.
2639  *
2640  * This is only needed if we don't use the sub_tlist chosen by
2641  * make_subplanTargetList.      We have to forget the column indexes found
2642  * by that routine and re-locate the grouping exprs in the real sub_tlist.
2643  */
2644 static void
2645 locate_grouping_columns(PlannerInfo *root,
2646                                                 List *tlist,
2647                                                 List *sub_tlist,
2648                                                 AttrNumber *groupColIdx)
2649 {
2650         int                     keyno = 0;
2651         ListCell   *gl;
2652
2653         /*
2654          * No work unless grouping.
2655          */
2656         if (!root->parse->groupClause)
2657         {
2658                 Assert(groupColIdx == NULL);
2659                 return;
2660         }
2661         Assert(groupColIdx != NULL);
2662
2663         foreach(gl, root->parse->groupClause)
2664         {
2665                 SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
2666                 Node       *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
2667                 TargetEntry *te = tlist_member(groupexpr, sub_tlist);
2668
2669                 if (!te)
2670                         elog(ERROR, "failed to locate grouping columns");
2671                 groupColIdx[keyno++] = te->resno;
2672         }
2673 }
2674
2675 /*
2676  * postprocess_setop_tlist
2677  *        Fix up targetlist returned by plan_set_operations().
2678  *
2679  * We need to transpose sort key info from the orig_tlist into new_tlist.
2680  * NOTE: this would not be good enough if we supported resjunk sort keys
2681  * for results of set operations --- then, we'd need to project a whole
2682  * new tlist to evaluate the resjunk columns.  For now, just ereport if we
2683  * find any resjunk columns in orig_tlist.
2684  */
2685 static List *
2686 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
2687 {
2688         ListCell   *l;
2689         ListCell   *orig_tlist_item = list_head(orig_tlist);
2690
2691         foreach(l, new_tlist)
2692         {
2693                 TargetEntry *new_tle = (TargetEntry *) lfirst(l);
2694                 TargetEntry *orig_tle;
2695
2696                 /* ignore resjunk columns in setop result */
2697                 if (new_tle->resjunk)
2698                         continue;
2699
2700                 Assert(orig_tlist_item != NULL);
2701                 orig_tle = (TargetEntry *) lfirst(orig_tlist_item);
2702                 orig_tlist_item = lnext(orig_tlist_item);
2703                 if (orig_tle->resjunk)  /* should not happen */
2704                         elog(ERROR, "resjunk output columns are not implemented");
2705                 Assert(new_tle->resno == orig_tle->resno);
2706                 new_tle->ressortgroupref = orig_tle->ressortgroupref;
2707         }
2708         if (orig_tlist_item != NULL)
2709                 elog(ERROR, "resjunk output columns are not implemented");
2710         return new_tlist;
2711 }
2712
2713 /*
2714  * select_active_windows
2715  *              Create a list of the "active" window clauses (ie, those referenced
2716  *              by non-deleted WindowFuncs) in the order they are to be executed.
2717  */
2718 static List *
2719 select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
2720 {
2721         List       *result;
2722         List       *actives;
2723         ListCell   *lc;
2724
2725         /* First, make a list of the active windows */
2726         actives = NIL;
2727         foreach(lc, root->parse->windowClause)
2728         {
2729                 WindowClause *wc = (WindowClause *) lfirst(lc);
2730
2731                 /* It's only active if wflists shows some related WindowFuncs */
2732                 Assert(wc->winref <= wflists->maxWinRef);
2733                 if (wflists->windowFuncs[wc->winref] != NIL)
2734                         actives = lappend(actives, wc);
2735         }
2736
2737         /*
2738          * Now, ensure that windows with identical partitioning/ordering clauses
2739          * are adjacent in the list.  This is required by the SQL standard, which
2740          * says that only one sort is to be used for such windows, even if they
2741          * are otherwise distinct (eg, different names or framing clauses).
2742          *
2743          * There is room to be much smarter here, for example detecting whether
2744          * one window's sort keys are a prefix of another's (so that sorting for
2745          * the latter would do for the former), or putting windows first that
2746          * match a sort order available for the underlying query.  For the moment
2747          * we are content with meeting the spec.
2748          */
2749         result = NIL;
2750         while (actives != NIL)
2751         {
2752                 WindowClause *wc = (WindowClause *) linitial(actives);
2753                 ListCell   *prev;
2754                 ListCell   *next;
2755
2756                 /* Move wc from actives to result */
2757                 actives = list_delete_first(actives);
2758                 result = lappend(result, wc);
2759
2760                 /* Now move any matching windows from actives to result */
2761                 prev = NULL;
2762                 for (lc = list_head(actives); lc; lc = next)
2763                 {
2764                         WindowClause *wc2 = (WindowClause *) lfirst(lc);
2765
2766                         next = lnext(lc);
2767                         /* framing options are NOT to be compared here! */
2768                         if (equal(wc->partitionClause, wc2->partitionClause) &&
2769                                 equal(wc->orderClause, wc2->orderClause))
2770                         {
2771                                 actives = list_delete_cell(actives, lc, prev);
2772                                 result = lappend(result, wc2);
2773                         }
2774                         else
2775                                 prev = lc;
2776                 }
2777         }
2778
2779         return result;
2780 }
2781
2782 /*
2783  * add_volatile_sort_exprs
2784  *              Identify any volatile sort/group expressions used by the active
2785  *              windows, and add them to window_tlist if not already present.
2786  *              Return the modified window_tlist.
2787  */
2788 static List *
2789 add_volatile_sort_exprs(List *window_tlist, List *tlist, List *activeWindows)
2790 {
2791         Bitmapset  *sgrefs = NULL;
2792         ListCell   *lc;
2793
2794         /* First, collect the sortgrouprefs of the windows into a bitmapset */
2795         foreach(lc, activeWindows)
2796         {
2797                 WindowClause *wc = (WindowClause *) lfirst(lc);
2798                 ListCell   *lc2;
2799
2800                 foreach(lc2, wc->partitionClause)
2801                 {
2802                         SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
2803
2804                         sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
2805                 }
2806                 foreach(lc2, wc->orderClause)
2807                 {
2808                         SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
2809
2810                         sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
2811                 }
2812         }
2813
2814         /*
2815          * Now scan the original tlist to find the referenced expressions. Any
2816          * that are volatile must be added to window_tlist.
2817          *
2818          * Note: we know that the input window_tlist contains no items marked with
2819          * ressortgrouprefs, so we don't have to worry about collisions of the
2820          * reference numbers.
2821          */
2822         foreach(lc, tlist)
2823         {
2824                 TargetEntry *tle = (TargetEntry *) lfirst(lc);
2825
2826                 if (tle->ressortgroupref != 0 &&
2827                         bms_is_member(tle->ressortgroupref, sgrefs) &&
2828                         contain_volatile_functions((Node *) tle->expr))
2829                 {
2830                         TargetEntry *newtle;
2831
2832                         newtle = makeTargetEntry(tle->expr,
2833                                                                          list_length(window_tlist) + 1,
2834                                                                          NULL,
2835                                                                          false);
2836                         newtle->ressortgroupref = tle->ressortgroupref;
2837                         window_tlist = lappend(window_tlist, newtle);
2838                 }
2839         }
2840
2841         return window_tlist;
2842 }
2843
2844 /*
2845  * make_pathkeys_for_window
2846  *              Create a pathkeys list describing the required input ordering
2847  *              for the given WindowClause.
2848  *
2849  * The required ordering is first the PARTITION keys, then the ORDER keys.
2850  * In the future we might try to implement windowing using hashing, in which
2851  * case the ordering could be relaxed, but for now we always sort.
2852  */
2853 static List *
2854 make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
2855                                                  List *tlist, bool canonicalize)
2856 {
2857         List       *window_pathkeys;
2858         List       *window_sortclauses;
2859
2860         /* Throw error if can't sort */
2861         if (!grouping_is_sortable(wc->partitionClause))
2862                 ereport(ERROR,
2863                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2864                                  errmsg("could not implement window PARTITION BY"),
2865                                  errdetail("Window partitioning columns must be of sortable datatypes.")));
2866         if (!grouping_is_sortable(wc->orderClause))
2867                 ereport(ERROR,
2868                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2869                                  errmsg("could not implement window ORDER BY"),
2870                 errdetail("Window ordering columns must be of sortable datatypes.")));
2871
2872         /* Okay, make the combined pathkeys */
2873         window_sortclauses = list_concat(list_copy(wc->partitionClause),
2874                                                                          list_copy(wc->orderClause));
2875         window_pathkeys = make_pathkeys_for_sortclauses(root,
2876                                                                                                         window_sortclauses,
2877                                                                                                         tlist,
2878                                                                                                         canonicalize);
2879         list_free(window_sortclauses);
2880         return window_pathkeys;
2881 }
2882
2883 /*----------
2884  * get_column_info_for_window
2885  *              Get the partitioning/ordering column numbers and equality operators
2886  *              for a WindowAgg node.
2887  *
2888  * This depends on the behavior of make_pathkeys_for_window()!
2889  *
2890  * We are given the target WindowClause and an array of the input column
2891  * numbers associated with the resulting pathkeys.      In the easy case, there
2892  * are the same number of pathkey columns as partitioning + ordering columns
2893  * and we just have to copy some data around.  However, it's possible that
2894  * some of the original partitioning + ordering columns were eliminated as
2895  * redundant during the transformation to pathkeys.  (This can happen even
2896  * though the parser gets rid of obvious duplicates.  A typical scenario is a
2897  * window specification "PARTITION BY x ORDER BY y" coupled with a clause
2898  * "WHERE x = y" that causes the two sort columns to be recognized as
2899  * redundant.)  In that unusual case, we have to work a lot harder to
2900  * determine which keys are significant.
2901  *
2902  * The method used here is a bit brute-force: add the sort columns to a list
2903  * one at a time and note when the resulting pathkey list gets longer.  But
2904  * it's a sufficiently uncommon case that a faster way doesn't seem worth
2905  * the amount of code refactoring that'd be needed.
2906  *----------
2907  */
2908 static void
2909 get_column_info_for_window(PlannerInfo *root, WindowClause *wc, List *tlist,
2910                                                    int numSortCols, AttrNumber *sortColIdx,
2911                                                    int *partNumCols,
2912                                                    AttrNumber **partColIdx,
2913                                                    Oid **partOperators,
2914                                                    int *ordNumCols,
2915                                                    AttrNumber **ordColIdx,
2916                                                    Oid **ordOperators)
2917 {
2918         int                     numPart = list_length(wc->partitionClause);
2919         int                     numOrder = list_length(wc->orderClause);
2920
2921         if (numSortCols == numPart + numOrder)
2922         {
2923                 /* easy case */
2924                 *partNumCols = numPart;
2925                 *partColIdx = sortColIdx;
2926                 *partOperators = extract_grouping_ops(wc->partitionClause);
2927                 *ordNumCols = numOrder;
2928                 *ordColIdx = sortColIdx + numPart;
2929                 *ordOperators = extract_grouping_ops(wc->orderClause);
2930         }
2931         else
2932         {
2933                 List       *sortclauses;
2934                 List       *pathkeys;
2935                 int                     scidx;
2936                 ListCell   *lc;
2937
2938                 /* first, allocate what's certainly enough space for the arrays */
2939                 *partNumCols = 0;
2940                 *partColIdx = (AttrNumber *) palloc(numPart * sizeof(AttrNumber));
2941                 *partOperators = (Oid *) palloc(numPart * sizeof(Oid));
2942                 *ordNumCols = 0;
2943                 *ordColIdx = (AttrNumber *) palloc(numOrder * sizeof(AttrNumber));
2944                 *ordOperators = (Oid *) palloc(numOrder * sizeof(Oid));
2945                 sortclauses = NIL;
2946                 pathkeys = NIL;
2947                 scidx = 0;
2948                 foreach(lc, wc->partitionClause)
2949                 {
2950                         SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2951                         List       *new_pathkeys;
2952
2953                         sortclauses = lappend(sortclauses, sgc);
2954                         new_pathkeys = make_pathkeys_for_sortclauses(root,
2955                                                                                                                  sortclauses,
2956                                                                                                                  tlist,
2957                                                                                                                  true);
2958                         if (list_length(new_pathkeys) > list_length(pathkeys))
2959                         {
2960                                 /* this sort clause is actually significant */
2961                                 (*partColIdx)[*partNumCols] = sortColIdx[scidx++];
2962                                 (*partOperators)[*partNumCols] = sgc->eqop;
2963                                 (*partNumCols)++;
2964                                 pathkeys = new_pathkeys;
2965                         }
2966                 }
2967                 foreach(lc, wc->orderClause)
2968                 {
2969                         SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2970                         List       *new_pathkeys;
2971
2972                         sortclauses = lappend(sortclauses, sgc);
2973                         new_pathkeys = make_pathkeys_for_sortclauses(root,
2974                                                                                                                  sortclauses,
2975                                                                                                                  tlist,
2976                                                                                                                  true);
2977                         if (list_length(new_pathkeys) > list_length(pathkeys))
2978                         {
2979                                 /* this sort clause is actually significant */
2980                                 (*ordColIdx)[*ordNumCols] = sortColIdx[scidx++];
2981                                 (*ordOperators)[*ordNumCols] = sgc->eqop;
2982                                 (*ordNumCols)++;
2983                                 pathkeys = new_pathkeys;
2984                         }
2985                 }
2986                 /* complain if we didn't eat exactly the right number of sort cols */
2987                 if (scidx != numSortCols)
2988                         elog(ERROR, "failed to deconstruct sort operators into partitioning/ordering operators");
2989         }
2990 }
2991
2992
2993 /*
2994  * expression_planner
2995  *              Perform planner's transformations on a standalone expression.
2996  *
2997  * Various utility commands need to evaluate expressions that are not part
2998  * of a plannable query.  They can do so using the executor's regular
2999  * expression-execution machinery, but first the expression has to be fed
3000  * through here to transform it from parser output to something executable.
3001  *
3002  * Currently, we disallow sublinks in standalone expressions, so there's no
3003  * real "planning" involved here.  (That might not always be true though.)
3004  * What we must do is run eval_const_expressions to ensure that any function
3005  * calls are converted to positional notation and function default arguments
3006  * get inserted.  The fact that constant subexpressions get simplified is a
3007  * side-effect that is useful when the expression will get evaluated more than
3008  * once.  Also, we must fix operator function IDs.
3009  *
3010  * Note: this must not make any damaging changes to the passed-in expression
3011  * tree.  (It would actually be okay to apply fix_opfuncids to it, but since
3012  * we first do an expression_tree_mutator-based walk, what is returned will
3013  * be a new node tree.)
3014  */
3015 Expr *
3016 expression_planner(Expr *expr)
3017 {
3018         Node       *result;
3019
3020         /*
3021          * Convert named-argument function calls, insert default arguments and
3022          * simplify constant subexprs
3023          */
3024         result = eval_const_expressions(NULL, (Node *) expr);
3025
3026         /* Fill in opfuncid values if missing */
3027         fix_opfuncids(result);
3028
3029         return (Expr *) result;
3030 }
3031
3032
3033 /*
3034  * plan_cluster_use_sort
3035  *              Use the planner to decide how CLUSTER should implement sorting
3036  *
3037  * tableOid is the OID of a table to be clustered on its index indexOid
3038  * (which is already known to be a btree index).  Decide whether it's
3039  * cheaper to do an indexscan or a seqscan-plus-sort to execute the CLUSTER.
3040  * Return TRUE to use sorting, FALSE to use an indexscan.
3041  *
3042  * Note: caller had better already hold some type of lock on the table.
3043  */
3044 bool
3045 plan_cluster_use_sort(Oid tableOid, Oid indexOid)
3046 {
3047         PlannerInfo *root;
3048         Query      *query;
3049         PlannerGlobal *glob;
3050         RangeTblEntry *rte;
3051         RelOptInfo *rel;
3052         IndexOptInfo *indexInfo;
3053         QualCost        indexExprCost;
3054         Cost            comparisonCost;
3055         Path       *seqScanPath;
3056         Path            seqScanAndSortPath;
3057         IndexPath  *indexScanPath;
3058         ListCell   *lc;
3059
3060         /* Set up mostly-dummy planner state */
3061         query = makeNode(Query);
3062         query->commandType = CMD_SELECT;
3063
3064         glob = makeNode(PlannerGlobal);
3065
3066         root = makeNode(PlannerInfo);
3067         root->parse = query;
3068         root->glob = glob;
3069         root->query_level = 1;
3070         root->planner_cxt = CurrentMemoryContext;
3071         root->wt_param_id = -1;
3072
3073         /* Build a minimal RTE for the rel */
3074         rte = makeNode(RangeTblEntry);
3075         rte->rtekind = RTE_RELATION;
3076         rte->relid = tableOid;
3077         rte->inh = false;
3078         rte->inFromCl = true;
3079         query->rtable = list_make1(rte);
3080
3081         /* ... and insert it into PlannerInfo */
3082         root->simple_rel_array_size = 2;
3083         root->simple_rel_array = (RelOptInfo **)
3084                 palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));
3085         root->simple_rte_array = (RangeTblEntry **)
3086                 palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *));
3087         root->simple_rte_array[1] = rte;
3088
3089         /* Build RelOptInfo */
3090         rel = build_simple_rel(root, 1, RELOPT_BASEREL);
3091
3092         /*
3093          * Rather than doing all the pushups that would be needed to use
3094          * set_baserel_size_estimates, just do a quick hack for rows and width.
3095          */
3096         rel->rows = rel->tuples;
3097         rel->width = get_relation_data_width(tableOid, NULL);
3098
3099         root->total_table_pages = rel->pages;
3100
3101         /* Locate IndexOptInfo for the target index */
3102         indexInfo = NULL;
3103         foreach(lc, rel->indexlist)
3104         {
3105                 indexInfo = (IndexOptInfo *) lfirst(lc);
3106                 if (indexInfo->indexoid == indexOid)
3107                         break;
3108         }
3109         if (lc == NULL)                         /* not in the list? */
3110                 elog(ERROR, "index %u does not belong to table %u",
3111                          indexOid, tableOid);
3112
3113         /*
3114          * Determine eval cost of the index expressions, if any.  We need to
3115          * charge twice that amount for each tuple comparison that happens
3116          * during the sort, since tuplesort.c will have to re-evaluate the
3117          * index expressions each time.  (XXX that's pretty inefficient...)
3118          */
3119         cost_qual_eval(&indexExprCost, indexInfo->indexprs, root);
3120         comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple);
3121
3122         /* Estimate the cost of seq scan + sort */
3123         seqScanPath = create_seqscan_path(root, rel);
3124         cost_sort(&seqScanAndSortPath, root, NIL,
3125                           seqScanPath->total_cost, rel->tuples, rel->width,
3126                           comparisonCost, maintenance_work_mem, -1.0);
3127
3128         /* Estimate the cost of index scan */
3129         indexScanPath = create_index_path(root, indexInfo,
3130                                                                           NIL, NIL, NIL,
3131                                                                           ForwardScanDirection, NULL);
3132
3133         return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
3134 }