PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
planner.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * planner.c
4  * The query optimizer external interface.
5  *
6  * Portions Copyright (c) 1996-2017, 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 #include <math.h>
20 
21 #include "access/htup_details.h"
22 #include "access/parallel.h"
23 #include "access/sysattr.h"
24 #include "access/xact.h"
26 #include "catalog/pg_proc.h"
27 #include "catalog/pg_type.h"
28 #include "executor/executor.h"
29 #include "executor/nodeAgg.h"
30 #include "foreign/fdwapi.h"
31 #include "miscadmin.h"
32 #include "lib/bipartite_match.h"
33 #include "nodes/makefuncs.h"
34 #include "nodes/nodeFuncs.h"
35 #ifdef OPTIMIZER_DEBUG
36 #include "nodes/print.h"
37 #endif
38 #include "optimizer/clauses.h"
39 #include "optimizer/cost.h"
40 #include "optimizer/pathnode.h"
41 #include "optimizer/paths.h"
42 #include "optimizer/plancat.h"
43 #include "optimizer/planmain.h"
44 #include "optimizer/planner.h"
45 #include "optimizer/prep.h"
46 #include "optimizer/subselect.h"
47 #include "optimizer/tlist.h"
48 #include "optimizer/var.h"
49 #include "parser/analyze.h"
50 #include "parser/parsetree.h"
51 #include "parser/parse_agg.h"
52 #include "rewrite/rewriteManip.h"
53 #include "storage/dsm_impl.h"
54 #include "utils/rel.h"
55 #include "utils/selfuncs.h"
56 #include "utils/lsyscache.h"
57 #include "utils/syscache.h"
58 
59 
60 /* GUC parameters */
63 
64 /* Hook for plugins to get control in planner() */
66 
67 /* Hook for plugins to get control when grouping_planner() plans upper rels */
69 
70 
71 /* Expression kind codes for preprocess_expression */
72 #define EXPRKIND_QUAL 0
73 #define EXPRKIND_TARGET 1
74 #define EXPRKIND_RTFUNC 2
75 #define EXPRKIND_RTFUNC_LATERAL 3
76 #define EXPRKIND_VALUES 4
77 #define EXPRKIND_VALUES_LATERAL 5
78 #define EXPRKIND_LIMIT 6
79 #define EXPRKIND_APPINFO 7
80 #define EXPRKIND_PHV 8
81 #define EXPRKIND_TABLESAMPLE 9
82 #define EXPRKIND_ARBITER_ELEM 10
83 
84 /* Passthrough data for standard_qp_callback */
85 typedef struct
86 {
87  List *tlist; /* preprocessed query targetlist */
88  List *activeWindows; /* active windows, if any */
89  List *groupClause; /* overrides parse->groupClause */
91 
92 /* Local functions */
93 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
94 static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
95 static void inheritance_planner(PlannerInfo *root);
96 static void grouping_planner(PlannerInfo *root, bool inheritance_update,
97  double tuple_fraction);
98 static void preprocess_rowmarks(PlannerInfo *root);
99 static double preprocess_limit(PlannerInfo *root,
100  double tuple_fraction,
101  int64 *offset_est, int64 *count_est);
102 static bool limit_needed(Query *parse);
104 static List *preprocess_groupclause(PlannerInfo *root, List *force);
105 static List *extract_rollup_sets(List *groupingSets);
106 static List *reorder_grouping_sets(List *groupingSets, List *sortclause);
107 static void standard_qp_callback(PlannerInfo *root, void *extra);
108 static double get_number_of_groups(PlannerInfo *root,
109  double path_rows,
110  List *rollup_lists,
111  List *rollup_groupclauses);
113  const AggClauseCosts *agg_costs,
114  double dNumGroups);
116  RelOptInfo *input_rel,
117  PathTarget *target,
118  const AggClauseCosts *agg_costs,
119  List *rollup_lists,
120  List *rollup_groupclauses);
122  RelOptInfo *input_rel,
123  PathTarget *input_target,
124  PathTarget *output_target,
125  List *tlist,
126  WindowFuncLists *wflists,
127  List *activeWindows);
128 static void create_one_window_path(PlannerInfo *root,
129  RelOptInfo *window_rel,
130  Path *path,
131  PathTarget *input_target,
132  PathTarget *output_target,
133  List *tlist,
134  WindowFuncLists *wflists,
135  List *activeWindows);
137  RelOptInfo *input_rel);
139  RelOptInfo *input_rel,
140  PathTarget *target,
141  double limit_tuples);
143  PathTarget *final_target);
145  PathTarget *grouping_target);
146 static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
147 static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
149  PathTarget *final_target,
150  List *activeWindows);
152  List *tlist);
154  PathTarget *final_target,
155  bool *have_postponed_srfs);
156 static void adjust_paths_for_srfs(PlannerInfo *root, RelOptInfo *rel,
157  List *targets, List *targets_contain_srfs);
158 
159 
160 /*****************************************************************************
161  *
162  * Query optimizer entry point
163  *
164  * To support loadable plugins that monitor or modify planner behavior,
165  * we provide a hook variable that lets a plugin get control before and
166  * after the standard planning process. The plugin would normally call
167  * standard_planner().
168  *
169  * Note to plugin authors: standard_planner() scribbles on its Query input,
170  * so you'd better copy that data structure if you want to plan more than once.
171  *
172  *****************************************************************************/
173 PlannedStmt *
174 planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
175 {
176  PlannedStmt *result;
177 
178  if (planner_hook)
179  result = (*planner_hook) (parse, cursorOptions, boundParams);
180  else
181  result = standard_planner(parse, cursorOptions, boundParams);
182  return result;
183 }
184 
185 PlannedStmt *
186 standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
187 {
188  PlannedStmt *result;
189  PlannerGlobal *glob;
190  double tuple_fraction;
191  PlannerInfo *root;
192  RelOptInfo *final_rel;
193  Path *best_path;
194  Plan *top_plan;
195  ListCell *lp,
196  *lr;
197 
198  /*
199  * Set up global state for this planner invocation. This data is needed
200  * across all levels of sub-Query that might exist in the given command,
201  * so we keep it in a separate struct that's linked to by each per-Query
202  * PlannerInfo.
203  */
204  glob = makeNode(PlannerGlobal);
205 
206  glob->boundParams = boundParams;
207  glob->subplans = NIL;
208  glob->subroots = NIL;
209  glob->rewindPlanIDs = NULL;
210  glob->finalrtable = NIL;
211  glob->finalrowmarks = NIL;
212  glob->resultRelations = NIL;
213  glob->relationOids = NIL;
214  glob->invalItems = NIL;
215  glob->nParamExec = 0;
216  glob->lastPHId = 0;
217  glob->lastRowMarkId = 0;
218  glob->lastPlanNodeId = 0;
219  glob->transientPlan = false;
220  glob->dependsOnRole = false;
221 
222  /*
223  * Assess whether it's feasible to use parallel mode for this query. We
224  * can't do this in a standalone backend, or if the command will try to
225  * modify any data, or if this is a cursor operation, or if GUCs are set
226  * to values that don't permit parallelism, or if parallel-unsafe
227  * functions are present in the query tree.
228  *
229  * For now, we don't try to use parallel mode if we're running inside a
230  * parallel worker. We might eventually be able to relax this
231  * restriction, but for now it seems best not to have parallel workers
232  * trying to create their own parallel workers.
233  *
234  * We can't use parallelism in serializable mode because the predicate
235  * locking code is not parallel-aware. It's not catastrophic if someone
236  * tries to run a parallel plan in serializable mode; it just won't get
237  * any workers and will run serially. But it seems like a good heuristic
238  * to assume that the same serialization level will be in effect at plan
239  * time and execution time, so don't generate a parallel plan if we're in
240  * serializable mode.
241  */
242  if ((cursorOptions & CURSOR_OPT_PARALLEL_OK) != 0 &&
245  parse->commandType == CMD_SELECT &&
246  !parse->hasModifyingCTE &&
248  !IsParallelWorker() &&
250  {
251  /* all the cheap tests pass, so scan the query tree */
252  glob->maxParallelHazard = max_parallel_hazard(parse);
254  }
255  else
256  {
257  /* skip the query tree scan, just assume it's unsafe */
259  glob->parallelModeOK = false;
260  }
261 
262  /*
263  * glob->parallelModeNeeded should tell us whether it's necessary to
264  * impose the parallel mode restrictions, but we don't actually want to
265  * impose them unless we choose a parallel plan, so it is normally set
266  * only if a parallel plan is chosen (see create_gather_plan). That way,
267  * people who mislabel their functions but don't use parallelism anyway
268  * aren't harmed. But when force_parallel_mode is set, we enable the
269  * restrictions whenever possible for testing purposes.
270  */
271  glob->parallelModeNeeded = glob->parallelModeOK &&
273 
274  /* Determine what fraction of the plan is likely to be scanned */
275  if (cursorOptions & CURSOR_OPT_FAST_PLAN)
276  {
277  /*
278  * We have no real idea how many tuples the user will ultimately FETCH
279  * from a cursor, but it is often the case that he doesn't want 'em
280  * all, or would prefer a fast-start plan anyway so that he can
281  * process some of the tuples sooner. Use a GUC parameter to decide
282  * what fraction to optimize for.
283  */
284  tuple_fraction = cursor_tuple_fraction;
285 
286  /*
287  * We document cursor_tuple_fraction as simply being a fraction, which
288  * means the edge cases 0 and 1 have to be treated specially here. We
289  * convert 1 to 0 ("all the tuples") and 0 to a very small fraction.
290  */
291  if (tuple_fraction >= 1.0)
292  tuple_fraction = 0.0;
293  else if (tuple_fraction <= 0.0)
294  tuple_fraction = 1e-10;
295  }
296  else
297  {
298  /* Default assumption is we need all the tuples */
299  tuple_fraction = 0.0;
300  }
301 
302  /* primary planning entry point (may recurse for subqueries) */
303  root = subquery_planner(glob, parse, NULL,
304  false, tuple_fraction);
305 
306  /* Select best Path and turn it into a Plan */
307  final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
308  best_path = get_cheapest_fractional_path(final_rel, tuple_fraction);
309 
310  top_plan = create_plan(root, best_path);
311 
312  /*
313  * If creating a plan for a scrollable cursor, make sure it can run
314  * backwards on demand. Add a Material node at the top at need.
315  */
316  if (cursorOptions & CURSOR_OPT_SCROLL)
317  {
318  if (!ExecSupportsBackwardScan(top_plan))
319  top_plan = materialize_finished_plan(top_plan);
320  }
321 
322  /*
323  * Optionally add a Gather node for testing purposes, provided this is
324  * actually a safe thing to do. (Note: we assume adding a Material node
325  * above did not change the parallel safety of the plan, so we can still
326  * rely on best_path->parallel_safe.)
327  */
329  {
330  Gather *gather = makeNode(Gather);
331 
332  gather->plan.targetlist = top_plan->targetlist;
333  gather->plan.qual = NIL;
334  gather->plan.lefttree = top_plan;
335  gather->plan.righttree = NULL;
336  gather->num_workers = 1;
337  gather->single_copy = true;
339 
340  /*
341  * Ideally we'd use cost_gather here, but setting up dummy path data
342  * to satisfy it doesn't seem much cleaner than knowing what it does.
343  */
344  gather->plan.startup_cost = top_plan->startup_cost +
346  gather->plan.total_cost = top_plan->total_cost +
348  gather->plan.plan_rows = top_plan->plan_rows;
349  gather->plan.plan_width = top_plan->plan_width;
350  gather->plan.parallel_aware = false;
351 
352  /* use parallel mode for parallel plans. */
353  root->glob->parallelModeNeeded = true;
354 
355  top_plan = &gather->plan;
356  }
357 
358  /*
359  * If any Params were generated, run through the plan tree and compute
360  * each plan node's extParam/allParam sets. Ideally we'd merge this into
361  * set_plan_references' tree traversal, but for now it has to be separate
362  * because we need to visit subplans before not after main plan.
363  */
364  if (glob->nParamExec > 0)
365  {
366  Assert(list_length(glob->subplans) == list_length(glob->subroots));
367  forboth(lp, glob->subplans, lr, glob->subroots)
368  {
369  Plan *subplan = (Plan *) lfirst(lp);
370  PlannerInfo *subroot = (PlannerInfo *) lfirst(lr);
371 
372  SS_finalize_plan(subroot, subplan);
373  }
374  SS_finalize_plan(root, top_plan);
375  }
376 
377  /* final cleanup of the plan */
378  Assert(glob->finalrtable == NIL);
379  Assert(glob->finalrowmarks == NIL);
380  Assert(glob->resultRelations == NIL);
381  top_plan = set_plan_references(root, top_plan);
382  /* ... and the subplans (both regular subplans and initplans) */
383  Assert(list_length(glob->subplans) == list_length(glob->subroots));
384  forboth(lp, glob->subplans, lr, glob->subroots)
385  {
386  Plan *subplan = (Plan *) lfirst(lp);
387  PlannerInfo *subroot = (PlannerInfo *) lfirst(lr);
388 
389  lfirst(lp) = set_plan_references(subroot, subplan);
390  }
391 
392  /* build the PlannedStmt result */
393  result = makeNode(PlannedStmt);
394 
395  result->commandType = parse->commandType;
396  result->queryId = parse->queryId;
397  result->hasReturning = (parse->returningList != NIL);
398  result->hasModifyingCTE = parse->hasModifyingCTE;
399  result->canSetTag = parse->canSetTag;
400  result->transientPlan = glob->transientPlan;
401  result->dependsOnRole = glob->dependsOnRole;
402  result->parallelModeNeeded = glob->parallelModeNeeded;
403  result->planTree = top_plan;
404  result->rtable = glob->finalrtable;
405  result->resultRelations = glob->resultRelations;
406  result->subplans = glob->subplans;
407  result->rewindPlanIDs = glob->rewindPlanIDs;
408  result->rowMarks = glob->finalrowmarks;
409  result->relationOids = glob->relationOids;
410  result->invalItems = glob->invalItems;
411  result->nParamExec = glob->nParamExec;
412  /* utilityStmt should be null, but we might as well copy it */
413  result->utilityStmt = parse->utilityStmt;
414  result->stmt_location = parse->stmt_location;
415  result->stmt_len = parse->stmt_len;
416 
417  return result;
418 }
419 
420 
421 /*--------------------
422  * subquery_planner
423  * Invokes the planner on a subquery. We recurse to here for each
424  * sub-SELECT found in the query tree.
425  *
426  * glob is the global state for the current planner run.
427  * parse is the querytree produced by the parser & rewriter.
428  * parent_root is the immediate parent Query's info (NULL at the top level).
429  * hasRecursion is true if this is a recursive WITH query.
430  * tuple_fraction is the fraction of tuples we expect will be retrieved.
431  * tuple_fraction is interpreted as explained for grouping_planner, below.
432  *
433  * Basically, this routine does the stuff that should only be done once
434  * per Query object. It then calls grouping_planner. At one time,
435  * grouping_planner could be invoked recursively on the same Query object;
436  * that's not currently true, but we keep the separation between the two
437  * routines anyway, in case we need it again someday.
438  *
439  * subquery_planner will be called recursively to handle sub-Query nodes
440  * found within the query's expressions and rangetable.
441  *
442  * Returns the PlannerInfo struct ("root") that contains all data generated
443  * while planning the subquery. In particular, the Path(s) attached to
444  * the (UPPERREL_FINAL, NULL) upperrel represent our conclusions about the
445  * cheapest way(s) to implement the query. The top level will select the
446  * best Path and pass it through createplan.c to produce a finished Plan.
447  *--------------------
448  */
449 PlannerInfo *
451  PlannerInfo *parent_root,
452  bool hasRecursion, double tuple_fraction)
453 {
454  PlannerInfo *root;
455  List *newWithCheckOptions;
456  List *newHaving;
457  bool hasOuterJoins;
458  RelOptInfo *final_rel;
459  ListCell *l;
460 
461  /* Create a PlannerInfo data structure for this subquery */
462  root = makeNode(PlannerInfo);
463  root->parse = parse;
464  root->glob = glob;
465  root->query_level = parent_root ? parent_root->query_level + 1 : 1;
466  root->parent_root = parent_root;
467  root->plan_params = NIL;
468  root->outer_params = NULL;
470  root->init_plans = NIL;
471  root->cte_plan_ids = NIL;
472  root->multiexpr_params = NIL;
473  root->eq_classes = NIL;
474  root->append_rel_list = NIL;
475  root->rowMarks = NIL;
476  memset(root->upper_rels, 0, sizeof(root->upper_rels));
477  memset(root->upper_targets, 0, sizeof(root->upper_targets));
478  root->processed_tlist = NIL;
479  root->grouping_map = NULL;
480  root->minmax_aggs = NIL;
481  root->qual_security_level = 0;
482  root->hasInheritedTarget = false;
483  root->hasRecursion = hasRecursion;
484  if (hasRecursion)
485  root->wt_param_id = SS_assign_special_param(root);
486  else
487  root->wt_param_id = -1;
488  root->non_recursive_path = NULL;
489 
490  /*
491  * If there is a WITH list, process each WITH query and build an initplan
492  * SubPlan structure for it.
493  */
494  if (parse->cteList)
495  SS_process_ctes(root);
496 
497  /*
498  * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
499  * to transform them into joins. Note that this step does not descend
500  * into subqueries; if we pull up any subqueries below, their SubLinks are
501  * processed just before pulling them up.
502  */
503  if (parse->hasSubLinks)
504  pull_up_sublinks(root);
505 
506  /*
507  * Scan the rangetable for set-returning functions, and inline them if
508  * possible (producing subqueries that might get pulled up next).
509  * Recursion issues here are handled in the same way as for SubLinks.
510  */
512 
513  /*
514  * Check to see if any subqueries in the jointree can be merged into this
515  * query.
516  */
517  pull_up_subqueries(root);
518 
519  /*
520  * If this is a simple UNION ALL query, flatten it into an appendrel. We
521  * do this now because it requires applying pull_up_subqueries to the leaf
522  * queries of the UNION ALL, which weren't touched above because they
523  * weren't referenced by the jointree (they will be after we do this).
524  */
525  if (parse->setOperations)
527 
528  /*
529  * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
530  * avoid the expense of doing flatten_join_alias_vars(). Also check for
531  * outer joins --- if none, we can skip reduce_outer_joins(). And check
532  * for LATERAL RTEs, too. This must be done after we have done
533  * pull_up_subqueries(), of course.
534  */
535  root->hasJoinRTEs = false;
536  root->hasLateralRTEs = false;
537  hasOuterJoins = false;
538  foreach(l, parse->rtable)
539  {
540  RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
541 
542  if (rte->rtekind == RTE_JOIN)
543  {
544  root->hasJoinRTEs = true;
545  if (IS_OUTER_JOIN(rte->jointype))
546  hasOuterJoins = true;
547  }
548  if (rte->lateral)
549  root->hasLateralRTEs = true;
550  }
551 
552  /*
553  * Preprocess RowMark information. We need to do this after subquery
554  * pullup (so that all non-inherited RTEs are present) and before
555  * inheritance expansion (so that the info is available for
556  * expand_inherited_tables to examine and modify).
557  */
558  preprocess_rowmarks(root);
559 
560  /*
561  * Expand any rangetable entries that are inheritance sets into "append
562  * relations". This can add entries to the rangetable, but they must be
563  * plain base relations not joins, so it's OK (and marginally more
564  * efficient) to do it after checking for join RTEs. We must do it after
565  * pulling up subqueries, else we'd fail to handle inherited tables in
566  * subqueries.
567  */
569 
570  /*
571  * Set hasHavingQual to remember if HAVING clause is present. Needed
572  * because preprocess_expression will reduce a constant-true condition to
573  * an empty qual list ... but "HAVING TRUE" is not a semantic no-op.
574  */
575  root->hasHavingQual = (parse->havingQual != NULL);
576 
577  /* Clear this flag; might get set in distribute_qual_to_rels */
578  root->hasPseudoConstantQuals = false;
579 
580  /*
581  * Do expression preprocessing on targetlist and quals, as well as other
582  * random expressions in the querytree. Note that we do not need to
583  * handle sort/group expressions explicitly, because they are actually
584  * part of the targetlist.
585  */
586  parse->targetList = (List *)
587  preprocess_expression(root, (Node *) parse->targetList,
589 
590  /* Constant-folding might have removed all set-returning functions */
591  if (parse->hasTargetSRFs)
593 
594  newWithCheckOptions = NIL;
595  foreach(l, parse->withCheckOptions)
596  {
597  WithCheckOption *wco = (WithCheckOption *) lfirst(l);
598 
599  wco->qual = preprocess_expression(root, wco->qual,
600  EXPRKIND_QUAL);
601  if (wco->qual != NULL)
602  newWithCheckOptions = lappend(newWithCheckOptions, wco);
603  }
604  parse->withCheckOptions = newWithCheckOptions;
605 
606  parse->returningList = (List *)
607  preprocess_expression(root, (Node *) parse->returningList,
609 
610  preprocess_qual_conditions(root, (Node *) parse->jointree);
611 
612  parse->havingQual = preprocess_expression(root, parse->havingQual,
613  EXPRKIND_QUAL);
614 
615  foreach(l, parse->windowClause)
616  {
617  WindowClause *wc = (WindowClause *) lfirst(l);
618 
619  /* partitionClause/orderClause are sort/group expressions */
622  wc->endOffset = preprocess_expression(root, wc->endOffset,
624  }
625 
626  parse->limitOffset = preprocess_expression(root, parse->limitOffset,
628  parse->limitCount = preprocess_expression(root, parse->limitCount,
630 
631  if (parse->onConflict)
632  {
633  parse->onConflict->arbiterElems = (List *)
635  (Node *) parse->onConflict->arbiterElems,
637  parse->onConflict->arbiterWhere =
639  parse->onConflict->arbiterWhere,
640  EXPRKIND_QUAL);
641  parse->onConflict->onConflictSet = (List *)
643  (Node *) parse->onConflict->onConflictSet,
645  parse->onConflict->onConflictWhere =
647  parse->onConflict->onConflictWhere,
648  EXPRKIND_QUAL);
649  /* exclRelTlist contains only Vars, so no preprocessing needed */
650  }
651 
652  root->append_rel_list = (List *)
655 
656  /* Also need to preprocess expressions within RTEs */
657  foreach(l, parse->rtable)
658  {
659  RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
660  int kind;
661  ListCell *lcsq;
662 
663  if (rte->rtekind == RTE_RELATION)
664  {
665  if (rte->tablesample)
666  rte->tablesample = (TableSampleClause *)
668  (Node *) rte->tablesample,
670  }
671  else if (rte->rtekind == RTE_SUBQUERY)
672  {
673  /*
674  * We don't want to do all preprocessing yet on the subquery's
675  * expressions, since that will happen when we plan it. But if it
676  * contains any join aliases of our level, those have to get
677  * expanded now, because planning of the subquery won't do it.
678  * That's only possible if the subquery is LATERAL.
679  */
680  if (rte->lateral && root->hasJoinRTEs)
681  rte->subquery = (Query *)
682  flatten_join_alias_vars(root, (Node *) rte->subquery);
683  }
684  else if (rte->rtekind == RTE_FUNCTION)
685  {
686  /* Preprocess the function expression(s) fully */
688  rte->functions = (List *) preprocess_expression(root, (Node *) rte->functions, kind);
689  }
690  else if (rte->rtekind == RTE_VALUES)
691  {
692  /* Preprocess the values lists fully */
694  rte->values_lists = (List *)
695  preprocess_expression(root, (Node *) rte->values_lists, kind);
696  }
697 
698  /*
699  * Process each element of the securityQuals list as if it were a
700  * separate qual expression (as indeed it is). We need to do it this
701  * way to get proper canonicalization of AND/OR structure. Note that
702  * this converts each element into an implicit-AND sublist.
703  */
704  foreach(lcsq, rte->securityQuals)
705  {
706  lfirst(lcsq) = preprocess_expression(root,
707  (Node *) lfirst(lcsq),
708  EXPRKIND_QUAL);
709  }
710  }
711 
712  /*
713  * In some cases we may want to transfer a HAVING clause into WHERE. We
714  * cannot do so if the HAVING clause contains aggregates (obviously) or
715  * volatile functions (since a HAVING clause is supposed to be executed
716  * only once per group). We also can't do this if there are any nonempty
717  * grouping sets; moving such a clause into WHERE would potentially change
718  * the results, if any referenced column isn't present in all the grouping
719  * sets. (If there are only empty grouping sets, then the HAVING clause
720  * must be degenerate as discussed below.)
721  *
722  * Also, it may be that the clause is so expensive to execute that we're
723  * better off doing it only once per group, despite the loss of
724  * selectivity. This is hard to estimate short of doing the entire
725  * planning process twice, so we use a heuristic: clauses containing
726  * subplans are left in HAVING. Otherwise, we move or copy the HAVING
727  * clause into WHERE, in hopes of eliminating tuples before aggregation
728  * instead of after.
729  *
730  * If the query has explicit grouping then we can simply move such a
731  * clause into WHERE; any group that fails the clause will not be in the
732  * output because none of its tuples will reach the grouping or
733  * aggregation stage. Otherwise we must have a degenerate (variable-free)
734  * HAVING clause, which we put in WHERE so that query_planner() can use it
735  * in a gating Result node, but also keep in HAVING to ensure that we
736  * don't emit a bogus aggregated row. (This could be done better, but it
737  * seems not worth optimizing.)
738  *
739  * Note that both havingQual and parse->jointree->quals are in
740  * implicitly-ANDed-list form at this point, even though they are declared
741  * as Node *.
742  */
743  newHaving = NIL;
744  foreach(l, (List *) parse->havingQual)
745  {
746  Node *havingclause = (Node *) lfirst(l);
747 
748  if ((parse->groupClause && parse->groupingSets) ||
749  contain_agg_clause(havingclause) ||
750  contain_volatile_functions(havingclause) ||
751  contain_subplans(havingclause))
752  {
753  /* keep it in HAVING */
754  newHaving = lappend(newHaving, havingclause);
755  }
756  else if (parse->groupClause && !parse->groupingSets)
757  {
758  /* move it to WHERE */
759  parse->jointree->quals = (Node *)
760  lappend((List *) parse->jointree->quals, havingclause);
761  }
762  else
763  {
764  /* put a copy in WHERE, keep it in HAVING */
765  parse->jointree->quals = (Node *)
766  lappend((List *) parse->jointree->quals,
767  copyObject(havingclause));
768  newHaving = lappend(newHaving, havingclause);
769  }
770  }
771  parse->havingQual = (Node *) newHaving;
772 
773  /* Remove any redundant GROUP BY columns */
775 
776  /*
777  * If we have any outer joins, try to reduce them to plain inner joins.
778  * This step is most easily done after we've done expression
779  * preprocessing.
780  */
781  if (hasOuterJoins)
782  reduce_outer_joins(root);
783 
784  /*
785  * Do the main planning. If we have an inherited target relation, that
786  * needs special processing, else go straight to grouping_planner.
787  */
788  if (parse->resultRelation &&
789  rt_fetch(parse->resultRelation, parse->rtable)->inh)
790  inheritance_planner(root);
791  else
792  grouping_planner(root, false, tuple_fraction);
793 
794  /*
795  * Capture the set of outer-level param IDs we have access to, for use in
796  * extParam/allParam calculations later.
797  */
799 
800  /*
801  * If any initPlans were created in this query level, adjust the surviving
802  * Paths' costs and parallel-safety flags to account for them. The
803  * initPlans won't actually get attached to the plan tree till
804  * create_plan() runs, but we must include their effects now.
805  */
806  final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
807  SS_charge_for_initplans(root, final_rel);
808 
809  /*
810  * Make sure we've identified the cheapest Path for the final rel. (By
811  * doing this here not in grouping_planner, we include initPlan costs in
812  * the decision, though it's unlikely that will change anything.)
813  */
814  set_cheapest(final_rel);
815 
816  return root;
817 }
818 
819 /*
820  * preprocess_expression
821  * Do subquery_planner's preprocessing work for an expression,
822  * which can be a targetlist, a WHERE clause (including JOIN/ON
823  * conditions), a HAVING clause, or a few other things.
824  */
825 static Node *
826 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
827 {
828  /*
829  * Fall out quickly if expression is empty. This occurs often enough to
830  * be worth checking. Note that null->null is the correct conversion for
831  * implicit-AND result format, too.
832  */
833  if (expr == NULL)
834  return NULL;
835 
836  /*
837  * If the query has any join RTEs, replace join alias variables with
838  * base-relation variables. We must do this before sublink processing,
839  * else sublinks expanded out from join aliases would not get processed.
840  * We can skip it in non-lateral RTE functions, VALUES lists, and
841  * TABLESAMPLE clauses, however, since they can't contain any Vars of the
842  * current query level.
843  */
844  if (root->hasJoinRTEs &&
845  !(kind == EXPRKIND_RTFUNC ||
846  kind == EXPRKIND_VALUES ||
847  kind == EXPRKIND_TABLESAMPLE))
848  expr = flatten_join_alias_vars(root, expr);
849 
850  /*
851  * Simplify constant expressions.
852  *
853  * Note: an essential effect of this is to convert named-argument function
854  * calls to positional notation and insert the current actual values of
855  * any default arguments for functions. To ensure that happens, we *must*
856  * process all expressions here. Previous PG versions sometimes skipped
857  * const-simplification if it didn't seem worth the trouble, but we can't
858  * do that anymore.
859  *
860  * Note: this also flattens nested AND and OR expressions into N-argument
861  * form. All processing of a qual expression after this point must be
862  * careful to maintain AND/OR flatness --- that is, do not generate a tree
863  * with AND directly under AND, nor OR directly under OR.
864  */
865  expr = eval_const_expressions(root, expr);
866 
867  /*
868  * If it's a qual or havingQual, canonicalize it.
869  */
870  if (kind == EXPRKIND_QUAL)
871  {
872  expr = (Node *) canonicalize_qual((Expr *) expr);
873 
874 #ifdef OPTIMIZER_DEBUG
875  printf("After canonicalize_qual()\n");
876  pprint(expr);
877 #endif
878  }
879 
880  /* Expand SubLinks to SubPlans */
881  if (root->parse->hasSubLinks)
882  expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));
883 
884  /*
885  * XXX do not insert anything here unless you have grokked the comments in
886  * SS_replace_correlation_vars ...
887  */
888 
889  /* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
890  if (root->query_level > 1)
891  expr = SS_replace_correlation_vars(root, expr);
892 
893  /*
894  * If it's a qual or havingQual, convert it to implicit-AND format. (We
895  * don't want to do this before eval_const_expressions, since the latter
896  * would be unable to simplify a top-level AND correctly. Also,
897  * SS_process_sublinks expects explicit-AND format.)
898  */
899  if (kind == EXPRKIND_QUAL)
900  expr = (Node *) make_ands_implicit((Expr *) expr);
901 
902  return expr;
903 }
904 
905 /*
906  * preprocess_qual_conditions
907  * Recursively scan the query's jointree and do subquery_planner's
908  * preprocessing work on each qual condition found therein.
909  */
910 static void
912 {
913  if (jtnode == NULL)
914  return;
915  if (IsA(jtnode, RangeTblRef))
916  {
917  /* nothing to do here */
918  }
919  else if (IsA(jtnode, FromExpr))
920  {
921  FromExpr *f = (FromExpr *) jtnode;
922  ListCell *l;
923 
924  foreach(l, f->fromlist)
926 
928  }
929  else if (IsA(jtnode, JoinExpr))
930  {
931  JoinExpr *j = (JoinExpr *) jtnode;
932 
935 
937  }
938  else
939  elog(ERROR, "unrecognized node type: %d",
940  (int) nodeTag(jtnode));
941 }
942 
943 /*
944  * preprocess_phv_expression
945  * Do preprocessing on a PlaceHolderVar expression that's been pulled up.
946  *
947  * If a LATERAL subquery references an output of another subquery, and that
948  * output must be wrapped in a PlaceHolderVar because of an intermediate outer
949  * join, then we'll push the PlaceHolderVar expression down into the subquery
950  * and later pull it back up during find_lateral_references, which runs after
951  * subquery_planner has preprocessed all the expressions that were in the
952  * current query level to start with. So we need to preprocess it then.
953  */
954 Expr *
956 {
957  return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
958 }
959 
960 /*
961  * inheritance_planner
962  * Generate Paths in the case where the result relation is an
963  * inheritance set.
964  *
965  * We have to handle this case differently from cases where a source relation
966  * is an inheritance set. Source inheritance is expanded at the bottom of the
967  * plan tree (see allpaths.c), but target inheritance has to be expanded at
968  * the top. The reason is that for UPDATE, each target relation needs a
969  * different targetlist matching its own column set. Fortunately,
970  * the UPDATE/DELETE target can never be the nullable side of an outer join,
971  * so it's OK to generate the plan this way.
972  *
973  * Returns nothing; the useful output is in the Paths we attach to
974  * the (UPPERREL_FINAL, NULL) upperrel stored in *root.
975  *
976  * Note that we have not done set_cheapest() on the final rel; it's convenient
977  * to leave this to the caller.
978  */
979 static void
981 {
982  Query *parse = root->parse;
983  int parentRTindex = parse->resultRelation;
984  Bitmapset *subqueryRTindexes;
985  Bitmapset *modifiableARIindexes;
986  int nominalRelation = -1;
987  List *final_rtable = NIL;
988  int save_rel_array_size = 0;
989  RelOptInfo **save_rel_array = NULL;
990  List *subpaths = NIL;
991  List *subroots = NIL;
992  List *resultRelations = NIL;
993  List *withCheckOptionLists = NIL;
994  List *returningLists = NIL;
995  List *rowMarks;
996  RelOptInfo *final_rel;
997  ListCell *lc;
998  Index rti;
999 
1000  Assert(parse->commandType != CMD_INSERT);
1001 
1002  /*
1003  * We generate a modified instance of the original Query for each target
1004  * relation, plan that, and put all the plans into a list that will be
1005  * controlled by a single ModifyTable node. All the instances share the
1006  * same rangetable, but each instance must have its own set of subquery
1007  * RTEs within the finished rangetable because (1) they are likely to get
1008  * scribbled on during planning, and (2) it's not inconceivable that
1009  * subqueries could get planned differently in different cases. We need
1010  * not create duplicate copies of other RTE kinds, in particular not the
1011  * target relations, because they don't have either of those issues. Not
1012  * having to duplicate the target relations is important because doing so
1013  * (1) would result in a rangetable of length O(N^2) for N targets, with
1014  * at least O(N^3) work expended here; and (2) would greatly complicate
1015  * management of the rowMarks list.
1016  *
1017  * To begin with, generate a bitmapset of the relids of the subquery RTEs.
1018  */
1019  subqueryRTindexes = NULL;
1020  rti = 1;
1021  foreach(lc, parse->rtable)
1022  {
1023  RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
1024 
1025  if (rte->rtekind == RTE_SUBQUERY)
1026  subqueryRTindexes = bms_add_member(subqueryRTindexes, rti);
1027  rti++;
1028  }
1029 
1030  /*
1031  * Next, we want to identify which AppendRelInfo items contain references
1032  * to any of the aforesaid subquery RTEs. These items will need to be
1033  * copied and modified to adjust their subquery references; whereas the
1034  * other ones need not be touched. It's worth being tense over this
1035  * because we can usually avoid processing most of the AppendRelInfo
1036  * items, thereby saving O(N^2) space and time when the target is a large
1037  * inheritance tree. We can identify AppendRelInfo items by their
1038  * child_relid, since that should be unique within the list.
1039  */
1040  modifiableARIindexes = NULL;
1041  if (subqueryRTindexes != NULL)
1042  {
1043  foreach(lc, root->append_rel_list)
1044  {
1045  AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
1046 
1047  if (bms_is_member(appinfo->parent_relid, subqueryRTindexes) ||
1048  bms_is_member(appinfo->child_relid, subqueryRTindexes) ||
1050  subqueryRTindexes))
1051  modifiableARIindexes = bms_add_member(modifiableARIindexes,
1052  appinfo->child_relid);
1053  }
1054  }
1055 
1056  /*
1057  * And now we can get on with generating a plan for each child table.
1058  */
1059  foreach(lc, root->append_rel_list)
1060  {
1061  AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
1062  PlannerInfo *subroot;
1063  RangeTblEntry *parent_rte;
1064  RangeTblEntry *child_rte;
1065  RelOptInfo *sub_final_rel;
1066  Path *subpath;
1067 
1068  /* append_rel_list contains all append rels; ignore others */
1069  if (appinfo->parent_relid != parentRTindex)
1070  continue;
1071 
1072  /*
1073  * We need a working copy of the PlannerInfo so that we can control
1074  * propagation of information back to the main copy.
1075  */
1076  subroot = makeNode(PlannerInfo);
1077  memcpy(subroot, root, sizeof(PlannerInfo));
1078 
1079  /*
1080  * Generate modified query with this rel as target. We first apply
1081  * adjust_appendrel_attrs, which copies the Query and changes
1082  * references to the parent RTE to refer to the current child RTE,
1083  * then fool around with subquery RTEs.
1084  */
1085  subroot->parse = (Query *)
1087  (Node *) parse,
1088  appinfo);
1089 
1090  /*
1091  * If there are securityQuals attached to the parent, move them to the
1092  * child rel (they've already been transformed properly for that).
1093  */
1094  parent_rte = rt_fetch(parentRTindex, subroot->parse->rtable);
1095  child_rte = rt_fetch(appinfo->child_relid, subroot->parse->rtable);
1096  child_rte->securityQuals = parent_rte->securityQuals;
1097  parent_rte->securityQuals = NIL;
1098 
1099  /*
1100  * The rowMarks list might contain references to subquery RTEs, so
1101  * make a copy that we can apply ChangeVarNodes to. (Fortunately, the
1102  * executor doesn't need to see the modified copies --- we can just
1103  * pass it the original rowMarks list.)
1104  */
1105  subroot->rowMarks = (List *) copyObject(root->rowMarks);
1106 
1107  /*
1108  * The append_rel_list likewise might contain references to subquery
1109  * RTEs (if any subqueries were flattenable UNION ALLs). So prepare
1110  * to apply ChangeVarNodes to that, too. As explained above, we only
1111  * want to copy items that actually contain such references; the rest
1112  * can just get linked into the subroot's append_rel_list.
1113  *
1114  * If we know there are no such references, we can just use the outer
1115  * append_rel_list unmodified.
1116  */
1117  if (modifiableARIindexes != NULL)
1118  {
1119  ListCell *lc2;
1120 
1121  subroot->append_rel_list = NIL;
1122  foreach(lc2, root->append_rel_list)
1123  {
1124  AppendRelInfo *appinfo2 = (AppendRelInfo *) lfirst(lc2);
1125 
1126  if (bms_is_member(appinfo2->child_relid, modifiableARIindexes))
1127  appinfo2 = (AppendRelInfo *) copyObject(appinfo2);
1128 
1129  subroot->append_rel_list = lappend(subroot->append_rel_list,
1130  appinfo2);
1131  }
1132  }
1133 
1134  /*
1135  * Add placeholders to the child Query's rangetable list to fill the
1136  * RT indexes already reserved for subqueries in previous children.
1137  * These won't be referenced, so there's no need to make them very
1138  * valid-looking.
1139  */
1140  while (list_length(subroot->parse->rtable) < list_length(final_rtable))
1141  subroot->parse->rtable = lappend(subroot->parse->rtable,
1143 
1144  /*
1145  * If this isn't the first child Query, generate duplicates of all
1146  * subquery RTEs, and adjust Var numbering to reference the
1147  * duplicates. To simplify the loop logic, we scan the original rtable
1148  * not the copy just made by adjust_appendrel_attrs; that should be OK
1149  * since subquery RTEs couldn't contain any references to the target
1150  * rel.
1151  */
1152  if (final_rtable != NIL && subqueryRTindexes != NULL)
1153  {
1154  ListCell *lr;
1155 
1156  rti = 1;
1157  foreach(lr, parse->rtable)
1158  {
1159  RangeTblEntry *rte = (RangeTblEntry *) lfirst(lr);
1160 
1161  if (bms_is_member(rti, subqueryRTindexes))
1162  {
1163  Index newrti;
1164 
1165  /*
1166  * The RTE can't contain any references to its own RT
1167  * index, except in its securityQuals, so we can save a
1168  * few cycles by applying ChangeVarNodes to the rest of
1169  * the rangetable before we append the RTE to it.
1170  */
1171  newrti = list_length(subroot->parse->rtable) + 1;
1172  ChangeVarNodes((Node *) subroot->parse, rti, newrti, 0);
1173  ChangeVarNodes((Node *) subroot->rowMarks, rti, newrti, 0);
1174  /* Skip processing unchanging parts of append_rel_list */
1175  if (modifiableARIindexes != NULL)
1176  {
1177  ListCell *lc2;
1178 
1179  foreach(lc2, subroot->append_rel_list)
1180  {
1181  AppendRelInfo *appinfo2 = (AppendRelInfo *) lfirst(lc2);
1182 
1183  if (bms_is_member(appinfo2->child_relid,
1184  modifiableARIindexes))
1185  ChangeVarNodes((Node *) appinfo2, rti, newrti, 0);
1186  }
1187  }
1188  rte = copyObject(rte);
1189  ChangeVarNodes((Node *) rte->securityQuals, rti, newrti, 0);
1190  subroot->parse->rtable = lappend(subroot->parse->rtable,
1191  rte);
1192  }
1193  rti++;
1194  }
1195  }
1196 
1197  /* There shouldn't be any OJ info to translate, as yet */
1198  Assert(subroot->join_info_list == NIL);
1199  /* and we haven't created PlaceHolderInfos, either */
1200  Assert(subroot->placeholder_list == NIL);
1201  /* hack to mark target relation as an inheritance partition */
1202  subroot->hasInheritedTarget = true;
1203 
1204  /* Generate Path(s) for accessing this result relation */
1205  grouping_planner(subroot, true, 0.0 /* retrieve all tuples */ );
1206 
1207  /*
1208  * We'll use the first child relation (even if it's excluded) as the
1209  * nominal target relation of the ModifyTable node. Because of the
1210  * way expand_inherited_rtentry works, this should always be the RTE
1211  * representing the parent table in its role as a simple member of the
1212  * inheritance set. (It would be logically cleaner to use the
1213  * inheritance parent RTE as the nominal target; but since that RTE
1214  * will not be otherwise referenced in the plan, doing so would give
1215  * rise to confusing use of multiple aliases in EXPLAIN output for
1216  * what the user will think is the "same" table.)
1217  */
1218  if (nominalRelation < 0)
1219  nominalRelation = appinfo->child_relid;
1220 
1221  /*
1222  * Select cheapest path in case there's more than one. We always run
1223  * modification queries to conclusion, so we care only for the
1224  * cheapest-total path.
1225  */
1226  sub_final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
1227  set_cheapest(sub_final_rel);
1228  subpath = sub_final_rel->cheapest_total_path;
1229 
1230  /*
1231  * If this child rel was excluded by constraint exclusion, exclude it
1232  * from the result plan.
1233  */
1234  if (IS_DUMMY_PATH(subpath))
1235  continue;
1236 
1237  /*
1238  * If this is the first non-excluded child, its post-planning rtable
1239  * becomes the initial contents of final_rtable; otherwise, append
1240  * just its modified subquery RTEs to final_rtable.
1241  */
1242  if (final_rtable == NIL)
1243  final_rtable = subroot->parse->rtable;
1244  else
1245  final_rtable = list_concat(final_rtable,
1246  list_copy_tail(subroot->parse->rtable,
1247  list_length(final_rtable)));
1248 
1249  /*
1250  * We need to collect all the RelOptInfos from all child plans into
1251  * the main PlannerInfo, since setrefs.c will need them. We use the
1252  * last child's simple_rel_array (previous ones are too short), so we
1253  * have to propagate forward the RelOptInfos that were already built
1254  * in previous children.
1255  */
1256  Assert(subroot->simple_rel_array_size >= save_rel_array_size);
1257  for (rti = 1; rti < save_rel_array_size; rti++)
1258  {
1259  RelOptInfo *brel = save_rel_array[rti];
1260 
1261  if (brel)
1262  subroot->simple_rel_array[rti] = brel;
1263  }
1264  save_rel_array_size = subroot->simple_rel_array_size;
1265  save_rel_array = subroot->simple_rel_array;
1266 
1267  /* Make sure any initplans from this rel get into the outer list */
1268  root->init_plans = subroot->init_plans;
1269 
1270  /* Build list of sub-paths */
1271  subpaths = lappend(subpaths, subpath);
1272 
1273  /* Build list of modified subroots, too */
1274  subroots = lappend(subroots, subroot);
1275 
1276  /* Build list of target-relation RT indexes */
1277  resultRelations = lappend_int(resultRelations, appinfo->child_relid);
1278 
1279  /* Build lists of per-relation WCO and RETURNING targetlists */
1280  if (parse->withCheckOptions)
1281  withCheckOptionLists = lappend(withCheckOptionLists,
1282  subroot->parse->withCheckOptions);
1283  if (parse->returningList)
1284  returningLists = lappend(returningLists,
1285  subroot->parse->returningList);
1286 
1287  Assert(!parse->onConflict);
1288  }
1289 
1290  /* Result path must go into outer query's FINAL upperrel */
1291  final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
1292 
1293  /*
1294  * We don't currently worry about setting final_rel's consider_parallel
1295  * flag in this case, nor about allowing FDWs or create_upper_paths_hook
1296  * to get control here.
1297  */
1298 
1299  /*
1300  * If we managed to exclude every child rel, return a dummy plan; it
1301  * doesn't even need a ModifyTable node.
1302  */
1303  if (subpaths == NIL)
1304  {
1305  set_dummy_rel_pathlist(final_rel);
1306  return;
1307  }
1308 
1309  /*
1310  * Put back the final adjusted rtable into the master copy of the Query.
1311  * (We mustn't do this if we found no non-excluded children.)
1312  */
1313  parse->rtable = final_rtable;
1314  root->simple_rel_array_size = save_rel_array_size;
1315  root->simple_rel_array = save_rel_array;
1316  /* Must reconstruct master's simple_rte_array, too */
1317  root->simple_rte_array = (RangeTblEntry **)
1318  palloc0((list_length(final_rtable) + 1) * sizeof(RangeTblEntry *));
1319  rti = 1;
1320  foreach(lc, final_rtable)
1321  {
1322  RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
1323 
1324  root->simple_rte_array[rti++] = rte;
1325  }
1326 
1327  /*
1328  * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node will
1329  * have dealt with fetching non-locked marked rows, else we need to have
1330  * ModifyTable do that.
1331  */
1332  if (parse->rowMarks)
1333  rowMarks = NIL;
1334  else
1335  rowMarks = root->rowMarks;
1336 
1337  /* Create Path representing a ModifyTable to do the UPDATE/DELETE work */
1338  add_path(final_rel, (Path *)
1339  create_modifytable_path(root, final_rel,
1340  parse->commandType,
1341  parse->canSetTag,
1342  nominalRelation,
1343  resultRelations,
1344  subpaths,
1345  subroots,
1346  withCheckOptionLists,
1347  returningLists,
1348  rowMarks,
1349  NULL,
1350  SS_assign_special_param(root)));
1351 }
1352 
1353 /*--------------------
1354  * grouping_planner
1355  * Perform planning steps related to grouping, aggregation, etc.
1356  *
1357  * This function adds all required top-level processing to the scan/join
1358  * Path(s) produced by query_planner.
1359  *
1360  * If inheritance_update is true, we're being called from inheritance_planner
1361  * and should not include a ModifyTable step in the resulting Path(s).
1362  * (inheritance_planner will create a single ModifyTable node covering all the
1363  * target tables.)
1364  *
1365  * tuple_fraction is the fraction of tuples we expect will be retrieved.
1366  * tuple_fraction is interpreted as follows:
1367  * 0: expect all tuples to be retrieved (normal case)
1368  * 0 < tuple_fraction < 1: expect the given fraction of tuples available
1369  * from the plan to be retrieved
1370  * tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
1371  * expected to be retrieved (ie, a LIMIT specification)
1372  *
1373  * Returns nothing; the useful output is in the Paths we attach to the
1374  * (UPPERREL_FINAL, NULL) upperrel in *root. In addition,
1375  * root->processed_tlist contains the final processed targetlist.
1376  *
1377  * Note that we have not done set_cheapest() on the final rel; it's convenient
1378  * to leave this to the caller.
1379  *--------------------
1380  */
1381 static void
1382 grouping_planner(PlannerInfo *root, bool inheritance_update,
1383  double tuple_fraction)
1384 {
1385  Query *parse = root->parse;
1386  List *tlist = parse->targetList;
1387  int64 offset_est = 0;
1388  int64 count_est = 0;
1389  double limit_tuples = -1.0;
1390  bool have_postponed_srfs = false;
1391  PathTarget *final_target;
1392  List *final_targets;
1393  List *final_targets_contain_srfs;
1394  RelOptInfo *current_rel;
1395  RelOptInfo *final_rel;
1396  ListCell *lc;
1397 
1398  /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
1399  if (parse->limitCount || parse->limitOffset)
1400  {
1401  tuple_fraction = preprocess_limit(root, tuple_fraction,
1402  &offset_est, &count_est);
1403 
1404  /*
1405  * If we have a known LIMIT, and don't have an unknown OFFSET, we can
1406  * estimate the effects of using a bounded sort.
1407  */
1408  if (count_est > 0 && offset_est >= 0)
1409  limit_tuples = (double) count_est + (double) offset_est;
1410  }
1411 
1412  /* Make tuple_fraction accessible to lower-level routines */
1413  root->tuple_fraction = tuple_fraction;
1414 
1415  if (parse->setOperations)
1416  {
1417  /*
1418  * If there's a top-level ORDER BY, assume we have to fetch all the
1419  * tuples. This might be too simplistic given all the hackery below
1420  * to possibly avoid the sort; but the odds of accurate estimates here
1421  * are pretty low anyway. XXX try to get rid of this in favor of
1422  * letting plan_set_operations generate both fast-start and
1423  * cheapest-total paths.
1424  */
1425  if (parse->sortClause)
1426  root->tuple_fraction = 0.0;
1427 
1428  /*
1429  * Construct Paths for set operations. The results will not need any
1430  * work except perhaps a top-level sort and/or LIMIT. Note that any
1431  * special work for recursive unions is the responsibility of
1432  * plan_set_operations.
1433  */
1434  current_rel = plan_set_operations(root);
1435 
1436  /*
1437  * We should not need to call preprocess_targetlist, since we must be
1438  * in a SELECT query node. Instead, use the targetlist returned by
1439  * plan_set_operations (since this tells whether it returned any
1440  * resjunk columns!), and transfer any sort key information from the
1441  * original tlist.
1442  */
1443  Assert(parse->commandType == CMD_SELECT);
1444 
1445  tlist = root->processed_tlist; /* from plan_set_operations */
1446 
1447  /* for safety, copy processed_tlist instead of modifying in-place */
1448  tlist = postprocess_setop_tlist(copyObject(tlist), parse->targetList);
1449 
1450  /* Save aside the final decorated tlist */
1451  root->processed_tlist = tlist;
1452 
1453  /* Also extract the PathTarget form of the setop result tlist */
1454  final_target = current_rel->cheapest_total_path->pathtarget;
1455 
1456  /* The setop result tlist couldn't contain any SRFs */
1457  Assert(!parse->hasTargetSRFs);
1458  final_targets = final_targets_contain_srfs = NIL;
1459 
1460  /*
1461  * Can't handle FOR [KEY] UPDATE/SHARE here (parser should have
1462  * checked already, but let's make sure).
1463  */
1464  if (parse->rowMarks)
1465  ereport(ERROR,
1466  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1467  /*------
1468  translator: %s is a SQL row locking clause such as FOR UPDATE */
1469  errmsg("%s is not allowed with UNION/INTERSECT/EXCEPT",
1471  linitial(parse->rowMarks))->strength))));
1472 
1473  /*
1474  * Calculate pathkeys that represent result ordering requirements
1475  */
1476  Assert(parse->distinctClause == NIL);
1478  parse->sortClause,
1479  tlist);
1480  }
1481  else
1482  {
1483  /* No set operations, do regular planning */
1484  PathTarget *sort_input_target;
1485  List *sort_input_targets;
1486  List *sort_input_targets_contain_srfs;
1487  PathTarget *grouping_target;
1488  List *grouping_targets;
1489  List *grouping_targets_contain_srfs;
1490  PathTarget *scanjoin_target;
1491  List *scanjoin_targets;
1492  List *scanjoin_targets_contain_srfs;
1493  bool have_grouping;
1494  AggClauseCosts agg_costs;
1495  WindowFuncLists *wflists = NULL;
1496  List *activeWindows = NIL;
1497  List *rollup_lists = NIL;
1498  List *rollup_groupclauses = NIL;
1499  standard_qp_extra qp_extra;
1500 
1501  /* A recursive query should always have setOperations */
1502  Assert(!root->hasRecursion);
1503 
1504  /* Preprocess grouping sets and GROUP BY clause, if any */
1505  if (parse->groupingSets)
1506  {
1507  int *tleref_to_colnum_map;
1508  List *sets;
1509  int maxref;
1510  ListCell *lc;
1511  ListCell *lc2;
1512  ListCell *lc_set;
1513 
1514  parse->groupingSets = expand_grouping_sets(parse->groupingSets, -1);
1515 
1516  /* Identify max SortGroupRef in groupClause, for array sizing */
1517  maxref = 0;
1518  foreach(lc, parse->groupClause)
1519  {
1520  SortGroupClause *gc = lfirst(lc);
1521 
1522  if (gc->tleSortGroupRef > maxref)
1523  maxref = gc->tleSortGroupRef;
1524  }
1525 
1526  /* Allocate workspace array for remapping */
1527  tleref_to_colnum_map = (int *) palloc((maxref + 1) * sizeof(int));
1528 
1529  /* Examine the rollup sets */
1530  sets = extract_rollup_sets(parse->groupingSets);
1531 
1532  foreach(lc_set, sets)
1533  {
1534  List *current_sets = (List *) lfirst(lc_set);
1535  List *groupclause;
1536  int ref;
1537 
1538  /*
1539  * Reorder the current list of grouping sets into correct
1540  * prefix order. If only one aggregation pass is needed, try
1541  * to make the list match the ORDER BY clause; if more than
1542  * one pass is needed, we don't bother with that.
1543  */
1544  current_sets = reorder_grouping_sets(current_sets,
1545  (list_length(sets) == 1
1546  ? parse->sortClause
1547  : NIL));
1548 
1549  /*
1550  * Order the groupClause appropriately. If the first grouping
1551  * set is empty, this can match regular GROUP BY
1552  * preprocessing, otherwise we have to force the groupClause
1553  * to match that grouping set's order.
1554  */
1555  groupclause = preprocess_groupclause(root,
1556  linitial(current_sets));
1557 
1558  /*
1559  * Now that we've pinned down an order for the groupClause for
1560  * this list of grouping sets, we need to remap the entries in
1561  * the grouping sets from sortgrouprefs to plain indices
1562  * (0-based) into the groupClause for this collection of
1563  * grouping sets.
1564  */
1565  ref = 0;
1566  foreach(lc, groupclause)
1567  {
1568  SortGroupClause *gc = lfirst(lc);
1569 
1570  tleref_to_colnum_map[gc->tleSortGroupRef] = ref++;
1571  }
1572 
1573  foreach(lc, current_sets)
1574  {
1575  foreach(lc2, (List *) lfirst(lc))
1576  {
1577  lfirst_int(lc2) = tleref_to_colnum_map[lfirst_int(lc2)];
1578  }
1579  }
1580 
1581  /* Save the reordered sets and corresponding groupclauses */
1582  rollup_lists = lcons(current_sets, rollup_lists);
1583  rollup_groupclauses = lcons(groupclause, rollup_groupclauses);
1584  }
1585  }
1586  else
1587  {
1588  /* Preprocess regular GROUP BY clause, if any */
1589  if (parse->groupClause)
1590  parse->groupClause = preprocess_groupclause(root, NIL);
1591  }
1592 
1593  /* Preprocess targetlist */
1594  tlist = preprocess_targetlist(root, tlist);
1595 
1596  if (parse->onConflict)
1597  parse->onConflict->onConflictSet =
1599  parse->resultRelation,
1600  parse->rtable);
1601 
1602  /*
1603  * We are now done hacking up the query's targetlist. Most of the
1604  * remaining planning work will be done with the PathTarget
1605  * representation of tlists, but save aside the full representation so
1606  * that we can transfer its decoration (resnames etc) to the topmost
1607  * tlist of the finished Plan.
1608  */
1609  root->processed_tlist = tlist;
1610 
1611  /*
1612  * Collect statistics about aggregates for estimating costs, and mark
1613  * all the aggregates with resolved aggtranstypes. We must do this
1614  * before slicing and dicing the tlist into various pathtargets, else
1615  * some copies of the Aggref nodes might escape being marked with the
1616  * correct transtypes.
1617  *
1618  * Note: currently, we do not detect duplicate aggregates here. This
1619  * may result in somewhat-overestimated cost, which is fine for our
1620  * purposes since all Paths will get charged the same. But at some
1621  * point we might wish to do that detection in the planner, rather
1622  * than during executor startup.
1623  */
1624  MemSet(&agg_costs, 0, sizeof(AggClauseCosts));
1625  if (parse->hasAggs)
1626  {
1627  get_agg_clause_costs(root, (Node *) tlist, AGGSPLIT_SIMPLE,
1628  &agg_costs);
1630  &agg_costs);
1631  }
1632 
1633  /*
1634  * Locate any window functions in the tlist. (We don't need to look
1635  * anywhere else, since expressions used in ORDER BY will be in there
1636  * too.) Note that they could all have been eliminated by constant
1637  * folding, in which case we don't need to do any more work.
1638  */
1639  if (parse->hasWindowFuncs)
1640  {
1641  wflists = find_window_functions((Node *) tlist,
1642  list_length(parse->windowClause));
1643  if (wflists->numWindowFuncs > 0)
1644  activeWindows = select_active_windows(root, wflists);
1645  else
1646  parse->hasWindowFuncs = false;
1647  }
1648 
1649  /*
1650  * Preprocess MIN/MAX aggregates, if any. Note: be careful about
1651  * adding logic between here and the query_planner() call. Anything
1652  * that is needed in MIN/MAX-optimizable cases will have to be
1653  * duplicated in planagg.c.
1654  */
1655  if (parse->hasAggs)
1656  preprocess_minmax_aggregates(root, tlist);
1657 
1658  /*
1659  * Figure out whether there's a hard limit on the number of rows that
1660  * query_planner's result subplan needs to return. Even if we know a
1661  * hard limit overall, it doesn't apply if the query has any
1662  * grouping/aggregation operations, or SRFs in the tlist.
1663  */
1664  if (parse->groupClause ||
1665  parse->groupingSets ||
1666  parse->distinctClause ||
1667  parse->hasAggs ||
1668  parse->hasWindowFuncs ||
1669  parse->hasTargetSRFs ||
1670  root->hasHavingQual)
1671  root->limit_tuples = -1.0;
1672  else
1673  root->limit_tuples = limit_tuples;
1674 
1675  /* Set up data needed by standard_qp_callback */
1676  qp_extra.tlist = tlist;
1677  qp_extra.activeWindows = activeWindows;
1678  qp_extra.groupClause =
1679  parse->groupingSets ? llast(rollup_groupclauses) : parse->groupClause;
1680 
1681  /*
1682  * Generate the best unsorted and presorted paths for the scan/join
1683  * portion of this Query, ie the processing represented by the
1684  * FROM/WHERE clauses. (Note there may not be any presorted paths.)
1685  * We also generate (in standard_qp_callback) pathkey representations
1686  * of the query's sort clause, distinct clause, etc.
1687  */
1688  current_rel = query_planner(root, tlist,
1689  standard_qp_callback, &qp_extra);
1690 
1691  /*
1692  * Convert the query's result tlist into PathTarget format.
1693  *
1694  * Note: it's desirable to not do this till after query_planner(),
1695  * because the target width estimates can use per-Var width numbers
1696  * that were obtained within query_planner().
1697  */
1698  final_target = create_pathtarget(root, tlist);
1699 
1700  /*
1701  * If ORDER BY was given, consider whether we should use a post-sort
1702  * projection, and compute the adjusted target for preceding steps if
1703  * so.
1704  */
1705  if (parse->sortClause)
1706  sort_input_target = make_sort_input_target(root,
1707  final_target,
1708  &have_postponed_srfs);
1709  else
1710  sort_input_target = final_target;
1711 
1712  /*
1713  * If we have window functions to deal with, the output from any
1714  * grouping step needs to be what the window functions want;
1715  * otherwise, it should be sort_input_target.
1716  */
1717  if (activeWindows)
1718  grouping_target = make_window_input_target(root,
1719  final_target,
1720  activeWindows);
1721  else
1722  grouping_target = sort_input_target;
1723 
1724  /*
1725  * If we have grouping or aggregation to do, the topmost scan/join
1726  * plan node must emit what the grouping step wants; otherwise, it
1727  * should emit grouping_target.
1728  */
1729  have_grouping = (parse->groupClause || parse->groupingSets ||
1730  parse->hasAggs || root->hasHavingQual);
1731  if (have_grouping)
1732  scanjoin_target = make_group_input_target(root, final_target);
1733  else
1734  scanjoin_target = grouping_target;
1735 
1736  /*
1737  * If there are any SRFs in the targetlist, we must separate each of
1738  * these PathTargets into SRF-computing and SRF-free targets. Replace
1739  * each of the named targets with a SRF-free version, and remember the
1740  * list of additional projection steps we need to add afterwards.
1741  */
1742  if (parse->hasTargetSRFs)
1743  {
1744  /* final_target doesn't recompute any SRFs in sort_input_target */
1745  split_pathtarget_at_srfs(root, final_target, sort_input_target,
1746  &final_targets,
1747  &final_targets_contain_srfs);
1748  final_target = (PathTarget *) linitial(final_targets);
1749  Assert(!linitial_int(final_targets_contain_srfs));
1750  /* likewise for sort_input_target vs. grouping_target */
1751  split_pathtarget_at_srfs(root, sort_input_target, grouping_target,
1752  &sort_input_targets,
1753  &sort_input_targets_contain_srfs);
1754  sort_input_target = (PathTarget *) linitial(sort_input_targets);
1755  Assert(!linitial_int(sort_input_targets_contain_srfs));
1756  /* likewise for grouping_target vs. scanjoin_target */
1757  split_pathtarget_at_srfs(root, grouping_target, scanjoin_target,
1758  &grouping_targets,
1759  &grouping_targets_contain_srfs);
1760  grouping_target = (PathTarget *) linitial(grouping_targets);
1761  Assert(!linitial_int(grouping_targets_contain_srfs));
1762  /* scanjoin_target will not have any SRFs precomputed for it */
1763  split_pathtarget_at_srfs(root, scanjoin_target, NULL,
1764  &scanjoin_targets,
1765  &scanjoin_targets_contain_srfs);
1766  scanjoin_target = (PathTarget *) linitial(scanjoin_targets);
1767  Assert(!linitial_int(scanjoin_targets_contain_srfs));
1768  }
1769  else
1770  {
1771  /* initialize lists, just to keep compiler quiet */
1772  final_targets = final_targets_contain_srfs = NIL;
1773  sort_input_targets = sort_input_targets_contain_srfs = NIL;
1774  grouping_targets = grouping_targets_contain_srfs = NIL;
1775  scanjoin_targets = scanjoin_targets_contain_srfs = NIL;
1776  }
1777 
1778  /*
1779  * Forcibly apply SRF-free scan/join target to all the Paths for the
1780  * scan/join rel.
1781  *
1782  * In principle we should re-run set_cheapest() here to identify the
1783  * cheapest path, but it seems unlikely that adding the same tlist
1784  * eval costs to all the paths would change that, so we don't bother.
1785  * Instead, just assume that the cheapest-startup and cheapest-total
1786  * paths remain so. (There should be no parameterized paths anymore,
1787  * so we needn't worry about updating cheapest_parameterized_paths.)
1788  */
1789  foreach(lc, current_rel->pathlist)
1790  {
1791  Path *subpath = (Path *) lfirst(lc);
1792  Path *path;
1793 
1794  Assert(subpath->param_info == NULL);
1795  path = apply_projection_to_path(root, current_rel,
1796  subpath, scanjoin_target);
1797  /* If we had to add a Result, path is different from subpath */
1798  if (path != subpath)
1799  {
1800  lfirst(lc) = path;
1801  if (subpath == current_rel->cheapest_startup_path)
1802  current_rel->cheapest_startup_path = path;
1803  if (subpath == current_rel->cheapest_total_path)
1804  current_rel->cheapest_total_path = path;
1805  }
1806  }
1807 
1808  /*
1809  * Upper planning steps which make use of the top scan/join rel's
1810  * partial pathlist will expect partial paths for that rel to produce
1811  * the same output as complete paths ... and we just changed the
1812  * output for the complete paths, so we'll need to do the same thing
1813  * for partial paths. But only parallel-safe expressions can be
1814  * computed by partial paths.
1815  */
1816  if (current_rel->partial_pathlist &&
1817  is_parallel_safe(root, (Node *) scanjoin_target->exprs))
1818  {
1819  /* Apply the scan/join target to each partial path */
1820  foreach(lc, current_rel->partial_pathlist)
1821  {
1822  Path *subpath = (Path *) lfirst(lc);
1823  Path *newpath;
1824 
1825  /* Shouldn't have any parameterized paths anymore */
1826  Assert(subpath->param_info == NULL);
1827 
1828  /*
1829  * Don't use apply_projection_to_path() here, because there
1830  * could be other pointers to these paths, and therefore we
1831  * mustn't modify them in place.
1832  */
1833  newpath = (Path *) create_projection_path(root,
1834  current_rel,
1835  subpath,
1836  scanjoin_target);
1837  lfirst(lc) = newpath;
1838  }
1839  }
1840  else
1841  {
1842  /*
1843  * In the unfortunate event that scanjoin_target is not
1844  * parallel-safe, we can't apply it to the partial paths; in that
1845  * case, we'll need to forget about the partial paths, which
1846  * aren't valid input for upper planning steps.
1847  */
1848  current_rel->partial_pathlist = NIL;
1849  }
1850 
1851  /* Now fix things up if scan/join target contains SRFs */
1852  if (parse->hasTargetSRFs)
1853  adjust_paths_for_srfs(root, current_rel,
1854  scanjoin_targets,
1855  scanjoin_targets_contain_srfs);
1856 
1857  /*
1858  * Save the various upper-rel PathTargets we just computed into
1859  * root->upper_targets[]. The core code doesn't use this, but it
1860  * provides a convenient place for extensions to get at the info. For
1861  * consistency, we save all the intermediate targets, even though some
1862  * of the corresponding upperrels might not be needed for this query.
1863  */
1864  root->upper_targets[UPPERREL_FINAL] = final_target;
1865  root->upper_targets[UPPERREL_WINDOW] = sort_input_target;
1866  root->upper_targets[UPPERREL_GROUP_AGG] = grouping_target;
1867 
1868  /*
1869  * If we have grouping and/or aggregation, consider ways to implement
1870  * that. We build a new upperrel representing the output of this
1871  * phase.
1872  */
1873  if (have_grouping)
1874  {
1875  current_rel = create_grouping_paths(root,
1876  current_rel,
1877  grouping_target,
1878  &agg_costs,
1879  rollup_lists,
1880  rollup_groupclauses);
1881  /* Fix things up if grouping_target contains SRFs */
1882  if (parse->hasTargetSRFs)
1883  adjust_paths_for_srfs(root, current_rel,
1884  grouping_targets,
1885  grouping_targets_contain_srfs);
1886  }
1887 
1888  /*
1889  * If we have window functions, consider ways to implement those. We
1890  * build a new upperrel representing the output of this phase.
1891  */
1892  if (activeWindows)
1893  {
1894  current_rel = create_window_paths(root,
1895  current_rel,
1896  grouping_target,
1897  sort_input_target,
1898  tlist,
1899  wflists,
1900  activeWindows);
1901  /* Fix things up if sort_input_target contains SRFs */
1902  if (parse->hasTargetSRFs)
1903  adjust_paths_for_srfs(root, current_rel,
1904  sort_input_targets,
1905  sort_input_targets_contain_srfs);
1906  }
1907 
1908  /*
1909  * If there is a DISTINCT clause, consider ways to implement that. We
1910  * build a new upperrel representing the output of this phase.
1911  */
1912  if (parse->distinctClause)
1913  {
1914  current_rel = create_distinct_paths(root,
1915  current_rel);
1916  }
1917 
1918  } /* end of if (setOperations) */
1919 
1920  /*
1921  * If ORDER BY was given, consider ways to implement that, and generate a
1922  * new upperrel containing only paths that emit the correct ordering and
1923  * project the correct final_target. We can apply the original
1924  * limit_tuples limit in sort costing here, but only if there are no
1925  * postponed SRFs.
1926  */
1927  if (parse->sortClause)
1928  {
1929  current_rel = create_ordered_paths(root,
1930  current_rel,
1931  final_target,
1932  have_postponed_srfs ? -1.0 :
1933  limit_tuples);
1934  /* Fix things up if final_target contains SRFs */
1935  if (parse->hasTargetSRFs)
1936  adjust_paths_for_srfs(root, current_rel,
1937  final_targets,
1938  final_targets_contain_srfs);
1939  }
1940 
1941  /*
1942  * Now we are prepared to build the final-output upperrel.
1943  */
1944  final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
1945 
1946  /*
1947  * If the input rel is marked consider_parallel and there's nothing that's
1948  * not parallel-safe in the LIMIT clause, then the final_rel can be marked
1949  * consider_parallel as well. Note that if the query has rowMarks or is
1950  * not a SELECT, consider_parallel will be false for every relation in the
1951  * query.
1952  */
1953  if (current_rel->consider_parallel &&
1954  is_parallel_safe(root, parse->limitOffset) &&
1955  is_parallel_safe(root, parse->limitCount))
1956  final_rel->consider_parallel = true;
1957 
1958  /*
1959  * If the current_rel belongs to a single FDW, so does the final_rel.
1960  */
1961  final_rel->serverid = current_rel->serverid;
1962  final_rel->userid = current_rel->userid;
1963  final_rel->useridiscurrent = current_rel->useridiscurrent;
1964  final_rel->fdwroutine = current_rel->fdwroutine;
1965 
1966  /*
1967  * Generate paths for the final_rel. Insert all surviving paths, with
1968  * LockRows, Limit, and/or ModifyTable steps added if needed.
1969  */
1970  foreach(lc, current_rel->pathlist)
1971  {
1972  Path *path = (Path *) lfirst(lc);
1973 
1974  /*
1975  * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node.
1976  * (Note: we intentionally test parse->rowMarks not root->rowMarks
1977  * here. If there are only non-locking rowmarks, they should be
1978  * handled by the ModifyTable node instead. However, root->rowMarks
1979  * is what goes into the LockRows node.)
1980  */
1981  if (parse->rowMarks)
1982  {
1983  path = (Path *) create_lockrows_path(root, final_rel, path,
1984  root->rowMarks,
1985  SS_assign_special_param(root));
1986  }
1987 
1988  /*
1989  * If there is a LIMIT/OFFSET clause, add the LIMIT node.
1990  */
1991  if (limit_needed(parse))
1992  {
1993  path = (Path *) create_limit_path(root, final_rel, path,
1994  parse->limitOffset,
1995  parse->limitCount,
1996  offset_est, count_est);
1997  }
1998 
1999  /*
2000  * If this is an INSERT/UPDATE/DELETE, and we're not being called from
2001  * inheritance_planner, add the ModifyTable node.
2002  */
2003  if (parse->commandType != CMD_SELECT && !inheritance_update)
2004  {
2005  List *withCheckOptionLists;
2006  List *returningLists;
2007  List *rowMarks;
2008 
2009  /*
2010  * Set up the WITH CHECK OPTION and RETURNING lists-of-lists, if
2011  * needed.
2012  */
2013  if (parse->withCheckOptions)
2014  withCheckOptionLists = list_make1(parse->withCheckOptions);
2015  else
2016  withCheckOptionLists = NIL;
2017 
2018  if (parse->returningList)
2019  returningLists = list_make1(parse->returningList);
2020  else
2021  returningLists = NIL;
2022 
2023  /*
2024  * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node
2025  * will have dealt with fetching non-locked marked rows, else we
2026  * need to have ModifyTable do that.
2027  */
2028  if (parse->rowMarks)
2029  rowMarks = NIL;
2030  else
2031  rowMarks = root->rowMarks;
2032 
2033  path = (Path *)
2034  create_modifytable_path(root, final_rel,
2035  parse->commandType,
2036  parse->canSetTag,
2037  parse->resultRelation,
2039  list_make1(path),
2040  list_make1(root),
2041  withCheckOptionLists,
2042  returningLists,
2043  rowMarks,
2044  parse->onConflict,
2045  SS_assign_special_param(root));
2046  }
2047 
2048  /* And shove it into final_rel */
2049  add_path(final_rel, path);
2050  }
2051 
2052  /*
2053  * If there is an FDW that's responsible for all baserels of the query,
2054  * let it consider adding ForeignPaths.
2055  */
2056  if (final_rel->fdwroutine &&
2057  final_rel->fdwroutine->GetForeignUpperPaths)
2059  current_rel, final_rel);
2060 
2061  /* Let extensions possibly add some more paths */
2063  (*create_upper_paths_hook) (root, UPPERREL_FINAL,
2064  current_rel, final_rel);
2065 
2066  /* Note: currently, we leave it to callers to do set_cheapest() */
2067 }
2068 
2069 
2070 /*
2071  * Detect whether a plan node is a "dummy" plan created when a relation
2072  * is deemed not to need scanning due to constraint exclusion.
2073  *
2074  * Currently, such dummy plans are Result nodes with constant FALSE
2075  * filter quals (see set_dummy_rel_pathlist and create_append_plan).
2076  *
2077  * XXX this probably ought to be somewhere else, but not clear where.
2078  */
2079 bool
2081 {
2082  if (IsA(plan, Result))
2083  {
2084  List *rcqual = (List *) ((Result *) plan)->resconstantqual;
2085 
2086  if (list_length(rcqual) == 1)
2087  {
2088  Const *constqual = (Const *) linitial(rcqual);
2089 
2090  if (constqual && IsA(constqual, Const))
2091  {
2092  if (!constqual->constisnull &&
2093  !DatumGetBool(constqual->constvalue))
2094  return true;
2095  }
2096  }
2097  }
2098  return false;
2099 }
2100 
2101 /*
2102  * preprocess_rowmarks - set up PlanRowMarks if needed
2103  */
2104 static void
2106 {
2107  Query *parse = root->parse;
2108  Bitmapset *rels;
2109  List *prowmarks;
2110  ListCell *l;
2111  int i;
2112 
2113  if (parse->rowMarks)
2114  {
2115  /*
2116  * We've got trouble if FOR [KEY] UPDATE/SHARE appears inside
2117  * grouping, since grouping renders a reference to individual tuple
2118  * CTIDs invalid. This is also checked at parse time, but that's
2119  * insufficient because of rule substitution, query pullup, etc.
2120  */
2121  CheckSelectLocking(parse, ((RowMarkClause *)
2122  linitial(parse->rowMarks))->strength);
2123  }
2124  else
2125  {
2126  /*
2127  * We only need rowmarks for UPDATE, DELETE, or FOR [KEY]
2128  * UPDATE/SHARE.
2129  */
2130  if (parse->commandType != CMD_UPDATE &&
2131  parse->commandType != CMD_DELETE)
2132  return;
2133  }
2134 
2135  /*
2136  * We need to have rowmarks for all base relations except the target. We
2137  * make a bitmapset of all base rels and then remove the items we don't
2138  * need or have FOR [KEY] UPDATE/SHARE marks for.
2139  */
2140  rels = get_relids_in_jointree((Node *) parse->jointree, false);
2141  if (parse->resultRelation)
2142  rels = bms_del_member(rels, parse->resultRelation);
2143 
2144  /*
2145  * Convert RowMarkClauses to PlanRowMark representation.
2146  */
2147  prowmarks = NIL;
2148  foreach(l, parse->rowMarks)
2149  {
2150  RowMarkClause *rc = (RowMarkClause *) lfirst(l);
2151  RangeTblEntry *rte = rt_fetch(rc->rti, parse->rtable);
2152  PlanRowMark *newrc;
2153 
2154  /*
2155  * Currently, it is syntactically impossible to have FOR UPDATE et al
2156  * applied to an update/delete target rel. If that ever becomes
2157  * possible, we should drop the target from the PlanRowMark list.
2158  */
2159  Assert(rc->rti != parse->resultRelation);
2160 
2161  /*
2162  * Ignore RowMarkClauses for subqueries; they aren't real tables and
2163  * can't support true locking. Subqueries that got flattened into the
2164  * main query should be ignored completely. Any that didn't will get
2165  * ROW_MARK_COPY items in the next loop.
2166  */
2167  if (rte->rtekind != RTE_RELATION)
2168  continue;
2169 
2170  rels = bms_del_member(rels, rc->rti);
2171 
2172  newrc = makeNode(PlanRowMark);
2173  newrc->rti = newrc->prti = rc->rti;
2174  newrc->rowmarkId = ++(root->glob->lastRowMarkId);
2175  newrc->markType = select_rowmark_type(rte, rc->strength);
2176  newrc->allMarkTypes = (1 << newrc->markType);
2177  newrc->strength = rc->strength;
2178  newrc->waitPolicy = rc->waitPolicy;
2179  newrc->isParent = false;
2180 
2181  prowmarks = lappend(prowmarks, newrc);
2182  }
2183 
2184  /*
2185  * Now, add rowmarks for any non-target, non-locked base relations.
2186  */
2187  i = 0;
2188  foreach(l, parse->rtable)
2189  {
2190  RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
2191  PlanRowMark *newrc;
2192 
2193  i++;
2194  if (!bms_is_member(i, rels))
2195  continue;
2196 
2197  newrc = makeNode(PlanRowMark);
2198  newrc->rti = newrc->prti = i;
2199  newrc->rowmarkId = ++(root->glob->lastRowMarkId);
2200  newrc->markType = select_rowmark_type(rte, LCS_NONE);
2201  newrc->allMarkTypes = (1 << newrc->markType);
2202  newrc->strength = LCS_NONE;
2203  newrc->waitPolicy = LockWaitBlock; /* doesn't matter */
2204  newrc->isParent = false;
2205 
2206  prowmarks = lappend(prowmarks, newrc);
2207  }
2208 
2209  root->rowMarks = prowmarks;
2210 }
2211 
2212 /*
2213  * Select RowMarkType to use for a given table
2214  */
2217 {
2218  if (rte->rtekind != RTE_RELATION)
2219  {
2220  /* If it's not a table at all, use ROW_MARK_COPY */
2221  return ROW_MARK_COPY;
2222  }
2223  else if (rte->relkind == RELKIND_FOREIGN_TABLE)
2224  {
2225  /* Let the FDW select the rowmark type, if it wants to */
2226  FdwRoutine *fdwroutine = GetFdwRoutineByRelId(rte->relid);
2227 
2228  if (fdwroutine->GetForeignRowMarkType != NULL)
2229  return fdwroutine->GetForeignRowMarkType(rte, strength);
2230  /* Otherwise, use ROW_MARK_COPY by default */
2231  return ROW_MARK_COPY;
2232  }
2233  else
2234  {
2235  /* Regular table, apply the appropriate lock type */
2236  switch (strength)
2237  {
2238  case LCS_NONE:
2239 
2240  /*
2241  * We don't need a tuple lock, only the ability to re-fetch
2242  * the row.
2243  */
2244  return ROW_MARK_REFERENCE;
2245  break;
2246  case LCS_FORKEYSHARE:
2247  return ROW_MARK_KEYSHARE;
2248  break;
2249  case LCS_FORSHARE:
2250  return ROW_MARK_SHARE;
2251  break;
2252  case LCS_FORNOKEYUPDATE:
2253  return ROW_MARK_NOKEYEXCLUSIVE;
2254  break;
2255  case LCS_FORUPDATE:
2256  return ROW_MARK_EXCLUSIVE;
2257  break;
2258  }
2259  elog(ERROR, "unrecognized LockClauseStrength %d", (int) strength);
2260  return ROW_MARK_EXCLUSIVE; /* keep compiler quiet */
2261  }
2262 }
2263 
2264 /*
2265  * preprocess_limit - do pre-estimation for LIMIT and/or OFFSET clauses
2266  *
2267  * We try to estimate the values of the LIMIT/OFFSET clauses, and pass the
2268  * results back in *count_est and *offset_est. These variables are set to
2269  * 0 if the corresponding clause is not present, and -1 if it's present
2270  * but we couldn't estimate the value for it. (The "0" convention is OK
2271  * for OFFSET but a little bit bogus for LIMIT: effectively we estimate
2272  * LIMIT 0 as though it were LIMIT 1. But this is in line with the planner's
2273  * usual practice of never estimating less than one row.) These values will
2274  * be passed to create_limit_path, which see if you change this code.
2275  *
2276  * The return value is the suitably adjusted tuple_fraction to use for
2277  * planning the query. This adjustment is not overridable, since it reflects
2278  * plan actions that grouping_planner() will certainly take, not assumptions
2279  * about context.
2280  */
2281 static double
2282 preprocess_limit(PlannerInfo *root, double tuple_fraction,
2283  int64 *offset_est, int64 *count_est)
2284 {
2285  Query *parse = root->parse;
2286  Node *est;
2287  double limit_fraction;
2288 
2289  /* Should not be called unless LIMIT or OFFSET */
2290  Assert(parse->limitCount || parse->limitOffset);
2291 
2292  /*
2293  * Try to obtain the clause values. We use estimate_expression_value
2294  * primarily because it can sometimes do something useful with Params.
2295  */
2296  if (parse->limitCount)
2297  {
2298  est = estimate_expression_value(root, parse->limitCount);
2299  if (est && IsA(est, Const))
2300  {
2301  if (((Const *) est)->constisnull)
2302  {
2303  /* NULL indicates LIMIT ALL, ie, no limit */
2304  *count_est = 0; /* treat as not present */
2305  }
2306  else
2307  {
2308  *count_est = DatumGetInt64(((Const *) est)->constvalue);
2309  if (*count_est <= 0)
2310  *count_est = 1; /* force to at least 1 */
2311  }
2312  }
2313  else
2314  *count_est = -1; /* can't estimate */
2315  }
2316  else
2317  *count_est = 0; /* not present */
2318 
2319  if (parse->limitOffset)
2320  {
2321  est = estimate_expression_value(root, parse->limitOffset);
2322  if (est && IsA(est, Const))
2323  {
2324  if (((Const *) est)->constisnull)
2325  {
2326  /* Treat NULL as no offset; the executor will too */
2327  *offset_est = 0; /* treat as not present */
2328  }
2329  else
2330  {
2331  *offset_est = DatumGetInt64(((Const *) est)->constvalue);
2332  if (*offset_est < 0)
2333  *offset_est = 0; /* treat as not present */
2334  }
2335  }
2336  else
2337  *offset_est = -1; /* can't estimate */
2338  }
2339  else
2340  *offset_est = 0; /* not present */
2341 
2342  if (*count_est != 0)
2343  {
2344  /*
2345  * A LIMIT clause limits the absolute number of tuples returned.
2346  * However, if it's not a constant LIMIT then we have to guess; for
2347  * lack of a better idea, assume 10% of the plan's result is wanted.
2348  */
2349  if (*count_est < 0 || *offset_est < 0)
2350  {
2351  /* LIMIT or OFFSET is an expression ... punt ... */
2352  limit_fraction = 0.10;
2353  }
2354  else
2355  {
2356  /* LIMIT (plus OFFSET, if any) is max number of tuples needed */
2357  limit_fraction = (double) *count_est + (double) *offset_est;
2358  }
2359 
2360  /*
2361  * If we have absolute limits from both caller and LIMIT, use the
2362  * smaller value; likewise if they are both fractional. If one is
2363  * fractional and the other absolute, we can't easily determine which
2364  * is smaller, but we use the heuristic that the absolute will usually
2365  * be smaller.
2366  */
2367  if (tuple_fraction >= 1.0)
2368  {
2369  if (limit_fraction >= 1.0)
2370  {
2371  /* both absolute */
2372  tuple_fraction = Min(tuple_fraction, limit_fraction);
2373  }
2374  else
2375  {
2376  /* caller absolute, limit fractional; use caller's value */
2377  }
2378  }
2379  else if (tuple_fraction > 0.0)
2380  {
2381  if (limit_fraction >= 1.0)
2382  {
2383  /* caller fractional, limit absolute; use limit */
2384  tuple_fraction = limit_fraction;
2385  }
2386  else
2387  {
2388  /* both fractional */
2389  tuple_fraction = Min(tuple_fraction, limit_fraction);
2390  }
2391  }
2392  else
2393  {
2394  /* no info from caller, just use limit */
2395  tuple_fraction = limit_fraction;
2396  }
2397  }
2398  else if (*offset_est != 0 && tuple_fraction > 0.0)
2399  {
2400  /*
2401  * We have an OFFSET but no LIMIT. This acts entirely differently
2402  * from the LIMIT case: here, we need to increase rather than decrease
2403  * the caller's tuple_fraction, because the OFFSET acts to cause more
2404  * tuples to be fetched instead of fewer. This only matters if we got
2405  * a tuple_fraction > 0, however.
2406  *
2407  * As above, use 10% if OFFSET is present but unestimatable.
2408  */
2409  if (*offset_est < 0)
2410  limit_fraction = 0.10;
2411  else
2412  limit_fraction = (double) *offset_est;
2413 
2414  /*
2415  * If we have absolute counts from both caller and OFFSET, add them
2416  * together; likewise if they are both fractional. If one is
2417  * fractional and the other absolute, we want to take the larger, and
2418  * we heuristically assume that's the fractional one.
2419  */
2420  if (tuple_fraction >= 1.0)
2421  {
2422  if (limit_fraction >= 1.0)
2423  {
2424  /* both absolute, so add them together */
2425  tuple_fraction += limit_fraction;
2426  }
2427  else
2428  {
2429  /* caller absolute, limit fractional; use limit */
2430  tuple_fraction = limit_fraction;
2431  }
2432  }
2433  else
2434  {
2435  if (limit_fraction >= 1.0)
2436  {
2437  /* caller fractional, limit absolute; use caller's value */
2438  }
2439  else
2440  {
2441  /* both fractional, so add them together */
2442  tuple_fraction += limit_fraction;
2443  if (tuple_fraction >= 1.0)
2444  tuple_fraction = 0.0; /* assume fetch all */
2445  }
2446  }
2447  }
2448 
2449  return tuple_fraction;
2450 }
2451 
2452 /*
2453  * limit_needed - do we actually need a Limit plan node?
2454  *
2455  * If we have constant-zero OFFSET and constant-null LIMIT, we can skip adding
2456  * a Limit node. This is worth checking for because "OFFSET 0" is a common
2457  * locution for an optimization fence. (Because other places in the planner
2458  * merely check whether parse->limitOffset isn't NULL, it will still work as
2459  * an optimization fence --- we're just suppressing unnecessary run-time
2460  * overhead.)
2461  *
2462  * This might look like it could be merged into preprocess_limit, but there's
2463  * a key distinction: here we need hard constants in OFFSET/LIMIT, whereas
2464  * in preprocess_limit it's good enough to consider estimated values.
2465  */
2466 static bool
2468 {
2469  Node *node;
2470 
2471  node = parse->limitCount;
2472  if (node)
2473  {
2474  if (IsA(node, Const))
2475  {
2476  /* NULL indicates LIMIT ALL, ie, no limit */
2477  if (!((Const *) node)->constisnull)
2478  return true; /* LIMIT with a constant value */
2479  }
2480  else
2481  return true; /* non-constant LIMIT */
2482  }
2483 
2484  node = parse->limitOffset;
2485  if (node)
2486  {
2487  if (IsA(node, Const))
2488  {
2489  /* Treat NULL as no offset; the executor would too */
2490  if (!((Const *) node)->constisnull)
2491  {
2492  int64 offset = DatumGetInt64(((Const *) node)->constvalue);
2493 
2494  if (offset != 0)
2495  return true; /* OFFSET with a nonzero value */
2496  }
2497  }
2498  else
2499  return true; /* non-constant OFFSET */
2500  }
2501 
2502  return false; /* don't need a Limit plan node */
2503 }
2504 
2505 
2506 /*
2507  * remove_useless_groupby_columns
2508  * Remove any columns in the GROUP BY clause that are redundant due to
2509  * being functionally dependent on other GROUP BY columns.
2510  *
2511  * Since some other DBMSes do not allow references to ungrouped columns, it's
2512  * not unusual to find all columns listed in GROUP BY even though listing the
2513  * primary-key columns would be sufficient. Deleting such excess columns
2514  * avoids redundant sorting work, so it's worth doing. When we do this, we
2515  * must mark the plan as dependent on the pkey constraint (compare the
2516  * parser's check_ungrouped_columns() and check_functional_grouping()).
2517  *
2518  * In principle, we could treat any NOT-NULL columns appearing in a UNIQUE
2519  * index as the determining columns. But as with check_functional_grouping(),
2520  * there's currently no way to represent dependency on a NOT NULL constraint,
2521  * so we consider only the pkey for now.
2522  */
2523 static void
2525 {
2526  Query *parse = root->parse;
2527  Bitmapset **groupbyattnos;
2528  Bitmapset **surplusvars;
2529  ListCell *lc;
2530  int relid;
2531 
2532  /* No chance to do anything if there are less than two GROUP BY items */
2533  if (list_length(parse->groupClause) < 2)
2534  return;
2535 
2536  /* Don't fiddle with the GROUP BY clause if the query has grouping sets */
2537  if (parse->groupingSets)
2538  return;
2539 
2540  /*
2541  * Scan the GROUP BY clause to find GROUP BY items that are simple Vars.
2542  * Fill groupbyattnos[k] with a bitmapset of the column attnos of RTE k
2543  * that are GROUP BY items.
2544  */
2545  groupbyattnos = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
2546  (list_length(parse->rtable) + 1));
2547  foreach(lc, parse->groupClause)
2548  {
2549  SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2550  TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
2551  Var *var = (Var *) tle->expr;
2552 
2553  /*
2554  * Ignore non-Vars and Vars from other query levels.
2555  *
2556  * XXX in principle, stable expressions containing Vars could also be
2557  * removed, if all the Vars are functionally dependent on other GROUP
2558  * BY items. But it's not clear that such cases occur often enough to
2559  * be worth troubling over.
2560  */
2561  if (!IsA(var, Var) ||
2562  var->varlevelsup > 0)
2563  continue;
2564 
2565  /* OK, remember we have this Var */
2566  relid = var->varno;
2567  Assert(relid <= list_length(parse->rtable));
2568  groupbyattnos[relid] = bms_add_member(groupbyattnos[relid],
2570  }
2571 
2572  /*
2573  * Consider each relation and see if it is possible to remove some of its
2574  * Vars from GROUP BY. For simplicity and speed, we do the actual removal
2575  * in a separate pass. Here, we just fill surplusvars[k] with a bitmapset
2576  * of the column attnos of RTE k that are removable GROUP BY items.
2577  */
2578  surplusvars = NULL; /* don't allocate array unless required */
2579  relid = 0;
2580  foreach(lc, parse->rtable)
2581  {
2582  RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
2583  Bitmapset *relattnos;
2584  Bitmapset *pkattnos;
2585  Oid constraintOid;
2586 
2587  relid++;
2588 
2589  /* Only plain relations could have primary-key constraints */
2590  if (rte->rtekind != RTE_RELATION)
2591  continue;
2592 
2593  /* Nothing to do unless this rel has multiple Vars in GROUP BY */
2594  relattnos = groupbyattnos[relid];
2595  if (bms_membership(relattnos) != BMS_MULTIPLE)
2596  continue;
2597 
2598  /*
2599  * Can't remove any columns for this rel if there is no suitable
2600  * (i.e., nondeferrable) primary key constraint.
2601  */
2602  pkattnos = get_primary_key_attnos(rte->relid, false, &constraintOid);
2603  if (pkattnos == NULL)
2604  continue;
2605 
2606  /*
2607  * If the primary key is a proper subset of relattnos then we have
2608  * some items in the GROUP BY that can be removed.
2609  */
2610  if (bms_subset_compare(pkattnos, relattnos) == BMS_SUBSET1)
2611  {
2612  /*
2613  * To easily remember whether we've found anything to do, we don't
2614  * allocate the surplusvars[] array until we find something.
2615  */
2616  if (surplusvars == NULL)
2617  surplusvars = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
2618  (list_length(parse->rtable) + 1));
2619 
2620  /* Remember the attnos of the removable columns */
2621  surplusvars[relid] = bms_difference(relattnos, pkattnos);
2622 
2623  /* Also, mark the resulting plan as dependent on this constraint */
2624  parse->constraintDeps = lappend_oid(parse->constraintDeps,
2625  constraintOid);
2626  }
2627  }
2628 
2629  /*
2630  * If we found any surplus Vars, build a new GROUP BY clause without them.
2631  * (Note: this may leave some TLEs with unreferenced ressortgroupref
2632  * markings, but that's harmless.)
2633  */
2634  if (surplusvars != NULL)
2635  {
2636  List *new_groupby = NIL;
2637 
2638  foreach(lc, parse->groupClause)
2639  {
2640  SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2641  TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
2642  Var *var = (Var *) tle->expr;
2643 
2644  /*
2645  * New list must include non-Vars, outer Vars, and anything not
2646  * marked as surplus.
2647  */
2648  if (!IsA(var, Var) ||
2649  var->varlevelsup > 0 ||
2651  surplusvars[var->varno]))
2652  new_groupby = lappend(new_groupby, sgc);
2653  }
2654 
2655  parse->groupClause = new_groupby;
2656  }
2657 }
2658 
2659 /*
2660  * preprocess_groupclause - do preparatory work on GROUP BY clause
2661  *
2662  * The idea here is to adjust the ordering of the GROUP BY elements
2663  * (which in itself is semantically insignificant) to match ORDER BY,
2664  * thereby allowing a single sort operation to both implement the ORDER BY
2665  * requirement and set up for a Unique step that implements GROUP BY.
2666  *
2667  * In principle it might be interesting to consider other orderings of the
2668  * GROUP BY elements, which could match the sort ordering of other
2669  * possible plans (eg an indexscan) and thereby reduce cost. We don't
2670  * bother with that, though. Hashed grouping will frequently win anyway.
2671  *
2672  * Note: we need no comparable processing of the distinctClause because
2673  * the parser already enforced that that matches ORDER BY.
2674  *
2675  * For grouping sets, the order of items is instead forced to agree with that
2676  * of the grouping set (and items not in the grouping set are skipped). The
2677  * work of sorting the order of grouping set elements to match the ORDER BY if
2678  * possible is done elsewhere.
2679  */
2680 static List *
2682 {
2683  Query *parse = root->parse;
2684  List *new_groupclause = NIL;
2685  bool partial_match;
2686  ListCell *sl;
2687  ListCell *gl;
2688 
2689  /* For grouping sets, we need to force the ordering */
2690  if (force)
2691  {
2692  foreach(sl, force)
2693  {
2694  Index ref = lfirst_int(sl);
2696 
2697  new_groupclause = lappend(new_groupclause, cl);
2698  }
2699 
2700  return new_groupclause;
2701  }
2702 
2703  /* If no ORDER BY, nothing useful to do here */
2704  if (parse->sortClause == NIL)
2705  return parse->groupClause;
2706 
2707  /*
2708  * Scan the ORDER BY clause and construct a list of matching GROUP BY
2709  * items, but only as far as we can make a matching prefix.
2710  *
2711  * This code assumes that the sortClause contains no duplicate items.
2712  */
2713  foreach(sl, parse->sortClause)
2714  {
2715  SortGroupClause *sc = (SortGroupClause *) lfirst(sl);
2716 
2717  foreach(gl, parse->groupClause)
2718  {
2719  SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
2720 
2721  if (equal(gc, sc))
2722  {
2723  new_groupclause = lappend(new_groupclause, gc);
2724  break;
2725  }
2726  }
2727  if (gl == NULL)
2728  break; /* no match, so stop scanning */
2729  }
2730 
2731  /* Did we match all of the ORDER BY list, or just some of it? */
2732  partial_match = (sl != NULL);
2733 
2734  /* If no match at all, no point in reordering GROUP BY */
2735  if (new_groupclause == NIL)
2736  return parse->groupClause;
2737 
2738  /*
2739  * Add any remaining GROUP BY items to the new list, but only if we were
2740  * able to make a complete match. In other words, we only rearrange the
2741  * GROUP BY list if the result is that one list is a prefix of the other
2742  * --- otherwise there's no possibility of a common sort. Also, give up
2743  * if there are any non-sortable GROUP BY items, since then there's no
2744  * hope anyway.
2745  */
2746  foreach(gl, parse->groupClause)
2747  {
2748  SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
2749 
2750  if (list_member_ptr(new_groupclause, gc))
2751  continue; /* it matched an ORDER BY item */
2752  if (partial_match)
2753  return parse->groupClause; /* give up, no common sort possible */
2754  if (!OidIsValid(gc->sortop))
2755  return parse->groupClause; /* give up, GROUP BY can't be sorted */
2756  new_groupclause = lappend(new_groupclause, gc);
2757  }
2758 
2759  /* Success --- install the rearranged GROUP BY list */
2760  Assert(list_length(parse->groupClause) == list_length(new_groupclause));
2761  return new_groupclause;
2762 }
2763 
2764 /*
2765  * Extract lists of grouping sets that can be implemented using a single
2766  * rollup-type aggregate pass each. Returns a list of lists of grouping sets.
2767  *
2768  * Input must be sorted with smallest sets first. Result has each sublist
2769  * sorted with smallest sets first.
2770  *
2771  * We want to produce the absolute minimum possible number of lists here to
2772  * avoid excess sorts. Fortunately, there is an algorithm for this; the problem
2773  * of finding the minimal partition of a partially-ordered set into chains
2774  * (which is what we need, taking the list of grouping sets as a poset ordered
2775  * by set inclusion) can be mapped to the problem of finding the maximum
2776  * cardinality matching on a bipartite graph, which is solvable in polynomial
2777  * time with a worst case of no worse than O(n^2.5) and usually much
2778  * better. Since our N is at most 4096, we don't need to consider fallbacks to
2779  * heuristic or approximate methods. (Planning time for a 12-d cube is under
2780  * half a second on my modest system even with optimization off and assertions
2781  * on.)
2782  */
2783 static List *
2785 {
2786  int num_sets_raw = list_length(groupingSets);
2787  int num_empty = 0;
2788  int num_sets = 0; /* distinct sets */
2789  int num_chains = 0;
2790  List *result = NIL;
2791  List **results;
2792  List **orig_sets;
2793  Bitmapset **set_masks;
2794  int *chains;
2795  short **adjacency;
2796  short *adjacency_buf;
2798  int i;
2799  int j;
2800  int j_size;
2801  ListCell *lc1 = list_head(groupingSets);
2802  ListCell *lc;
2803 
2804  /*
2805  * Start by stripping out empty sets. The algorithm doesn't require this,
2806  * but the planner currently needs all empty sets to be returned in the
2807  * first list, so we strip them here and add them back after.
2808  */
2809  while (lc1 && lfirst(lc1) == NIL)
2810  {
2811  ++num_empty;
2812  lc1 = lnext(lc1);
2813  }
2814 
2815  /* bail out now if it turns out that all we had were empty sets. */
2816  if (!lc1)
2817  return list_make1(groupingSets);
2818 
2819  /*----------
2820  * We don't strictly need to remove duplicate sets here, but if we don't,
2821  * they tend to become scattered through the result, which is a bit
2822  * confusing (and irritating if we ever decide to optimize them out).
2823  * So we remove them here and add them back after.
2824  *
2825  * For each non-duplicate set, we fill in the following:
2826  *
2827  * orig_sets[i] = list of the original set lists
2828  * set_masks[i] = bitmapset for testing inclusion
2829  * adjacency[i] = array [n, v1, v2, ... vn] of adjacency indices
2830  *
2831  * chains[i] will be the result group this set is assigned to.
2832  *
2833  * We index all of these from 1 rather than 0 because it is convenient
2834  * to leave 0 free for the NIL node in the graph algorithm.
2835  *----------
2836  */
2837  orig_sets = palloc0((num_sets_raw + 1) * sizeof(List *));
2838  set_masks = palloc0((num_sets_raw + 1) * sizeof(Bitmapset *));
2839  adjacency = palloc0((num_sets_raw + 1) * sizeof(short *));
2840  adjacency_buf = palloc((num_sets_raw + 1) * sizeof(short));
2841 
2842  j_size = 0;
2843  j = 0;
2844  i = 1;
2845 
2846  for_each_cell(lc, lc1)
2847  {
2848  List *candidate = lfirst(lc);
2849  Bitmapset *candidate_set = NULL;
2850  ListCell *lc2;
2851  int dup_of = 0;
2852 
2853  foreach(lc2, candidate)
2854  {
2855  candidate_set = bms_add_member(candidate_set, lfirst_int(lc2));
2856  }
2857 
2858  /* we can only be a dup if we're the same length as a previous set */
2859  if (j_size == list_length(candidate))
2860  {
2861  int k;
2862 
2863  for (k = j; k < i; ++k)
2864  {
2865  if (bms_equal(set_masks[k], candidate_set))
2866  {
2867  dup_of = k;
2868  break;
2869  }
2870  }
2871  }
2872  else if (j_size < list_length(candidate))
2873  {
2874  j_size = list_length(candidate);
2875  j = i;
2876  }
2877 
2878  if (dup_of > 0)
2879  {
2880  orig_sets[dup_of] = lappend(orig_sets[dup_of], candidate);
2881  bms_free(candidate_set);
2882  }
2883  else
2884  {
2885  int k;
2886  int n_adj = 0;
2887 
2888  orig_sets[i] = list_make1(candidate);
2889  set_masks[i] = candidate_set;
2890 
2891  /* fill in adjacency list; no need to compare equal-size sets */
2892 
2893  for (k = j - 1; k > 0; --k)
2894  {
2895  if (bms_is_subset(set_masks[k], candidate_set))
2896  adjacency_buf[++n_adj] = k;
2897  }
2898 
2899  if (n_adj > 0)
2900  {
2901  adjacency_buf[0] = n_adj;
2902  adjacency[i] = palloc((n_adj + 1) * sizeof(short));
2903  memcpy(adjacency[i], adjacency_buf, (n_adj + 1) * sizeof(short));
2904  }
2905  else
2906  adjacency[i] = NULL;
2907 
2908  ++i;
2909  }
2910  }
2911 
2912  num_sets = i - 1;
2913 
2914  /*
2915  * Apply the graph matching algorithm to do the work.
2916  */
2917  state = BipartiteMatch(num_sets, num_sets, adjacency);
2918 
2919  /*
2920  * Now, the state->pair* fields have the info we need to assign sets to
2921  * chains. Two sets (u,v) belong to the same chain if pair_uv[u] = v or
2922  * pair_vu[v] = u (both will be true, but we check both so that we can do
2923  * it in one pass)
2924  */
2925  chains = palloc0((num_sets + 1) * sizeof(int));
2926 
2927  for (i = 1; i <= num_sets; ++i)
2928  {
2929  int u = state->pair_vu[i];
2930  int v = state->pair_uv[i];
2931 
2932  if (u > 0 && u < i)
2933  chains[i] = chains[u];
2934  else if (v > 0 && v < i)
2935  chains[i] = chains[v];
2936  else
2937  chains[i] = ++num_chains;
2938  }
2939 
2940  /* build result lists. */
2941  results = palloc0((num_chains + 1) * sizeof(List *));
2942 
2943  for (i = 1; i <= num_sets; ++i)
2944  {
2945  int c = chains[i];
2946 
2947  Assert(c > 0);
2948 
2949  results[c] = list_concat(results[c], orig_sets[i]);
2950  }
2951 
2952  /* push any empty sets back on the first list. */
2953  while (num_empty-- > 0)
2954  results[1] = lcons(NIL, results[1]);
2955 
2956  /* make result list */
2957  for (i = 1; i <= num_chains; ++i)
2958  result = lappend(result, results[i]);
2959 
2960  /*
2961  * Free all the things.
2962  *
2963  * (This is over-fussy for small sets but for large sets we could have
2964  * tied up a nontrivial amount of memory.)
2965  */
2966  BipartiteMatchFree(state);
2967  pfree(results);
2968  pfree(chains);
2969  for (i = 1; i <= num_sets; ++i)
2970  if (adjacency[i])
2971  pfree(adjacency[i]);
2972  pfree(adjacency);
2973  pfree(adjacency_buf);
2974  pfree(orig_sets);
2975  for (i = 1; i <= num_sets; ++i)
2976  bms_free(set_masks[i]);
2977  pfree(set_masks);
2978 
2979  return result;
2980 }
2981 
2982 /*
2983  * Reorder the elements of a list of grouping sets such that they have correct
2984  * prefix relationships.
2985  *
2986  * The input must be ordered with smallest sets first; the result is returned
2987  * with largest sets first. Note that the result shares no list substructure
2988  * with the input, so it's safe for the caller to modify it later.
2989  *
2990  * If we're passed in a sortclause, we follow its order of columns to the
2991  * extent possible, to minimize the chance that we add unnecessary sorts.
2992  * (We're trying here to ensure that GROUPING SETS ((a,b,c),(c)) ORDER BY c,b,a
2993  * gets implemented in one pass.)
2994  */
2995 static List *
2996 reorder_grouping_sets(List *groupingsets, List *sortclause)
2997 {
2998  ListCell *lc;
2999  ListCell *lc2;
3000  List *previous = NIL;
3001  List *result = NIL;
3002 
3003  foreach(lc, groupingsets)
3004  {
3005  List *candidate = lfirst(lc);
3006  List *new_elems = list_difference_int(candidate, previous);
3007 
3008  if (list_length(new_elems) > 0)
3009  {
3010  while (list_length(sortclause) > list_length(previous))
3011  {
3012  SortGroupClause *sc = list_nth(sortclause, list_length(previous));
3013  int ref = sc->tleSortGroupRef;
3014 
3015  if (list_member_int(new_elems, ref))
3016  {
3017  previous = lappend_int(previous, ref);
3018  new_elems = list_delete_int(new_elems, ref);
3019  }
3020  else
3021  {
3022  /* diverged from the sortclause; give up on it */
3023  sortclause = NIL;
3024  break;
3025  }
3026  }
3027 
3028  foreach(lc2, new_elems)
3029  {
3030  previous = lappend_int(previous, lfirst_int(lc2));
3031  }
3032  }
3033 
3034  result = lcons(list_copy(previous), result);
3035  list_free(new_elems);
3036  }
3037 
3038  list_free(previous);
3039 
3040  return result;
3041 }
3042 
3043 /*
3044  * Compute query_pathkeys and other pathkeys during plan generation
3045  */
3046 static void
3048 {
3049  Query *parse = root->parse;
3050  standard_qp_extra *qp_extra = (standard_qp_extra *) extra;
3051  List *tlist = qp_extra->tlist;
3052  List *activeWindows = qp_extra->activeWindows;
3053 
3054  /*
3055  * Calculate pathkeys that represent grouping/ordering requirements. The
3056  * sortClause is certainly sort-able, but GROUP BY and DISTINCT might not
3057  * be, in which case we just leave their pathkeys empty.
3058  */
3059  if (qp_extra->groupClause &&
3060  grouping_is_sortable(qp_extra->groupClause))
3061  root->group_pathkeys =
3063  qp_extra->groupClause,
3064  tlist);
3065  else
3066  root->group_pathkeys = NIL;
3067 
3068  /* We consider only the first (bottom) window in pathkeys logic */
3069  if (activeWindows != NIL)
3070  {
3071  WindowClause *wc = (WindowClause *) linitial(activeWindows);
3072 
3074  wc,
3075  tlist);
3076  }
3077  else
3078  root->window_pathkeys = NIL;
3079 
3080  if (parse->distinctClause &&
3082  root->distinct_pathkeys =
3084  parse->distinctClause,
3085  tlist);
3086  else
3087  root->distinct_pathkeys = NIL;
3088 
3089  root->sort_pathkeys =
3091  parse->sortClause,
3092  tlist);
3093 
3094  /*
3095  * Figure out whether we want a sorted result from query_planner.
3096  *
3097  * If we have a sortable GROUP BY clause, then we want a result sorted
3098  * properly for grouping. Otherwise, if we have window functions to
3099  * evaluate, we try to sort for the first window. Otherwise, if there's a
3100  * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
3101  * we try to produce output that's sufficiently well sorted for the
3102  * DISTINCT. Otherwise, if there is an ORDER BY clause, we want to sort
3103  * by the ORDER BY clause.
3104  *
3105  * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
3106  * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
3107  * that might just leave us failing to exploit an available sort order at
3108  * all. Needs more thought. The choice for DISTINCT versus ORDER BY is
3109  * much easier, since we know that the parser ensured that one is a
3110  * superset of the other.
3111  */
3112  if (root->group_pathkeys)
3113  root->query_pathkeys = root->group_pathkeys;
3114  else if (root->window_pathkeys)
3115  root->query_pathkeys = root->window_pathkeys;
3116  else if (list_length(root->distinct_pathkeys) >
3117  list_length(root->sort_pathkeys))
3118  root->query_pathkeys = root->distinct_pathkeys;
3119  else if (root->sort_pathkeys)
3120  root->query_pathkeys = root->sort_pathkeys;
3121  else
3122  root->query_pathkeys = NIL;
3123 }
3124 
3125 /*
3126  * Estimate number of groups produced by grouping clauses (1 if not grouping)
3127  *
3128  * path_rows: number of output rows from scan/join step
3129  * rollup_lists: list of grouping sets, or NIL if not doing grouping sets
3130  * rollup_groupclauses: list of grouping clauses for grouping sets,
3131  * or NIL if not doing grouping sets
3132  */
3133 static double
3135  double path_rows,
3136  List *rollup_lists,
3137  List *rollup_groupclauses)
3138 {
3139  Query *parse = root->parse;
3140  double dNumGroups;
3141 
3142  if (parse->groupClause)
3143  {
3144  List *groupExprs;
3145 
3146  if (parse->groupingSets)
3147  {
3148  /* Add up the estimates for each grouping set */
3149  ListCell *lc,
3150  *lc2;
3151 
3152  dNumGroups = 0;
3153  forboth(lc, rollup_groupclauses, lc2, rollup_lists)
3154  {
3155  List *groupClause = (List *) lfirst(lc);
3156  List *gsets = (List *) lfirst(lc2);
3157  ListCell *lc3;
3158 
3159  groupExprs = get_sortgrouplist_exprs(groupClause,
3160  parse->targetList);
3161 
3162  foreach(lc3, gsets)
3163  {
3164  List *gset = (List *) lfirst(lc3);
3165 
3166  dNumGroups += estimate_num_groups(root,
3167  groupExprs,
3168  path_rows,
3169  &gset);
3170  }
3171  }
3172  }
3173  else
3174  {
3175  /* Plain GROUP BY */
3176  groupExprs = get_sortgrouplist_exprs(parse->groupClause,
3177  parse->targetList);
3178 
3179  dNumGroups = estimate_num_groups(root, groupExprs, path_rows,
3180  NULL);
3181  }
3182  }
3183  else if (parse->groupingSets)
3184  {
3185  /* Empty grouping sets ... one result row for each one */
3186  dNumGroups = list_length(parse->groupingSets);
3187  }
3188  else if (parse->hasAggs || root->hasHavingQual)
3189  {
3190  /* Plain aggregation, one result row */
3191  dNumGroups = 1;
3192  }
3193  else
3194  {
3195  /* Not grouping */
3196  dNumGroups = 1;
3197  }
3198 
3199  return dNumGroups;
3200 }
3201 
3202 /*
3203  * estimate_hashagg_tablesize
3204  * estimate the number of bytes that a hash aggregate hashtable will
3205  * require based on the agg_costs, path width and dNumGroups.
3206  */
3207 static Size
3209  double dNumGroups)
3210 {
3211  Size hashentrysize;
3212 
3213  /* Estimate per-hash-entry space at tuple width... */
3214  hashentrysize = MAXALIGN(path->pathtarget->width) +
3216 
3217  /* plus space for pass-by-ref transition values... */
3218  hashentrysize += agg_costs->transitionSpace;
3219  /* plus the per-hash-entry overhead */
3220  hashentrysize += hash_agg_entry_size(agg_costs->numAggs);
3221 
3222  /*
3223  * Note that this disregards the effect of fill-factor and growth policy
3224  * of the hash-table. That's probably ok, given default the default
3225  * fill-factor is relatively high. It'd be hard to meaningfully factor in
3226  * "double-in-size" growth policies here.
3227  */
3228  return hashentrysize * dNumGroups;
3229 }
3230 
3231 /*
3232  * create_grouping_paths
3233  *
3234  * Build a new upperrel containing Paths for grouping and/or aggregation.
3235  *
3236  * input_rel: contains the source-data Paths
3237  * target: the pathtarget for the result Paths to compute
3238  * agg_costs: cost info about all aggregates in query (in AGGSPLIT_SIMPLE mode)
3239  * rollup_lists: list of grouping sets, or NIL if not doing grouping sets
3240  * rollup_groupclauses: list of grouping clauses for grouping sets,
3241  * or NIL if not doing grouping sets
3242  *
3243  * Note: all Paths in input_rel are expected to return the target computed
3244  * by make_group_input_target.
3245  *
3246  * We need to consider sorted and hashed aggregation in the same function,
3247  * because otherwise (1) it would be harder to throw an appropriate error
3248  * message if neither way works, and (2) we should not allow hashtable size
3249  * considerations to dissuade us from using hashing if sorting is not possible.
3250  */
3251 static RelOptInfo *
3253  RelOptInfo *input_rel,
3254  PathTarget *target,
3255  const AggClauseCosts *agg_costs,
3256  List *rollup_lists,
3257  List *rollup_groupclauses)
3258 {
3259  Query *parse = root->parse;
3260  Path *cheapest_path = input_rel->cheapest_total_path;
3261  RelOptInfo *grouped_rel;
3262  PathTarget *partial_grouping_target = NULL;
3263  AggClauseCosts agg_partial_costs; /* parallel only */
3264  AggClauseCosts agg_final_costs; /* parallel only */
3265  Size hashaggtablesize;
3266  double dNumGroups;
3267  double dNumPartialGroups = 0;
3268  bool can_hash;
3269  bool can_sort;
3270  bool try_parallel_aggregation;
3271 
3272  ListCell *lc;
3273 
3274  /* For now, do all work in the (GROUP_AGG, NULL) upperrel */
3275  grouped_rel = fetch_upper_rel(root, UPPERREL_GROUP_AGG, NULL);
3276 
3277  /*
3278  * If the input relation is not parallel-safe, then the grouped relation
3279  * can't be parallel-safe, either. Otherwise, it's parallel-safe if the
3280  * target list and HAVING quals are parallel-safe.
3281  */
3282  if (input_rel->consider_parallel &&
3283  is_parallel_safe(root, (Node *) target->exprs) &&
3284  is_parallel_safe(root, (Node *) parse->havingQual))
3285  grouped_rel->consider_parallel = true;
3286 
3287  /*
3288  * If the input rel belongs to a single FDW, so does the grouped rel.
3289  */
3290  grouped_rel->serverid = input_rel->serverid;
3291  grouped_rel->userid = input_rel->userid;
3292  grouped_rel->useridiscurrent = input_rel->useridiscurrent;
3293  grouped_rel->fdwroutine = input_rel->fdwroutine;
3294 
3295  /*
3296  * Check for degenerate grouping.
3297  */
3298  if ((root->hasHavingQual || parse->groupingSets) &&
3299  !parse->hasAggs && parse->groupClause == NIL)
3300  {
3301  /*
3302  * We have a HAVING qual and/or grouping sets, but no aggregates and
3303  * no GROUP BY (which implies that the grouping sets are all empty).
3304  *
3305  * This is a degenerate case in which we are supposed to emit either
3306  * zero or one row for each grouping set depending on whether HAVING
3307  * succeeds. Furthermore, there cannot be any variables in either
3308  * HAVING or the targetlist, so we actually do not need the FROM table
3309  * at all! We can just throw away the plan-so-far and generate a
3310  * Result node. This is a sufficiently unusual corner case that it's
3311  * not worth contorting the structure of this module to avoid having
3312  * to generate the earlier paths in the first place.
3313  */
3314  int nrows = list_length(parse->groupingSets);
3315  Path *path;
3316 
3317  if (nrows > 1)
3318  {
3319  /*
3320  * Doesn't seem worthwhile writing code to cons up a
3321  * generate_series or a values scan to emit multiple rows. Instead
3322  * just make N clones and append them. (With a volatile HAVING
3323  * clause, this means you might get between 0 and N output rows.
3324  * Offhand I think that's desired.)
3325  */
3326  List *paths = NIL;
3327 
3328  while (--nrows >= 0)
3329  {
3330  path = (Path *)
3331  create_result_path(root, grouped_rel,
3332  target,
3333  (List *) parse->havingQual);
3334  paths = lappend(paths, path);
3335  }
3336  path = (Path *)
3337  create_append_path(grouped_rel,
3338  paths,
3339  NULL,
3340  0);
3341  path->pathtarget = target;
3342  }
3343  else
3344  {
3345  /* No grouping sets, or just one, so one output row */
3346  path = (Path *)
3347  create_result_path(root, grouped_rel,
3348  target,
3349  (List *) parse->havingQual);
3350  }
3351 
3352  add_path(grouped_rel, path);
3353 
3354  /* No need to consider any other alternatives. */
3355  set_cheapest(grouped_rel);
3356 
3357  return grouped_rel;
3358  }
3359 
3360  /*
3361  * Estimate number of groups.
3362  */
3363  dNumGroups = get_number_of_groups(root,
3364  cheapest_path->rows,
3365  rollup_lists,
3366  rollup_groupclauses);
3367 
3368  /*
3369  * Determine whether it's possible to perform sort-based implementations
3370  * of grouping. (Note that if groupClause is empty,
3371  * grouping_is_sortable() is trivially true, and all the
3372  * pathkeys_contained_in() tests will succeed too, so that we'll consider
3373  * every surviving input path.)
3374  */
3375  can_sort = grouping_is_sortable(parse->groupClause);
3376 
3377  /*
3378  * Determine whether we should consider hash-based implementations of
3379  * grouping.
3380  *
3381  * Hashed aggregation only applies if we're grouping. We currently can't
3382  * hash if there are grouping sets, though.
3383  *
3384  * Executor doesn't support hashed aggregation with DISTINCT or ORDER BY
3385  * aggregates. (Doing so would imply storing *all* the input values in
3386  * the hash table, and/or running many sorts in parallel, either of which
3387  * seems like a certain loser.) We similarly don't support ordered-set
3388  * aggregates in hashed aggregation, but that case is also included in the
3389  * numOrderedAggs count.
3390  *
3391  * Note: grouping_is_hashable() is much more expensive to check than the
3392  * other gating conditions, so we want to do it last.
3393  */
3394  can_hash = (parse->groupClause != NIL &&
3395  parse->groupingSets == NIL &&
3396  agg_costs->numOrderedAggs == 0 &&
3398 
3399  /*
3400  * If grouped_rel->consider_parallel is true, then paths that we generate
3401  * for this grouping relation could be run inside of a worker, but that
3402  * doesn't mean we can actually use the PartialAggregate/FinalizeAggregate
3403  * execution strategy. Figure that out.
3404  */
3405  if (!grouped_rel->consider_parallel)
3406  {
3407  /* Not even parallel-safe. */
3408  try_parallel_aggregation = false;
3409  }
3410  else if (input_rel->partial_pathlist == NIL)
3411  {
3412  /* Nothing to use as input for partial aggregate. */
3413  try_parallel_aggregation = false;
3414  }
3415  else if (!parse->hasAggs && parse->groupClause == NIL)
3416  {
3417  /*
3418  * We don't know how to do parallel aggregation unless we have either
3419  * some aggregates or a grouping clause.
3420  */
3421  try_parallel_aggregation = false;
3422  }
3423  else if (parse->groupingSets)
3424  {
3425  /* We don't know how to do grouping sets in parallel. */
3426  try_parallel_aggregation = false;
3427  }
3428  else if (agg_costs->hasNonPartial || agg_costs->hasNonSerial)
3429  {
3430  /* Insufficient support for partial mode. */
3431  try_parallel_aggregation = false;
3432  }
3433  else
3434  {
3435  /* Everything looks good. */
3436  try_parallel_aggregation = true;
3437  }
3438 
3439  /*
3440  * Before generating paths for grouped_rel, we first generate any possible
3441  * partial paths; that way, later code can easily consider both parallel
3442  * and non-parallel approaches to grouping. Note that the partial paths
3443  * we generate here are also partially aggregated, so simply pushing a
3444  * Gather node on top is insufficient to create a final path, as would be
3445  * the case for a scan/join rel.
3446  */
3447  if (try_parallel_aggregation)
3448  {
3449  Path *cheapest_partial_path = linitial(input_rel->partial_pathlist);
3450 
3451  /*
3452  * Build target list for partial aggregate paths. These paths cannot
3453  * just emit the same tlist as regular aggregate paths, because (1) we
3454  * must include Vars and Aggrefs needed in HAVING, which might not
3455  * appear in the result tlist, and (2) the Aggrefs must be set in
3456  * partial mode.
3457  */
3458  partial_grouping_target = make_partial_grouping_target(root, target);
3459 
3460  /* Estimate number of partial groups. */
3461  dNumPartialGroups = get_number_of_groups(root,
3462  cheapest_partial_path->rows,
3463  NIL,
3464  NIL);
3465 
3466  /*
3467  * Collect statistics about aggregates for estimating costs of
3468  * performing aggregation in parallel.
3469  */
3470  MemSet(&agg_partial_costs, 0, sizeof(AggClauseCosts));
3471  MemSet(&agg_final_costs, 0, sizeof(AggClauseCosts));
3472  if (parse->hasAggs)
3473  {
3474  /* partial phase */
3475  get_agg_clause_costs(root, (Node *) partial_grouping_target->exprs,
3477  &agg_partial_costs);
3478 
3479  /* final phase */
3480  get_agg_clause_costs(root, (Node *) target->exprs,
3482  &agg_final_costs);
3483  get_agg_clause_costs(root, parse->havingQual,
3485  &agg_final_costs);
3486  }
3487 
3488  if (can_sort)
3489  {
3490  /* This was checked before setting try_parallel_aggregation */
3491  Assert(parse->hasAggs || parse->groupClause);
3492 
3493  /*
3494  * Use any available suitably-sorted path as input, and also
3495  * consider sorting the cheapest partial path.
3496  */
3497  foreach(lc, input_rel->partial_pathlist)
3498  {
3499  Path *path = (Path *) lfirst(lc);
3500  bool is_sorted;
3501 
3502  is_sorted = pathkeys_contained_in(root->group_pathkeys,
3503  path->pathkeys);
3504  if (path == cheapest_partial_path || is_sorted)
3505  {
3506  /* Sort the cheapest partial path, if it isn't already */
3507  if (!is_sorted)
3508  path = (Path *) create_sort_path(root,
3509  grouped_rel,
3510  path,
3511  root->group_pathkeys,
3512  -1.0);
3513 
3514  if (parse->hasAggs)
3515  add_partial_path(grouped_rel, (Path *)
3516  create_agg_path(root,
3517  grouped_rel,
3518  path,
3519  partial_grouping_target,
3520  parse->groupClause ? AGG_SORTED : AGG_PLAIN,
3522  parse->groupClause,
3523  NIL,
3524  &agg_partial_costs,
3525  dNumPartialGroups));
3526  else
3527  add_partial_path(grouped_rel, (Path *)
3528  create_group_path(root,
3529  grouped_rel,
3530  path,
3531  partial_grouping_target,
3532  parse->groupClause,
3533  NIL,
3534  dNumPartialGroups));
3535  }
3536  }
3537  }
3538 
3539  if (can_hash)
3540  {
3541  /* Checked above */
3542  Assert(parse->hasAggs || parse->groupClause);
3543 
3544  hashaggtablesize =
3545  estimate_hashagg_tablesize(cheapest_partial_path,
3546  &agg_partial_costs,
3547  dNumPartialGroups);
3548 
3549  /*
3550  * Tentatively produce a partial HashAgg Path, depending on if it
3551  * looks as if the hash table will fit in work_mem.
3552  */
3553  if (hashaggtablesize < work_mem * 1024L)
3554  {
3555  add_partial_path(grouped_rel, (Path *)
3556  create_agg_path(root,
3557  grouped_rel,
3558  cheapest_partial_path,
3559  partial_grouping_target,
3560  AGG_HASHED,
3562  parse->groupClause,
3563  NIL,
3564  &agg_partial_costs,
3565  dNumPartialGroups));
3566  }
3567  }
3568  }
3569 
3570  /* Build final grouping paths */
3571  if (can_sort)
3572  {
3573  /*
3574  * Use any available suitably-sorted path as input, and also consider
3575  * sorting the cheapest-total path.
3576  */
3577  foreach(lc, input_rel->pathlist)
3578  {
3579  Path *path = (Path *) lfirst(lc);
3580  bool is_sorted;
3581 
3582  is_sorted = pathkeys_contained_in(root->group_pathkeys,
3583  path->pathkeys);
3584  if (path == cheapest_path || is_sorted)
3585  {
3586  /* Sort the cheapest-total path if it isn't already sorted */
3587  if (!is_sorted)
3588  path = (Path *) create_sort_path(root,
3589  grouped_rel,
3590  path,
3591  root->group_pathkeys,
3592  -1.0);
3593 
3594  /* Now decide what to stick atop it */
3595  if (parse->groupingSets)
3596  {
3597  /*
3598  * We have grouping sets, possibly with aggregation. Make
3599  * a GroupingSetsPath.
3600  */
3601  add_path(grouped_rel, (Path *)
3603  grouped_rel,
3604  path,
3605  target,
3606  (List *) parse->havingQual,
3607  rollup_lists,
3608  rollup_groupclauses,
3609  agg_costs,
3610  dNumGroups));
3611  }
3612  else if (parse->hasAggs)
3613  {
3614  /*
3615  * We have aggregation, possibly with plain GROUP BY. Make
3616  * an AggPath.
3617  */
3618  add_path(grouped_rel, (Path *)
3619  create_agg_path(root,
3620  grouped_rel,
3621  path,
3622  target,
3623  parse->groupClause ? AGG_SORTED : AGG_PLAIN,
3625  parse->groupClause,
3626  (List *) parse->havingQual,
3627  agg_costs,
3628  dNumGroups));
3629  }
3630  else if (parse->groupClause)
3631  {
3632  /*
3633  * We have GROUP BY without aggregation or grouping sets.
3634  * Make a GroupPath.
3635  */
3636  add_path(grouped_rel, (Path *)
3637  create_group_path(root,
3638  grouped_rel,
3639  path,
3640  target,
3641  parse->groupClause,
3642  (List *) parse->havingQual,
3643  dNumGroups));
3644  }
3645  else
3646  {
3647  /* Other cases should have been handled above */
3648  Assert(false);
3649  }
3650  }
3651  }
3652 
3653  /*
3654  * Now generate a complete GroupAgg Path atop of the cheapest partial
3655  * path. We need only bother with the cheapest path here, as the
3656  * output of Gather is never sorted.
3657  */
3658  if (grouped_rel->partial_pathlist)
3659  {
3660  Path *path = (Path *) linitial(grouped_rel->partial_pathlist);
3661  double total_groups = path->rows * path->parallel_workers;
3662 
3663  path = (Path *) create_gather_path(root,
3664  grouped_rel,
3665  path,
3666  partial_grouping_target,
3667  NULL,
3668  &total_groups);
3669 
3670  /*
3671  * Since Gather's output is always unsorted, we'll need to sort,
3672  * unless there's no GROUP BY clause or a degenerate (constant)
3673  * one, in which case there will only be a single group.
3674  */
3675  if (root->group_pathkeys)
3676  path = (Path *) create_sort_path(root,
3677  grouped_rel,
3678  path,
3679  root->group_pathkeys,
3680  -1.0);
3681 
3682  if (parse->hasAggs)
3683  add_path(grouped_rel, (Path *)
3684  create_agg_path(root,
3685  grouped_rel,
3686  path,
3687  target,
3688  parse->groupClause ? AGG_SORTED : AGG_PLAIN,
3690  parse->groupClause,
3691  (List *) parse->havingQual,
3692  &agg_final_costs,
3693  dNumGroups));
3694  else
3695  add_path(grouped_rel, (Path *)
3696  create_group_path(root,
3697  grouped_rel,
3698  path,
3699  target,
3700  parse->groupClause,
3701  (List *) parse->havingQual,
3702  dNumGroups));
3703  }
3704  }
3705 
3706  if (can_hash)
3707  {
3708  hashaggtablesize = estimate_hashagg_tablesize(cheapest_path,
3709  agg_costs,
3710  dNumGroups);
3711 
3712  /*
3713  * Provided that the estimated size of the hashtable does not exceed
3714  * work_mem, we'll generate a HashAgg Path, although if we were unable
3715  * to sort above, then we'd better generate a Path, so that we at
3716  * least have one.
3717  */
3718  if (hashaggtablesize < work_mem * 1024L ||
3719  grouped_rel->pathlist == NIL)
3720  {
3721  /*
3722  * We just need an Agg over the cheapest-total input path, since
3723  * input order won't matter.
3724  */
3725  add_path(grouped_rel, (Path *)
3726  create_agg_path(root, grouped_rel,
3727  cheapest_path,
3728  target,
3729  AGG_HASHED,
3731  parse->groupClause,
3732  (List *) parse->havingQual,
3733  agg_costs,
3734  dNumGroups));
3735  }
3736 
3737  /*
3738  * Generate a HashAgg Path atop of the cheapest partial path. Once
3739  * again, we'll only do this if it looks as though the hash table
3740  * won't exceed work_mem.
3741  */
3742  if (grouped_rel->partial_pathlist)
3743  {
3744  Path *path = (Path *) linitial(grouped_rel->partial_pathlist);
3745 
3746  hashaggtablesize = estimate_hashagg_tablesize(path,
3747  &agg_final_costs,
3748  dNumGroups);
3749 
3750  if (hashaggtablesize < work_mem * 1024L)
3751  {
3752  double total_groups = path->rows * path->parallel_workers;
3753 
3754  path = (Path *) create_gather_path(root,
3755  grouped_rel,
3756  path,
3757  partial_grouping_target,
3758  NULL,
3759  &total_groups);
3760 
3761  add_path(grouped_rel, (Path *)
3762  create_agg_path(root,
3763  grouped_rel,
3764  path,
3765  target,
3766  AGG_HASHED,
3768  parse->groupClause,
3769  (List *) parse->havingQual,
3770  &agg_final_costs,
3771  dNumGroups));
3772  }
3773  }
3774  }
3775 
3776  /* Give a helpful error if we failed to find any implementation */
3777  if (grouped_rel->pathlist == NIL)
3778  ereport(ERROR,
3779  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
3780  errmsg("could not implement GROUP BY"),
3781  errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
3782 
3783  /*
3784  * If there is an FDW that's responsible for all baserels of the query,
3785  * let it consider adding ForeignPaths.
3786  */
3787  if (grouped_rel->fdwroutine &&
3788  grouped_rel->fdwroutine->GetForeignUpperPaths)
3790  input_rel, grouped_rel);
3791 
3792  /* Let extensions possibly add some more paths */
3794  (*create_upper_paths_hook) (root, UPPERREL_GROUP_AGG,
3795  input_rel, grouped_rel);
3796 
3797  /* Now choose the best path(s) */
3798  set_cheapest(grouped_rel);
3799 
3800  return grouped_rel;
3801 }
3802 
3803 /*
3804  * create_window_paths
3805  *
3806  * Build a new upperrel containing Paths for window-function evaluation.
3807  *
3808  * input_rel: contains the source-data Paths
3809  * input_target: result of make_window_input_target
3810  * output_target: what the topmost WindowAggPath should return
3811  * tlist: query's target list (needed to look up pathkeys)
3812  * wflists: result of find_window_functions
3813  * activeWindows: result of select_active_windows
3814  *
3815  * Note: all Paths in input_rel are expected to return input_target.
3816  */
3817 static RelOptInfo *
3819  RelOptInfo *input_rel,
3820  PathTarget *input_target,
3821  PathTarget *output_target,
3822  List *tlist,
3823  WindowFuncLists *wflists,
3824  List *activeWindows)
3825 {
3826  RelOptInfo *window_rel;
3827  ListCell *lc;
3828 
3829  /* For now, do all work in the (WINDOW, NULL) upperrel */
3830  window_rel = fetch_upper_rel(root, UPPERREL_WINDOW, NULL);
3831 
3832  /*
3833  * If the input relation is not parallel-safe, then the window relation
3834  * can't be parallel-safe, either. Otherwise, we need to examine the
3835  * target list and active windows for non-parallel-safe constructs.
3836  */
3837  if (input_rel->consider_parallel &&
3838  is_parallel_safe(root, (Node *) output_target->exprs) &&
3839  is_parallel_safe(root, (Node *) activeWindows))
3840  window_rel->consider_parallel = true;
3841 
3842  /*
3843  * If the input rel belongs to a single FDW, so does the window rel.
3844  */
3845  window_rel->serverid = input_rel->serverid;
3846  window_rel->userid = input_rel->userid;
3847  window_rel->useridiscurrent = input_rel->useridiscurrent;
3848  window_rel->fdwroutine = input_rel->fdwroutine;
3849 
3850  /*
3851  * Consider computing window functions starting from the existing
3852  * cheapest-total path (which will likely require a sort) as well as any
3853  * existing paths that satisfy root->window_pathkeys (which won't).
3854  */
3855  foreach(lc, input_rel->pathlist)
3856  {
3857  Path *path = (Path *) lfirst(lc);
3858 
3859  if (path == input_rel->cheapest_total_path ||
3862  window_rel,
3863  path,
3864  input_target,
3865  output_target,
3866  tlist,
3867  wflists,
3868  activeWindows);
3869  }
3870 
3871  /*
3872  * If there is an FDW that's responsible for all baserels of the query,
3873  * let it consider adding ForeignPaths.
3874  */
3875  if (window_rel->fdwroutine &&
3876  window_rel->fdwroutine->GetForeignUpperPaths)
3877  window_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_WINDOW,
3878  input_rel, window_rel);
3879 
3880  /* Let extensions possibly add some more paths */
3882  (*create_upper_paths_hook) (root, UPPERREL_WINDOW,
3883  input_rel, window_rel);
3884 
3885  /* Now choose the best path(s) */
3886  set_cheapest(window_rel);
3887 
3888  return window_rel;
3889 }
3890 
3891 /*
3892  * Stack window-function implementation steps atop the given Path, and
3893  * add the result to window_rel.
3894  *
3895  * window_rel: upperrel to contain result
3896  * path: input Path to use (must return input_target)
3897  * input_target: result of make_window_input_target
3898  * output_target: what the topmost WindowAggPath should return
3899  * tlist: query's target list (needed to look up pathkeys)
3900  * wflists: result of find_window_functions
3901  * activeWindows: result of select_active_windows
3902  */
3903 static void
3905  RelOptInfo *window_rel,
3906  Path *path,
3907  PathTarget *input_target,
3908  PathTarget *output_target,
3909  List *tlist,
3910  WindowFuncLists *wflists,
3911  List *activeWindows)
3912 {
3913  PathTarget *window_target;
3914  ListCell *l;
3915 
3916  /*
3917  * Since each window clause could require a different sort order, we stack
3918  * up a WindowAgg node for each clause, with sort steps between them as
3919  * needed. (We assume that select_active_windows chose a good order for
3920  * executing the clauses in.)
3921  *
3922  * input_target should contain all Vars and Aggs needed for the result.
3923  * (In some cases we wouldn't need to propagate all of these all the way
3924  * to the top, since they might only be needed as inputs to WindowFuncs.
3925  * It's probably not worth trying to optimize that though.) It must also
3926  * contain all window partitioning and sorting expressions, to ensure
3927  * they're computed only once at the bottom of the stack (that's critical
3928  * for volatile functions). As we climb up the stack, we'll add outputs
3929  * for the WindowFuncs computed at each level.
3930  */
3931  window_target = input_target;
3932 
3933  foreach(l, activeWindows)
3934  {
3935  WindowClause *wc = (WindowClause *) lfirst(l);
3936  List *window_pathkeys;
3937 
3938  window_pathkeys = make_pathkeys_for_window(root,
3939  wc,
3940  tlist);
3941 
3942  /* Sort if necessary */
3943  if (!pathkeys_contained_in(window_pathkeys, path->pathkeys))
3944  {
3945  path = (Path *) create_sort_path(root, window_rel,
3946  path,
3947  window_pathkeys,
3948  -1.0);
3949  }
3950 
3951  if (lnext(l))
3952  {
3953  /*
3954  * Add the current WindowFuncs to the output target for this
3955  * intermediate WindowAggPath. We must copy window_target to
3956  * avoid changing the previous path's target.
3957  *
3958  * Note: a WindowFunc adds nothing to the target's eval costs; but
3959  * we do need to account for the increase in tlist width.
3960  */
3961  ListCell *lc2;
3962 
3963  window_target = copy_pathtarget(window_target);
3964  foreach(lc2, wflists->windowFuncs[wc->winref])
3965  {
3966  WindowFunc *wfunc = (WindowFunc *) lfirst(lc2);
3967 
3968  Assert(IsA(wfunc, WindowFunc));
3969  add_column_to_pathtarget(window_target, (Expr *) wfunc, 0);
3970  window_target->width += get_typavgwidth(wfunc->wintype, -1);
3971  }
3972  }
3973  else
3974  {
3975  /* Install the goal target in the topmost WindowAgg */
3976  window_target = output_target;
3977  }
3978 
3979  path = (Path *)
3980  create_windowagg_path(root, window_rel, path, window_target,
3981  wflists->windowFuncs[wc->winref],
3982  wc,
3983  window_pathkeys);
3984  }
3985 
3986  add_path(window_rel, path);
3987 }
3988 
3989 /*
3990  * create_distinct_paths
3991  *
3992  * Build a new upperrel containing Paths for SELECT DISTINCT evaluation.
3993  *
3994  * input_rel: contains the source-data Paths
3995  *
3996  * Note: input paths should already compute the desired pathtarget, since
3997  * Sort/Unique won't project anything.
3998  */
3999 static RelOptInfo *
4001  RelOptInfo *input_rel)
4002 {
4003  Query *parse = root->parse;
4004  Path *cheapest_input_path = input_rel->cheapest_total_path;
4005  RelOptInfo *distinct_rel;
4006  double numDistinctRows;
4007  bool allow_hash;
4008  Path *path;
4009  ListCell *lc;
4010 
4011  /* For now, do all work in the (DISTINCT, NULL) upperrel */
4012  distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
4013 
4014  /*
4015  * We don't compute anything at this level, so distinct_rel will be
4016  * parallel-safe if the input rel is parallel-safe. In particular, if
4017  * there is a DISTINCT ON (...) clause, any path for the input_rel will
4018  * output those expressions, and will not be parallel-safe unless those
4019  * expressions are parallel-safe.
4020  */
4021  distinct_rel->consider_parallel = input_rel->consider_parallel;
4022 
4023  /*
4024  * If the input rel belongs to a single FDW, so does the distinct_rel.
4025  */
4026  distinct_rel->serverid = input_rel->serverid;
4027  distinct_rel->userid = input_rel->userid;
4028  distinct_rel->useridiscurrent = input_rel->useridiscurrent;
4029  distinct_rel->fdwroutine = input_rel->fdwroutine;
4030 
4031  /* Estimate number of distinct rows there will be */
4032  if (parse->groupClause || parse->groupingSets || parse->hasAggs ||
4033  root->hasHavingQual)
4034  {
4035  /*
4036  * If there was grouping or aggregation, use the number of input rows
4037  * as the estimated number of DISTINCT rows (ie, assume the input is
4038  * already mostly unique).
4039  */
4040  numDistinctRows = cheapest_input_path->rows;
4041  }
4042  else
4043  {
4044  /*
4045  * Otherwise, the UNIQUE filter has effects comparable to GROUP BY.
4046  */
4047  List *distinctExprs;
4048 
4049  distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
4050  parse->targetList);
4051  numDistinctRows = estimate_num_groups(root, distinctExprs,
4052  cheapest_input_path->rows,
4053  NULL);
4054  }
4055 
4056  /*
4057  * Consider sort-based implementations of DISTINCT, if possible.
4058  */
4060  {
4061  /*
4062  * First, if we have any adequately-presorted paths, just stick a
4063  * Unique node on those. Then consider doing an explicit sort of the
4064  * cheapest input path and Unique'ing that.
4065  *
4066  * When we have DISTINCT ON, we must sort by the more rigorous of
4067  * DISTINCT and ORDER BY, else it won't have the desired behavior.
4068  * Also, if we do have to do an explicit sort, we might as well use
4069  * the more rigorous ordering to avoid a second sort later. (Note
4070  * that the parser will have ensured that one clause is a prefix of
4071  * the other.)
4072  */
4073  List *needed_pathkeys;
4074 
4075  if (parse->hasDistinctOn &&
4077  list_length(root->sort_pathkeys))
4078  needed_pathkeys = root->sort_pathkeys;
4079  else
4080  needed_pathkeys = root->distinct_pathkeys;
4081 
4082  foreach(lc, input_rel->pathlist)
4083  {
4084  Path *path = (Path *) lfirst(lc);
4085 
4086  if (pathkeys_contained_in(needed_pathkeys, path->pathkeys))
4087  {
4088  add_path(distinct_rel, (Path *)
4089  create_upper_unique_path(root, distinct_rel,
4090  path,
4092  numDistinctRows));
4093  }
4094  }
4095 
4096  /* For explicit-sort case, always use the more rigorous clause */
4097  if (list_length(root->distinct_pathkeys) <
4098  list_length(root->sort_pathkeys))
4099  {
4100  needed_pathkeys = root->sort_pathkeys;
4101  /* Assert checks that parser didn't mess up... */
4103  needed_pathkeys));
4104  }
4105  else
4106  needed_pathkeys = root->distinct_pathkeys;
4107 
4108  path = cheapest_input_path;
4109  if (!pathkeys_contained_in(needed_pathkeys, path->pathkeys))
4110  path = (Path *) create_sort_path(root, distinct_rel,
4111  path,
4112  needed_pathkeys,
4113  -1.0);
4114 
4115  add_path(distinct_rel, (Path *)
4116  create_upper_unique_path(root, distinct_rel,
4117  path,
4119  numDistinctRows));
4120  }
4121 
4122  /*
4123  * Consider hash-based implementations of DISTINCT, if possible.
4124  *
4125  * If we were not able to make any other types of path, we *must* hash or
4126  * die trying. If we do have other choices, there are several things that
4127  * should prevent selection of hashing: if the query uses DISTINCT ON
4128  * (because it won't really have the expected behavior if we hash), or if
4129  * enable_hashagg is off, or if it looks like the hashtable will exceed
4130  * work_mem.
4131  *
4132  * Note: grouping_is_hashable() is much more expensive to check than the
4133  * other gating conditions, so we want to do it last.
4134  */
4135  if (distinct_rel->pathlist == NIL)
4136  allow_hash = true; /* we have no alternatives */
4137  else if (parse->hasDistinctOn || !enable_hashagg)
4138  allow_hash = false; /* policy-based decision not to hash */
4139  else
4140  {
4141  Size hashentrysize;
4142 
4143  /* Estimate per-hash-entry space at tuple width... */
4144  hashentrysize = MAXALIGN(cheapest_input_path->pathtarget->width) +
4146  /* plus the per-hash-entry overhead */
4147  hashentrysize += hash_agg_entry_size(0);
4148 
4149  /* Allow hashing only if hashtable is predicted to fit in work_mem */
4150  allow_hash = (hashentrysize * numDistinctRows <= work_mem * 1024L);
4151  }
4152 
4153  if (allow_hash && grouping_is_hashable(parse->distinctClause))
4154  {
4155  /* Generate hashed aggregate path --- no sort needed */
4156  add_path(distinct_rel, (Path *)
4157  create_agg_path(root,
4158  distinct_rel,
4159  cheapest_input_path,
4160  cheapest_input_path->pathtarget,
4161  AGG_HASHED,
4163  parse->distinctClause,
4164  NIL,
4165  NULL,
4166  numDistinctRows));
4167  }
4168 
4169  /* Give a helpful error if we failed to find any implementation */
4170  if (distinct_rel->pathlist == NIL)
4171  ereport(ERROR,
4172  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
4173  errmsg("could not implement DISTINCT"),
4174  errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
4175 
4176  /*
4177  * If there is an FDW that's responsible for all baserels of the query,
4178  * let it consider adding ForeignPaths.
4179  */
4180  if (distinct_rel->fdwroutine &&
4181  distinct_rel->fdwroutine->GetForeignUpperPaths)
4182  distinct_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_DISTINCT,
4183  input_rel, distinct_rel);
4184 
4185  /* Let extensions possibly add some more paths */
4187  (*create_upper_paths_hook) (root, UPPERREL_DISTINCT,
4188  input_rel, distinct_rel);
4189 
4190  /* Now choose the best path(s) */
4191  set_cheapest(distinct_rel);
4192 
4193  return distinct_rel;
4194 }
4195 
4196 /*
4197  * create_ordered_paths
4198  *
4199  * Build a new upperrel containing Paths for ORDER BY evaluation.
4200  *
4201  * All paths in the result must satisfy the ORDER BY ordering.
4202  * The only new path we need consider is an explicit sort on the
4203  * cheapest-total existing path.
4204  *
4205  * input_rel: contains the source-data Paths
4206  * target: the output tlist the result Paths must emit
4207  * limit_tuples: estimated bound on the number of output tuples,
4208  * or -1 if no LIMIT or couldn't estimate
4209  */
4210 static RelOptInfo *
4212  RelOptInfo *input_rel,
4213  PathTarget *target,
4214  double limit_tuples)
4215 {
4216  Path *cheapest_input_path = input_rel->cheapest_total_path;
4217  RelOptInfo *ordered_rel;
4218  ListCell *lc;
4219 
4220  /* For now, do all work in the (ORDERED, NULL) upperrel */
4221  ordered_rel = fetch_upper_rel(root, UPPERREL_ORDERED, NULL);
4222 
4223  /*
4224  * If the input relation is not parallel-safe, then the ordered relation
4225  * can't be parallel-safe, either. Otherwise, it's parallel-safe if the
4226  * target list is parallel-safe.
4227  */
4228  if (input_rel->consider_parallel &&
4229  is_parallel_safe(root, (Node *) target->exprs))
4230  ordered_rel->consider_parallel = true;
4231 
4232  /*
4233  * If the input rel belongs to a single FDW, so does the ordered_rel.
4234  */
4235  ordered_rel->serverid = input_rel->serverid;
4236  ordered_rel->userid = input_rel->userid;
4237  ordered_rel->useridiscurrent = input_rel->useridiscurrent;
4238  ordered_rel->fdwroutine = input_rel->fdwroutine;
4239 
4240  foreach(lc, input_rel->pathlist)
4241  {
4242  Path *path = (Path *) lfirst(lc);
4243  bool is_sorted;
4244 
4245  is_sorted = pathkeys_contained_in(root->sort_pathkeys,
4246  path->pathkeys);
4247  if (path == cheapest_input_path || is_sorted)
4248  {
4249  if (!is_sorted)
4250  {
4251  /* An explicit sort here can take advantage of LIMIT */
4252  path = (Path *) create_sort_path(root,
4253  ordered_rel,
4254  path,
4255  root->sort_pathkeys,
4256  limit_tuples);
4257  }
4258 
4259  /* Add projection step if needed */
4260  if (path->pathtarget != target)
4261  path = apply_projection_to_path(root, ordered_rel,
4262  path, target);
4263 
4264  add_path(ordered_rel, path);
4265  }
4266  }
4267 
4268  /*
4269  * If there is an FDW that's responsible for all baserels of the query,
4270  * let it consider adding ForeignPaths.
4271  */
4272  if (ordered_rel->fdwroutine &&
4273  ordered_rel->fdwroutine->GetForeignUpperPaths)
4274  ordered_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_ORDERED,
4275  input_rel, ordered_rel);
4276 
4277  /* Let extensions possibly add some more paths */
4279  (*create_upper_paths_hook) (root, UPPERREL_ORDERED,
4280  input_rel, ordered_rel);
4281 
4282  /*
4283  * No need to bother with set_cheapest here; grouping_planner does not
4284  * need us to do it.
4285  */
4286  Assert(ordered_rel->pathlist != NIL);
4287 
4288  return ordered_rel;
4289 }
4290 
4291 
4292 /*
4293  * make_group_input_target
4294  * Generate appropriate PathTarget for initial input to grouping nodes.
4295  *
4296  * If there is grouping or aggregation, the scan/join subplan cannot emit
4297  * the query's final targetlist; for example, it certainly can't emit any
4298  * aggregate function calls. This routine generates the correct target
4299  * for the scan/join subplan.
4300  *
4301  * The query target list passed from the parser already contains entries
4302  * for all ORDER BY and GROUP BY expressions, but it will not have entries
4303  * for variables used only in HAVING clauses; so we need to add those
4304  * variables to the subplan target list. Also, we flatten all expressions
4305  * except GROUP BY items into their component variables; other expressions
4306  * will be computed by the upper plan nodes rather than by the subplan.
4307  * For example, given a query like
4308  * SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
4309  * we want to pass this targetlist to the subplan:
4310  * a+b,c,d
4311  * where the a+b target will be used by the Sort/Group steps, and the
4312  * other targets will be used for computing the final results.
4313  *
4314  * 'final_target' is the query's final target list (in PathTarget form)
4315  *
4316  * The result is the PathTarget to be computed by the Paths returned from
4317  * query_planner().
4318  */
4319 static PathTarget *
4321 {
4322  Query *parse = root->parse;
4323  PathTarget *input_target;
4324  List *non_group_cols;
4325  List *non_group_vars;
4326  int i;
4327  ListCell *lc;
4328 
4329  /*
4330  * We must build a target containing all grouping columns, plus any other
4331  * Vars mentioned in the query's targetlist and HAVING qual.
4332  */
4333  input_target = create_empty_pathtarget();
4334  non_group_cols = NIL;
4335 
4336  i = 0;
4337  foreach(lc, final_target->exprs)
4338  {
4339  Expr *expr = (Expr *) lfirst(lc);
4340  Index sgref = get_pathtarget_sortgroupref(final_target, i);
4341 
4342  if (sgref && parse->groupClause &&
4344  {
4345  /*
4346  * It's a grouping column, so add it to the input target as-is.
4347  */
4348  add_column_to_pathtarget(input_target, expr, sgref);
4349  }
4350  else
4351  {
4352  /*
4353  * Non-grouping column, so just remember the expression for later
4354  * call to pull_var_clause.
4355  */
4356  non_group_cols = lappend(non_group_cols, expr);
4357  }
4358 
4359  i++;
4360  }
4361 
4362  /*
4363  * If there's a HAVING clause, we'll need the Vars it uses, too.
4364  */
4365  if (parse->havingQual)
4366  non_group_cols = lappend(non_group_cols, parse->havingQual);
4367 
4368  /*
4369  * Pull out all the Vars mentioned in non-group cols (plus HAVING), and
4370  * add them to the input target if not already present. (A Var used
4371  * directly as a GROUP BY item will be present already.) Note this
4372  * includes Vars used in resjunk items, so we are covering the needs of
4373  * ORDER BY and window specifications. Vars used within Aggrefs and
4374  * WindowFuncs will be pulled out here, too.
4375  */
4376  non_group_vars = pull_var_clause((Node *) non_group_cols,
4380  add_new_columns_to_pathtarget(input_target, non_group_vars);
4381 
4382  /* clean up cruft */
4383  list_free(non_group_vars);
4384  list_free(non_group_cols);
4385 
4386  /* XXX this causes some redundant cost calculation ... */
4387  return set_pathtarget_cost_width(root, input_target);
4388 }
4389 
4390 /*
4391  * make_partial_grouping_target
4392  * Generate appropriate PathTarget for output of partial aggregate
4393  * (or partial grouping, if there are no aggregates) nodes.
4394  *
4395  * A partial aggregation node needs to emit all the same aggregates that
4396  * a regular aggregation node would, plus any aggregates used in HAVING;
4397  * except that the Aggref nodes should be marked as partial aggregates.
4398  *
4399  * In addition, we'd better emit any Vars and PlaceholderVars that are
4400  * used outside of Aggrefs in the aggregation tlist and HAVING. (Presumably,
4401  * these would be Vars that are grouped by or used in grouping expressions.)
4402  *
4403  * grouping_target is the tlist to be emitted by the topmost aggregation step.
4404  * We get the HAVING clause out of *root.
4405  */
4406 static PathTarget *
4408 {
4409  Query *parse = root->parse;
4410  PathTarget *partial_target;
4411  List *non_group_cols;
4412  List *non_group_exprs;
4413  int i;
4414  ListCell *lc;
4415 
4416  partial_target = create_empty_pathtarget();
4417  non_group_cols = NIL;
4418 
4419  i = 0;
4420  foreach(lc, grouping_target->exprs)
4421  {
4422  Expr *expr = (Expr *) lfirst(lc);
4423  Index sgref = get_pathtarget_sortgroupref(grouping_target, i);
4424 
4425  if (sgref && parse->groupClause &&
4427  {
4428  /*
4429  * It's a grouping column, so add it to the partial_target as-is.
4430  * (This allows the upper agg step to repeat the grouping calcs.)
4431  */
4432  add_column_to_pathtarget(partial_target, expr, sgref);
4433  }
4434  else
4435  {
4436  /*
4437  * Non-grouping column, so just remember the expression for later
4438  * call to pull_var_clause.
4439  */
4440  non_group_cols = lappend(non_group_cols, expr);
4441  }
4442 
4443  i++;
4444  }
4445 
4446  /*
4447  * If there's a HAVING clause, we'll need the Vars/Aggrefs it uses, too.
4448  */
4449  if (parse->havingQual)
4450  non_group_cols = lappend(non_group_cols, parse->havingQual);
4451 
4452  /*
4453  * Pull out all the Vars, PlaceHolderVars, and Aggrefs mentioned in
4454  * non-group cols (plus HAVING), and add them to the partial_target if not
4455  * already present. (An expression used directly as a GROUP BY item will
4456  * be present already.) Note this includes Vars used in resjunk items, so
4457  * we are covering the needs of ORDER BY and window specifications.
4458  */
4459  non_group_exprs = pull_var_clause((Node *) non_group_cols,
4463 
4464  add_new_columns_to_pathtarget(partial_target, non_group_exprs);
4465 
4466  /*
4467  * Adjust Aggrefs to put them in partial mode. At this point all Aggrefs
4468  * are at the top level of the target list, so we can just scan the list
4469  * rather than recursing through the expression trees.
4470  */
4471  foreach(lc, partial_target->exprs)
4472  {
4473  Aggref *aggref = (Aggref *) lfirst(lc);
4474 
4475  if (IsA(aggref, Aggref))
4476  {
4477  Aggref *newaggref;
4478 
4479  /*
4480  * We shouldn't need to copy the substructure of the Aggref node,
4481  * but flat-copy the node itself to avoid damaging other trees.
4482  */
4483  newaggref = makeNode(Aggref);
4484  memcpy(newaggref, aggref, sizeof(Aggref));
4485 
4486  /* For now, assume serialization is required */
4488 
4489  lfirst(lc) = newaggref;
4490  }
4491  }
4492 
4493  /* clean up cruft */
4494  list_free(non_group_exprs);
4495  list_free(non_group_cols);
4496 
4497  /* XXX this causes some redundant cost calculation ... */
4498  return set_pathtarget_cost_width(root, partial_target);
4499 }
4500 
4501 /*
4502  * mark_partial_aggref
4503  * Adjust an Aggref to make it represent a partial-aggregation step.
4504  *
4505  * The Aggref node is modified in-place; caller must do any copying required.
4506  */
4507 void
4509 {
4510  /* aggtranstype should be computed by this point */
4512  /* ... but aggsplit should still be as the parser left it */
4513  Assert(agg->aggsplit == AGGSPLIT_SIMPLE);
4514 
4515  /* Mark the Aggref with the intended partial-aggregation mode */
4516  agg->aggsplit = aggsplit;
4517 
4518  /*
4519  * Adjust result type if needed. Normally, a partial aggregate returns
4520  * the aggregate's transition type; but if that's INTERNAL and we're
4521  * serializing, it returns BYTEA instead.
4522  */
4523  if (DO_AGGSPLIT_SKIPFINAL(aggsplit))
4524  {
4525  if (agg->aggtranstype == INTERNALOID && DO_AGGSPLIT_SERIALIZE(aggsplit))
4526  agg->aggtype = BYTEAOID;
4527  else
4528  agg->aggtype = agg->aggtranstype;
4529  }
4530 }
4531 
4532 /*
4533  * postprocess_setop_tlist
4534  * Fix up targetlist returned by plan_set_operations().
4535  *
4536  * We need to transpose sort key info from the orig_tlist into new_tlist.
4537  * NOTE: this would not be good enough if we supported resjunk sort keys
4538  * for results of set operations --- then, we'd need to project a whole
4539  * new tlist to evaluate the resjunk columns. For now, just ereport if we
4540  * find any resjunk columns in orig_tlist.
4541  */
4542 static List *
4543 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
4544 {
4545  ListCell *l;
4546  ListCell *orig_tlist_item = list_head(orig_tlist);
4547 
4548  foreach(l, new_tlist)
4549  {
4550  TargetEntry *new_tle = (TargetEntry *) lfirst(l);
4551  TargetEntry *orig_tle;
4552 
4553  /* ignore resjunk columns in setop result */
4554  if (new_tle->resjunk)
4555  continue;
4556 
4557  Assert(orig_tlist_item != NULL);
4558  orig_tle = (TargetEntry *) lfirst(orig_tlist_item);
4559  orig_tlist_item = lnext(orig_tlist_item);
4560  if (orig_tle->resjunk) /* should not happen */
4561  elog(ERROR, "resjunk output columns are not implemented");
4562  Assert(new_tle->resno == orig_tle->resno);
4563  new_tle->ressortgroupref = orig_tle->ressortgroupref;
4564  }
4565  if (orig_tlist_item != NULL)
4566  elog(ERROR, "resjunk output columns are not implemented");
4567  return new_tlist;
4568 }
4569 
4570 /*
4571  * select_active_windows
4572  * Create a list of the "active" window clauses (ie, those referenced
4573  * by non-deleted WindowFuncs) in the order they are to be executed.
4574  */
4575 static List *
4577 {
4578  List *result;
4579  List *actives;
4580  ListCell *lc;
4581 
4582  /* First, make a list of the active windows */
4583  actives = NIL;
4584  foreach(lc, root->parse->windowClause)
4585  {
4586  WindowClause *wc = (WindowClause *) lfirst(lc);
4587 
4588  /* It's only active if wflists shows some related WindowFuncs */
4589  Assert(wc->winref <= wflists->maxWinRef);
4590  if (wflists->windowFuncs[wc->winref] != NIL)
4591  actives = lappend(actives, wc);
4592  }
4593 
4594  /*
4595  * Now, ensure that windows with identical partitioning/ordering clauses
4596  * are adjacent in the list. This is required by the SQL standard, which
4597  * says that only one sort is to be used for such windows, even if they
4598  * are otherwise distinct (eg, different names or framing clauses).
4599  *
4600  * There is room to be much smarter here, for example detecting whether
4601  * one window's sort keys are a prefix of another's (so that sorting for
4602  * the latter would do for the former), or putting windows first that
4603  * match a sort order available for the underlying query. For the moment
4604  * we are content with meeting the spec.
4605  */
4606  result = NIL;
4607  while (actives != NIL)
4608  {
4609  WindowClause *wc = (WindowClause *) linitial(actives);
4610  ListCell *prev;
4611  ListCell *next;
4612 
4613  /* Move wc from actives to result */
4614  actives = list_delete_first(actives);
4615  result = lappend(result, wc);
4616 
4617  /* Now move any matching windows from actives to result */
4618  prev = NULL;
4619  for (lc = list_head(actives); lc; lc = next)
4620  {
4621  WindowClause *wc2 = (WindowClause *) lfirst(lc);
4622 
4623  next = lnext(lc);
4624  /* framing options are NOT to be compared here! */
4625  if (equal(wc->partitionClause, wc2->partitionClause) &&
4626  equal(wc->orderClause, wc2->orderClause))
4627  {
4628  actives = list_delete_cell(actives, lc, prev);
4629  result = lappend(result, wc2);
4630  }
4631  else
4632  prev = lc;
4633  }
4634  }
4635 
4636  return result;
4637 }
4638 
4639 /*
4640  * make_window_input_target
4641  * Generate appropriate PathTarget for initial input to WindowAgg nodes.
4642  *
4643  * When the query has window functions, this function computes the desired
4644  * target to be computed by the node just below the first WindowAgg.
4645  * This tlist must contain all values needed to evaluate the window functions,
4646  * compute the final target list, and perform any required final sort step.
4647  * If multiple WindowAggs are needed, each intermediate one adds its window
4648  * function results onto this base tlist; only the topmost WindowAgg computes
4649  * the actual desired target list.
4650  *
4651  * This function is much like make_group_input_target, though not quite enough
4652  * like it to share code. As in that function, we flatten most expressions
4653  * into their component variables. But we do not want to flatten window
4654  * PARTITION BY/ORDER BY clauses, since that might result in multiple
4655  * evaluations of them, which would be bad (possibly even resulting in
4656  * inconsistent answers, if they contain volatile functions).
4657  * Also, we must not flatten GROUP BY clauses that were left unflattened by
4658  * make_group_input_target, because we may no longer have access to the
4659  * individual Vars in them.
4660  *
4661  * Another key difference from make_group_input_target is that we don't
4662  * flatten Aggref expressions, since those are to be computed below the
4663  * window functions and just referenced like Vars above that.
4664  *
4665  * 'final_target' is the query's final target list (in PathTarget form)
4666  * 'activeWindows' is the list of active windows previously identified by
4667  * select_active_windows.
4668  *
4669  * The result is the PathTarget to be computed by the plan node immediately
4670  * below the first WindowAgg node.
4671  */
4672 static PathTarget *
4674  PathTarget *final_target,
4675  List *activeWindows)
4676 {
4677  Query *parse = root->parse;
4678  PathTarget *input_target;
4679  Bitmapset *sgrefs;
4680  List *flattenable_cols;
4681  List *flattenable_vars;
4682  int i;
4683  ListCell *lc;
4684 
4685  Assert(parse->hasWindowFuncs);
4686 
4687  /*
4688  * Collect the sortgroupref numbers of window PARTITION/ORDER BY clauses
4689  * into a bitmapset for convenient reference below.
4690  */
4691  sgrefs = NULL;
4692  foreach(lc, activeWindows)
4693  {
4694  WindowClause *wc = (WindowClause *) lfirst(lc);
4695  ListCell *lc2;
4696 
4697  foreach(lc2, wc->partitionClause)
4698  {
4699  SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
4700 
4701  sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
4702  }
4703  foreach(lc2, wc->orderClause)
4704  {
4705  SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
4706 
4707  sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
4708  }
4709  }
4710 
4711  /* Add in sortgroupref numbers of GROUP BY clauses, too */
4712  foreach(lc, parse->groupClause)
4713  {
4714  SortGroupClause *grpcl = (SortGroupClause *) lfirst(lc);
4715 
4716  sgrefs = bms_add_member(sgrefs, grpcl->tleSortGroupRef);
4717  }
4718 
4719  /*
4720  * Construct a target containing all the non-flattenable targetlist items,
4721  * and save aside the others for a moment.
4722  */
4723  input_target = create_empty_pathtarget();
4724  flattenable_cols = NIL;
4725 
4726  i = 0;
4727  foreach(lc, final_target->exprs)
4728  {
4729  Expr *expr = (Expr *) lfirst(lc);
4730  Index sgref = get_pathtarget_sortgroupref(final_target, i);
4731 
4732  /*
4733  * Don't want to deconstruct window clauses or GROUP BY items. (Note
4734  * that such items can't contain window functions, so it's okay to
4735  * compute them below the WindowAgg nodes.)
4736  */
4737  if (sgref != 0 && bms_is_member(sgref, sgrefs))
4738  {
4739  /*
4740  * Don't want to deconstruct this value, so add it to the input
4741  * target as-is.
4742  */
4743  add_column_to_pathtarget(input_target, expr, sgref);
4744  }
4745  else
4746  {
4747  /*
4748  * Column is to be flattened, so just remember the expression for
4749  * later call to pull_var_clause.
4750  */
4751  flattenable_cols = lappend(flattenable_cols, expr);
4752  }
4753 
4754  i++;
4755  }
4756 
4757  /*
4758  * Pull out all the Vars and Aggrefs mentioned in flattenable columns, and
4759  * add them to the input target if not already present. (Some might be
4760  * there already because they're used directly as window/group clauses.)
4761  *
4762  * Note: it's essential to use PVC_INCLUDE_AGGREGATES here, so that any
4763  * Aggrefs are placed in the Agg node's tlist and not left to be computed
4764  * at higher levels. On the other hand, we should recurse into
4765  * WindowFuncs to make sure their input expressions are available.
4766  */
4767  flattenable_vars = pull_var_clause((Node *) flattenable_cols,
4771  add_new_columns_to_pathtarget(input_target, flattenable_vars);
4772 
4773  /* clean up cruft */
4774  list_free(flattenable_vars);
4775  list_free(flattenable_cols);
4776 
4777  /* XXX this causes some redundant cost calculation ... */
4778  return set_pathtarget_cost_width(root, input_target);
4779 }
4780 
4781 /*
4782  * make_pathkeys_for_window
4783  * Create a pathkeys list describing the required input ordering
4784  * for the given WindowClause.
4785  *
4786  * The required ordering is first the PARTITION keys, then the ORDER keys.
4787  * In the future we might try to implement windowing using hashing, in which
4788  * case the ordering could be relaxed, but for now we always sort.
4789  *
4790  * Caution: if you change this, see createplan.c's get_column_info_for_window!
4791  */
4792 static List *
4794  List *tlist)
4795 {
4796  List *window_pathkeys;
4797  List *window_sortclauses;
4798 
4799  /* Throw error if can't sort */
4801  ereport(ERROR,
4802  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
4803  errmsg("could not implement window PARTITION BY"),
4804  errdetail("Window partitioning columns must be of sortable datatypes.")));
4806  ereport(ERROR,
4807  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
4808  errmsg("could not implement window ORDER BY"),
4809  errdetail("Window ordering columns must be of sortable datatypes.")));
4810 
4811  /* Okay, make the combined pathkeys */
4812  window_sortclauses = list_concat(list_copy(wc->partitionClause),
4813  list_copy(wc->orderClause));
4814  window_pathkeys = make_pathkeys_for_sortclauses(root,
4815  window_sortclauses,
4816  tlist);
4817  list_free(window_sortclauses);
4818  return window_pathkeys;
4819 }
4820 
4821 /*
4822  * make_sort_input_target
4823  * Generate appropriate PathTarget for initial input to Sort step.
4824  *
4825  * If the query has ORDER BY, this function chooses the target to be computed
4826  * by the node just below the Sort (and DISTINCT, if any, since Unique can't
4827  * project) steps. This might or might not be identical to the query's final
4828  * output target.
4829  *
4830  * The main argument for keeping the sort-input tlist the same as the final
4831  * is that we avoid a separate projection node (which will be needed if
4832  * they're different, because Sort can't project). However, there are also
4833  * advantages to postponing tlist evaluation till after the Sort: it ensures
4834  * a consistent order of evaluation for any volatile functions in the tlist,
4835  * and if there's also a LIMIT, we can stop the query without ever computing
4836  * tlist functions for later rows, which is beneficial for both volatile and
4837  * expensive functions.
4838  *
4839  * Our current policy is to postpone volatile expressions till after the sort
4840  * unconditionally (assuming that that's possible, ie they are in plain tlist
4841  * columns and not ORDER BY/GROUP BY/DISTINCT columns). We also prefer to
4842  * postpone set-returning expressions, because running them beforehand would
4843  * bloat the sort dataset, and because it might cause unexpected output order
4844  * if the sort isn't stable. However there's a constraint on that: all SRFs
4845  * in the tlist should be evaluated at the same plan step, so that they can
4846  * run in sync in ExecTargetList. So if any SRFs are in sort columns, we
4847  * mustn't postpone any SRFs. (Note that in principle that policy should
4848  * probably get applied to the group/window input targetlists too, but we
4849  * have not done that historically.) Lastly, expensive expressions are
4850  * postponed if there is a LIMIT, or if root->tuple_fraction shows that
4851  * partial evaluation of the query is possible (if neither is true, we expect
4852  * to have to evaluate the expressions for every row anyway), or if there are
4853  * any volatile or set-returning expressions (since once we've put in a
4854  * projection at all, it won't cost any more to postpone more stuff).
4855  *
4856  * Another issue that could potentially be considered here is that
4857  * evaluating tlist expressions could result in data that's either wider
4858  * or narrower than the input Vars, thus changing the volume of data that
4859  * has to go through the Sort. However, we usually have only a very bad
4860  * idea of the output width of any expression more complex than a Var,
4861  * so for now it seems too risky to try to optimize on that basis.
4862  *
4863  * Note that if we do produce a modified sort-input target, and then the
4864  * query ends up not using an explicit Sort, no particular harm is done:
4865  * we'll initially use the modified target for the preceding path nodes,
4866  * but then change them to the final target with apply_projection_to_path.
4867  * Moreover, in such a case the guarantees about evaluation order of
4868  * volatile functions still hold, since the rows are sorted already.
4869  *
4870  * This function has some things in common with make_group_input_target and
4871  * make_window_input_target, though the detailed rules for what to do are
4872  * different. We never flatten/postpone any grouping or ordering columns;
4873  * those are needed before the sort. If we do flatten a particular
4874  * expression, we leave Aggref and WindowFunc nodes alone, since those were
4875  * computed earlier.
4876  *
4877  * 'final_target' is the query's final target list (in PathTarget form)
4878  * 'have_postponed_srfs' is an output argument, see below
4879  *
4880  * The result is the PathTarget to be computed by the plan node immediately
4881  * below the Sort step (and the Distinct step, if any). This will be
4882  * exactly final_target if we decide a projection step wouldn't be helpful.
4883  *
4884  * In addition, *have_postponed_srfs is set to TRUE if we choose to postpone
4885  * any set-returning functions to after the Sort.
4886  */
4887 static PathTarget *
4889  PathTarget *final_target,
4890  bool *have_postponed_srfs)
4891 {
4892  Query *parse = root->parse;
4893  PathTarget *input_target;
4894  int ncols;
4895  bool *col_is_srf;
4896  bool *postpone_col;
4897  bool have_srf;
4898  bool have_volatile;
4899  bool have_expensive;
4900  bool have_srf_sortcols;
4901  bool postpone_srfs;
4902  List *postponable_cols;
4903  List *postponable_vars;
4904  int i;
4905  ListCell *lc;
4906 
4907  /* Shouldn't get here unless query has ORDER BY */
4908  Assert(parse->sortClause);
4909 
4910  *have_postponed_srfs = false; /* default result */
4911 
4912  /* Inspect tlist and collect per-column information */
4913  ncols = list_length(final_target->exprs);
4914  col_is_srf = (bool *) palloc0(ncols * sizeof(bool));
4915  postpone_col = (bool *) palloc0(ncols * sizeof(bool));
4916  have_srf = have_volatile = have_expensive = have_srf_sortcols = false;
4917 
4918  i = 0;
4919  foreach(lc, final_target->exprs)
4920  {
4921  Expr *expr = (Expr *) lfirst(lc);
4922 
4923  /*
4924  * If the column has a sortgroupref, assume it has to be evaluated
4925  * before sorting. Generally such columns would be ORDER BY, GROUP
4926  * BY, etc targets. One exception is columns that were removed from
4927  * GROUP BY by remove_useless_groupby_columns() ... but those would
4928  * only be Vars anyway. There don't seem to be any cases where it
4929  * would be worth the trouble to double-check.
4930  */
4931  if (get_pathtarget_sortgroupref(final_target, i) == 0)
4932  {
4933  /*
4934  * Check for SRF or volatile functions. Check the SRF case first
4935  * because we must know whether we have any postponed SRFs.
4936  */
4937  if (parse->hasTargetSRFs &&
4938  expression_returns_set((Node *) expr))
4939  {
4940  /* We'll decide below whether these are postponable */
4941  col_is_srf[i] = true;
4942  have_srf = true;
4943  }
4944  else if (contain_volatile_functions((Node *) expr))
4945  {
4946  /* Unconditionally postpone */
4947  postpone_col[i] = true;
4948  have_volatile = true;
4949  }
4950  else
4951  {
4952  /*
4953  * Else check the cost. XXX it's annoying to have to do this
4954  * when set_pathtarget_cost_width() just did it. Refactor to
4955  * allow sharing the work?
4956  */
4957  QualCost cost;
4958 
4959  cost_qual_eval_node(&cost, (Node *) expr, root);
4960 
4961  /*
4962  * We arbitrarily define "expensive" as "more than 10X
4963  * cpu_operator_cost". Note this will take in any PL function
4964  * with default cost.
4965  */
4966  if (cost.per_tuple > 10 * cpu_operator_cost)
4967  {
4968  postpone_col[i] = true;
4969  have_expensive = true;
4970  }
4971  }
4972  }
4973  else
4974  {
4975  /* For sortgroupref cols, just check if any contain SRFs */
4976  if (!have_srf_sortcols &&
4977  parse->hasTargetSRFs &&
4978  expression_returns_set((Node *) expr))
4979  have_srf_sortcols = true;
4980  }
4981 
4982  i++;
4983  }
4984 
4985  /*
4986  * We can postpone SRFs if we have some but none are in sortgroupref cols.
4987  */
4988  postpone_srfs = (have_srf && !have_srf_sortcols);
4989 
4990  /*
4991  * If we don't need a post-sort projection, just return final_target.
4992  */
4993  if (!(postpone_srfs || have_volatile ||
4994  (have_expensive &&
4995  (parse->limitCount || root->tuple_fraction > 0))))
4996  return final_target;
4997 
4998  /*
4999  * Report whether the post-sort projection will contain set-returning
5000  * functions. This is important because it affects whether the Sort can
5001  * rely on the query's LIMIT (if any) to bound the number of rows it needs
5002  * to return.
5003  */
5004  *have_postponed_srfs = postpone_srfs;
5005 
5006  /*
5007  * Construct the sort-input target, taking all non-postponable columns and
5008  * then adding Vars, PlaceHolderVars, Aggrefs, and WindowFuncs found in
5009  * the postponable ones.
5010  */
5011  input_target = create_empty_pathtarget();
5012  postponable_cols = NIL;
5013 
5014  i = 0;
5015  foreach(lc, final_target->exprs)
5016  {
5017  Expr *expr = (Expr *) lfirst(lc);
5018 
5019  if (postpone_col[i] || (postpone_srfs && col_is_srf[i]))
5020  postponable_cols = lappend(postponable_cols, expr);
5021  else
5022  add_column_to_pathtarget(input_target, expr,
5023  get_pathtarget_sortgroupref(final_target, i));
5024 
5025  i++;
5026  }
5027 
5028  /*
5029  * Pull out all the Vars, Aggrefs, and WindowFuncs mentioned in
5030  * postponable columns, and add them to the sort-input target if not
5031  * already present. (Some might be there already.) We mustn't
5032  * deconstruct Aggrefs or WindowFuncs here, since the projection node
5033  * would be unable to recompute them.
5034  */
5035  postponable_vars = pull_var_clause((Node *) postponable_cols,
5039  add_new_columns_to_pathtarget(input_target, postponable_vars);
5040 
5041  /* clean up cruft */
5042  list_free(postponable_vars);
5043  list_free(postponable_cols);
5044 
5045  /* XXX this represents even more redundant cost calculation ... */
5046  return set_pathtarget_cost_width(root, input_target);
5047 }
5048 
5049 /*
5050  * get_cheapest_fractional_path
5051  * Find the cheapest path for retrieving a specified fraction of all
5052  * the tuples expected to be returned by the given relation.
5053  *
5054  * We interpret tuple_fraction the same way as grouping_planner.
5055  *
5056  * We assume set_cheapest() has been run on the given rel.
5057  */
5058 Path *
5059 get_cheapest_fractional_path(RelOptInfo *rel, double tuple_fraction)
5060 {
5061  Path *best_path = rel->cheapest_total_path;
5062  ListCell *l;
5063 
5064  /* If all tuples will be retrieved, just return the cheapest-total path */
5065  if (tuple_fraction <= 0.0)
5066  return best_path;
5067 
5068  /* Convert absolute # of tuples to a fraction; no need to clamp to 0..1 */
5069  if (tuple_fraction >= 1.0 && best_path->rows > 0)
5070  tuple_fraction /= best_path->rows;
5071 
5072  foreach(l, rel->pathlist)
5073  {
5074  Path *path = (Path *) lfirst(l);
5075 
5076  if (path == rel->cheapest_total_path ||
5077  compare_fractional_path_costs(best_path, path, tuple_fraction) <= 0)
5078  continue;
5079 
5080  best_path = path;
5081  }
5082 
5083  return best_path;
5084 }
5085 
5086 /*
5087  * adjust_paths_for_srfs
5088  * Fix up the Paths of the given upperrel to handle tSRFs properly.
5089  *
5090  * The executor can only handle set-returning functions that appear at the
5091  * top level of the targetlist of a ProjectSet plan node. If we have any SRFs
5092  * that are not at top level, we need to split up the evaluation into multiple
5093  * plan levels in which each level satisfies this constraint. This function
5094  * modifies each Path of an upperrel that (might) compute any SRFs in its
5095  * output tlist to insert appropriate projection steps.
5096  *
5097  * The given targets and targets_contain_srfs lists are from
5098  * split_pathtarget_at_srfs(). We assume the existing Paths emit the first
5099  * target in targets.
5100  */
5101 static void
5103  List *targets, List *targets_contain_srfs)
5104 {
5105  ListCell *lc;
5106 
5107  Assert(list_length(targets) == list_length(targets_contain_srfs));
5108  Assert(!linitial_int(targets_contain_srfs));
5109 
5110  /* If no SRFs appear at this plan level, nothing to do */
5111  if (list_length(targets) == 1)
5112  return;
5113 
5114  /*
5115  * Stack SRF-evaluation nodes atop each path for the rel.
5116  *
5117  * In principle we should re-run set_cheapest() here to identify the
5118  * cheapest path, but it seems unlikely that adding the same tlist eval
5119  * costs to all the paths would change that, so we don't bother. Instead,
5120  * just assume that the cheapest-startup and cheapest-total paths remain
5121  * so. (There should be no parameterized paths anymore, so we needn't
5122  * worry about updating cheapest_parameterized_paths.)
5123  */
5124  foreach(lc, rel->pathlist)
5125  {
5126  Path *subpath = (Path *) lfirst(lc);
5127  Path *newpath = subpath;
5128  ListCell *lc1,
5129  *lc2;
5130 
5131  Assert(subpath->param_info == NULL);
5132  forboth(lc1, targets, lc2, targets_contain_srfs)
5133  {
5134  PathTarget *thistarget = (PathTarget *) lfirst(lc1);
5135  bool contains_srfs = (bool) lfirst_int(lc2);
5136 
5137  /* If this level doesn't contain SRFs, do regular projection */
5138  if (contains_srfs)
5139  newpath = (Path *) create_set_projection_path(root,
5140  rel,
5141  newpath,
5142  thistarget);
5143  else
5144  newpath = (Path *) apply_projection_to_path(root,
5145  rel,
5146  newpath,
5147  thistarget);
5148  }
5149  lfirst(lc) = newpath;
5150  if (subpath == rel->cheapest_startup_path)
5151  rel->cheapest_startup_path = newpath;
5152  if (subpath == rel->cheapest_total_path)
5153  rel->cheapest_total_path = newpath;
5154  }
5155 
5156  /* Likewise for partial paths, if any */
5157  foreach(lc, rel->partial_pathlist)
5158  {
5159  Path *subpath = (Path *) lfirst(lc);
5160  Path *newpath = subpath;
5161  ListCell *lc1,
5162  *lc2;
5163 
5164  Assert(subpath->param_info == NULL);
5165  forboth(lc1, targets, lc2, targets_contain_srfs)
5166  {
5167  PathTarget *thistarget = (PathTarget *) lfirst(lc1);
5168  bool contains_srfs = (bool) lfirst_int(lc2);
5169 
5170  /* If this level doesn't contain SRFs, do regular projection */
5171  if (contains_srfs)
5172  newpath = (Path *) create_set_projection_path(root,
5173  rel,
5174  newpath,
5175  thistarget);
5176  else
5177  {
5178  /* avoid apply_projection_to_path, in case of multiple refs */
5179  newpath = (Path *) create_projection_path(root,
5180  rel,
5181  newpath,
5182  thistarget);
5183  }
5184  }
5185  lfirst(lc) = newpath;
5186  }
5187 }
5188 
5189 /*
5190  * expression_planner
5191  * Perform planner's transformations on a standalone expression.
5192  *
5193  * Various utility commands need to evaluate expressions that are not part
5194  * of a plannable query. They can do so using the executor's regular
5195  * expression-execution machinery, but first the expression has to be fed
5196  * through here to transform it from parser output to something executable.
5197  *
5198  * Currently, we disallow sublinks in standalone expressions, so there's no
5199  * real "planning" involved here. (That might not always be true though.)
5200  * What we must do is run eval_const_expressions to ensure that any function
5201  * calls are converted to positional notation and function default arguments
5202  * get inserted. The fact that constant subexpressions get simplified is a
5203  * side-effect that is useful when the expression will get evaluated more than
5204  * once. Also, we must fix operator function IDs.
5205  *
5206  * Note: this must not make any damaging changes to the passed-in expression
5207  * tree. (It would actually be okay to apply fix_opfuncids to it, but since
5208  * we first do an expression_tree_mutator-based walk, what is returned will
5209  * be a new node tree.)
5210  */
5211 Expr *
5213 {
5214  Node *result;
5215 
5216  /*
5217  * Convert named-argument function calls, insert default arguments and
5218  * simplify constant subexprs
5219  */
5220  result = eval_const_expressions(NULL, (Node *) expr);
5221 
5222  /* Fill in opfuncid values if missing */
5223  fix_opfuncids(result);
5224 
5225  return (Expr *) result;
5226 }
5227 
5228 
5229 /*
5230  * plan_cluster_use_sort
5231  * Use the planner to decide how CLUSTER should implement sorting
5232  *
5233  * tableOid is the OID of a table to be clustered on its index indexOid
5234  * (which is already known to be a btree index). Decide whether it's
5235  * cheaper to do an indexscan or a seqscan-plus-sort to execute the CLUSTER.
5236  * Return TRUE to use sorting, FALSE to use an indexscan.
5237  *
5238  * Note: caller had better already hold some type of lock on the table.
5239  */
5240 bool
5241 plan_cluster_use_sort(Oid tableOid, Oid indexOid)
5242 {
5243  PlannerInfo *root;
5244  Query *query;
5245  PlannerGlobal *glob;
5246  RangeTblEntry *rte;
5247  RelOptInfo *rel;
5248  IndexOptInfo *indexInfo;
5249  QualCost indexExprCost;
5250  Cost comparisonCost;
5251  Path *seqScanPath;
5252  Path seqScanAndSortPath;
5253  IndexPath *indexScanPath;
5254  ListCell *lc;
5255 
5256  /* We can short-circuit the cost comparison if indexscans are disabled */
5257  if (!enable_indexscan)
5258  return true; /* use sort */
5259 
5260  /* Set up mostly-dummy planner state */
5261  query = makeNode(Query);
5262  query->commandType = CMD_SELECT;
5263 
5264  glob = makeNode(PlannerGlobal);
5265 
5266  root = makeNode(PlannerInfo);
5267  root->parse = query;
5268  root->glob = glob;
5269  root->query_level = 1;
5271  root->wt_param_id = -1;
5272 
5273  /* Build a minimal RTE for the rel */
5274  rte = makeNode(RangeTblEntry);
5275  rte->rtekind = RTE_RELATION;
5276  rte->relid = tableOid;
5277  rte->relkind = RELKIND_RELATION; /* Don't be too picky. */
5278  rte->lateral = false;
5279  rte->inh = false;
5280  rte->inFromCl = true;
5281  query->rtable = list_make1(rte);
5282 
5283  /* Set up RTE/RelOptInfo arrays */
5285 
5286  /* Build RelOptInfo */
5287  rel = build_simple_rel(root, 1, RELOPT_BASEREL);
5288 
5289  /* Locate IndexOptInfo for the target index */
5290  indexInfo = NULL;
5291  foreach(lc, rel->indexlist)
5292  {
5293  indexInfo = (IndexOptInfo *) lfirst(lc);
5294  if (indexInfo->indexoid == indexOid)
5295  break;
5296  }
5297 
5298  /*
5299  * It's possible that get_relation_info did not generate an IndexOptInfo
5300  * for the desired index; this could happen if it's not yet reached its
5301  * indcheckxmin usability horizon, or if it's a system index and we're
5302  * ignoring system indexes. In such cases we should tell CLUSTER to not
5303  * trust the index contents but use seqscan-and-sort.
5304  */
5305  if (lc == NULL) /* not in the list? */
5306  return true; /* use sort */
5307 
5308  /*
5309  * Rather than doing all the pushups that would be needed to use
5310  * set_baserel_size_estimates, just do a quick hack for rows and width.
5311  */
5312  rel->rows = rel->tuples;
5313  rel->reltarget->width = get_relation_data_width(tableOid, NULL);
5314 
5315  root->total_table_pages = rel->pages;
5316 
5317  /*
5318  * Determine eval cost of the index expressions, if any. We need to
5319  * charge twice that amount for each tuple comparison that happens during
5320  * the sort, since tuplesort.c will have to re-evaluate the index
5321  * expressions each time. (XXX that's pretty inefficient...)
5322  */
5323  cost_qual_eval(&indexExprCost, indexInfo->indexprs, root);
5324  comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple);
5325 
5326  /* Estimate the cost of seq scan + sort */
5327  seqScanPath = create_seqscan_path(root, rel, NULL, 0);
5328  cost_sort(&seqScanAndSortPath, root, NIL,
5329  seqScanPath->total_cost, rel->tuples, rel->reltarget->width,
5330  comparisonCost, maintenance_work_mem, -1.0);
5331 
5332  /* Estimate the cost of index scan */
5333  indexScanPath = create_index_path(root, indexInfo,
5334  NIL, NIL, NIL, NIL, NIL,
5335  ForwardScanDirection, false,
5336  NULL, 1.0, false);
5337 
5338  return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
5339 }
Path * apply_projection_to_path(PlannerInfo *root, RelOptInfo *rel, Path *path, PathTarget *target)
Definition: pathnode.c:2253
Datum constvalue
Definition: primnodes.h:174
RelOptInfo * plan_set_operations(PlannerInfo *root)
Definition: prepunion.c:129
char maxParallelHazard
Definition: relation.h:130
GetForeignUpperPaths_function GetForeignUpperPaths
Definition: fdwapi.h:190
bool dependsOnRole
Definition: plannodes.h:57
Node * limitOffset
Definition: parsenodes.h:149
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:3230
List * group_pathkeys
Definition: relation.h:259
PathTarget * create_empty_pathtarget(void)
Definition: tlist.c:653
#define NIL
Definition: pg_list.h:69
PathTarget * copy_pathtarget(PathTarget *src)
Definition: tlist.c:629
List * rowMarks
Definition: relation.h:251
static double preprocess_limit(PlannerInfo *root, double tuple_fraction, int64 *offset_est, int64 *count_est)
Definition: planner.c:2282
List * qual
Definition: plannodes.h:130
Bitmapset * get_primary_key_attnos(Oid relid, bool deferrableOk, Oid *constraintOid)
double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset)
Definition: selfuncs.c:3272
uint32 queryId
Definition: parsenodes.h:107
double plan_rows
Definition: plannodes.h:117
ModifyTablePath * create_modifytable_path(PlannerInfo *root, RelOptInfo *rel, CmdType operation, bool canSetTag, Index nominalRelation, List *resultRelations, List *subpaths, List *subroots, List *withCheckOptionLists, List *returningLists, List *rowMarks, OnConflictExpr *onconflict, int epqParam)
Definition: pathnode.c:3019
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1667
List * list_delete_int(List *list, int datum)
Definition: list.c:613
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
PathTarget * pathtarget
Definition: relation.h:895
Query * parse
Definition: relation.h:152
uint32 queryId
Definition: plannodes.h:47
Expr * preprocess_phv_expression(PlannerInfo *root, Expr *expr)
Definition: planner.c:955
const char * LCS_asString(LockClauseStrength strength)
Definition: analyze.c:2580
Index varlevelsup
Definition: primnodes.h:151
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:370
bool plan_cluster_use_sort(Oid tableOid, Oid indexOid)
Definition: planner.c:5241
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:174
List * list_difference_int(const List *list1, const List *list2)
Definition: list.c:909
int stmt_location
Definition: parsenodes.h:171
RowMarkType markType
Definition: plannodes.h:943
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
Path path
Definition: relation.h:971
List * plan_params
Definition: relation.h:166
List * sortClause
Definition: parsenodes.h:147
bool hasJoinRTEs
Definition: relation.h:294
#define PVC_RECURSE_AGGREGATES
Definition: var.h:21
static int32 next
Definition: blutils.c:210
static List * extract_rollup_sets(List *groupingSets)
Definition: planner.c:2784
List * query_pathkeys
Definition: relation.h:257
List * join_info_list
Definition: relation.h:247
PathTarget * set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target)
Definition: costsize.c:4710
PlannedStmt * standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
Definition: planner.c:186
LockRowsPath * create_lockrows_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *rowMarks, int epqParam)
Definition: pathnode.c:2963
AppendPath * create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer, int parallel_workers)
Definition: pathnode.c:1202
#define EXPRKIND_ARBITER_ELEM
Definition: planner.c:82
void reduce_outer_joins(PlannerInfo *root)
FromExpr * jointree
Definition: parsenodes.h:129
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2870
int SS_assign_special_param(PlannerInfo *root)
Definition: subselect.c:415
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2399
Index maxWinRef
Definition: clauses.h:26
OnConflictExpr * onConflict
Definition: parsenodes.h:133
List * make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist)
Definition: pathkeys.c:838
UpperUniquePath * create_upper_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, int numCols, double numGroups)
Definition: pathnode.c:2498
static void preprocess_rowmarks(PlannerInfo *root)
Definition: planner.c:2105
List * preprocess_onconflict_targetlist(List *tlist, int result_relation, List *range_table)
Definition: preptlist.c:206
static List * preprocess_groupclause(PlannerInfo *root, List *force)
Definition: planner.c:2681
RelOptInfo * query_planner(PlannerInfo *root, List *tlist, query_pathkeys_callback qp_callback, void *qp_extra)
Definition: planmain.c:54
struct Path * cheapest_startup_path
Definition: relation.h:507
RowMarkType select_rowmark_type(RangeTblEntry *rte, LockClauseStrength strength)
Definition: planner.c:2216
List * constraintDeps
Definition: parsenodes.h:157
Oid userid
Definition: relation.h:537
List * securityQuals
Definition: parsenodes.h:970
List * withCheckOptions
Definition: parsenodes.h:160
void fix_opfuncids(Node *node)
Definition: nodeFuncs.c:1596
void add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
Definition: tlist.c:667
List * relationOids
Definition: plannodes.h:74
#define EXPRKIND_APPINFO
Definition: planner.c:79
#define EXPRKIND_QUAL
Definition: planner.c:72
int lastPlanNodeId
Definition: relation.h:120
double tuples
Definition: relation.h:529
void split_pathtarget_at_srfs(PlannerInfo *root, PathTarget *target, PathTarget *input_target, List **targets, List **targets_contain_srfs)
Definition: tlist.c:840
void get_agg_clause_costs(PlannerInfo *root, Node *clause, AggSplit aggsplit, AggClauseCosts *costs)
Definition: clauses.c:466
bool hasAggs
Definition: parsenodes.h:116
#define Min(x, y)
Definition: c.h:801
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:670
int parallel_workers
Definition: relation.h:901
Expr * expression_planner(Expr *expr)
Definition: planner.c:5212
int resultRelation
Definition: parsenodes.h:113
int numWindowFuncs
Definition: clauses.h:25
WindowFuncLists * find_window_functions(Node *clause, Index maxWinRef)
Definition: clauses.c:739
#define llast(l)
Definition: pg_list.h:126
void mark_partial_aggref(Aggref *agg, AggSplit aggsplit)
Definition: planner.c:4508
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:283
List * resultRelations
Definition: relation.h:108
void SS_charge_for_initplans(PlannerInfo *root, RelOptInfo *final_rel)
Definition: subselect.c:2154
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:714
Index tleSortGroupRef
Definition: parsenodes.h:1102
List * preprocess_targetlist(PlannerInfo *root, List *tlist)
Definition: preptlist.c:64
ParamPathInfo * param_info
Definition: relation.h:897
#define EXPRKIND_RTFUNC
Definition: planner.c:74
List * groupingSets
Definition: parsenodes.h:139
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:508
ProjectionPath * create_projection_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target)
Definition: pathnode.c:2162
int errcode(int sqlerrcode)
Definition: elog.c:575
List * partial_pathlist
Definition: relation.h:506
Index prti
Definition: plannodes.h:941
static Node * preprocess_expression(PlannerInfo *root, Node *expr, int kind)
Definition: planner.c:826
#define MemSet(start, val, len)
Definition: c.h:852
static RelOptInfo * create_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel)
Definition: planner.c:4000
AttrNumber varattno
Definition: primnodes.h:146
Node * eval_const_expressions(PlannerInfo *root, Node *node)
Definition: clauses.c:2366
IndexPath * create_index_path(PlannerInfo *root, IndexOptInfo *index, List *indexclauses, List *indexclausecols, List *indexorderbys, List *indexorderbycols, List *pathkeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, double loop_count, bool partial_path)
Definition: pathnode.c:1008
List * list_concat(List *list1, List *list2)
Definition: list.c:321
double parallel_setup_cost
Definition: costsize.c:110
Node * SS_process_sublinks(PlannerInfo *root, Node *expr, bool isQual)
Definition: subselect.c:1945
#define FirstLowInvalidHeapAttributeNumber
Definition: sysattr.h:28
List * tlist
Definition: planner.c:87
bool hasNonSerial
Definition: relation.h:61
bool grouping_is_hashable(List *groupClause)
Definition: tlist.c:538
List * minmax_aggs
Definition: relation.h:280
List * pull_var_clause(Node *node, int flags)
Definition: var.c:535
static PathTarget * make_group_input_target(PlannerInfo *root, PathTarget *final_target)
Definition: planner.c:4320
List * fromlist
Definition: primnodes.h:1433
create_upper_paths_hook_type create_upper_paths_hook
Definition: planner.c:68
void(* create_upper_paths_hook_type)(PlannerInfo *root, UpperRelationKind stage, RelOptInfo *input_rel, RelOptInfo *output_rel)
Definition: planner.h:28
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:950
bool hasNonPartial
Definition: relation.h:60
bool useridiscurrent
Definition: relation.h:538
List * list_copy_tail(const List *oldlist, int nskip)
Definition: list.c:1203
void preprocess_minmax_aggregates(PlannerInfo *root, List *tlist)
Definition: planagg.c:75
#define EXPRKIND_VALUES_LATERAL
Definition: planner.c:77
void expand_inherited_tables(PlannerInfo *root)
Definition: prepunion.c:1318
unsigned int Oid
Definition: postgres_ext.h:31
List * rowMarks
Definition: parsenodes.h:152
Node * utilityStmt
Definition: parsenodes.h:111
Definition: primnodes.h:141
Index rowmarkId
Definition: plannodes.h:942
AttrNumber * grouping_map
Definition: relation.h:279
LockWaitPolicy waitPolicy
Definition: plannodes.h:946
bool transientPlan
Definition: plannodes.h:55
List * lappend_oid(List *list, Oid datum)
Definition: list.c:164
#define OidIsValid(objectId)
Definition: c.h:533
LimitPath * create_limit_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, Node *limitOffset, Node *limitCount, int64 offset_est, int64 count_est)
Definition: pathnode.c:3118
bool hasRecursion
Definition: relation.h:300
void pull_up_subqueries(PlannerInfo *root)
Definition: prepjointree.c:607
#define EXPRKIND_TARGET
Definition: planner.c:73
List * translated_vars
Definition: relation.h:1893
int stmt_len
Definition: plannodes.h:84
List * values_lists
Definition: parsenodes.h:937
PlannedStmt * planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
Definition: planner.c:174
#define EXPRKIND_PHV
Definition: planner.c:80
Node * quals
Definition: primnodes.h:1434
static PathTarget * make_partial_grouping_target(PlannerInfo *root, PathTarget *grouping_target)
Definition: planner.c:4407
Cost startup
Definition: relation.h:45
LockClauseStrength strength
Definition: parsenodes.h:1220
bool hasDistinctOn
Definition: parsenodes.h:120
char bool
Definition: c.h:199
char max_parallel_hazard(Query *parse)
Definition: clauses.c:1053
struct Plan * planTree
Definition: plannodes.h:61
static RelOptInfo * create_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, PathTarget *target, const AggClauseCosts *agg_costs, List *rollup_lists, List *rollup_groupclauses)
Definition: planner.c:3252
#define PVC_INCLUDE_AGGREGATES
Definition: var.h:20
List * windowClause
Definition: parsenodes.h:143
List * invalItems
Definition: plannodes.h:76
List * targetList
Definition: parsenodes.h:131
List * arbiterElems
Definition: primnodes.h:1452
struct RelOptInfo ** simple_rel_array
Definition: relation.h:176
static List * postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
Definition: planner.c:4543
void * copyObject(const void *from)
Definition: copyfuncs.c:4475
static void adjust_paths_for_srfs(PlannerInfo *root, RelOptInfo *rel, List *targets, List *targets_contain_srfs)
Definition: planner.c:5102
List * multiexpr_params
Definition: relation.h:229
#define IS_DUMMY_PATH(p)
Definition: relation.h:1122
Node * larg
Definition: primnodes.h:1413
void BipartiteMatchFree(BipartiteMatchState *state)
Plan * create_plan(PlannerInfo *root, Path *best_path)
Definition: createplan.c:293
#define list_make1(x1)
Definition: pg_list.h:133
#define linitial_int(l)
Definition: pg_list.h:111
bool contain_subplans(Node *clause)
Definition: clauses.c:842
#define PVC_INCLUDE_PLACEHOLDERS
Definition: var.h:24
#define EXPRKIND_LIMIT
Definition: planner.c:78
bool dependsOnRole
Definition: relation.h:124
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:1071
Cost per_tuple
Definition: relation.h:46
int nParamExec
Definition: plannodes.h:78
#define DO_AGGSPLIT_SERIALIZE(as)
Definition: nodes.h:761
int wt_param_id
Definition: relation.h:303
double tuple_fraction
Definition: relation.h:286
void set_dummy_rel_pathlist(RelOptInfo *rel)
Definition: allpaths.c:1616
struct Plan * righttree
Definition: plannodes.h:132
void CheckSelectLocking(Query *qry, LockClauseStrength strength)
Definition: analyze.c:2605
void pfree(void *pointer)
Definition: mcxt.c:992
bool parallelModeNeeded
Definition: relation.h:128
bool resjunk
Definition: primnodes.h:1337
#define linitial(l)
Definition: pg_list.h:110
List * rtable
Definition: parsenodes.h:128
List * make_ands_implicit(Expr *clause)
Definition: clauses.c:377
List * distinctClause
Definition: parsenodes.h:145
static void create_one_window_path(PlannerInfo *root, RelOptInfo *window_rel, Path *path, PathTarget *input_target, PathTarget *output_target, List *tlist, WindowFuncLists *wflists, List *activeWindows)
Definition: planner.c:3904
#define ERROR
Definition: elog.h:43
static bool limit_needed(Query *parse)
Definition: planner.c:2467
Plan plan
Definition: plannodes.h:782
double limit_tuples
Definition: relation.h:287
#define lfirst_int(lc)
Definition: pg_list.h:107
List * partitionClause
Definition: parsenodes.h:1195
bool single_copy
Definition: plannodes.h:784
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:3204
bool hasLateralRTEs
Definition: relation.h:295
bool parallelModeOK
Definition: relation.h:126
Bitmapset * rewindPlanIDs
Definition: relation.h:102
void inline_set_returning_functions(PlannerInfo *root)
Definition: prepjointree.c:573
#define DatumGetInt64(X)
Definition: postgres.h:615
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
static List * reorder_grouping_sets(List *groupingSets, List *sortclause)
Definition: planner.c:2996
RelOptInfo * fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
Definition: relnode.c:870
bool list_member_int(const List *list, int datum)
Definition: list.c:485
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, AppendRelInfo *appinfo)
Definition: prepunion.c:1734
static void remove_useless_groupby_columns(PlannerInfo *root)
Definition: planner.c:2524
AggPath * create_agg_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, AggStrategy aggstrategy, AggSplit aggsplit, List *groupClause, List *qual, const AggClauseCosts *aggcosts, double numGroups)
Definition: pathnode.c:2550
Relids get_relids_in_jointree(Node *jtnode, bool include_joins)
struct Path * cheapest_total_path
Definition: relation.h:508
static double get_number_of_groups(PlannerInfo *root, double path_rows, List *rollup_lists, List *rollup_groupclauses)
Definition: planner.c:3134
Node * limitCount
Definition: parsenodes.h:150
static PathTarget * make_window_input_target(PlannerInfo *root, PathTarget *final_target, List *activeWindows)
Definition: planner.c:4673
char * c
int stmt_location
Definition: plannodes.h:83
void * list_nth(const List *list, int n)
Definition: list.c:410
List * subplans
Definition: relation.h:98
Cost startup_cost
Definition: plannodes.h:111
ProjectSetPath * create_set_projection_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target)
Definition: pathnode.c:2329