1 /*-------------------------------------------------------------------------
2 *
3 * planner.c
4 * The query optimizer external interface.
5 *
6 * Portions Copyright (c) 1996-2020, 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 */
69 double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
70 int force_parallel_mode = FORCE_PARALLEL_OFF;
71 bool parallel_leader_participation = true;
72
73 /* Hook for plugins to get control in planner() */
74 planner_hook_type planner_hook = NULL;
75
76 /* Hook for plugins to get control when grouping_planner() plans upper rels */
77 create_upper_paths_hook_type create_upper_paths_hook = NULL;
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 */
100 } standard_qp_extra;
101
102 /*
103 * Data specific to grouping sets
104 */
105
106 typedef struct
107 {
108 List *rollups;
109 List *hash_sets_idx;
110 double dNumHashGroups;
111 bool any_hashable;
112 Bitmapset *unsortable_refs;
113 Bitmapset *unhashable_refs;
114 List *unsortable_sets;
115 int *tleref_to_colnum_map;
116 } grouping_sets_data;
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 {
124 WindowClause *wc;
125 List *uniqueOrder; /* A List of unique ordering/partitioning
126 * clauses per Window */
127 } WindowClauseSortData;
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 inheritance_planner(PlannerInfo *root);
133 static void grouping_planner(PlannerInfo *root, bool inheritance_update,
134 double tuple_fraction);
135 static grouping_sets_data *preprocess_grouping_sets(PlannerInfo *root);
136 static List *remap_to_groupclause_idx(List *groupClause, List *gsets,
137 int *tleref_to_colnum_map);
138 static void preprocess_rowmarks(PlannerInfo *root);
139 static double preprocess_limit(PlannerInfo *root,
140 double tuple_fraction,
141 int64 *offset_est, int64 *count_est);
142 static void remove_useless_groupby_columns(PlannerInfo *root);
143 static List *preprocess_groupclause(PlannerInfo *root, List *force);
144 static List *extract_rollup_sets(List *groupingSets);
145 static List *reorder_grouping_sets(List *groupingSets, List *sortclause);
146 static void standard_qp_callback(PlannerInfo *root, void *extra);
147 static double get_number_of_groups(PlannerInfo *root,
148 double path_rows,
149 grouping_sets_data *gd,
150 List *target_list);
151 static RelOptInfo *create_grouping_paths(PlannerInfo *root,
152 RelOptInfo *input_rel,
153 PathTarget *target,
154 bool target_parallel_safe,
155 const AggClauseCosts *agg_costs,
156 grouping_sets_data *gd);
157 static bool is_degenerate_grouping(PlannerInfo *root);
158 static void create_degenerate_grouping_paths(PlannerInfo *root,
159 RelOptInfo *input_rel,
160 RelOptInfo *grouped_rel);
161 static RelOptInfo *make_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
162 PathTarget *target, bool target_parallel_safe,
163 Node *havingQual);
164 static void create_ordinary_grouping_paths(PlannerInfo *root,
165 RelOptInfo *input_rel,
166 RelOptInfo *grouped_rel,
167 const AggClauseCosts *agg_costs,
168 grouping_sets_data *gd,
169 GroupPathExtraData *extra,
170 RelOptInfo **partially_grouped_rel_p);
171 static void consider_groupingsets_paths(PlannerInfo *root,
172 RelOptInfo *grouped_rel,
173 Path *path,
174 bool is_sorted,
175 bool can_hash,
176 grouping_sets_data *gd,
177 const AggClauseCosts *agg_costs,
178 double dNumGroups);
179 static RelOptInfo *create_window_paths(PlannerInfo *root,
180 RelOptInfo *input_rel,
181 PathTarget *input_target,
182 PathTarget *output_target,
183 bool output_target_parallel_safe,
184 WindowFuncLists *wflists,
185 List *activeWindows);
186 static void create_one_window_path(PlannerInfo *root,
187 RelOptInfo *window_rel,
188 Path *path,
189 PathTarget *input_target,
190 PathTarget *output_target,
191 WindowFuncLists *wflists,
192 List *activeWindows);
193 static RelOptInfo *create_distinct_paths(PlannerInfo *root,
194 RelOptInfo *input_rel);
195 static RelOptInfo *create_ordered_paths(PlannerInfo *root,
196 RelOptInfo *input_rel,
197 PathTarget *target,
198 bool target_parallel_safe,
199 double limit_tuples);
200 static PathTarget *make_group_input_target(PlannerInfo *root,
201 PathTarget *final_target);
202 static PathTarget *make_partial_grouping_target(PlannerInfo *root,
203 PathTarget *grouping_target,
204 Node *havingQual);
205 static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
206 static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
207 static PathTarget *make_window_input_target(PlannerInfo *root,
208 PathTarget *final_target,
209 List *activeWindows);
210 static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
211 List *tlist);
212 static PathTarget *make_sort_input_target(PlannerInfo *root,
213 PathTarget *final_target,
214 bool *have_postponed_srfs);
215 static void adjust_paths_for_srfs(PlannerInfo *root, RelOptInfo *rel,
216 List *targets, List *targets_contain_srfs);
217 static void add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
218 RelOptInfo *grouped_rel,
219 RelOptInfo *partially_grouped_rel,
220 const AggClauseCosts *agg_costs,
221 grouping_sets_data *gd,
222 double dNumGroups,
223 GroupPathExtraData *extra);
224 static RelOptInfo *create_partial_grouping_paths(PlannerInfo *root,
225 RelOptInfo *grouped_rel,
226 RelOptInfo *input_rel,
227 grouping_sets_data *gd,
228 GroupPathExtraData *extra,
229 bool force_rel_creation);
230 static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel);
231 static bool can_partial_agg(PlannerInfo *root,
232 const AggClauseCosts *agg_costs);
233 static void apply_scanjoin_target_to_paths(PlannerInfo *root,
234 RelOptInfo *rel,
235 List *scanjoin_targets,
236 List *scanjoin_targets_contain_srfs,
237 bool scanjoin_target_parallel_safe,
238 bool tlist_same_exprs);
239 static void create_partitionwise_grouping_paths(PlannerInfo *root,
240 RelOptInfo *input_rel,
241 RelOptInfo *grouped_rel,
242 RelOptInfo *partially_grouped_rel,
243 const AggClauseCosts *agg_costs,
244 grouping_sets_data *gd,
245 PartitionwiseAggregateType patype,
246 GroupPathExtraData *extra);
247 static bool group_by_has_partkey(RelOptInfo *input_rel,
248 List *targetList,
249 List *groupClause);
250 static int common_prefix_cmp(const void *a, const void *b);
251
252
253 /*****************************************************************************
254 *
255 * Query optimizer entry point
256 *
257 * To support loadable plugins that monitor or modify planner behavior,
258 * we provide a hook variable that lets a plugin get control before and
259 * after the standard planning process. The plugin would normally call
260 * standard_planner().
261 *
262 * Note to plugin authors: standard_planner() scribbles on its Query input,
263 * so you'd better copy that data structure if you want to plan more than once.
264 *
265 *****************************************************************************/
266 PlannedStmt *
planner(Query * parse,const char * query_string,int cursorOptions,ParamListInfo boundParams)267 planner(Query *parse, const char *query_string, int cursorOptions,
268 ParamListInfo boundParams)
269 {
270 PlannedStmt *result;
271
272 if (planner_hook)
273 result = (*planner_hook) (parse, query_string, cursorOptions, boundParams);
274 else
275 result = standard_planner(parse, query_string, cursorOptions, boundParams);
276 return result;
277 }
278
279 PlannedStmt *
standard_planner(Query * parse,const char * query_string,int cursorOptions,ParamListInfo boundParams)280 standard_planner(Query *parse, const char *query_string, int cursorOptions,
281 ParamListInfo boundParams)
282 {
283 PlannedStmt *result;
284 PlannerGlobal *glob;
285 double tuple_fraction;
286 PlannerInfo *root;
287 RelOptInfo *final_rel;
288 Path *best_path;
289 Plan *top_plan;
290 ListCell *lp,
291 *lr;
292
293 /*
294 * Set up global state for this planner invocation. This data is needed
295 * across all levels of sub-Query that might exist in the given command,
296 * so we keep it in a separate struct that's linked to by each per-Query
297 * PlannerInfo.
298 */
299 glob = makeNode(PlannerGlobal);
300
301 glob->boundParams = boundParams;
302 glob->subplans = NIL;
303 glob->subroots = NIL;
304 glob->rewindPlanIDs = NULL;
305 glob->finalrtable = NIL;
306 glob->finalrowmarks = NIL;
307 glob->resultRelations = NIL;
308 glob->rootResultRelations = NIL;
309 glob->appendRelations = NIL;
310 glob->relationOids = NIL;
311 glob->invalItems = NIL;
312 glob->paramExecTypes = NIL;
313 glob->lastPHId = 0;
314 glob->lastRowMarkId = 0;
315 glob->lastPlanNodeId = 0;
316 glob->transientPlan = false;
317 glob->dependsOnRole = false;
318
319 /*
320 * Assess whether it's feasible to use parallel mode for this query. We
321 * can't do this in a standalone backend, or if the command will try to
322 * modify any data, or if this is a cursor operation, or if GUCs are set
323 * to values that don't permit parallelism, or if parallel-unsafe
324 * functions are present in the query tree.
325 *
326 * (Note that we do allow CREATE TABLE AS, SELECT INTO, and CREATE
327 * MATERIALIZED VIEW to use parallel plans, but as of now, only the leader
328 * backend writes into a completely new table. In the future, we can
329 * extend it to allow workers to write into the table. However, to allow
330 * parallel updates and deletes, we have to solve other problems,
331 * especially around combo CIDs.)
332 *
333 * For now, we don't try to use parallel mode if we're running inside a
334 * parallel worker. We might eventually be able to relax this
335 * restriction, but for now it seems best not to have parallel workers
336 * trying to create their own parallel workers.
337 */
338 if ((cursorOptions & CURSOR_OPT_PARALLEL_OK) != 0 &&
339 IsUnderPostmaster &&
340 parse->commandType == CMD_SELECT &&
341 !parse->hasModifyingCTE &&
342 max_parallel_workers_per_gather > 0 &&
343 !IsParallelWorker())
344 {
345 /* all the cheap tests pass, so scan the query tree */
346 glob->maxParallelHazard = max_parallel_hazard(parse);
347 glob->parallelModeOK = (glob->maxParallelHazard != PROPARALLEL_UNSAFE);
348 }
349 else
350 {
351 /* skip the query tree scan, just assume it's unsafe */
352 glob->maxParallelHazard = PROPARALLEL_UNSAFE;
353 glob->parallelModeOK = false;
354 }
355
356 /*
357 * glob->parallelModeNeeded is normally set to false here and changed to
358 * true during plan creation if a Gather or Gather Merge plan is actually
359 * created (cf. create_gather_plan, create_gather_merge_plan).
360 *
361 * However, if force_parallel_mode = on or force_parallel_mode = regress,
362 * then we impose parallel mode whenever it's safe to do so, even if the
363 * final plan doesn't use parallelism. It's not safe to do so if the
364 * query contains anything parallel-unsafe; parallelModeOK will be false
365 * in that case. Note that parallelModeOK can't change after this point.
366 * Otherwise, everything in the query is either parallel-safe or
367 * parallel-restricted, and in either case it should be OK to impose
368 * parallel-mode restrictions. If that ends up breaking something, then
369 * either some function the user included in the query is incorrectly
370 * labeled as parallel-safe or parallel-restricted when in reality it's
371 * parallel-unsafe, or else the query planner itself has a bug.
372 */
373 glob->parallelModeNeeded = glob->parallelModeOK &&
374 (force_parallel_mode != FORCE_PARALLEL_OFF);
375
376 /* Determine what fraction of the plan is likely to be scanned */
377 if (cursorOptions & CURSOR_OPT_FAST_PLAN)
378 {
379 /*
380 * We have no real idea how many tuples the user will ultimately FETCH
381 * from a cursor, but it is often the case that he doesn't want 'em
382 * all, or would prefer a fast-start plan anyway so that he can
383 * process some of the tuples sooner. Use a GUC parameter to decide
384 * what fraction to optimize for.
385 */
386 tuple_fraction = cursor_tuple_fraction;
387
388 /*
389 * We document cursor_tuple_fraction as simply being a fraction, which
390 * means the edge cases 0 and 1 have to be treated specially here. We
391 * convert 1 to 0 ("all the tuples") and 0 to a very small fraction.
392 */
393 if (tuple_fraction >= 1.0)
394 tuple_fraction = 0.0;
395 else if (tuple_fraction <= 0.0)
396 tuple_fraction = 1e-10;
397 }
398 else
399 {
400 /* Default assumption is we need all the tuples */
401 tuple_fraction = 0.0;
402 }
403
404 /* primary planning entry point (may recurse for subqueries) */
405 root = subquery_planner(glob, parse, NULL,
406 false, tuple_fraction);
407
408 /* Select best Path and turn it into a Plan */
409 final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
410 best_path = get_cheapest_fractional_path(final_rel, tuple_fraction);
411
412 top_plan = create_plan(root, best_path);
413
414 /*
415 * If creating a plan for a scrollable cursor, make sure it can run
416 * backwards on demand. Add a Material node at the top at need.
417 */
418 if (cursorOptions & CURSOR_OPT_SCROLL)
419 {
420 if (!ExecSupportsBackwardScan(top_plan))
421 top_plan = materialize_finished_plan(top_plan);
422 }
423
424 /*
425 * Optionally add a Gather node for testing purposes, provided this is
426 * actually a safe thing to do.
427 */
428 if (force_parallel_mode != FORCE_PARALLEL_OFF && top_plan->parallel_safe)
429 {
430 Gather *gather = makeNode(Gather);
431
432 /*
433 * If there are any initPlans attached to the formerly-top plan node,
434 * move them up to the Gather node; same as we do for Material node in
435 * materialize_finished_plan.
436 */
437 gather->plan.initPlan = top_plan->initPlan;
438 top_plan->initPlan = NIL;
439
440 gather->plan.targetlist = top_plan->targetlist;
441 gather->plan.qual = NIL;
442 gather->plan.lefttree = top_plan;
443 gather->plan.righttree = NULL;
444 gather->num_workers = 1;
445 gather->single_copy = true;
446 gather->invisible = (force_parallel_mode == FORCE_PARALLEL_REGRESS);
447
448 /*
449 * Since this Gather has no parallel-aware descendants to signal to,
450 * we don't need a rescan Param.
451 */
452 gather->rescan_param = -1;
453
454 /*
455 * Ideally we'd use cost_gather here, but setting up dummy path data
456 * to satisfy it doesn't seem much cleaner than knowing what it does.
457 */
458 gather->plan.startup_cost = top_plan->startup_cost +
459 parallel_setup_cost;
460 gather->plan.total_cost = top_plan->total_cost +
461 parallel_setup_cost + parallel_tuple_cost * top_plan->plan_rows;
462 gather->plan.plan_rows = top_plan->plan_rows;
463 gather->plan.plan_width = top_plan->plan_width;
464 gather->plan.parallel_aware = false;
465 gather->plan.parallel_safe = false;
466
467 /* use parallel mode for parallel plans. */
468 root->glob->parallelModeNeeded = true;
469
470 top_plan = &gather->plan;
471 }
472
473 /*
474 * If any Params were generated, run through the plan tree and compute
475 * each plan node's extParam/allParam sets. Ideally we'd merge this into
476 * set_plan_references' tree traversal, but for now it has to be separate
477 * because we need to visit subplans before not after main plan.
478 */
479 if (glob->paramExecTypes != NIL)
480 {
481 Assert(list_length(glob->subplans) == list_length(glob->subroots));
482 forboth(lp, glob->subplans, lr, glob->subroots)
483 {
484 Plan *subplan = (Plan *) lfirst(lp);
485 PlannerInfo *subroot = lfirst_node(PlannerInfo, lr);
486
487 SS_finalize_plan(subroot, subplan);
488 }
489 SS_finalize_plan(root, top_plan);
490 }
491
492 /* final cleanup of the plan */
493 Assert(glob->finalrtable == NIL);
494 Assert(glob->finalrowmarks == NIL);
495 Assert(glob->resultRelations == NIL);
496 Assert(glob->rootResultRelations == 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->rootResultRelations = glob->rootResultRelations;
524 result->appendRelations = glob->appendRelations;
525 result->subplans = glob->subplans;
526 result->rewindPlanIDs = glob->rewindPlanIDs;
527 result->rowMarks = glob->finalrowmarks;
528 result->relationOids = glob->relationOids;
529 result->invalItems = glob->invalItems;
530 result->paramExecTypes = glob->paramExecTypes;
531 /* utilityStmt should be null, but we might as well copy it */
532 result->utilityStmt = parse->utilityStmt;
533 result->stmt_location = parse->stmt_location;
534 result->stmt_len = parse->stmt_len;
535
536 result->jitFlags = PGJIT_NONE;
537 if (jit_enabled && jit_above_cost >= 0 &&
538 top_plan->total_cost > jit_above_cost)
539 {
540 result->jitFlags |= PGJIT_PERFORM;
541
542 /*
543 * Decide how much effort should be put into generating better code.
544 */
545 if (jit_optimize_above_cost >= 0 &&
546 top_plan->total_cost > jit_optimize_above_cost)
547 result->jitFlags |= PGJIT_OPT3;
548 if (jit_inline_above_cost >= 0 &&
549 top_plan->total_cost > jit_inline_above_cost)
550 result->jitFlags |= PGJIT_INLINE;
551
552 /*
553 * Decide which operations should be JITed.
554 */
555 if (jit_expressions)
556 result->jitFlags |= PGJIT_EXPR;
557 if (jit_tuple_deforming)
558 result->jitFlags |= PGJIT_DEFORM;
559 }
560
561 if (glob->partition_directory != NULL)
562 DestroyPartitionDirectory(glob->partition_directory);
563
564 return result;
565 }
566
567
568 /*--------------------
569 * subquery_planner
570 * Invokes the planner on a subquery. We recurse to here for each
571 * sub-SELECT found in the query tree.
572 *
573 * glob is the global state for the current planner run.
574 * parse is the querytree produced by the parser & rewriter.
575 * parent_root is the immediate parent Query's info (NULL at the top level).
576 * hasRecursion is true if this is a recursive WITH query.
577 * tuple_fraction is the fraction of tuples we expect will be retrieved.
578 * tuple_fraction is interpreted as explained for grouping_planner, below.
579 *
580 * Basically, this routine does the stuff that should only be done once
581 * per Query object. It then calls grouping_planner. At one time,
582 * grouping_planner could be invoked recursively on the same Query object;
583 * that's not currently true, but we keep the separation between the two
584 * routines anyway, in case we need it again someday.
585 *
586 * subquery_planner will be called recursively to handle sub-Query nodes
587 * found within the query's expressions and rangetable.
588 *
589 * Returns the PlannerInfo struct ("root") that contains all data generated
590 * while planning the subquery. In particular, the Path(s) attached to
591 * the (UPPERREL_FINAL, NULL) upperrel represent our conclusions about the
592 * cheapest way(s) to implement the query. The top level will select the
593 * best Path and pass it through createplan.c to produce a finished Plan.
594 *--------------------
595 */
596 PlannerInfo *
subquery_planner(PlannerGlobal * glob,Query * parse,PlannerInfo * parent_root,bool hasRecursion,double tuple_fraction)597 subquery_planner(PlannerGlobal *glob, Query *parse,
598 PlannerInfo *parent_root,
599 bool hasRecursion, double tuple_fraction)
600 {
601 PlannerInfo *root;
602 List *newWithCheckOptions;
603 List *newHaving;
604 bool hasOuterJoins;
605 bool hasResultRTEs;
606 RelOptInfo *final_rel;
607 ListCell *l;
608
609 /* Create a PlannerInfo data structure for this subquery */
610 root = makeNode(PlannerInfo);
611 root->parse = parse;
612 root->glob = glob;
613 root->query_level = parent_root ? parent_root->query_level + 1 : 1;
614 root->parent_root = parent_root;
615 root->plan_params = NIL;
616 root->outer_params = NULL;
617 root->planner_cxt = CurrentMemoryContext;
618 root->init_plans = NIL;
619 root->cte_plan_ids = NIL;
620 root->multiexpr_params = NIL;
621 root->eq_classes = NIL;
622 root->ec_merging_done = false;
623 root->append_rel_list = NIL;
624 root->rowMarks = NIL;
625 memset(root->upper_rels, 0, sizeof(root->upper_rels));
626 memset(root->upper_targets, 0, sizeof(root->upper_targets));
627 root->processed_tlist = NIL;
628 root->grouping_map = NULL;
629 root->minmax_aggs = NIL;
630 root->qual_security_level = 0;
631 root->inhTargetKind = INHKIND_NONE;
632 root->hasRecursion = hasRecursion;
633 if (hasRecursion)
634 root->wt_param_id = assign_special_exec_param(root);
635 else
636 root->wt_param_id = -1;
637 root->non_recursive_path = NULL;
638 root->partColsUpdated = false;
639
640 /*
641 * If there is a WITH list, process each WITH query and either convert it
642 * to RTE_SUBQUERY RTE(s) or build an initplan SubPlan structure for it.
643 */
644 if (parse->cteList)
645 SS_process_ctes(root);
646
647 /*
648 * If the FROM clause is empty, replace it with a dummy RTE_RESULT RTE, so
649 * that we don't need so many special cases to deal with that situation.
650 */
651 replace_empty_jointree(parse);
652
653 /*
654 * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
655 * to transform them into joins. Note that this step does not descend
656 * into subqueries; if we pull up any subqueries below, their SubLinks are
657 * processed just before pulling them up.
658 */
659 if (parse->hasSubLinks)
660 pull_up_sublinks(root);
661
662 /*
663 * Scan the rangetable for function RTEs, do const-simplification on them,
664 * and then inline them if possible (producing subqueries that might get
665 * pulled up next). Recursion issues here are handled in the same way as
666 * for SubLinks.
667 */
668 preprocess_function_rtes(root);
669
670 /*
671 * Check to see if any subqueries in the jointree can be merged into this
672 * query.
673 */
674 pull_up_subqueries(root);
675
676 /*
677 * If this is a simple UNION ALL query, flatten it into an appendrel. We
678 * do this now because it requires applying pull_up_subqueries to the leaf
679 * queries of the UNION ALL, which weren't touched above because they
680 * weren't referenced by the jointree (they will be after we do this).
681 */
682 if (parse->setOperations)
683 flatten_simple_union_all(root);
684
685 /*
686 * Survey the rangetable to see what kinds of entries are present. We can
687 * skip some later processing if relevant SQL features are not used; for
688 * example if there are no JOIN RTEs we can avoid the expense of doing
689 * flatten_join_alias_vars(). This must be done after we have finished
690 * adding rangetable entries, of course. (Note: actually, processing of
691 * inherited or partitioned rels can cause RTEs for their child tables to
692 * get added later; but those must all be RTE_RELATION entries, so they
693 * don't invalidate the conclusions drawn here.)
694 */
695 root->hasJoinRTEs = false;
696 root->hasLateralRTEs = false;
697 hasOuterJoins = false;
698 hasResultRTEs = false;
699 foreach(l, parse->rtable)
700 {
701 RangeTblEntry *rte = lfirst_node(RangeTblEntry, l);
702
703 switch (rte->rtekind)
704 {
705 case RTE_RELATION:
706 if (rte->inh)
707 {
708 /*
709 * Check to see if the relation actually has any children;
710 * if not, clear the inh flag so we can treat it as a
711 * plain base relation.
712 *
713 * Note: this could give a false-positive result, if the
714 * rel once had children but no longer does. We used to
715 * be able to clear rte->inh later on when we discovered
716 * that, but no more; we have to handle such cases as
717 * full-fledged inheritance.
718 */
719 rte->inh = has_subclass(rte->relid);
720 }
721 break;
722 case RTE_JOIN:
723 root->hasJoinRTEs = true;
724 if (IS_OUTER_JOIN(rte->jointype))
725 hasOuterJoins = true;
726 break;
727 case RTE_RESULT:
728 hasResultRTEs = true;
729 break;
730 default:
731 /* No work here for other RTE types */
732 break;
733 }
734
735 if (rte->lateral)
736 root->hasLateralRTEs = true;
737
738 /*
739 * We can also determine the maximum security level required for any
740 * securityQuals now. Addition of inheritance-child RTEs won't affect
741 * this, because child tables don't have their own securityQuals; see
742 * expand_single_inheritance_child().
743 */
744 if (rte->securityQuals)
745 root->qual_security_level = Max(root->qual_security_level,
746 list_length(rte->securityQuals));
747 }
748
749 /*
750 * Preprocess RowMark information. We need to do this after subquery
751 * pullup, so that all base relations are present.
752 */
753 preprocess_rowmarks(root);
754
755 /*
756 * Set hasHavingQual to remember if HAVING clause is present. Needed
757 * because preprocess_expression will reduce a constant-true condition to
758 * an empty qual list ... but "HAVING TRUE" is not a semantic no-op.
759 */
760 root->hasHavingQual = (parse->havingQual != NULL);
761
762 /* Clear this flag; might get set in distribute_qual_to_rels */
763 root->hasPseudoConstantQuals = false;
764
765 /*
766 * Do expression preprocessing on targetlist and quals, as well as other
767 * random expressions in the querytree. Note that we do not need to
768 * handle sort/group expressions explicitly, because they are actually
769 * part of the targetlist.
770 */
771 parse->targetList = (List *)
772 preprocess_expression(root, (Node *) parse->targetList,
773 EXPRKIND_TARGET);
774
775 /* Constant-folding might have removed all set-returning functions */
776 if (parse->hasTargetSRFs)
777 parse->hasTargetSRFs = expression_returns_set((Node *) parse->targetList);
778
779 newWithCheckOptions = NIL;
780 foreach(l, parse->withCheckOptions)
781 {
782 WithCheckOption *wco = lfirst_node(WithCheckOption, l);
783
784 wco->qual = preprocess_expression(root, wco->qual,
785 EXPRKIND_QUAL);
786 if (wco->qual != NULL)
787 newWithCheckOptions = lappend(newWithCheckOptions, wco);
788 }
789 parse->withCheckOptions = newWithCheckOptions;
790
791 parse->returningList = (List *)
792 preprocess_expression(root, (Node *) parse->returningList,
793 EXPRKIND_TARGET);
794
795 preprocess_qual_conditions(root, (Node *) parse->jointree);
796
797 parse->havingQual = preprocess_expression(root, parse->havingQual,
798 EXPRKIND_QUAL);
799
800 foreach(l, parse->windowClause)
801 {
802 WindowClause *wc = lfirst_node(WindowClause, l);
803
804 /* partitionClause/orderClause are sort/group expressions */
805 wc->startOffset = preprocess_expression(root, wc->startOffset,
806 EXPRKIND_LIMIT);
807 wc->endOffset = preprocess_expression(root, wc->endOffset,
808 EXPRKIND_LIMIT);
809 }
810
811 parse->limitOffset = preprocess_expression(root, parse->limitOffset,
812 EXPRKIND_LIMIT);
813 parse->limitCount = preprocess_expression(root, parse->limitCount,
814 EXPRKIND_LIMIT);
815
816 if (parse->onConflict)
817 {
818 parse->onConflict->arbiterElems = (List *)
819 preprocess_expression(root,
820 (Node *) parse->onConflict->arbiterElems,
821 EXPRKIND_ARBITER_ELEM);
822 parse->onConflict->arbiterWhere =
823 preprocess_expression(root,
824 parse->onConflict->arbiterWhere,
825 EXPRKIND_QUAL);
826 parse->onConflict->onConflictSet = (List *)
827 preprocess_expression(root,
828 (Node *) parse->onConflict->onConflictSet,
829 EXPRKIND_TARGET);
830 parse->onConflict->onConflictWhere =
831 preprocess_expression(root,
832 parse->onConflict->onConflictWhere,
833 EXPRKIND_QUAL);
834 /* exclRelTlist contains only Vars, so no preprocessing needed */
835 }
836
837 root->append_rel_list = (List *)
838 preprocess_expression(root, (Node *) root->append_rel_list,
839 EXPRKIND_APPINFO);
840
841 /* Also need to preprocess expressions within RTEs */
842 foreach(l, parse->rtable)
843 {
844 RangeTblEntry *rte = lfirst_node(RangeTblEntry, l);
845 int kind;
846 ListCell *lcsq;
847
848 if (rte->rtekind == RTE_RELATION)
849 {
850 if (rte->tablesample)
851 rte->tablesample = (TableSampleClause *)
852 preprocess_expression(root,
853 (Node *) rte->tablesample,
854 EXPRKIND_TABLESAMPLE);
855 }
856 else if (rte->rtekind == RTE_SUBQUERY)
857 {
858 /*
859 * We don't want to do all preprocessing yet on the subquery's
860 * expressions, since that will happen when we plan it. But if it
861 * contains any join aliases of our level, those have to get
862 * expanded now, because planning of the subquery won't do it.
863 * That's only possible if the subquery is LATERAL.
864 */
865 if (rte->lateral && root->hasJoinRTEs)
866 rte->subquery = (Query *)
867 flatten_join_alias_vars(root->parse,
868 (Node *) rte->subquery);
869 }
870 else if (rte->rtekind == RTE_FUNCTION)
871 {
872 /* Preprocess the function expression(s) fully */
873 kind = rte->lateral ? EXPRKIND_RTFUNC_LATERAL : EXPRKIND_RTFUNC;
874 rte->functions = (List *)
875 preprocess_expression(root, (Node *) rte->functions, kind);
876 }
877 else if (rte->rtekind == RTE_TABLEFUNC)
878 {
879 /* Preprocess the function expression(s) fully */
880 kind = rte->lateral ? EXPRKIND_TABLEFUNC_LATERAL : EXPRKIND_TABLEFUNC;
881 rte->tablefunc = (TableFunc *)
882 preprocess_expression(root, (Node *) rte->tablefunc, kind);
883 }
884 else if (rte->rtekind == RTE_VALUES)
885 {
886 /* Preprocess the values lists fully */
887 kind = rte->lateral ? EXPRKIND_VALUES_LATERAL : EXPRKIND_VALUES;
888 rte->values_lists = (List *)
889 preprocess_expression(root, (Node *) rte->values_lists, kind);
890 }
891
892 /*
893 * Process each element of the securityQuals list as if it were a
894 * separate qual expression (as indeed it is). We need to do it this
895 * way to get proper canonicalization of AND/OR structure. Note that
896 * this converts each element into an implicit-AND sublist.
897 */
898 foreach(lcsq, rte->securityQuals)
899 {
900 lfirst(lcsq) = preprocess_expression(root,
901 (Node *) lfirst(lcsq),
902 EXPRKIND_QUAL);
903 }
904 }
905
906 /*
907 * Now that we are done preprocessing expressions, and in particular done
908 * flattening join alias variables, get rid of the joinaliasvars lists.
909 * They no longer match what expressions in the rest of the tree look
910 * like, because we have not preprocessed expressions in those lists (and
911 * do not want to; for example, expanding a SubLink there would result in
912 * a useless unreferenced subplan). Leaving them in place simply creates
913 * a hazard for later scans of the tree. We could try to prevent that by
914 * using QTW_IGNORE_JOINALIASES in every tree scan done after this point,
915 * but that doesn't sound very reliable.
916 */
917 if (root->hasJoinRTEs)
918 {
919 foreach(l, parse->rtable)
920 {
921 RangeTblEntry *rte = lfirst_node(RangeTblEntry, l);
922
923 rte->joinaliasvars = NIL;
924 }
925 }
926
927 /*
928 * In some cases we may want to transfer a HAVING clause into WHERE. We
929 * cannot do so if the HAVING clause contains aggregates (obviously) or
930 * volatile functions (since a HAVING clause is supposed to be executed
931 * only once per group). We also can't do this if there are any nonempty
932 * grouping sets; moving such a clause into WHERE would potentially change
933 * the results, if any referenced column isn't present in all the grouping
934 * sets. (If there are only empty grouping sets, then the HAVING clause
935 * must be degenerate as discussed below.)
936 *
937 * Also, it may be that the clause is so expensive to execute that we're
938 * better off doing it only once per group, despite the loss of
939 * selectivity. This is hard to estimate short of doing the entire
940 * planning process twice, so we use a heuristic: clauses containing
941 * subplans are left in HAVING. Otherwise, we move or copy the HAVING
942 * clause into WHERE, in hopes of eliminating tuples before aggregation
943 * instead of after.
944 *
945 * If the query has explicit grouping then we can simply move such a
946 * clause into WHERE; any group that fails the clause will not be in the
947 * output because none of its tuples will reach the grouping or
948 * aggregation stage. Otherwise we must have a degenerate (variable-free)
949 * HAVING clause, which we put in WHERE so that query_planner() can use it
950 * in a gating Result node, but also keep in HAVING to ensure that we
951 * don't emit a bogus aggregated row. (This could be done better, but it
952 * seems not worth optimizing.)
953 *
954 * Note that both havingQual and parse->jointree->quals are in
955 * implicitly-ANDed-list form at this point, even though they are declared
956 * as Node *.
957 */
958 newHaving = NIL;
959 foreach(l, (List *) parse->havingQual)
960 {
961 Node *havingclause = (Node *) lfirst(l);
962
963 if ((parse->groupClause && parse->groupingSets) ||
964 contain_agg_clause(havingclause) ||
965 contain_volatile_functions(havingclause) ||
966 contain_subplans(havingclause))
967 {
968 /* keep it in HAVING */
969 newHaving = lappend(newHaving, havingclause);
970 }
971 else if (parse->groupClause && !parse->groupingSets)
972 {
973 /* move it to WHERE */
974 parse->jointree->quals = (Node *)
975 lappend((List *) parse->jointree->quals, havingclause);
976 }
977 else
978 {
979 /* put a copy in WHERE, keep it in HAVING */
980 parse->jointree->quals = (Node *)
981 lappend((List *) parse->jointree->quals,
982 copyObject(havingclause));
983 newHaving = lappend(newHaving, havingclause);
984 }
985 }
986 parse->havingQual = (Node *) newHaving;
987
988 /* Remove any redundant GROUP BY columns */
989 remove_useless_groupby_columns(root);
990
991 /*
992 * If we have any outer joins, try to reduce them to plain inner joins.
993 * This step is most easily done after we've done expression
994 * preprocessing.
995 */
996 if (hasOuterJoins)
997 reduce_outer_joins(root);
998
999 /*
1000 * If we have any RTE_RESULT relations, see if they can be deleted from
1001 * the jointree. This step is most effectively done after we've done
1002 * expression preprocessing and outer join reduction.
1003 */
1004 if (hasResultRTEs)
1005 remove_useless_result_rtes(root);
1006
1007 /*
1008 * Do the main planning. If we have an inherited target relation, that
1009 * needs special processing, else go straight to grouping_planner.
1010 */
1011 if (parse->resultRelation &&
1012 rt_fetch(parse->resultRelation, parse->rtable)->inh)
1013 inheritance_planner(root);
1014 else
1015 grouping_planner(root, false, tuple_fraction);
1016
1017 /*
1018 * Capture the set of outer-level param IDs we have access to, for use in
1019 * extParam/allParam calculations later.
1020 */
1021 SS_identify_outer_params(root);
1022
1023 /*
1024 * If any initPlans were created in this query level, adjust the surviving
1025 * Paths' costs and parallel-safety flags to account for them. The
1026 * initPlans won't actually get attached to the plan tree till
1027 * create_plan() runs, but we must include their effects now.
1028 */
1029 final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
1030 SS_charge_for_initplans(root, final_rel);
1031
1032 /*
1033 * Make sure we've identified the cheapest Path for the final rel. (By
1034 * doing this here not in grouping_planner, we include initPlan costs in
1035 * the decision, though it's unlikely that will change anything.)
1036 */
1037 set_cheapest(final_rel);
1038
1039 return root;
1040 }
1041
1042 /*
1043 * preprocess_expression
1044 * Do subquery_planner's preprocessing work for an expression,
1045 * which can be a targetlist, a WHERE clause (including JOIN/ON
1046 * conditions), a HAVING clause, or a few other things.
1047 */
1048 static Node *
preprocess_expression(PlannerInfo * root,Node * expr,int kind)1049 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
1050 {
1051 /*
1052 * Fall out quickly if expression is empty. This occurs often enough to
1053 * be worth checking. Note that null->null is the correct conversion for
1054 * implicit-AND result format, too.
1055 */
1056 if (expr == NULL)
1057 return NULL;
1058
1059 /*
1060 * If the query has any join RTEs, replace join alias variables with
1061 * base-relation variables. We must do this first, since any expressions
1062 * we may extract from the joinaliasvars lists have not been preprocessed.
1063 * For example, if we did this after sublink processing, sublinks expanded
1064 * out from join aliases would not get processed. But we can skip this in
1065 * non-lateral RTE functions, VALUES lists, and TABLESAMPLE clauses, since
1066 * they can't contain any Vars of the current query level.
1067 */
1068 if (root->hasJoinRTEs &&
1069 !(kind == EXPRKIND_RTFUNC ||
1070 kind == EXPRKIND_VALUES ||
1071 kind == EXPRKIND_TABLESAMPLE ||
1072 kind == EXPRKIND_TABLEFUNC))
1073 expr = flatten_join_alias_vars(root->parse, expr);
1074
1075 /*
1076 * Simplify constant expressions. For function RTEs, this was already
1077 * done by preprocess_function_rtes. (But note we must do it again for
1078 * EXPRKIND_RTFUNC_LATERAL, because those might by now contain
1079 * un-simplified subexpressions inserted by flattening of subqueries or
1080 * join alias variables.)
1081 *
1082 * Note: an essential effect of this is to convert named-argument function
1083 * calls to positional notation and insert the current actual values of
1084 * any default arguments for functions. To ensure that happens, we *must*
1085 * process all expressions here. Previous PG versions sometimes skipped
1086 * const-simplification if it didn't seem worth the trouble, but we can't
1087 * do that anymore.
1088 *
1089 * Note: this also flattens nested AND and OR expressions into N-argument
1090 * form. All processing of a qual expression after this point must be
1091 * careful to maintain AND/OR flatness --- that is, do not generate a tree
1092 * with AND directly under AND, nor OR directly under OR.
1093 */
1094 if (kind != EXPRKIND_RTFUNC)
1095 expr = eval_const_expressions(root, expr);
1096
1097 /*
1098 * If it's a qual or havingQual, canonicalize it.
1099 */
1100 if (kind == EXPRKIND_QUAL)
1101 {
1102 expr = (Node *) canonicalize_qual((Expr *) expr, false);
1103
1104 #ifdef OPTIMIZER_DEBUG
1105 printf("After canonicalize_qual()\n");
1106 pprint(expr);
1107 #endif
1108 }
1109
1110 /* Expand SubLinks to SubPlans */
1111 if (root->parse->hasSubLinks)
1112 expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));
1113
1114 /*
1115 * XXX do not insert anything here unless you have grokked the comments in
1116 * SS_replace_correlation_vars ...
1117 */
1118
1119 /* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
1120 if (root->query_level > 1)
1121 expr = SS_replace_correlation_vars(root, expr);
1122
1123 /*
1124 * If it's a qual or havingQual, convert it to implicit-AND format. (We
1125 * don't want to do this before eval_const_expressions, since the latter
1126 * would be unable to simplify a top-level AND correctly. Also,
1127 * SS_process_sublinks expects explicit-AND format.)
1128 */
1129 if (kind == EXPRKIND_QUAL)
1130 expr = (Node *) make_ands_implicit((Expr *) expr);
1131
1132 return expr;
1133 }
1134
1135 /*
1136 * preprocess_qual_conditions
1137 * Recursively scan the query's jointree and do subquery_planner's
1138 * preprocessing work on each qual condition found therein.
1139 */
1140 static void
preprocess_qual_conditions(PlannerInfo * root,Node * jtnode)1141 preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
1142 {
1143 if (jtnode == NULL)
1144 return;
1145 if (IsA(jtnode, RangeTblRef))
1146 {
1147 /* nothing to do here */
1148 }
1149 else if (IsA(jtnode, FromExpr))
1150 {
1151 FromExpr *f = (FromExpr *) jtnode;
1152 ListCell *l;
1153
1154 foreach(l, f->fromlist)
1155 preprocess_qual_conditions(root, lfirst(l));
1156
1157 f->quals = preprocess_expression(root, f->quals, EXPRKIND_QUAL);
1158 }
1159 else if (IsA(jtnode, JoinExpr))
1160 {
1161 JoinExpr *j = (JoinExpr *) jtnode;
1162
1163 preprocess_qual_conditions(root, j->larg);
1164 preprocess_qual_conditions(root, j->rarg);
1165
1166 j->quals = preprocess_expression(root, j->quals, EXPRKIND_QUAL);
1167 }
1168 else
1169 elog(ERROR, "unrecognized node type: %d",
1170 (int) nodeTag(jtnode));
1171 }
1172
1173 /*
1174 * preprocess_phv_expression
1175 * Do preprocessing on a PlaceHolderVar expression that's been pulled up.
1176 *
1177 * If a LATERAL subquery references an output of another subquery, and that
1178 * output must be wrapped in a PlaceHolderVar because of an intermediate outer
1179 * join, then we'll push the PlaceHolderVar expression down into the subquery
1180 * and later pull it back up during find_lateral_references, which runs after
1181 * subquery_planner has preprocessed all the expressions that were in the
1182 * current query level to start with. So we need to preprocess it then.
1183 */
1184 Expr *
preprocess_phv_expression(PlannerInfo * root,Expr * expr)1185 preprocess_phv_expression(PlannerInfo *root, Expr *expr)
1186 {
1187 return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
1188 }
1189
1190 /*
1191 * inheritance_planner
1192 * Generate Paths in the case where the result relation is an
1193 * inheritance set.
1194 *
1195 * We have to handle this case differently from cases where a source relation
1196 * is an inheritance set. Source inheritance is expanded at the bottom of the
1197 * plan tree (see allpaths.c), but target inheritance has to be expanded at
1198 * the top. The reason is that for UPDATE, each target relation needs a
1199 * different targetlist matching its own column set. Fortunately,
1200 * the UPDATE/DELETE target can never be the nullable side of an outer join,
1201 * so it's OK to generate the plan this way.
1202 *
1203 * Returns nothing; the useful output is in the Paths we attach to
1204 * the (UPPERREL_FINAL, NULL) upperrel stored in *root.
1205 *
1206 * Note that we have not done set_cheapest() on the final rel; it's convenient
1207 * to leave this to the caller.
1208 */
1209 static void
inheritance_planner(PlannerInfo * root)1210 inheritance_planner(PlannerInfo *root)
1211 {
1212 Query *parse = root->parse;
1213 int top_parentRTindex = parse->resultRelation;
1214 List *select_rtable;
1215 List *select_appinfos;
1216 List *child_appinfos;
1217 List *old_child_rtis;
1218 List *new_child_rtis;
1219 Bitmapset *subqueryRTindexes;
1220 Index next_subquery_rti;
1221 int nominalRelation = -1;
1222 Index rootRelation = 0;
1223 List *final_rtable = NIL;
1224 List *final_rowmarks = NIL;
1225 List *final_appendrels = NIL;
1226 int save_rel_array_size = 0;
1227 RelOptInfo **save_rel_array = NULL;
1228 AppendRelInfo **save_append_rel_array = NULL;
1229 List *subpaths = NIL;
1230 List *subroots = NIL;
1231 List *resultRelations = NIL;
1232 List *withCheckOptionLists = NIL;
1233 List *returningLists = NIL;
1234 List *rowMarks;
1235 RelOptInfo *final_rel;
1236 ListCell *lc;
1237 ListCell *lc2;
1238 Index rti;
1239 RangeTblEntry *parent_rte;
1240 Bitmapset *parent_relids;
1241 Query **parent_parses;
1242
1243 /* Should only get here for UPDATE or DELETE */
1244 Assert(parse->commandType == CMD_UPDATE ||
1245 parse->commandType == CMD_DELETE);
1246
1247 /*
1248 * We generate a modified instance of the original Query for each target
1249 * relation, plan that, and put all the plans into a list that will be
1250 * controlled by a single ModifyTable node. All the instances share the
1251 * same rangetable, but each instance must have its own set of subquery
1252 * RTEs within the finished rangetable because (1) they are likely to get
1253 * scribbled on during planning, and (2) it's not inconceivable that
1254 * subqueries could get planned differently in different cases. We need
1255 * not create duplicate copies of other RTE kinds, in particular not the
1256 * target relations, because they don't have either of those issues. Not
1257 * having to duplicate the target relations is important because doing so
1258 * (1) would result in a rangetable of length O(N^2) for N targets, with
1259 * at least O(N^3) work expended here; and (2) would greatly complicate
1260 * management of the rowMarks list.
1261 *
1262 * To begin with, generate a bitmapset of the relids of the subquery RTEs.
1263 */
1264 subqueryRTindexes = NULL;
1265 rti = 1;
1266 foreach(lc, parse->rtable)
1267 {
1268 RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
1269
1270 if (rte->rtekind == RTE_SUBQUERY)
1271 subqueryRTindexes = bms_add_member(subqueryRTindexes, rti);
1272 rti++;
1273 }
1274
1275 /*
1276 * If the parent RTE is a partitioned table, we should use that as the
1277 * nominal target relation, because the RTEs added for partitioned tables
1278 * (including the root parent) as child members of the inheritance set do
1279 * not appear anywhere else in the plan, so the confusion explained below
1280 * for non-partitioning inheritance cases is not possible.
1281 */
1282 parent_rte = rt_fetch(top_parentRTindex, parse->rtable);
1283 Assert(parent_rte->inh);
1284 if (parent_rte->relkind == RELKIND_PARTITIONED_TABLE)
1285 {
1286 nominalRelation = top_parentRTindex;
1287 rootRelation = top_parentRTindex;
1288 }
1289
1290 /*
1291 * Before generating the real per-child-relation plans, do a cycle of
1292 * planning as though the query were a SELECT. The objective here is to
1293 * find out which child relations need to be processed, using the same
1294 * expansion and pruning logic as for a SELECT. We'll then pull out the
1295 * RangeTblEntry-s generated for the child rels, and make use of the
1296 * AppendRelInfo entries for them to guide the real planning. (This is
1297 * rather inefficient; we could perhaps stop short of making a full Path
1298 * tree. But this whole function is inefficient and slated for
1299 * destruction, so let's not contort query_planner for that.)
1300 */
1301 {
1302 PlannerInfo *subroot;
1303
1304 /*
1305 * Flat-copy the PlannerInfo to prevent modification of the original.
1306 */
1307 subroot = makeNode(PlannerInfo);
1308 memcpy(subroot, root, sizeof(PlannerInfo));
1309
1310 /*
1311 * Make a deep copy of the parsetree for this planning cycle to mess
1312 * around with, and change it to look like a SELECT. (Hack alert: the
1313 * target RTE still has updatedCols set if this is an UPDATE, so that
1314 * expand_partitioned_rtentry will correctly update
1315 * subroot->partColsUpdated.)
1316 */
1317 subroot->parse = copyObject(root->parse);
1318
1319 subroot->parse->commandType = CMD_SELECT;
1320 subroot->parse->resultRelation = 0;
1321
1322 /*
1323 * Ensure the subroot has its own copy of the original
1324 * append_rel_list, since it'll be scribbled on. (Note that at this
1325 * point, the list only contains AppendRelInfos for flattened UNION
1326 * ALL subqueries.)
1327 */
1328 subroot->append_rel_list = copyObject(root->append_rel_list);
1329
1330 /*
1331 * Better make a private copy of the rowMarks, too.
1332 */
1333 subroot->rowMarks = copyObject(root->rowMarks);
1334
1335 /* There shouldn't be any OJ info to translate, as yet */
1336 Assert(subroot->join_info_list == NIL);
1337 /* and we haven't created PlaceHolderInfos, either */
1338 Assert(subroot->placeholder_list == NIL);
1339
1340 /* Generate Path(s) for accessing this result relation */
1341 grouping_planner(subroot, true, 0.0 /* retrieve all tuples */ );
1342
1343 /* Extract the info we need. */
1344 select_rtable = subroot->parse->rtable;
1345 select_appinfos = subroot->append_rel_list;
1346
1347 /*
1348 * We need to propagate partColsUpdated back, too. (The later
1349 * planning cycles will not set this because they won't run
1350 * expand_partitioned_rtentry for the UPDATE target.)
1351 */
1352 root->partColsUpdated = subroot->partColsUpdated;
1353 }
1354
1355 /*----------
1356 * Since only one rangetable can exist in the final plan, we need to make
1357 * sure that it contains all the RTEs needed for any child plan. This is
1358 * complicated by the need to use separate subquery RTEs for each child.
1359 * We arrange the final rtable as follows:
1360 * 1. All original rtable entries (with their original RT indexes).
1361 * 2. All the relation RTEs generated for children of the target table.
1362 * 3. Subquery RTEs for children after the first. We need N * (K - 1)
1363 * RT slots for this, if there are N subqueries and K child tables.
1364 * 4. Additional RTEs generated during the child planning runs, such as
1365 * children of inheritable RTEs other than the target table.
1366 * We assume that each child planning run will create an identical set
1367 * of type-4 RTEs.
1368 *
1369 * So the next thing to do is append the type-2 RTEs (the target table's
1370 * children) to the original rtable. We look through select_appinfos
1371 * to find them.
1372 *
1373 * To identify which AppendRelInfos are relevant as we thumb through
1374 * select_appinfos, we need to look for both direct and indirect children
1375 * of top_parentRTindex, so we use a bitmap of known parent relids.
1376 * expand_inherited_rtentry() always processes a parent before any of that
1377 * parent's children, so we should see an intermediate parent before its
1378 * children.
1379 *----------
1380 */
1381 child_appinfos = NIL;
1382 old_child_rtis = NIL;
1383 new_child_rtis = NIL;
1384 parent_relids = bms_make_singleton(top_parentRTindex);
1385 foreach(lc, select_appinfos)
1386 {
1387 AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);
1388 RangeTblEntry *child_rte;
1389
1390 /* append_rel_list contains all append rels; ignore others */
1391 if (!bms_is_member(appinfo->parent_relid, parent_relids))
1392 continue;
1393
1394 /* remember relevant AppendRelInfos for use below */
1395 child_appinfos = lappend(child_appinfos, appinfo);
1396
1397 /* extract RTE for this child rel */
1398 child_rte = rt_fetch(appinfo->child_relid, select_rtable);
1399
1400 /* and append it to the original rtable */
1401 parse->rtable = lappend(parse->rtable, child_rte);
1402
1403 /* remember child's index in the SELECT rtable */
1404 old_child_rtis = lappend_int(old_child_rtis, appinfo->child_relid);
1405
1406 /* and its new index in the final rtable */
1407 new_child_rtis = lappend_int(new_child_rtis, list_length(parse->rtable));
1408
1409 /* if child is itself partitioned, update parent_relids */
1410 if (child_rte->inh)
1411 {
1412 Assert(child_rte->relkind == RELKIND_PARTITIONED_TABLE);
1413 parent_relids = bms_add_member(parent_relids, appinfo->child_relid);
1414 }
1415 }
1416
1417 /*
1418 * It's possible that the RTIs we just assigned for the child rels in the
1419 * final rtable are different from what they were in the SELECT query.
1420 * Adjust the AppendRelInfos so that they will correctly map RT indexes to
1421 * the final indexes. We can do this left-to-right since no child rel's
1422 * final RT index could be greater than what it had in the SELECT query.
1423 */
1424 forboth(lc, old_child_rtis, lc2, new_child_rtis)
1425 {
1426 int old_child_rti = lfirst_int(lc);
1427 int new_child_rti = lfirst_int(lc2);
1428
1429 if (old_child_rti == new_child_rti)
1430 continue; /* nothing to do */
1431
1432 Assert(old_child_rti > new_child_rti);
1433
1434 ChangeVarNodes((Node *) child_appinfos,
1435 old_child_rti, new_child_rti, 0);
1436 }
1437
1438 /*
1439 * Now set up rangetable entries for subqueries for additional children
1440 * (the first child will just use the original ones). These all have to
1441 * look more or less real, or EXPLAIN will get unhappy; so we just make
1442 * them all clones of the original subqueries.
1443 */
1444 next_subquery_rti = list_length(parse->rtable) + 1;
1445 if (subqueryRTindexes != NULL)
1446 {
1447 int n_children = list_length(child_appinfos);
1448
1449 while (n_children-- > 1)
1450 {
1451 int oldrti = -1;
1452
1453 while ((oldrti = bms_next_member(subqueryRTindexes, oldrti)) >= 0)
1454 {
1455 RangeTblEntry *subqrte;
1456
1457 subqrte = rt_fetch(oldrti, parse->rtable);
1458 parse->rtable = lappend(parse->rtable, copyObject(subqrte));
1459 }
1460 }
1461 }
1462
1463 /*
1464 * The query for each child is obtained by translating the query for its
1465 * immediate parent, since the AppendRelInfo data we have shows deltas
1466 * between parents and children. We use the parent_parses array to
1467 * remember the appropriate query trees. This is indexed by parent relid.
1468 * Since the maximum number of parents is limited by the number of RTEs in
1469 * the SELECT query, we use that number to allocate the array. An extra
1470 * entry is needed since relids start from 1.
1471 */
1472 parent_parses = (Query **) palloc0((list_length(select_rtable) + 1) *
1473 sizeof(Query *));
1474 parent_parses[top_parentRTindex] = parse;
1475
1476 /*
1477 * And now we can get on with generating a plan for each child table.
1478 */
1479 foreach(lc, child_appinfos)
1480 {
1481 AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);
1482 Index this_subquery_rti = next_subquery_rti;
1483 Query *parent_parse;
1484 PlannerInfo *subroot;
1485 RangeTblEntry *child_rte;
1486 RelOptInfo *sub_final_rel;
1487 Path *subpath;
1488
1489 /*
1490 * expand_inherited_rtentry() always processes a parent before any of
1491 * that parent's children, so the parent query for this relation
1492 * should already be available.
1493 */
1494 parent_parse = parent_parses[appinfo->parent_relid];
1495 Assert(parent_parse != NULL);
1496
1497 /*
1498 * We need a working copy of the PlannerInfo so that we can control
1499 * propagation of information back to the main copy.
1500 */
1501 subroot = makeNode(PlannerInfo);
1502 memcpy(subroot, root, sizeof(PlannerInfo));
1503
1504 /*
1505 * Generate modified query with this rel as target. We first apply
1506 * adjust_appendrel_attrs, which copies the Query and changes
1507 * references to the parent RTE to refer to the current child RTE,
1508 * then fool around with subquery RTEs.
1509 */
1510 subroot->parse = (Query *)
1511 adjust_appendrel_attrs(subroot,
1512 (Node *) parent_parse,
1513 1, &appinfo);
1514
1515 /*
1516 * If there are securityQuals attached to the parent, move them to the
1517 * child rel (they've already been transformed properly for that).
1518 */
1519 parent_rte = rt_fetch(appinfo->parent_relid, subroot->parse->rtable);
1520 child_rte = rt_fetch(appinfo->child_relid, subroot->parse->rtable);
1521 child_rte->securityQuals = parent_rte->securityQuals;
1522 parent_rte->securityQuals = NIL;
1523
1524 /*
1525 * HACK: setting this to a value other than INHKIND_NONE signals to
1526 * relation_excluded_by_constraints() to treat the result relation as
1527 * being an appendrel member.
1528 */
1529 subroot->inhTargetKind =
1530 (rootRelation != 0) ? INHKIND_PARTITIONED : INHKIND_INHERITED;
1531
1532 /*
1533 * If this child is further partitioned, remember it as a parent.
1534 * Since a partitioned table does not have any data, we don't need to
1535 * create a plan for it, and we can stop processing it here. We do,
1536 * however, need to remember its modified PlannerInfo for use when
1537 * processing its children, since we'll update their varnos based on
1538 * the delta from immediate parent to child, not from top to child.
1539 *
1540 * Note: a very non-obvious point is that we have not yet added
1541 * duplicate subquery RTEs to the subroot's rtable. We mustn't,
1542 * because then its children would have two sets of duplicates,
1543 * confusing matters.
1544 */
1545 if (child_rte->inh)
1546 {
1547 Assert(child_rte->relkind == RELKIND_PARTITIONED_TABLE);
1548 parent_parses[appinfo->child_relid] = subroot->parse;
1549 continue;
1550 }
1551
1552 /*
1553 * Set the nominal target relation of the ModifyTable node if not
1554 * already done. If the target is a partitioned table, we already set
1555 * nominalRelation to refer to the partition root, above. For
1556 * non-partitioned inheritance cases, we'll use the first child
1557 * relation (even if it's excluded) as the nominal target relation.
1558 * Because of the way expand_inherited_rtentry works, that should be
1559 * the RTE representing the parent table in its role as a simple
1560 * member of the inheritance set.
1561 *
1562 * It would be logically cleaner to *always* use the inheritance
1563 * parent RTE as the nominal relation; but that RTE is not otherwise
1564 * referenced in the plan in the non-partitioned inheritance case.
1565 * Instead the duplicate child RTE created by expand_inherited_rtentry
1566 * is used elsewhere in the plan, so using the original parent RTE
1567 * would give rise to confusing use of multiple aliases in EXPLAIN
1568 * output for what the user will think is the "same" table. OTOH,
1569 * it's not a problem in the partitioned inheritance case, because
1570 * there is no duplicate RTE for the parent.
1571 */
1572 if (nominalRelation < 0)
1573 nominalRelation = appinfo->child_relid;
1574
1575 /*
1576 * As above, each child plan run needs its own append_rel_list and
1577 * rowmarks, which should start out as pristine copies of the
1578 * originals. There can't be any references to UPDATE/DELETE target
1579 * rels in them; but there could be subquery references, which we'll
1580 * fix up in a moment.
1581 */
1582 subroot->append_rel_list = copyObject(root->append_rel_list);
1583 subroot->rowMarks = copyObject(root->rowMarks);
1584
1585 /*
1586 * If this isn't the first child Query, adjust Vars and jointree
1587 * entries to reference the appropriate set of subquery RTEs.
1588 */
1589 if (final_rtable != NIL && subqueryRTindexes != NULL)
1590 {
1591 int oldrti = -1;
1592
1593 while ((oldrti = bms_next_member(subqueryRTindexes, oldrti)) >= 0)
1594 {
1595 Index newrti = next_subquery_rti++;
1596
1597 ChangeVarNodes((Node *) subroot->parse, oldrti, newrti, 0);
1598 ChangeVarNodes((Node *) subroot->append_rel_list,
1599 oldrti, newrti, 0);
1600 ChangeVarNodes((Node *) subroot->rowMarks, oldrti, newrti, 0);
1601 }
1602 }
1603
1604 /* There shouldn't be any OJ info to translate, as yet */
1605 Assert(subroot->join_info_list == NIL);
1606 /* and we haven't created PlaceHolderInfos, either */
1607 Assert(subroot->placeholder_list == NIL);
1608
1609 /* Generate Path(s) for accessing this result relation */
1610 grouping_planner(subroot, true, 0.0 /* retrieve all tuples */ );
1611
1612 /*
1613 * Select cheapest path in case there's more than one. We always run
1614 * modification queries to conclusion, so we care only for the
1615 * cheapest-total path.
1616 */
1617 sub_final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
1618 set_cheapest(sub_final_rel);
1619 subpath = sub_final_rel->cheapest_total_path;
1620
1621 /*
1622 * If this child rel was excluded by constraint exclusion, exclude it
1623 * from the result plan.
1624 */
1625 if (IS_DUMMY_REL(sub_final_rel))
1626 continue;
1627
1628 /*
1629 * If this is the first non-excluded child, its post-planning rtable
1630 * becomes the initial contents of final_rtable; otherwise, copy its
1631 * modified subquery RTEs into final_rtable, to ensure we have sane
1632 * copies of those. Also save the first non-excluded child's version
1633 * of the rowmarks list; we assume all children will end up with
1634 * equivalent versions of that. Likewise for append_rel_list.
1635 */
1636 if (final_rtable == NIL)
1637 {
1638 final_rtable = subroot->parse->rtable;
1639 final_rowmarks = subroot->rowMarks;
1640 final_appendrels = subroot->append_rel_list;
1641 }
1642 else
1643 {
1644 Assert(list_length(final_rtable) ==
1645 list_length(subroot->parse->rtable));
1646 if (subqueryRTindexes != NULL)
1647 {
1648 int oldrti = -1;
1649
1650 while ((oldrti = bms_next_member(subqueryRTindexes, oldrti)) >= 0)
1651 {
1652 Index newrti = this_subquery_rti++;
1653 RangeTblEntry *subqrte;
1654 ListCell *newrticell;
1655
1656 subqrte = rt_fetch(newrti, subroot->parse->rtable);
1657 newrticell = list_nth_cell(final_rtable, newrti - 1);
1658 lfirst(newrticell) = subqrte;
1659 }
1660 }
1661 }
1662
1663 /*
1664 * We need to collect all the RelOptInfos from all child plans into
1665 * the main PlannerInfo, since setrefs.c will need them. We use the
1666 * last child's simple_rel_array, so we have to propagate forward the
1667 * RelOptInfos that were already built in previous children.
1668 */
1669 Assert(subroot->simple_rel_array_size >= save_rel_array_size);
1670 for (rti = 1; rti < save_rel_array_size; rti++)
1671 {
1672 RelOptInfo *brel = save_rel_array[rti];
1673
1674 if (brel)
1675 subroot->simple_rel_array[rti] = brel;
1676 }
1677 save_rel_array_size = subroot->simple_rel_array_size;
1678 save_rel_array = subroot->simple_rel_array;
1679 save_append_rel_array = subroot->append_rel_array;
1680
1681 /*
1682 * Make sure any initplans from this rel get into the outer list. Note
1683 * we're effectively assuming all children generate the same
1684 * init_plans.
1685 */
1686 root->init_plans = subroot->init_plans;
1687
1688 /* Build list of sub-paths */
1689 subpaths = lappend(subpaths, subpath);
1690
1691 /* Build list of modified subroots, too */
1692 subroots = lappend(subroots, subroot);
1693
1694 /* Build list of target-relation RT indexes */
1695 resultRelations = lappend_int(resultRelations, appinfo->child_relid);
1696
1697 /* Build lists of per-relation WCO and RETURNING targetlists */
1698 if (parse->withCheckOptions)
1699 withCheckOptionLists = lappend(withCheckOptionLists,
1700 subroot->parse->withCheckOptions);
1701 if (parse->returningList)
1702 returningLists = lappend(returningLists,
1703 subroot->parse->returningList);
1704
1705 Assert(!parse->onConflict);
1706 }
1707
1708 /* Result path must go into outer query's FINAL upperrel */
1709 final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
1710
1711 /*
1712 * We don't currently worry about setting final_rel's consider_parallel
1713 * flag in this case, nor about allowing FDWs or create_upper_paths_hook
1714 * to get control here.
1715 */
1716
1717 if (subpaths == NIL)
1718 {
1719 /*
1720 * We managed to exclude every child rel, so generate a dummy path
1721 * representing the empty set. Although it's clear that no data will
1722 * be updated or deleted, we will still need to have a ModifyTable
1723 * node so that any statement triggers are executed. (This could be
1724 * cleaner if we fixed nodeModifyTable.c to support zero child nodes,
1725 * but that probably wouldn't be a net win.)
1726 */
1727 Path *dummy_path;
1728
1729 /* tlist processing never got done, either */
1730 root->processed_tlist = preprocess_targetlist(root);
1731 final_rel->reltarget = create_pathtarget(root, root->processed_tlist);
1732
1733 /* Make a dummy path, cf set_dummy_rel_pathlist() */
1734 dummy_path = (Path *) create_append_path(NULL, final_rel, NIL, NIL,
1735 NIL, NULL, 0, false,
1736 NIL, -1);
1737
1738 /* These lists must be nonempty to make a valid ModifyTable node */
1739 subpaths = list_make1(dummy_path);
1740 subroots = list_make1(root);
1741 resultRelations = list_make1_int(parse->resultRelation);
1742 if (parse->withCheckOptions)
1743 withCheckOptionLists = list_make1(parse->withCheckOptions);
1744 if (parse->returningList)
1745 returningLists = list_make1(parse->returningList);
1746 /* Disable tuple routing, too, just to be safe */
1747 root->partColsUpdated = false;
1748 }
1749 else
1750 {
1751 /*
1752 * Put back the final adjusted rtable into the master copy of the
1753 * Query. (We mustn't do this if we found no non-excluded children,
1754 * since we never saved an adjusted rtable at all.)
1755 */
1756 parse->rtable = final_rtable;
1757 root->simple_rel_array_size = save_rel_array_size;
1758 root->simple_rel_array = save_rel_array;
1759 root->append_rel_array = save_append_rel_array;
1760
1761 /* Must reconstruct master's simple_rte_array, too */
1762 root->simple_rte_array = (RangeTblEntry **)
1763 palloc0((list_length(final_rtable) + 1) * sizeof(RangeTblEntry *));
1764 rti = 1;
1765 foreach(lc, final_rtable)
1766 {
1767 RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
1768
1769 root->simple_rte_array[rti++] = rte;
1770 }
1771
1772 /* Put back adjusted rowmarks and appendrels, too */
1773 root->rowMarks = final_rowmarks;
1774 root->append_rel_list = final_appendrels;
1775 }
1776
1777 /*
1778 * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node will
1779 * have dealt with fetching non-locked marked rows, else we need to have
1780 * ModifyTable do that.
1781 */
1782 if (parse->rowMarks)
1783 rowMarks = NIL;
1784 else
1785 rowMarks = root->rowMarks;
1786
1787 /* Create Path representing a ModifyTable to do the UPDATE/DELETE work */
1788 add_path(final_rel, (Path *)
1789 create_modifytable_path(root, final_rel,
1790 parse->commandType,
1791 parse->canSetTag,
1792 nominalRelation,
1793 rootRelation,
1794 root->partColsUpdated,
1795 resultRelations,
1796 subpaths,
1797 subroots,
1798 withCheckOptionLists,
1799 returningLists,
1800 rowMarks,
1801 NULL,
1802 assign_special_exec_param(root)));
1803 }
1804
1805 /*--------------------
1806 * grouping_planner
1807 * Perform planning steps related to grouping, aggregation, etc.
1808 *
1809 * This function adds all required top-level processing to the scan/join
1810 * Path(s) produced by query_planner.
1811 *
1812 * If inheritance_update is true, we're being called from inheritance_planner
1813 * and should not include a ModifyTable step in the resulting Path(s).
1814 * (inheritance_planner will create a single ModifyTable node covering all the
1815 * target tables.)
1816 *
1817 * tuple_fraction is the fraction of tuples we expect will be retrieved.
1818 * tuple_fraction is interpreted as follows:
1819 * 0: expect all tuples to be retrieved (normal case)
1820 * 0 < tuple_fraction < 1: expect the given fraction of tuples available
1821 * from the plan to be retrieved
1822 * tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
1823 * expected to be retrieved (ie, a LIMIT specification)
1824 *
1825 * Returns nothing; the useful output is in the Paths we attach to the
1826 * (UPPERREL_FINAL, NULL) upperrel in *root. In addition,
1827 * root->processed_tlist contains the final processed targetlist.
1828 *
1829 * Note that we have not done set_cheapest() on the final rel; it's convenient
1830 * to leave this to the caller.
1831 *--------------------
1832 */
1833 static void
grouping_planner(PlannerInfo * root,bool inheritance_update,double tuple_fraction)1834 grouping_planner(PlannerInfo *root, bool inheritance_update,
1835 double tuple_fraction)
1836 {
1837 Query *parse = root->parse;
1838 int64 offset_est = 0;
1839 int64 count_est = 0;
1840 double limit_tuples = -1.0;
1841 bool have_postponed_srfs = false;
1842 PathTarget *final_target;
1843 List *final_targets;
1844 List *final_targets_contain_srfs;
1845 bool final_target_parallel_safe;
1846 RelOptInfo *current_rel;
1847 RelOptInfo *final_rel;
1848 FinalPathExtraData extra;
1849 ListCell *lc;
1850
1851 /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
1852 if (parse->limitCount || parse->limitOffset)
1853 {
1854 tuple_fraction = preprocess_limit(root, tuple_fraction,
1855 &offset_est, &count_est);
1856
1857 /*
1858 * If we have a known LIMIT, and don't have an unknown OFFSET, we can
1859 * estimate the effects of using a bounded sort.
1860 */
1861 if (count_est > 0 && offset_est >= 0)
1862 limit_tuples = (double) count_est + (double) offset_est;
1863 }
1864
1865 /* Make tuple_fraction accessible to lower-level routines */
1866 root->tuple_fraction = tuple_fraction;
1867
1868 if (parse->setOperations)
1869 {
1870 /*
1871 * If there's a top-level ORDER BY, assume we have to fetch all the
1872 * tuples. This might be too simplistic given all the hackery below
1873 * to possibly avoid the sort; but the odds of accurate estimates here
1874 * are pretty low anyway. XXX try to get rid of this in favor of
1875 * letting plan_set_operations generate both fast-start and
1876 * cheapest-total paths.
1877 */
1878 if (parse->sortClause)
1879 root->tuple_fraction = 0.0;
1880
1881 /*
1882 * Construct Paths for set operations. The results will not need any
1883 * work except perhaps a top-level sort and/or LIMIT. Note that any
1884 * special work for recursive unions is the responsibility of
1885 * plan_set_operations.
1886 */
1887 current_rel = plan_set_operations(root);
1888
1889 /*
1890 * We should not need to call preprocess_targetlist, since we must be
1891 * in a SELECT query node. Instead, use the processed_tlist returned
1892 * by plan_set_operations (since this tells whether it returned any
1893 * resjunk columns!), and transfer any sort key information from the
1894 * original tlist.
1895 */
1896 Assert(parse->commandType == CMD_SELECT);
1897
1898 /* for safety, copy processed_tlist instead of modifying in-place */
1899 root->processed_tlist =
1900 postprocess_setop_tlist(copyObject(root->processed_tlist),
1901 parse->targetList);
1902
1903 /* Also extract the PathTarget form of the setop result tlist */
1904 final_target = current_rel->cheapest_total_path->pathtarget;
1905
1906 /* And check whether it's parallel safe */
1907 final_target_parallel_safe =
1908 is_parallel_safe(root, (Node *) final_target->exprs);
1909
1910 /* The setop result tlist couldn't contain any SRFs */
1911 Assert(!parse->hasTargetSRFs);
1912 final_targets = final_targets_contain_srfs = NIL;
1913
1914 /*
1915 * Can't handle FOR [KEY] UPDATE/SHARE here (parser should have
1916 * checked already, but let's make sure).
1917 */
1918 if (parse->rowMarks)
1919 ereport(ERROR,
1920 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1921 /*------
1922 translator: %s is a SQL row locking clause such as FOR UPDATE */
1923 errmsg("%s is not allowed with UNION/INTERSECT/EXCEPT",
1924 LCS_asString(linitial_node(RowMarkClause,
1925 parse->rowMarks)->strength))));
1926
1927 /*
1928 * Calculate pathkeys that represent result ordering requirements
1929 */
1930 Assert(parse->distinctClause == NIL);
1931 root->sort_pathkeys = make_pathkeys_for_sortclauses(root,
1932 parse->sortClause,
1933 root->processed_tlist);
1934 }
1935 else
1936 {
1937 /* No set operations, do regular planning */
1938 PathTarget *sort_input_target;
1939 List *sort_input_targets;
1940 List *sort_input_targets_contain_srfs;
1941 bool sort_input_target_parallel_safe;
1942 PathTarget *grouping_target;
1943 List *grouping_targets;
1944 List *grouping_targets_contain_srfs;
1945 bool grouping_target_parallel_safe;
1946 PathTarget *scanjoin_target;
1947 List *scanjoin_targets;
1948 List *scanjoin_targets_contain_srfs;
1949 bool scanjoin_target_parallel_safe;
1950 bool scanjoin_target_same_exprs;
1951 bool have_grouping;
1952 AggClauseCosts agg_costs;
1953 WindowFuncLists *wflists = NULL;
1954 List *activeWindows = NIL;
1955 grouping_sets_data *gset_data = NULL;
1956 standard_qp_extra qp_extra;
1957
1958 /* A recursive query should always have setOperations */
1959 Assert(!root->hasRecursion);
1960
1961 /* Preprocess grouping sets and GROUP BY clause, if any */
1962 if (parse->groupingSets)
1963 {
1964 gset_data = preprocess_grouping_sets(root);
1965 }
1966 else
1967 {
1968 /* Preprocess regular GROUP BY clause, if any */
1969 if (parse->groupClause)
1970 parse->groupClause = preprocess_groupclause(root, NIL);
1971 }
1972
1973 /*
1974 * Preprocess targetlist. Note that much of the remaining planning
1975 * work will be done with the PathTarget representation of tlists, but
1976 * we must also maintain the full representation of the final tlist so
1977 * that we can transfer its decoration (resnames etc) to the topmost
1978 * tlist of the finished Plan. This is kept in processed_tlist.
1979 */
1980 root->processed_tlist = preprocess_targetlist(root);
1981
1982 /*
1983 * Collect statistics about aggregates for estimating costs, and mark
1984 * all the aggregates with resolved aggtranstypes. We must do this
1985 * before slicing and dicing the tlist into various pathtargets, else
1986 * some copies of the Aggref nodes might escape being marked with the
1987 * correct transtypes.
1988 *
1989 * Note: currently, we do not detect duplicate aggregates here. This
1990 * may result in somewhat-overestimated cost, which is fine for our
1991 * purposes since all Paths will get charged the same. But at some
1992 * point we might wish to do that detection in the planner, rather
1993 * than during executor startup.
1994 */
1995 MemSet(&agg_costs, 0, sizeof(AggClauseCosts));
1996 if (parse->hasAggs)
1997 {
1998 get_agg_clause_costs(root, (Node *) root->processed_tlist,
1999 AGGSPLIT_SIMPLE, &agg_costs);
2000 get_agg_clause_costs(root, parse->havingQual, AGGSPLIT_SIMPLE,
2001 &agg_costs);
2002 }
2003
2004 /*
2005 * Locate any window functions in the tlist. (We don't need to look
2006 * anywhere else, since expressions used in ORDER BY will be in there
2007 * too.) Note that they could all have been eliminated by constant
2008 * folding, in which case we don't need to do any more work.
2009 */
2010 if (parse->hasWindowFuncs)
2011 {
2012 wflists = find_window_functions((Node *) root->processed_tlist,
2013 list_length(parse->windowClause));
2014 if (wflists->numWindowFuncs > 0)
2015 activeWindows = select_active_windows(root, wflists);
2016 else
2017 parse->hasWindowFuncs = false;
2018 }
2019
2020 /*
2021 * Preprocess MIN/MAX aggregates, if any. Note: be careful about
2022 * adding logic between here and the query_planner() call. Anything
2023 * that is needed in MIN/MAX-optimizable cases will have to be
2024 * duplicated in planagg.c.
2025 */
2026 if (parse->hasAggs)
2027 preprocess_minmax_aggregates(root);
2028
2029 /*
2030 * Figure out whether there's a hard limit on the number of rows that
2031 * query_planner's result subplan needs to return. Even if we know a
2032 * hard limit overall, it doesn't apply if the query has any
2033 * grouping/aggregation operations, or SRFs in the tlist.
2034 */
2035 if (parse->groupClause ||
2036 parse->groupingSets ||
2037 parse->distinctClause ||
2038 parse->hasAggs ||
2039 parse->hasWindowFuncs ||
2040 parse->hasTargetSRFs ||
2041 root->hasHavingQual)
2042 root->limit_tuples = -1.0;
2043 else
2044 root->limit_tuples = limit_tuples;
2045
2046 /* Set up data needed by standard_qp_callback */
2047 qp_extra.activeWindows = activeWindows;
2048 qp_extra.groupClause = (gset_data
2049 ? (gset_data->rollups ? linitial_node(RollupData, gset_data->rollups)->groupClause : NIL)
2050 : parse->groupClause);
2051
2052 /*
2053 * Generate the best unsorted and presorted paths for the scan/join
2054 * portion of this Query, ie the processing represented by the
2055 * FROM/WHERE clauses. (Note there may not be any presorted paths.)
2056 * We also generate (in standard_qp_callback) pathkey representations
2057 * of the query's sort clause, distinct clause, etc.
2058 */
2059 current_rel = query_planner(root, standard_qp_callback, &qp_extra);
2060
2061 /*
2062 * Convert the query's result tlist into PathTarget format.
2063 *
2064 * Note: this cannot be done before query_planner() has performed
2065 * appendrel expansion, because that might add resjunk entries to
2066 * root->processed_tlist. Waiting till afterwards is also helpful
2067 * because the target width estimates can use per-Var width numbers
2068 * that were obtained within query_planner().
2069 */
2070 final_target = create_pathtarget(root, root->processed_tlist);
2071 final_target_parallel_safe =
2072 is_parallel_safe(root, (Node *) final_target->exprs);
2073
2074 /*
2075 * If ORDER BY was given, consider whether we should use a post-sort
2076 * projection, and compute the adjusted target for preceding steps if
2077 * so.
2078 */
2079 if (parse->sortClause)
2080 {
2081 sort_input_target = make_sort_input_target(root,
2082 final_target,
2083 &have_postponed_srfs);
2084 sort_input_target_parallel_safe =
2085 is_parallel_safe(root, (Node *) sort_input_target->exprs);
2086 }
2087 else
2088 {
2089 sort_input_target = final_target;
2090 sort_input_target_parallel_safe = final_target_parallel_safe;
2091 }
2092
2093 /*
2094 * If we have window functions to deal with, the output from any
2095 * grouping step needs to be what the window functions want;
2096 * otherwise, it should be sort_input_target.
2097 */
2098 if (activeWindows)
2099 {
2100 grouping_target = make_window_input_target(root,
2101 final_target,
2102 activeWindows);
2103 grouping_target_parallel_safe =
2104 is_parallel_safe(root, (Node *) grouping_target->exprs);
2105 }
2106 else
2107 {
2108 grouping_target = sort_input_target;
2109 grouping_target_parallel_safe = sort_input_target_parallel_safe;
2110 }
2111
2112 /*
2113 * If we have grouping or aggregation to do, the topmost scan/join
2114 * plan node must emit what the grouping step wants; otherwise, it
2115 * should emit grouping_target.
2116 */
2117 have_grouping = (parse->groupClause || parse->groupingSets ||
2118 parse->hasAggs || root->hasHavingQual);
2119 if (have_grouping)
2120 {
2121 scanjoin_target = make_group_input_target(root, final_target);
2122 scanjoin_target_parallel_safe =
2123 is_parallel_safe(root, (Node *) scanjoin_target->exprs);
2124 }
2125 else
2126 {
2127 scanjoin_target = grouping_target;
2128 scanjoin_target_parallel_safe = grouping_target_parallel_safe;
2129 }
2130
2131 /*
2132 * If there are any SRFs in the targetlist, we must separate each of
2133 * these PathTargets into SRF-computing and SRF-free targets. Replace
2134 * each of the named targets with a SRF-free version, and remember the
2135 * list of additional projection steps we need to add afterwards.
2136 */
2137 if (parse->hasTargetSRFs)
2138 {
2139 /* final_target doesn't recompute any SRFs in sort_input_target */
2140 split_pathtarget_at_srfs(root, final_target, sort_input_target,
2141 &final_targets,
2142 &final_targets_contain_srfs);
2143 final_target = linitial_node(PathTarget, final_targets);
2144 Assert(!linitial_int(final_targets_contain_srfs));
2145 /* likewise for sort_input_target vs. grouping_target */
2146 split_pathtarget_at_srfs(root, sort_input_target, grouping_target,
2147 &sort_input_targets,
2148 &sort_input_targets_contain_srfs);
2149 sort_input_target = linitial_node(PathTarget, sort_input_targets);
2150 Assert(!linitial_int(sort_input_targets_contain_srfs));
2151 /* likewise for grouping_target vs. scanjoin_target */
2152 split_pathtarget_at_srfs(root, grouping_target, scanjoin_target,
2153 &grouping_targets,
2154 &grouping_targets_contain_srfs);
2155 grouping_target = linitial_node(PathTarget, grouping_targets);
2156 Assert(!linitial_int(grouping_targets_contain_srfs));
2157 /* scanjoin_target will not have any SRFs precomputed for it */
2158 split_pathtarget_at_srfs(root, scanjoin_target, NULL,
2159 &scanjoin_targets,
2160 &scanjoin_targets_contain_srfs);
2161 scanjoin_target = linitial_node(PathTarget, scanjoin_targets);
2162 Assert(!linitial_int(scanjoin_targets_contain_srfs));
2163 }
2164 else
2165 {
2166 /* initialize lists; for most of these, dummy values are OK */
2167 final_targets = final_targets_contain_srfs = NIL;
2168 sort_input_targets = sort_input_targets_contain_srfs = NIL;
2169 grouping_targets = grouping_targets_contain_srfs = NIL;
2170 scanjoin_targets = list_make1(scanjoin_target);
2171 scanjoin_targets_contain_srfs = NIL;
2172 }
2173
2174 /* Apply scan/join target. */
2175 scanjoin_target_same_exprs = list_length(scanjoin_targets) == 1
2176 && equal(scanjoin_target->exprs, current_rel->reltarget->exprs);
2177 apply_scanjoin_target_to_paths(root, current_rel, scanjoin_targets,
2178 scanjoin_targets_contain_srfs,
2179 scanjoin_target_parallel_safe,
2180 scanjoin_target_same_exprs);
2181
2182 /*
2183 * Save the various upper-rel PathTargets we just computed into
2184 * root->upper_targets[]. The core code doesn't use this, but it
2185 * provides a convenient place for extensions to get at the info. For
2186 * consistency, we save all the intermediate targets, even though some
2187 * of the corresponding upperrels might not be needed for this query.
2188 */
2189 root->upper_targets[UPPERREL_FINAL] = final_target;
2190 root->upper_targets[UPPERREL_ORDERED] = final_target;
2191 root->upper_targets[UPPERREL_DISTINCT] = sort_input_target;
2192 root->upper_targets[UPPERREL_WINDOW] = sort_input_target;
2193 root->upper_targets[UPPERREL_GROUP_AGG] = grouping_target;
2194
2195 /*
2196 * If we have grouping and/or aggregation, consider ways to implement
2197 * that. We build a new upperrel representing the output of this
2198 * phase.
2199 */
2200 if (have_grouping)
2201 {
2202 current_rel = create_grouping_paths(root,
2203 current_rel,
2204 grouping_target,
2205 grouping_target_parallel_safe,
2206 &agg_costs,
2207 gset_data);
2208 /* Fix things up if grouping_target contains SRFs */
2209 if (parse->hasTargetSRFs)
2210 adjust_paths_for_srfs(root, current_rel,
2211 grouping_targets,
2212 grouping_targets_contain_srfs);
2213 }
2214
2215 /*
2216 * If we have window functions, consider ways to implement those. We
2217 * build a new upperrel representing the output of this phase.
2218 */
2219 if (activeWindows)
2220 {
2221 current_rel = create_window_paths(root,
2222 current_rel,
2223 grouping_target,
2224 sort_input_target,
2225 sort_input_target_parallel_safe,
2226 wflists,
2227 activeWindows);
2228 /* Fix things up if sort_input_target contains SRFs */
2229 if (parse->hasTargetSRFs)
2230 adjust_paths_for_srfs(root, current_rel,
2231 sort_input_targets,
2232 sort_input_targets_contain_srfs);
2233 }
2234
2235 /*
2236 * If there is a DISTINCT clause, consider ways to implement that. We
2237 * build a new upperrel representing the output of this phase.
2238 */
2239 if (parse->distinctClause)
2240 {
2241 current_rel = create_distinct_paths(root,
2242 current_rel);
2243 }
2244 } /* end of if (setOperations) */
2245
2246 /*
2247 * If ORDER BY was given, consider ways to implement that, and generate a
2248 * new upperrel containing only paths that emit the correct ordering and
2249 * project the correct final_target. We can apply the original
2250 * limit_tuples limit in sort costing here, but only if there are no
2251 * postponed SRFs.
2252 */
2253 if (parse->sortClause)
2254 {
2255 current_rel = create_ordered_paths(root,
2256 current_rel,
2257 final_target,
2258 final_target_parallel_safe,
2259 have_postponed_srfs ? -1.0 :
2260 limit_tuples);
2261 /* Fix things up if final_target contains SRFs */
2262 if (parse->hasTargetSRFs)
2263 adjust_paths_for_srfs(root, current_rel,
2264 final_targets,
2265 final_targets_contain_srfs);
2266 }
2267
2268 /*
2269 * Now we are prepared to build the final-output upperrel.
2270 */
2271 final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
2272
2273 /*
2274 * If the input rel is marked consider_parallel and there's nothing that's
2275 * not parallel-safe in the LIMIT clause, then the final_rel can be marked
2276 * consider_parallel as well. Note that if the query has rowMarks or is
2277 * not a SELECT, consider_parallel will be false for every relation in the
2278 * query.
2279 */
2280 if (current_rel->consider_parallel &&
2281 is_parallel_safe(root, parse->limitOffset) &&
2282 is_parallel_safe(root, parse->limitCount))
2283 final_rel->consider_parallel = true;
2284
2285 /*
2286 * If the current_rel belongs to a single FDW, so does the final_rel.
2287 */
2288 final_rel->serverid = current_rel->serverid;
2289 final_rel->userid = current_rel->userid;
2290 final_rel->useridiscurrent = current_rel->useridiscurrent;
2291 final_rel->fdwroutine = current_rel->fdwroutine;
2292
2293 /*
2294 * Generate paths for the final_rel. Insert all surviving paths, with
2295 * LockRows, Limit, and/or ModifyTable steps added if needed.
2296 */
2297 foreach(lc, current_rel->pathlist)
2298 {
2299 Path *path = (Path *) lfirst(lc);
2300
2301 /*
2302 * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node.
2303 * (Note: we intentionally test parse->rowMarks not root->rowMarks
2304 * here. If there are only non-locking rowmarks, they should be
2305 * handled by the ModifyTable node instead. However, root->rowMarks
2306 * is what goes into the LockRows node.)
2307 */
2308 if (parse->rowMarks)
2309 {
2310 path = (Path *) create_lockrows_path(root, final_rel, path,
2311 root->rowMarks,
2312 assign_special_exec_param(root));
2313 }
2314
2315 /*
2316 * If there is a LIMIT/OFFSET clause, add the LIMIT node.
2317 */
2318 if (limit_needed(parse))
2319 {
2320 path = (Path *) create_limit_path(root, final_rel, path,
2321 parse->limitOffset,
2322 parse->limitCount,
2323 parse->limitOption,
2324 offset_est, count_est);
2325 }
2326
2327 /*
2328 * If this is an INSERT/UPDATE/DELETE, and we're not being called from
2329 * inheritance_planner, add the ModifyTable node.
2330 */
2331 if (parse->commandType != CMD_SELECT && !inheritance_update)
2332 {
2333 Index rootRelation;
2334 List *withCheckOptionLists;
2335 List *returningLists;
2336 List *rowMarks;
2337
2338 /*
2339 * If target is a partition root table, we need to mark the
2340 * ModifyTable node appropriately for that.
2341 */
2342 if (rt_fetch(parse->resultRelation, parse->rtable)->relkind ==
2343 RELKIND_PARTITIONED_TABLE)
2344 rootRelation = parse->resultRelation;
2345 else
2346 rootRelation = 0;
2347
2348 /*
2349 * Set up the WITH CHECK OPTION and RETURNING lists-of-lists, if
2350 * needed.
2351 */
2352 if (parse->withCheckOptions)
2353 withCheckOptionLists = list_make1(parse->withCheckOptions);
2354 else
2355 withCheckOptionLists = NIL;
2356
2357 if (parse->returningList)
2358 returningLists = list_make1(parse->returningList);
2359 else
2360 returningLists = NIL;
2361
2362 /*
2363 * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node
2364 * will have dealt with fetching non-locked marked rows, else we
2365 * need to have ModifyTable do that.
2366 */
2367 if (parse->rowMarks)
2368 rowMarks = NIL;
2369 else
2370 rowMarks = root->rowMarks;
2371
2372 path = (Path *)
2373 create_modifytable_path(root, final_rel,
2374 parse->commandType,
2375 parse->canSetTag,
2376 parse->resultRelation,
2377 rootRelation,
2378 false,
2379 list_make1_int(parse->resultRelation),
2380 list_make1(path),
2381 list_make1(root),
2382 withCheckOptionLists,
2383 returningLists,
2384 rowMarks,
2385 parse->onConflict,
2386 assign_special_exec_param(root));
2387 }
2388
2389 /* And shove it into final_rel */
2390 add_path(final_rel, path);
2391 }
2392
2393 /*
2394 * Generate partial paths for final_rel, too, if outer query levels might
2395 * be able to make use of them.
2396 */
2397 if (final_rel->consider_parallel && root->query_level > 1 &&
2398 !limit_needed(parse))
2399 {
2400 Assert(!parse->rowMarks && parse->commandType == CMD_SELECT);
2401 foreach(lc, current_rel->partial_pathlist)
2402 {
2403 Path *partial_path = (Path *) lfirst(lc);
2404
2405 add_partial_path(final_rel, partial_path);
2406 }
2407 }
2408
2409 extra.limit_needed = limit_needed(parse);
2410 extra.limit_tuples = limit_tuples;
2411 extra.count_est = count_est;
2412 extra.offset_est = offset_est;
2413
2414 /*
2415 * If there is an FDW that's responsible for all baserels of the query,
2416 * let it consider adding ForeignPaths.
2417 */
2418 if (final_rel->fdwroutine &&
2419 final_rel->fdwroutine->GetForeignUpperPaths)
2420 final_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_FINAL,
2421 current_rel, final_rel,
2422 &extra);
2423
2424 /* Let extensions possibly add some more paths */
2425 if (create_upper_paths_hook)
2426 (*create_upper_paths_hook) (root, UPPERREL_FINAL,
2427 current_rel, final_rel, &extra);
2428
2429 /* Note: currently, we leave it to callers to do set_cheapest() */
2430 }
2431
2432 /*
2433 * Do preprocessing for groupingSets clause and related data. This handles the
2434 * preliminary steps of expanding the grouping sets, organizing them into lists
2435 * of rollups, and preparing annotations which will later be filled in with
2436 * size estimates.
2437 */
2438 static grouping_sets_data *
preprocess_grouping_sets(PlannerInfo * root)2439 preprocess_grouping_sets(PlannerInfo *root)
2440 {
2441 Query *parse = root->parse;
2442 List *sets;
2443 int maxref = 0;
2444 ListCell *lc;
2445 ListCell *lc_set;
2446 grouping_sets_data *gd = palloc0(sizeof(grouping_sets_data));
2447
2448 parse->groupingSets = expand_grouping_sets(parse->groupingSets, -1);
2449
2450 gd->any_hashable = false;
2451 gd->unhashable_refs = NULL;
2452 gd->unsortable_refs = NULL;
2453 gd->unsortable_sets = NIL;
2454
2455 if (parse->groupClause)
2456 {
2457 ListCell *lc;
2458
2459 foreach(lc, parse->groupClause)
2460 {
2461 SortGroupClause *gc = lfirst_node(SortGroupClause, lc);
2462 Index ref = gc->tleSortGroupRef;
2463
2464 if (ref > maxref)
2465 maxref = ref;
2466
2467 if (!gc->hashable)
2468 gd->unhashable_refs = bms_add_member(gd->unhashable_refs, ref);
2469
2470 if (!OidIsValid(gc->sortop))
2471 gd->unsortable_refs = bms_add_member(gd->unsortable_refs, ref);
2472 }
2473 }
2474
2475 /* Allocate workspace array for remapping */
2476 gd->tleref_to_colnum_map = (int *) palloc((maxref + 1) * sizeof(int));
2477
2478 /*
2479 * If we have any unsortable sets, we must extract them before trying to
2480 * prepare rollups. Unsortable sets don't go through
2481 * reorder_grouping_sets, so we must apply the GroupingSetData annotation
2482 * here.
2483 */
2484 if (!bms_is_empty(gd->unsortable_refs))
2485 {
2486 List *sortable_sets = NIL;
2487
2488 foreach(lc, parse->groupingSets)
2489 {
2490 List *gset = (List *) lfirst(lc);
2491
2492 if (bms_overlap_list(gd->unsortable_refs, gset))
2493 {
2494 GroupingSetData *gs = makeNode(GroupingSetData);
2495
2496 gs->set = gset;
2497 gd->unsortable_sets = lappend(gd->unsortable_sets, gs);
2498
2499 /*
2500 * We must enforce here that an unsortable set is hashable;
2501 * later code assumes this. Parse analysis only checks that
2502 * every individual column is either hashable or sortable.
2503 *
2504 * Note that passing this test doesn't guarantee we can
2505 * generate a plan; there might be other showstoppers.
2506 */
2507 if (bms_overlap_list(gd->unhashable_refs, gset))
2508 ereport(ERROR,
2509 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2510 errmsg("could not implement GROUP BY"),
2511 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
2512 }
2513 else
2514 sortable_sets = lappend(sortable_sets, gset);
2515 }
2516
2517 if (sortable_sets)
2518 sets = extract_rollup_sets(sortable_sets);
2519 else
2520 sets = NIL;
2521 }
2522 else
2523 sets = extract_rollup_sets(parse->groupingSets);
2524
2525 foreach(lc_set, sets)
2526 {
2527 List *current_sets = (List *) lfirst(lc_set);
2528 RollupData *rollup = makeNode(RollupData);
2529 GroupingSetData *gs;
2530
2531 /*
2532 * Reorder the current list of grouping sets into correct prefix
2533 * order. If only one aggregation pass is needed, try to make the
2534 * list match the ORDER BY clause; if more than one pass is needed, we
2535 * don't bother with that.
2536 *
2537 * Note that this reorders the sets from smallest-member-first to
2538 * largest-member-first, and applies the GroupingSetData annotations,
2539 * though the data will be filled in later.
2540 */
2541 current_sets = reorder_grouping_sets(current_sets,
2542 (list_length(sets) == 1
2543 ? parse->sortClause
2544 : NIL));
2545
2546 /*
2547 * Get the initial (and therefore largest) grouping set.
2548 */
2549 gs = linitial_node(GroupingSetData, current_sets);
2550
2551 /*
2552 * Order the groupClause appropriately. If the first grouping set is
2553 * empty, then the groupClause must also be empty; otherwise we have
2554 * to force the groupClause to match that grouping set's order.
2555 *
2556 * (The first grouping set can be empty even though parse->groupClause
2557 * is not empty only if all non-empty grouping sets are unsortable.
2558 * The groupClauses for hashed grouping sets are built later on.)
2559 */
2560 if (gs->set)
2561 rollup->groupClause = preprocess_groupclause(root, gs->set);
2562 else
2563 rollup->groupClause = NIL;
2564
2565 /*
2566 * Is it hashable? We pretend empty sets are hashable even though we
2567 * actually force them not to be hashed later. But don't bother if
2568 * there's nothing but empty sets (since in that case we can't hash
2569 * anything).
2570 */
2571 if (gs->set &&
2572 !bms_overlap_list(gd->unhashable_refs, gs->set))
2573 {
2574 rollup->hashable = true;
2575 gd->any_hashable = true;
2576 }
2577
2578 /*
2579 * Now that we've pinned down an order for the groupClause for this
2580 * list of grouping sets, we need to remap the entries in the grouping
2581 * sets from sortgrouprefs to plain indices (0-based) into the
2582 * groupClause for this collection of grouping sets. We keep the
2583 * original form for later use, though.
2584 */
2585 rollup->gsets = remap_to_groupclause_idx(rollup->groupClause,
2586 current_sets,
2587 gd->tleref_to_colnum_map);
2588 rollup->gsets_data = current_sets;
2589
2590 gd->rollups = lappend(gd->rollups, rollup);
2591 }
2592
2593 if (gd->unsortable_sets)
2594 {
2595 /*
2596 * We have not yet pinned down a groupclause for this, but we will
2597 * need index-based lists for estimation purposes. Construct
2598 * hash_sets_idx based on the entire original groupclause for now.
2599 */
2600 gd->hash_sets_idx = remap_to_groupclause_idx(parse->groupClause,
2601 gd->unsortable_sets,
2602 gd->tleref_to_colnum_map);
2603 gd->any_hashable = true;
2604 }
2605
2606 return gd;
2607 }
2608
2609 /*
2610 * Given a groupclause and a list of GroupingSetData, return equivalent sets
2611 * (without annotation) mapped to indexes into the given groupclause.
2612 */
2613 static List *
remap_to_groupclause_idx(List * groupClause,List * gsets,int * tleref_to_colnum_map)2614 remap_to_groupclause_idx(List *groupClause,
2615 List *gsets,
2616 int *tleref_to_colnum_map)
2617 {
2618 int ref = 0;
2619 List *result = NIL;
2620 ListCell *lc;
2621
2622 foreach(lc, groupClause)
2623 {
2624 SortGroupClause *gc = lfirst_node(SortGroupClause, lc);
2625
2626 tleref_to_colnum_map[gc->tleSortGroupRef] = ref++;
2627 }
2628
2629 foreach(lc, gsets)
2630 {
2631 List *set = NIL;
2632 ListCell *lc2;
2633 GroupingSetData *gs = lfirst_node(GroupingSetData, lc);
2634
2635 foreach(lc2, gs->set)
2636 {
2637 set = lappend_int(set, tleref_to_colnum_map[lfirst_int(lc2)]);
2638 }
2639
2640 result = lappend(result, set);
2641 }
2642
2643 return result;
2644 }
2645
2646
2647 /*
2648 * preprocess_rowmarks - set up PlanRowMarks if needed
2649 */
2650 static void
preprocess_rowmarks(PlannerInfo * root)2651 preprocess_rowmarks(PlannerInfo *root)
2652 {
2653 Query *parse = root->parse;
2654 Bitmapset *rels;
2655 List *prowmarks;
2656 ListCell *l;
2657 int i;
2658
2659 if (parse->rowMarks)
2660 {
2661 /*
2662 * We've got trouble if FOR [KEY] UPDATE/SHARE appears inside
2663 * grouping, since grouping renders a reference to individual tuple
2664 * CTIDs invalid. This is also checked at parse time, but that's
2665 * insufficient because of rule substitution, query pullup, etc.
2666 */
2667 CheckSelectLocking(parse, linitial_node(RowMarkClause,
2668 parse->rowMarks)->strength);
2669 }
2670 else
2671 {
2672 /*
2673 * We only need rowmarks for UPDATE, DELETE, or FOR [KEY]
2674 * UPDATE/SHARE.
2675 */
2676 if (parse->commandType != CMD_UPDATE &&
2677 parse->commandType != CMD_DELETE)
2678 return;
2679 }
2680
2681 /*
2682 * We need to have rowmarks for all base relations except the target. We
2683 * make a bitmapset of all base rels and then remove the items we don't
2684 * need or have FOR [KEY] UPDATE/SHARE marks for.
2685 */
2686 rels = get_relids_in_jointree((Node *) parse->jointree, false);
2687 if (parse->resultRelation)
2688 rels = bms_del_member(rels, parse->resultRelation);
2689
2690 /*
2691 * Convert RowMarkClauses to PlanRowMark representation.
2692 */
2693 prowmarks = NIL;
2694 foreach(l, parse->rowMarks)
2695 {
2696 RowMarkClause *rc = lfirst_node(RowMarkClause, l);
2697 RangeTblEntry *rte = rt_fetch(rc->rti, parse->rtable);
2698 PlanRowMark *newrc;
2699
2700 /*
2701 * Currently, it is syntactically impossible to have FOR UPDATE et al
2702 * applied to an update/delete target rel. If that ever becomes
2703 * possible, we should drop the target from the PlanRowMark list.
2704 */
2705 Assert(rc->rti != parse->resultRelation);
2706
2707 /*
2708 * Ignore RowMarkClauses for subqueries; they aren't real tables and
2709 * can't support true locking. Subqueries that got flattened into the
2710 * main query should be ignored completely. Any that didn't will get
2711 * ROW_MARK_COPY items in the next loop.
2712 */
2713 if (rte->rtekind != RTE_RELATION)
2714 continue;
2715
2716 rels = bms_del_member(rels, rc->rti);
2717
2718 newrc = makeNode(PlanRowMark);
2719 newrc->rti = newrc->prti = rc->rti;
2720 newrc->rowmarkId = ++(root->glob->lastRowMarkId);
2721 newrc->markType = select_rowmark_type(rte, rc->strength);
2722 newrc->allMarkTypes = (1 << newrc->markType);
2723 newrc->strength = rc->strength;
2724 newrc->waitPolicy = rc->waitPolicy;
2725 newrc->isParent = false;
2726
2727 prowmarks = lappend(prowmarks, newrc);
2728 }
2729
2730 /*
2731 * Now, add rowmarks for any non-target, non-locked base relations.
2732 */
2733 i = 0;
2734 foreach(l, parse->rtable)
2735 {
2736 RangeTblEntry *rte = lfirst_node(RangeTblEntry, l);
2737 PlanRowMark *newrc;
2738
2739 i++;
2740 if (!bms_is_member(i, rels))
2741 continue;
2742
2743 newrc = makeNode(PlanRowMark);
2744 newrc->rti = newrc->prti = i;
2745 newrc->rowmarkId = ++(root->glob->lastRowMarkId);
2746 newrc->markType = select_rowmark_type(rte, LCS_NONE);
2747 newrc->allMarkTypes = (1 << newrc->markType);
2748 newrc->strength = LCS_NONE;
2749 newrc->waitPolicy = LockWaitBlock; /* doesn't matter */
2750 newrc->isParent = false;
2751
2752 prowmarks = lappend(prowmarks, newrc);
2753 }
2754
2755 root->rowMarks = prowmarks;
2756 }
2757
2758 /*
2759 * Select RowMarkType to use for a given table
2760 */
2761 RowMarkType
select_rowmark_type(RangeTblEntry * rte,LockClauseStrength strength)2762 select_rowmark_type(RangeTblEntry *rte, LockClauseStrength strength)
2763 {
2764 if (rte->rtekind != RTE_RELATION)
2765 {
2766 /* If it's not a table at all, use ROW_MARK_COPY */
2767 return ROW_MARK_COPY;
2768 }
2769 else if (rte->relkind == RELKIND_FOREIGN_TABLE)
2770 {
2771 /* Let the FDW select the rowmark type, if it wants to */
2772 FdwRoutine *fdwroutine = GetFdwRoutineByRelId(rte->relid);
2773
2774 if (fdwroutine->GetForeignRowMarkType != NULL)
2775 return fdwroutine->GetForeignRowMarkType(rte, strength);
2776 /* Otherwise, use ROW_MARK_COPY by default */
2777 return ROW_MARK_COPY;
2778 }
2779 else
2780 {
2781 /* Regular table, apply the appropriate lock type */
2782 switch (strength)
2783 {
2784 case LCS_NONE:
2785
2786 /*
2787 * We don't need a tuple lock, only the ability to re-fetch
2788 * the row.
2789 */
2790 return ROW_MARK_REFERENCE;
2791 break;
2792 case LCS_FORKEYSHARE:
2793 return ROW_MARK_KEYSHARE;
2794 break;
2795 case LCS_FORSHARE:
2796 return ROW_MARK_SHARE;
2797 break;
2798 case LCS_FORNOKEYUPDATE:
2799 return ROW_MARK_NOKEYEXCLUSIVE;
2800 break;
2801 case LCS_FORUPDATE:
2802 return ROW_MARK_EXCLUSIVE;
2803 break;
2804 }
2805 elog(ERROR, "unrecognized LockClauseStrength %d", (int) strength);
2806 return ROW_MARK_EXCLUSIVE; /* keep compiler quiet */
2807 }
2808 }
2809
2810 /*
2811 * preprocess_limit - do pre-estimation for LIMIT and/or OFFSET clauses
2812 *
2813 * We try to estimate the values of the LIMIT/OFFSET clauses, and pass the
2814 * results back in *count_est and *offset_est. These variables are set to
2815 * 0 if the corresponding clause is not present, and -1 if it's present
2816 * but we couldn't estimate the value for it. (The "0" convention is OK
2817 * for OFFSET but a little bit bogus for LIMIT: effectively we estimate
2818 * LIMIT 0 as though it were LIMIT 1. But this is in line with the planner's
2819 * usual practice of never estimating less than one row.) These values will
2820 * be passed to create_limit_path, which see if you change this code.
2821 *
2822 * The return value is the suitably adjusted tuple_fraction to use for
2823 * planning the query. This adjustment is not overridable, since it reflects
2824 * plan actions that grouping_planner() will certainly take, not assumptions
2825 * about context.
2826 */
2827 static double
preprocess_limit(PlannerInfo * root,double tuple_fraction,int64 * offset_est,int64 * count_est)2828 preprocess_limit(PlannerInfo *root, double tuple_fraction,
2829 int64 *offset_est, int64 *count_est)
2830 {
2831 Query *parse = root->parse;
2832 Node *est;
2833 double limit_fraction;
2834
2835 /* Should not be called unless LIMIT or OFFSET */
2836 Assert(parse->limitCount || parse->limitOffset);
2837
2838 /*
2839 * Try to obtain the clause values. We use estimate_expression_value
2840 * primarily because it can sometimes do something useful with Params.
2841 */
2842 if (parse->limitCount)
2843 {
2844 est = estimate_expression_value(root, parse->limitCount);
2845 if (est && IsA(est, Const))
2846 {
2847 if (((Const *) est)->constisnull)
2848 {
2849 /* NULL indicates LIMIT ALL, ie, no limit */
2850 *count_est = 0; /* treat as not present */
2851 }
2852 else
2853 {
2854 *count_est = DatumGetInt64(((Const *) est)->constvalue);
2855 if (*count_est <= 0)
2856 *count_est = 1; /* force to at least 1 */
2857 }
2858 }
2859 else
2860 *count_est = -1; /* can't estimate */
2861 }
2862 else
2863 *count_est = 0; /* not present */
2864
2865 if (parse->limitOffset)
2866 {
2867 est = estimate_expression_value(root, parse->limitOffset);
2868 if (est && IsA(est, Const))
2869 {
2870 if (((Const *) est)->constisnull)
2871 {
2872 /* Treat NULL as no offset; the executor will too */
2873 *offset_est = 0; /* treat as not present */
2874 }
2875 else
2876 {
2877 *offset_est = DatumGetInt64(((Const *) est)->constvalue);
2878 if (*offset_est < 0)
2879 *offset_est = 0; /* treat as not present */
2880 }
2881 }
2882 else
2883 *offset_est = -1; /* can't estimate */
2884 }
2885 else
2886 *offset_est = 0; /* not present */
2887
2888 if (*count_est != 0)
2889 {
2890 /*
2891 * A LIMIT clause limits the absolute number of tuples returned.
2892 * However, if it's not a constant LIMIT then we have to guess; for
2893 * lack of a better idea, assume 10% of the plan's result is wanted.
2894 */
2895 if (*count_est < 0 || *offset_est < 0)
2896 {
2897 /* LIMIT or OFFSET is an expression ... punt ... */
2898 limit_fraction = 0.10;
2899 }
2900 else
2901 {
2902 /* LIMIT (plus OFFSET, if any) is max number of tuples needed */
2903 limit_fraction = (double) *count_est + (double) *offset_est;
2904 }
2905
2906 /*
2907 * If we have absolute limits from both caller and LIMIT, use the
2908 * smaller value; likewise if they are both fractional. If one is
2909 * fractional and the other absolute, we can't easily determine which
2910 * is smaller, but we use the heuristic that the absolute will usually
2911 * be smaller.
2912 */
2913 if (tuple_fraction >= 1.0)
2914 {
2915 if (limit_fraction >= 1.0)
2916 {
2917 /* both absolute */
2918 tuple_fraction = Min(tuple_fraction, limit_fraction);
2919 }
2920 else
2921 {
2922 /* caller absolute, limit fractional; use caller's value */
2923 }
2924 }
2925 else if (tuple_fraction > 0.0)
2926 {
2927 if (limit_fraction >= 1.0)
2928 {
2929 /* caller fractional, limit absolute; use limit */
2930 tuple_fraction = limit_fraction;
2931 }
2932 else
2933 {
2934 /* both fractional */
2935 tuple_fraction = Min(tuple_fraction, limit_fraction);
2936 }
2937 }
2938 else
2939 {
2940 /* no info from caller, just use limit */
2941 tuple_fraction = limit_fraction;
2942 }
2943 }
2944 else if (*offset_est != 0 && tuple_fraction > 0.0)
2945 {
2946 /*
2947 * We have an OFFSET but no LIMIT. This acts entirely differently
2948 * from the LIMIT case: here, we need to increase rather than decrease
2949 * the caller's tuple_fraction, because the OFFSET acts to cause more
2950 * tuples to be fetched instead of fewer. This only matters if we got
2951 * a tuple_fraction > 0, however.
2952 *
2953 * As above, use 10% if OFFSET is present but unestimatable.
2954 */
2955 if (*offset_est < 0)
2956 limit_fraction = 0.10;
2957 else
2958 limit_fraction = (double) *offset_est;
2959
2960 /*
2961 * If we have absolute counts from both caller and OFFSET, add them
2962 * together; likewise if they are both fractional. If one is
2963 * fractional and the other absolute, we want to take the larger, and
2964 * we heuristically assume that's the fractional one.
2965 */
2966 if (tuple_fraction >= 1.0)
2967 {
2968 if (limit_fraction >= 1.0)
2969 {
2970 /* both absolute, so add them together */
2971 tuple_fraction += limit_fraction;
2972 }
2973 else
2974 {
2975 /* caller absolute, limit fractional; use limit */
2976 tuple_fraction = limit_fraction;
2977 }
2978 }
2979 else
2980 {
2981 if (limit_fraction >= 1.0)
2982 {
2983 /* caller fractional, limit absolute; use caller's value */
2984 }
2985 else
2986 {
2987 /* both fractional, so add them together */
2988 tuple_fraction += limit_fraction;
2989 if (tuple_fraction >= 1.0)
2990 tuple_fraction = 0.0; /* assume fetch all */
2991 }
2992 }
2993 }
2994
2995 return tuple_fraction;
2996 }
2997
2998 /*
2999 * limit_needed - do we actually need a Limit plan node?
3000 *
3001 * If we have constant-zero OFFSET and constant-null LIMIT, we can skip adding
3002 * a Limit node. This is worth checking for because "OFFSET 0" is a common
3003 * locution for an optimization fence. (Because other places in the planner
3004 * merely check whether parse->limitOffset isn't NULL, it will still work as
3005 * an optimization fence --- we're just suppressing unnecessary run-time
3006 * overhead.)
3007 *
3008 * This might look like it could be merged into preprocess_limit, but there's
3009 * a key distinction: here we need hard constants in OFFSET/LIMIT, whereas
3010 * in preprocess_limit it's good enough to consider estimated values.
3011 */
3012 bool
limit_needed(Query * parse)3013 limit_needed(Query *parse)
3014 {
3015 Node *node;
3016
3017 node = parse->limitCount;
3018 if (node)
3019 {
3020 if (IsA(node, Const))
3021 {
3022 /* NULL indicates LIMIT ALL, ie, no limit */
3023 if (!((Const *) node)->constisnull)
3024 return true; /* LIMIT with a constant value */
3025 }
3026 else
3027 return true; /* non-constant LIMIT */
3028 }
3029
3030 node = parse->limitOffset;
3031 if (node)
3032 {
3033 if (IsA(node, Const))
3034 {
3035 /* Treat NULL as no offset; the executor would too */
3036 if (!((Const *) node)->constisnull)
3037 {
3038 int64 offset = DatumGetInt64(((Const *) node)->constvalue);
3039
3040 if (offset != 0)
3041 return true; /* OFFSET with a nonzero value */
3042 }
3043 }
3044 else
3045 return true; /* non-constant OFFSET */
3046 }
3047
3048 return false; /* don't need a Limit plan node */
3049 }
3050
3051
3052 /*
3053 * remove_useless_groupby_columns
3054 * Remove any columns in the GROUP BY clause that are redundant due to
3055 * being functionally dependent on other GROUP BY columns.
3056 *
3057 * Since some other DBMSes do not allow references to ungrouped columns, it's
3058 * not unusual to find all columns listed in GROUP BY even though listing the
3059 * primary-key columns would be sufficient. Deleting such excess columns
3060 * avoids redundant sorting work, so it's worth doing.
3061 *
3062 * Relcache invalidations will ensure that cached plans become invalidated
3063 * when the underlying index of the pkey constraint is dropped.
3064 *
3065 * Currently, we only make use of pkey constraints for this, however, we may
3066 * wish to take this further in the future and also use unique constraints
3067 * which have NOT NULL columns. In that case, plan invalidation will still
3068 * work since relations will receive a relcache invalidation when a NOT NULL
3069 * constraint is dropped.
3070 */
3071 static void
remove_useless_groupby_columns(PlannerInfo * root)3072 remove_useless_groupby_columns(PlannerInfo *root)
3073 {
3074 Query *parse = root->parse;
3075 Bitmapset **groupbyattnos;
3076 Bitmapset **surplusvars;
3077 ListCell *lc;
3078 int relid;
3079
3080 /* No chance to do anything if there are less than two GROUP BY items */
3081 if (list_length(parse->groupClause) < 2)
3082 return;
3083
3084 /* Don't fiddle with the GROUP BY clause if the query has grouping sets */
3085 if (parse->groupingSets)
3086 return;
3087
3088 /*
3089 * Scan the GROUP BY clause to find GROUP BY items that are simple Vars.
3090 * Fill groupbyattnos[k] with a bitmapset of the column attnos of RTE k
3091 * that are GROUP BY items.
3092 */
3093 groupbyattnos = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
3094 (list_length(parse->rtable) + 1));
3095 foreach(lc, parse->groupClause)
3096 {
3097 SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
3098 TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
3099 Var *var = (Var *) tle->expr;
3100
3101 /*
3102 * Ignore non-Vars and Vars from other query levels.
3103 *
3104 * XXX in principle, stable expressions containing Vars could also be
3105 * removed, if all the Vars are functionally dependent on other GROUP
3106 * BY items. But it's not clear that such cases occur often enough to
3107 * be worth troubling over.
3108 */
3109 if (!IsA(var, Var) ||
3110 var->varlevelsup > 0)
3111 continue;
3112
3113 /* OK, remember we have this Var */
3114 relid = var->varno;
3115 Assert(relid <= list_length(parse->rtable));
3116 groupbyattnos[relid] = bms_add_member(groupbyattnos[relid],
3117 var->varattno - FirstLowInvalidHeapAttributeNumber);
3118 }
3119
3120 /*
3121 * Consider each relation and see if it is possible to remove some of its
3122 * Vars from GROUP BY. For simplicity and speed, we do the actual removal
3123 * in a separate pass. Here, we just fill surplusvars[k] with a bitmapset
3124 * of the column attnos of RTE k that are removable GROUP BY items.
3125 */
3126 surplusvars = NULL; /* don't allocate array unless required */
3127 relid = 0;
3128 foreach(lc, parse->rtable)
3129 {
3130 RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
3131 Bitmapset *relattnos;
3132 Bitmapset *pkattnos;
3133 Oid constraintOid;
3134
3135 relid++;
3136
3137 /* Only plain relations could have primary-key constraints */
3138 if (rte->rtekind != RTE_RELATION)
3139 continue;
3140
3141 /*
3142 * We must skip inheritance parent tables as some of the child rels
3143 * may cause duplicate rows. This cannot happen with partitioned
3144 * tables, however.
3145 */
3146 if (rte->inh && rte->relkind != RELKIND_PARTITIONED_TABLE)
3147 continue;
3148
3149 /* Nothing to do unless this rel has multiple Vars in GROUP BY */
3150 relattnos = groupbyattnos[relid];
3151 if (bms_membership(relattnos) != BMS_MULTIPLE)
3152 continue;
3153
3154 /*
3155 * Can't remove any columns for this rel if there is no suitable
3156 * (i.e., nondeferrable) primary key constraint.
3157 */
3158 pkattnos = get_primary_key_attnos(rte->relid, false, &constraintOid);
3159 if (pkattnos == NULL)
3160 continue;
3161
3162 /*
3163 * If the primary key is a proper subset of relattnos then we have
3164 * some items in the GROUP BY that can be removed.
3165 */
3166 if (bms_subset_compare(pkattnos, relattnos) == BMS_SUBSET1)
3167 {
3168 /*
3169 * To easily remember whether we've found anything to do, we don't
3170 * allocate the surplusvars[] array until we find something.
3171 */
3172 if (surplusvars == NULL)
3173 surplusvars = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
3174 (list_length(parse->rtable) + 1));
3175
3176 /* Remember the attnos of the removable columns */
3177 surplusvars[relid] = bms_difference(relattnos, pkattnos);
3178 }
3179 }
3180
3181 /*
3182 * If we found any surplus Vars, build a new GROUP BY clause without them.
3183 * (Note: this may leave some TLEs with unreferenced ressortgroupref
3184 * markings, but that's harmless.)
3185 */
3186 if (surplusvars != NULL)
3187 {
3188 List *new_groupby = NIL;
3189
3190 foreach(lc, parse->groupClause)
3191 {
3192 SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
3193 TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
3194 Var *var = (Var *) tle->expr;
3195
3196 /*
3197 * New list must include non-Vars, outer Vars, and anything not
3198 * marked as surplus.
3199 */
3200 if (!IsA(var, Var) ||
3201 var->varlevelsup > 0 ||
3202 !bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
3203 surplusvars[var->varno]))
3204 new_groupby = lappend(new_groupby, sgc);
3205 }
3206
3207 parse->groupClause = new_groupby;
3208 }
3209 }
3210
3211 /*
3212 * preprocess_groupclause - do preparatory work on GROUP BY clause
3213 *
3214 * The idea here is to adjust the ordering of the GROUP BY elements
3215 * (which in itself is semantically insignificant) to match ORDER BY,
3216 * thereby allowing a single sort operation to both implement the ORDER BY
3217 * requirement and set up for a Unique step that implements GROUP BY.
3218 *
3219 * In principle it might be interesting to consider other orderings of the
3220 * GROUP BY elements, which could match the sort ordering of other
3221 * possible plans (eg an indexscan) and thereby reduce cost. We don't
3222 * bother with that, though. Hashed grouping will frequently win anyway.
3223 *
3224 * Note: we need no comparable processing of the distinctClause because
3225 * the parser already enforced that that matches ORDER BY.
3226 *
3227 * For grouping sets, the order of items is instead forced to agree with that
3228 * of the grouping set (and items not in the grouping set are skipped). The
3229 * work of sorting the order of grouping set elements to match the ORDER BY if
3230 * possible is done elsewhere.
3231 */
3232 static List *
preprocess_groupclause(PlannerInfo * root,List * force)3233 preprocess_groupclause(PlannerInfo *root, List *force)
3234 {
3235 Query *parse = root->parse;
3236 List *new_groupclause = NIL;
3237 bool partial_match;
3238 ListCell *sl;
3239 ListCell *gl;
3240
3241 /* For grouping sets, we need to force the ordering */
3242 if (force)
3243 {
3244 foreach(sl, force)
3245 {
3246 Index ref = lfirst_int(sl);
3247 SortGroupClause *cl = get_sortgroupref_clause(ref, parse->groupClause);
3248
3249 new_groupclause = lappend(new_groupclause, cl);
3250 }
3251
3252 return new_groupclause;
3253 }
3254
3255 /* If no ORDER BY, nothing useful to do here */
3256 if (parse->sortClause == NIL)
3257 return parse->groupClause;
3258
3259 /*
3260 * Scan the ORDER BY clause and construct a list of matching GROUP BY
3261 * items, but only as far as we can make a matching prefix.
3262 *
3263 * This code assumes that the sortClause contains no duplicate items.
3264 */
3265 foreach(sl, parse->sortClause)
3266 {
3267 SortGroupClause *sc = lfirst_node(SortGroupClause, sl);
3268
3269 foreach(gl, parse->groupClause)
3270 {
3271 SortGroupClause *gc = lfirst_node(SortGroupClause, gl);
3272
3273 if (equal(gc, sc))
3274 {
3275 new_groupclause = lappend(new_groupclause, gc);
3276 break;
3277 }
3278 }
3279 if (gl == NULL)
3280 break; /* no match, so stop scanning */
3281 }
3282
3283 /* Did we match all of the ORDER BY list, or just some of it? */
3284 partial_match = (sl != NULL);
3285
3286 /* If no match at all, no point in reordering GROUP BY */
3287 if (new_groupclause == NIL)
3288 return parse->groupClause;
3289
3290 /*
3291 * Add any remaining GROUP BY items to the new list, but only if we were
3292 * able to make a complete match. In other words, we only rearrange the
3293 * GROUP BY list if the result is that one list is a prefix of the other
3294 * --- otherwise there's no possibility of a common sort. Also, give up
3295 * if there are any non-sortable GROUP BY items, since then there's no
3296 * hope anyway.
3297 */
3298 foreach(gl, parse->groupClause)
3299 {
3300 SortGroupClause *gc = lfirst_node(SortGroupClause, gl);
3301
3302 if (list_member_ptr(new_groupclause, gc))
3303 continue; /* it matched an ORDER BY item */
3304 if (partial_match)
3305 return parse->groupClause; /* give up, no common sort possible */
3306 if (!OidIsValid(gc->sortop))
3307 return parse->groupClause; /* give up, GROUP BY can't be sorted */
3308 new_groupclause = lappend(new_groupclause, gc);
3309 }
3310
3311 /* Success --- install the rearranged GROUP BY list */
3312 Assert(list_length(parse->groupClause) == list_length(new_groupclause));
3313 return new_groupclause;
3314 }
3315
3316 /*
3317 * Extract lists of grouping sets that can be implemented using a single
3318 * rollup-type aggregate pass each. Returns a list of lists of grouping sets.
3319 *
3320 * Input must be sorted with smallest sets first. Result has each sublist
3321 * sorted with smallest sets first.
3322 *
3323 * We want to produce the absolute minimum possible number of lists here to
3324 * avoid excess sorts. Fortunately, there is an algorithm for this; the problem
3325 * of finding the minimal partition of a partially-ordered set into chains
3326 * (which is what we need, taking the list of grouping sets as a poset ordered
3327 * by set inclusion) can be mapped to the problem of finding the maximum
3328 * cardinality matching on a bipartite graph, which is solvable in polynomial
3329 * time with a worst case of no worse than O(n^2.5) and usually much
3330 * better. Since our N is at most 4096, we don't need to consider fallbacks to
3331 * heuristic or approximate methods. (Planning time for a 12-d cube is under
3332 * half a second on my modest system even with optimization off and assertions
3333 * on.)
3334 */
3335 static List *
extract_rollup_sets(List * groupingSets)3336 extract_rollup_sets(List *groupingSets)
3337 {
3338 int num_sets_raw = list_length(groupingSets);
3339 int num_empty = 0;
3340 int num_sets = 0; /* distinct sets */
3341 int num_chains = 0;
3342 List *result = NIL;
3343 List **results;
3344 List **orig_sets;
3345 Bitmapset **set_masks;
3346 int *chains;
3347 short **adjacency;
3348 short *adjacency_buf;
3349 BipartiteMatchState *state;
3350 int i;
3351 int j;
3352 int j_size;
3353 ListCell *lc1 = list_head(groupingSets);
3354 ListCell *lc;
3355
3356 /*
3357 * Start by stripping out empty sets. The algorithm doesn't require this,
3358 * but the planner currently needs all empty sets to be returned in the
3359 * first list, so we strip them here and add them back after.
3360 */
3361 while (lc1 && lfirst(lc1) == NIL)
3362 {
3363 ++num_empty;
3364 lc1 = lnext(groupingSets, lc1);
3365 }
3366
3367 /* bail out now if it turns out that all we had were empty sets. */
3368 if (!lc1)
3369 return list_make1(groupingSets);
3370
3371 /*----------
3372 * We don't strictly need to remove duplicate sets here, but if we don't,
3373 * they tend to become scattered through the result, which is a bit
3374 * confusing (and irritating if we ever decide to optimize them out).
3375 * So we remove them here and add them back after.
3376 *
3377 * For each non-duplicate set, we fill in the following:
3378 *
3379 * orig_sets[i] = list of the original set lists
3380 * set_masks[i] = bitmapset for testing inclusion
3381 * adjacency[i] = array [n, v1, v2, ... vn] of adjacency indices
3382 *
3383 * chains[i] will be the result group this set is assigned to.
3384 *
3385 * We index all of these from 1 rather than 0 because it is convenient
3386 * to leave 0 free for the NIL node in the graph algorithm.
3387 *----------
3388 */
3389 orig_sets = palloc0((num_sets_raw + 1) * sizeof(List *));
3390 set_masks = palloc0((num_sets_raw + 1) * sizeof(Bitmapset *));
3391 adjacency = palloc0((num_sets_raw + 1) * sizeof(short *));
3392 adjacency_buf = palloc((num_sets_raw + 1) * sizeof(short));
3393
3394 j_size = 0;
3395 j = 0;
3396 i = 1;
3397
3398 for_each_cell(lc, groupingSets, lc1)
3399 {
3400 List *candidate = (List *) lfirst(lc);
3401 Bitmapset *candidate_set = NULL;
3402 ListCell *lc2;
3403 int dup_of = 0;
3404
3405 foreach(lc2, candidate)
3406 {
3407 candidate_set = bms_add_member(candidate_set, lfirst_int(lc2));
3408 }
3409
3410 /* we can only be a dup if we're the same length as a previous set */
3411 if (j_size == list_length(candidate))
3412 {
3413 int k;
3414
3415 for (k = j; k < i; ++k)
3416 {
3417 if (bms_equal(set_masks[k], candidate_set))
3418 {
3419 dup_of = k;
3420 break;
3421 }
3422 }
3423 }
3424 else if (j_size < list_length(candidate))
3425 {
3426 j_size = list_length(candidate);
3427 j = i;
3428 }
3429
3430 if (dup_of > 0)
3431 {
3432 orig_sets[dup_of] = lappend(orig_sets[dup_of], candidate);
3433 bms_free(candidate_set);
3434 }
3435 else
3436 {
3437 int k;
3438 int n_adj = 0;
3439
3440 orig_sets[i] = list_make1(candidate);
3441 set_masks[i] = candidate_set;
3442
3443 /* fill in adjacency list; no need to compare equal-size sets */
3444
3445 for (k = j - 1; k > 0; --k)
3446 {
3447 if (bms_is_subset(set_masks[k], candidate_set))
3448 adjacency_buf[++n_adj] = k;
3449 }
3450
3451 if (n_adj > 0)
3452 {
3453 adjacency_buf[0] = n_adj;
3454 adjacency[i] = palloc((n_adj + 1) * sizeof(short));
3455 memcpy(adjacency[i], adjacency_buf, (n_adj + 1) * sizeof(short));
3456 }
3457 else
3458 adjacency[i] = NULL;
3459
3460 ++i;
3461 }
3462 }
3463
3464 num_sets = i - 1;
3465
3466 /*
3467 * Apply the graph matching algorithm to do the work.
3468 */
3469 state = BipartiteMatch(num_sets, num_sets, adjacency);
3470
3471 /*
3472 * Now, the state->pair* fields have the info we need to assign sets to
3473 * chains. Two sets (u,v) belong to the same chain if pair_uv[u] = v or
3474 * pair_vu[v] = u (both will be true, but we check both so that we can do
3475 * it in one pass)
3476 */
3477 chains = palloc0((num_sets + 1) * sizeof(int));
3478
3479 for (i = 1; i <= num_sets; ++i)
3480 {
3481 int u = state->pair_vu[i];
3482 int v = state->pair_uv[i];
3483
3484 if (u > 0 && u < i)
3485 chains[i] = chains[u];
3486 else if (v > 0 && v < i)
3487 chains[i] = chains[v];
3488 else
3489 chains[i] = ++num_chains;
3490 }
3491
3492 /* build result lists. */
3493 results = palloc0((num_chains + 1) * sizeof(List *));
3494
3495 for (i = 1; i <= num_sets; ++i)
3496 {
3497 int c = chains[i];
3498
3499 Assert(c > 0);
3500
3501 results[c] = list_concat(results[c], orig_sets[i]);
3502 }
3503
3504 /* push any empty sets back on the first list. */
3505 while (num_empty-- > 0)
3506 results[1] = lcons(NIL, results[1]);
3507
3508 /* make result list */
3509 for (i = 1; i <= num_chains; ++i)
3510 result = lappend(result, results[i]);
3511
3512 /*
3513 * Free all the things.
3514 *
3515 * (This is over-fussy for small sets but for large sets we could have
3516 * tied up a nontrivial amount of memory.)
3517 */
3518 BipartiteMatchFree(state);
3519 pfree(results);
3520 pfree(chains);
3521 for (i = 1; i <= num_sets; ++i)
3522 if (adjacency[i])
3523 pfree(adjacency[i]);
3524 pfree(adjacency);
3525 pfree(adjacency_buf);
3526 pfree(orig_sets);
3527 for (i = 1; i <= num_sets; ++i)
3528 bms_free(set_masks[i]);
3529 pfree(set_masks);
3530
3531 return result;
3532 }
3533
3534 /*
3535 * Reorder the elements of a list of grouping sets such that they have correct
3536 * prefix relationships. Also inserts the GroupingSetData annotations.
3537 *
3538 * The input must be ordered with smallest sets first; the result is returned
3539 * with largest sets first. Note that the result shares no list substructure
3540 * with the input, so it's safe for the caller to modify it later.
3541 *
3542 * If we're passed in a sortclause, we follow its order of columns to the
3543 * extent possible, to minimize the chance that we add unnecessary sorts.
3544 * (We're trying here to ensure that GROUPING SETS ((a,b,c),(c)) ORDER BY c,b,a
3545 * gets implemented in one pass.)
3546 */
3547 static List *
reorder_grouping_sets(List * groupingsets,List * sortclause)3548 reorder_grouping_sets(List *groupingsets, List *sortclause)
3549 {
3550 ListCell *lc;
3551 List *previous = NIL;
3552 List *result = NIL;
3553
3554 foreach(lc, groupingsets)
3555 {
3556 List *candidate = (List *) lfirst(lc);
3557 List *new_elems = list_difference_int(candidate, previous);
3558 GroupingSetData *gs = makeNode(GroupingSetData);
3559
3560 while (list_length(sortclause) > list_length(previous) &&
3561 list_length(new_elems) > 0)
3562 {
3563 SortGroupClause *sc = list_nth(sortclause, list_length(previous));
3564 int ref = sc->tleSortGroupRef;
3565
3566 if (list_member_int(new_elems, ref))
3567 {
3568 previous = lappend_int(previous, ref);
3569 new_elems = list_delete_int(new_elems, ref);
3570 }
3571 else
3572 {
3573 /* diverged from the sortclause; give up on it */
3574 sortclause = NIL;
3575 break;
3576 }
3577 }
3578
3579 previous = list_concat(previous, new_elems);
3580
3581 gs->set = list_copy(previous);
3582 result = lcons(gs, result);
3583 }
3584
3585 list_free(previous);
3586
3587 return result;
3588 }
3589
3590 /*
3591 * Compute query_pathkeys and other pathkeys during plan generation
3592 */
3593 static void
standard_qp_callback(PlannerInfo * root,void * extra)3594 standard_qp_callback(PlannerInfo *root, void *extra)
3595 {
3596 Query *parse = root->parse;
3597 standard_qp_extra *qp_extra = (standard_qp_extra *) extra;
3598 List *tlist = root->processed_tlist;
3599 List *activeWindows = qp_extra->activeWindows;
3600
3601 /*
3602 * Calculate pathkeys that represent grouping/ordering requirements. The
3603 * sortClause is certainly sort-able, but GROUP BY and DISTINCT might not
3604 * be, in which case we just leave their pathkeys empty.
3605 */
3606 if (qp_extra->groupClause &&
3607 grouping_is_sortable(qp_extra->groupClause))
3608 root->group_pathkeys =
3609 make_pathkeys_for_sortclauses(root,
3610 qp_extra->groupClause,
3611 tlist);
3612 else
3613 root->group_pathkeys = NIL;
3614
3615 /* We consider only the first (bottom) window in pathkeys logic */
3616 if (activeWindows != NIL)
3617 {
3618 WindowClause *wc = linitial_node(WindowClause, activeWindows);
3619
3620 root->window_pathkeys = make_pathkeys_for_window(root,
3621 wc,
3622 tlist);
3623 }
3624 else
3625 root->window_pathkeys = NIL;
3626
3627 if (parse->distinctClause &&
3628 grouping_is_sortable(parse->distinctClause))
3629 root->distinct_pathkeys =
3630 make_pathkeys_for_sortclauses(root,
3631 parse->distinctClause,
3632 tlist);
3633 else
3634 root->distinct_pathkeys = NIL;
3635
3636 root->sort_pathkeys =
3637 make_pathkeys_for_sortclauses(root,
3638 parse->sortClause,
3639 tlist);
3640
3641 /*
3642 * Figure out whether we want a sorted result from query_planner.
3643 *
3644 * If we have a sortable GROUP BY clause, then we want a result sorted
3645 * properly for grouping. Otherwise, if we have window functions to
3646 * evaluate, we try to sort for the first window. Otherwise, if there's a
3647 * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
3648 * we try to produce output that's sufficiently well sorted for the
3649 * DISTINCT. Otherwise, if there is an ORDER BY clause, we want to sort
3650 * by the ORDER BY clause.
3651 *
3652 * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
3653 * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
3654 * that might just leave us failing to exploit an available sort order at
3655 * all. Needs more thought. The choice for DISTINCT versus ORDER BY is
3656 * much easier, since we know that the parser ensured that one is a
3657 * superset of the other.
3658 */
3659 if (root->group_pathkeys)
3660 root->query_pathkeys = root->group_pathkeys;
3661 else if (root->window_pathkeys)
3662 root->query_pathkeys = root->window_pathkeys;
3663 else if (list_length(root->distinct_pathkeys) >
3664 list_length(root->sort_pathkeys))
3665 root->query_pathkeys = root->distinct_pathkeys;
3666 else if (root->sort_pathkeys)
3667 root->query_pathkeys = root->sort_pathkeys;
3668 else
3669 root->query_pathkeys = NIL;
3670 }
3671
3672 /*
3673 * Estimate number of groups produced by grouping clauses (1 if not grouping)
3674 *
3675 * path_rows: number of output rows from scan/join step
3676 * gd: grouping sets data including list of grouping sets and their clauses
3677 * target_list: target list containing group clause references
3678 *
3679 * If doing grouping sets, we also annotate the gsets data with the estimates
3680 * for each set and each individual rollup list, with a view to later
3681 * determining whether some combination of them could be hashed instead.
3682 */
3683 static double
get_number_of_groups(PlannerInfo * root,double path_rows,grouping_sets_data * gd,List * target_list)3684 get_number_of_groups(PlannerInfo *root,
3685 double path_rows,
3686 grouping_sets_data *gd,
3687 List *target_list)
3688 {
3689 Query *parse = root->parse;
3690 double dNumGroups;
3691
3692 if (parse->groupClause)
3693 {
3694 List *groupExprs;
3695
3696 if (parse->groupingSets)
3697 {
3698 /* Add up the estimates for each grouping set */
3699 ListCell *lc;
3700 ListCell *lc2;
3701
3702 Assert(gd); /* keep Coverity happy */
3703
3704 dNumGroups = 0;
3705
3706 foreach(lc, gd->rollups)
3707 {
3708 RollupData *rollup = lfirst_node(RollupData, lc);
3709 ListCell *lc;
3710
3711 groupExprs = get_sortgrouplist_exprs(rollup->groupClause,
3712 target_list);
3713
3714 rollup->numGroups = 0.0;
3715
3716 forboth(lc, rollup->gsets, lc2, rollup->gsets_data)
3717 {
3718 List *gset = (List *) lfirst(lc);
3719 GroupingSetData *gs = lfirst_node(GroupingSetData, lc2);
3720 double numGroups = estimate_num_groups(root,
3721 groupExprs,
3722 path_rows,
3723 &gset);
3724
3725 gs->numGroups = numGroups;
3726 rollup->numGroups += numGroups;
3727 }
3728
3729 dNumGroups += rollup->numGroups;
3730 }
3731
3732 if (gd->hash_sets_idx)
3733 {
3734 ListCell *lc;
3735
3736 gd->dNumHashGroups = 0;
3737
3738 groupExprs = get_sortgrouplist_exprs(parse->groupClause,
3739 target_list);
3740
3741 forboth(lc, gd->hash_sets_idx, lc2, gd->unsortable_sets)
3742 {
3743 List *gset = (List *) lfirst(lc);
3744 GroupingSetData *gs = lfirst_node(GroupingSetData, lc2);
3745 double numGroups = estimate_num_groups(root,
3746 groupExprs,
3747 path_rows,
3748 &gset);
3749
3750 gs->numGroups = numGroups;
3751 gd->dNumHashGroups += numGroups;
3752 }
3753
3754 dNumGroups += gd->dNumHashGroups;
3755 }
3756 }
3757 else
3758 {
3759 /* Plain GROUP BY */
3760 groupExprs = get_sortgrouplist_exprs(parse->groupClause,
3761 target_list);
3762
3763 dNumGroups = estimate_num_groups(root, groupExprs, path_rows,
3764 NULL);
3765 }
3766 }
3767 else if (parse->groupingSets)
3768 {
3769 /* Empty grouping sets ... one result row for each one */
3770 dNumGroups = list_length(parse->groupingSets);
3771 }
3772 else if (parse->hasAggs || root->hasHavingQual)
3773 {
3774 /* Plain aggregation, one result row */
3775 dNumGroups = 1;
3776 }
3777 else
3778 {
3779 /* Not grouping */
3780 dNumGroups = 1;
3781 }
3782
3783 return dNumGroups;
3784 }
3785
3786 /*
3787 * create_grouping_paths
3788 *
3789 * Build a new upperrel containing Paths for grouping and/or aggregation.
3790 * Along the way, we also build an upperrel for Paths which are partially
3791 * grouped and/or aggregated. A partially grouped and/or aggregated path
3792 * needs a FinalizeAggregate node to complete the aggregation. Currently,
3793 * the only partially grouped paths we build are also partial paths; that
3794 * is, they need a Gather and then a FinalizeAggregate.
3795 *
3796 * input_rel: contains the source-data Paths
3797 * target: the pathtarget for the result Paths to compute
3798 * agg_costs: cost info about all aggregates in query (in AGGSPLIT_SIMPLE mode)
3799 * gd: grouping sets data including list of grouping sets and their clauses
3800 *
3801 * Note: all Paths in input_rel are expected to return the target computed
3802 * by make_group_input_target.
3803 */
3804 static RelOptInfo *
create_grouping_paths(PlannerInfo * root,RelOptInfo * input_rel,PathTarget * target,bool target_parallel_safe,const AggClauseCosts * agg_costs,grouping_sets_data * gd)3805 create_grouping_paths(PlannerInfo *root,
3806 RelOptInfo *input_rel,
3807 PathTarget *target,
3808 bool target_parallel_safe,
3809 const AggClauseCosts *agg_costs,
3810 grouping_sets_data *gd)
3811 {
3812 Query *parse = root->parse;
3813 RelOptInfo *grouped_rel;
3814 RelOptInfo *partially_grouped_rel;
3815
3816 /*
3817 * Create grouping relation to hold fully aggregated grouping and/or
3818 * aggregation paths.
3819 */
3820 grouped_rel = make_grouping_rel(root, input_rel, target,
3821 target_parallel_safe, parse->havingQual);
3822
3823 /*
3824 * Create either paths for a degenerate grouping or paths for ordinary
3825 * grouping, as appropriate.
3826 */
3827 if (is_degenerate_grouping(root))
3828 create_degenerate_grouping_paths(root, input_rel, grouped_rel);
3829 else
3830 {
3831 int flags = 0;
3832 GroupPathExtraData extra;
3833
3834 /*
3835 * Determine whether it's possible to perform sort-based
3836 * implementations of grouping. (Note that if groupClause is empty,
3837 * grouping_is_sortable() is trivially true, and all the
3838 * pathkeys_contained_in() tests will succeed too, so that we'll
3839 * consider every surviving input path.)
3840 *
3841 * If we have grouping sets, we might be able to sort some but not all
3842 * of them; in this case, we need can_sort to be true as long as we
3843 * must consider any sorted-input plan.
3844 */
3845 if ((gd && gd->rollups != NIL)
3846 || grouping_is_sortable(parse->groupClause))
3847 flags |= GROUPING_CAN_USE_SORT;
3848
3849 /*
3850 * Determine whether we should consider hash-based implementations of
3851 * grouping.
3852 *
3853 * Hashed aggregation only applies if we're grouping. If we have
3854 * grouping sets, some groups might be hashable but others not; in
3855 * this case we set can_hash true as long as there is nothing globally
3856 * preventing us from hashing (and we should therefore consider plans
3857 * with hashes).
3858 *
3859 * Executor doesn't support hashed aggregation with DISTINCT or ORDER
3860 * BY aggregates. (Doing so would imply storing *all* the input
3861 * values in the hash table, and/or running many sorts in parallel,
3862 * either of which seems like a certain loser.) We similarly don't
3863 * support ordered-set aggregates in hashed aggregation, but that case
3864 * is also included in the numOrderedAggs count.
3865 *
3866 * Note: grouping_is_hashable() is much more expensive to check than
3867 * the other gating conditions, so we want to do it last.
3868 */
3869 if ((parse->groupClause != NIL &&
3870 agg_costs->numOrderedAggs == 0 &&
3871 (gd ? gd->any_hashable : grouping_is_hashable(parse->groupClause))))
3872 flags |= GROUPING_CAN_USE_HASH;
3873
3874 /*
3875 * Determine whether partial aggregation is possible.
3876 */
3877 if (can_partial_agg(root, agg_costs))
3878 flags |= GROUPING_CAN_PARTIAL_AGG;
3879
3880 extra.flags = flags;
3881 extra.target_parallel_safe = target_parallel_safe;
3882 extra.havingQual = parse->havingQual;
3883 extra.targetList = parse->targetList;
3884 extra.partial_costs_set = false;
3885
3886 /*
3887 * Determine whether partitionwise aggregation is in theory possible.
3888 * It can be disabled by the user, and for now, we don't try to
3889 * support grouping sets. create_ordinary_grouping_paths() will check
3890 * additional conditions, such as whether input_rel is partitioned.
3891 */
3892 if (enable_partitionwise_aggregate && !parse->groupingSets)
3893 extra.patype = PARTITIONWISE_AGGREGATE_FULL;
3894 else
3895 extra.patype = PARTITIONWISE_AGGREGATE_NONE;
3896
3897 create_ordinary_grouping_paths(root, input_rel, grouped_rel,
3898 agg_costs, gd, &extra,
3899 &partially_grouped_rel);
3900 }
3901
3902 set_cheapest(grouped_rel);
3903 return grouped_rel;
3904 }
3905
3906 /*
3907 * make_grouping_rel
3908 *
3909 * Create a new grouping rel and set basic properties.
3910 *
3911 * input_rel represents the underlying scan/join relation.
3912 * target is the output expected from the grouping relation.
3913 */
3914 static RelOptInfo *
make_grouping_rel(PlannerInfo * root,RelOptInfo * input_rel,PathTarget * target,bool target_parallel_safe,Node * havingQual)3915 make_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
3916 PathTarget *target, bool target_parallel_safe,
3917 Node *havingQual)
3918 {
3919 RelOptInfo *grouped_rel;
3920
3921 if (IS_OTHER_REL(input_rel))
3922 {
3923 grouped_rel = fetch_upper_rel(root, UPPERREL_GROUP_AGG,
3924 input_rel->relids);
3925 grouped_rel->reloptkind = RELOPT_OTHER_UPPER_REL;
3926 }
3927 else
3928 {
3929 /*
3930 * By tradition, the relids set for the main grouping relation is
3931 * NULL. (This could be changed, but might require adjustments
3932 * elsewhere.)
3933 */
3934 grouped_rel = fetch_upper_rel(root, UPPERREL_GROUP_AGG, NULL);
3935 }
3936
3937 /* Set target. */
3938 grouped_rel->reltarget = target;
3939
3940 /*
3941 * If the input relation is not parallel-safe, then the grouped relation
3942 * can't be parallel-safe, either. Otherwise, it's parallel-safe if the
3943 * target list and HAVING quals are parallel-safe.
3944 */
3945 if (input_rel->consider_parallel && target_parallel_safe &&
3946 is_parallel_safe(root, (Node *) havingQual))
3947 grouped_rel->consider_parallel = true;
3948
3949 /*
3950 * If the input rel belongs to a single FDW, so does the grouped rel.
3951 */
3952 grouped_rel->serverid = input_rel->serverid;
3953 grouped_rel->userid = input_rel->userid;
3954 grouped_rel->useridiscurrent = input_rel->useridiscurrent;
3955 grouped_rel->fdwroutine = input_rel->fdwroutine;
3956
3957 return grouped_rel;
3958 }
3959
3960 /*
3961 * is_degenerate_grouping
3962 *
3963 * A degenerate grouping is one in which the query has a HAVING qual and/or
3964 * grouping sets, but no aggregates and no GROUP BY (which implies that the
3965 * grouping sets are all empty).
3966 */
3967 static bool
is_degenerate_grouping(PlannerInfo * root)3968 is_degenerate_grouping(PlannerInfo *root)
3969 {
3970 Query *parse = root->parse;
3971
3972 return (root->hasHavingQual || parse->groupingSets) &&
3973 !parse->hasAggs && parse->groupClause == NIL;
3974 }
3975
3976 /*
3977 * create_degenerate_grouping_paths
3978 *
3979 * When the grouping is degenerate (see is_degenerate_grouping), we are
3980 * supposed to emit either zero or one row for each grouping set depending on
3981 * whether HAVING succeeds. Furthermore, there cannot be any variables in
3982 * either HAVING or the targetlist, so we actually do not need the FROM table
3983 * at all! We can just throw away the plan-so-far and generate a Result node.
3984 * This is a sufficiently unusual corner case that it's not worth contorting
3985 * the structure of this module to avoid having to generate the earlier paths
3986 * in the first place.
3987 */
3988 static void
create_degenerate_grouping_paths(PlannerInfo * root,RelOptInfo * input_rel,RelOptInfo * grouped_rel)3989 create_degenerate_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel,
3990 RelOptInfo *grouped_rel)
3991 {
3992 Query *parse = root->parse;
3993 int nrows;
3994 Path *path;
3995
3996 nrows = list_length(parse->groupingSets);
3997 if (nrows > 1)
3998 {
3999 /*
4000 * Doesn't seem worthwhile writing code to cons up a generate_series
4001 * or a values scan to emit multiple rows. Instead just make N clones
4002 * and append them. (With a volatile HAVING clause, this means you
4003 * might get between 0 and N output rows. Offhand I think that's
4004 * desired.)
4005 */
4006 List *paths = NIL;
4007
4008 while (--nrows >= 0)
4009 {
4010 path = (Path *)
4011 create_group_result_path(root, grouped_rel,
4012 grouped_rel->reltarget,
4013 (List *) parse->havingQual);
4014 paths = lappend(paths, path);
4015 }
4016 path = (Path *)
4017 create_append_path(root,
4018 grouped_rel,
4019 paths,
4020 NIL,
4021 NIL,
4022 NULL,
4023 0,
4024 false,
4025 NIL,
4026 -1);
4027 }
4028 else
4029 {
4030 /* No grouping sets, or just one, so one output row */
4031 path = (Path *)
4032 create_group_result_path(root, grouped_rel,
4033 grouped_rel->reltarget,
4034 (List *) parse->havingQual);
4035 }
4036
4037 add_path(grouped_rel, path);
4038 }
4039
4040 /*
4041 * create_ordinary_grouping_paths
4042 *
4043 * Create grouping paths for the ordinary (that is, non-degenerate) case.
4044 *
4045 * We need to consider sorted and hashed aggregation in the same function,
4046 * because otherwise (1) it would be harder to throw an appropriate error
4047 * message if neither way works, and (2) we should not allow hashtable size
4048 * considerations to dissuade us from using hashing if sorting is not possible.
4049 *
4050 * *partially_grouped_rel_p will be set to the partially grouped rel which this
4051 * function creates, or to NULL if it doesn't create one.
4052 */
4053 static void
create_ordinary_grouping_paths(PlannerInfo * root,RelOptInfo * input_rel,RelOptInfo * grouped_rel,const AggClauseCosts * agg_costs,grouping_sets_data * gd,GroupPathExtraData * extra,RelOptInfo ** partially_grouped_rel_p)4054 create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel,
4055 RelOptInfo *grouped_rel,
4056 const AggClauseCosts *agg_costs,
4057 grouping_sets_data *gd,
4058 GroupPathExtraData *extra,
4059 RelOptInfo **partially_grouped_rel_p)
4060 {
4061 Path *cheapest_path = input_rel->cheapest_total_path;
4062 RelOptInfo *partially_grouped_rel = NULL;
4063 double dNumGroups;
4064 PartitionwiseAggregateType patype = PARTITIONWISE_AGGREGATE_NONE;
4065
4066 /*
4067 * If this is the topmost grouping relation or if the parent relation is
4068 * doing some form of partitionwise aggregation, then we may be able to do
4069 * it at this level also. However, if the input relation is not
4070 * partitioned, partitionwise aggregate is impossible.
4071 */
4072 if (extra->patype != PARTITIONWISE_AGGREGATE_NONE &&
4073 IS_PARTITIONED_REL(input_rel))
4074 {
4075 /*
4076 * If this is the topmost relation or if the parent relation is doing
4077 * full partitionwise aggregation, then we can do full partitionwise
4078 * aggregation provided that the GROUP BY clause contains all of the
4079 * partitioning columns at this level. Otherwise, we can do at most
4080 * partial partitionwise aggregation. But if partial aggregation is
4081 * not supported in general then we can't use it for partitionwise
4082 * aggregation either.
4083 */
4084 if (extra->patype == PARTITIONWISE_AGGREGATE_FULL &&
4085 group_by_has_partkey(input_rel, extra->targetList,
4086 root->parse->groupClause))
4087 patype = PARTITIONWISE_AGGREGATE_FULL;
4088 else if ((extra->flags & GROUPING_CAN_PARTIAL_AGG) != 0)
4089 patype = PARTITIONWISE_AGGREGATE_PARTIAL;
4090 else
4091 patype = PARTITIONWISE_AGGREGATE_NONE;
4092 }
4093
4094 /*
4095 * Before generating paths for grouped_rel, we first generate any possible
4096 * partially grouped paths; that way, later code can easily consider both
4097 * parallel and non-parallel approaches to grouping.
4098 */
4099 if ((extra->flags & GROUPING_CAN_PARTIAL_AGG) != 0)
4100 {
4101 bool force_rel_creation;
4102
4103 /*
4104 * If we're doing partitionwise aggregation at this level, force
4105 * creation of a partially_grouped_rel so we can add partitionwise
4106 * paths to it.
4107 */
4108 force_rel_creation = (patype == PARTITIONWISE_AGGREGATE_PARTIAL);
4109
4110 partially_grouped_rel =
4111 create_partial_grouping_paths(root,
4112 grouped_rel,
4113 input_rel,
4114 gd,
4115 extra,
4116 force_rel_creation);
4117 }
4118
4119 /* Set out parameter. */
4120 *partially_grouped_rel_p = partially_grouped_rel;
4121
4122 /* Apply partitionwise aggregation technique, if possible. */
4123 if (patype != PARTITIONWISE_AGGREGATE_NONE)
4124 create_partitionwise_grouping_paths(root, input_rel, grouped_rel,
4125 partially_grouped_rel, agg_costs,
4126 gd, patype, extra);
4127
4128 /* If we are doing partial aggregation only, return. */
4129 if (extra->patype == PARTITIONWISE_AGGREGATE_PARTIAL)
4130 {
4131 Assert(partially_grouped_rel);
4132
4133 if (partially_grouped_rel->pathlist)
4134 set_cheapest(partially_grouped_rel);
4135
4136 return;
4137 }
4138
4139 /* Gather any partially grouped partial paths. */
4140 if (partially_grouped_rel && partially_grouped_rel->partial_pathlist)
4141 {
4142 gather_grouping_paths(root, partially_grouped_rel);
4143 set_cheapest(partially_grouped_rel);
4144 }
4145
4146 /*
4147 * Estimate number of groups.
4148 */
4149 dNumGroups = get_number_of_groups(root,
4150 cheapest_path->rows,
4151 gd,
4152 extra->targetList);
4153
4154 /* Build final grouping paths */
4155 add_paths_to_grouping_rel(root, input_rel, grouped_rel,
4156 partially_grouped_rel, agg_costs, gd,
4157 dNumGroups, extra);
4158
4159 /* Give a helpful error if we failed to find any implementation */
4160 if (grouped_rel->pathlist == NIL)
4161 ereport(ERROR,
4162 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
4163 errmsg("could not implement GROUP BY"),
4164 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
4165
4166 /*
4167 * If there is an FDW that's responsible for all baserels of the query,
4168 * let it consider adding ForeignPaths.
4169 */
4170 if (grouped_rel->fdwroutine &&
4171 grouped_rel->fdwroutine->GetForeignUpperPaths)
4172 grouped_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_GROUP_AGG,
4173 input_rel, grouped_rel,
4174 extra);
4175
4176 /* Let extensions possibly add some more paths */
4177 if (create_upper_paths_hook)
4178 (*create_upper_paths_hook) (root, UPPERREL_GROUP_AGG,
4179 input_rel, grouped_rel,
4180 extra);
4181 }
4182
4183 /*
4184 * For a given input path, consider the possible ways of doing grouping sets on
4185 * it, by combinations of hashing and sorting. This can be called multiple
4186 * times, so it's important that it not scribble on input. No result is
4187 * returned, but any generated paths are added to grouped_rel.
4188 */
4189 static void
consider_groupingsets_paths(PlannerInfo * root,RelOptInfo * grouped_rel,Path * path,bool is_sorted,bool can_hash,grouping_sets_data * gd,const AggClauseCosts * agg_costs,double dNumGroups)4190 consider_groupingsets_paths(PlannerInfo *root,
4191 RelOptInfo *grouped_rel,
4192 Path *path,
4193 bool is_sorted,
4194 bool can_hash,
4195 grouping_sets_data *gd,
4196 const AggClauseCosts *agg_costs,
4197 double dNumGroups)
4198 {
4199 Query *parse = root->parse;
4200 Size hash_mem_limit = get_hash_memory_limit();
4201
4202 /*
4203 * If we're not being offered sorted input, then only consider plans that
4204 * can be done entirely by hashing.
4205 *
4206 * We can hash everything if it looks like it'll fit in hash_mem. But if
4207 * the input is actually sorted despite not being advertised as such, we
4208 * prefer to make use of that in order to use less memory.
4209 *
4210 * If none of the grouping sets are sortable, then ignore the hash_mem
4211 * limit and generate a path anyway, since otherwise we'll just fail.
4212 */
4213 if (!is_sorted)
4214 {
4215 List *new_rollups = NIL;
4216 RollupData *unhashed_rollup = NULL;
4217 List *sets_data;
4218 List *empty_sets_data = NIL;
4219 List *empty_sets = NIL;
4220 ListCell *lc;
4221 ListCell *l_start = list_head(gd->rollups);
4222 AggStrategy strat = AGG_HASHED;
4223 double hashsize;
4224 double exclude_groups = 0.0;
4225
4226 Assert(can_hash);
4227
4228 /*
4229 * If the input is coincidentally sorted usefully (which can happen
4230 * even if is_sorted is false, since that only means that our caller
4231 * has set up the sorting for us), then save some hashtable space by
4232 * making use of that. But we need to watch out for degenerate cases:
4233 *
4234 * 1) If there are any empty grouping sets, then group_pathkeys might
4235 * be NIL if all non-empty grouping sets are unsortable. In this case,
4236 * there will be a rollup containing only empty groups, and the
4237 * pathkeys_contained_in test is vacuously true; this is ok.
4238 *
4239 * XXX: the above relies on the fact that group_pathkeys is generated
4240 * from the first rollup. If we add the ability to consider multiple
4241 * sort orders for grouping input, this assumption might fail.
4242 *
4243 * 2) If there are no empty sets and only unsortable sets, then the
4244 * rollups list will be empty (and thus l_start == NULL), and
4245 * group_pathkeys will be NIL; we must ensure that the vacuously-true
4246 * pathkeys_contained_in test doesn't cause us to crash.
4247 */
4248 if (l_start != NULL &&
4249 pathkeys_contained_in(root->group_pathkeys, path->pathkeys))
4250 {
4251 unhashed_rollup = lfirst_node(RollupData, l_start);
4252 exclude_groups = unhashed_rollup->numGroups;
4253 l_start = lnext(gd->rollups, l_start);
4254 }
4255
4256 hashsize = estimate_hashagg_tablesize(path,
4257 agg_costs,
4258 dNumGroups - exclude_groups);
4259
4260 /*
4261 * gd->rollups is empty if we have only unsortable columns to work
4262 * with. Override hash_mem in that case; otherwise, we'll rely on the
4263 * sorted-input case to generate usable mixed paths.
4264 */
4265 if (hashsize > hash_mem_limit && gd->rollups)
4266 return; /* nope, won't fit */
4267
4268 /*
4269 * We need to burst the existing rollups list into individual grouping
4270 * sets and recompute a groupClause for each set.
4271 */
4272 sets_data = list_copy(gd->unsortable_sets);
4273
4274 for_each_cell(lc, gd->rollups, l_start)
4275 {
4276 RollupData *rollup = lfirst_node(RollupData, lc);
4277
4278 /*
4279 * If we find an unhashable rollup that's not been skipped by the
4280 * "actually sorted" check above, we can't cope; we'd need sorted
4281 * input (with a different sort order) but we can't get that here.
4282 * So bail out; we'll get a valid path from the is_sorted case
4283 * instead.
4284 *
4285 * The mere presence of empty grouping sets doesn't make a rollup
4286 * unhashable (see preprocess_grouping_sets), we handle those
4287 * specially below.
4288 */
4289 if (!rollup->hashable)
4290 return;
4291
4292 sets_data = list_concat(sets_data, rollup->gsets_data);
4293 }
4294 foreach(lc, sets_data)
4295 {
4296 GroupingSetData *gs = lfirst_node(GroupingSetData, lc);
4297 List *gset = gs->set;
4298 RollupData *rollup;
4299
4300 if (gset == NIL)
4301 {
4302 /* Empty grouping sets can't be hashed. */
4303 empty_sets_data = lappend(empty_sets_data, gs);
4304 empty_sets = lappend(empty_sets, NIL);
4305 }
4306 else
4307 {
4308 rollup = makeNode(RollupData);
4309
4310 rollup->groupClause = preprocess_groupclause(root, gset);
4311 rollup->gsets_data = list_make1(gs);
4312 rollup->gsets = remap_to_groupclause_idx(rollup->groupClause,
4313 rollup->gsets_data,
4314 gd->tleref_to_colnum_map);
4315 rollup->numGroups = gs->numGroups;
4316 rollup->hashable = true;
4317 rollup->is_hashed = true;
4318 new_rollups = lappend(new_rollups, rollup);
4319 }
4320 }
4321
4322 /*
4323 * If we didn't find anything nonempty to hash, then bail. We'll
4324 * generate a path from the is_sorted case.
4325 */
4326 if (new_rollups == NIL)
4327 return;
4328
4329 /*
4330 * If there were empty grouping sets they should have been in the
4331 * first rollup.
4332 */
4333 Assert(!unhashed_rollup || !empty_sets);
4334
4335 if (unhashed_rollup)
4336 {
4337 new_rollups = lappend(new_rollups, unhashed_rollup);
4338 strat = AGG_MIXED;
4339 }
4340 else if (empty_sets)
4341 {
4342 RollupData *rollup = makeNode(RollupData);
4343
4344 rollup->groupClause = NIL;
4345 rollup->gsets_data = empty_sets_data;
4346 rollup->gsets = empty_sets;
4347 rollup->numGroups = list_length(empty_sets);
4348 rollup->hashable = false;
4349 rollup->is_hashed = false;
4350 new_rollups = lappend(new_rollups, rollup);
4351 strat = AGG_MIXED;
4352 }
4353
4354 add_path(grouped_rel, (Path *)
4355 create_groupingsets_path(root,
4356 grouped_rel,
4357 path,
4358 (List *) parse->havingQual,
4359 strat,
4360 new_rollups,
4361 agg_costs,
4362 dNumGroups));
4363 return;
4364 }
4365
4366 /*
4367 * If we have sorted input but nothing we can do with it, bail.
4368 */
4369 if (list_length(gd->rollups) == 0)
4370 return;
4371
4372 /*
4373 * Given sorted input, we try and make two paths: one sorted and one mixed
4374 * sort/hash. (We need to try both because hashagg might be disabled, or
4375 * some columns might not be sortable.)
4376 *
4377 * can_hash is passed in as false if some obstacle elsewhere (such as
4378 * ordered aggs) means that we shouldn't consider hashing at all.
4379 */
4380 if (can_hash && gd->any_hashable)
4381 {
4382 List *rollups = NIL;
4383 List *hash_sets = list_copy(gd->unsortable_sets);
4384 double availspace = hash_mem_limit;
4385 ListCell *lc;
4386
4387 /*
4388 * Account first for space needed for groups we can't sort at all.
4389 */
4390 availspace -= estimate_hashagg_tablesize(path,
4391 agg_costs,
4392 gd->dNumHashGroups);
4393
4394 if (availspace > 0 && list_length(gd->rollups) > 1)
4395 {
4396 double scale;
4397 int num_rollups = list_length(gd->rollups);
4398 int k_capacity;
4399 int *k_weights = palloc(num_rollups * sizeof(int));
4400 Bitmapset *hash_items = NULL;
4401 int i;
4402
4403 /*
4404 * We treat this as a knapsack problem: the knapsack capacity
4405 * represents hash_mem, the item weights are the estimated memory
4406 * usage of the hashtables needed to implement a single rollup,
4407 * and we really ought to use the cost saving as the item value;
4408 * however, currently the costs assigned to sort nodes don't
4409 * reflect the comparison costs well, and so we treat all items as
4410 * of equal value (each rollup we hash instead saves us one sort).
4411 *
4412 * To use the discrete knapsack, we need to scale the values to a
4413 * reasonably small bounded range. We choose to allow a 5% error
4414 * margin; we have no more than 4096 rollups in the worst possible
4415 * case, which with a 5% error margin will require a bit over 42MB
4416 * of workspace. (Anyone wanting to plan queries that complex had
4417 * better have the memory for it. In more reasonable cases, with
4418 * no more than a couple of dozen rollups, the memory usage will
4419 * be negligible.)
4420 *
4421 * k_capacity is naturally bounded, but we clamp the values for
4422 * scale and weight (below) to avoid overflows or underflows (or
4423 * uselessly trying to use a scale factor less than 1 byte).
4424 */
4425 scale = Max(availspace / (20.0 * num_rollups), 1.0);
4426 k_capacity = (int) floor(availspace / scale);
4427
4428 /*
4429 * We leave the first rollup out of consideration since it's the
4430 * one that matches the input sort order. We assign indexes "i"
4431 * to only those entries considered for hashing; the second loop,
4432 * below, must use the same condition.
4433 */
4434 i = 0;
4435 for_each_from(lc, gd->rollups, 1)
4436 {
4437 RollupData *rollup = lfirst_node(RollupData, lc);
4438
4439 if (rollup->hashable)
4440 {
4441 double sz = estimate_hashagg_tablesize(path,
4442 agg_costs,
4443 rollup->numGroups);
4444
4445 /*
4446 * If sz is enormous, but hash_mem (and hence scale) is
4447 * small, avoid integer overflow here.
4448 */
4449 k_weights[i] = (int) Min(floor(sz / scale),
4450 k_capacity + 1.0);
4451 ++i;
4452 }
4453 }
4454
4455 /*
4456 * Apply knapsack algorithm; compute the set of items which
4457 * maximizes the value stored (in this case the number of sorts
4458 * saved) while keeping the total size (approximately) within
4459 * capacity.
4460 */
4461 if (i > 0)
4462 hash_items = DiscreteKnapsack(k_capacity, i, k_weights, NULL);
4463
4464 if (!bms_is_empty(hash_items))
4465 {
4466 rollups = list_make1(linitial(gd->rollups));
4467
4468 i = 0;
4469 for_each_from(lc, gd->rollups, 1)
4470 {
4471 RollupData *rollup = lfirst_node(RollupData, lc);
4472
4473 if (rollup->hashable)
4474 {
4475 if (bms_is_member(i, hash_items))
4476 hash_sets = list_concat(hash_sets,
4477 rollup->gsets_data);
4478 else
4479 rollups = lappend(rollups, rollup);
4480 ++i;
4481 }
4482 else
4483 rollups = lappend(rollups, rollup);
4484 }
4485 }
4486 }
4487
4488 if (!rollups && hash_sets)
4489 rollups = list_copy(gd->rollups);
4490
4491 foreach(lc, hash_sets)
4492 {
4493 GroupingSetData *gs = lfirst_node(GroupingSetData, lc);
4494 RollupData *rollup = makeNode(RollupData);
4495
4496 Assert(gs->set != NIL);
4497
4498 rollup->groupClause = preprocess_groupclause(root, gs->set);
4499 rollup->gsets_data = list_make1(gs);
4500 rollup->gsets = remap_to_groupclause_idx(rollup->groupClause,
4501 rollup->gsets_data,
4502 gd->tleref_to_colnum_map);
4503 rollup->numGroups = gs->numGroups;
4504 rollup->hashable = true;
4505 rollup->is_hashed = true;
4506 rollups = lcons(rollup, rollups);
4507 }
4508
4509 if (rollups)
4510 {
4511 add_path(grouped_rel, (Path *)
4512 create_groupingsets_path(root,
4513 grouped_rel,
4514 path,
4515 (List *) parse->havingQual,
4516 AGG_MIXED,
4517 rollups,
4518 agg_costs,
4519 dNumGroups));
4520 }
4521 }
4522
4523 /*
4524 * Now try the simple sorted case.
4525 */
4526 if (!gd->unsortable_sets)
4527 add_path(grouped_rel, (Path *)
4528 create_groupingsets_path(root,
4529 grouped_rel,
4530 path,
4531 (List *) parse->havingQual,
4532 AGG_SORTED,
4533 gd->rollups,
4534 agg_costs,
4535 dNumGroups));
4536 }
4537
4538 /*
4539 * create_window_paths
4540 *
4541 * Build a new upperrel containing Paths for window-function evaluation.
4542 *
4543 * input_rel: contains the source-data Paths
4544 * input_target: result of make_window_input_target
4545 * output_target: what the topmost WindowAggPath should return
4546 * wflists: result of find_window_functions
4547 * activeWindows: result of select_active_windows
4548 *
4549 * Note: all Paths in input_rel are expected to return input_target.
4550 */
4551 static RelOptInfo *
create_window_paths(PlannerInfo * root,RelOptInfo * input_rel,PathTarget * input_target,PathTarget * output_target,bool output_target_parallel_safe,WindowFuncLists * wflists,List * activeWindows)4552 create_window_paths(PlannerInfo *root,
4553 RelOptInfo *input_rel,
4554 PathTarget *input_target,
4555 PathTarget *output_target,
4556 bool output_target_parallel_safe,
4557 WindowFuncLists *wflists,
4558 List *activeWindows)
4559 {
4560 RelOptInfo *window_rel;
4561 ListCell *lc;
4562
4563 /* For now, do all work in the (WINDOW, NULL) upperrel */
4564 window_rel = fetch_upper_rel(root, UPPERREL_WINDOW, NULL);
4565
4566 /*
4567 * If the input relation is not parallel-safe, then the window relation
4568 * can't be parallel-safe, either. Otherwise, we need to examine the
4569 * target list and active windows for non-parallel-safe constructs.
4570 */
4571 if (input_rel->consider_parallel && output_target_parallel_safe &&
4572 is_parallel_safe(root, (Node *) activeWindows))
4573 window_rel->consider_parallel = true;
4574
4575 /*
4576 * If the input rel belongs to a single FDW, so does the window rel.
4577 */
4578 window_rel->serverid = input_rel->serverid;
4579 window_rel->userid = input_rel->userid;
4580 window_rel->useridiscurrent = input_rel->useridiscurrent;
4581 window_rel->fdwroutine = input_rel->fdwroutine;
4582
4583 /*
4584 * Consider computing window functions starting from the existing
4585 * cheapest-total path (which will likely require a sort) as well as any
4586 * existing paths that satisfy root->window_pathkeys (which won't).
4587 */
4588 foreach(lc, input_rel->pathlist)
4589 {
4590 Path *path = (Path *) lfirst(lc);
4591
4592 if (path == input_rel->cheapest_total_path ||
4593 pathkeys_contained_in(root->window_pathkeys, path->pathkeys))
4594 create_one_window_path(root,
4595 window_rel,
4596 path,
4597 input_target,
4598 output_target,
4599 wflists,
4600 activeWindows);
4601 }
4602
4603 /*
4604 * If there is an FDW that's responsible for all baserels of the query,
4605 * let it consider adding ForeignPaths.
4606 */
4607 if (window_rel->fdwroutine &&
4608 window_rel->fdwroutine->GetForeignUpperPaths)
4609 window_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_WINDOW,
4610 input_rel, window_rel,
4611 NULL);
4612
4613 /* Let extensions possibly add some more paths */
4614 if (create_upper_paths_hook)
4615 (*create_upper_paths_hook) (root, UPPERREL_WINDOW,
4616 input_rel, window_rel, NULL);
4617
4618 /* Now choose the best path(s) */
4619 set_cheapest(window_rel);
4620
4621 return window_rel;
4622 }
4623
4624 /*
4625 * Stack window-function implementation steps atop the given Path, and
4626 * add the result to window_rel.
4627 *
4628 * window_rel: upperrel to contain result
4629 * path: input Path to use (must return input_target)
4630 * input_target: result of make_window_input_target
4631 * output_target: what the topmost WindowAggPath should return
4632 * wflists: result of find_window_functions
4633 * activeWindows: result of select_active_windows
4634 */
4635 static void
create_one_window_path(PlannerInfo * root,RelOptInfo * window_rel,Path * path,PathTarget * input_target,PathTarget * output_target,WindowFuncLists * wflists,List * activeWindows)4636 create_one_window_path(PlannerInfo *root,
4637 RelOptInfo *window_rel,
4638 Path *path,
4639 PathTarget *input_target,
4640 PathTarget *output_target,
4641 WindowFuncLists *wflists,
4642 List *activeWindows)
4643 {
4644 PathTarget *window_target;
4645 ListCell *l;
4646
4647 /*
4648 * Since each window clause could require a different sort order, we stack
4649 * up a WindowAgg node for each clause, with sort steps between them as
4650 * needed. (We assume that select_active_windows chose a good order for
4651 * executing the clauses in.)
4652 *
4653 * input_target should contain all Vars and Aggs needed for the result.
4654 * (In some cases we wouldn't need to propagate all of these all the way
4655 * to the top, since they might only be needed as inputs to WindowFuncs.
4656 * It's probably not worth trying to optimize that though.) It must also
4657 * contain all window partitioning and sorting expressions, to ensure
4658 * they're computed only once at the bottom of the stack (that's critical
4659 * for volatile functions). As we climb up the stack, we'll add outputs
4660 * for the WindowFuncs computed at each level.
4661 */
4662 window_target = input_target;
4663
4664 foreach(l, activeWindows)
4665 {
4666 WindowClause *wc = lfirst_node(WindowClause, l);
4667 List *window_pathkeys;
4668
4669 window_pathkeys = make_pathkeys_for_window(root,
4670 wc,
4671 root->processed_tlist);
4672
4673 /* Sort if necessary */
4674 if (!pathkeys_contained_in(window_pathkeys, path->pathkeys))
4675 {
4676 path = (Path *) create_sort_path(root, window_rel,
4677 path,
4678 window_pathkeys,
4679 -1.0);
4680 }
4681
4682 if (lnext(activeWindows, l))
4683 {
4684 /*
4685 * Add the current WindowFuncs to the output target for this
4686 * intermediate WindowAggPath. We must copy window_target to
4687 * avoid changing the previous path's target.
4688 *
4689 * Note: a WindowFunc adds nothing to the target's eval costs; but
4690 * we do need to account for the increase in tlist width.
4691 */
4692 ListCell *lc2;
4693
4694 window_target = copy_pathtarget(window_target);
4695 foreach(lc2, wflists->windowFuncs[wc->winref])
4696 {
4697 WindowFunc *wfunc = lfirst_node(WindowFunc, lc2);
4698
4699 add_column_to_pathtarget(window_target, (Expr *) wfunc, 0);
4700 window_target->width += get_typavgwidth(wfunc->wintype, -1);
4701 }
4702 }
4703 else
4704 {
4705 /* Install the goal target in the topmost WindowAgg */
4706 window_target = output_target;
4707 }
4708
4709 path = (Path *)
4710 create_windowagg_path(root, window_rel, path, window_target,
4711 wflists->windowFuncs[wc->winref],
4712 wc);
4713 }
4714
4715 add_path(window_rel, path);
4716 }
4717
4718 /*
4719 * create_distinct_paths
4720 *
4721 * Build a new upperrel containing Paths for SELECT DISTINCT evaluation.
4722 *
4723 * input_rel: contains the source-data Paths
4724 *
4725 * Note: input paths should already compute the desired pathtarget, since
4726 * Sort/Unique won't project anything.
4727 */
4728 static RelOptInfo *
create_distinct_paths(PlannerInfo * root,RelOptInfo * input_rel)4729 create_distinct_paths(PlannerInfo *root,
4730 RelOptInfo *input_rel)
4731 {
4732 Query *parse = root->parse;
4733 Path *cheapest_input_path = input_rel->cheapest_total_path;
4734 RelOptInfo *distinct_rel;
4735 double numDistinctRows;
4736 bool allow_hash;
4737 Path *path;
4738 ListCell *lc;
4739
4740 /* For now, do all work in the (DISTINCT, NULL) upperrel */
4741 distinct_rel = fetch_upper_rel(root, UPPERREL_DISTINCT, NULL);
4742
4743 /*
4744 * We don't compute anything at this level, so distinct_rel will be
4745 * parallel-safe if the input rel is parallel-safe. In particular, if
4746 * there is a DISTINCT ON (...) clause, any path for the input_rel will
4747 * output those expressions, and will not be parallel-safe unless those
4748 * expressions are parallel-safe.
4749 */
4750 distinct_rel->consider_parallel = input_rel->consider_parallel;
4751
4752 /*
4753 * If the input rel belongs to a single FDW, so does the distinct_rel.
4754 */
4755 distinct_rel->serverid = input_rel->serverid;
4756 distinct_rel->userid = input_rel->userid;
4757 distinct_rel->useridiscurrent = input_rel->useridiscurrent;
4758 distinct_rel->fdwroutine = input_rel->fdwroutine;
4759
4760 /* Estimate number of distinct rows there will be */
4761 if (parse->groupClause || parse->groupingSets || parse->hasAggs ||
4762 root->hasHavingQual)
4763 {
4764 /*
4765 * If there was grouping or aggregation, use the number of input rows
4766 * as the estimated number of DISTINCT rows (ie, assume the input is
4767 * already mostly unique).
4768 */
4769 numDistinctRows = cheapest_input_path->rows;
4770 }
4771 else
4772 {
4773 /*
4774 * Otherwise, the UNIQUE filter has effects comparable to GROUP BY.
4775 */
4776 List *distinctExprs;
4777
4778 distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
4779 parse->targetList);
4780 numDistinctRows = estimate_num_groups(root, distinctExprs,
4781 cheapest_input_path->rows,
4782 NULL);
4783 }
4784
4785 /*
4786 * Consider sort-based implementations of DISTINCT, if possible.
4787 */
4788 if (grouping_is_sortable(parse->distinctClause))
4789 {
4790 /*
4791 * First, if we have any adequately-presorted paths, just stick a
4792 * Unique node on those. Then consider doing an explicit sort of the
4793 * cheapest input path and Unique'ing that.
4794 *
4795 * When we have DISTINCT ON, we must sort by the more rigorous of
4796 * DISTINCT and ORDER BY, else it won't have the desired behavior.
4797 * Also, if we do have to do an explicit sort, we might as well use
4798 * the more rigorous ordering to avoid a second sort later. (Note
4799 * that the parser will have ensured that one clause is a prefix of
4800 * the other.)
4801 */
4802 List *needed_pathkeys;
4803
4804 if (parse->hasDistinctOn &&
4805 list_length(root->distinct_pathkeys) <
4806 list_length(root->sort_pathkeys))
4807 needed_pathkeys = root->sort_pathkeys;
4808 else
4809 needed_pathkeys = root->distinct_pathkeys;
4810
4811 foreach(lc, input_rel->pathlist)
4812 {
4813 Path *path = (Path *) lfirst(lc);
4814
4815 if (pathkeys_contained_in(needed_pathkeys, path->pathkeys))
4816 {
4817 add_path(distinct_rel, (Path *)
4818 create_upper_unique_path(root, distinct_rel,
4819 path,
4820 list_length(root->distinct_pathkeys),
4821 numDistinctRows));
4822 }
4823 }
4824
4825 /* For explicit-sort case, always use the more rigorous clause */
4826 if (list_length(root->distinct_pathkeys) <
4827 list_length(root->sort_pathkeys))
4828 {
4829 needed_pathkeys = root->sort_pathkeys;
4830 /* Assert checks that parser didn't mess up... */
4831 Assert(pathkeys_contained_in(root->distinct_pathkeys,
4832 needed_pathkeys));
4833 }
4834 else
4835 needed_pathkeys = root->distinct_pathkeys;
4836
4837 path = cheapest_input_path;
4838 if (!pathkeys_contained_in(needed_pathkeys, path->pathkeys))
4839 path = (Path *) create_sort_path(root, distinct_rel,
4840 path,
4841 needed_pathkeys,
4842 -1.0);
4843
4844 add_path(distinct_rel, (Path *)
4845 create_upper_unique_path(root, distinct_rel,
4846 path,
4847 list_length(root->distinct_pathkeys),
4848 numDistinctRows));
4849 }
4850
4851 /*
4852 * Consider hash-based implementations of DISTINCT, if possible.
4853 *
4854 * If we were not able to make any other types of path, we *must* hash or
4855 * die trying. If we do have other choices, there are two things that
4856 * should prevent selection of hashing: if the query uses DISTINCT ON
4857 * (because it won't really have the expected behavior if we hash), or if
4858 * enable_hashagg is off.
4859 *
4860 * Note: grouping_is_hashable() is much more expensive to check than the
4861 * other gating conditions, so we want to do it last.
4862 */
4863 if (distinct_rel->pathlist == NIL)
4864 allow_hash = true; /* we have no alternatives */
4865 else if (parse->hasDistinctOn || !enable_hashagg)
4866 allow_hash = false; /* policy-based decision not to hash */
4867 else
4868 allow_hash = true; /* default */
4869
4870 if (allow_hash && grouping_is_hashable(parse->distinctClause))
4871 {
4872 /* Generate hashed aggregate path --- no sort needed */
4873 add_path(distinct_rel, (Path *)
4874 create_agg_path(root,
4875 distinct_rel,
4876 cheapest_input_path,
4877 cheapest_input_path->pathtarget,
4878 AGG_HASHED,
4879 AGGSPLIT_SIMPLE,
4880 parse->distinctClause,
4881 NIL,
4882 NULL,
4883 numDistinctRows));
4884 }
4885
4886 /* Give a helpful error if we failed to find any implementation */
4887 if (distinct_rel->pathlist == NIL)
4888 ereport(ERROR,
4889 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
4890 errmsg("could not implement DISTINCT"),
4891 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
4892
4893 /*
4894 * If there is an FDW that's responsible for all baserels of the query,
4895 * let it consider adding ForeignPaths.
4896 */
4897 if (distinct_rel->fdwroutine &&
4898 distinct_rel->fdwroutine->GetForeignUpperPaths)
4899 distinct_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_DISTINCT,
4900 input_rel, distinct_rel,
4901 NULL);
4902
4903 /* Let extensions possibly add some more paths */
4904 if (create_upper_paths_hook)
4905 (*create_upper_paths_hook) (root, UPPERREL_DISTINCT,
4906 input_rel, distinct_rel, NULL);
4907
4908 /* Now choose the best path(s) */
4909 set_cheapest(distinct_rel);
4910
4911 return distinct_rel;
4912 }
4913
4914 /*
4915 * create_ordered_paths
4916 *
4917 * Build a new upperrel containing Paths for ORDER BY evaluation.
4918 *
4919 * All paths in the result must satisfy the ORDER BY ordering.
4920 * The only new paths we need consider are an explicit full sort
4921 * and incremental sort on the cheapest-total existing path.
4922 *
4923 * input_rel: contains the source-data Paths
4924 * target: the output tlist the result Paths must emit
4925 * limit_tuples: estimated bound on the number of output tuples,
4926 * or -1 if no LIMIT or couldn't estimate
4927 *
4928 * XXX This only looks at sort_pathkeys. I wonder if it needs to look at the
4929 * other pathkeys (grouping, ...) like generate_useful_gather_paths.
4930 */
4931 static RelOptInfo *
create_ordered_paths(PlannerInfo * root,RelOptInfo * input_rel,PathTarget * target,bool target_parallel_safe,double limit_tuples)4932 create_ordered_paths(PlannerInfo *root,
4933 RelOptInfo *input_rel,
4934 PathTarget *target,
4935 bool target_parallel_safe,
4936 double limit_tuples)
4937 {
4938 Path *cheapest_input_path = input_rel->cheapest_total_path;
4939 RelOptInfo *ordered_rel;
4940 ListCell *lc;
4941
4942 /* For now, do all work in the (ORDERED, NULL) upperrel */
4943 ordered_rel = fetch_upper_rel(root, UPPERREL_ORDERED, NULL);
4944
4945 /*
4946 * If the input relation is not parallel-safe, then the ordered relation
4947 * can't be parallel-safe, either. Otherwise, it's parallel-safe if the
4948 * target list is parallel-safe.
4949 */
4950 if (input_rel->consider_parallel && target_parallel_safe)
4951 ordered_rel->consider_parallel = true;
4952
4953 /*
4954 * If the input rel belongs to a single FDW, so does the ordered_rel.
4955 */
4956 ordered_rel->serverid = input_rel->serverid;
4957 ordered_rel->userid = input_rel->userid;
4958 ordered_rel->useridiscurrent = input_rel->useridiscurrent;
4959 ordered_rel->fdwroutine = input_rel->fdwroutine;
4960
4961 foreach(lc, input_rel->pathlist)
4962 {
4963 Path *input_path = (Path *) lfirst(lc);
4964 Path *sorted_path = input_path;
4965 bool is_sorted;
4966 int presorted_keys;
4967
4968 is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
4969 input_path->pathkeys, &presorted_keys);
4970
4971 if (is_sorted)
4972 {
4973 /* Use the input path as is, but add a projection step if needed */
4974 if (sorted_path->pathtarget != target)
4975 sorted_path = apply_projection_to_path(root, ordered_rel,
4976 sorted_path, target);
4977
4978 add_path(ordered_rel, sorted_path);
4979 }
4980 else
4981 {
4982 /*
4983 * Try adding an explicit sort, but only to the cheapest total
4984 * path since a full sort should generally add the same cost to
4985 * all paths.
4986 */
4987 if (input_path == cheapest_input_path)
4988 {
4989 /*
4990 * Sort the cheapest input path. An explicit sort here can
4991 * take advantage of LIMIT.
4992 */
4993 sorted_path = (Path *) create_sort_path(root,
4994 ordered_rel,
4995 input_path,
4996 root->sort_pathkeys,
4997 limit_tuples);
4998 /* Add projection step if needed */
4999 if (sorted_path->pathtarget != target)
5000 sorted_path = apply_projection_to_path(root, ordered_rel,
5001 sorted_path, target);
5002
5003 add_path(ordered_rel, sorted_path);
5004 }
5005
5006 /*
5007 * If incremental sort is enabled, then try it as well. Unlike
5008 * with regular sorts, we can't just look at the cheapest path,
5009 * because the cost of incremental sort depends on how well
5010 * presorted the path is. Additionally incremental sort may enable
5011 * a cheaper startup path to win out despite higher total cost.
5012 */
5013 if (!enable_incremental_sort)
5014 continue;
5015
5016 /* Likewise, if the path can't be used for incremental sort. */
5017 if (!presorted_keys)
5018 continue;
5019
5020 /* Also consider incremental sort. */
5021 sorted_path = (Path *) create_incremental_sort_path(root,
5022 ordered_rel,
5023 input_path,
5024 root->sort_pathkeys,
5025 presorted_keys,
5026 limit_tuples);
5027
5028 /* Add projection step if needed */
5029 if (sorted_path->pathtarget != target)
5030 sorted_path = apply_projection_to_path(root, ordered_rel,
5031 sorted_path, target);
5032
5033 add_path(ordered_rel, sorted_path);
5034 }
5035 }
5036
5037 /*
5038 * generate_gather_paths() will have already generated a simple Gather
5039 * path for the best parallel path, if any, and the loop above will have
5040 * considered sorting it. Similarly, generate_gather_paths() will also
5041 * have generated order-preserving Gather Merge plans which can be used
5042 * without sorting if they happen to match the sort_pathkeys, and the loop
5043 * above will have handled those as well. However, there's one more
5044 * possibility: it may make sense to sort the cheapest partial path
5045 * according to the required output order and then use Gather Merge.
5046 */
5047 if (ordered_rel->consider_parallel && root->sort_pathkeys != NIL &&
5048 input_rel->partial_pathlist != NIL)
5049 {
5050 Path *cheapest_partial_path;
5051
5052 cheapest_partial_path = linitial(input_rel->partial_pathlist);
5053
5054 /*
5055 * If cheapest partial path doesn't need a sort, this is redundant
5056 * with what's already been tried.
5057 */
5058 if (!pathkeys_contained_in(root->sort_pathkeys,
5059 cheapest_partial_path->pathkeys))
5060 {
5061 Path *path;
5062 double total_groups;
5063
5064 path = (Path *) create_sort_path(root,
5065 ordered_rel,
5066 cheapest_partial_path,
5067 root->sort_pathkeys,
5068 limit_tuples);
5069
5070 total_groups = cheapest_partial_path->rows *
5071 cheapest_partial_path->parallel_workers;
5072 path = (Path *)
5073 create_gather_merge_path(root, ordered_rel,
5074 path,
5075 path->pathtarget,
5076 root->sort_pathkeys, NULL,
5077 &total_groups);
5078
5079 /* Add projection step if needed */
5080 if (path->pathtarget != target)
5081 path = apply_projection_to_path(root, ordered_rel,
5082 path, target);
5083
5084 add_path(ordered_rel, path);
5085 }
5086
5087 /*
5088 * Consider incremental sort with a gather merge on partial paths.
5089 *
5090 * We can also skip the entire loop when we only have a single-item
5091 * sort_pathkeys because then we can't possibly have a presorted
5092 * prefix of the list without having the list be fully sorted.
5093 */
5094 if (enable_incremental_sort && list_length(root->sort_pathkeys) > 1)
5095 {
5096 ListCell *lc;
5097
5098 foreach(lc, input_rel->partial_pathlist)
5099 {
5100 Path *input_path = (Path *) lfirst(lc);
5101 Path *sorted_path = input_path;
5102 bool is_sorted;
5103 int presorted_keys;
5104 double total_groups;
5105
5106 /*
5107 * We don't care if this is the cheapest partial path - we
5108 * can't simply skip it, because it may be partially sorted in
5109 * which case we want to consider adding incremental sort
5110 * (instead of full sort, which is what happens above).
5111 */
5112
5113 is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
5114 input_path->pathkeys,
5115 &presorted_keys);
5116
5117 /* No point in adding incremental sort on fully sorted paths. */
5118 if (is_sorted)
5119 continue;
5120
5121 if (presorted_keys == 0)
5122 continue;
5123
5124 /* Since we have presorted keys, consider incremental sort. */
5125 sorted_path = (Path *) create_incremental_sort_path(root,
5126 ordered_rel,
5127 input_path,
5128 root->sort_pathkeys,
5129 presorted_keys,
5130 limit_tuples);
5131 total_groups = input_path->rows *
5132 input_path->parallel_workers;
5133 sorted_path = (Path *)
5134 create_gather_merge_path(root, ordered_rel,
5135 sorted_path,
5136 sorted_path->pathtarget,
5137 root->sort_pathkeys, NULL,
5138 &total_groups);
5139
5140 /* Add projection step if needed */
5141 if (sorted_path->pathtarget != target)
5142 sorted_path = apply_projection_to_path(root, ordered_rel,
5143 sorted_path, target);
5144
5145 add_path(ordered_rel, sorted_path);
5146 }
5147 }
5148 }
5149
5150 /*
5151 * If there is an FDW that's responsible for all baserels of the query,
5152 * let it consider adding ForeignPaths.
5153 */
5154 if (ordered_rel->fdwroutine &&
5155 ordered_rel->fdwroutine->GetForeignUpperPaths)
5156 ordered_rel->fdwroutine->GetForeignUpperPaths(root, UPPERREL_ORDERED,
5157 input_rel, ordered_rel,
5158 NULL);
5159
5160 /* Let extensions possibly add some more paths */
5161 if (create_upper_paths_hook)
5162 (*create_upper_paths_hook) (root, UPPERREL_ORDERED,
5163 input_rel, ordered_rel, NULL);
5164
5165 /*
5166 * No need to bother with set_cheapest here; grouping_planner does not
5167 * need us to do it.
5168 */
5169 Assert(ordered_rel->pathlist != NIL);
5170
5171 return ordered_rel;
5172 }
5173
5174
5175 /*
5176 * make_group_input_target
5177 * Generate appropriate PathTarget for initial input to grouping nodes.
5178 *
5179 * If there is grouping or aggregation, the scan/join subplan cannot emit
5180 * the query's final targetlist; for example, it certainly can't emit any
5181 * aggregate function calls. This routine generates the correct target
5182 * for the scan/join subplan.
5183 *
5184 * The query target list passed from the parser already contains entries
5185 * for all ORDER BY and GROUP BY expressions, but it will not have entries
5186 * for variables used only in HAVING clauses; so we need to add those
5187 * variables to the subplan target list. Also, we flatten all expressions
5188 * except GROUP BY items into their component variables; other expressions
5189 * will be computed by the upper plan nodes rather than by the subplan.
5190 * For example, given a query like
5191 * SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
5192 * we want to pass this targetlist to the subplan:
5193 * a+b,c,d
5194 * where the a+b target will be used by the Sort/Group steps, and the
5195 * other targets will be used for computing the final results.
5196 *
5197 * 'final_target' is the query's final target list (in PathTarget form)
5198 *
5199 * The result is the PathTarget to be computed by the Paths returned from
5200 * query_planner().
5201 */
5202 static PathTarget *
make_group_input_target(PlannerInfo * root,PathTarget * final_target)5203 make_group_input_target(PlannerInfo *root, PathTarget *final_target)
5204 {
5205 Query *parse = root->parse;
5206 PathTarget *input_target;
5207 List *non_group_cols;
5208 List *non_group_vars;
5209 int i;
5210 ListCell *lc;
5211
5212 /*
5213 * We must build a target containing all grouping columns, plus any other
5214 * Vars mentioned in the query's targetlist and HAVING qual.
5215 */
5216 input_target = create_empty_pathtarget();
5217 non_group_cols = NIL;
5218
5219 i = 0;
5220 foreach(lc, final_target->exprs)
5221 {
5222 Expr *expr = (Expr *) lfirst(lc);
5223 Index sgref = get_pathtarget_sortgroupref(final_target, i);
5224
5225 if (sgref && parse->groupClause &&
5226 get_sortgroupref_clause_noerr(sgref, parse->groupClause) != NULL)
5227 {
5228 /*
5229 * It's a grouping column, so add it to the input target as-is.
5230 */
5231 add_column_to_pathtarget(input_target, expr, sgref);
5232 }
5233 else
5234 {
5235 /*
5236 * Non-grouping column, so just remember the expression for later
5237 * call to pull_var_clause.
5238 */
5239 non_group_cols = lappend(non_group_cols, expr);
5240 }
5241
5242 i++;
5243 }
5244
5245 /*
5246 * If there's a HAVING clause, we'll need the Vars it uses, too.
5247 */
5248 if (parse->havingQual)
5249 non_group_cols = lappend(non_group_cols, parse->havingQual);
5250
5251 /*
5252 * Pull out all the Vars mentioned in non-group cols (plus HAVING), and
5253 * add them to the input target if not already present. (A Var used
5254 * directly as a GROUP BY item will be present already.) Note this
5255 * includes Vars used in resjunk items, so we are covering the needs of
5256 * ORDER BY and window specifications. Vars used within Aggrefs and
5257 * WindowFuncs will be pulled out here, too.
5258 */
5259 non_group_vars = pull_var_clause((Node *) non_group_cols,
5260 PVC_RECURSE_AGGREGATES |
5261 PVC_RECURSE_WINDOWFUNCS |
5262 PVC_INCLUDE_PLACEHOLDERS);
5263 add_new_columns_to_pathtarget(input_target, non_group_vars);
5264
5265 /* clean up cruft */
5266 list_free(non_group_vars);
5267 list_free(non_group_cols);
5268
5269 /* XXX this causes some redundant cost calculation ... */
5270 return set_pathtarget_cost_width(root, input_target);
5271 }
5272
5273 /*
5274 * make_partial_grouping_target
5275 * Generate appropriate PathTarget for output of partial aggregate
5276 * (or partial grouping, if there are no aggregates) nodes.
5277 *
5278 * A partial aggregation node needs to emit all the same aggregates that
5279 * a regular aggregation node would, plus any aggregates used in HAVING;
5280 * except that the Aggref nodes should be marked as partial aggregates.
5281 *
5282 * In addition, we'd better emit any Vars and PlaceHolderVars that are
5283 * used outside of Aggrefs in the aggregation tlist and HAVING. (Presumably,
5284 * these would be Vars that are grouped by or used in grouping expressions.)
5285 *
5286 * grouping_target is the tlist to be emitted by the topmost aggregation step.
5287 * havingQual represents the HAVING clause.
5288 */
5289 static PathTarget *
make_partial_grouping_target(PlannerInfo * root,PathTarget * grouping_target,Node * havingQual)5290 make_partial_grouping_target(PlannerInfo *root,
5291 PathTarget *grouping_target,
5292 Node *havingQual)
5293 {
5294 Query *parse = root->parse;
5295 PathTarget *partial_target;
5296 List *non_group_cols;
5297 List *non_group_exprs;
5298 int i;
5299 ListCell *lc;
5300
5301 partial_target = create_empty_pathtarget();
5302 non_group_cols = NIL;
5303
5304 i = 0;
5305 foreach(lc, grouping_target->exprs)
5306 {
5307 Expr *expr = (Expr *) lfirst(lc);
5308 Index sgref = get_pathtarget_sortgroupref(grouping_target, i);
5309
5310 if (sgref && parse->groupClause &&
5311 get_sortgroupref_clause_noerr(sgref, parse->groupClause) != NULL)
5312 {
5313 /*
5314 * It's a grouping column, so add it to the partial_target as-is.
5315 * (This allows the upper agg step to repeat the grouping calcs.)
5316 */
5317 add_column_to_pathtarget(partial_target, expr, sgref);
5318 }
5319 else
5320 {
5321 /*
5322 * Non-grouping column, so just remember the expression for later
5323 * call to pull_var_clause.
5324 */
5325 non_group_cols = lappend(non_group_cols, expr);
5326 }
5327
5328 i++;
5329 }
5330
5331 /*
5332 * If there's a HAVING clause, we'll need the Vars/Aggrefs it uses, too.
5333 */
5334 if (havingQual)
5335 non_group_cols = lappend(non_group_cols, havingQual);
5336
5337 /*
5338 * Pull out all the Vars, PlaceHolderVars, and Aggrefs mentioned in
5339 * non-group cols (plus HAVING), and add them to the partial_target if not
5340 * already present. (An expression used directly as a GROUP BY item will
5341 * be present already.) Note this includes Vars used in resjunk items, so
5342 * we are covering the needs of ORDER BY and window specifications.
5343 */
5344 non_group_exprs = pull_var_clause((Node *) non_group_cols,
5345 PVC_INCLUDE_AGGREGATES |
5346 PVC_RECURSE_WINDOWFUNCS |
5347 PVC_INCLUDE_PLACEHOLDERS);
5348
5349 add_new_columns_to_pathtarget(partial_target, non_group_exprs);
5350
5351 /*
5352 * Adjust Aggrefs to put them in partial mode. At this point all Aggrefs
5353 * are at the top level of the target list, so we can just scan the list
5354 * rather than recursing through the expression trees.
5355 */
5356 foreach(lc, partial_target->exprs)
5357 {
5358 Aggref *aggref = (Aggref *) lfirst(lc);
5359
5360 if (IsA(aggref, Aggref))
5361 {
5362 Aggref *newaggref;
5363
5364 /*
5365 * We shouldn't need to copy the substructure of the Aggref node,
5366 * but flat-copy the node itself to avoid damaging other trees.
5367 */
5368 newaggref = makeNode(Aggref);
5369 memcpy(newaggref, aggref, sizeof(Aggref));
5370
5371 /* For now, assume serialization is required */
5372 mark_partial_aggref(newaggref, AGGSPLIT_INITIAL_SERIAL);
5373
5374 lfirst(lc) = newaggref;
5375 }
5376 }
5377
5378 /* clean up cruft */
5379 list_free(non_group_exprs);
5380 list_free(non_group_cols);
5381
5382 /* XXX this causes some redundant cost calculation ... */
5383 return set_pathtarget_cost_width(root, partial_target);
5384 }
5385
5386 /*
5387 * mark_partial_aggref
5388 * Adjust an Aggref to make it represent a partial-aggregation step.
5389 *
5390 * The Aggref node is modified in-place; caller must do any copying required.
5391 */
5392 void
mark_partial_aggref(Aggref * agg,AggSplit aggsplit)5393 mark_partial_aggref(Aggref *agg, AggSplit aggsplit)
5394 {
5395 /* aggtranstype should be computed by this point */
5396 Assert(OidIsValid(agg->aggtranstype));
5397 /* ... but aggsplit should still be as the parser left it */
5398 Assert(agg->aggsplit == AGGSPLIT_SIMPLE);
5399
5400 /* Mark the Aggref with the intended partial-aggregation mode */
5401 agg->aggsplit = aggsplit;
5402
5403 /*
5404 * Adjust result type if needed. Normally, a partial aggregate returns
5405 * the aggregate's transition type; but if that's INTERNAL and we're
5406 * serializing, it returns BYTEA instead.
5407 */
5408 if (DO_AGGSPLIT_SKIPFINAL(aggsplit))
5409 {
5410 if (agg->aggtranstype == INTERNALOID && DO_AGGSPLIT_SERIALIZE(aggsplit))
5411 agg->aggtype = BYTEAOID;
5412 else
5413 agg->aggtype = agg->aggtranstype;
5414 }
5415 }
5416
5417 /*
5418 * postprocess_setop_tlist
5419 * Fix up targetlist returned by plan_set_operations().
5420 *
5421 * We need to transpose sort key info from the orig_tlist into new_tlist.
5422 * NOTE: this would not be good enough if we supported resjunk sort keys
5423 * for results of set operations --- then, we'd need to project a whole
5424 * new tlist to evaluate the resjunk columns. For now, just ereport if we
5425 * find any resjunk columns in orig_tlist.
5426 */
5427 static List *
postprocess_setop_tlist(List * new_tlist,List * orig_tlist)5428 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
5429 {
5430 ListCell *l;
5431 ListCell *orig_tlist_item = list_head(orig_tlist);
5432
5433 foreach(l, new_tlist)
5434 {
5435 TargetEntry *new_tle = lfirst_node(TargetEntry, l);
5436 TargetEntry *orig_tle;
5437
5438 /* ignore resjunk columns in setop result */
5439 if (new_tle->resjunk)
5440 continue;
5441
5442 Assert(orig_tlist_item != NULL);
5443 orig_tle = lfirst_node(TargetEntry, orig_tlist_item);
5444 orig_tlist_item = lnext(orig_tlist, orig_tlist_item);
5445 if (orig_tle->resjunk) /* should not happen */
5446 elog(ERROR, "resjunk output columns are not implemented");
5447 Assert(new_tle->resno == orig_tle->resno);
5448 new_tle->ressortgroupref = orig_tle->ressortgroupref;
5449 }
5450 if (orig_tlist_item != NULL)
5451 elog(ERROR, "resjunk output columns are not implemented");
5452 return new_tlist;
5453 }
5454
5455 /*
5456 * select_active_windows
5457 * Create a list of the "active" window clauses (ie, those referenced
5458 * by non-deleted WindowFuncs) in the order they are to be executed.
5459 */
5460 static List *
select_active_windows(PlannerInfo * root,WindowFuncLists * wflists)5461 select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
5462 {
5463 List *windowClause = root->parse->windowClause;
5464 List *result = NIL;
5465 ListCell *lc;
5466 int nActive = 0;
5467 WindowClauseSortData *actives = palloc(sizeof(WindowClauseSortData)
5468 * list_length(windowClause));
5469
5470 /* First, construct an array of the active windows */
5471 foreach(lc, windowClause)
5472 {
5473 WindowClause *wc = lfirst_node(WindowClause, lc);
5474
5475 /* It's only active if wflists shows some related WindowFuncs */
5476 Assert(wc->winref <= wflists->maxWinRef);
5477 if (wflists->windowFuncs[wc->winref] == NIL)
5478 continue;
5479
5480 actives[nActive].wc = wc; /* original clause */
5481
5482 /*
5483 * For sorting, we want the list of partition keys followed by the
5484 * list of sort keys. But pathkeys construction will remove duplicates
5485 * between the two, so we can as well (even though we can't detect all
5486 * of the duplicates, since some may come from ECs - that might mean
5487 * we miss optimization chances here). We must, however, ensure that
5488 * the order of entries is preserved with respect to the ones we do
5489 * keep.
5490 *
5491 * partitionClause and orderClause had their own duplicates removed in
5492 * parse analysis, so we're only concerned here with removing
5493 * orderClause entries that also appear in partitionClause.
5494 */
5495 actives[nActive].uniqueOrder =
5496 list_concat_unique(list_copy(wc->partitionClause),
5497 wc->orderClause);
5498 nActive++;
5499 }
5500
5501 /*
5502 * Sort active windows by their partitioning/ordering clauses, ignoring
5503 * any framing clauses, so that the windows that need the same sorting are
5504 * adjacent in the list. When we come to generate paths, this will avoid
5505 * inserting additional Sort nodes.
5506 *
5507 * This is how we implement a specific requirement from the SQL standard,
5508 * which says that when two or more windows are order-equivalent (i.e.
5509 * have matching partition and order clauses, even if their names or
5510 * framing clauses differ), then all peer rows must be presented in the
5511 * same order in all of them. If we allowed multiple sort nodes for such
5512 * cases, we'd risk having the peer rows end up in different orders in
5513 * equivalent windows due to sort instability. (See General Rule 4 of
5514 * <window clause> in SQL2008 - SQL2016.)
5515 *
5516 * Additionally, if the entire list of clauses of one window is a prefix
5517 * of another, put first the window with stronger sorting requirements.
5518 * This way we will first sort for stronger window, and won't have to sort
5519 * again for the weaker one.
5520 */
5521 qsort(actives, nActive, sizeof(WindowClauseSortData), common_prefix_cmp);
5522
5523 /* build ordered list of the original WindowClause nodes */
5524 for (int i = 0; i < nActive; i++)
5525 result = lappend(result, actives[i].wc);
5526
5527 pfree(actives);
5528
5529 return result;
5530 }
5531
5532 /*
5533 * common_prefix_cmp
5534 * QSort comparison function for WindowClauseSortData
5535 *
5536 * Sort the windows by the required sorting clauses. First, compare the sort
5537 * clauses themselves. Second, if one window's clauses are a prefix of another
5538 * one's clauses, put the window with more sort clauses first.
5539 */
5540 static int
common_prefix_cmp(const void * a,const void * b)5541 common_prefix_cmp(const void *a, const void *b)
5542 {
5543 const WindowClauseSortData *wcsa = a;
5544 const WindowClauseSortData *wcsb = b;
5545 ListCell *item_a;
5546 ListCell *item_b;
5547
5548 forboth(item_a, wcsa->uniqueOrder, item_b, wcsb->uniqueOrder)
5549 {
5550 SortGroupClause *sca = lfirst_node(SortGroupClause, item_a);
5551 SortGroupClause *scb = lfirst_node(SortGroupClause, item_b);
5552
5553 if (sca->tleSortGroupRef > scb->tleSortGroupRef)
5554 return -1;
5555 else if (sca->tleSortGroupRef < scb->tleSortGroupRef)
5556 return 1;
5557 else if (sca->sortop > scb->sortop)
5558 return -1;
5559 else if (sca->sortop < scb->sortop)
5560 return 1;
5561 else if (sca->nulls_first && !scb->nulls_first)
5562 return -1;
5563 else if (!sca->nulls_first && scb->nulls_first)
5564 return 1;
5565 /* no need to compare eqop, since it is fully determined by sortop */
5566 }
5567
5568 if (list_length(wcsa->uniqueOrder) > list_length(wcsb->uniqueOrder))
5569 return -1;
5570 else if (list_length(wcsa->uniqueOrder) < list_length(wcsb->uniqueOrder))
5571 return 1;
5572
5573 return 0;
5574 }
5575
5576 /*
5577 * make_window_input_target
5578 * Generate appropriate PathTarget for initial input to WindowAgg nodes.
5579 *
5580 * When the query has window functions, this function computes the desired
5581 * target to be computed by the node just below the first WindowAgg.
5582 * This tlist must contain all values needed to evaluate the window functions,
5583 * compute the final target list, and perform any required final sort step.
5584 * If multiple WindowAggs are needed, each intermediate one adds its window
5585 * function results onto this base tlist; only the topmost WindowAgg computes
5586 * the actual desired target list.
5587 *
5588 * This function is much like make_group_input_target, though not quite enough
5589 * like it to share code. As in that function, we flatten most expressions
5590 * into their component variables. But we do not want to flatten window
5591 * PARTITION BY/ORDER BY clauses, since that might result in multiple
5592 * evaluations of them, which would be bad (possibly even resulting in
5593 * inconsistent answers, if they contain volatile functions).
5594 * Also, we must not flatten GROUP BY clauses that were left unflattened by
5595 * make_group_input_target, because we may no longer have access to the
5596 * individual Vars in them.
5597 *
5598 * Another key difference from make_group_input_target is that we don't
5599 * flatten Aggref expressions, since those are to be computed below the
5600 * window functions and just referenced like Vars above that.
5601 *
5602 * 'final_target' is the query's final target list (in PathTarget form)
5603 * 'activeWindows' is the list of active windows previously identified by
5604 * select_active_windows.
5605 *
5606 * The result is the PathTarget to be computed by the plan node immediately
5607 * below the first WindowAgg node.
5608 */
5609 static PathTarget *
make_window_input_target(PlannerInfo * root,PathTarget * final_target,List * activeWindows)5610 make_window_input_target(PlannerInfo *root,
5611 PathTarget *final_target,
5612 List *activeWindows)
5613 {
5614 Query *parse = root->parse;
5615 PathTarget *input_target;
5616 Bitmapset *sgrefs;
5617 List *flattenable_cols;
5618 List *flattenable_vars;
5619 int i;
5620 ListCell *lc;
5621
5622 Assert(parse->hasWindowFuncs);
5623
5624 /*
5625 * Collect the sortgroupref numbers of window PARTITION/ORDER BY clauses
5626 * into a bitmapset for convenient reference below.
5627 */
5628 sgrefs = NULL;
5629 foreach(lc, activeWindows)
5630 {
5631 WindowClause *wc = lfirst_node(WindowClause, lc);
5632 ListCell *lc2;
5633
5634 foreach(lc2, wc->partitionClause)
5635 {
5636 SortGroupClause *sortcl = lfirst_node(SortGroupClause, lc2);
5637
5638 sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
5639 }
5640 foreach(lc2, wc->orderClause)
5641 {
5642 SortGroupClause *sortcl = lfirst_node(SortGroupClause, lc2);
5643
5644 sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
5645 }
5646 }
5647
5648 /* Add in sortgroupref numbers of GROUP BY clauses, too */
5649 foreach(lc, parse->groupClause)
5650 {
5651 SortGroupClause *grpcl = lfirst_node(SortGroupClause, lc);
5652
5653 sgrefs = bms_add_member(sgrefs, grpcl->tleSortGroupRef);
5654 }
5655
5656 /*
5657 * Construct a target containing all the non-flattenable targetlist items,
5658 * and save aside the others for a moment.
5659 */
5660 input_target = create_empty_pathtarget();
5661 flattenable_cols = NIL;
5662
5663 i = 0;
5664 foreach(lc, final_target->exprs)
5665 {
5666 Expr *expr = (Expr *) lfirst(lc);
5667 Index sgref = get_pathtarget_sortgroupref(final_target, i);
5668
5669 /*
5670 * Don't want to deconstruct window clauses or GROUP BY items. (Note
5671 * that such items can't contain window functions, so it's okay to
5672 * compute them below the WindowAgg nodes.)
5673 */
5674 if (sgref != 0 && bms_is_member(sgref, sgrefs))
5675 {
5676 /*
5677 * Don't want to deconstruct this value, so add it to the input
5678 * target as-is.
5679 */
5680 add_column_to_pathtarget(input_target, expr, sgref);
5681 }
5682 else
5683 {
5684 /*
5685 * Column is to be flattened, so just remember the expression for
5686 * later call to pull_var_clause.
5687 */
5688 flattenable_cols = lappend(flattenable_cols, expr);
5689 }
5690
5691 i++;
5692 }
5693
5694 /*
5695 * Pull out all the Vars and Aggrefs mentioned in flattenable columns, and
5696 * add them to the input target if not already present. (Some might be
5697 * there already because they're used directly as window/group clauses.)
5698 *
5699 * Note: it's essential to use PVC_INCLUDE_AGGREGATES here, so that any
5700 * Aggrefs are placed in the Agg node's tlist and not left to be computed
5701 * at higher levels. On the other hand, we should recurse into
5702 * WindowFuncs to make sure their input expressions are available.
5703 */
5704 flattenable_vars = pull_var_clause((Node *) flattenable_cols,
5705 PVC_INCLUDE_AGGREGATES |
5706 PVC_RECURSE_WINDOWFUNCS |
5707 PVC_INCLUDE_PLACEHOLDERS);
5708 add_new_columns_to_pathtarget(input_target, flattenable_vars);
5709
5710 /* clean up cruft */
5711 list_free(flattenable_vars);
5712 list_free(flattenable_cols);
5713
5714 /* XXX this causes some redundant cost calculation ... */
5715 return set_pathtarget_cost_width(root, input_target);
5716 }
5717
5718 /*
5719 * make_pathkeys_for_window
5720 * Create a pathkeys list describing the required input ordering
5721 * for the given WindowClause.
5722 *
5723 * The required ordering is first the PARTITION keys, then the ORDER keys.
5724 * In the future we might try to implement windowing using hashing, in which
5725 * case the ordering could be relaxed, but for now we always sort.
5726 */
5727 static List *
make_pathkeys_for_window(PlannerInfo * root,WindowClause * wc,List * tlist)5728 make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
5729 List *tlist)
5730 {
5731 List *window_pathkeys;
5732 List *window_sortclauses;
5733
5734 /* Throw error if can't sort */
5735 if (!grouping_is_sortable(wc->partitionClause))
5736 ereport(ERROR,
5737 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5738 errmsg("could not implement window PARTITION BY"),
5739 errdetail("Window partitioning columns must be of sortable datatypes.")));
5740 if (!grouping_is_sortable(wc->orderClause))
5741 ereport(ERROR,
5742 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5743 errmsg("could not implement window ORDER BY"),
5744 errdetail("Window ordering columns must be of sortable datatypes.")));
5745
5746 /* Okay, make the combined pathkeys */
5747 window_sortclauses = list_concat_copy(wc->partitionClause, wc->orderClause);
5748 window_pathkeys = make_pathkeys_for_sortclauses(root,
5749 window_sortclauses,
5750 tlist);
5751 list_free(window_sortclauses);
5752 return window_pathkeys;
5753 }
5754
5755 /*
5756 * make_sort_input_target
5757 * Generate appropriate PathTarget for initial input to Sort step.
5758 *
5759 * If the query has ORDER BY, this function chooses the target to be computed
5760 * by the node just below the Sort (and DISTINCT, if any, since Unique can't
5761 * project) steps. This might or might not be identical to the query's final
5762 * output target.
5763 *
5764 * The main argument for keeping the sort-input tlist the same as the final
5765 * is that we avoid a separate projection node (which will be needed if
5766 * they're different, because Sort can't project). However, there are also
5767 * advantages to postponing tlist evaluation till after the Sort: it ensures
5768 * a consistent order of evaluation for any volatile functions in the tlist,
5769 * and if there's also a LIMIT, we can stop the query without ever computing
5770 * tlist functions for later rows, which is beneficial for both volatile and
5771 * expensive functions.
5772 *
5773 * Our current policy is to postpone volatile expressions till after the sort
5774 * unconditionally (assuming that that's possible, ie they are in plain tlist
5775 * columns and not ORDER BY/GROUP BY/DISTINCT columns). We also prefer to
5776 * postpone set-returning expressions, because running them beforehand would
5777 * bloat the sort dataset, and because it might cause unexpected output order
5778 * if the sort isn't stable. However there's a constraint on that: all SRFs
5779 * in the tlist should be evaluated at the same plan step, so that they can
5780 * run in sync in nodeProjectSet. So if any SRFs are in sort columns, we
5781 * mustn't postpone any SRFs. (Note that in principle that policy should
5782 * probably get applied to the group/window input targetlists too, but we
5783 * have not done that historically.) Lastly, expensive expressions are
5784 * postponed if there is a LIMIT, or if root->tuple_fraction shows that
5785 * partial evaluation of the query is possible (if neither is true, we expect
5786 * to have to evaluate the expressions for every row anyway), or if there are
5787 * any volatile or set-returning expressions (since once we've put in a
5788 * projection at all, it won't cost any more to postpone more stuff).
5789 *
5790 * Another issue that could potentially be considered here is that
5791 * evaluating tlist expressions could result in data that's either wider
5792 * or narrower than the input Vars, thus changing the volume of data that
5793 * has to go through the Sort. However, we usually have only a very bad
5794 * idea of the output width of any expression more complex than a Var,
5795 * so for now it seems too risky to try to optimize on that basis.
5796 *
5797 * Note that if we do produce a modified sort-input target, and then the
5798 * query ends up not using an explicit Sort, no particular harm is done:
5799 * we'll initially use the modified target for the preceding path nodes,
5800 * but then change them to the final target with apply_projection_to_path.
5801 * Moreover, in such a case the guarantees about evaluation order of
5802 * volatile functions still hold, since the rows are sorted already.
5803 *
5804 * This function has some things in common with make_group_input_target and
5805 * make_window_input_target, though the detailed rules for what to do are
5806 * different. We never flatten/postpone any grouping or ordering columns;
5807 * those are needed before the sort. If we do flatten a particular
5808 * expression, we leave Aggref and WindowFunc nodes alone, since those were
5809 * computed earlier.
5810 *
5811 * 'final_target' is the query's final target list (in PathTarget form)
5812 * 'have_postponed_srfs' is an output argument, see below
5813 *
5814 * The result is the PathTarget to be computed by the plan node immediately
5815 * below the Sort step (and the Distinct step, if any). This will be
5816 * exactly final_target if we decide a projection step wouldn't be helpful.
5817 *
5818 * In addition, *have_postponed_srfs is set to true if we choose to postpone
5819 * any set-returning functions to after the Sort.
5820 */
5821 static PathTarget *
make_sort_input_target(PlannerInfo * root,PathTarget * final_target,bool * have_postponed_srfs)5822 make_sort_input_target(PlannerInfo *root,
5823 PathTarget *final_target,
5824 bool *have_postponed_srfs)
5825 {
5826 Query *parse = root->parse;
5827 PathTarget *input_target;
5828 int ncols;
5829 bool *col_is_srf;
5830 bool *postpone_col;
5831 bool have_srf;
5832 bool have_volatile;
5833 bool have_expensive;
5834 bool have_srf_sortcols;
5835 bool postpone_srfs;
5836 List *postponable_cols;
5837 List *postponable_vars;
5838 int i;
5839 ListCell *lc;
5840
5841 /* Shouldn't get here unless query has ORDER BY */
5842 Assert(parse->sortClause);
5843
5844 *have_postponed_srfs = false; /* default result */
5845
5846 /* Inspect tlist and collect per-column information */
5847 ncols = list_length(final_target->exprs);
5848 col_is_srf = (bool *) palloc0(ncols * sizeof(bool));
5849 postpone_col = (bool *) palloc0(ncols * sizeof(bool));
5850 have_srf = have_volatile = have_expensive = have_srf_sortcols = false;
5851
5852 i = 0;
5853 foreach(lc, final_target->exprs)
5854 {
5855 Expr *expr = (Expr *) lfirst(lc);
5856
5857 /*
5858 * If the column has a sortgroupref, assume it has to be evaluated
5859 * before sorting. Generally such columns would be ORDER BY, GROUP
5860 * BY, etc targets. One exception is columns that were removed from
5861 * GROUP BY by remove_useless_groupby_columns() ... but those would
5862 * only be Vars anyway. There don't seem to be any cases where it
5863 * would be worth the trouble to double-check.
5864 */
5865 if (get_pathtarget_sortgroupref(final_target, i) == 0)
5866 {
5867 /*
5868 * Check for SRF or volatile functions. Check the SRF case first
5869 * because we must know whether we have any postponed SRFs.
5870 */
5871 if (parse->hasTargetSRFs &&
5872 expression_returns_set((Node *) expr))
5873 {
5874 /* We'll decide below whether these are postponable */
5875 col_is_srf[i] = true;
5876 have_srf = true;
5877 }
5878 else if (contain_volatile_functions((Node *) expr))
5879 {
5880 /* Unconditionally postpone */
5881 postpone_col[i] = true;
5882 have_volatile = true;
5883 }
5884 else
5885 {
5886 /*
5887 * Else check the cost. XXX it's annoying to have to do this
5888 * when set_pathtarget_cost_width() just did it. Refactor to
5889 * allow sharing the work?
5890 */
5891 QualCost cost;
5892
5893 cost_qual_eval_node(&cost, (Node *) expr, root);
5894
5895 /*
5896 * We arbitrarily define "expensive" as "more than 10X
5897 * cpu_operator_cost". Note this will take in any PL function
5898 * with default cost.
5899 */
5900 if (cost.per_tuple > 10 * cpu_operator_cost)
5901 {
5902 postpone_col[i] = true;
5903 have_expensive = true;
5904 }
5905 }
5906 }
5907 else
5908 {
5909 /* For sortgroupref cols, just check if any contain SRFs */
5910 if (!have_srf_sortcols &&
5911 parse->hasTargetSRFs &&
5912 expression_returns_set((Node *) expr))
5913 have_srf_sortcols = true;
5914 }
5915
5916 i++;
5917 }
5918
5919 /*
5920 * We can postpone SRFs if we have some but none are in sortgroupref cols.
5921 */
5922 postpone_srfs = (have_srf && !have_srf_sortcols);
5923
5924 /*
5925 * If we don't need a post-sort projection, just return final_target.
5926 */
5927 if (!(postpone_srfs || have_volatile ||
5928 (have_expensive &&
5929 (parse->limitCount || root->tuple_fraction > 0))))
5930 return final_target;
5931
5932 /*
5933 * Report whether the post-sort projection will contain set-returning
5934 * functions. This is important because it affects whether the Sort can
5935 * rely on the query's LIMIT (if any) to bound the number of rows it needs
5936 * to return.
5937 */
5938 *have_postponed_srfs = postpone_srfs;
5939
5940 /*
5941 * Construct the sort-input target, taking all non-postponable columns and
5942 * then adding Vars, PlaceHolderVars, Aggrefs, and WindowFuncs found in
5943 * the postponable ones.
5944 */
5945 input_target = create_empty_pathtarget();
5946 postponable_cols = NIL;
5947
5948 i = 0;
5949 foreach(lc, final_target->exprs)
5950 {
5951 Expr *expr = (Expr *) lfirst(lc);
5952
5953 if (postpone_col[i] || (postpone_srfs && col_is_srf[i]))
5954 postponable_cols = lappend(postponable_cols, expr);
5955 else
5956 add_column_to_pathtarget(input_target, expr,
5957 get_pathtarget_sortgroupref(final_target, i));
5958
5959 i++;
5960 }
5961
5962 /*
5963 * Pull out all the Vars, Aggrefs, and WindowFuncs mentioned in
5964 * postponable columns, and add them to the sort-input target if not
5965 * already present. (Some might be there already.) We mustn't
5966 * deconstruct Aggrefs or WindowFuncs here, since the projection node
5967 * would be unable to recompute them.
5968 */
5969 postponable_vars = pull_var_clause((Node *) postponable_cols,
5970 PVC_INCLUDE_AGGREGATES |
5971 PVC_INCLUDE_WINDOWFUNCS |
5972 PVC_INCLUDE_PLACEHOLDERS);
5973 add_new_columns_to_pathtarget(input_target, postponable_vars);
5974
5975 /* clean up cruft */
5976 list_free(postponable_vars);
5977 list_free(postponable_cols);
5978
5979 /* XXX this represents even more redundant cost calculation ... */
5980 return set_pathtarget_cost_width(root, input_target);
5981 }
5982
5983 /*
5984 * get_cheapest_fractional_path
5985 * Find the cheapest path for retrieving a specified fraction of all
5986 * the tuples expected to be returned by the given relation.
5987 *
5988 * We interpret tuple_fraction the same way as grouping_planner.
5989 *
5990 * We assume set_cheapest() has been run on the given rel.
5991 */
5992 Path *
get_cheapest_fractional_path(RelOptInfo * rel,double tuple_fraction)5993 get_cheapest_fractional_path(RelOptInfo *rel, double tuple_fraction)
5994 {
5995 Path *best_path = rel->cheapest_total_path;
5996 ListCell *l;
5997
5998 /* If all tuples will be retrieved, just return the cheapest-total path */
5999 if (tuple_fraction <= 0.0)
6000 return best_path;
6001
6002 /* Convert absolute # of tuples to a fraction; no need to clamp to 0..1 */
6003 if (tuple_fraction >= 1.0 && best_path->rows > 0)
6004 tuple_fraction /= best_path->rows;
6005
6006 foreach(l, rel->pathlist)
6007 {
6008 Path *path = (Path *) lfirst(l);
6009
6010 if (path == rel->cheapest_total_path ||
6011 compare_fractional_path_costs(best_path, path, tuple_fraction) <= 0)
6012 continue;
6013
6014 best_path = path;
6015 }
6016
6017 return best_path;
6018 }
6019
6020 /*
6021 * adjust_paths_for_srfs
6022 * Fix up the Paths of the given upperrel to handle tSRFs properly.
6023 *
6024 * The executor can only handle set-returning functions that appear at the
6025 * top level of the targetlist of a ProjectSet plan node. If we have any SRFs
6026 * that are not at top level, we need to split up the evaluation into multiple
6027 * plan levels in which each level satisfies this constraint. This function
6028 * modifies each Path of an upperrel that (might) compute any SRFs in its
6029 * output tlist to insert appropriate projection steps.
6030 *
6031 * The given targets and targets_contain_srfs lists are from
6032 * split_pathtarget_at_srfs(). We assume the existing Paths emit the first
6033 * target in targets.
6034 */
6035 static void
adjust_paths_for_srfs(PlannerInfo * root,RelOptInfo * rel,List * targets,List * targets_contain_srfs)6036 adjust_paths_for_srfs(PlannerInfo *root, RelOptInfo *rel,
6037 List *targets, List *targets_contain_srfs)
6038 {
6039 ListCell *lc;
6040
6041 Assert(list_length(targets) == list_length(targets_contain_srfs));
6042 Assert(!linitial_int(targets_contain_srfs));
6043
6044 /* If no SRFs appear at this plan level, nothing to do */
6045 if (list_length(targets) == 1)
6046 return;
6047
6048 /*
6049 * Stack SRF-evaluation nodes atop each path for the rel.
6050 *
6051 * In principle we should re-run set_cheapest() here to identify the
6052 * cheapest path, but it seems unlikely that adding the same tlist eval
6053 * costs to all the paths would change that, so we don't bother. Instead,
6054 * just assume that the cheapest-startup and cheapest-total paths remain
6055 * so. (There should be no parameterized paths anymore, so we needn't
6056 * worry about updating cheapest_parameterized_paths.)
6057 */
6058 foreach(lc, rel->pathlist)
6059 {
6060 Path *subpath = (Path *) lfirst(lc);
6061 Path *newpath = subpath;
6062 ListCell *lc1,
6063 *lc2;
6064
6065 Assert(subpath->param_info == NULL);
6066 forboth(lc1, targets, lc2, targets_contain_srfs)
6067 {
6068 PathTarget *thistarget = lfirst_node(PathTarget, lc1);
6069 bool contains_srfs = (bool) lfirst_int(lc2);
6070
6071 /* If this level doesn't contain SRFs, do regular projection */
6072 if (contains_srfs)
6073 newpath = (Path *) create_set_projection_path(root,
6074 rel,
6075 newpath,
6076 thistarget);
6077 else
6078 newpath = (Path *) apply_projection_to_path(root,
6079 rel,
6080 newpath,
6081 thistarget);
6082 }
6083 lfirst(lc) = newpath;
6084 if (subpath == rel->cheapest_startup_path)
6085 rel->cheapest_startup_path = newpath;
6086 if (subpath == rel->cheapest_total_path)
6087 rel->cheapest_total_path = newpath;
6088 }
6089
6090 /* Likewise for partial paths, if any */
6091 foreach(lc, rel->partial_pathlist)
6092 {
6093 Path *subpath = (Path *) lfirst(lc);
6094 Path *newpath = subpath;
6095 ListCell *lc1,
6096 *lc2;
6097
6098 Assert(subpath->param_info == NULL);
6099 forboth(lc1, targets, lc2, targets_contain_srfs)
6100 {
6101 PathTarget *thistarget = lfirst_node(PathTarget, lc1);
6102 bool contains_srfs = (bool) lfirst_int(lc2);
6103
6104 /* If this level doesn't contain SRFs, do regular projection */
6105 if (contains_srfs)
6106 newpath = (Path *) create_set_projection_path(root,
6107 rel,
6108 newpath,
6109 thistarget);
6110 else
6111 {
6112 /* avoid apply_projection_to_path, in case of multiple refs */
6113 newpath = (Path *) create_projection_path(root,
6114 rel,
6115 newpath,
6116 thistarget);
6117 }
6118 }
6119 lfirst(lc) = newpath;
6120 }
6121 }
6122
6123 /*
6124 * expression_planner
6125 * Perform planner's transformations on a standalone expression.
6126 *
6127 * Various utility commands need to evaluate expressions that are not part
6128 * of a plannable query. They can do so using the executor's regular
6129 * expression-execution machinery, but first the expression has to be fed
6130 * through here to transform it from parser output to something executable.
6131 *
6132 * Currently, we disallow sublinks in standalone expressions, so there's no
6133 * real "planning" involved here. (That might not always be true though.)
6134 * What we must do is run eval_const_expressions to ensure that any function
6135 * calls are converted to positional notation and function default arguments
6136 * get inserted. The fact that constant subexpressions get simplified is a
6137 * side-effect that is useful when the expression will get evaluated more than
6138 * once. Also, we must fix operator function IDs.
6139 *
6140 * This does not return any information about dependencies of the expression.
6141 * Hence callers should use the results only for the duration of the current
6142 * query. Callers that would like to cache the results for longer should use
6143 * expression_planner_with_deps, probably via the plancache.
6144 *
6145 * Note: this must not make any damaging changes to the passed-in expression
6146 * tree. (It would actually be okay to apply fix_opfuncids to it, but since
6147 * we first do an expression_tree_mutator-based walk, what is returned will
6148 * be a new node tree.) The result is constructed in the current memory
6149 * context; beware that this can leak a lot of additional stuff there, too.
6150 */
6151 Expr *
expression_planner(Expr * expr)6152 expression_planner(Expr *expr)
6153 {
6154 Node *result;
6155
6156 /*
6157 * Convert named-argument function calls, insert default arguments and
6158 * simplify constant subexprs
6159 */
6160 result = eval_const_expressions(NULL, (Node *) expr);
6161
6162 /* Fill in opfuncid values if missing */
6163 fix_opfuncids(result);
6164
6165 return (Expr *) result;
6166 }
6167
6168 /*
6169 * expression_planner_with_deps
6170 * Perform planner's transformations on a standalone expression,
6171 * returning expression dependency information along with the result.
6172 *
6173 * This is identical to expression_planner() except that it also returns
6174 * information about possible dependencies of the expression, ie identities of
6175 * objects whose definitions affect the result. As in a PlannedStmt, these
6176 * are expressed as a list of relation Oids and a list of PlanInvalItems.
6177 */
6178 Expr *
expression_planner_with_deps(Expr * expr,List ** relationOids,List ** invalItems)6179 expression_planner_with_deps(Expr *expr,
6180 List **relationOids,
6181 List **invalItems)
6182 {
6183 Node *result;
6184 PlannerGlobal glob;
6185 PlannerInfo root;
6186
6187 /* Make up dummy planner state so we can use setrefs machinery */
6188 MemSet(&glob, 0, sizeof(glob));
6189 glob.type = T_PlannerGlobal;
6190 glob.relationOids = NIL;
6191 glob.invalItems = NIL;
6192
6193 MemSet(&root, 0, sizeof(root));
6194 root.type = T_PlannerInfo;
6195 root.glob = &glob;
6196
6197 /*
6198 * Convert named-argument function calls, insert default arguments and
6199 * simplify constant subexprs. Collect identities of inlined functions
6200 * and elided domains, too.
6201 */
6202 result = eval_const_expressions(&root, (Node *) expr);
6203
6204 /* Fill in opfuncid values if missing */
6205 fix_opfuncids(result);
6206
6207 /*
6208 * Now walk the finished expression to find anything else we ought to
6209 * record as an expression dependency.
6210 */
6211 (void) extract_query_dependencies_walker(result, &root);
6212
6213 *relationOids = glob.relationOids;
6214 *invalItems = glob.invalItems;
6215
6216 return (Expr *) result;
6217 }
6218
6219
6220 /*
6221 * plan_cluster_use_sort
6222 * Use the planner to decide how CLUSTER should implement sorting
6223 *
6224 * tableOid is the OID of a table to be clustered on its index indexOid
6225 * (which is already known to be a btree index). Decide whether it's
6226 * cheaper to do an indexscan or a seqscan-plus-sort to execute the CLUSTER.
6227 * Return true to use sorting, false to use an indexscan.
6228 *
6229 * Note: caller had better already hold some type of lock on the table.
6230 */
6231 bool
plan_cluster_use_sort(Oid tableOid,Oid indexOid)6232 plan_cluster_use_sort(Oid tableOid, Oid indexOid)
6233 {
6234 PlannerInfo *root;
6235 Query *query;
6236 PlannerGlobal *glob;
6237 RangeTblEntry *rte;
6238 RelOptInfo *rel;
6239 IndexOptInfo *indexInfo;
6240 QualCost indexExprCost;
6241 Cost comparisonCost;
6242 Path *seqScanPath;
6243 Path seqScanAndSortPath;
6244 IndexPath *indexScanPath;
6245 ListCell *lc;
6246
6247 /* We can short-circuit the cost comparison if indexscans are disabled */
6248 if (!enable_indexscan)
6249 return true; /* use sort */
6250
6251 /* Set up mostly-dummy planner state */
6252 query = makeNode(Query);
6253 query->commandType = CMD_SELECT;
6254
6255 glob = makeNode(PlannerGlobal);
6256
6257 root = makeNode(PlannerInfo);
6258 root->parse = query;
6259 root->glob = glob;
6260 root->query_level = 1;
6261 root->planner_cxt = CurrentMemoryContext;
6262 root->wt_param_id = -1;
6263
6264 /* Build a minimal RTE for the rel */
6265 rte = makeNode(RangeTblEntry);
6266 rte->rtekind = RTE_RELATION;
6267 rte->relid = tableOid;
6268 rte->relkind = RELKIND_RELATION; /* Don't be too picky. */
6269 rte->rellockmode = AccessShareLock;
6270 rte->lateral = false;
6271 rte->inh = false;
6272 rte->inFromCl = true;
6273 query->rtable = list_make1(rte);
6274
6275 /* Set up RTE/RelOptInfo arrays */
6276 setup_simple_rel_arrays(root);
6277
6278 /* Build RelOptInfo */
6279 rel = build_simple_rel(root, 1, NULL);
6280
6281 /* Locate IndexOptInfo for the target index */
6282 indexInfo = NULL;
6283 foreach(lc, rel->indexlist)
6284 {
6285 indexInfo = lfirst_node(IndexOptInfo, lc);
6286 if (indexInfo->indexoid == indexOid)
6287 break;
6288 }
6289
6290 /*
6291 * It's possible that get_relation_info did not generate an IndexOptInfo
6292 * for the desired index; this could happen if it's not yet reached its
6293 * indcheckxmin usability horizon, or if it's a system index and we're
6294 * ignoring system indexes. In such cases we should tell CLUSTER to not
6295 * trust the index contents but use seqscan-and-sort.
6296 */
6297 if (lc == NULL) /* not in the list? */
6298 return true; /* use sort */
6299
6300 /*
6301 * Rather than doing all the pushups that would be needed to use
6302 * set_baserel_size_estimates, just do a quick hack for rows and width.
6303 */
6304 rel->rows = rel->tuples;
6305 rel->reltarget->width = get_relation_data_width(tableOid, NULL);
6306
6307 root->total_table_pages = rel->pages;
6308
6309 /*
6310 * Determine eval cost of the index expressions, if any. We need to
6311 * charge twice that amount for each tuple comparison that happens during
6312 * the sort, since tuplesort.c will have to re-evaluate the index
6313 * expressions each time. (XXX that's pretty inefficient...)
6314 */
6315 cost_qual_eval(&indexExprCost, indexInfo->indexprs, root);
6316 comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple);
6317
6318 /* Estimate the cost of seq scan + sort */
6319 seqScanPath = create_seqscan_path(root, rel, NULL, 0);
6320 cost_sort(&seqScanAndSortPath, root, NIL,
6321 seqScanPath->total_cost, rel->tuples, rel->reltarget->width,
6322 comparisonCost, maintenance_work_mem, -1.0);
6323
6324 /* Estimate the cost of index scan */
6325 indexScanPath = create_index_path(root, indexInfo,
6326 NIL, NIL, NIL, NIL,
6327 ForwardScanDirection, false,
6328 NULL, 1.0, false);
6329
6330 return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
6331 }
6332
6333 /*
6334 * plan_create_index_workers
6335 * Use the planner to decide how many parallel worker processes
6336 * CREATE INDEX should request for use
6337 *
6338 * tableOid is the table on which the index is to be built. indexOid is the
6339 * OID of an index to be created or reindexed (which must be a btree index).
6340 *
6341 * Return value is the number of parallel worker processes to request. It
6342 * may be unsafe to proceed if this is 0. Note that this does not include the
6343 * leader participating as a worker (value is always a number of parallel
6344 * worker processes).
6345 *
6346 * Note: caller had better already hold some type of lock on the table and
6347 * index.
6348 */
6349 int
plan_create_index_workers(Oid tableOid,Oid indexOid)6350 plan_create_index_workers(Oid tableOid, Oid indexOid)
6351 {
6352 PlannerInfo *root;
6353 Query *query;
6354 PlannerGlobal *glob;
6355 RangeTblEntry *rte;
6356 Relation heap;
6357 Relation index;
6358 RelOptInfo *rel;
6359 int parallel_workers;
6360 BlockNumber heap_blocks;
6361 double reltuples;
6362 double allvisfrac;
6363
6364 /*
6365 * We don't allow performing parallel operation in standalone backend or
6366 * when parallelism is disabled.
6367 */
6368 if (!IsUnderPostmaster || max_parallel_maintenance_workers == 0)
6369 return 0;
6370
6371 /* Set up largely-dummy planner state */
6372 query = makeNode(Query);
6373 query->commandType = CMD_SELECT;
6374
6375 glob = makeNode(PlannerGlobal);
6376
6377 root = makeNode(PlannerInfo);
6378 root->parse = query;
6379 root->glob = glob;
6380 root->query_level = 1;
6381 root->planner_cxt = CurrentMemoryContext;
6382 root->wt_param_id = -1;
6383
6384 /*
6385 * Build a minimal RTE.
6386 *
6387 * Mark the RTE with inh = true. This is a kludge to prevent
6388 * get_relation_info() from fetching index info, which is necessary
6389 * because it does not expect that any IndexOptInfo is currently
6390 * undergoing REINDEX.
6391 */
6392 rte = makeNode(RangeTblEntry);
6393 rte->rtekind = RTE_RELATION;
6394 rte->relid = tableOid;
6395 rte->relkind = RELKIND_RELATION; /* Don't be too picky. */
6396 rte->rellockmode = AccessShareLock;
6397 rte->lateral = false;
6398 rte->inh = true;
6399 rte->inFromCl = true;
6400 query->rtable = list_make1(rte);
6401
6402 /* Set up RTE/RelOptInfo arrays */
6403 setup_simple_rel_arrays(root);
6404
6405 /* Build RelOptInfo */
6406 rel = build_simple_rel(root, 1, NULL);
6407
6408 /* Rels are assumed already locked by the caller */
6409 heap = table_open(tableOid, NoLock);
6410 index = index_open(indexOid, NoLock);
6411
6412 /*
6413 * Determine if it's safe to proceed.
6414 *
6415 * Currently, parallel workers can't access the leader's temporary tables.
6416 * Furthermore, any index predicate or index expressions must be parallel
6417 * safe.
6418 */
6419 if (heap->rd_rel->relpersistence == RELPERSISTENCE_TEMP ||
6420 !is_parallel_safe(root, (Node *) RelationGetIndexExpressions(index)) ||
6421 !is_parallel_safe(root, (Node *) RelationGetIndexPredicate(index)))
6422 {
6423 parallel_workers = 0;
6424 goto done;
6425 }
6426
6427 /*
6428 * If parallel_workers storage parameter is set for the table, accept that
6429 * as the number of parallel worker processes to launch (though still cap
6430 * at max_parallel_maintenance_workers). Note that we deliberately do not
6431 * consider any other factor when parallel_workers is set. (e.g., memory
6432 * use by workers.)
6433 */
6434 if (rel->rel_parallel_workers != -1)
6435 {
6436 parallel_workers = Min(rel->rel_parallel_workers,
6437 max_parallel_maintenance_workers);
6438 goto done;
6439 }
6440
6441 /*
6442 * Estimate heap relation size ourselves, since rel->pages cannot be
6443 * trusted (heap RTE was marked as inheritance parent)
6444 */
6445 estimate_rel_size(heap, NULL, &heap_blocks, &reltuples, &allvisfrac);
6446
6447 /*
6448 * Determine number of workers to scan the heap relation using generic
6449 * model
6450 */
6451 parallel_workers = compute_parallel_worker(rel, heap_blocks, -1,
6452 max_parallel_maintenance_workers);
6453
6454 /*
6455 * Cap workers based on available maintenance_work_mem as needed.
6456 *
6457 * Note that each tuplesort participant receives an even share of the
6458 * total maintenance_work_mem budget. Aim to leave participants
6459 * (including the leader as a participant) with no less than 32MB of
6460 * memory. This leaves cases where maintenance_work_mem is set to 64MB
6461 * immediately past the threshold of being capable of launching a single
6462 * parallel worker to sort.
6463 */
6464 while (parallel_workers > 0 &&
6465 maintenance_work_mem / (parallel_workers + 1) < 32768L)
6466 parallel_workers--;
6467
6468 done:
6469 index_close(index, NoLock);
6470 table_close(heap, NoLock);
6471
6472 return parallel_workers;
6473 }
6474
6475 /*
6476 * add_paths_to_grouping_rel
6477 *
6478 * Add non-partial paths to grouping relation.
6479 */
6480 static void
add_paths_to_grouping_rel(PlannerInfo * root,RelOptInfo * input_rel,RelOptInfo * grouped_rel,RelOptInfo * partially_grouped_rel,const AggClauseCosts * agg_costs,grouping_sets_data * gd,double dNumGroups,GroupPathExtraData * extra)6481 add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
6482 RelOptInfo *grouped_rel,
6483 RelOptInfo *partially_grouped_rel,
6484 const AggClauseCosts *agg_costs,
6485 grouping_sets_data *gd, double dNumGroups,
6486 GroupPathExtraData *extra)
6487 {
6488 Query *parse = root->parse;
6489 Path *cheapest_path = input_rel->cheapest_total_path;
6490 ListCell *lc;
6491 bool can_hash = (extra->flags & GROUPING_CAN_USE_HASH) != 0;
6492 bool can_sort = (extra->flags & GROUPING_CAN_USE_SORT) != 0;
6493 List *havingQual = (List *) extra->havingQual;
6494 AggClauseCosts *agg_final_costs = &extra->agg_final_costs;
6495
6496 if (can_sort)
6497 {
6498 /*
6499 * Use any available suitably-sorted path as input, and also consider
6500 * sorting the cheapest-total path.
6501 */
6502 foreach(lc, input_rel->pathlist)
6503 {
6504 Path *path = (Path *) lfirst(lc);
6505 Path *path_original = path;
6506 bool is_sorted;
6507 int presorted_keys;
6508
6509 is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
6510 path->pathkeys,
6511 &presorted_keys);
6512
6513 if (path == cheapest_path || is_sorted)
6514 {
6515 /* Sort the cheapest-total path if it isn't already sorted */
6516 if (!is_sorted)
6517 path = (Path *) create_sort_path(root,
6518 grouped_rel,
6519 path,
6520 root->group_pathkeys,
6521 -1.0);
6522
6523 /* Now decide what to stick atop it */
6524 if (parse->groupingSets)
6525 {
6526 consider_groupingsets_paths(root, grouped_rel,
6527 path, true, can_hash,
6528 gd, agg_costs, dNumGroups);
6529 }
6530 else if (parse->hasAggs)
6531 {
6532 /*
6533 * We have aggregation, possibly with plain GROUP BY. Make
6534 * an AggPath.
6535 */
6536 add_path(grouped_rel, (Path *)
6537 create_agg_path(root,
6538 grouped_rel,
6539 path,
6540 grouped_rel->reltarget,
6541 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
6542 AGGSPLIT_SIMPLE,
6543 parse->groupClause,
6544 havingQual,
6545 agg_costs,
6546 dNumGroups));
6547 }
6548 else if (parse->groupClause)
6549 {
6550 /*
6551 * We have GROUP BY without aggregation or grouping sets.
6552 * Make a GroupPath.
6553 */
6554 add_path(grouped_rel, (Path *)
6555 create_group_path(root,
6556 grouped_rel,
6557 path,
6558 parse->groupClause,
6559 havingQual,
6560 dNumGroups));
6561 }
6562 else
6563 {
6564 /* Other cases should have been handled above */
6565 Assert(false);
6566 }
6567 }
6568
6569 /*
6570 * Now we may consider incremental sort on this path, but only
6571 * when the path is not already sorted and when incremental sort
6572 * is enabled.
6573 */
6574 if (is_sorted || !enable_incremental_sort)
6575 continue;
6576
6577 /* Restore the input path (we might have added Sort on top). */
6578 path = path_original;
6579
6580 /* no shared prefix, no point in building incremental sort */
6581 if (presorted_keys == 0)
6582 continue;
6583
6584 /*
6585 * We should have already excluded pathkeys of length 1 because
6586 * then presorted_keys > 0 would imply is_sorted was true.
6587 */
6588 Assert(list_length(root->group_pathkeys) != 1);
6589
6590 path = (Path *) create_incremental_sort_path(root,
6591 grouped_rel,
6592 path,
6593 root->group_pathkeys,
6594 presorted_keys,
6595 -1.0);
6596
6597 /* Now decide what to stick atop it */
6598 if (parse->groupingSets)
6599 {
6600 consider_groupingsets_paths(root, grouped_rel,
6601 path, true, can_hash,
6602 gd, agg_costs, dNumGroups);
6603 }
6604 else if (parse->hasAggs)
6605 {
6606 /*
6607 * We have aggregation, possibly with plain GROUP BY. Make an
6608 * AggPath.
6609 */
6610 add_path(grouped_rel, (Path *)
6611 create_agg_path(root,
6612 grouped_rel,
6613 path,
6614 grouped_rel->reltarget,
6615 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
6616 AGGSPLIT_SIMPLE,
6617 parse->groupClause,
6618 havingQual,
6619 agg_costs,
6620 dNumGroups));
6621 }
6622 else if (parse->groupClause)
6623 {
6624 /*
6625 * We have GROUP BY without aggregation or grouping sets. Make
6626 * a GroupPath.
6627 */
6628 add_path(grouped_rel, (Path *)
6629 create_group_path(root,
6630 grouped_rel,
6631 path,
6632 parse->groupClause,
6633 havingQual,
6634 dNumGroups));
6635 }
6636 else
6637 {
6638 /* Other cases should have been handled above */
6639 Assert(false);
6640 }
6641 }
6642
6643 /*
6644 * Instead of operating directly on the input relation, we can
6645 * consider finalizing a partially aggregated path.
6646 */
6647 if (partially_grouped_rel != NULL)
6648 {
6649 foreach(lc, partially_grouped_rel->pathlist)
6650 {
6651 Path *path = (Path *) lfirst(lc);
6652 Path *path_original = path;
6653 bool is_sorted;
6654 int presorted_keys;
6655
6656 is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
6657 path->pathkeys,
6658 &presorted_keys);
6659
6660 /*
6661 * Insert a Sort node, if required. But there's no point in
6662 * sorting anything but the cheapest path.
6663 */
6664 if (!is_sorted)
6665 {
6666 if (path != partially_grouped_rel->cheapest_total_path)
6667 continue;
6668 path = (Path *) create_sort_path(root,
6669 grouped_rel,
6670 path,
6671 root->group_pathkeys,
6672 -1.0);
6673 }
6674
6675 if (parse->hasAggs)
6676 add_path(grouped_rel, (Path *)
6677 create_agg_path(root,
6678 grouped_rel,
6679 path,
6680 grouped_rel->reltarget,
6681 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
6682 AGGSPLIT_FINAL_DESERIAL,
6683 parse->groupClause,
6684 havingQual,
6685 agg_final_costs,
6686 dNumGroups));
6687 else
6688 add_path(grouped_rel, (Path *)
6689 create_group_path(root,
6690 grouped_rel,
6691 path,
6692 parse->groupClause,
6693 havingQual,
6694 dNumGroups));
6695
6696 /*
6697 * Now we may consider incremental sort on this path, but only
6698 * when the path is not already sorted and when incremental
6699 * sort is enabled.
6700 */
6701 if (is_sorted || !enable_incremental_sort)
6702 continue;
6703
6704 /* Restore the input path (we might have added Sort on top). */
6705 path = path_original;
6706
6707 /* no shared prefix, not point in building incremental sort */
6708 if (presorted_keys == 0)
6709 continue;
6710
6711 /*
6712 * We should have already excluded pathkeys of length 1
6713 * because then presorted_keys > 0 would imply is_sorted was
6714 * true.
6715 */
6716 Assert(list_length(root->group_pathkeys) != 1);
6717
6718 path = (Path *) create_incremental_sort_path(root,
6719 grouped_rel,
6720 path,
6721 root->group_pathkeys,
6722 presorted_keys,
6723 -1.0);
6724
6725 if (parse->hasAggs)
6726 add_path(grouped_rel, (Path *)
6727 create_agg_path(root,
6728 grouped_rel,
6729 path,
6730 grouped_rel->reltarget,
6731 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
6732 AGGSPLIT_FINAL_DESERIAL,
6733 parse->groupClause,
6734 havingQual,
6735 agg_final_costs,
6736 dNumGroups));
6737 else
6738 add_path(grouped_rel, (Path *)
6739 create_group_path(root,
6740 grouped_rel,
6741 path,
6742 parse->groupClause,
6743 havingQual,
6744 dNumGroups));
6745 }
6746 }
6747 }
6748
6749 if (can_hash)
6750 {
6751 if (parse->groupingSets)
6752 {
6753 /*
6754 * Try for a hash-only groupingsets path over unsorted input.
6755 */
6756 consider_groupingsets_paths(root, grouped_rel,
6757 cheapest_path, false, true,
6758 gd, agg_costs, dNumGroups);
6759 }
6760 else
6761 {
6762 /*
6763 * Generate a HashAgg Path. We just need an Agg over the
6764 * cheapest-total input path, since input order won't matter.
6765 */
6766 add_path(grouped_rel, (Path *)
6767 create_agg_path(root, grouped_rel,
6768 cheapest_path,
6769 grouped_rel->reltarget,
6770 AGG_HASHED,
6771 AGGSPLIT_SIMPLE,
6772 parse->groupClause,
6773 havingQual,
6774 agg_costs,
6775 dNumGroups));
6776 }
6777
6778 /*
6779 * Generate a Finalize HashAgg Path atop of the cheapest partially
6780 * grouped path, assuming there is one
6781 */
6782 if (partially_grouped_rel && partially_grouped_rel->pathlist)
6783 {
6784 Path *path = partially_grouped_rel->cheapest_total_path;
6785
6786 add_path(grouped_rel, (Path *)
6787 create_agg_path(root,
6788 grouped_rel,
6789 path,
6790 grouped_rel->reltarget,
6791 AGG_HASHED,
6792 AGGSPLIT_FINAL_DESERIAL,
6793 parse->groupClause,
6794 havingQual,
6795 agg_final_costs,
6796 dNumGroups));
6797 }
6798 }
6799
6800 /*
6801 * When partitionwise aggregate is used, we might have fully aggregated
6802 * paths in the partial pathlist, because add_paths_to_append_rel() will
6803 * consider a path for grouped_rel consisting of a Parallel Append of
6804 * non-partial paths from each child.
6805 */
6806 if (grouped_rel->partial_pathlist != NIL)
6807 gather_grouping_paths(root, grouped_rel);
6808 }
6809
6810 /*
6811 * create_partial_grouping_paths
6812 *
6813 * Create a new upper relation representing the result of partial aggregation
6814 * and populate it with appropriate paths. Note that we don't finalize the
6815 * lists of paths here, so the caller can add additional partial or non-partial
6816 * paths and must afterward call gather_grouping_paths and set_cheapest on
6817 * the returned upper relation.
6818 *
6819 * All paths for this new upper relation -- both partial and non-partial --
6820 * have been partially aggregated but require a subsequent FinalizeAggregate
6821 * step.
6822 *
6823 * NB: This function is allowed to return NULL if it determines that there is
6824 * no real need to create a new RelOptInfo.
6825 */
6826 static RelOptInfo *
create_partial_grouping_paths(PlannerInfo * root,RelOptInfo * grouped_rel,RelOptInfo * input_rel,grouping_sets_data * gd,GroupPathExtraData * extra,bool force_rel_creation)6827 create_partial_grouping_paths(PlannerInfo *root,
6828 RelOptInfo *grouped_rel,
6829 RelOptInfo *input_rel,
6830 grouping_sets_data *gd,
6831 GroupPathExtraData *extra,
6832 bool force_rel_creation)
6833 {
6834 Query *parse = root->parse;
6835 RelOptInfo *partially_grouped_rel;
6836 AggClauseCosts *agg_partial_costs = &extra->agg_partial_costs;
6837 AggClauseCosts *agg_final_costs = &extra->agg_final_costs;
6838 Path *cheapest_partial_path = NULL;
6839 Path *cheapest_total_path = NULL;
6840 double dNumPartialGroups = 0;
6841 double dNumPartialPartialGroups = 0;
6842 ListCell *lc;
6843 bool can_hash = (extra->flags & GROUPING_CAN_USE_HASH) != 0;
6844 bool can_sort = (extra->flags & GROUPING_CAN_USE_SORT) != 0;
6845
6846 /*
6847 * Consider whether we should generate partially aggregated non-partial
6848 * paths. We can only do this if we have a non-partial path, and only if
6849 * the parent of the input rel is performing partial partitionwise
6850 * aggregation. (Note that extra->patype is the type of partitionwise
6851 * aggregation being used at the parent level, not this level.)
6852 */
6853 if (input_rel->pathlist != NIL &&
6854 extra->patype == PARTITIONWISE_AGGREGATE_PARTIAL)
6855 cheapest_total_path = input_rel->cheapest_total_path;
6856
6857 /*
6858 * If parallelism is possible for grouped_rel, then we should consider
6859 * generating partially-grouped partial paths. However, if the input rel
6860 * has no partial paths, then we can't.
6861 */
6862 if (grouped_rel->consider_parallel && input_rel->partial_pathlist != NIL)
6863 cheapest_partial_path = linitial(input_rel->partial_pathlist);
6864
6865 /*
6866 * If we can't partially aggregate partial paths, and we can't partially
6867 * aggregate non-partial paths, then don't bother creating the new
6868 * RelOptInfo at all, unless the caller specified force_rel_creation.
6869 */
6870 if (cheapest_total_path == NULL &&
6871 cheapest_partial_path == NULL &&
6872 !force_rel_creation)
6873 return NULL;
6874
6875 /*
6876 * Build a new upper relation to represent the result of partially
6877 * aggregating the rows from the input relation.
6878 */
6879 partially_grouped_rel = fetch_upper_rel(root,
6880 UPPERREL_PARTIAL_GROUP_AGG,
6881 grouped_rel->relids);
6882 partially_grouped_rel->consider_parallel =
6883 grouped_rel->consider_parallel;
6884 partially_grouped_rel->reloptkind = grouped_rel->reloptkind;
6885 partially_grouped_rel->serverid = grouped_rel->serverid;
6886 partially_grouped_rel->userid = grouped_rel->userid;
6887 partially_grouped_rel->useridiscurrent = grouped_rel->useridiscurrent;
6888 partially_grouped_rel->fdwroutine = grouped_rel->fdwroutine;
6889
6890 /*
6891 * Build target list for partial aggregate paths. These paths cannot just
6892 * emit the same tlist as regular aggregate paths, because (1) we must
6893 * include Vars and Aggrefs needed in HAVING, which might not appear in
6894 * the result tlist, and (2) the Aggrefs must be set in partial mode.
6895 */
6896 partially_grouped_rel->reltarget =
6897 make_partial_grouping_target(root, grouped_rel->reltarget,
6898 extra->havingQual);
6899
6900 if (!extra->partial_costs_set)
6901 {
6902 /*
6903 * Collect statistics about aggregates for estimating costs of
6904 * performing aggregation in parallel.
6905 */
6906 MemSet(agg_partial_costs, 0, sizeof(AggClauseCosts));
6907 MemSet(agg_final_costs, 0, sizeof(AggClauseCosts));
6908 if (parse->hasAggs)
6909 {
6910 List *partial_target_exprs;
6911
6912 /* partial phase */
6913 partial_target_exprs = partially_grouped_rel->reltarget->exprs;
6914 get_agg_clause_costs(root, (Node *) partial_target_exprs,
6915 AGGSPLIT_INITIAL_SERIAL,
6916 agg_partial_costs);
6917
6918 /* final phase */
6919 get_agg_clause_costs(root, (Node *) grouped_rel->reltarget->exprs,
6920 AGGSPLIT_FINAL_DESERIAL,
6921 agg_final_costs);
6922 get_agg_clause_costs(root, extra->havingQual,
6923 AGGSPLIT_FINAL_DESERIAL,
6924 agg_final_costs);
6925 }
6926
6927 extra->partial_costs_set = true;
6928 }
6929
6930 /* Estimate number of partial groups. */
6931 if (cheapest_total_path != NULL)
6932 dNumPartialGroups =
6933 get_number_of_groups(root,
6934 cheapest_total_path->rows,
6935 gd,
6936 extra->targetList);
6937 if (cheapest_partial_path != NULL)
6938 dNumPartialPartialGroups =
6939 get_number_of_groups(root,
6940 cheapest_partial_path->rows,
6941 gd,
6942 extra->targetList);
6943
6944 if (can_sort && cheapest_total_path != NULL)
6945 {
6946 /* This should have been checked previously */
6947 Assert(parse->hasAggs || parse->groupClause);
6948
6949 /*
6950 * Use any available suitably-sorted path as input, and also consider
6951 * sorting the cheapest partial path.
6952 */
6953 foreach(lc, input_rel->pathlist)
6954 {
6955 Path *path = (Path *) lfirst(lc);
6956 bool is_sorted;
6957
6958 is_sorted = pathkeys_contained_in(root->group_pathkeys,
6959 path->pathkeys);
6960 if (path == cheapest_total_path || is_sorted)
6961 {
6962 /* Sort the cheapest partial path, if it isn't already */
6963 if (!is_sorted)
6964 path = (Path *) create_sort_path(root,
6965 partially_grouped_rel,
6966 path,
6967 root->group_pathkeys,
6968 -1.0);
6969
6970 if (parse->hasAggs)
6971 add_path(partially_grouped_rel, (Path *)
6972 create_agg_path(root,
6973 partially_grouped_rel,
6974 path,
6975 partially_grouped_rel->reltarget,
6976 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
6977 AGGSPLIT_INITIAL_SERIAL,
6978 parse->groupClause,
6979 NIL,
6980 agg_partial_costs,
6981 dNumPartialGroups));
6982 else
6983 add_path(partially_grouped_rel, (Path *)
6984 create_group_path(root,
6985 partially_grouped_rel,
6986 path,
6987 parse->groupClause,
6988 NIL,
6989 dNumPartialGroups));
6990 }
6991 }
6992
6993 /*
6994 * Consider incremental sort on all partial paths, if enabled.
6995 *
6996 * We can also skip the entire loop when we only have a single-item
6997 * group_pathkeys because then we can't possibly have a presorted
6998 * prefix of the list without having the list be fully sorted.
6999 */
7000 if (enable_incremental_sort && list_length(root->group_pathkeys) > 1)
7001 {
7002 foreach(lc, input_rel->pathlist)
7003 {
7004 Path *path = (Path *) lfirst(lc);
7005 bool is_sorted;
7006 int presorted_keys;
7007
7008 is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
7009 path->pathkeys,
7010 &presorted_keys);
7011
7012 /* Ignore already sorted paths */
7013 if (is_sorted)
7014 continue;
7015
7016 if (presorted_keys == 0)
7017 continue;
7018
7019 /* Since we have presorted keys, consider incremental sort. */
7020 path = (Path *) create_incremental_sort_path(root,
7021 partially_grouped_rel,
7022 path,
7023 root->group_pathkeys,
7024 presorted_keys,
7025 -1.0);
7026
7027 if (parse->hasAggs)
7028 add_path(partially_grouped_rel, (Path *)
7029 create_agg_path(root,
7030 partially_grouped_rel,
7031 path,
7032 partially_grouped_rel->reltarget,
7033 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
7034 AGGSPLIT_INITIAL_SERIAL,
7035 parse->groupClause,
7036 NIL,
7037 agg_partial_costs,
7038 dNumPartialGroups));
7039 else
7040 add_path(partially_grouped_rel, (Path *)
7041 create_group_path(root,
7042 partially_grouped_rel,
7043 path,
7044 parse->groupClause,
7045 NIL,
7046 dNumPartialGroups));
7047 }
7048 }
7049
7050 }
7051
7052 if (can_sort && cheapest_partial_path != NULL)
7053 {
7054 /* Similar to above logic, but for partial paths. */
7055 foreach(lc, input_rel->partial_pathlist)
7056 {
7057 Path *path = (Path *) lfirst(lc);
7058 Path *path_original = path;
7059 bool is_sorted;
7060 int presorted_keys;
7061
7062 is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
7063 path->pathkeys,
7064 &presorted_keys);
7065
7066 if (path == cheapest_partial_path || is_sorted)
7067 {
7068 /* Sort the cheapest partial path, if it isn't already */
7069 if (!is_sorted)
7070 path = (Path *) create_sort_path(root,
7071 partially_grouped_rel,
7072 path,
7073 root->group_pathkeys,
7074 -1.0);
7075
7076 if (parse->hasAggs)
7077 add_partial_path(partially_grouped_rel, (Path *)
7078 create_agg_path(root,
7079 partially_grouped_rel,
7080 path,
7081 partially_grouped_rel->reltarget,
7082 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
7083 AGGSPLIT_INITIAL_SERIAL,
7084 parse->groupClause,
7085 NIL,
7086 agg_partial_costs,
7087 dNumPartialPartialGroups));
7088 else
7089 add_partial_path(partially_grouped_rel, (Path *)
7090 create_group_path(root,
7091 partially_grouped_rel,
7092 path,
7093 parse->groupClause,
7094 NIL,
7095 dNumPartialPartialGroups));
7096 }
7097
7098 /*
7099 * Now we may consider incremental sort on this path, but only
7100 * when the path is not already sorted and when incremental sort
7101 * is enabled.
7102 */
7103 if (is_sorted || !enable_incremental_sort)
7104 continue;
7105
7106 /* Restore the input path (we might have added Sort on top). */
7107 path = path_original;
7108
7109 /* no shared prefix, not point in building incremental sort */
7110 if (presorted_keys == 0)
7111 continue;
7112
7113 /*
7114 * We should have already excluded pathkeys of length 1 because
7115 * then presorted_keys > 0 would imply is_sorted was true.
7116 */
7117 Assert(list_length(root->group_pathkeys) != 1);
7118
7119 path = (Path *) create_incremental_sort_path(root,
7120 partially_grouped_rel,
7121 path,
7122 root->group_pathkeys,
7123 presorted_keys,
7124 -1.0);
7125
7126 if (parse->hasAggs)
7127 add_partial_path(partially_grouped_rel, (Path *)
7128 create_agg_path(root,
7129 partially_grouped_rel,
7130 path,
7131 partially_grouped_rel->reltarget,
7132 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
7133 AGGSPLIT_INITIAL_SERIAL,
7134 parse->groupClause,
7135 NIL,
7136 agg_partial_costs,
7137 dNumPartialPartialGroups));
7138 else
7139 add_partial_path(partially_grouped_rel, (Path *)
7140 create_group_path(root,
7141 partially_grouped_rel,
7142 path,
7143 parse->groupClause,
7144 NIL,
7145 dNumPartialPartialGroups));
7146 }
7147 }
7148
7149 /*
7150 * Add a partially-grouped HashAgg Path where possible
7151 */
7152 if (can_hash && cheapest_total_path != NULL)
7153 {
7154 /* Checked above */
7155 Assert(parse->hasAggs || parse->groupClause);
7156
7157 add_path(partially_grouped_rel, (Path *)
7158 create_agg_path(root,
7159 partially_grouped_rel,
7160 cheapest_total_path,
7161 partially_grouped_rel->reltarget,
7162 AGG_HASHED,
7163 AGGSPLIT_INITIAL_SERIAL,
7164 parse->groupClause,
7165 NIL,
7166 agg_partial_costs,
7167 dNumPartialGroups));
7168 }
7169
7170 /*
7171 * Now add a partially-grouped HashAgg partial Path where possible
7172 */
7173 if (can_hash && cheapest_partial_path != NULL)
7174 {
7175 add_partial_path(partially_grouped_rel, (Path *)
7176 create_agg_path(root,
7177 partially_grouped_rel,
7178 cheapest_partial_path,
7179 partially_grouped_rel->reltarget,
7180 AGG_HASHED,
7181 AGGSPLIT_INITIAL_SERIAL,
7182 parse->groupClause,
7183 NIL,
7184 agg_partial_costs,
7185 dNumPartialPartialGroups));
7186 }
7187
7188 /*
7189 * If there is an FDW that's responsible for all baserels of the query,
7190 * let it consider adding partially grouped ForeignPaths.
7191 */
7192 if (partially_grouped_rel->fdwroutine &&
7193 partially_grouped_rel->fdwroutine->GetForeignUpperPaths)
7194 {
7195 FdwRoutine *fdwroutine = partially_grouped_rel->fdwroutine;
7196
7197 fdwroutine->GetForeignUpperPaths(root,
7198 UPPERREL_PARTIAL_GROUP_AGG,
7199 input_rel, partially_grouped_rel,
7200 extra);
7201 }
7202
7203 return partially_grouped_rel;
7204 }
7205
7206 /*
7207 * Generate Gather and Gather Merge paths for a grouping relation or partial
7208 * grouping relation.
7209 *
7210 * generate_gather_paths does most of the work, but we also consider a special
7211 * case: we could try sorting the data by the group_pathkeys and then applying
7212 * Gather Merge.
7213 *
7214 * NB: This function shouldn't be used for anything other than a grouped or
7215 * partially grouped relation not only because of the fact that it explicitly
7216 * references group_pathkeys but we pass "true" as the third argument to
7217 * generate_gather_paths().
7218 */
7219 static void
gather_grouping_paths(PlannerInfo * root,RelOptInfo * rel)7220 gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
7221 {
7222 ListCell *lc;
7223 Path *cheapest_partial_path;
7224
7225 /* Try Gather for unordered paths and Gather Merge for ordered ones. */
7226 generate_useful_gather_paths(root, rel, true);
7227
7228 /* Try cheapest partial path + explicit Sort + Gather Merge. */
7229 cheapest_partial_path = linitial(rel->partial_pathlist);
7230 if (!pathkeys_contained_in(root->group_pathkeys,
7231 cheapest_partial_path->pathkeys))
7232 {
7233 Path *path;
7234 double total_groups;
7235
7236 total_groups =
7237 cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
7238 path = (Path *) create_sort_path(root, rel, cheapest_partial_path,
7239 root->group_pathkeys,
7240 -1.0);
7241 path = (Path *)
7242 create_gather_merge_path(root,
7243 rel,
7244 path,
7245 rel->reltarget,
7246 root->group_pathkeys,
7247 NULL,
7248 &total_groups);
7249
7250 add_path(rel, path);
7251 }
7252
7253 /*
7254 * Consider incremental sort on all partial paths, if enabled.
7255 *
7256 * We can also skip the entire loop when we only have a single-item
7257 * group_pathkeys because then we can't possibly have a presorted prefix
7258 * of the list without having the list be fully sorted.
7259 */
7260 if (!enable_incremental_sort || list_length(root->group_pathkeys) == 1)
7261 return;
7262
7263 /* also consider incremental sort on partial paths, if enabled */
7264 foreach(lc, rel->partial_pathlist)
7265 {
7266 Path *path = (Path *) lfirst(lc);
7267 bool is_sorted;
7268 int presorted_keys;
7269 double total_groups;
7270
7271 is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
7272 path->pathkeys,
7273 &presorted_keys);
7274
7275 if (is_sorted)
7276 continue;
7277
7278 if (presorted_keys == 0)
7279 continue;
7280
7281 path = (Path *) create_incremental_sort_path(root,
7282 rel,
7283 path,
7284 root->group_pathkeys,
7285 presorted_keys,
7286 -1.0);
7287
7288 path = (Path *)
7289 create_gather_merge_path(root,
7290 rel,
7291 path,
7292 rel->reltarget,
7293 root->group_pathkeys,
7294 NULL,
7295 &total_groups);
7296
7297 add_path(rel, path);
7298 }
7299 }
7300
7301 /*
7302 * can_partial_agg
7303 *
7304 * Determines whether or not partial grouping and/or aggregation is possible.
7305 * Returns true when possible, false otherwise.
7306 */
7307 static bool
can_partial_agg(PlannerInfo * root,const AggClauseCosts * agg_costs)7308 can_partial_agg(PlannerInfo *root, const AggClauseCosts *agg_costs)
7309 {
7310 Query *parse = root->parse;
7311
7312 if (!parse->hasAggs && parse->groupClause == NIL)
7313 {
7314 /*
7315 * We don't know how to do parallel aggregation unless we have either
7316 * some aggregates or a grouping clause.
7317 */
7318 return false;
7319 }
7320 else if (parse->groupingSets)
7321 {
7322 /* We don't know how to do grouping sets in parallel. */
7323 return false;
7324 }
7325 else if (agg_costs->hasNonPartial || agg_costs->hasNonSerial)
7326 {
7327 /* Insufficient support for partial mode. */
7328 return false;
7329 }
7330
7331 /* Everything looks good. */
7332 return true;
7333 }
7334
7335 /*
7336 * apply_scanjoin_target_to_paths
7337 *
7338 * Adjust the final scan/join relation, and recursively all of its children,
7339 * to generate the final scan/join target. It would be more correct to model
7340 * this as a separate planning step with a new RelOptInfo at the toplevel and
7341 * for each child relation, but doing it this way is noticeably cheaper.
7342 * Maybe that problem can be solved at some point, but for now we do this.
7343 *
7344 * If tlist_same_exprs is true, then the scan/join target to be applied has
7345 * the same expressions as the existing reltarget, so we need only insert the
7346 * appropriate sortgroupref information. By avoiding the creation of
7347 * projection paths we save effort both immediately and at plan creation time.
7348 */
7349 static void
apply_scanjoin_target_to_paths(PlannerInfo * root,RelOptInfo * rel,List * scanjoin_targets,List * scanjoin_targets_contain_srfs,bool scanjoin_target_parallel_safe,bool tlist_same_exprs)7350 apply_scanjoin_target_to_paths(PlannerInfo *root,
7351 RelOptInfo *rel,
7352 List *scanjoin_targets,
7353 List *scanjoin_targets_contain_srfs,
7354 bool scanjoin_target_parallel_safe,
7355 bool tlist_same_exprs)
7356 {
7357 bool rel_is_partitioned = IS_PARTITIONED_REL(rel);
7358 PathTarget *scanjoin_target;
7359 ListCell *lc;
7360
7361 /* This recurses, so be paranoid. */
7362 check_stack_depth();
7363
7364 /*
7365 * If the rel is partitioned, we want to drop its existing paths and
7366 * generate new ones. This function would still be correct if we kept the
7367 * existing paths: we'd modify them to generate the correct target above
7368 * the partitioning Append, and then they'd compete on cost with paths
7369 * generating the target below the Append. However, in our current cost
7370 * model the latter way is always the same or cheaper cost, so modifying
7371 * the existing paths would just be useless work. Moreover, when the cost
7372 * is the same, varying roundoff errors might sometimes allow an existing
7373 * path to be picked, resulting in undesirable cross-platform plan
7374 * variations. So we drop old paths and thereby force the work to be done
7375 * below the Append, except in the case of a non-parallel-safe target.
7376 *
7377 * Some care is needed, because we have to allow generate_gather_paths to
7378 * see the old partial paths in the next stanza. Hence, zap the main
7379 * pathlist here, then allow generate_gather_paths to add path(s) to the
7380 * main list, and finally zap the partial pathlist.
7381 */
7382 if (rel_is_partitioned)
7383 rel->pathlist = NIL;
7384
7385 /*
7386 * If the scan/join target is not parallel-safe, partial paths cannot
7387 * generate it.
7388 */
7389 if (!scanjoin_target_parallel_safe)
7390 {
7391 /*
7392 * Since we can't generate the final scan/join target in parallel
7393 * workers, this is our last opportunity to use any partial paths that
7394 * exist; so build Gather path(s) that use them and emit whatever the
7395 * current reltarget is. We don't do this in the case where the
7396 * target is parallel-safe, since we will be able to generate superior
7397 * paths by doing it after the final scan/join target has been
7398 * applied.
7399 */
7400 generate_useful_gather_paths(root, rel, false);
7401
7402 /* Can't use parallel query above this level. */
7403 rel->partial_pathlist = NIL;
7404 rel->consider_parallel = false;
7405 }
7406
7407 /* Finish dropping old paths for a partitioned rel, per comment above */
7408 if (rel_is_partitioned)
7409 rel->partial_pathlist = NIL;
7410
7411 /* Extract SRF-free scan/join target. */
7412 scanjoin_target = linitial_node(PathTarget, scanjoin_targets);
7413
7414 /*
7415 * Apply the SRF-free scan/join target to each existing path.
7416 *
7417 * If the tlist exprs are the same, we can just inject the sortgroupref
7418 * information into the existing pathtargets. Otherwise, replace each
7419 * path with a projection path that generates the SRF-free scan/join
7420 * target. This can't change the ordering of paths within rel->pathlist,
7421 * so we just modify the list in place.
7422 */
7423 foreach(lc, rel->pathlist)
7424 {
7425 Path *subpath = (Path *) lfirst(lc);
7426
7427 /* Shouldn't have any parameterized paths anymore */
7428 Assert(subpath->param_info == NULL);
7429
7430 if (tlist_same_exprs)
7431 subpath->pathtarget->sortgrouprefs =
7432 scanjoin_target->sortgrouprefs;
7433 else
7434 {
7435 Path *newpath;
7436
7437 newpath = (Path *) create_projection_path(root, rel, subpath,
7438 scanjoin_target);
7439 lfirst(lc) = newpath;
7440 }
7441 }
7442
7443 /* Likewise adjust the targets for any partial paths. */
7444 foreach(lc, rel->partial_pathlist)
7445 {
7446 Path *subpath = (Path *) lfirst(lc);
7447
7448 /* Shouldn't have any parameterized paths anymore */
7449 Assert(subpath->param_info == NULL);
7450
7451 if (tlist_same_exprs)
7452 subpath->pathtarget->sortgrouprefs =
7453 scanjoin_target->sortgrouprefs;
7454 else
7455 {
7456 Path *newpath;
7457
7458 newpath = (Path *) create_projection_path(root, rel, subpath,
7459 scanjoin_target);
7460 lfirst(lc) = newpath;
7461 }
7462 }
7463
7464 /*
7465 * Now, if final scan/join target contains SRFs, insert ProjectSetPath(s)
7466 * atop each existing path. (Note that this function doesn't look at the
7467 * cheapest-path fields, which is a good thing because they're bogus right
7468 * now.)
7469 */
7470 if (root->parse->hasTargetSRFs)
7471 adjust_paths_for_srfs(root, rel,
7472 scanjoin_targets,
7473 scanjoin_targets_contain_srfs);
7474
7475 /*
7476 * Update the rel's target to be the final (with SRFs) scan/join target.
7477 * This now matches the actual output of all the paths, and we might get
7478 * confused in createplan.c if they don't agree. We must do this now so
7479 * that any append paths made in the next part will use the correct
7480 * pathtarget (cf. create_append_path).
7481 *
7482 * Note that this is also necessary if GetForeignUpperPaths() gets called
7483 * on the final scan/join relation or on any of its children, since the
7484 * FDW might look at the rel's target to create ForeignPaths.
7485 */
7486 rel->reltarget = llast_node(PathTarget, scanjoin_targets);
7487
7488 /*
7489 * If the relation is partitioned, recursively apply the scan/join target
7490 * to all partitions, and generate brand-new Append paths in which the
7491 * scan/join target is computed below the Append rather than above it.
7492 * Since Append is not projection-capable, that might save a separate
7493 * Result node, and it also is important for partitionwise aggregate.
7494 */
7495 if (rel_is_partitioned)
7496 {
7497 List *live_children = NIL;
7498 int partition_idx;
7499
7500 /* Adjust each partition. */
7501 for (partition_idx = 0; partition_idx < rel->nparts; partition_idx++)
7502 {
7503 RelOptInfo *child_rel = rel->part_rels[partition_idx];
7504 AppendRelInfo **appinfos;
7505 int nappinfos;
7506 List *child_scanjoin_targets = NIL;
7507 ListCell *lc;
7508
7509 /* Pruned or dummy children can be ignored. */
7510 if (child_rel == NULL || IS_DUMMY_REL(child_rel))
7511 continue;
7512
7513 /* Translate scan/join targets for this child. */
7514 appinfos = find_appinfos_by_relids(root, child_rel->relids,
7515 &nappinfos);
7516 foreach(lc, scanjoin_targets)
7517 {
7518 PathTarget *target = lfirst_node(PathTarget, lc);
7519
7520 target = copy_pathtarget(target);
7521 target->exprs = (List *)
7522 adjust_appendrel_attrs(root,
7523 (Node *) target->exprs,
7524 nappinfos, appinfos);
7525 child_scanjoin_targets = lappend(child_scanjoin_targets,
7526 target);
7527 }
7528 pfree(appinfos);
7529
7530 /* Recursion does the real work. */
7531 apply_scanjoin_target_to_paths(root, child_rel,
7532 child_scanjoin_targets,
7533 scanjoin_targets_contain_srfs,
7534 scanjoin_target_parallel_safe,
7535 tlist_same_exprs);
7536
7537 /* Save non-dummy children for Append paths. */
7538 if (!IS_DUMMY_REL(child_rel))
7539 live_children = lappend(live_children, child_rel);
7540 }
7541
7542 /* Build new paths for this relation by appending child paths. */
7543 add_paths_to_append_rel(root, rel, live_children);
7544 }
7545
7546 /*
7547 * Consider generating Gather or Gather Merge paths. We must only do this
7548 * if the relation is parallel safe, and we don't do it for child rels to
7549 * avoid creating multiple Gather nodes within the same plan. We must do
7550 * this after all paths have been generated and before set_cheapest, since
7551 * one of the generated paths may turn out to be the cheapest one.
7552 */
7553 if (rel->consider_parallel && !IS_OTHER_REL(rel))
7554 generate_useful_gather_paths(root, rel, false);
7555
7556 /*
7557 * Reassess which paths are the cheapest, now that we've potentially added
7558 * new Gather (or Gather Merge) and/or Append (or MergeAppend) paths to
7559 * this relation.
7560 */
7561 set_cheapest(rel);
7562 }
7563
7564 /*
7565 * create_partitionwise_grouping_paths
7566 *
7567 * If the partition keys of input relation are part of the GROUP BY clause, all
7568 * the rows belonging to a given group come from a single partition. This
7569 * allows aggregation/grouping over a partitioned relation to be broken down
7570 * into aggregation/grouping on each partition. This should be no worse, and
7571 * often better, than the normal approach.
7572 *
7573 * However, if the GROUP BY clause does not contain all the partition keys,
7574 * rows from a given group may be spread across multiple partitions. In that
7575 * case, we perform partial aggregation for each group, append the results,
7576 * and then finalize aggregation. This is less certain to win than the
7577 * previous case. It may win if the PartialAggregate stage greatly reduces
7578 * the number of groups, because fewer rows will pass through the Append node.
7579 * It may lose if we have lots of small groups.
7580 */
7581 static void
create_partitionwise_grouping_paths(PlannerInfo * root,RelOptInfo * input_rel,RelOptInfo * grouped_rel,RelOptInfo * partially_grouped_rel,const AggClauseCosts * agg_costs,grouping_sets_data * gd,PartitionwiseAggregateType patype,GroupPathExtraData * extra)7582 create_partitionwise_grouping_paths(PlannerInfo *root,
7583 RelOptInfo *input_rel,
7584 RelOptInfo *grouped_rel,
7585 RelOptInfo *partially_grouped_rel,
7586 const AggClauseCosts *agg_costs,
7587 grouping_sets_data *gd,
7588 PartitionwiseAggregateType patype,
7589 GroupPathExtraData *extra)
7590 {
7591 int nparts = input_rel->nparts;
7592 int cnt_parts;
7593 List *grouped_live_children = NIL;
7594 List *partially_grouped_live_children = NIL;
7595 PathTarget *target = grouped_rel->reltarget;
7596 bool partial_grouping_valid = true;
7597
7598 Assert(patype != PARTITIONWISE_AGGREGATE_NONE);
7599 Assert(patype != PARTITIONWISE_AGGREGATE_PARTIAL ||
7600 partially_grouped_rel != NULL);
7601
7602 /* Add paths for partitionwise aggregation/grouping. */
7603 for (cnt_parts = 0; cnt_parts < nparts; cnt_parts++)
7604 {
7605 RelOptInfo *child_input_rel = input_rel->part_rels[cnt_parts];
7606 PathTarget *child_target = copy_pathtarget(target);
7607 AppendRelInfo **appinfos;
7608 int nappinfos;
7609 GroupPathExtraData child_extra;
7610 RelOptInfo *child_grouped_rel;
7611 RelOptInfo *child_partially_grouped_rel;
7612
7613 /* Pruned or dummy children can be ignored. */
7614 if (child_input_rel == NULL || IS_DUMMY_REL(child_input_rel))
7615 continue;
7616
7617 /*
7618 * Copy the given "extra" structure as is and then override the
7619 * members specific to this child.
7620 */
7621 memcpy(&child_extra, extra, sizeof(child_extra));
7622
7623 appinfos = find_appinfos_by_relids(root, child_input_rel->relids,
7624 &nappinfos);
7625
7626 child_target->exprs = (List *)
7627 adjust_appendrel_attrs(root,
7628 (Node *) target->exprs,
7629 nappinfos, appinfos);
7630
7631 /* Translate havingQual and targetList. */
7632 child_extra.havingQual = (Node *)
7633 adjust_appendrel_attrs(root,
7634 extra->havingQual,
7635 nappinfos, appinfos);
7636 child_extra.targetList = (List *)
7637 adjust_appendrel_attrs(root,
7638 (Node *) extra->targetList,
7639 nappinfos, appinfos);
7640
7641 /*
7642 * extra->patype was the value computed for our parent rel; patype is
7643 * the value for this relation. For the child, our value is its
7644 * parent rel's value.
7645 */
7646 child_extra.patype = patype;
7647
7648 /*
7649 * Create grouping relation to hold fully aggregated grouping and/or
7650 * aggregation paths for the child.
7651 */
7652 child_grouped_rel = make_grouping_rel(root, child_input_rel,
7653 child_target,
7654 extra->target_parallel_safe,
7655 child_extra.havingQual);
7656
7657 /* Create grouping paths for this child relation. */
7658 create_ordinary_grouping_paths(root, child_input_rel,
7659 child_grouped_rel,
7660 agg_costs, gd, &child_extra,
7661 &child_partially_grouped_rel);
7662
7663 if (child_partially_grouped_rel)
7664 {
7665 partially_grouped_live_children =
7666 lappend(partially_grouped_live_children,
7667 child_partially_grouped_rel);
7668 }
7669 else
7670 partial_grouping_valid = false;
7671
7672 if (patype == PARTITIONWISE_AGGREGATE_FULL)
7673 {
7674 set_cheapest(child_grouped_rel);
7675 grouped_live_children = lappend(grouped_live_children,
7676 child_grouped_rel);
7677 }
7678
7679 pfree(appinfos);
7680 }
7681
7682 /*
7683 * Try to create append paths for partially grouped children. For full
7684 * partitionwise aggregation, we might have paths in the partial_pathlist
7685 * if parallel aggregation is possible. For partial partitionwise
7686 * aggregation, we may have paths in both pathlist and partial_pathlist.
7687 *
7688 * NB: We must have a partially grouped path for every child in order to
7689 * generate a partially grouped path for this relation.
7690 */
7691 if (partially_grouped_rel && partial_grouping_valid)
7692 {
7693 Assert(partially_grouped_live_children != NIL);
7694
7695 add_paths_to_append_rel(root, partially_grouped_rel,
7696 partially_grouped_live_children);
7697
7698 /*
7699 * We need call set_cheapest, since the finalization step will use the
7700 * cheapest path from the rel.
7701 */
7702 if (partially_grouped_rel->pathlist)
7703 set_cheapest(partially_grouped_rel);
7704 }
7705
7706 /* If possible, create append paths for fully grouped children. */
7707 if (patype == PARTITIONWISE_AGGREGATE_FULL)
7708 {
7709 Assert(grouped_live_children != NIL);
7710
7711 add_paths_to_append_rel(root, grouped_rel, grouped_live_children);
7712 }
7713 }
7714
7715 /*
7716 * group_by_has_partkey
7717 *
7718 * Returns true, if all the partition keys of the given relation are part of
7719 * the GROUP BY clauses, false otherwise.
7720 */
7721 static bool
group_by_has_partkey(RelOptInfo * input_rel,List * targetList,List * groupClause)7722 group_by_has_partkey(RelOptInfo *input_rel,
7723 List *targetList,
7724 List *groupClause)
7725 {
7726 List *groupexprs = get_sortgrouplist_exprs(groupClause, targetList);
7727 int cnt = 0;
7728 int partnatts;
7729
7730 /* Input relation should be partitioned. */
7731 Assert(input_rel->part_scheme);
7732
7733 /* Rule out early, if there are no partition keys present. */
7734 if (!input_rel->partexprs)
7735 return false;
7736
7737 partnatts = input_rel->part_scheme->partnatts;
7738
7739 for (cnt = 0; cnt < partnatts; cnt++)
7740 {
7741 List *partexprs = input_rel->partexprs[cnt];
7742 ListCell *lc;
7743 bool found = false;
7744
7745 foreach(lc, partexprs)
7746 {
7747 Expr *partexpr = lfirst(lc);
7748
7749 if (list_member(groupexprs, partexpr))
7750 {
7751 found = true;
7752 break;
7753 }
7754 }
7755
7756 /*
7757 * If none of the partition key expressions match with any of the
7758 * GROUP BY expression, return false.
7759 */
7760 if (!found)
7761 return false;
7762 }
7763
7764 return true;
7765 }
7766