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