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