Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * allpaths.c
4 : * Routines to find possible search paths for processing a query
5 : *
6 : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : * Portions Copyright (c) 1994, Regents of the University of California
8 : *
9 : *
10 : * IDENTIFICATION
11 : * src/backend/optimizer/path/allpaths.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 :
16 : #include "postgres.h"
17 :
18 : #include <limits.h>
19 : #include <math.h>
20 :
21 : #include "access/sysattr.h"
22 : #include "access/tsmapi.h"
23 : #include "catalog/pg_class.h"
24 : #include "catalog/pg_operator.h"
25 : #include "catalog/pg_proc.h"
26 : #include "foreign/fdwapi.h"
27 : #include "miscadmin.h"
28 : #include "nodes/makefuncs.h"
29 : #include "nodes/nodeFuncs.h"
30 : #include "nodes/supportnodes.h"
31 : #ifdef OPTIMIZER_DEBUG
32 : #include "nodes/print.h"
33 : #endif
34 : #include "optimizer/appendinfo.h"
35 : #include "optimizer/clauses.h"
36 : #include "optimizer/cost.h"
37 : #include "optimizer/geqo.h"
38 : #include "optimizer/optimizer.h"
39 : #include "optimizer/pathnode.h"
40 : #include "optimizer/paths.h"
41 : #include "optimizer/plancat.h"
42 : #include "optimizer/planner.h"
43 : #include "optimizer/prep.h"
44 : #include "optimizer/tlist.h"
45 : #include "parser/parse_clause.h"
46 : #include "parser/parsetree.h"
47 : #include "partitioning/partbounds.h"
48 : #include "port/pg_bitutils.h"
49 : #include "rewrite/rewriteManip.h"
50 : #include "utils/lsyscache.h"
51 : #include "utils/selfuncs.h"
52 :
53 :
54 : /* Bitmask flags for pushdown_safety_info.unsafeFlags */
55 : #define UNSAFE_HAS_VOLATILE_FUNC (1 << 0)
56 : #define UNSAFE_HAS_SET_FUNC (1 << 1)
57 : #define UNSAFE_NOTIN_DISTINCTON_CLAUSE (1 << 2)
58 : #define UNSAFE_NOTIN_PARTITIONBY_CLAUSE (1 << 3)
59 : #define UNSAFE_TYPE_MISMATCH (1 << 4)
60 :
61 : /* results of subquery_is_pushdown_safe */
62 : typedef struct pushdown_safety_info
63 : {
64 : unsigned char *unsafeFlags; /* bitmask of reasons why this target list
65 : * column is unsafe for qual pushdown, or 0 if
66 : * no reason. */
67 : bool unsafeVolatile; /* don't push down volatile quals */
68 : bool unsafeLeaky; /* don't push down leaky quals */
69 : } pushdown_safety_info;
70 :
71 : /* Return type for qual_is_pushdown_safe */
72 : typedef enum pushdown_safe_type
73 : {
74 : PUSHDOWN_UNSAFE, /* unsafe to push qual into subquery */
75 : PUSHDOWN_SAFE, /* safe to push qual into subquery */
76 : PUSHDOWN_WINDOWCLAUSE_RUNCOND, /* unsafe, but may work as WindowClause
77 : * run condition */
78 : } pushdown_safe_type;
79 :
80 : /* These parameters are set by GUC */
81 : bool enable_geqo = false; /* just in case GUC doesn't set it */
82 : bool enable_eager_aggregate = true;
83 : int geqo_threshold;
84 : double min_eager_agg_group_size;
85 : int min_parallel_table_scan_size;
86 : int min_parallel_index_scan_size;
87 :
88 : /* Hook for plugins to get control in set_rel_pathlist() */
89 : set_rel_pathlist_hook_type set_rel_pathlist_hook = NULL;
90 :
91 : /* Hook for plugins to replace standard_join_search() */
92 : join_search_hook_type join_search_hook = NULL;
93 :
94 :
95 : static void set_base_rel_consider_startup(PlannerInfo *root);
96 : static void set_base_rel_sizes(PlannerInfo *root);
97 : static void setup_simple_grouped_rels(PlannerInfo *root);
98 : static void set_base_rel_pathlists(PlannerInfo *root);
99 : static void set_rel_size(PlannerInfo *root, RelOptInfo *rel,
100 : Index rti, RangeTblEntry *rte);
101 : static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
102 : Index rti, RangeTblEntry *rte);
103 : static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel,
104 : RangeTblEntry *rte);
105 : static void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel);
106 : static void set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
107 : RangeTblEntry *rte);
108 : static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
109 : RangeTblEntry *rte);
110 : static void set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel,
111 : RangeTblEntry *rte);
112 : static void set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
113 : RangeTblEntry *rte);
114 : static void set_foreign_size(PlannerInfo *root, RelOptInfo *rel,
115 : RangeTblEntry *rte);
116 : static void set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel,
117 : RangeTblEntry *rte);
118 : static void set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
119 : Index rti, RangeTblEntry *rte);
120 : static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
121 : Index rti, RangeTblEntry *rte);
122 : static void set_grouped_rel_pathlist(PlannerInfo *root, RelOptInfo *rel);
123 : static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
124 : List *live_childrels,
125 : List *all_child_pathkeys);
126 : static Path *get_cheapest_parameterized_child_path(PlannerInfo *root,
127 : RelOptInfo *rel,
128 : Relids required_outer);
129 : static void accumulate_append_subpath(Path *path,
130 : List **subpaths,
131 : List **special_subpaths,
132 : List **child_append_relid_sets);
133 : static Path *get_singleton_append_subpath(Path *path,
134 : List **child_append_relid_sets);
135 : static void set_dummy_rel_pathlist(RelOptInfo *rel);
136 : static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
137 : Index rti, RangeTblEntry *rte);
138 : static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
139 : RangeTblEntry *rte);
140 : static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
141 : RangeTblEntry *rte);
142 : static void set_tablefunc_pathlist(PlannerInfo *root, RelOptInfo *rel,
143 : RangeTblEntry *rte);
144 : static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel,
145 : RangeTblEntry *rte);
146 : static void set_namedtuplestore_pathlist(PlannerInfo *root, RelOptInfo *rel,
147 : RangeTblEntry *rte);
148 : static void set_result_pathlist(PlannerInfo *root, RelOptInfo *rel,
149 : RangeTblEntry *rte);
150 : static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel,
151 : RangeTblEntry *rte);
152 : static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
153 : static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
154 : pushdown_safety_info *safetyInfo);
155 : static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
156 : pushdown_safety_info *safetyInfo);
157 : static void check_output_expressions(Query *subquery,
158 : pushdown_safety_info *safetyInfo);
159 : static void compare_tlist_datatypes(List *tlist, List *colTypes,
160 : pushdown_safety_info *safetyInfo);
161 : static bool targetIsInAllPartitionLists(TargetEntry *tle, Query *query);
162 : static pushdown_safe_type qual_is_pushdown_safe(Query *subquery, Index rti,
163 : RestrictInfo *rinfo,
164 : pushdown_safety_info *safetyInfo);
165 : static void subquery_push_qual(Query *subquery,
166 : RangeTblEntry *rte, Index rti, Node *qual);
167 : static void recurse_push_qual(Node *setOp, Query *topquery,
168 : RangeTblEntry *rte, Index rti, Node *qual);
169 : static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel,
170 : Bitmapset *extra_used_attrs);
171 :
172 :
173 : /*
174 : * make_one_rel
175 : * Finds all possible access paths for executing a query, returning a
176 : * single rel that represents the join of all base rels in the query.
177 : */
178 : RelOptInfo *
179 182975 : make_one_rel(PlannerInfo *root, List *joinlist)
180 : {
181 : RelOptInfo *rel;
182 : Index rti;
183 : double total_pages;
184 :
185 : /* Mark base rels as to whether we care about fast-start plans */
186 182975 : set_base_rel_consider_startup(root);
187 :
188 : /*
189 : * Compute size estimates and consider_parallel flags for each base rel.
190 : */
191 182975 : set_base_rel_sizes(root);
192 :
193 : /*
194 : * Build grouped relations for simple rels (i.e., base or "other" member
195 : * relations) where possible.
196 : */
197 182958 : setup_simple_grouped_rels(root);
198 :
199 : /*
200 : * We should now have size estimates for every actual table involved in
201 : * the query, and we also know which if any have been deleted from the
202 : * query by join removal, pruned by partition pruning, or eliminated by
203 : * constraint exclusion. So we can now compute total_table_pages.
204 : *
205 : * Note that appendrels are not double-counted here, even though we don't
206 : * bother to distinguish RelOptInfos for appendrel parents, because the
207 : * parents will have pages = 0.
208 : *
209 : * XXX if a table is self-joined, we will count it once per appearance,
210 : * which perhaps is the wrong thing ... but that's not completely clear,
211 : * and detecting self-joins here is difficult, so ignore it for now.
212 : */
213 182958 : total_pages = 0;
214 568100 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
215 : {
216 385142 : RelOptInfo *brel = root->simple_rel_array[rti];
217 :
218 : /* there may be empty slots corresponding to non-baserel RTEs */
219 385142 : if (brel == NULL)
220 91496 : continue;
221 :
222 : Assert(brel->relid == rti); /* sanity check on array */
223 :
224 293646 : if (IS_DUMMY_REL(brel))
225 748 : continue;
226 :
227 292898 : if (IS_SIMPLE_REL(brel))
228 292898 : total_pages += (double) brel->pages;
229 : }
230 182958 : root->total_table_pages = total_pages;
231 :
232 : /*
233 : * Generate access paths for each base rel.
234 : */
235 182958 : set_base_rel_pathlists(root);
236 :
237 : /*
238 : * Generate access paths for the entire join tree.
239 : */
240 182958 : rel = make_rel_from_joinlist(root, joinlist);
241 :
242 : /*
243 : * The result should join all and only the query's base + outer-join rels.
244 : */
245 : Assert(bms_equal(rel->relids, root->all_query_rels));
246 :
247 182958 : return rel;
248 : }
249 :
250 : /*
251 : * set_base_rel_consider_startup
252 : * Set the consider_[param_]startup flags for each base-relation entry.
253 : *
254 : * For the moment, we only deal with consider_param_startup here; because the
255 : * logic for consider_startup is pretty trivial and is the same for every base
256 : * relation, we just let build_simple_rel() initialize that flag correctly to
257 : * start with. If that logic ever gets more complicated it would probably
258 : * be better to move it here.
259 : */
260 : static void
261 182975 : set_base_rel_consider_startup(PlannerInfo *root)
262 : {
263 : /*
264 : * Since parameterized paths can only be used on the inside of a nestloop
265 : * join plan, there is usually little value in considering fast-start
266 : * plans for them. However, for relations that are on the RHS of a SEMI
267 : * or ANTI join, a fast-start plan can be useful because we're only going
268 : * to care about fetching one tuple anyway.
269 : *
270 : * To minimize growth of planning time, we currently restrict this to
271 : * cases where the RHS is a single base relation, not a join; there is no
272 : * provision for consider_param_startup to get set at all on joinrels.
273 : * Also we don't worry about appendrels. costsize.c's costing rules for
274 : * nestloop semi/antijoins don't consider such cases either.
275 : */
276 : ListCell *lc;
277 :
278 207814 : foreach(lc, root->join_info_list)
279 : {
280 24839 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
281 : int varno;
282 :
283 30984 : if ((sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI) &&
284 6145 : bms_get_singleton_member(sjinfo->syn_righthand, &varno))
285 : {
286 6030 : RelOptInfo *rel = find_base_rel(root, varno);
287 :
288 6030 : rel->consider_param_startup = true;
289 : }
290 : }
291 182975 : }
292 :
293 : /*
294 : * set_base_rel_sizes
295 : * Set the size estimates (rows and widths) for each base-relation entry.
296 : * Also determine whether to consider parallel paths for base relations.
297 : *
298 : * We do this in a separate pass over the base rels so that rowcount
299 : * estimates are available for parameterized path generation, and also so
300 : * that each rel's consider_parallel flag is set correctly before we begin to
301 : * generate paths.
302 : */
303 : static void
304 182975 : set_base_rel_sizes(PlannerInfo *root)
305 : {
306 : Index rti;
307 :
308 568118 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
309 : {
310 385160 : RelOptInfo *rel = root->simple_rel_array[rti];
311 : RangeTblEntry *rte;
312 :
313 : /* there may be empty slots corresponding to non-baserel RTEs */
314 385160 : if (rel == NULL)
315 91497 : continue;
316 :
317 : Assert(rel->relid == rti); /* sanity check on array */
318 :
319 : /* ignore RTEs that are "other rels" */
320 293663 : if (rel->reloptkind != RELOPT_BASEREL)
321 30862 : continue;
322 :
323 262801 : rte = root->simple_rte_array[rti];
324 :
325 : /*
326 : * If parallelism is allowable for this query in general, see whether
327 : * it's allowable for this rel in particular. We have to do this
328 : * before set_rel_size(), because (a) if this rel is an inheritance
329 : * parent, set_append_rel_size() will use and perhaps change the rel's
330 : * consider_parallel flag, and (b) for some RTE types, set_rel_size()
331 : * goes ahead and makes paths immediately.
332 : */
333 262801 : if (root->glob->parallelModeOK)
334 208579 : set_rel_consider_parallel(root, rel, rte);
335 :
336 262801 : set_rel_size(root, rel, rti, rte);
337 : }
338 182958 : }
339 :
340 : /*
341 : * setup_simple_grouped_rels
342 : * For each simple relation, build a grouped simple relation if eager
343 : * aggregation is possible and if this relation can produce grouped paths.
344 : */
345 : static void
346 182958 : setup_simple_grouped_rels(PlannerInfo *root)
347 : {
348 : Index rti;
349 :
350 : /*
351 : * If there are no aggregate expressions or grouping expressions, eager
352 : * aggregation is not possible.
353 : */
354 182958 : if (root->agg_clause_list == NIL ||
355 329 : root->group_expr_list == NIL)
356 182662 : return;
357 :
358 2537 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
359 : {
360 2241 : RelOptInfo *rel = root->simple_rel_array[rti];
361 :
362 : /* there may be empty slots corresponding to non-baserel RTEs */
363 2241 : if (rel == NULL)
364 707 : continue;
365 :
366 : Assert(rel->relid == rti); /* sanity check on array */
367 : Assert(IS_SIMPLE_REL(rel)); /* sanity check on rel */
368 :
369 1534 : (void) build_simple_grouped_rel(root, rel);
370 : }
371 : }
372 :
373 : /*
374 : * set_base_rel_pathlists
375 : * Finds all paths available for scanning each base-relation entry.
376 : * Sequential scan and any available indices are considered.
377 : * Each useful path is attached to its relation's 'pathlist' field.
378 : */
379 : static void
380 182958 : set_base_rel_pathlists(PlannerInfo *root)
381 : {
382 : Index rti;
383 :
384 568100 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
385 : {
386 385142 : RelOptInfo *rel = root->simple_rel_array[rti];
387 :
388 : /* there may be empty slots corresponding to non-baserel RTEs */
389 385142 : if (rel == NULL)
390 91496 : continue;
391 :
392 : Assert(rel->relid == rti); /* sanity check on array */
393 :
394 : /* ignore RTEs that are "other rels" */
395 293646 : if (rel->reloptkind != RELOPT_BASEREL)
396 30862 : continue;
397 :
398 262784 : set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
399 : }
400 182958 : }
401 :
402 : /*
403 : * set_rel_size
404 : * Set size estimates for a base relation
405 : */
406 : static void
407 293502 : set_rel_size(PlannerInfo *root, RelOptInfo *rel,
408 : Index rti, RangeTblEntry *rte)
409 : {
410 556303 : if (rel->reloptkind == RELOPT_BASEREL &&
411 262801 : relation_excluded_by_constraints(root, rel, rte))
412 : {
413 : /*
414 : * We proved we don't need to scan the rel via constraint exclusion,
415 : * so set up a single dummy path for it. Here we only check this for
416 : * regular baserels; if it's an otherrel, CE was already checked in
417 : * set_append_rel_size().
418 : *
419 : * In this case, we go ahead and set up the relation's path right away
420 : * instead of leaving it for set_rel_pathlist to do. This is because
421 : * we don't have a convention for marking a rel as dummy except by
422 : * assigning a dummy path to it.
423 : */
424 371 : set_dummy_rel_pathlist(rel);
425 : }
426 293131 : else if (rte->inh)
427 : {
428 : /* It's an "append relation", process accordingly */
429 13311 : set_append_rel_size(root, rel, rti, rte);
430 : }
431 : else
432 : {
433 279820 : switch (rel->rtekind)
434 : {
435 229039 : case RTE_RELATION:
436 229039 : if (rte->relkind == RELKIND_FOREIGN_TABLE)
437 : {
438 : /* Foreign table */
439 1237 : set_foreign_size(root, rel, rte);
440 : }
441 227802 : else if (rte->relkind == RELKIND_PARTITIONED_TABLE)
442 : {
443 : /*
444 : * We could get here if asked to scan a partitioned table
445 : * with ONLY. In that case we shouldn't scan any of the
446 : * partitions, so mark it as a dummy rel.
447 : */
448 20 : set_dummy_rel_pathlist(rel);
449 : }
450 227782 : else if (rte->tablesample != NULL)
451 : {
452 : /* Sampled relation */
453 153 : set_tablesample_rel_size(root, rel, rte);
454 : }
455 : else
456 : {
457 : /* Plain relation */
458 227629 : set_plain_rel_size(root, rel, rte);
459 : }
460 229022 : break;
461 13383 : case RTE_SUBQUERY:
462 :
463 : /*
464 : * Subqueries don't support making a choice between
465 : * parameterized and unparameterized paths, so just go ahead
466 : * and build their paths immediately.
467 : */
468 13383 : set_subquery_pathlist(root, rel, rti, rte);
469 13383 : break;
470 27429 : case RTE_FUNCTION:
471 27429 : set_function_size_estimates(root, rel);
472 27429 : break;
473 313 : case RTE_TABLEFUNC:
474 313 : set_tablefunc_size_estimates(root, rel);
475 313 : break;
476 4329 : case RTE_VALUES:
477 4329 : set_values_size_estimates(root, rel);
478 4329 : break;
479 2918 : case RTE_CTE:
480 :
481 : /*
482 : * CTEs don't support making a choice between parameterized
483 : * and unparameterized paths, so just go ahead and build their
484 : * paths immediately.
485 : */
486 2918 : if (rte->self_reference)
487 540 : set_worktable_pathlist(root, rel, rte);
488 : else
489 2378 : set_cte_pathlist(root, rel, rte);
490 2918 : break;
491 237 : case RTE_NAMEDTUPLESTORE:
492 : /* Might as well just build the path immediately */
493 237 : set_namedtuplestore_pathlist(root, rel, rte);
494 237 : break;
495 2172 : case RTE_RESULT:
496 : /* Might as well just build the path immediately */
497 2172 : set_result_pathlist(root, rel, rte);
498 2172 : break;
499 0 : default:
500 0 : elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind);
501 : break;
502 : }
503 : }
504 :
505 : /*
506 : * We insist that all non-dummy rels have a nonzero rowcount estimate.
507 : */
508 : Assert(rel->rows > 0 || IS_DUMMY_REL(rel));
509 293484 : }
510 :
511 : /*
512 : * set_rel_pathlist
513 : * Build access paths for a base relation
514 : */
515 : static void
516 293556 : set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
517 : Index rti, RangeTblEntry *rte)
518 : {
519 293556 : if (IS_DUMMY_REL(rel))
520 : {
521 : /* We already proved the relation empty, so nothing more to do */
522 : }
523 292880 : else if (rte->inh)
524 : {
525 : /* It's an "append relation", process accordingly */
526 13160 : set_append_rel_pathlist(root, rel, rti, rte);
527 : }
528 : else
529 : {
530 279720 : switch (rel->rtekind)
531 : {
532 229002 : case RTE_RELATION:
533 229002 : if (rte->relkind == RELKIND_FOREIGN_TABLE)
534 : {
535 : /* Foreign table */
536 1235 : set_foreign_pathlist(root, rel, rte);
537 : }
538 227767 : else if (rte->tablesample != NULL)
539 : {
540 : /* Sampled relation */
541 153 : set_tablesample_rel_pathlist(root, rel, rte);
542 : }
543 : else
544 : {
545 : /* Plain relation */
546 227614 : set_plain_rel_pathlist(root, rel, rte);
547 : }
548 229002 : break;
549 13320 : case RTE_SUBQUERY:
550 : /* Subquery --- fully handled during set_rel_size */
551 13320 : break;
552 27429 : case RTE_FUNCTION:
553 : /* RangeFunction */
554 27429 : set_function_pathlist(root, rel, rte);
555 27429 : break;
556 313 : case RTE_TABLEFUNC:
557 : /* Table Function */
558 313 : set_tablefunc_pathlist(root, rel, rte);
559 313 : break;
560 4329 : case RTE_VALUES:
561 : /* Values list */
562 4329 : set_values_pathlist(root, rel, rte);
563 4329 : break;
564 2918 : case RTE_CTE:
565 : /* CTE reference --- fully handled during set_rel_size */
566 2918 : break;
567 237 : case RTE_NAMEDTUPLESTORE:
568 : /* tuplestore reference --- fully handled during set_rel_size */
569 237 : break;
570 2172 : case RTE_RESULT:
571 : /* simple Result --- fully handled during set_rel_size */
572 2172 : break;
573 0 : default:
574 0 : elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind);
575 : break;
576 : }
577 : }
578 :
579 : /*
580 : * Allow a plugin to editorialize on the set of Paths for this base
581 : * relation. It could add new paths (such as CustomPaths) by calling
582 : * add_path(), or add_partial_path() if parallel aware. It could also
583 : * delete or modify paths added by the core code.
584 : */
585 293556 : if (set_rel_pathlist_hook)
586 0 : (*set_rel_pathlist_hook) (root, rel, rti, rte);
587 :
588 : /*
589 : * If this is a baserel, we should normally consider gathering any partial
590 : * paths we may have created for it. We have to do this after calling the
591 : * set_rel_pathlist_hook, else it cannot add partial paths to be included
592 : * here.
593 : *
594 : * However, if this is an inheritance child, skip it. Otherwise, we could
595 : * end up with a very large number of gather nodes, each trying to grab
596 : * its own pool of workers. Instead, we'll consider gathering partial
597 : * paths for the parent appendrel.
598 : *
599 : * Also, if this is the topmost scan/join rel, we postpone gathering until
600 : * the final scan/join targetlist is available (see grouping_planner).
601 : */
602 293556 : if (rel->reloptkind == RELOPT_BASEREL &&
603 262784 : !bms_equal(rel->relids, root->all_query_rels))
604 137408 : generate_useful_gather_paths(root, rel, false);
605 :
606 : /* Now find the cheapest of the paths for this rel */
607 293556 : set_cheapest(rel);
608 :
609 : /*
610 : * If a grouped relation for this rel exists, build partial aggregation
611 : * paths for it.
612 : *
613 : * Note that this can only happen after we've called set_cheapest() for
614 : * this base rel, because we need its cheapest paths.
615 : */
616 293556 : set_grouped_rel_pathlist(root, rel);
617 :
618 : #ifdef OPTIMIZER_DEBUG
619 : pprint(rel);
620 : #endif
621 293556 : }
622 :
623 : /*
624 : * set_plain_rel_size
625 : * Set size estimates for a plain relation (no subquery, no inheritance)
626 : */
627 : static void
628 227629 : set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
629 : {
630 : /*
631 : * Test any partial indexes of rel for applicability. We must do this
632 : * first since partial unique indexes can affect size estimates.
633 : */
634 227629 : check_index_predicates(root, rel);
635 :
636 : /* Mark rel with estimated output rows, width, etc */
637 227629 : set_baserel_size_estimates(root, rel);
638 227614 : }
639 :
640 : /*
641 : * If this relation could possibly be scanned from within a worker, then set
642 : * its consider_parallel flag.
643 : */
644 : static void
645 231777 : set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
646 : RangeTblEntry *rte)
647 : {
648 : /*
649 : * The flag has previously been initialized to false, so we can just
650 : * return if it becomes clear that we can't safely set it.
651 : */
652 : Assert(!rel->consider_parallel);
653 :
654 : /* Don't call this if parallelism is disallowed for the entire query. */
655 : Assert(root->glob->parallelModeOK);
656 :
657 : /* This should only be called for baserels and appendrel children. */
658 : Assert(IS_SIMPLE_REL(rel));
659 :
660 : /* Assorted checks based on rtekind. */
661 231777 : switch (rte->rtekind)
662 : {
663 198832 : case RTE_RELATION:
664 :
665 : /*
666 : * Currently, parallel workers can't access the leader's temporary
667 : * tables. We could possibly relax this if we wrote all of its
668 : * local buffers at the start of the query and made no changes
669 : * thereafter (maybe we could allow hint bit changes), and if we
670 : * taught the workers to read them. Writing a large number of
671 : * temporary buffers could be expensive, though, and we don't have
672 : * the rest of the necessary infrastructure right now anyway. So
673 : * for now, bail out if we see a temporary table.
674 : */
675 198832 : if (get_rel_persistence(rte->relid) == RELPERSISTENCE_TEMP)
676 4540 : return;
677 :
678 : /*
679 : * Table sampling can be pushed down to workers if the sample
680 : * function and its arguments are safe.
681 : */
682 194292 : if (rte->tablesample != NULL)
683 : {
684 165 : char proparallel = func_parallel(rte->tablesample->tsmhandler);
685 :
686 165 : if (proparallel != PROPARALLEL_SAFE)
687 18 : return;
688 147 : if (!is_parallel_safe(root, (Node *) rte->tablesample->args))
689 6 : return;
690 : }
691 :
692 : /*
693 : * Ask FDWs whether they can support performing a ForeignScan
694 : * within a worker. Most often, the answer will be no. For
695 : * example, if the nature of the FDW is such that it opens a TCP
696 : * connection with a remote server, each parallel worker would end
697 : * up with a separate connection, and these connections might not
698 : * be appropriately coordinated between workers and the leader.
699 : */
700 194268 : if (rte->relkind == RELKIND_FOREIGN_TABLE)
701 : {
702 : Assert(rel->fdwroutine);
703 782 : if (!rel->fdwroutine->IsForeignScanParallelSafe)
704 744 : return;
705 38 : if (!rel->fdwroutine->IsForeignScanParallelSafe(root, rel, rte))
706 0 : return;
707 : }
708 :
709 : /*
710 : * There are additional considerations for appendrels, which we'll
711 : * deal with in set_append_rel_size and set_append_rel_pathlist.
712 : * For now, just set consider_parallel based on the rel's own
713 : * quals and targetlist.
714 : */
715 193524 : break;
716 :
717 11530 : case RTE_SUBQUERY:
718 :
719 : /*
720 : * There's no intrinsic problem with scanning a subquery-in-FROM
721 : * (as distinct from a SubPlan or InitPlan) in a parallel worker.
722 : * If the subquery doesn't happen to have any parallel-safe paths,
723 : * then flagging it as consider_parallel won't change anything,
724 : * but that's true for plain tables, too. We must set
725 : * consider_parallel based on the rel's own quals and targetlist,
726 : * so that if a subquery path is parallel-safe but the quals and
727 : * projection we're sticking onto it are not, we correctly mark
728 : * the SubqueryScanPath as not parallel-safe. (Note that
729 : * set_subquery_pathlist() might push some of these quals down
730 : * into the subquery itself, but that doesn't change anything.)
731 : *
732 : * We can't push sub-select containing LIMIT/OFFSET to workers as
733 : * there is no guarantee that the row order will be fully
734 : * deterministic, and applying LIMIT/OFFSET will lead to
735 : * inconsistent results at the top-level. (In some cases, where
736 : * the result is ordered, we could relax this restriction. But it
737 : * doesn't currently seem worth expending extra effort to do so.)
738 : */
739 : {
740 11530 : Query *subquery = castNode(Query, rte->subquery);
741 :
742 11530 : if (limit_needed(subquery))
743 256 : return;
744 : }
745 11274 : break;
746 :
747 0 : case RTE_JOIN:
748 : /* Shouldn't happen; we're only considering baserels here. */
749 : Assert(false);
750 0 : return;
751 :
752 15193 : case RTE_FUNCTION:
753 : /* Check for parallel-restricted functions. */
754 15193 : if (!is_parallel_safe(root, (Node *) rte->functions))
755 6849 : return;
756 8344 : break;
757 :
758 313 : case RTE_TABLEFUNC:
759 : /* not parallel safe */
760 313 : return;
761 :
762 1444 : case RTE_VALUES:
763 : /* Check for parallel-restricted functions. */
764 1444 : if (!is_parallel_safe(root, (Node *) rte->values_lists))
765 6 : return;
766 1438 : break;
767 :
768 2296 : case RTE_CTE:
769 :
770 : /*
771 : * CTE tuplestores aren't shared among parallel workers, so we
772 : * force all CTE scans to happen in the leader. Also, populating
773 : * the CTE would require executing a subplan that's not available
774 : * in the worker, might be parallel-restricted, and must get
775 : * executed only once.
776 : */
777 2296 : return;
778 :
779 223 : case RTE_NAMEDTUPLESTORE:
780 :
781 : /*
782 : * tuplestore cannot be shared, at least without more
783 : * infrastructure to support that.
784 : */
785 223 : return;
786 :
787 1946 : case RTE_RESULT:
788 : /* RESULT RTEs, in themselves, are no problem. */
789 1946 : break;
790 0 : case RTE_GROUP:
791 : /* Shouldn't happen; we're only considering baserels here. */
792 : Assert(false);
793 0 : return;
794 : }
795 :
796 : /*
797 : * If there's anything in baserestrictinfo that's parallel-restricted, we
798 : * give up on parallelizing access to this relation. We could consider
799 : * instead postponing application of the restricted quals until we're
800 : * above all the parallelism in the plan tree, but it's not clear that
801 : * that would be a win in very many cases, and it might be tricky to make
802 : * outer join clauses work correctly. It would likely break equivalence
803 : * classes, too.
804 : */
805 216526 : if (!is_parallel_safe(root, (Node *) rel->baserestrictinfo))
806 15079 : return;
807 :
808 : /*
809 : * Likewise, if the relation's outputs are not parallel-safe, give up.
810 : * (Usually, they're just Vars, but sometimes they're not.)
811 : */
812 201447 : if (!is_parallel_safe(root, (Node *) rel->reltarget->exprs))
813 9 : return;
814 :
815 : /* We have a winner. */
816 201438 : rel->consider_parallel = true;
817 : }
818 :
819 : /*
820 : * set_plain_rel_pathlist
821 : * Build access paths for a plain relation (no subquery, no inheritance)
822 : */
823 : static void
824 227614 : set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
825 : {
826 : Relids required_outer;
827 :
828 : /*
829 : * We don't support pushing join clauses into the quals of a seqscan, but
830 : * it could still have required parameterization due to LATERAL refs in
831 : * its tlist.
832 : */
833 227614 : required_outer = rel->lateral_relids;
834 :
835 : /*
836 : * Consider TID scans.
837 : *
838 : * If create_tidscan_paths returns true, then a TID scan path is forced.
839 : * This happens when rel->baserestrictinfo contains CurrentOfExpr, because
840 : * the executor can't handle any other type of path for such queries.
841 : * Hence, we return without adding any other paths.
842 : */
843 227614 : if (create_tidscan_paths(root, rel))
844 202 : return;
845 :
846 : /* Consider sequential scan */
847 227412 : add_path(rel, create_seqscan_path(root, rel, required_outer, 0));
848 :
849 : /* If appropriate, consider parallel sequential scan */
850 227412 : if (rel->consider_parallel && required_outer == NULL)
851 171513 : create_plain_partial_paths(root, rel);
852 :
853 : /* Consider index scans */
854 227412 : create_index_paths(root, rel);
855 : }
856 :
857 : /*
858 : * create_plain_partial_paths
859 : * Build partial access paths for parallel scan of a plain relation
860 : */
861 : static void
862 171513 : create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel)
863 : {
864 : int parallel_workers;
865 :
866 171513 : parallel_workers = compute_parallel_worker(rel, rel->pages, -1,
867 : max_parallel_workers_per_gather);
868 :
869 : /* If any limit was set to zero, the user doesn't want a parallel scan. */
870 171513 : if (parallel_workers <= 0)
871 156897 : return;
872 :
873 : /* Add an unordered partial path based on a parallel sequential scan. */
874 14616 : add_partial_path(rel, create_seqscan_path(root, rel, NULL, parallel_workers));
875 : }
876 :
877 : /*
878 : * set_tablesample_rel_size
879 : * Set size estimates for a sampled relation
880 : */
881 : static void
882 153 : set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
883 : {
884 153 : TableSampleClause *tsc = rte->tablesample;
885 : TsmRoutine *tsm;
886 : BlockNumber pages;
887 : double tuples;
888 :
889 : /*
890 : * Test any partial indexes of rel for applicability. We must do this
891 : * first since partial unique indexes can affect size estimates.
892 : */
893 153 : check_index_predicates(root, rel);
894 :
895 : /*
896 : * Call the sampling method's estimation function to estimate the number
897 : * of pages it will read and the number of tuples it will return. (Note:
898 : * we assume the function returns sane values.)
899 : */
900 153 : tsm = GetTsmRoutine(tsc->tsmhandler);
901 153 : tsm->SampleScanGetSampleSize(root, rel, tsc->args,
902 : &pages, &tuples);
903 :
904 : /*
905 : * For the moment, because we will only consider a SampleScan path for the
906 : * rel, it's okay to just overwrite the pages and tuples estimates for the
907 : * whole relation. If we ever consider multiple path types for sampled
908 : * rels, we'll need more complication.
909 : */
910 153 : rel->pages = pages;
911 153 : rel->tuples = tuples;
912 :
913 : /* Mark rel with estimated output rows, width, etc */
914 153 : set_baserel_size_estimates(root, rel);
915 153 : }
916 :
917 : /*
918 : * set_tablesample_rel_pathlist
919 : * Build access paths for a sampled relation
920 : */
921 : static void
922 153 : set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
923 : {
924 : Relids required_outer;
925 : Path *path;
926 :
927 : /*
928 : * We don't support pushing join clauses into the quals of a samplescan,
929 : * but it could still have required parameterization due to LATERAL refs
930 : * in its tlist or TABLESAMPLE arguments.
931 : */
932 153 : required_outer = rel->lateral_relids;
933 :
934 : /* Consider sampled scan */
935 153 : path = create_samplescan_path(root, rel, required_outer);
936 :
937 : /*
938 : * If the sampling method does not support repeatable scans, we must avoid
939 : * plans that would scan the rel multiple times. Ideally, we'd simply
940 : * avoid putting the rel on the inside of a nestloop join; but adding such
941 : * a consideration to the planner seems like a great deal of complication
942 : * to support an uncommon usage of second-rate sampling methods. Instead,
943 : * if there is a risk that the query might perform an unsafe join, just
944 : * wrap the SampleScan in a Materialize node. We can check for joins by
945 : * counting the membership of all_query_rels (note that this correctly
946 : * counts inheritance trees as single rels). If we're inside a subquery,
947 : * we can't easily check whether a join might occur in the outer query, so
948 : * just assume one is possible.
949 : *
950 : * GetTsmRoutine is relatively expensive compared to the other tests here,
951 : * so check repeatable_across_scans last, even though that's a bit odd.
952 : */
953 293 : if ((root->query_level > 1 ||
954 140 : bms_membership(root->all_query_rels) != BMS_SINGLETON) &&
955 49 : !(GetTsmRoutine(rte->tablesample->tsmhandler)->repeatable_across_scans))
956 : {
957 4 : path = (Path *) create_material_path(rel, path, true);
958 : }
959 :
960 153 : add_path(rel, path);
961 :
962 : /* For the moment, at least, there are no other paths to consider */
963 153 : }
964 :
965 : /*
966 : * set_foreign_size
967 : * Set size estimates for a foreign table RTE
968 : */
969 : static void
970 1237 : set_foreign_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
971 : {
972 : /* Mark rel with estimated output rows, width, etc */
973 1237 : set_foreign_size_estimates(root, rel);
974 :
975 : /* Let FDW adjust the size estimates, if it can */
976 1237 : rel->fdwroutine->GetForeignRelSize(root, rel, rte->relid);
977 :
978 : /* ... but do not let it set the rows estimate to zero */
979 1235 : rel->rows = clamp_row_est(rel->rows);
980 :
981 : /*
982 : * Also, make sure rel->tuples is not insane relative to rel->rows.
983 : * Notably, this ensures sanity if pg_class.reltuples contains -1 and the
984 : * FDW doesn't do anything to replace that.
985 : */
986 1235 : rel->tuples = Max(rel->tuples, rel->rows);
987 1235 : }
988 :
989 : /*
990 : * set_foreign_pathlist
991 : * Build access paths for a foreign table RTE
992 : */
993 : static void
994 1235 : set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
995 : {
996 : /* Call the FDW's GetForeignPaths function to generate path(s) */
997 1235 : rel->fdwroutine->GetForeignPaths(root, rel, rte->relid);
998 1235 : }
999 :
1000 : /*
1001 : * set_append_rel_size
1002 : * Set size estimates for a simple "append relation"
1003 : *
1004 : * The passed-in rel and RTE represent the entire append relation. The
1005 : * relation's contents are computed by appending together the output of the
1006 : * individual member relations. Note that in the non-partitioned inheritance
1007 : * case, the first member relation is actually the same table as is mentioned
1008 : * in the parent RTE ... but it has a different RTE and RelOptInfo. This is
1009 : * a good thing because their outputs are not the same size.
1010 : */
1011 : static void
1012 13311 : set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
1013 : Index rti, RangeTblEntry *rte)
1014 : {
1015 13311 : int parentRTindex = rti;
1016 : bool has_live_children;
1017 : double parent_tuples;
1018 : double parent_rows;
1019 : double parent_size;
1020 : double *parent_attrsizes;
1021 : int nattrs;
1022 : ListCell *l;
1023 :
1024 : /* Guard against stack overflow due to overly deep inheritance tree. */
1025 13311 : check_stack_depth();
1026 :
1027 : Assert(IS_SIMPLE_REL(rel));
1028 :
1029 : /*
1030 : * If this is a partitioned baserel, set the consider_partitionwise_join
1031 : * flag; currently, we only consider partitionwise joins with the baserel
1032 : * if its targetlist doesn't contain a whole-row Var.
1033 : */
1034 13311 : if (enable_partitionwise_join &&
1035 2517 : rel->reloptkind == RELOPT_BASEREL &&
1036 2007 : rte->relkind == RELKIND_PARTITIONED_TABLE &&
1037 2007 : bms_is_empty(rel->attr_needed[InvalidAttrNumber - rel->min_attr]))
1038 1969 : rel->consider_partitionwise_join = true;
1039 :
1040 : /*
1041 : * Initialize to compute size estimates for whole append relation.
1042 : *
1043 : * We handle tuples estimates by setting "tuples" to the total number of
1044 : * tuples accumulated from each live child, rather than using "rows".
1045 : * Although an appendrel itself doesn't directly enforce any quals, its
1046 : * child relations may. Therefore, setting "tuples" equal to "rows" for
1047 : * an appendrel isn't always appropriate, and can lead to inaccurate cost
1048 : * estimates. For example, when estimating the number of distinct values
1049 : * from an appendrel, we would be unable to adjust the estimate based on
1050 : * the restriction selectivity (see estimate_num_groups).
1051 : *
1052 : * We handle width estimates by weighting the widths of different child
1053 : * rels proportionally to their number of rows. This is sensible because
1054 : * the use of width estimates is mainly to compute the total relation
1055 : * "footprint" if we have to sort or hash it. To do this, we sum the
1056 : * total equivalent size (in "double" arithmetic) and then divide by the
1057 : * total rowcount estimate. This is done separately for the total rel
1058 : * width and each attribute.
1059 : *
1060 : * Note: if you consider changing this logic, beware that child rels could
1061 : * have zero rows and/or width, if they were excluded by constraints.
1062 : */
1063 13311 : has_live_children = false;
1064 13311 : parent_tuples = 0;
1065 13311 : parent_rows = 0;
1066 13311 : parent_size = 0;
1067 13311 : nattrs = rel->max_attr - rel->min_attr + 1;
1068 13311 : parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
1069 :
1070 70206 : foreach(l, root->append_rel_list)
1071 : {
1072 56896 : AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
1073 : int childRTindex;
1074 : RangeTblEntry *childRTE;
1075 : RelOptInfo *childrel;
1076 : List *childrinfos;
1077 : ListCell *parentvars;
1078 : ListCell *childvars;
1079 : ListCell *lc;
1080 :
1081 : /* append_rel_list contains all append rels; ignore others */
1082 56896 : if (appinfo->parent_relid != parentRTindex)
1083 26264 : continue;
1084 :
1085 30806 : childRTindex = appinfo->child_relid;
1086 30806 : childRTE = root->simple_rte_array[childRTindex];
1087 :
1088 : /*
1089 : * The child rel's RelOptInfo was already created during
1090 : * add_other_rels_to_query.
1091 : */
1092 30806 : childrel = find_base_rel(root, childRTindex);
1093 : Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1094 :
1095 : /* We may have already proven the child to be dummy. */
1096 30806 : if (IS_DUMMY_REL(childrel))
1097 9 : continue;
1098 :
1099 : /*
1100 : * We have to copy the parent's targetlist and quals to the child,
1101 : * with appropriate substitution of variables. However, the
1102 : * baserestrictinfo quals were already copied/substituted when the
1103 : * child RelOptInfo was built. So we don't need any additional setup
1104 : * before applying constraint exclusion.
1105 : */
1106 30797 : if (relation_excluded_by_constraints(root, childrel, childRTE))
1107 : {
1108 : /*
1109 : * This child need not be scanned, so we can omit it from the
1110 : * appendrel.
1111 : */
1112 96 : set_dummy_rel_pathlist(childrel);
1113 96 : continue;
1114 : }
1115 :
1116 : /*
1117 : * Constraint exclusion failed, so copy the parent's join quals and
1118 : * targetlist to the child, with appropriate variable substitutions.
1119 : *
1120 : * We skip join quals that came from above outer joins that can null
1121 : * this rel, since they would be of no value while generating paths
1122 : * for the child. This saves some effort while processing the child
1123 : * rel, and it also avoids an implementation restriction in
1124 : * adjust_appendrel_attrs (it can't apply nullingrels to a non-Var).
1125 : */
1126 30701 : childrinfos = NIL;
1127 37301 : foreach(lc, rel->joininfo)
1128 : {
1129 6600 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1130 :
1131 6600 : if (!bms_overlap(rinfo->clause_relids, rel->nulling_relids))
1132 5439 : childrinfos = lappend(childrinfos,
1133 5439 : adjust_appendrel_attrs(root,
1134 : (Node *) rinfo,
1135 : 1, &appinfo));
1136 : }
1137 30701 : childrel->joininfo = childrinfos;
1138 :
1139 : /*
1140 : * Now for the child's targetlist.
1141 : *
1142 : * NB: the resulting childrel->reltarget->exprs may contain arbitrary
1143 : * expressions, which otherwise would not occur in a rel's targetlist.
1144 : * Code that might be looking at an appendrel child must cope with
1145 : * such. (Normally, a rel's targetlist would only include Vars and
1146 : * PlaceHolderVars.) XXX we do not bother to update the cost or width
1147 : * fields of childrel->reltarget; not clear if that would be useful.
1148 : */
1149 61402 : childrel->reltarget->exprs = (List *)
1150 30701 : adjust_appendrel_attrs(root,
1151 30701 : (Node *) rel->reltarget->exprs,
1152 : 1, &appinfo);
1153 :
1154 : /*
1155 : * We have to make child entries in the EquivalenceClass data
1156 : * structures as well. This is needed either if the parent
1157 : * participates in some eclass joins (because we will want to consider
1158 : * inner-indexscan joins on the individual children) or if the parent
1159 : * has useful pathkeys (because we should try to build MergeAppend
1160 : * paths that produce those sort orderings).
1161 : */
1162 30701 : if (rel->has_eclass_joins || has_useful_pathkeys(root, rel))
1163 19190 : add_child_rel_equivalences(root, appinfo, rel, childrel);
1164 30701 : childrel->has_eclass_joins = rel->has_eclass_joins;
1165 :
1166 : /*
1167 : * Note: we could compute appropriate attr_needed data for the child's
1168 : * variables, by transforming the parent's attr_needed through the
1169 : * translated_vars mapping. However, currently there's no need
1170 : * because attr_needed is only examined for base relations not
1171 : * otherrels. So we just leave the child's attr_needed empty.
1172 : */
1173 :
1174 : /*
1175 : * If we consider partitionwise joins with the parent rel, do the same
1176 : * for partitioned child rels.
1177 : *
1178 : * Note: here we abuse the consider_partitionwise_join flag by setting
1179 : * it for child rels that are not themselves partitioned. We do so to
1180 : * tell try_partitionwise_join() that the child rel is sufficiently
1181 : * valid to be used as a per-partition input, even if it later gets
1182 : * proven to be dummy. (It's not usable until we've set up the
1183 : * reltarget and EC entries, which we just did.)
1184 : */
1185 30701 : if (rel->consider_partitionwise_join)
1186 6651 : childrel->consider_partitionwise_join = true;
1187 :
1188 : /*
1189 : * If parallelism is allowable for this query in general, see whether
1190 : * it's allowable for this childrel in particular. But if we've
1191 : * already decided the appendrel is not parallel-safe as a whole,
1192 : * there's no point in considering parallelism for this child. For
1193 : * consistency, do this before calling set_rel_size() for the child.
1194 : */
1195 30701 : if (root->glob->parallelModeOK && rel->consider_parallel)
1196 23198 : set_rel_consider_parallel(root, childrel, childRTE);
1197 :
1198 : /*
1199 : * Compute the child's size.
1200 : */
1201 30701 : set_rel_size(root, childrel, childRTindex, childRTE);
1202 :
1203 : /*
1204 : * It is possible that constraint exclusion detected a contradiction
1205 : * within a child subquery, even though we didn't prove one above. If
1206 : * so, we can skip this child.
1207 : */
1208 30700 : if (IS_DUMMY_REL(childrel))
1209 69 : continue;
1210 :
1211 : /* We have at least one live child. */
1212 30631 : has_live_children = true;
1213 :
1214 : /*
1215 : * If any live child is not parallel-safe, treat the whole appendrel
1216 : * as not parallel-safe. In future we might be able to generate plans
1217 : * in which some children are farmed out to workers while others are
1218 : * not; but we don't have that today, so it's a waste to consider
1219 : * partial paths anywhere in the appendrel unless it's all safe.
1220 : * (Child rels visited before this one will be unmarked in
1221 : * set_append_rel_pathlist().)
1222 : */
1223 30631 : if (!childrel->consider_parallel)
1224 7861 : rel->consider_parallel = false;
1225 :
1226 : /*
1227 : * Accumulate size information from each live child.
1228 : */
1229 : Assert(childrel->rows > 0);
1230 :
1231 30631 : parent_tuples += childrel->tuples;
1232 30631 : parent_rows += childrel->rows;
1233 30631 : parent_size += childrel->reltarget->width * childrel->rows;
1234 :
1235 : /*
1236 : * Accumulate per-column estimates too. We need not do anything for
1237 : * PlaceHolderVars in the parent list. If child expression isn't a
1238 : * Var, or we didn't record a width estimate for it, we have to fall
1239 : * back on a datatype-based estimate.
1240 : *
1241 : * By construction, child's targetlist is 1-to-1 with parent's.
1242 : */
1243 103914 : forboth(parentvars, rel->reltarget->exprs,
1244 : childvars, childrel->reltarget->exprs)
1245 : {
1246 73283 : Var *parentvar = (Var *) lfirst(parentvars);
1247 73283 : Node *childvar = (Node *) lfirst(childvars);
1248 :
1249 73283 : if (IsA(parentvar, Var) && parentvar->varno == parentRTindex)
1250 : {
1251 66733 : int pndx = parentvar->varattno - rel->min_attr;
1252 66733 : int32 child_width = 0;
1253 :
1254 66733 : if (IsA(childvar, Var) &&
1255 64220 : ((Var *) childvar)->varno == childrel->relid)
1256 : {
1257 64175 : int cndx = ((Var *) childvar)->varattno - childrel->min_attr;
1258 :
1259 64175 : child_width = childrel->attr_widths[cndx];
1260 : }
1261 66733 : if (child_width <= 0)
1262 2558 : child_width = get_typavgwidth(exprType(childvar),
1263 : exprTypmod(childvar));
1264 : Assert(child_width > 0);
1265 66733 : parent_attrsizes[pndx] += child_width * childrel->rows;
1266 : }
1267 : }
1268 : }
1269 :
1270 13310 : if (has_live_children)
1271 : {
1272 : /*
1273 : * Save the finished size estimates.
1274 : */
1275 : int i;
1276 :
1277 : Assert(parent_rows > 0);
1278 13160 : rel->tuples = parent_tuples;
1279 13160 : rel->rows = parent_rows;
1280 13160 : rel->reltarget->width = rint(parent_size / parent_rows);
1281 122474 : for (i = 0; i < nattrs; i++)
1282 109314 : rel->attr_widths[i] = rint(parent_attrsizes[i] / parent_rows);
1283 :
1284 : /*
1285 : * Note that we leave rel->pages as zero; this is important to avoid
1286 : * double-counting the appendrel tree in total_table_pages.
1287 : */
1288 : }
1289 : else
1290 : {
1291 : /*
1292 : * All children were excluded by constraints, so mark the whole
1293 : * appendrel dummy. We must do this in this phase so that the rel's
1294 : * dummy-ness is visible when we generate paths for other rels.
1295 : */
1296 150 : set_dummy_rel_pathlist(rel);
1297 : }
1298 :
1299 13310 : pfree(parent_attrsizes);
1300 13310 : }
1301 :
1302 : /*
1303 : * set_append_rel_pathlist
1304 : * Build access paths for an "append relation"
1305 : */
1306 : static void
1307 13160 : set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
1308 : Index rti, RangeTblEntry *rte)
1309 : {
1310 13160 : int parentRTindex = rti;
1311 13160 : List *live_childrels = NIL;
1312 : ListCell *l;
1313 :
1314 : /*
1315 : * Generate access paths for each member relation, and remember the
1316 : * non-dummy children.
1317 : */
1318 69848 : foreach(l, root->append_rel_list)
1319 : {
1320 56688 : AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
1321 : int childRTindex;
1322 : RangeTblEntry *childRTE;
1323 : RelOptInfo *childrel;
1324 :
1325 : /* append_rel_list contains all append rels; ignore others */
1326 56688 : if (appinfo->parent_relid != parentRTindex)
1327 25916 : continue;
1328 :
1329 : /* Re-locate the child RTE and RelOptInfo */
1330 30772 : childRTindex = appinfo->child_relid;
1331 30772 : childRTE = root->simple_rte_array[childRTindex];
1332 30772 : childrel = root->simple_rel_array[childRTindex];
1333 :
1334 : /*
1335 : * If set_append_rel_size() decided the parent appendrel was
1336 : * parallel-unsafe at some point after visiting this child rel, we
1337 : * need to propagate the unsafety marking down to the child, so that
1338 : * we don't generate useless partial paths for it.
1339 : */
1340 30772 : if (!rel->consider_parallel)
1341 7962 : childrel->consider_parallel = false;
1342 :
1343 : /*
1344 : * Compute the child's access paths.
1345 : */
1346 30772 : set_rel_pathlist(root, childrel, childRTindex, childRTE);
1347 :
1348 : /*
1349 : * If child is dummy, ignore it.
1350 : */
1351 30772 : if (IS_DUMMY_REL(childrel))
1352 141 : continue;
1353 :
1354 : /*
1355 : * Child is live, so add it to the live_childrels list for use below.
1356 : */
1357 30631 : live_childrels = lappend(live_childrels, childrel);
1358 : }
1359 :
1360 : /* Add paths to the append relation. */
1361 13160 : add_paths_to_append_rel(root, rel, live_childrels);
1362 13160 : }
1363 :
1364 : /*
1365 : * set_grouped_rel_pathlist
1366 : * If a grouped relation for the given 'rel' exists, build partial
1367 : * aggregation paths for it.
1368 : */
1369 : static void
1370 293556 : set_grouped_rel_pathlist(PlannerInfo *root, RelOptInfo *rel)
1371 : {
1372 : RelOptInfo *grouped_rel;
1373 :
1374 : /*
1375 : * If there are no aggregate expressions or grouping expressions, eager
1376 : * aggregation is not possible.
1377 : */
1378 293556 : if (root->agg_clause_list == NIL ||
1379 1666 : root->group_expr_list == NIL)
1380 292022 : return;
1381 :
1382 : /* Add paths to the grouped base relation if one exists. */
1383 1534 : grouped_rel = rel->grouped_rel;
1384 1534 : if (grouped_rel)
1385 : {
1386 : Assert(IS_GROUPED_REL(grouped_rel));
1387 :
1388 293 : generate_grouped_paths(root, grouped_rel, rel);
1389 293 : set_cheapest(grouped_rel);
1390 : }
1391 : }
1392 :
1393 :
1394 : /*
1395 : * add_paths_to_append_rel
1396 : * Generate paths for the given append relation given the set of non-dummy
1397 : * child rels.
1398 : *
1399 : * The function collects all parameterizations and orderings supported by the
1400 : * non-dummy children. For every such parameterization or ordering, it creates
1401 : * an append path collecting one path from each non-dummy child with given
1402 : * parameterization or ordering. Similarly it collects partial paths from
1403 : * non-dummy children to create partial append paths.
1404 : */
1405 : void
1406 23985 : add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
1407 : List *live_childrels)
1408 : {
1409 23985 : AppendPathInput unparameterized = {0};
1410 23985 : AppendPathInput startup = {0};
1411 23985 : AppendPathInput partial_only = {0};
1412 23985 : AppendPathInput parallel_append = {0};
1413 23985 : bool unparameterized_valid = true;
1414 23985 : bool startup_valid = true;
1415 23985 : bool partial_only_valid = true;
1416 23985 : bool parallel_append_valid = true;
1417 23985 : List *all_child_pathkeys = NIL;
1418 23985 : List *all_child_outers = NIL;
1419 : ListCell *l;
1420 23985 : double partial_rows = -1;
1421 :
1422 : /* If appropriate, consider parallel append */
1423 23985 : parallel_append_valid = enable_parallel_append && rel->consider_parallel;
1424 :
1425 : /*
1426 : * For every non-dummy child, remember the cheapest path. Also, identify
1427 : * all pathkeys (orderings) and parameterizations (required_outer sets)
1428 : * available for the non-dummy member relations.
1429 : */
1430 77650 : foreach(l, live_childrels)
1431 : {
1432 53665 : RelOptInfo *childrel = lfirst(l);
1433 : ListCell *lcp;
1434 53665 : Path *cheapest_partial_path = NULL;
1435 :
1436 : /*
1437 : * If child has an unparameterized cheapest-total path, add that to
1438 : * the unparameterized Append path we are constructing for the parent.
1439 : * If not, there's no workable unparameterized path.
1440 : *
1441 : * With partitionwise aggregates, the child rel's pathlist may be
1442 : * empty, so don't assume that a path exists here.
1443 : */
1444 53665 : if (childrel->pathlist != NIL &&
1445 53665 : childrel->cheapest_total_path->param_info == NULL)
1446 53287 : accumulate_append_subpath(childrel->cheapest_total_path,
1447 : &unparameterized.subpaths, NULL, &unparameterized.child_append_relid_sets);
1448 : else
1449 378 : unparameterized_valid = false;
1450 :
1451 : /*
1452 : * When the planner is considering cheap startup plans, we'll also
1453 : * collect all the cheapest_startup_paths (if set) and build an
1454 : * AppendPath containing those as subpaths.
1455 : */
1456 53665 : if (rel->consider_startup && childrel->cheapest_startup_path != NULL)
1457 865 : {
1458 : Path *cheapest_path;
1459 :
1460 : /*
1461 : * With an indication of how many tuples the query should provide,
1462 : * the optimizer tries to choose the path optimal for that
1463 : * specific number of tuples.
1464 : */
1465 865 : if (root->tuple_fraction > 0.0)
1466 : cheapest_path =
1467 865 : get_cheapest_fractional_path(childrel,
1468 : root->tuple_fraction);
1469 : else
1470 0 : cheapest_path = childrel->cheapest_startup_path;
1471 :
1472 : /* cheapest_startup_path must not be a parameterized path. */
1473 : Assert(cheapest_path->param_info == NULL);
1474 865 : accumulate_append_subpath(cheapest_path,
1475 : &startup.subpaths,
1476 : NULL,
1477 : &startup.child_append_relid_sets);
1478 : }
1479 : else
1480 52800 : startup_valid = false;
1481 :
1482 :
1483 : /* Same idea, but for a partial plan. */
1484 53665 : if (childrel->partial_pathlist != NIL)
1485 : {
1486 32683 : cheapest_partial_path = linitial(childrel->partial_pathlist);
1487 32683 : accumulate_append_subpath(cheapest_partial_path,
1488 : &partial_only.partial_subpaths, NULL,
1489 : &partial_only.child_append_relid_sets);
1490 : }
1491 : else
1492 20982 : partial_only_valid = false;
1493 :
1494 : /*
1495 : * Same idea, but for a parallel append mixing partial and non-partial
1496 : * paths.
1497 : */
1498 53665 : if (parallel_append_valid)
1499 : {
1500 40644 : Path *nppath = NULL;
1501 :
1502 : nppath =
1503 40644 : get_cheapest_parallel_safe_total_inner(childrel->pathlist);
1504 :
1505 40644 : if (cheapest_partial_path == NULL && nppath == NULL)
1506 : {
1507 : /* Neither a partial nor a parallel-safe path? Forget it. */
1508 283 : parallel_append_valid = false;
1509 : }
1510 40361 : else if (nppath == NULL ||
1511 32458 : (cheapest_partial_path != NULL &&
1512 32458 : cheapest_partial_path->total_cost < nppath->total_cost))
1513 : {
1514 : /* Partial path is cheaper or the only option. */
1515 : Assert(cheapest_partial_path != NULL);
1516 32388 : accumulate_append_subpath(cheapest_partial_path,
1517 : ¶llel_append.partial_subpaths,
1518 : ¶llel_append.subpaths,
1519 : ¶llel_append.child_append_relid_sets);
1520 : }
1521 : else
1522 : {
1523 : /*
1524 : * Either we've got only a non-partial path, or we think that
1525 : * a single backend can execute the best non-partial path
1526 : * faster than all the parallel backends working together can
1527 : * execute the best partial path.
1528 : *
1529 : * It might make sense to be more aggressive here. Even if
1530 : * the best non-partial path is more expensive than the best
1531 : * partial path, it could still be better to choose the
1532 : * non-partial path if there are several such paths that can
1533 : * be given to different workers. For now, we don't try to
1534 : * figure that out.
1535 : */
1536 7973 : accumulate_append_subpath(nppath,
1537 : ¶llel_append.subpaths,
1538 : NULL,
1539 : ¶llel_append.child_append_relid_sets);
1540 : }
1541 : }
1542 :
1543 : /*
1544 : * Collect lists of all the available path orderings and
1545 : * parameterizations for all the children. We use these as a
1546 : * heuristic to indicate which sort orderings and parameterizations we
1547 : * should build Append and MergeAppend paths for.
1548 : */
1549 126210 : foreach(lcp, childrel->pathlist)
1550 : {
1551 72545 : Path *childpath = (Path *) lfirst(lcp);
1552 72545 : List *childkeys = childpath->pathkeys;
1553 72545 : Relids childouter = PATH_REQ_OUTER(childpath);
1554 :
1555 : /* Unsorted paths don't contribute to pathkey list */
1556 72545 : if (childkeys != NIL)
1557 : {
1558 : ListCell *lpk;
1559 18707 : bool found = false;
1560 :
1561 : /* Have we already seen this ordering? */
1562 18822 : foreach(lpk, all_child_pathkeys)
1563 : {
1564 12676 : List *existing_pathkeys = (List *) lfirst(lpk);
1565 :
1566 12676 : if (compare_pathkeys(existing_pathkeys,
1567 : childkeys) == PATHKEYS_EQUAL)
1568 : {
1569 12561 : found = true;
1570 12561 : break;
1571 : }
1572 : }
1573 18707 : if (!found)
1574 : {
1575 : /* No, so add it to all_child_pathkeys */
1576 6146 : all_child_pathkeys = lappend(all_child_pathkeys,
1577 : childkeys);
1578 : }
1579 : }
1580 :
1581 : /* Unparameterized paths don't contribute to param-set list */
1582 72545 : if (childouter)
1583 : {
1584 : ListCell *lco;
1585 3429 : bool found = false;
1586 :
1587 : /* Have we already seen this param set? */
1588 3843 : foreach(lco, all_child_outers)
1589 : {
1590 2540 : Relids existing_outers = (Relids) lfirst(lco);
1591 :
1592 2540 : if (bms_equal(existing_outers, childouter))
1593 : {
1594 2126 : found = true;
1595 2126 : break;
1596 : }
1597 : }
1598 3429 : if (!found)
1599 : {
1600 : /* No, so add it to all_child_outers */
1601 1303 : all_child_outers = lappend(all_child_outers,
1602 : childouter);
1603 : }
1604 : }
1605 : }
1606 : }
1607 :
1608 : /*
1609 : * If we found unparameterized paths for all children, build an unordered,
1610 : * unparameterized Append path for the rel. (Note: this is correct even
1611 : * if we have zero or one live subpath due to constraint exclusion.)
1612 : */
1613 23985 : if (unparameterized_valid)
1614 23823 : add_path(rel, (Path *) create_append_path(root, rel, unparameterized,
1615 : NIL, NULL, 0, false,
1616 : -1));
1617 :
1618 : /* build an AppendPath for the cheap startup paths, if valid */
1619 23985 : if (startup_valid)
1620 350 : add_path(rel, (Path *) create_append_path(root, rel, startup,
1621 : NIL, NULL, 0, false, -1));
1622 :
1623 : /*
1624 : * Consider an append of unordered, unparameterized partial paths. Make
1625 : * it parallel-aware if possible.
1626 : */
1627 23985 : if (partial_only_valid && partial_only.partial_subpaths != NIL)
1628 : {
1629 : AppendPath *appendpath;
1630 : ListCell *lc;
1631 14230 : int parallel_workers = 0;
1632 :
1633 : /* Find the highest number of workers requested for any subpath. */
1634 49150 : foreach(lc, partial_only.partial_subpaths)
1635 : {
1636 34920 : Path *path = lfirst(lc);
1637 :
1638 34920 : parallel_workers = Max(parallel_workers, path->parallel_workers);
1639 : }
1640 : Assert(parallel_workers > 0);
1641 :
1642 : /*
1643 : * If the use of parallel append is permitted, always request at least
1644 : * log2(# of children) workers. We assume it can be useful to have
1645 : * extra workers in this case because they will be spread out across
1646 : * the children. The precise formula is just a guess, but we don't
1647 : * want to end up with a radically different answer for a table with N
1648 : * partitions vs. an unpartitioned table with the same data, so the
1649 : * use of some kind of log-scaling here seems to make some sense.
1650 : */
1651 14230 : if (enable_parallel_append)
1652 : {
1653 14206 : parallel_workers = Max(parallel_workers,
1654 : pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1655 14206 : parallel_workers = Min(parallel_workers,
1656 : max_parallel_workers_per_gather);
1657 : }
1658 : Assert(parallel_workers > 0);
1659 :
1660 : /* Generate a partial append path. */
1661 14230 : appendpath = create_append_path(root, rel, partial_only,
1662 : NIL, NULL, parallel_workers,
1663 : enable_parallel_append,
1664 : -1);
1665 :
1666 : /*
1667 : * Make sure any subsequent partial paths use the same row count
1668 : * estimate.
1669 : */
1670 14230 : partial_rows = appendpath->path.rows;
1671 :
1672 : /* Add the path. */
1673 14230 : add_partial_path(rel, (Path *) appendpath);
1674 : }
1675 :
1676 : /*
1677 : * Consider a parallel-aware append using a mix of partial and non-partial
1678 : * paths. (This only makes sense if there's at least one child which has
1679 : * a non-partial path that is substantially cheaper than any partial path;
1680 : * otherwise, we should use the append path added in the previous step.)
1681 : */
1682 23985 : if (parallel_append_valid && parallel_append.subpaths != NIL)
1683 : {
1684 : AppendPath *appendpath;
1685 : ListCell *lc;
1686 2611 : int parallel_workers = 0;
1687 :
1688 : /*
1689 : * Find the highest number of workers requested for any partial
1690 : * subpath.
1691 : */
1692 3062 : foreach(lc, parallel_append.partial_subpaths)
1693 : {
1694 451 : Path *path = lfirst(lc);
1695 :
1696 451 : parallel_workers = Max(parallel_workers, path->parallel_workers);
1697 : }
1698 :
1699 : /*
1700 : * Same formula here as above. It's even more important in this
1701 : * instance because the non-partial paths won't contribute anything to
1702 : * the planned number of parallel workers.
1703 : */
1704 2611 : parallel_workers = Max(parallel_workers,
1705 : pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1706 2611 : parallel_workers = Min(parallel_workers,
1707 : max_parallel_workers_per_gather);
1708 : Assert(parallel_workers > 0);
1709 :
1710 2611 : appendpath = create_append_path(root, rel, parallel_append,
1711 : NIL, NULL, parallel_workers, true,
1712 : partial_rows);
1713 2611 : add_partial_path(rel, (Path *) appendpath);
1714 : }
1715 :
1716 : /*
1717 : * Also build unparameterized ordered append paths based on the collected
1718 : * list of child pathkeys.
1719 : */
1720 23985 : if (unparameterized_valid)
1721 23823 : generate_orderedappend_paths(root, rel, live_childrels,
1722 : all_child_pathkeys);
1723 :
1724 : /*
1725 : * Build Append paths for each parameterization seen among the child rels.
1726 : * (This may look pretty expensive, but in most cases of practical
1727 : * interest, the child rels will expose mostly the same parameterizations,
1728 : * so that not that many cases actually get considered here.)
1729 : *
1730 : * The Append node itself cannot enforce quals, so all qual checking must
1731 : * be done in the child paths. This means that to have a parameterized
1732 : * Append path, we must have the exact same parameterization for each
1733 : * child path; otherwise some children might be failing to check the
1734 : * moved-down quals. To make them match up, we can try to increase the
1735 : * parameterization of lesser-parameterized paths.
1736 : */
1737 25288 : foreach(l, all_child_outers)
1738 : {
1739 1303 : Relids required_outer = (Relids) lfirst(l);
1740 : ListCell *lcr;
1741 1303 : AppendPathInput parameterized = {0};
1742 1303 : bool parameterized_valid = true;
1743 :
1744 : /* Select the child paths for an Append with this parameterization */
1745 4780 : foreach(lcr, live_childrels)
1746 : {
1747 3483 : RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1748 : Path *subpath;
1749 :
1750 3483 : if (childrel->pathlist == NIL)
1751 : {
1752 : /* failed to make a suitable path for this child */
1753 0 : parameterized_valid = false;
1754 0 : break;
1755 : }
1756 :
1757 3483 : subpath = get_cheapest_parameterized_child_path(root,
1758 : childrel,
1759 : required_outer);
1760 3483 : if (subpath == NULL)
1761 : {
1762 : /* failed to make a suitable path for this child */
1763 6 : parameterized_valid = false;
1764 6 : break;
1765 : }
1766 3477 : accumulate_append_subpath(subpath, ¶meterized.subpaths, NULL,
1767 : ¶meterized.child_append_relid_sets);
1768 : }
1769 :
1770 1303 : if (parameterized_valid)
1771 1297 : add_path(rel, (Path *)
1772 1297 : create_append_path(root, rel, parameterized,
1773 : NIL, required_outer, 0, false,
1774 : -1));
1775 : }
1776 :
1777 : /*
1778 : * When there is only a single child relation, the Append path can inherit
1779 : * any ordering available for the child rel's path, so that it's useful to
1780 : * consider ordered partial paths. Above we only considered the cheapest
1781 : * partial path for each child, but let's also make paths using any
1782 : * partial paths that have pathkeys.
1783 : */
1784 23985 : if (list_length(live_childrels) == 1)
1785 : {
1786 7424 : RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
1787 :
1788 : /* skip the cheapest partial path, since we already used that above */
1789 7532 : for_each_from(l, childrel->partial_pathlist, 1)
1790 : {
1791 108 : Path *path = (Path *) lfirst(l);
1792 : AppendPath *appendpath;
1793 108 : AppendPathInput append = {0};
1794 :
1795 : /* skip paths with no pathkeys. */
1796 108 : if (path->pathkeys == NIL)
1797 0 : continue;
1798 :
1799 108 : append.partial_subpaths = list_make1(path);
1800 108 : appendpath = create_append_path(root, rel, append, NIL, NULL,
1801 : path->parallel_workers, true,
1802 : partial_rows);
1803 108 : add_partial_path(rel, (Path *) appendpath);
1804 : }
1805 : }
1806 23985 : }
1807 :
1808 : /*
1809 : * generate_orderedappend_paths
1810 : * Generate ordered append paths for an append relation
1811 : *
1812 : * Usually we generate MergeAppend paths here, but there are some special
1813 : * cases where we can generate simple Append paths, because the subpaths
1814 : * can provide tuples in the required order already.
1815 : *
1816 : * We generate a path for each ordering (pathkey list) appearing in
1817 : * all_child_pathkeys.
1818 : *
1819 : * We consider the cheapest-startup and cheapest-total cases, and also the
1820 : * cheapest-fractional case when not all tuples need to be retrieved. For each
1821 : * interesting ordering, we collect all the cheapest startup subpaths, all the
1822 : * cheapest total paths, and, if applicable, all the cheapest fractional paths,
1823 : * and build a suitable path for each case.
1824 : *
1825 : * We don't currently generate any parameterized ordered paths here. While
1826 : * it would not take much more code here to do so, it's very unclear that it
1827 : * is worth the planning cycles to investigate such paths: there's little
1828 : * use for an ordered path on the inside of a nestloop. In fact, it's likely
1829 : * that the current coding of add_path would reject such paths out of hand,
1830 : * because add_path gives no credit for sort ordering of parameterized paths,
1831 : * and a parameterized MergeAppend is going to be more expensive than the
1832 : * corresponding parameterized Append path. If we ever try harder to support
1833 : * parameterized mergejoin plans, it might be worth adding support for
1834 : * parameterized paths here to feed such joins. (See notes in
1835 : * optimizer/README for why that might not ever happen, though.)
1836 : */
1837 : static void
1838 23823 : generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
1839 : List *live_childrels,
1840 : List *all_child_pathkeys)
1841 : {
1842 : ListCell *lcp;
1843 23823 : List *partition_pathkeys = NIL;
1844 23823 : List *partition_pathkeys_desc = NIL;
1845 23823 : bool partition_pathkeys_partial = true;
1846 23823 : bool partition_pathkeys_desc_partial = true;
1847 :
1848 : /*
1849 : * Some partitioned table setups may allow us to use an Append node
1850 : * instead of a MergeAppend. This is possible in cases such as RANGE
1851 : * partitioned tables where it's guaranteed that an earlier partition must
1852 : * contain rows which come earlier in the sort order. To detect whether
1853 : * this is relevant, build pathkey descriptions of the partition ordering,
1854 : * for both forward and reverse scans.
1855 : */
1856 38540 : if (rel->part_scheme != NULL && IS_SIMPLE_REL(rel) &&
1857 14717 : partitions_are_ordered(rel->boundinfo, rel->live_parts))
1858 : {
1859 12261 : partition_pathkeys = build_partition_pathkeys(root, rel,
1860 : ForwardScanDirection,
1861 : &partition_pathkeys_partial);
1862 :
1863 12261 : partition_pathkeys_desc = build_partition_pathkeys(root, rel,
1864 : BackwardScanDirection,
1865 : &partition_pathkeys_desc_partial);
1866 :
1867 : /*
1868 : * You might think we should truncate_useless_pathkeys here, but
1869 : * allowing partition keys which are a subset of the query's pathkeys
1870 : * can often be useful. For example, consider a table partitioned by
1871 : * RANGE (a, b), and a query with ORDER BY a, b, c. If we have child
1872 : * paths that can produce the a, b, c ordering (perhaps via indexes on
1873 : * (a, b, c)) then it works to consider the appendrel output as
1874 : * ordered by a, b, c.
1875 : */
1876 : }
1877 :
1878 : /* Now consider each interesting sort ordering */
1879 29939 : foreach(lcp, all_child_pathkeys)
1880 : {
1881 6116 : List *pathkeys = (List *) lfirst(lcp);
1882 6116 : AppendPathInput startup = {0};
1883 6116 : AppendPathInput total = {0};
1884 6116 : AppendPathInput fractional = {0};
1885 6116 : bool startup_neq_total = false;
1886 6116 : bool fraction_neq_total = false;
1887 : bool match_partition_order;
1888 : bool match_partition_order_desc;
1889 : int end_index;
1890 : int first_index;
1891 : int direction;
1892 :
1893 : /*
1894 : * Determine if this sort ordering matches any partition pathkeys we
1895 : * have, for both ascending and descending partition order. If the
1896 : * partition pathkeys happen to be contained in pathkeys then it still
1897 : * works, as described above, providing that the partition pathkeys
1898 : * are complete and not just a prefix of the partition keys. (In such
1899 : * cases we'll be relying on the child paths to have sorted the
1900 : * lower-order columns of the required pathkeys.)
1901 : */
1902 6116 : match_partition_order =
1903 11054 : pathkeys_contained_in(pathkeys, partition_pathkeys) ||
1904 5042 : (!partition_pathkeys_partial &&
1905 104 : pathkeys_contained_in(partition_pathkeys, pathkeys));
1906 :
1907 15866 : match_partition_order_desc = !match_partition_order &&
1908 4884 : (pathkeys_contained_in(pathkeys, partition_pathkeys_desc) ||
1909 4898 : (!partition_pathkeys_desc_partial &&
1910 32 : pathkeys_contained_in(partition_pathkeys_desc, pathkeys)));
1911 :
1912 : /*
1913 : * When the required pathkeys match the reverse of the partition
1914 : * order, we must build the list of paths in reverse starting with the
1915 : * last matching partition first. We can get away without making any
1916 : * special cases for this in the loop below by just looping backward
1917 : * over the child relations in this case.
1918 : */
1919 6116 : if (match_partition_order_desc)
1920 : {
1921 : /* loop backward */
1922 24 : first_index = list_length(live_childrels) - 1;
1923 24 : end_index = -1;
1924 24 : direction = -1;
1925 :
1926 : /*
1927 : * Set this to true to save us having to check for
1928 : * match_partition_order_desc in the loop below.
1929 : */
1930 24 : match_partition_order = true;
1931 : }
1932 : else
1933 : {
1934 : /* for all other case, loop forward */
1935 6092 : first_index = 0;
1936 6092 : end_index = list_length(live_childrels);
1937 6092 : direction = 1;
1938 : }
1939 :
1940 : /* Select the child paths for this ordering... */
1941 21964 : for (int i = first_index; i != end_index; i += direction)
1942 : {
1943 15848 : RelOptInfo *childrel = list_nth_node(RelOptInfo, live_childrels, i);
1944 : Path *cheapest_startup,
1945 : *cheapest_total,
1946 15848 : *cheapest_fractional = NULL;
1947 :
1948 : /* Locate the right paths, if they are available. */
1949 : cheapest_startup =
1950 15848 : get_cheapest_path_for_pathkeys(childrel->pathlist,
1951 : pathkeys,
1952 : NULL,
1953 : STARTUP_COST,
1954 : false);
1955 : cheapest_total =
1956 15848 : get_cheapest_path_for_pathkeys(childrel->pathlist,
1957 : pathkeys,
1958 : NULL,
1959 : TOTAL_COST,
1960 : false);
1961 :
1962 : /*
1963 : * If we can't find any paths with the right order just use the
1964 : * cheapest-total path; we'll have to sort it later.
1965 : */
1966 15848 : if (cheapest_startup == NULL || cheapest_total == NULL)
1967 : {
1968 170 : cheapest_startup = cheapest_total =
1969 : childrel->cheapest_total_path;
1970 : /* Assert we do have an unparameterized path for this child */
1971 : Assert(cheapest_total->param_info == NULL);
1972 : }
1973 :
1974 : /*
1975 : * When building a fractional path, determine a cheapest
1976 : * fractional path for each child relation too. Looking at startup
1977 : * and total costs is not enough, because the cheapest fractional
1978 : * path may be dominated by two separate paths (one for startup,
1979 : * one for total).
1980 : *
1981 : * When needed (building fractional path), determine the cheapest
1982 : * fractional path too.
1983 : */
1984 15848 : if (root->tuple_fraction > 0)
1985 : {
1986 448 : double path_fraction = root->tuple_fraction;
1987 :
1988 : /*
1989 : * We should not have a dummy child relation here. However,
1990 : * we cannot use childrel->rows to compute the tuple fraction,
1991 : * as childrel can be an upper relation with an unset row
1992 : * estimate. Instead, we use the row estimate from the
1993 : * cheapest_total path, which should already have been forced
1994 : * to a sane value.
1995 : */
1996 : Assert(cheapest_total->rows > 0);
1997 :
1998 : /* Convert absolute limit to a path fraction */
1999 448 : if (path_fraction >= 1.0)
2000 448 : path_fraction /= cheapest_total->rows;
2001 :
2002 : cheapest_fractional =
2003 448 : get_cheapest_fractional_path_for_pathkeys(childrel->pathlist,
2004 : pathkeys,
2005 : NULL,
2006 : path_fraction);
2007 :
2008 : /*
2009 : * If we found no path with matching pathkeys, use the
2010 : * cheapest total path instead.
2011 : *
2012 : * XXX We might consider partially sorted paths too (with an
2013 : * incremental sort on top). But we'd have to build all the
2014 : * incremental paths, do the costing etc.
2015 : *
2016 : * Also, notice whether we actually have different paths for
2017 : * the "fractional" and "total" cases. This helps avoid
2018 : * generating two identical ordered append paths.
2019 : */
2020 448 : if (cheapest_fractional == NULL)
2021 22 : cheapest_fractional = cheapest_total;
2022 426 : else if (cheapest_fractional != cheapest_total)
2023 0 : fraction_neq_total = true;
2024 : }
2025 :
2026 : /*
2027 : * Notice whether we actually have different paths for the
2028 : * "cheapest" and "total" cases. This helps avoid generating two
2029 : * identical ordered append paths.
2030 : */
2031 15848 : if (cheapest_startup != cheapest_total)
2032 48 : startup_neq_total = true;
2033 :
2034 : /*
2035 : * Collect the appropriate child paths. The required logic varies
2036 : * for the Append and MergeAppend cases.
2037 : */
2038 15848 : if (match_partition_order)
2039 : {
2040 : /*
2041 : * We're going to make a plain Append path. We don't need
2042 : * most of what accumulate_append_subpath would do, but we do
2043 : * want to cut out child Appends or MergeAppends if they have
2044 : * just a single subpath (and hence aren't doing anything
2045 : * useful).
2046 : */
2047 : cheapest_startup =
2048 3345 : get_singleton_append_subpath(cheapest_startup,
2049 : &startup.child_append_relid_sets);
2050 : cheapest_total =
2051 3345 : get_singleton_append_subpath(cheapest_total,
2052 : &total.child_append_relid_sets);
2053 :
2054 3345 : startup.subpaths = lappend(startup.subpaths, cheapest_startup);
2055 3345 : total.subpaths = lappend(total.subpaths, cheapest_total);
2056 :
2057 3345 : if (cheapest_fractional)
2058 : {
2059 : cheapest_fractional =
2060 72 : get_singleton_append_subpath(cheapest_fractional,
2061 : &fractional.child_append_relid_sets);
2062 72 : fractional.subpaths =
2063 72 : lappend(fractional.subpaths, cheapest_fractional);
2064 : }
2065 : }
2066 : else
2067 : {
2068 : /*
2069 : * Otherwise, rely on accumulate_append_subpath to collect the
2070 : * child paths for the MergeAppend.
2071 : */
2072 12503 : accumulate_append_subpath(cheapest_startup,
2073 : &startup.subpaths, NULL,
2074 : &startup.child_append_relid_sets);
2075 12503 : accumulate_append_subpath(cheapest_total,
2076 : &total.subpaths, NULL,
2077 : &total.child_append_relid_sets);
2078 :
2079 12503 : if (cheapest_fractional)
2080 376 : accumulate_append_subpath(cheapest_fractional,
2081 : &fractional.subpaths, NULL,
2082 : &fractional.child_append_relid_sets);
2083 : }
2084 : }
2085 :
2086 : /* ... and build the Append or MergeAppend paths */
2087 6116 : if (match_partition_order)
2088 : {
2089 : /* We only need Append */
2090 1256 : add_path(rel, (Path *) create_append_path(root,
2091 : rel,
2092 : startup,
2093 : pathkeys,
2094 : NULL,
2095 : 0,
2096 : false,
2097 : -1));
2098 1256 : if (startup_neq_total)
2099 0 : add_path(rel, (Path *) create_append_path(root,
2100 : rel,
2101 : total,
2102 : pathkeys,
2103 : NULL,
2104 : 0,
2105 : false,
2106 : -1));
2107 :
2108 1256 : if (fractional.subpaths && fraction_neq_total)
2109 0 : add_path(rel, (Path *) create_append_path(root,
2110 : rel,
2111 : fractional,
2112 : pathkeys,
2113 : NULL,
2114 : 0,
2115 : false,
2116 : -1));
2117 : }
2118 : else
2119 : {
2120 : /* We need MergeAppend */
2121 4860 : add_path(rel, (Path *) create_merge_append_path(root,
2122 : rel,
2123 : startup.subpaths,
2124 : startup.child_append_relid_sets,
2125 : pathkeys,
2126 : NULL));
2127 4860 : if (startup_neq_total)
2128 30 : add_path(rel, (Path *) create_merge_append_path(root,
2129 : rel,
2130 : total.subpaths,
2131 : total.child_append_relid_sets,
2132 : pathkeys,
2133 : NULL));
2134 :
2135 4860 : if (fractional.subpaths && fraction_neq_total)
2136 0 : add_path(rel, (Path *) create_merge_append_path(root,
2137 : rel,
2138 : fractional.subpaths,
2139 : fractional.child_append_relid_sets,
2140 : pathkeys,
2141 : NULL));
2142 : }
2143 : }
2144 23823 : }
2145 :
2146 : /*
2147 : * get_cheapest_parameterized_child_path
2148 : * Get cheapest path for this relation that has exactly the requested
2149 : * parameterization.
2150 : *
2151 : * Returns NULL if unable to create such a path.
2152 : */
2153 : static Path *
2154 3483 : get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel,
2155 : Relids required_outer)
2156 : {
2157 : Path *cheapest;
2158 : ListCell *lc;
2159 :
2160 : /*
2161 : * Look up the cheapest existing path with no more than the needed
2162 : * parameterization. If it has exactly the needed parameterization, we're
2163 : * done.
2164 : */
2165 3483 : cheapest = get_cheapest_path_for_pathkeys(rel->pathlist,
2166 : NIL,
2167 : required_outer,
2168 : TOTAL_COST,
2169 : false);
2170 : Assert(cheapest != NULL);
2171 3483 : if (bms_equal(PATH_REQ_OUTER(cheapest), required_outer))
2172 3313 : return cheapest;
2173 :
2174 : /*
2175 : * Otherwise, we can "reparameterize" an existing path to match the given
2176 : * parameterization, which effectively means pushing down additional
2177 : * joinquals to be checked within the path's scan. However, some existing
2178 : * paths might check the available joinquals already while others don't;
2179 : * therefore, it's not clear which existing path will be cheapest after
2180 : * reparameterization. We have to go through them all and find out.
2181 : */
2182 170 : cheapest = NULL;
2183 590 : foreach(lc, rel->pathlist)
2184 : {
2185 420 : Path *path = (Path *) lfirst(lc);
2186 :
2187 : /* Can't use it if it needs more than requested parameterization */
2188 420 : if (!bms_is_subset(PATH_REQ_OUTER(path), required_outer))
2189 12 : continue;
2190 :
2191 : /*
2192 : * Reparameterization can only increase the path's cost, so if it's
2193 : * already more expensive than the current cheapest, forget it.
2194 : */
2195 636 : if (cheapest != NULL &&
2196 228 : compare_path_costs(cheapest, path, TOTAL_COST) <= 0)
2197 192 : continue;
2198 :
2199 : /* Reparameterize if needed, then recheck cost */
2200 216 : if (!bms_equal(PATH_REQ_OUTER(path), required_outer))
2201 : {
2202 178 : path = reparameterize_path(root, path, required_outer, 1.0);
2203 178 : if (path == NULL)
2204 16 : continue; /* failed to reparameterize this one */
2205 : Assert(bms_equal(PATH_REQ_OUTER(path), required_outer));
2206 :
2207 162 : if (cheapest != NULL &&
2208 0 : compare_path_costs(cheapest, path, TOTAL_COST) <= 0)
2209 0 : continue;
2210 : }
2211 :
2212 : /* We have a new best path */
2213 200 : cheapest = path;
2214 : }
2215 :
2216 : /* Return the best path, or NULL if we found no suitable candidate */
2217 170 : return cheapest;
2218 : }
2219 :
2220 : /*
2221 : * accumulate_append_subpath
2222 : * Add a subpath to the list being built for an Append or MergeAppend.
2223 : *
2224 : * It's possible that the child is itself an Append or MergeAppend path, in
2225 : * which case we can "cut out the middleman" and just add its child paths to
2226 : * our own list. (We don't try to do this earlier because we need to apply
2227 : * both levels of transformation to the quals.)
2228 : *
2229 : * Note that if we omit a child MergeAppend in this way, we are effectively
2230 : * omitting a sort step, which seems fine: if the parent is to be an Append,
2231 : * its result would be unsorted anyway, while if the parent is to be a
2232 : * MergeAppend, there's no point in a separate sort on a child.
2233 : *
2234 : * Normally, either path is a partial path and subpaths is a list of partial
2235 : * paths, or else path is a non-partial plan and subpaths is a list of those.
2236 : * However, if path is a parallel-aware Append, then we add its partial path
2237 : * children to subpaths and the rest to special_subpaths. If the latter is
2238 : * NULL, we don't flatten the path at all (unless it contains only partial
2239 : * paths).
2240 : */
2241 : static void
2242 156055 : accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths,
2243 : List **child_append_relid_sets)
2244 : {
2245 156055 : if (IsA(path, AppendPath))
2246 : {
2247 7894 : AppendPath *apath = (AppendPath *) path;
2248 :
2249 7894 : if (!apath->path.parallel_aware || apath->first_partial_path == 0)
2250 : {
2251 7726 : *subpaths = list_concat(*subpaths, apath->subpaths);
2252 7726 : *child_append_relid_sets =
2253 7726 : lappend(*child_append_relid_sets, path->parent->relids);
2254 7726 : *child_append_relid_sets =
2255 7726 : list_concat(*child_append_relid_sets,
2256 7726 : apath->child_append_relid_sets);
2257 7726 : return;
2258 : }
2259 168 : else if (special_subpaths != NULL)
2260 : {
2261 : List *new_special_subpaths;
2262 :
2263 : /* Split Parallel Append into partial and non-partial subpaths */
2264 84 : *subpaths = list_concat(*subpaths,
2265 84 : list_copy_tail(apath->subpaths,
2266 : apath->first_partial_path));
2267 84 : new_special_subpaths = list_copy_head(apath->subpaths,
2268 : apath->first_partial_path);
2269 84 : *special_subpaths = list_concat(*special_subpaths,
2270 : new_special_subpaths);
2271 84 : *child_append_relid_sets =
2272 84 : lappend(*child_append_relid_sets, path->parent->relids);
2273 84 : *child_append_relid_sets =
2274 84 : list_concat(*child_append_relid_sets,
2275 84 : apath->child_append_relid_sets);
2276 84 : return;
2277 : }
2278 : }
2279 148161 : else if (IsA(path, MergeAppendPath))
2280 : {
2281 538 : MergeAppendPath *mpath = (MergeAppendPath *) path;
2282 :
2283 538 : *subpaths = list_concat(*subpaths, mpath->subpaths);
2284 538 : *child_append_relid_sets =
2285 538 : lappend(*child_append_relid_sets, path->parent->relids);
2286 538 : *child_append_relid_sets =
2287 538 : list_concat(*child_append_relid_sets,
2288 538 : mpath->child_append_relid_sets);
2289 538 : return;
2290 : }
2291 :
2292 147707 : *subpaths = lappend(*subpaths, path);
2293 : }
2294 :
2295 : /*
2296 : * get_singleton_append_subpath
2297 : * Returns the single subpath of an Append/MergeAppend, or just
2298 : * return 'path' if it's not a single sub-path Append/MergeAppend.
2299 : *
2300 : * As a side effect, whenever we return a single subpath rather than the
2301 : * original path, add the relid sets for the original path to
2302 : * child_append_relid_sets, so that those relids don't entirely disappear
2303 : * from the final plan.
2304 : *
2305 : * Note: 'path' must not be a parallel-aware path.
2306 : */
2307 : static Path *
2308 6762 : get_singleton_append_subpath(Path *path, List **child_append_relid_sets)
2309 : {
2310 : Assert(!path->parallel_aware);
2311 :
2312 6762 : if (IsA(path, AppendPath))
2313 : {
2314 206 : AppendPath *apath = (AppendPath *) path;
2315 :
2316 206 : if (list_length(apath->subpaths) == 1)
2317 : {
2318 108 : *child_append_relid_sets =
2319 108 : lappend(*child_append_relid_sets, path->parent->relids);
2320 108 : *child_append_relid_sets =
2321 108 : list_concat(*child_append_relid_sets,
2322 108 : apath->child_append_relid_sets);
2323 108 : return (Path *) linitial(apath->subpaths);
2324 : }
2325 : }
2326 6556 : else if (IsA(path, MergeAppendPath))
2327 : {
2328 174 : MergeAppendPath *mpath = (MergeAppendPath *) path;
2329 :
2330 174 : if (list_length(mpath->subpaths) == 1)
2331 : {
2332 0 : *child_append_relid_sets =
2333 0 : lappend(*child_append_relid_sets, path->parent->relids);
2334 0 : *child_append_relid_sets =
2335 0 : list_concat(*child_append_relid_sets,
2336 0 : mpath->child_append_relid_sets);
2337 0 : return (Path *) linitial(mpath->subpaths);
2338 : }
2339 : }
2340 :
2341 6654 : return path;
2342 : }
2343 :
2344 : /*
2345 : * set_dummy_rel_pathlist
2346 : * Build a dummy path for a relation that's been excluded by constraints
2347 : *
2348 : * Rather than inventing a special "dummy" path type, we represent this as an
2349 : * AppendPath with no members (see also IS_DUMMY_APPEND/IS_DUMMY_REL macros).
2350 : *
2351 : * (See also mark_dummy_rel, which does basically the same thing, but is
2352 : * typically used to change a rel into dummy state after we already made
2353 : * paths for it.)
2354 : */
2355 : static void
2356 700 : set_dummy_rel_pathlist(RelOptInfo *rel)
2357 : {
2358 700 : AppendPathInput in = {0};
2359 :
2360 : /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
2361 700 : rel->rows = 0;
2362 700 : rel->reltarget->width = 0;
2363 :
2364 : /* Discard any pre-existing paths; no further need for them */
2365 700 : rel->pathlist = NIL;
2366 700 : rel->partial_pathlist = NIL;
2367 :
2368 : /* Set up the dummy path */
2369 700 : add_path(rel, (Path *) create_append_path(NULL, rel, in,
2370 : NIL, rel->lateral_relids,
2371 : 0, false, -1));
2372 :
2373 : /*
2374 : * We set the cheapest-path fields immediately, just in case they were
2375 : * pointing at some discarded path. This is redundant in current usage
2376 : * because set_rel_pathlist will do it later, but it's cheap so we keep it
2377 : * for safety and consistency with mark_dummy_rel.
2378 : */
2379 700 : set_cheapest(rel);
2380 700 : }
2381 :
2382 : /*
2383 : * find_window_run_conditions
2384 : * Determine if 'wfunc' is really a WindowFunc and call its prosupport
2385 : * function to determine the function's monotonic properties. We then
2386 : * see if 'opexpr' can be used to short-circuit execution.
2387 : *
2388 : * For example row_number() over (order by ...) always produces a value one
2389 : * higher than the previous. If someone has a window function in a subquery
2390 : * and has a WHERE clause in the outer query to filter rows <= 10, then we may
2391 : * as well stop processing the windowagg once the row number reaches 11. Here
2392 : * we check if 'opexpr' might help us to stop doing needless extra processing
2393 : * in WindowAgg nodes.
2394 : *
2395 : * '*keep_original' is set to true if the caller should also use 'opexpr' for
2396 : * its original purpose. This is set to false if the caller can assume that
2397 : * the run condition will handle all of the required filtering.
2398 : *
2399 : * Returns true if 'opexpr' was found to be useful and was added to the
2400 : * WindowFunc's runCondition. We also set *keep_original accordingly and add
2401 : * 'attno' to *run_cond_attrs offset by FirstLowInvalidHeapAttributeNumber.
2402 : * If the 'opexpr' cannot be used then we set *keep_original to true and
2403 : * return false.
2404 : */
2405 : static bool
2406 120 : find_window_run_conditions(Query *subquery, AttrNumber attno,
2407 : WindowFunc *wfunc, OpExpr *opexpr, bool wfunc_left,
2408 : bool *keep_original, Bitmapset **run_cond_attrs)
2409 : {
2410 : Oid prosupport;
2411 : Expr *otherexpr;
2412 : SupportRequestWFuncMonotonic req;
2413 : SupportRequestWFuncMonotonic *res;
2414 : WindowClause *wclause;
2415 : List *opinfos;
2416 : OpExpr *runopexpr;
2417 : Oid runoperator;
2418 : ListCell *lc;
2419 :
2420 120 : *keep_original = true;
2421 :
2422 120 : while (IsA(wfunc, RelabelType))
2423 0 : wfunc = (WindowFunc *) ((RelabelType *) wfunc)->arg;
2424 :
2425 : /* we can only work with window functions */
2426 120 : if (!IsA(wfunc, WindowFunc))
2427 12 : return false;
2428 :
2429 : /* can't use it if there are subplans in the WindowFunc */
2430 108 : if (contain_subplans((Node *) wfunc))
2431 3 : return false;
2432 :
2433 105 : prosupport = get_func_support(wfunc->winfnoid);
2434 :
2435 : /* Check if there's a support function for 'wfunc' */
2436 105 : if (!OidIsValid(prosupport))
2437 9 : return false;
2438 :
2439 : /* get the Expr from the other side of the OpExpr */
2440 96 : if (wfunc_left)
2441 84 : otherexpr = lsecond(opexpr->args);
2442 : else
2443 12 : otherexpr = linitial(opexpr->args);
2444 :
2445 : /*
2446 : * The value being compared must not change during the evaluation of the
2447 : * window partition.
2448 : */
2449 96 : if (!is_pseudo_constant_clause((Node *) otherexpr))
2450 0 : return false;
2451 :
2452 : /* find the window clause belonging to the window function */
2453 96 : wclause = (WindowClause *) list_nth(subquery->windowClause,
2454 96 : wfunc->winref - 1);
2455 :
2456 96 : req.type = T_SupportRequestWFuncMonotonic;
2457 96 : req.window_func = wfunc;
2458 96 : req.window_clause = wclause;
2459 :
2460 : /* call the support function */
2461 : res = (SupportRequestWFuncMonotonic *)
2462 96 : DatumGetPointer(OidFunctionCall1(prosupport,
2463 : PointerGetDatum(&req)));
2464 :
2465 : /*
2466 : * Nothing to do if the function is neither monotonically increasing nor
2467 : * monotonically decreasing.
2468 : */
2469 96 : if (res == NULL || res->monotonic == MONOTONICFUNC_NONE)
2470 0 : return false;
2471 :
2472 96 : runopexpr = NULL;
2473 96 : runoperator = InvalidOid;
2474 96 : opinfos = get_op_index_interpretation(opexpr->opno);
2475 :
2476 96 : foreach(lc, opinfos)
2477 : {
2478 96 : OpIndexInterpretation *opinfo = (OpIndexInterpretation *) lfirst(lc);
2479 96 : CompareType cmptype = opinfo->cmptype;
2480 :
2481 : /* handle < / <= */
2482 96 : if (cmptype == COMPARE_LT || cmptype == COMPARE_LE)
2483 : {
2484 : /*
2485 : * < / <= is supported for monotonically increasing functions in
2486 : * the form <wfunc> op <pseudoconst> and <pseudoconst> op <wfunc>
2487 : * for monotonically decreasing functions.
2488 : */
2489 69 : if ((wfunc_left && (res->monotonic & MONOTONICFUNC_INCREASING)) ||
2490 9 : (!wfunc_left && (res->monotonic & MONOTONICFUNC_DECREASING)))
2491 : {
2492 63 : *keep_original = false;
2493 63 : runopexpr = opexpr;
2494 63 : runoperator = opexpr->opno;
2495 : }
2496 69 : break;
2497 : }
2498 : /* handle > / >= */
2499 27 : else if (cmptype == COMPARE_GT || cmptype == COMPARE_GE)
2500 : {
2501 : /*
2502 : * > / >= is supported for monotonically decreasing functions in
2503 : * the form <wfunc> op <pseudoconst> and <pseudoconst> op <wfunc>
2504 : * for monotonically increasing functions.
2505 : */
2506 9 : if ((wfunc_left && (res->monotonic & MONOTONICFUNC_DECREASING)) ||
2507 6 : (!wfunc_left && (res->monotonic & MONOTONICFUNC_INCREASING)))
2508 : {
2509 9 : *keep_original = false;
2510 9 : runopexpr = opexpr;
2511 9 : runoperator = opexpr->opno;
2512 : }
2513 9 : break;
2514 : }
2515 : /* handle = */
2516 18 : else if (cmptype == COMPARE_EQ)
2517 : {
2518 : CompareType newcmptype;
2519 :
2520 : /*
2521 : * When both monotonically increasing and decreasing then the
2522 : * return value of the window function will be the same each time.
2523 : * We can simply use 'opexpr' as the run condition without
2524 : * modifying it.
2525 : */
2526 18 : if ((res->monotonic & MONOTONICFUNC_BOTH) == MONOTONICFUNC_BOTH)
2527 : {
2528 3 : *keep_original = false;
2529 3 : runopexpr = opexpr;
2530 3 : runoperator = opexpr->opno;
2531 3 : break;
2532 : }
2533 :
2534 : /*
2535 : * When monotonically increasing we make a qual with <wfunc> <=
2536 : * <value> or <value> >= <wfunc> in order to filter out values
2537 : * which are above the value in the equality condition. For
2538 : * monotonically decreasing functions we want to filter values
2539 : * below the value in the equality condition.
2540 : */
2541 15 : if (res->monotonic & MONOTONICFUNC_INCREASING)
2542 15 : newcmptype = wfunc_left ? COMPARE_LE : COMPARE_GE;
2543 : else
2544 0 : newcmptype = wfunc_left ? COMPARE_GE : COMPARE_LE;
2545 :
2546 : /* We must keep the original equality qual */
2547 15 : *keep_original = true;
2548 15 : runopexpr = opexpr;
2549 :
2550 : /* determine the operator to use for the WindowFuncRunCondition */
2551 15 : runoperator = get_opfamily_member_for_cmptype(opinfo->opfamily_id,
2552 : opinfo->oplefttype,
2553 : opinfo->oprighttype,
2554 : newcmptype);
2555 15 : break;
2556 : }
2557 : }
2558 :
2559 96 : if (runopexpr != NULL)
2560 : {
2561 : WindowFuncRunCondition *wfuncrc;
2562 :
2563 90 : wfuncrc = makeNode(WindowFuncRunCondition);
2564 90 : wfuncrc->opno = runoperator;
2565 90 : wfuncrc->inputcollid = runopexpr->inputcollid;
2566 90 : wfuncrc->wfunc_left = wfunc_left;
2567 90 : wfuncrc->arg = copyObject(otherexpr);
2568 :
2569 90 : wfunc->runCondition = lappend(wfunc->runCondition, wfuncrc);
2570 :
2571 : /* record that this attno was used in a run condition */
2572 90 : *run_cond_attrs = bms_add_member(*run_cond_attrs,
2573 : attno - FirstLowInvalidHeapAttributeNumber);
2574 90 : return true;
2575 : }
2576 :
2577 : /* unsupported OpExpr */
2578 6 : return false;
2579 : }
2580 :
2581 : /*
2582 : * check_and_push_window_quals
2583 : * Check if 'clause' is a qual that can be pushed into a WindowFunc
2584 : * as a 'runCondition' qual. These, when present, allow some unnecessary
2585 : * work to be skipped during execution.
2586 : *
2587 : * 'run_cond_attrs' will be populated with all targetlist resnos of subquery
2588 : * targets (offset by FirstLowInvalidHeapAttributeNumber) that we pushed
2589 : * window quals for.
2590 : *
2591 : * Returns true if the caller still must keep the original qual or false if
2592 : * the caller can safely ignore the original qual because the WindowAgg node
2593 : * will use the runCondition to stop returning tuples.
2594 : */
2595 : static bool
2596 126 : check_and_push_window_quals(Query *subquery, Node *clause,
2597 : Bitmapset **run_cond_attrs)
2598 : {
2599 126 : OpExpr *opexpr = (OpExpr *) clause;
2600 126 : bool keep_original = true;
2601 : Var *var1;
2602 : Var *var2;
2603 :
2604 : /* We're only able to use OpExprs with 2 operands */
2605 126 : if (!IsA(opexpr, OpExpr))
2606 9 : return true;
2607 :
2608 117 : if (list_length(opexpr->args) != 2)
2609 0 : return true;
2610 :
2611 : /*
2612 : * Currently, we restrict this optimization to strict OpExprs. The reason
2613 : * for this is that during execution, once the runcondition becomes false,
2614 : * we stop evaluating WindowFuncs. To avoid leaving around stale window
2615 : * function result values, we set them to NULL. Having only strict
2616 : * OpExprs here ensures that we properly filter out the tuples with NULLs
2617 : * in the top-level WindowAgg.
2618 : */
2619 117 : set_opfuncid(opexpr);
2620 117 : if (!func_strict(opexpr->opfuncid))
2621 0 : return true;
2622 :
2623 : /*
2624 : * Check for plain Vars that reference window functions in the subquery.
2625 : * If we find any, we'll ask find_window_run_conditions() if 'opexpr' can
2626 : * be used as part of the run condition.
2627 : */
2628 :
2629 : /* Check the left side of the OpExpr */
2630 117 : var1 = linitial(opexpr->args);
2631 117 : if (IsA(var1, Var) && var1->varattno > 0)
2632 : {
2633 99 : TargetEntry *tle = list_nth(subquery->targetList, var1->varattno - 1);
2634 99 : WindowFunc *wfunc = (WindowFunc *) tle->expr;
2635 :
2636 99 : if (find_window_run_conditions(subquery, tle->resno, wfunc, opexpr,
2637 : true, &keep_original, run_cond_attrs))
2638 81 : return keep_original;
2639 : }
2640 :
2641 : /* and check the right side */
2642 36 : var2 = lsecond(opexpr->args);
2643 36 : if (IsA(var2, Var) && var2->varattno > 0)
2644 : {
2645 21 : TargetEntry *tle = list_nth(subquery->targetList, var2->varattno - 1);
2646 21 : WindowFunc *wfunc = (WindowFunc *) tle->expr;
2647 :
2648 21 : if (find_window_run_conditions(subquery, tle->resno, wfunc, opexpr,
2649 : false, &keep_original, run_cond_attrs))
2650 9 : return keep_original;
2651 : }
2652 :
2653 27 : return true;
2654 : }
2655 :
2656 : /*
2657 : * set_subquery_pathlist
2658 : * Generate SubqueryScan access paths for a subquery RTE
2659 : *
2660 : * We don't currently support generating parameterized paths for subqueries
2661 : * by pushing join clauses down into them; it seems too expensive to re-plan
2662 : * the subquery multiple times to consider different alternatives.
2663 : * (XXX that could stand to be reconsidered, now that we use Paths.)
2664 : * So the paths made here will be parameterized if the subquery contains
2665 : * LATERAL references, otherwise not. As long as that's true, there's no need
2666 : * for a separate set_subquery_size phase: just make the paths right away.
2667 : */
2668 : static void
2669 13383 : set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
2670 : Index rti, RangeTblEntry *rte)
2671 : {
2672 13383 : Query *parse = root->parse;
2673 13383 : Query *subquery = rte->subquery;
2674 : bool trivial_pathtarget;
2675 : Relids required_outer;
2676 : pushdown_safety_info safetyInfo;
2677 : double tuple_fraction;
2678 : RelOptInfo *sub_final_rel;
2679 13383 : Bitmapset *run_cond_attrs = NULL;
2680 : ListCell *lc;
2681 : char *plan_name;
2682 :
2683 : /*
2684 : * Must copy the Query so that planning doesn't mess up the RTE contents
2685 : * (really really need to fix the planner to not scribble on its input,
2686 : * someday ... but see remove_unused_subquery_outputs to start with).
2687 : */
2688 13383 : subquery = copyObject(subquery);
2689 :
2690 : /*
2691 : * If it's a LATERAL subquery, it might contain some Vars of the current
2692 : * query level, requiring it to be treated as parameterized, even though
2693 : * we don't support pushing down join quals into subqueries.
2694 : */
2695 13383 : required_outer = rel->lateral_relids;
2696 :
2697 : /*
2698 : * Zero out result area for subquery_is_pushdown_safe, so that it can set
2699 : * flags as needed while recursing. In particular, we need a workspace
2700 : * for keeping track of the reasons why columns are unsafe to reference.
2701 : * These reasons are stored in the bits inside unsafeFlags[i] when we
2702 : * discover reasons that column i of the subquery is unsafe to be used in
2703 : * a pushed-down qual.
2704 : */
2705 13383 : memset(&safetyInfo, 0, sizeof(safetyInfo));
2706 13383 : safetyInfo.unsafeFlags = (unsigned char *)
2707 13383 : palloc0((list_length(subquery->targetList) + 1) * sizeof(unsigned char));
2708 :
2709 : /*
2710 : * If the subquery has the "security_barrier" flag, it means the subquery
2711 : * originated from a view that must enforce row-level security. Then we
2712 : * must not push down quals that contain leaky functions. (Ideally this
2713 : * would be checked inside subquery_is_pushdown_safe, but since we don't
2714 : * currently pass the RTE to that function, we must do it here.)
2715 : */
2716 13383 : safetyInfo.unsafeLeaky = rte->security_barrier;
2717 :
2718 : /*
2719 : * If there are any restriction clauses that have been attached to the
2720 : * subquery relation, consider pushing them down to become WHERE or HAVING
2721 : * quals of the subquery itself. This transformation is useful because it
2722 : * may allow us to generate a better plan for the subquery than evaluating
2723 : * all the subquery output rows and then filtering them.
2724 : *
2725 : * There are several cases where we cannot push down clauses. Restrictions
2726 : * involving the subquery are checked by subquery_is_pushdown_safe().
2727 : * Restrictions on individual clauses are checked by
2728 : * qual_is_pushdown_safe(). Also, we don't want to push down
2729 : * pseudoconstant clauses; better to have the gating node above the
2730 : * subquery.
2731 : *
2732 : * Non-pushed-down clauses will get evaluated as qpquals of the
2733 : * SubqueryScan node.
2734 : *
2735 : * XXX Are there any cases where we want to make a policy decision not to
2736 : * push down a pushable qual, because it'd result in a worse plan?
2737 : */
2738 14944 : if (rel->baserestrictinfo != NIL &&
2739 1561 : subquery_is_pushdown_safe(subquery, subquery, &safetyInfo))
2740 : {
2741 : /* OK to consider pushing down individual quals */
2742 1488 : List *upperrestrictlist = NIL;
2743 : ListCell *l;
2744 :
2745 3998 : foreach(l, rel->baserestrictinfo)
2746 : {
2747 2510 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2748 2510 : Node *clause = (Node *) rinfo->clause;
2749 :
2750 2510 : if (rinfo->pseudoconstant)
2751 : {
2752 2 : upperrestrictlist = lappend(upperrestrictlist, rinfo);
2753 2 : continue;
2754 : }
2755 :
2756 2508 : switch (qual_is_pushdown_safe(subquery, rti, rinfo, &safetyInfo))
2757 : {
2758 1956 : case PUSHDOWN_SAFE:
2759 : /* Push it down */
2760 1956 : subquery_push_qual(subquery, rte, rti, clause);
2761 1956 : break;
2762 :
2763 126 : case PUSHDOWN_WINDOWCLAUSE_RUNCOND:
2764 :
2765 : /*
2766 : * Since we can't push the qual down into the subquery,
2767 : * check if it happens to reference a window function. If
2768 : * so then it might be useful to use for the WindowAgg's
2769 : * runCondition.
2770 : */
2771 252 : if (!subquery->hasWindowFuncs ||
2772 126 : check_and_push_window_quals(subquery, clause,
2773 : &run_cond_attrs))
2774 : {
2775 : /*
2776 : * subquery has no window funcs or the clause is not a
2777 : * suitable window run condition qual or it is, but
2778 : * the original must also be kept in the upper query.
2779 : */
2780 51 : upperrestrictlist = lappend(upperrestrictlist, rinfo);
2781 : }
2782 126 : break;
2783 :
2784 426 : case PUSHDOWN_UNSAFE:
2785 426 : upperrestrictlist = lappend(upperrestrictlist, rinfo);
2786 426 : break;
2787 : }
2788 : }
2789 1488 : rel->baserestrictinfo = upperrestrictlist;
2790 : /* We don't bother recomputing baserestrict_min_security */
2791 : }
2792 :
2793 13383 : pfree(safetyInfo.unsafeFlags);
2794 :
2795 : /*
2796 : * The upper query might not use all the subquery's output columns; if
2797 : * not, we can simplify. Pass the attributes that were pushed down into
2798 : * WindowAgg run conditions to ensure we don't accidentally think those
2799 : * are unused.
2800 : */
2801 13383 : remove_unused_subquery_outputs(subquery, rel, run_cond_attrs);
2802 :
2803 : /*
2804 : * We can safely pass the outer tuple_fraction down to the subquery if the
2805 : * outer level has no joining, aggregation, or sorting to do. Otherwise
2806 : * we'd better tell the subquery to plan for full retrieval. (XXX This
2807 : * could probably be made more intelligent ...)
2808 : */
2809 13383 : if (parse->hasAggs ||
2810 9832 : parse->groupClause ||
2811 9823 : parse->groupingSets ||
2812 9823 : root->hasHavingQual ||
2813 9823 : parse->distinctClause ||
2814 13245 : parse->sortClause ||
2815 3686 : bms_membership(root->all_baserels) == BMS_MULTIPLE)
2816 10707 : tuple_fraction = 0.0; /* default case */
2817 : else
2818 2676 : tuple_fraction = root->tuple_fraction;
2819 :
2820 : /* plan_params should not be in use in current query level */
2821 : Assert(root->plan_params == NIL);
2822 :
2823 : /* Generate a subroot and Paths for the subquery */
2824 13383 : plan_name = choose_plan_name(root->glob, rte->eref->aliasname, false);
2825 13383 : rel->subroot = subquery_planner(root->glob, subquery, plan_name,
2826 : root, false, tuple_fraction, NULL);
2827 :
2828 : /* Isolate the params needed by this specific subplan */
2829 13383 : rel->subplan_params = root->plan_params;
2830 13383 : root->plan_params = NIL;
2831 :
2832 : /*
2833 : * It's possible that constraint exclusion proved the subquery empty. If
2834 : * so, it's desirable to produce an unadorned dummy path so that we will
2835 : * recognize appropriate optimizations at this query level.
2836 : */
2837 13383 : sub_final_rel = fetch_upper_rel(rel->subroot, UPPERREL_FINAL, NULL);
2838 :
2839 13383 : if (IS_DUMMY_REL(sub_final_rel))
2840 : {
2841 63 : set_dummy_rel_pathlist(rel);
2842 63 : return;
2843 : }
2844 :
2845 : /*
2846 : * Mark rel with estimated output rows, width, etc. Note that we have to
2847 : * do this before generating outer-query paths, else cost_subqueryscan is
2848 : * not happy.
2849 : */
2850 13320 : set_subquery_size_estimates(root, rel);
2851 :
2852 : /*
2853 : * Also detect whether the reltarget is trivial, so that we can pass that
2854 : * info to cost_subqueryscan (rather than re-deriving it multiple times).
2855 : * It's trivial if it fetches all the subplan output columns in order.
2856 : */
2857 13320 : if (list_length(rel->reltarget->exprs) != list_length(subquery->targetList))
2858 8290 : trivial_pathtarget = false;
2859 : else
2860 : {
2861 5030 : trivial_pathtarget = true;
2862 16342 : foreach(lc, rel->reltarget->exprs)
2863 : {
2864 11461 : Node *node = (Node *) lfirst(lc);
2865 : Var *var;
2866 :
2867 11461 : if (!IsA(node, Var))
2868 : {
2869 0 : trivial_pathtarget = false;
2870 0 : break;
2871 : }
2872 11461 : var = (Var *) node;
2873 11461 : if (var->varno != rti ||
2874 11461 : var->varattno != foreach_current_index(lc) + 1)
2875 : {
2876 149 : trivial_pathtarget = false;
2877 149 : break;
2878 : }
2879 : }
2880 : }
2881 :
2882 : /*
2883 : * For each Path that subquery_planner produced, make a SubqueryScanPath
2884 : * in the outer query.
2885 : */
2886 27730 : foreach(lc, sub_final_rel->pathlist)
2887 : {
2888 14410 : Path *subpath = (Path *) lfirst(lc);
2889 : List *pathkeys;
2890 :
2891 : /* Convert subpath's pathkeys to outer representation */
2892 14410 : pathkeys = convert_subquery_pathkeys(root,
2893 : rel,
2894 : subpath->pathkeys,
2895 : make_tlist_from_pathtarget(subpath->pathtarget));
2896 :
2897 : /* Generate outer path using this subpath */
2898 14410 : add_path(rel, (Path *)
2899 14410 : create_subqueryscan_path(root, rel, subpath,
2900 : trivial_pathtarget,
2901 : pathkeys, required_outer));
2902 : }
2903 :
2904 : /* If outer rel allows parallelism, do same for partial paths. */
2905 13320 : if (rel->consider_parallel && bms_is_empty(required_outer))
2906 : {
2907 : /* If consider_parallel is false, there should be no partial paths. */
2908 : Assert(sub_final_rel->consider_parallel ||
2909 : sub_final_rel->partial_pathlist == NIL);
2910 :
2911 : /* Same for partial paths. */
2912 7881 : foreach(lc, sub_final_rel->partial_pathlist)
2913 : {
2914 27 : Path *subpath = (Path *) lfirst(lc);
2915 : List *pathkeys;
2916 :
2917 : /* Convert subpath's pathkeys to outer representation */
2918 27 : pathkeys = convert_subquery_pathkeys(root,
2919 : rel,
2920 : subpath->pathkeys,
2921 : make_tlist_from_pathtarget(subpath->pathtarget));
2922 :
2923 : /* Generate outer path using this subpath */
2924 27 : add_partial_path(rel, (Path *)
2925 27 : create_subqueryscan_path(root, rel, subpath,
2926 : trivial_pathtarget,
2927 : pathkeys,
2928 : required_outer));
2929 : }
2930 : }
2931 : }
2932 :
2933 : /*
2934 : * set_function_pathlist
2935 : * Build the (single) access path for a function RTE
2936 : */
2937 : static void
2938 27429 : set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
2939 : {
2940 : Relids required_outer;
2941 27429 : List *pathkeys = NIL;
2942 :
2943 : /*
2944 : * We don't support pushing join clauses into the quals of a function
2945 : * scan, but it could still have required parameterization due to LATERAL
2946 : * refs in the function expression.
2947 : */
2948 27429 : required_outer = rel->lateral_relids;
2949 :
2950 : /*
2951 : * The result is considered unordered unless ORDINALITY was used, in which
2952 : * case it is ordered by the ordinal column (the last one). See if we
2953 : * care, by checking for uses of that Var in equivalence classes.
2954 : */
2955 27429 : if (rte->funcordinality)
2956 : {
2957 477 : AttrNumber ordattno = rel->max_attr;
2958 477 : Var *var = NULL;
2959 : ListCell *lc;
2960 :
2961 : /*
2962 : * Is there a Var for it in rel's targetlist? If not, the query did
2963 : * not reference the ordinality column, or at least not in any way
2964 : * that would be interesting for sorting.
2965 : */
2966 1069 : foreach(lc, rel->reltarget->exprs)
2967 : {
2968 1066 : Var *node = (Var *) lfirst(lc);
2969 :
2970 : /* checking varno/varlevelsup is just paranoia */
2971 1066 : if (IsA(node, Var) &&
2972 1066 : node->varattno == ordattno &&
2973 474 : node->varno == rel->relid &&
2974 474 : node->varlevelsup == 0)
2975 : {
2976 474 : var = node;
2977 474 : break;
2978 : }
2979 : }
2980 :
2981 : /*
2982 : * Try to build pathkeys for this Var with int8 sorting. We tell
2983 : * build_expression_pathkey not to build any new equivalence class; if
2984 : * the Var isn't already mentioned in some EC, it means that nothing
2985 : * cares about the ordering.
2986 : */
2987 477 : if (var)
2988 474 : pathkeys = build_expression_pathkey(root,
2989 : (Expr *) var,
2990 : Int8LessOperator,
2991 : rel->relids,
2992 : false);
2993 : }
2994 :
2995 : /* Generate appropriate path */
2996 27429 : add_path(rel, create_functionscan_path(root, rel,
2997 : pathkeys, required_outer));
2998 27429 : }
2999 :
3000 : /*
3001 : * set_values_pathlist
3002 : * Build the (single) access path for a VALUES RTE
3003 : */
3004 : static void
3005 4329 : set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
3006 : {
3007 : Relids required_outer;
3008 :
3009 : /*
3010 : * We don't support pushing join clauses into the quals of a values scan,
3011 : * but it could still have required parameterization due to LATERAL refs
3012 : * in the values expressions.
3013 : */
3014 4329 : required_outer = rel->lateral_relids;
3015 :
3016 : /* Generate appropriate path */
3017 4329 : add_path(rel, create_valuesscan_path(root, rel, required_outer));
3018 4329 : }
3019 :
3020 : /*
3021 : * set_tablefunc_pathlist
3022 : * Build the (single) access path for a table func RTE
3023 : */
3024 : static void
3025 313 : set_tablefunc_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
3026 : {
3027 : Relids required_outer;
3028 :
3029 : /*
3030 : * We don't support pushing join clauses into the quals of a tablefunc
3031 : * scan, but it could still have required parameterization due to LATERAL
3032 : * refs in the function expression.
3033 : */
3034 313 : required_outer = rel->lateral_relids;
3035 :
3036 : /* Generate appropriate path */
3037 313 : add_path(rel, create_tablefuncscan_path(root, rel,
3038 : required_outer));
3039 313 : }
3040 :
3041 : /*
3042 : * set_cte_pathlist
3043 : * Build the (single) access path for a non-self-reference CTE RTE
3044 : *
3045 : * There's no need for a separate set_cte_size phase, since we don't
3046 : * support join-qual-parameterized paths for CTEs.
3047 : */
3048 : static void
3049 2378 : set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
3050 : {
3051 : Path *ctepath;
3052 : Plan *cteplan;
3053 : PlannerInfo *cteroot;
3054 : Index levelsup;
3055 : List *pathkeys;
3056 : int ndx;
3057 : ListCell *lc;
3058 : int plan_id;
3059 : Relids required_outer;
3060 :
3061 : /*
3062 : * Find the referenced CTE, and locate the path and plan previously made
3063 : * for it.
3064 : */
3065 2378 : levelsup = rte->ctelevelsup;
3066 2378 : cteroot = root;
3067 4158 : while (levelsup-- > 0)
3068 : {
3069 1780 : cteroot = cteroot->parent_root;
3070 1780 : if (!cteroot) /* shouldn't happen */
3071 0 : elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3072 : }
3073 :
3074 : /*
3075 : * Note: cte_plan_ids can be shorter than cteList, if we are still working
3076 : * on planning the CTEs (ie, this is a side-reference from another CTE).
3077 : * So we mustn't use forboth here.
3078 : */
3079 2378 : ndx = 0;
3080 3252 : foreach(lc, cteroot->parse->cteList)
3081 : {
3082 3252 : CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
3083 :
3084 3252 : if (strcmp(cte->ctename, rte->ctename) == 0)
3085 2378 : break;
3086 874 : ndx++;
3087 : }
3088 2378 : if (lc == NULL) /* shouldn't happen */
3089 0 : elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
3090 2378 : if (ndx >= list_length(cteroot->cte_plan_ids))
3091 0 : elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
3092 2378 : plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
3093 2378 : if (plan_id <= 0)
3094 0 : elog(ERROR, "no plan was made for CTE \"%s\"", rte->ctename);
3095 :
3096 : Assert(list_length(root->glob->subpaths) == list_length(root->glob->subplans));
3097 2378 : ctepath = (Path *) list_nth(root->glob->subpaths, plan_id - 1);
3098 2378 : cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
3099 :
3100 : /* Mark rel with estimated output rows, width, etc */
3101 2378 : set_cte_size_estimates(root, rel, cteplan->plan_rows);
3102 :
3103 : /* Convert the ctepath's pathkeys to outer query's representation */
3104 2378 : pathkeys = convert_subquery_pathkeys(root,
3105 : rel,
3106 : ctepath->pathkeys,
3107 : cteplan->targetlist);
3108 :
3109 : /*
3110 : * We don't support pushing join clauses into the quals of a CTE scan, but
3111 : * it could still have required parameterization due to LATERAL refs in
3112 : * its tlist.
3113 : */
3114 2378 : required_outer = rel->lateral_relids;
3115 :
3116 : /* Generate appropriate path */
3117 2378 : add_path(rel, create_ctescan_path(root, rel, pathkeys, required_outer));
3118 2378 : }
3119 :
3120 : /*
3121 : * set_namedtuplestore_pathlist
3122 : * Build the (single) access path for a named tuplestore RTE
3123 : *
3124 : * There's no need for a separate set_namedtuplestore_size phase, since we
3125 : * don't support join-qual-parameterized paths for tuplestores.
3126 : */
3127 : static void
3128 237 : set_namedtuplestore_pathlist(PlannerInfo *root, RelOptInfo *rel,
3129 : RangeTblEntry *rte)
3130 : {
3131 : Relids required_outer;
3132 :
3133 : /* Mark rel with estimated output rows, width, etc */
3134 237 : set_namedtuplestore_size_estimates(root, rel);
3135 :
3136 : /*
3137 : * We don't support pushing join clauses into the quals of a tuplestore
3138 : * scan, but it could still have required parameterization due to LATERAL
3139 : * refs in its tlist.
3140 : */
3141 237 : required_outer = rel->lateral_relids;
3142 :
3143 : /* Generate appropriate path */
3144 237 : add_path(rel, create_namedtuplestorescan_path(root, rel, required_outer));
3145 237 : }
3146 :
3147 : /*
3148 : * set_result_pathlist
3149 : * Build the (single) access path for an RTE_RESULT RTE
3150 : *
3151 : * There's no need for a separate set_result_size phase, since we
3152 : * don't support join-qual-parameterized paths for these RTEs.
3153 : */
3154 : static void
3155 2172 : set_result_pathlist(PlannerInfo *root, RelOptInfo *rel,
3156 : RangeTblEntry *rte)
3157 : {
3158 : Relids required_outer;
3159 :
3160 : /* Mark rel with estimated output rows, width, etc */
3161 2172 : set_result_size_estimates(root, rel);
3162 :
3163 : /*
3164 : * We don't support pushing join clauses into the quals of a Result scan,
3165 : * but it could still have required parameterization due to LATERAL refs
3166 : * in its tlist.
3167 : */
3168 2172 : required_outer = rel->lateral_relids;
3169 :
3170 : /* Generate appropriate path */
3171 2172 : add_path(rel, create_resultscan_path(root, rel, required_outer));
3172 2172 : }
3173 :
3174 : /*
3175 : * set_worktable_pathlist
3176 : * Build the (single) access path for a self-reference CTE RTE
3177 : *
3178 : * There's no need for a separate set_worktable_size phase, since we don't
3179 : * support join-qual-parameterized paths for CTEs.
3180 : */
3181 : static void
3182 540 : set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
3183 : {
3184 : Path *ctepath;
3185 : PlannerInfo *cteroot;
3186 : Index levelsup;
3187 : Relids required_outer;
3188 :
3189 : /*
3190 : * We need to find the non-recursive term's path, which is in the plan
3191 : * level that's processing the recursive UNION, which is one level *below*
3192 : * where the CTE comes from.
3193 : */
3194 540 : levelsup = rte->ctelevelsup;
3195 540 : if (levelsup == 0) /* shouldn't happen */
3196 0 : elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3197 540 : levelsup--;
3198 540 : cteroot = root;
3199 1294 : while (levelsup-- > 0)
3200 : {
3201 754 : cteroot = cteroot->parent_root;
3202 754 : if (!cteroot) /* shouldn't happen */
3203 0 : elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3204 : }
3205 540 : ctepath = cteroot->non_recursive_path;
3206 540 : if (!ctepath) /* shouldn't happen */
3207 0 : elog(ERROR, "could not find path for CTE \"%s\"", rte->ctename);
3208 :
3209 : /* Mark rel with estimated output rows, width, etc */
3210 540 : set_cte_size_estimates(root, rel, ctepath->rows);
3211 :
3212 : /*
3213 : * We don't support pushing join clauses into the quals of a worktable
3214 : * scan, but it could still have required parameterization due to LATERAL
3215 : * refs in its tlist. (I'm not sure this is actually possible given the
3216 : * restrictions on recursive references, but it's easy enough to support.)
3217 : */
3218 540 : required_outer = rel->lateral_relids;
3219 :
3220 : /* Generate appropriate path */
3221 540 : add_path(rel, create_worktablescan_path(root, rel, required_outer));
3222 540 : }
3223 :
3224 : /*
3225 : * generate_gather_paths
3226 : * Generate parallel access paths for a relation by pushing a Gather or
3227 : * Gather Merge on top of a partial path.
3228 : *
3229 : * This must not be called until after we're done creating all partial paths
3230 : * for the specified relation. (Otherwise, add_partial_path might delete a
3231 : * path that some GatherPath or GatherMergePath has a reference to.)
3232 : *
3233 : * If we're generating paths for a scan or join relation, override_rows will
3234 : * be false, and we'll just use the relation's size estimate. When we're
3235 : * being called for a partially-grouped or partially-distinct path, though, we
3236 : * need to override the rowcount estimate. (It's not clear that the
3237 : * particular value we're using here is actually best, but the underlying rel
3238 : * has no estimate so we must do something.)
3239 : */
3240 : void
3241 13547 : generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
3242 : {
3243 : Path *cheapest_partial_path;
3244 : Path *simple_gather_path;
3245 : ListCell *lc;
3246 : double rows;
3247 13547 : double *rowsp = NULL;
3248 :
3249 : /* If there are no partial paths, there's nothing to do here. */
3250 13547 : if (rel->partial_pathlist == NIL)
3251 0 : return;
3252 :
3253 : /* Should we override the rel's rowcount estimate? */
3254 13547 : if (override_rows)
3255 3486 : rowsp = &rows;
3256 :
3257 : /*
3258 : * The output of Gather is always unsorted, so there's only one partial
3259 : * path of interest: the cheapest one. That will be the one at the front
3260 : * of partial_pathlist because of the way add_partial_path works.
3261 : */
3262 13547 : cheapest_partial_path = linitial(rel->partial_pathlist);
3263 13547 : rows = compute_gather_rows(cheapest_partial_path);
3264 : simple_gather_path = (Path *)
3265 13547 : create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
3266 : NULL, rowsp);
3267 13547 : add_path(rel, simple_gather_path);
3268 :
3269 : /*
3270 : * For each useful ordering, we can consider an order-preserving Gather
3271 : * Merge.
3272 : */
3273 30221 : foreach(lc, rel->partial_pathlist)
3274 : {
3275 16674 : Path *subpath = (Path *) lfirst(lc);
3276 : GatherMergePath *path;
3277 :
3278 16674 : if (subpath->pathkeys == NIL)
3279 13212 : continue;
3280 :
3281 3462 : rows = compute_gather_rows(subpath);
3282 3462 : path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
3283 : subpath->pathkeys, NULL, rowsp);
3284 3462 : add_path(rel, &path->path);
3285 : }
3286 : }
3287 :
3288 : /*
3289 : * get_useful_pathkeys_for_relation
3290 : * Determine which orderings of a relation might be useful.
3291 : *
3292 : * Getting data in sorted order can be useful either because the requested
3293 : * order matches the final output ordering for the overall query we're
3294 : * planning, or because it enables an efficient merge join. Here, we try
3295 : * to figure out which pathkeys to consider.
3296 : *
3297 : * This allows us to do incremental sort on top of an index scan under a gather
3298 : * merge node, i.e. parallelized.
3299 : *
3300 : * If the require_parallel_safe is true, we also require the expressions to
3301 : * be parallel safe (which allows pushing the sort below Gather Merge).
3302 : *
3303 : * XXX At the moment this can only ever return a list with a single element,
3304 : * because it looks at query_pathkeys only. So we might return the pathkeys
3305 : * directly, but it seems plausible we'll want to consider other orderings
3306 : * in the future. For example, we might want to consider pathkeys useful for
3307 : * merge joins.
3308 : */
3309 : static List *
3310 13547 : get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel,
3311 : bool require_parallel_safe)
3312 : {
3313 13547 : List *useful_pathkeys_list = NIL;
3314 :
3315 : /*
3316 : * Considering query_pathkeys is always worth it, because it might allow
3317 : * us to avoid a total sort when we have a partially presorted path
3318 : * available or to push the total sort into the parallel portion of the
3319 : * query.
3320 : */
3321 13547 : if (root->query_pathkeys)
3322 : {
3323 : ListCell *lc;
3324 7771 : int npathkeys = 0; /* useful pathkeys */
3325 :
3326 13789 : foreach(lc, root->query_pathkeys)
3327 : {
3328 9973 : PathKey *pathkey = (PathKey *) lfirst(lc);
3329 9973 : EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
3330 :
3331 : /*
3332 : * We can only build a sort for pathkeys that contain a
3333 : * safe-to-compute-early EC member computable from the current
3334 : * relation's reltarget, so ignore the remainder of the list as
3335 : * soon as we find a pathkey without such a member.
3336 : *
3337 : * It's still worthwhile to return any prefix of the pathkeys list
3338 : * that meets this requirement, as we may be able to do an
3339 : * incremental sort.
3340 : *
3341 : * If requested, ensure the sort expression is parallel-safe too.
3342 : */
3343 9973 : if (!relation_can_be_sorted_early(root, rel, pathkey_ec,
3344 : require_parallel_safe))
3345 3955 : break;
3346 :
3347 6018 : npathkeys++;
3348 : }
3349 :
3350 : /*
3351 : * The whole query_pathkeys list matches, so append it directly, to
3352 : * allow comparing pathkeys easily by comparing list pointer. If we
3353 : * have to truncate the pathkeys, we gotta do a copy though.
3354 : */
3355 7771 : if (npathkeys == list_length(root->query_pathkeys))
3356 3816 : useful_pathkeys_list = lappend(useful_pathkeys_list,
3357 3816 : root->query_pathkeys);
3358 3955 : else if (npathkeys > 0)
3359 237 : useful_pathkeys_list = lappend(useful_pathkeys_list,
3360 237 : list_copy_head(root->query_pathkeys,
3361 : npathkeys));
3362 : }
3363 :
3364 13547 : return useful_pathkeys_list;
3365 : }
3366 :
3367 : /*
3368 : * generate_useful_gather_paths
3369 : * Generate parallel access paths for a relation by pushing a Gather or
3370 : * Gather Merge on top of a partial path.
3371 : *
3372 : * Unlike plain generate_gather_paths, this looks both at pathkeys of input
3373 : * paths (aiming to preserve the ordering), but also considers ordering that
3374 : * might be useful for nodes above the gather merge node, and tries to add
3375 : * a sort (regular or incremental) to provide that.
3376 : */
3377 : void
3378 351118 : generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
3379 : {
3380 : ListCell *lc;
3381 : double rows;
3382 351118 : double *rowsp = NULL;
3383 351118 : List *useful_pathkeys_list = NIL;
3384 351118 : Path *cheapest_partial_path = NULL;
3385 :
3386 : /* If there are no partial paths, there's nothing to do here. */
3387 351118 : if (rel->partial_pathlist == NIL)
3388 337571 : return;
3389 :
3390 : /* Should we override the rel's rowcount estimate? */
3391 13547 : if (override_rows)
3392 3486 : rowsp = &rows;
3393 :
3394 : /* generate the regular gather (merge) paths */
3395 13547 : generate_gather_paths(root, rel, override_rows);
3396 :
3397 : /* consider incremental sort for interesting orderings */
3398 13547 : useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3399 :
3400 : /* used for explicit (full) sort paths */
3401 13547 : cheapest_partial_path = linitial(rel->partial_pathlist);
3402 :
3403 : /*
3404 : * Consider sorted paths for each interesting ordering. We generate both
3405 : * incremental and full sort.
3406 : */
3407 17600 : foreach(lc, useful_pathkeys_list)
3408 : {
3409 4053 : List *useful_pathkeys = lfirst(lc);
3410 : ListCell *lc2;
3411 : bool is_sorted;
3412 : int presorted_keys;
3413 :
3414 9566 : foreach(lc2, rel->partial_pathlist)
3415 : {
3416 5513 : Path *subpath = (Path *) lfirst(lc2);
3417 : GatherMergePath *path;
3418 :
3419 5513 : is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3420 : subpath->pathkeys,
3421 : &presorted_keys);
3422 :
3423 : /*
3424 : * We don't need to consider the case where a subpath is already
3425 : * fully sorted because generate_gather_paths already creates a
3426 : * gather merge path for every subpath that has pathkeys present.
3427 : *
3428 : * But since the subpath is already sorted, we know we don't need
3429 : * to consider adding a sort (full or incremental) on top of it,
3430 : * so we can continue here.
3431 : */
3432 5513 : if (is_sorted)
3433 1518 : continue;
3434 :
3435 : /*
3436 : * Try at least sorting the cheapest path and also try
3437 : * incrementally sorting any path which is partially sorted
3438 : * already (no need to deal with paths which have presorted keys
3439 : * when incremental sort is disabled unless it's the cheapest
3440 : * input path).
3441 : */
3442 3995 : if (subpath != cheapest_partial_path &&
3443 189 : (presorted_keys == 0 || !enable_incremental_sort))
3444 51 : continue;
3445 :
3446 : /*
3447 : * Consider regular sort for any path that's not presorted or if
3448 : * incremental sort is disabled. We've no need to consider both
3449 : * sort and incremental sort on the same path. We assume that
3450 : * incremental sort is always faster when there are presorted
3451 : * keys.
3452 : *
3453 : * This is not redundant with the gather paths created in
3454 : * generate_gather_paths, because that doesn't generate ordered
3455 : * output. Here we add an explicit sort to match the useful
3456 : * ordering.
3457 : */
3458 3944 : if (presorted_keys == 0 || !enable_incremental_sort)
3459 : {
3460 3800 : subpath = (Path *) create_sort_path(root,
3461 : rel,
3462 : subpath,
3463 : useful_pathkeys,
3464 : -1.0);
3465 : }
3466 : else
3467 144 : subpath = (Path *) create_incremental_sort_path(root,
3468 : rel,
3469 : subpath,
3470 : useful_pathkeys,
3471 : presorted_keys,
3472 : -1);
3473 3944 : rows = compute_gather_rows(subpath);
3474 3944 : path = create_gather_merge_path(root, rel,
3475 : subpath,
3476 3944 : rel->reltarget,
3477 : subpath->pathkeys,
3478 : NULL,
3479 : rowsp);
3480 :
3481 3944 : add_path(rel, &path->path);
3482 : }
3483 : }
3484 : }
3485 :
3486 : /*
3487 : * generate_grouped_paths
3488 : * Generate paths for a grouped relation by adding sorted and hashed
3489 : * partial aggregation paths on top of paths of the ungrouped relation.
3490 : *
3491 : * The information needed is provided by the RelAggInfo structure stored in
3492 : * "grouped_rel".
3493 : */
3494 : void
3495 449 : generate_grouped_paths(PlannerInfo *root, RelOptInfo *grouped_rel,
3496 : RelOptInfo *rel)
3497 : {
3498 449 : RelAggInfo *agg_info = grouped_rel->agg_info;
3499 : AggClauseCosts agg_costs;
3500 : bool can_hash;
3501 : bool can_sort;
3502 449 : Path *cheapest_total_path = NULL;
3503 449 : Path *cheapest_partial_path = NULL;
3504 449 : double dNumGroups = 0;
3505 449 : double dNumPartialGroups = 0;
3506 449 : List *group_pathkeys = NIL;
3507 :
3508 449 : if (IS_DUMMY_REL(rel))
3509 : {
3510 0 : mark_dummy_rel(grouped_rel);
3511 0 : return;
3512 : }
3513 :
3514 : /*
3515 : * We push partial aggregation only to the lowest possible level in the
3516 : * join tree that is deemed useful.
3517 : */
3518 449 : if (!bms_equal(agg_info->apply_agg_at, rel->relids) ||
3519 449 : !agg_info->agg_useful)
3520 0 : return;
3521 :
3522 2694 : MemSet(&agg_costs, 0, sizeof(AggClauseCosts));
3523 449 : get_agg_clause_costs(root, AGGSPLIT_INITIAL_SERIAL, &agg_costs);
3524 :
3525 : /*
3526 : * Determine whether it's possible to perform sort-based implementations
3527 : * of grouping, and generate the pathkeys that represent the grouping
3528 : * requirements in that case.
3529 : */
3530 449 : can_sort = grouping_is_sortable(agg_info->group_clauses);
3531 449 : if (can_sort)
3532 : {
3533 : RelOptInfo *top_grouped_rel;
3534 : List *top_group_tlist;
3535 :
3536 251 : top_grouped_rel = IS_OTHER_REL(rel) ?
3537 700 : rel->top_parent->grouped_rel : grouped_rel;
3538 : top_group_tlist =
3539 449 : make_tlist_from_pathtarget(top_grouped_rel->agg_info->target);
3540 :
3541 : group_pathkeys =
3542 449 : make_pathkeys_for_sortclauses(root, agg_info->group_clauses,
3543 : top_group_tlist);
3544 : }
3545 :
3546 : /*
3547 : * Determine whether we should consider hash-based implementations of
3548 : * grouping.
3549 : */
3550 : Assert(root->numOrderedAggs == 0);
3551 898 : can_hash = (agg_info->group_clauses != NIL &&
3552 449 : grouping_is_hashable(agg_info->group_clauses));
3553 :
3554 : /*
3555 : * Consider whether we should generate partially aggregated non-partial
3556 : * paths. We can only do this if we have a non-partial path.
3557 : */
3558 449 : if (rel->pathlist != NIL)
3559 : {
3560 449 : cheapest_total_path = rel->cheapest_total_path;
3561 : Assert(cheapest_total_path != NULL);
3562 : }
3563 :
3564 : /*
3565 : * If parallelism is possible for grouped_rel, then we should consider
3566 : * generating partially-grouped partial paths. However, if the ungrouped
3567 : * rel has no partial paths, then we can't.
3568 : */
3569 449 : if (grouped_rel->consider_parallel && rel->partial_pathlist != NIL)
3570 : {
3571 366 : cheapest_partial_path = linitial(rel->partial_pathlist);
3572 : Assert(cheapest_partial_path != NULL);
3573 : }
3574 :
3575 : /* Estimate number of partial groups. */
3576 449 : if (cheapest_total_path != NULL)
3577 449 : dNumGroups = estimate_num_groups(root,
3578 : agg_info->group_exprs,
3579 : cheapest_total_path->rows,
3580 : NULL, NULL);
3581 449 : if (cheapest_partial_path != NULL)
3582 366 : dNumPartialGroups = estimate_num_groups(root,
3583 : agg_info->group_exprs,
3584 : cheapest_partial_path->rows,
3585 : NULL, NULL);
3586 :
3587 449 : if (can_sort && cheapest_total_path != NULL)
3588 : {
3589 : ListCell *lc;
3590 :
3591 : /*
3592 : * Use any available suitably-sorted path as input, and also consider
3593 : * sorting the cheapest-total path and incremental sort on any paths
3594 : * with presorted keys.
3595 : *
3596 : * To save planning time, we ignore parameterized input paths unless
3597 : * they are the cheapest-total path.
3598 : */
3599 1087 : foreach(lc, rel->pathlist)
3600 : {
3601 638 : Path *input_path = (Path *) lfirst(lc);
3602 : Path *path;
3603 : bool is_sorted;
3604 : int presorted_keys;
3605 :
3606 : /*
3607 : * Ignore parameterized paths that are not the cheapest-total
3608 : * path.
3609 : */
3610 638 : if (input_path->param_info &&
3611 : input_path != cheapest_total_path)
3612 15 : continue;
3613 :
3614 635 : is_sorted = pathkeys_count_contained_in(group_pathkeys,
3615 : input_path->pathkeys,
3616 : &presorted_keys);
3617 :
3618 : /*
3619 : * Ignore paths that are not suitably or partially sorted, unless
3620 : * they are the cheapest total path (no need to deal with paths
3621 : * which have presorted keys when incremental sort is disabled).
3622 : */
3623 635 : if (!is_sorted && input_path != cheapest_total_path &&
3624 84 : (presorted_keys == 0 || !enable_incremental_sort))
3625 12 : continue;
3626 :
3627 : /*
3628 : * Since the path originates from a non-grouped relation that is
3629 : * not aware of eager aggregation, we must ensure that it provides
3630 : * the correct input for partial aggregation.
3631 : */
3632 623 : path = (Path *) create_projection_path(root,
3633 : grouped_rel,
3634 : input_path,
3635 623 : agg_info->agg_input);
3636 :
3637 623 : if (!is_sorted)
3638 : {
3639 : /*
3640 : * We've no need to consider both a sort and incremental sort.
3641 : * We'll just do a sort if there are no presorted keys and an
3642 : * incremental sort when there are presorted keys.
3643 : */
3644 518 : if (presorted_keys == 0 || !enable_incremental_sort)
3645 446 : path = (Path *) create_sort_path(root,
3646 : grouped_rel,
3647 : path,
3648 : group_pathkeys,
3649 : -1.0);
3650 : else
3651 72 : path = (Path *) create_incremental_sort_path(root,
3652 : grouped_rel,
3653 : path,
3654 : group_pathkeys,
3655 : presorted_keys,
3656 : -1.0);
3657 : }
3658 :
3659 : /*
3660 : * qual is NIL because the HAVING clause cannot be evaluated until
3661 : * the final value of the aggregate is known.
3662 : */
3663 623 : path = (Path *) create_agg_path(root,
3664 : grouped_rel,
3665 : path,
3666 623 : agg_info->target,
3667 : AGG_SORTED,
3668 : AGGSPLIT_INITIAL_SERIAL,
3669 : agg_info->group_clauses,
3670 : NIL,
3671 : &agg_costs,
3672 : dNumGroups);
3673 :
3674 623 : add_path(grouped_rel, path);
3675 : }
3676 : }
3677 :
3678 449 : if (can_sort && cheapest_partial_path != NULL)
3679 : {
3680 : ListCell *lc;
3681 :
3682 : /* Similar to above logic, but for partial paths. */
3683 852 : foreach(lc, rel->partial_pathlist)
3684 : {
3685 486 : Path *input_path = (Path *) lfirst(lc);
3686 : Path *path;
3687 : bool is_sorted;
3688 : int presorted_keys;
3689 :
3690 486 : is_sorted = pathkeys_count_contained_in(group_pathkeys,
3691 : input_path->pathkeys,
3692 : &presorted_keys);
3693 :
3694 : /*
3695 : * Ignore paths that are not suitably or partially sorted, unless
3696 : * they are the cheapest partial path (no need to deal with paths
3697 : * which have presorted keys when incremental sort is disabled).
3698 : */
3699 486 : if (!is_sorted && input_path != cheapest_partial_path &&
3700 48 : (presorted_keys == 0 || !enable_incremental_sort))
3701 0 : continue;
3702 :
3703 : /*
3704 : * Since the path originates from a non-grouped relation that is
3705 : * not aware of eager aggregation, we must ensure that it provides
3706 : * the correct input for partial aggregation.
3707 : */
3708 486 : path = (Path *) create_projection_path(root,
3709 : grouped_rel,
3710 : input_path,
3711 486 : agg_info->agg_input);
3712 :
3713 486 : if (!is_sorted)
3714 : {
3715 : /*
3716 : * We've no need to consider both a sort and incremental sort.
3717 : * We'll just do a sort if there are no presorted keys and an
3718 : * incremental sort when there are presorted keys.
3719 : */
3720 414 : if (presorted_keys == 0 || !enable_incremental_sort)
3721 366 : path = (Path *) create_sort_path(root,
3722 : grouped_rel,
3723 : path,
3724 : group_pathkeys,
3725 : -1.0);
3726 : else
3727 48 : path = (Path *) create_incremental_sort_path(root,
3728 : grouped_rel,
3729 : path,
3730 : group_pathkeys,
3731 : presorted_keys,
3732 : -1.0);
3733 : }
3734 :
3735 : /*
3736 : * qual is NIL because the HAVING clause cannot be evaluated until
3737 : * the final value of the aggregate is known.
3738 : */
3739 486 : path = (Path *) create_agg_path(root,
3740 : grouped_rel,
3741 : path,
3742 486 : agg_info->target,
3743 : AGG_SORTED,
3744 : AGGSPLIT_INITIAL_SERIAL,
3745 : agg_info->group_clauses,
3746 : NIL,
3747 : &agg_costs,
3748 : dNumPartialGroups);
3749 :
3750 486 : add_partial_path(grouped_rel, path);
3751 : }
3752 : }
3753 :
3754 : /*
3755 : * Add a partially-grouped HashAgg Path where possible
3756 : */
3757 449 : if (can_hash && cheapest_total_path != NULL)
3758 : {
3759 : Path *path;
3760 :
3761 : /*
3762 : * Since the path originates from a non-grouped relation that is not
3763 : * aware of eager aggregation, we must ensure that it provides the
3764 : * correct input for partial aggregation.
3765 : */
3766 449 : path = (Path *) create_projection_path(root,
3767 : grouped_rel,
3768 : cheapest_total_path,
3769 449 : agg_info->agg_input);
3770 :
3771 : /*
3772 : * qual is NIL because the HAVING clause cannot be evaluated until the
3773 : * final value of the aggregate is known.
3774 : */
3775 449 : path = (Path *) create_agg_path(root,
3776 : grouped_rel,
3777 : path,
3778 449 : agg_info->target,
3779 : AGG_HASHED,
3780 : AGGSPLIT_INITIAL_SERIAL,
3781 : agg_info->group_clauses,
3782 : NIL,
3783 : &agg_costs,
3784 : dNumGroups);
3785 :
3786 449 : add_path(grouped_rel, path);
3787 : }
3788 :
3789 : /*
3790 : * Now add a partially-grouped HashAgg partial Path where possible
3791 : */
3792 449 : if (can_hash && cheapest_partial_path != NULL)
3793 : {
3794 : Path *path;
3795 :
3796 : /*
3797 : * Since the path originates from a non-grouped relation that is not
3798 : * aware of eager aggregation, we must ensure that it provides the
3799 : * correct input for partial aggregation.
3800 : */
3801 366 : path = (Path *) create_projection_path(root,
3802 : grouped_rel,
3803 : cheapest_partial_path,
3804 366 : agg_info->agg_input);
3805 :
3806 : /*
3807 : * qual is NIL because the HAVING clause cannot be evaluated until the
3808 : * final value of the aggregate is known.
3809 : */
3810 366 : path = (Path *) create_agg_path(root,
3811 : grouped_rel,
3812 : path,
3813 366 : agg_info->target,
3814 : AGG_HASHED,
3815 : AGGSPLIT_INITIAL_SERIAL,
3816 : agg_info->group_clauses,
3817 : NIL,
3818 : &agg_costs,
3819 : dNumPartialGroups);
3820 :
3821 366 : add_partial_path(grouped_rel, path);
3822 : }
3823 : }
3824 :
3825 : /*
3826 : * make_rel_from_joinlist
3827 : * Build access paths using a "joinlist" to guide the join path search.
3828 : *
3829 : * See comments for deconstruct_jointree() for definition of the joinlist
3830 : * data structure.
3831 : */
3832 : static RelOptInfo *
3833 184704 : make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
3834 : {
3835 : int levels_needed;
3836 : List *initial_rels;
3837 : ListCell *jl;
3838 :
3839 : /*
3840 : * Count the number of child joinlist nodes. This is the depth of the
3841 : * dynamic-programming algorithm we must employ to consider all ways of
3842 : * joining the child nodes.
3843 : */
3844 184704 : levels_needed = list_length(joinlist);
3845 :
3846 184704 : if (levels_needed <= 0)
3847 0 : return NULL; /* nothing to do? */
3848 :
3849 : /*
3850 : * Construct a list of rels corresponding to the child joinlist nodes.
3851 : * This may contain both base rels and rels constructed according to
3852 : * sub-joinlists.
3853 : */
3854 184704 : initial_rels = NIL;
3855 449234 : foreach(jl, joinlist)
3856 : {
3857 264530 : Node *jlnode = (Node *) lfirst(jl);
3858 : RelOptInfo *thisrel;
3859 :
3860 264530 : if (IsA(jlnode, RangeTblRef))
3861 : {
3862 262784 : int varno = ((RangeTblRef *) jlnode)->rtindex;
3863 :
3864 262784 : thisrel = find_base_rel(root, varno);
3865 : }
3866 1746 : else if (IsA(jlnode, List))
3867 : {
3868 : /* Recurse to handle subproblem */
3869 1746 : thisrel = make_rel_from_joinlist(root, (List *) jlnode);
3870 : }
3871 : else
3872 : {
3873 0 : elog(ERROR, "unrecognized joinlist node type: %d",
3874 : (int) nodeTag(jlnode));
3875 : thisrel = NULL; /* keep compiler quiet */
3876 : }
3877 :
3878 264530 : initial_rels = lappend(initial_rels, thisrel);
3879 : }
3880 :
3881 184704 : if (levels_needed == 1)
3882 : {
3883 : /*
3884 : * Single joinlist node, so we're done.
3885 : */
3886 126867 : return (RelOptInfo *) linitial(initial_rels);
3887 : }
3888 : else
3889 : {
3890 : /*
3891 : * Consider the different orders in which we could join the rels,
3892 : * using a plugin, GEQO, or the regular join search code.
3893 : *
3894 : * We put the initial_rels list into a PlannerInfo field because
3895 : * has_legal_joinclause() needs to look at it (ugly :-().
3896 : */
3897 57837 : root->initial_rels = initial_rels;
3898 :
3899 57837 : if (join_search_hook)
3900 0 : return (*join_search_hook) (root, levels_needed, initial_rels);
3901 57837 : else if (enable_geqo && levels_needed >= geqo_threshold)
3902 21 : return geqo(root, levels_needed, initial_rels);
3903 : else
3904 57816 : return standard_join_search(root, levels_needed, initial_rels);
3905 : }
3906 : }
3907 :
3908 : /*
3909 : * standard_join_search
3910 : * Find possible joinpaths for a query by successively finding ways
3911 : * to join component relations into join relations.
3912 : *
3913 : * 'levels_needed' is the number of iterations needed, ie, the number of
3914 : * independent jointree items in the query. This is > 1.
3915 : *
3916 : * 'initial_rels' is a list of RelOptInfo nodes for each independent
3917 : * jointree item. These are the components to be joined together.
3918 : * Note that levels_needed == list_length(initial_rels).
3919 : *
3920 : * Returns the final level of join relations, i.e., the relation that is
3921 : * the result of joining all the original relations together.
3922 : * At least one implementation path must be provided for this relation and
3923 : * all required sub-relations.
3924 : *
3925 : * To support loadable plugins that modify planner behavior by changing the
3926 : * join searching algorithm, we provide a hook variable that lets a plugin
3927 : * replace or supplement this function. Any such hook must return the same
3928 : * final join relation as the standard code would, but it might have a
3929 : * different set of implementation paths attached, and only the sub-joinrels
3930 : * needed for these paths need have been instantiated.
3931 : *
3932 : * Note to plugin authors: the functions invoked during standard_join_search()
3933 : * modify root->join_rel_list and root->join_rel_hash. If you want to do more
3934 : * than one join-order search, you'll probably need to save and restore the
3935 : * original states of those data structures. See geqo_eval() for an example.
3936 : */
3937 : RelOptInfo *
3938 57816 : standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
3939 : {
3940 : int lev;
3941 : RelOptInfo *rel;
3942 :
3943 : /*
3944 : * This function cannot be invoked recursively within any one planning
3945 : * problem, so join_rel_level[] can't be in use already.
3946 : */
3947 : Assert(root->join_rel_level == NULL);
3948 :
3949 : /*
3950 : * We employ a simple "dynamic programming" algorithm: we first find all
3951 : * ways to build joins of two jointree items, then all ways to build joins
3952 : * of three items (from two-item joins and single items), then four-item
3953 : * joins, and so on until we have considered all ways to join all the
3954 : * items into one rel.
3955 : *
3956 : * root->join_rel_level[j] is a list of all the j-item rels. Initially we
3957 : * set root->join_rel_level[1] to represent all the single-jointree-item
3958 : * relations.
3959 : */
3960 57816 : root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
3961 :
3962 57816 : root->join_rel_level[1] = initial_rels;
3963 :
3964 137612 : for (lev = 2; lev <= levels_needed; lev++)
3965 : {
3966 : ListCell *lc;
3967 :
3968 : /*
3969 : * Determine all possible pairs of relations to be joined at this
3970 : * level, and build paths for making each one from every available
3971 : * pair of lower-level relations.
3972 : */
3973 79796 : join_search_one_level(root, lev);
3974 :
3975 : /*
3976 : * Run generate_partitionwise_join_paths() and
3977 : * generate_useful_gather_paths() for each just-processed joinrel. We
3978 : * could not do this earlier because both regular and partial paths
3979 : * can get added to a particular joinrel at multiple times within
3980 : * join_search_one_level.
3981 : *
3982 : * After that, we're done creating paths for the joinrel, so run
3983 : * set_cheapest().
3984 : *
3985 : * In addition, we also run generate_grouped_paths() for the grouped
3986 : * relation of each just-processed joinrel, and run set_cheapest() for
3987 : * the grouped relation afterwards.
3988 : */
3989 205876 : foreach(lc, root->join_rel_level[lev])
3990 : {
3991 : bool is_top_rel;
3992 :
3993 126080 : rel = (RelOptInfo *) lfirst(lc);
3994 :
3995 126080 : is_top_rel = bms_equal(rel->relids, root->all_query_rels);
3996 :
3997 : /* Create paths for partitionwise joins. */
3998 126080 : generate_partitionwise_join_paths(root, rel);
3999 :
4000 : /*
4001 : * Except for the topmost scan/join rel, consider gathering
4002 : * partial paths. We'll do the same for the topmost scan/join rel
4003 : * once we know the final targetlist (see grouping_planner's and
4004 : * its call to apply_scanjoin_target_to_paths).
4005 : */
4006 126080 : if (!is_top_rel)
4007 68519 : generate_useful_gather_paths(root, rel, false);
4008 :
4009 : /* Find and save the cheapest paths for this rel */
4010 126080 : set_cheapest(rel);
4011 :
4012 : /*
4013 : * Except for the topmost scan/join rel, consider generating
4014 : * partial aggregation paths for the grouped relation on top of
4015 : * the paths of this rel. After that, we're done creating paths
4016 : * for the grouped relation, so run set_cheapest().
4017 : */
4018 126080 : if (rel->grouped_rel != NULL && !is_top_rel)
4019 : {
4020 36 : RelOptInfo *grouped_rel = rel->grouped_rel;
4021 :
4022 : Assert(IS_GROUPED_REL(grouped_rel));
4023 :
4024 36 : generate_grouped_paths(root, grouped_rel, rel);
4025 36 : set_cheapest(grouped_rel);
4026 : }
4027 :
4028 : #ifdef OPTIMIZER_DEBUG
4029 : pprint(rel);
4030 : #endif
4031 : }
4032 : }
4033 :
4034 : /*
4035 : * We should have a single rel at the final level.
4036 : */
4037 57816 : if (root->join_rel_level[levels_needed] == NIL)
4038 0 : elog(ERROR, "failed to build any %d-way joins", levels_needed);
4039 : Assert(list_length(root->join_rel_level[levels_needed]) == 1);
4040 :
4041 57816 : rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
4042 :
4043 57816 : root->join_rel_level = NULL;
4044 :
4045 57816 : return rel;
4046 : }
4047 :
4048 : /*****************************************************************************
4049 : * PUSHING QUALS DOWN INTO SUBQUERIES
4050 : *****************************************************************************/
4051 :
4052 : /*
4053 : * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
4054 : *
4055 : * subquery is the particular component query being checked. topquery
4056 : * is the top component of a set-operations tree (the same Query if no
4057 : * set-op is involved).
4058 : *
4059 : * Conditions checked here:
4060 : *
4061 : * 1. If the subquery has a LIMIT clause, we must not push down any quals,
4062 : * since that could change the set of rows returned.
4063 : *
4064 : * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
4065 : * quals into it, because that could change the results.
4066 : *
4067 : * 3. If the subquery uses DISTINCT, we cannot push volatile quals into it.
4068 : * This is because upper-level quals should semantically be evaluated only
4069 : * once per distinct row, not once per original row, and if the qual is
4070 : * volatile then extra evaluations could change the results. (This issue
4071 : * does not apply to other forms of aggregation such as GROUP BY, because
4072 : * when those are present we push into HAVING not WHERE, so that the quals
4073 : * are still applied after aggregation.)
4074 : *
4075 : * 4. If the subquery contains window functions, we cannot push volatile quals
4076 : * into it. The issue here is a bit different from DISTINCT: a volatile qual
4077 : * might succeed for some rows of a window partition and fail for others,
4078 : * thereby changing the partition contents and thus the window functions'
4079 : * results for rows that remain.
4080 : *
4081 : * 5. If the subquery contains any set-returning functions in its targetlist,
4082 : * we cannot push volatile quals into it. That would push them below the SRFs
4083 : * and thereby change the number of times they are evaluated. Also, a
4084 : * volatile qual could succeed for some SRF output rows and fail for others,
4085 : * a behavior that cannot occur if it's evaluated before SRF expansion.
4086 : *
4087 : * 6. If the subquery has nonempty grouping sets, we cannot push down any
4088 : * quals. The concern here is that a qual referencing a "constant" grouping
4089 : * column could get constant-folded, which would be improper because the value
4090 : * is potentially nullable by grouping-set expansion. This restriction could
4091 : * be removed if we had a parsetree representation that shows that such
4092 : * grouping columns are not really constant. (There are other ideas that
4093 : * could be used to relax this restriction, but that's the approach most
4094 : * likely to get taken in the future. Note that there's not much to be gained
4095 : * so long as subquery_planner can't move HAVING clauses to WHERE within such
4096 : * a subquery.)
4097 : *
4098 : * In addition, we make several checks on the subquery's output columns to see
4099 : * if it is safe to reference them in pushed-down quals. If output column k
4100 : * is found to be unsafe to reference, we set the reason for that inside
4101 : * safetyInfo->unsafeFlags[k], but we don't reject the subquery overall since
4102 : * column k might not be referenced by some/all quals. The unsafeFlags[]
4103 : * array will be consulted later by qual_is_pushdown_safe(). It's better to
4104 : * do it this way than to make the checks directly in qual_is_pushdown_safe(),
4105 : * because when the subquery involves set operations we have to check the
4106 : * output expressions in each arm of the set op.
4107 : *
4108 : * Note: pushing quals into a DISTINCT subquery is theoretically dubious:
4109 : * we're effectively assuming that the quals cannot distinguish values that
4110 : * the DISTINCT's equality operator sees as equal, yet there are many
4111 : * counterexamples to that assumption. However use of such a qual with a
4112 : * DISTINCT subquery would be unsafe anyway, since there's no guarantee which
4113 : * "equal" value will be chosen as the output value by the DISTINCT operation.
4114 : * So we don't worry too much about that. Another objection is that if the
4115 : * qual is expensive to evaluate, running it for each original row might cost
4116 : * more than we save by eliminating rows before the DISTINCT step. But it
4117 : * would be very hard to estimate that at this stage, and in practice pushdown
4118 : * seldom seems to make things worse, so we ignore that problem too.
4119 : *
4120 : * Note: likewise, pushing quals into a subquery with window functions is a
4121 : * bit dubious: the quals might remove some rows of a window partition while
4122 : * leaving others, causing changes in the window functions' results for the
4123 : * surviving rows. We insist that such a qual reference only partitioning
4124 : * columns, but again that only protects us if the qual does not distinguish
4125 : * values that the partitioning equality operator sees as equal. The risks
4126 : * here are perhaps larger than for DISTINCT, since no de-duplication of rows
4127 : * occurs and thus there is no theoretical problem with such a qual. But
4128 : * we'll do this anyway because the potential performance benefits are very
4129 : * large, and we've seen no field complaints about the longstanding comparable
4130 : * behavior with DISTINCT.
4131 : */
4132 : static bool
4133 1717 : subquery_is_pushdown_safe(Query *subquery, Query *topquery,
4134 : pushdown_safety_info *safetyInfo)
4135 : {
4136 : SetOperationStmt *topop;
4137 :
4138 : /* Check point 1 */
4139 1717 : if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
4140 67 : return false;
4141 :
4142 : /* Check point 6 */
4143 1650 : if (subquery->groupClause && subquery->groupingSets)
4144 6 : return false;
4145 :
4146 : /* Check points 3, 4, and 5 */
4147 1644 : if (subquery->distinctClause ||
4148 1602 : subquery->hasWindowFuncs ||
4149 1469 : subquery->hasTargetSRFs)
4150 466 : safetyInfo->unsafeVolatile = true;
4151 :
4152 : /*
4153 : * If we're at a leaf query, check for unsafe expressions in its target
4154 : * list, and mark any reasons why they're unsafe in unsafeFlags[].
4155 : * (Non-leaf nodes in setop trees have only simple Vars in their tlists,
4156 : * so no need to check them.)
4157 : */
4158 1644 : if (subquery->setOperations == NULL)
4159 1566 : check_output_expressions(subquery, safetyInfo);
4160 :
4161 : /* Are we at top level, or looking at a setop component? */
4162 1644 : if (subquery == topquery)
4163 : {
4164 : /* Top level, so check any component queries */
4165 1488 : if (subquery->setOperations != NULL)
4166 78 : if (!recurse_pushdown_safe(subquery->setOperations, topquery,
4167 : safetyInfo))
4168 0 : return false;
4169 : }
4170 : else
4171 : {
4172 : /* Setop component must not have more components (too weird) */
4173 156 : if (subquery->setOperations != NULL)
4174 0 : return false;
4175 : /* Check whether setop component output types match top level */
4176 156 : topop = castNode(SetOperationStmt, topquery->setOperations);
4177 : Assert(topop);
4178 156 : compare_tlist_datatypes(subquery->targetList,
4179 : topop->colTypes,
4180 : safetyInfo);
4181 : }
4182 1644 : return true;
4183 : }
4184 :
4185 : /*
4186 : * Helper routine to recurse through setOperations tree
4187 : */
4188 : static bool
4189 234 : recurse_pushdown_safe(Node *setOp, Query *topquery,
4190 : pushdown_safety_info *safetyInfo)
4191 : {
4192 234 : if (IsA(setOp, RangeTblRef))
4193 : {
4194 156 : RangeTblRef *rtr = (RangeTblRef *) setOp;
4195 156 : RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
4196 156 : Query *subquery = rte->subquery;
4197 :
4198 : Assert(subquery != NULL);
4199 156 : return subquery_is_pushdown_safe(subquery, topquery, safetyInfo);
4200 : }
4201 78 : else if (IsA(setOp, SetOperationStmt))
4202 : {
4203 78 : SetOperationStmt *op = (SetOperationStmt *) setOp;
4204 :
4205 : /* EXCEPT is no good (point 2 for subquery_is_pushdown_safe) */
4206 78 : if (op->op == SETOP_EXCEPT)
4207 0 : return false;
4208 : /* Else recurse */
4209 78 : if (!recurse_pushdown_safe(op->larg, topquery, safetyInfo))
4210 0 : return false;
4211 78 : if (!recurse_pushdown_safe(op->rarg, topquery, safetyInfo))
4212 0 : return false;
4213 : }
4214 : else
4215 : {
4216 0 : elog(ERROR, "unrecognized node type: %d",
4217 : (int) nodeTag(setOp));
4218 : }
4219 78 : return true;
4220 : }
4221 :
4222 : /*
4223 : * check_output_expressions - check subquery's output expressions for safety
4224 : *
4225 : * There are several cases in which it's unsafe to push down an upper-level
4226 : * qual if it references a particular output column of a subquery. We check
4227 : * each output column of the subquery and set flags in unsafeFlags[k] when we
4228 : * see that column is unsafe for a pushed-down qual to reference. The
4229 : * conditions checked here are:
4230 : *
4231 : * 1. We must not push down any quals that refer to subselect outputs that
4232 : * return sets, else we'd introduce functions-returning-sets into the
4233 : * subquery's WHERE/HAVING quals.
4234 : *
4235 : * 2. We must not push down any quals that refer to subselect outputs that
4236 : * contain volatile functions, for fear of introducing strange results due
4237 : * to multiple evaluation of a volatile function.
4238 : *
4239 : * 3. If the subquery uses DISTINCT ON, we must not push down any quals that
4240 : * refer to non-DISTINCT output columns, because that could change the set
4241 : * of rows returned. (This condition is vacuous for DISTINCT, because then
4242 : * there are no non-DISTINCT output columns, so we needn't check. Note that
4243 : * subquery_is_pushdown_safe already reported that we can't use volatile
4244 : * quals if there's DISTINCT or DISTINCT ON.)
4245 : *
4246 : * 4. If the subquery has any window functions, we must not push down quals
4247 : * that reference any output columns that are not listed in all the subquery's
4248 : * window PARTITION BY clauses. We can push down quals that use only
4249 : * partitioning columns because they should succeed or fail identically for
4250 : * every row of any one window partition, and totally excluding some
4251 : * partitions will not change a window function's results for remaining
4252 : * partitions. (Again, this also requires nonvolatile quals, but
4253 : * subquery_is_pushdown_safe handles that.). Subquery columns marked as
4254 : * unsafe for this reason can still have WindowClause run conditions pushed
4255 : * down.
4256 : */
4257 : static void
4258 1566 : check_output_expressions(Query *subquery, pushdown_safety_info *safetyInfo)
4259 : {
4260 1566 : List *flattened_targetList = subquery->targetList;
4261 : ListCell *lc;
4262 :
4263 : /*
4264 : * We must be careful with grouping Vars and join alias Vars in the
4265 : * subquery's outputs, as they hide the underlying expressions.
4266 : *
4267 : * We need to expand grouping Vars to their underlying expressions (the
4268 : * grouping clauses) because the grouping expressions themselves might be
4269 : * volatile or set-returning. However, we do not need to expand join
4270 : * alias Vars, as their underlying structure does not introduce volatile
4271 : * or set-returning functions at the current level.
4272 : *
4273 : * In neither case do we need to recursively examine the Vars contained in
4274 : * these underlying expressions. Even if they reference outputs from
4275 : * lower-level subqueries (at any depth), those references are guaranteed
4276 : * not to expand to volatile or set-returning functions, because
4277 : * subqueries containing such functions in their targetlists are never
4278 : * pulled up.
4279 : */
4280 1566 : if (subquery->hasGroupRTE)
4281 : {
4282 : /*
4283 : * We can safely pass NULL for the root here. This function uses the
4284 : * expanded expressions solely to check for volatile or set-returning
4285 : * functions, which is independent of the Vars' nullingrels.
4286 : */
4287 : flattened_targetList = (List *)
4288 160 : flatten_group_exprs(NULL, subquery, (Node *) subquery->targetList);
4289 : }
4290 :
4291 18139 : foreach(lc, flattened_targetList)
4292 : {
4293 16573 : TargetEntry *tle = (TargetEntry *) lfirst(lc);
4294 :
4295 16573 : if (tle->resjunk)
4296 67 : continue; /* ignore resjunk columns */
4297 :
4298 : /* Functions returning sets are unsafe (point 1) */
4299 16506 : if (subquery->hasTargetSRFs &&
4300 720 : (safetyInfo->unsafeFlags[tle->resno] &
4301 720 : UNSAFE_HAS_SET_FUNC) == 0 &&
4302 720 : expression_returns_set((Node *) tle->expr))
4303 : {
4304 568 : safetyInfo->unsafeFlags[tle->resno] |= UNSAFE_HAS_SET_FUNC;
4305 568 : continue;
4306 : }
4307 :
4308 : /* Volatile functions are unsafe (point 2) */
4309 15938 : if ((safetyInfo->unsafeFlags[tle->resno] &
4310 15932 : UNSAFE_HAS_VOLATILE_FUNC) == 0 &&
4311 15932 : contain_volatile_functions((Node *) tle->expr))
4312 : {
4313 45 : safetyInfo->unsafeFlags[tle->resno] |= UNSAFE_HAS_VOLATILE_FUNC;
4314 45 : continue;
4315 : }
4316 :
4317 : /* If subquery uses DISTINCT ON, check point 3 */
4318 15893 : if (subquery->hasDistinctOn &&
4319 0 : (safetyInfo->unsafeFlags[tle->resno] &
4320 0 : UNSAFE_NOTIN_DISTINCTON_CLAUSE) == 0 &&
4321 0 : !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
4322 : {
4323 : /* non-DISTINCT column, so mark it unsafe */
4324 0 : safetyInfo->unsafeFlags[tle->resno] |= UNSAFE_NOTIN_DISTINCTON_CLAUSE;
4325 0 : continue;
4326 : }
4327 :
4328 : /* If subquery uses window functions, check point 4 */
4329 15893 : if (subquery->hasWindowFuncs &&
4330 545 : (safetyInfo->unsafeFlags[tle->resno] &
4331 1046 : UNSAFE_NOTIN_DISTINCTON_CLAUSE) == 0 &&
4332 545 : !targetIsInAllPartitionLists(tle, subquery))
4333 : {
4334 : /* not present in all PARTITION BY clauses, so mark it unsafe */
4335 501 : safetyInfo->unsafeFlags[tle->resno] |= UNSAFE_NOTIN_PARTITIONBY_CLAUSE;
4336 501 : continue;
4337 : }
4338 : }
4339 1566 : }
4340 :
4341 : /*
4342 : * For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
4343 : * push quals into each component query, but the quals can only reference
4344 : * subquery columns that suffer no type coercions in the set operation.
4345 : * Otherwise there are possible semantic gotchas. So, we check the
4346 : * component queries to see if any of them have output types different from
4347 : * the top-level setop outputs. We set the UNSAFE_TYPE_MISMATCH bit in
4348 : * unsafeFlags[k] if column k has different type in any component.
4349 : *
4350 : * We don't have to care about typmods here: the only allowed difference
4351 : * between set-op input and output typmods is input is a specific typmod
4352 : * and output is -1, and that does not require a coercion.
4353 : *
4354 : * tlist is a subquery tlist.
4355 : * colTypes is an OID list of the top-level setop's output column types.
4356 : * safetyInfo is the pushdown_safety_info to set unsafeFlags[] for.
4357 : */
4358 : static void
4359 156 : compare_tlist_datatypes(List *tlist, List *colTypes,
4360 : pushdown_safety_info *safetyInfo)
4361 : {
4362 : ListCell *l;
4363 156 : ListCell *colType = list_head(colTypes);
4364 :
4365 492 : foreach(l, tlist)
4366 : {
4367 336 : TargetEntry *tle = (TargetEntry *) lfirst(l);
4368 :
4369 336 : if (tle->resjunk)
4370 0 : continue; /* ignore resjunk columns */
4371 336 : if (colType == NULL)
4372 0 : elog(ERROR, "wrong number of tlist entries");
4373 336 : if (exprType((Node *) tle->expr) != lfirst_oid(colType))
4374 52 : safetyInfo->unsafeFlags[tle->resno] |= UNSAFE_TYPE_MISMATCH;
4375 336 : colType = lnext(colTypes, colType);
4376 : }
4377 156 : if (colType != NULL)
4378 0 : elog(ERROR, "wrong number of tlist entries");
4379 156 : }
4380 :
4381 : /*
4382 : * targetIsInAllPartitionLists
4383 : * True if the TargetEntry is listed in the PARTITION BY clause
4384 : * of every window defined in the query.
4385 : *
4386 : * It would be safe to ignore windows not actually used by any window
4387 : * function, but it's not easy to get that info at this stage; and it's
4388 : * unlikely to be useful to spend any extra cycles getting it, since
4389 : * unreferenced window definitions are probably infrequent in practice.
4390 : */
4391 : static bool
4392 545 : targetIsInAllPartitionLists(TargetEntry *tle, Query *query)
4393 : {
4394 : ListCell *lc;
4395 :
4396 601 : foreach(lc, query->windowClause)
4397 : {
4398 557 : WindowClause *wc = (WindowClause *) lfirst(lc);
4399 :
4400 557 : if (!targetIsInSortList(tle, InvalidOid, wc->partitionClause))
4401 501 : return false;
4402 : }
4403 44 : return true;
4404 : }
4405 :
4406 : /*
4407 : * qual_is_pushdown_safe - is a particular rinfo safe to push down?
4408 : *
4409 : * rinfo is a restriction clause applying to the given subquery (whose RTE
4410 : * has index rti in the parent query).
4411 : *
4412 : * Conditions checked here:
4413 : *
4414 : * 1. rinfo's clause must not contain any SubPlans (mainly because it's
4415 : * unclear that it will work correctly: SubLinks will already have been
4416 : * transformed into SubPlans in the qual, but not in the subquery). Note that
4417 : * SubLinks that transform to initplans are safe, and will be accepted here
4418 : * because what we'll see in the qual is just a Param referencing the initplan
4419 : * output.
4420 : *
4421 : * 2. If unsafeVolatile is set, rinfo's clause must not contain any volatile
4422 : * functions.
4423 : *
4424 : * 3. If unsafeLeaky is set, rinfo's clause must not contain any leaky
4425 : * functions that are passed Var nodes, and therefore might reveal values from
4426 : * the subquery as side effects.
4427 : *
4428 : * 4. rinfo's clause must not refer to the whole-row output of the subquery
4429 : * (since there is no easy way to name that within the subquery itself).
4430 : *
4431 : * 5. rinfo's clause must not refer to any subquery output columns that were
4432 : * found to be unsafe to reference by subquery_is_pushdown_safe().
4433 : */
4434 : static pushdown_safe_type
4435 2508 : qual_is_pushdown_safe(Query *subquery, Index rti, RestrictInfo *rinfo,
4436 : pushdown_safety_info *safetyInfo)
4437 : {
4438 2508 : pushdown_safe_type safe = PUSHDOWN_SAFE;
4439 2508 : Node *qual = (Node *) rinfo->clause;
4440 : List *vars;
4441 : ListCell *vl;
4442 :
4443 : /* Refuse subselects (point 1) */
4444 2508 : if (contain_subplans(qual))
4445 33 : return PUSHDOWN_UNSAFE;
4446 :
4447 : /* Refuse volatile quals if we found they'd be unsafe (point 2) */
4448 2994 : if (safetyInfo->unsafeVolatile &&
4449 519 : contain_volatile_functions((Node *) rinfo))
4450 9 : return PUSHDOWN_UNSAFE;
4451 :
4452 : /* Refuse leaky quals if told to (point 3) */
4453 3974 : if (safetyInfo->unsafeLeaky &&
4454 1508 : contain_leaked_vars(qual))
4455 81 : return PUSHDOWN_UNSAFE;
4456 :
4457 : /*
4458 : * Examine all Vars used in clause. Since it's a restriction clause, all
4459 : * such Vars must refer to subselect output columns ... unless this is
4460 : * part of a LATERAL subquery, in which case there could be lateral
4461 : * references.
4462 : *
4463 : * By omitting the relevant flags, this also gives us a cheap sanity check
4464 : * that no aggregates or window functions appear in the qual. Those would
4465 : * be unsafe to push down, but at least for the moment we could never see
4466 : * any in a qual anyhow.
4467 : */
4468 2385 : vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS);
4469 4521 : foreach(vl, vars)
4470 : {
4471 2439 : Var *var = (Var *) lfirst(vl);
4472 :
4473 : /*
4474 : * XXX Punt if we find any PlaceHolderVars in the restriction clause.
4475 : * It's not clear whether a PHV could safely be pushed down, and even
4476 : * less clear whether such a situation could arise in any cases of
4477 : * practical interest anyway. So for the moment, just refuse to push
4478 : * down.
4479 : */
4480 2439 : if (!IsA(var, Var))
4481 : {
4482 0 : safe = PUSHDOWN_UNSAFE;
4483 0 : break;
4484 : }
4485 :
4486 : /*
4487 : * Punt if we find any lateral references. It would be safe to push
4488 : * these down, but we'd have to convert them into outer references,
4489 : * which subquery_push_qual lacks the infrastructure to do. The case
4490 : * arises so seldom that it doesn't seem worth working hard on.
4491 : */
4492 2439 : if (var->varno != rti)
4493 : {
4494 6 : safe = PUSHDOWN_UNSAFE;
4495 6 : break;
4496 : }
4497 :
4498 : /* Subqueries have no system columns */
4499 : Assert(var->varattno >= 0);
4500 :
4501 : /* Check point 4 */
4502 2433 : if (var->varattno == 0)
4503 : {
4504 0 : safe = PUSHDOWN_UNSAFE;
4505 0 : break;
4506 : }
4507 :
4508 : /* Check point 5 */
4509 2433 : if (safetyInfo->unsafeFlags[var->varattno] != 0)
4510 : {
4511 462 : if (safetyInfo->unsafeFlags[var->varattno] &
4512 : (UNSAFE_HAS_VOLATILE_FUNC | UNSAFE_HAS_SET_FUNC |
4513 : UNSAFE_NOTIN_DISTINCTON_CLAUSE | UNSAFE_TYPE_MISMATCH))
4514 : {
4515 297 : safe = PUSHDOWN_UNSAFE;
4516 297 : break;
4517 : }
4518 : else
4519 : {
4520 : /* UNSAFE_NOTIN_PARTITIONBY_CLAUSE is ok for run conditions */
4521 165 : safe = PUSHDOWN_WINDOWCLAUSE_RUNCOND;
4522 : /* don't break, we might find another Var that's unsafe */
4523 : }
4524 : }
4525 : }
4526 :
4527 2385 : list_free(vars);
4528 :
4529 2385 : return safe;
4530 : }
4531 :
4532 : /*
4533 : * subquery_push_qual - push down a qual that we have determined is safe
4534 : */
4535 : static void
4536 2088 : subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
4537 : {
4538 2088 : if (subquery->setOperations != NULL)
4539 : {
4540 : /* Recurse to push it separately to each component query */
4541 66 : recurse_push_qual(subquery->setOperations, subquery,
4542 : rte, rti, qual);
4543 : }
4544 : else
4545 : {
4546 : /*
4547 : * We need to replace Vars in the qual (which must refer to outputs of
4548 : * the subquery) with copies of the subquery's targetlist expressions.
4549 : * Note that at this point, any uplevel Vars in the qual should have
4550 : * been replaced with Params, so they need no work.
4551 : *
4552 : * This step also ensures that when we are pushing into a setop tree,
4553 : * each component query gets its own copy of the qual.
4554 : */
4555 2022 : qual = ReplaceVarsFromTargetList(qual, rti, 0, rte,
4556 : subquery->targetList,
4557 : subquery->resultRelation,
4558 : REPLACEVARS_REPORT_ERROR, 0,
4559 : &subquery->hasSubLinks);
4560 :
4561 : /*
4562 : * Now attach the qual to the proper place: normally WHERE, but if the
4563 : * subquery uses grouping or aggregation, put it in HAVING (since the
4564 : * qual really refers to the group-result rows).
4565 : */
4566 2022 : if (subquery->hasAggs || subquery->groupClause || subquery->groupingSets || subquery->havingQual)
4567 196 : subquery->havingQual = make_and_qual(subquery->havingQual, qual);
4568 : else
4569 1826 : subquery->jointree->quals =
4570 1826 : make_and_qual(subquery->jointree->quals, qual);
4571 :
4572 : /*
4573 : * We need not change the subquery's hasAggs or hasSubLinks flags,
4574 : * since we can't be pushing down any aggregates that weren't there
4575 : * before, and we don't push down subselects at all.
4576 : */
4577 : }
4578 2088 : }
4579 :
4580 : /*
4581 : * Helper routine to recurse through setOperations tree
4582 : */
4583 : static void
4584 198 : recurse_push_qual(Node *setOp, Query *topquery,
4585 : RangeTblEntry *rte, Index rti, Node *qual)
4586 : {
4587 198 : if (IsA(setOp, RangeTblRef))
4588 : {
4589 132 : RangeTblRef *rtr = (RangeTblRef *) setOp;
4590 132 : RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
4591 132 : Query *subquery = subrte->subquery;
4592 :
4593 : Assert(subquery != NULL);
4594 132 : subquery_push_qual(subquery, rte, rti, qual);
4595 : }
4596 66 : else if (IsA(setOp, SetOperationStmt))
4597 : {
4598 66 : SetOperationStmt *op = (SetOperationStmt *) setOp;
4599 :
4600 66 : recurse_push_qual(op->larg, topquery, rte, rti, qual);
4601 66 : recurse_push_qual(op->rarg, topquery, rte, rti, qual);
4602 : }
4603 : else
4604 : {
4605 0 : elog(ERROR, "unrecognized node type: %d",
4606 : (int) nodeTag(setOp));
4607 : }
4608 198 : }
4609 :
4610 : /*****************************************************************************
4611 : * SIMPLIFYING SUBQUERY TARGETLISTS
4612 : *****************************************************************************/
4613 :
4614 : /*
4615 : * remove_unused_subquery_outputs
4616 : * Remove subquery targetlist items we don't need
4617 : *
4618 : * It's possible, even likely, that the upper query does not read all the
4619 : * output columns of the subquery. We can remove any such outputs that are
4620 : * not needed by the subquery itself (e.g., as sort/group columns) and do not
4621 : * affect semantics otherwise (e.g., volatile functions can't be removed).
4622 : * This is useful not only because we might be able to remove expensive-to-
4623 : * compute expressions, but because deletion of output columns might allow
4624 : * optimizations such as join removal to occur within the subquery.
4625 : *
4626 : * extra_used_attrs can be passed as non-NULL to mark any columns (offset by
4627 : * FirstLowInvalidHeapAttributeNumber) that we should not remove. This
4628 : * parameter is modified by the function, so callers must make a copy if they
4629 : * need to use the passed in Bitmapset after calling this function.
4630 : *
4631 : * To avoid affecting column numbering in the targetlist, we don't physically
4632 : * remove unused tlist entries, but rather replace their expressions with NULL
4633 : * constants. This is implemented by modifying subquery->targetList.
4634 : */
4635 : static void
4636 13383 : remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel,
4637 : Bitmapset *extra_used_attrs)
4638 : {
4639 : Bitmapset *attrs_used;
4640 : ListCell *lc;
4641 :
4642 : /*
4643 : * Just point directly to extra_used_attrs. No need to bms_copy as none of
4644 : * the current callers use the Bitmapset after calling this function.
4645 : */
4646 13383 : attrs_used = extra_used_attrs;
4647 :
4648 : /*
4649 : * Do nothing if subquery has UNION/INTERSECT/EXCEPT: in principle we
4650 : * could update all the child SELECTs' tlists, but it seems not worth the
4651 : * trouble presently.
4652 : */
4653 13383 : if (subquery->setOperations)
4654 1065 : return;
4655 :
4656 : /*
4657 : * If subquery has regular DISTINCT (not DISTINCT ON), we're wasting our
4658 : * time: all its output columns must be used in the distinctClause.
4659 : */
4660 12922 : if (subquery->distinctClause && !subquery->hasDistinctOn)
4661 447 : return;
4662 :
4663 : /*
4664 : * Collect a bitmap of all the output column numbers used by the upper
4665 : * query.
4666 : *
4667 : * Add all the attributes needed for joins or final output. Note: we must
4668 : * look at rel's targetlist, not the attr_needed data, because attr_needed
4669 : * isn't computed for inheritance child rels, cf set_append_rel_size().
4670 : * (XXX might be worth changing that sometime.)
4671 : */
4672 12475 : pull_varattnos((Node *) rel->reltarget->exprs, rel->relid, &attrs_used);
4673 :
4674 : /* Add all the attributes used by un-pushed-down restriction clauses. */
4675 13042 : foreach(lc, rel->baserestrictinfo)
4676 : {
4677 567 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
4678 :
4679 567 : pull_varattnos((Node *) rinfo->clause, rel->relid, &attrs_used);
4680 : }
4681 :
4682 : /*
4683 : * If there's a whole-row reference to the subquery, we can't remove
4684 : * anything.
4685 : */
4686 12475 : if (bms_is_member(0 - FirstLowInvalidHeapAttributeNumber, attrs_used))
4687 157 : return;
4688 :
4689 : /*
4690 : * Run through the tlist and zap entries we don't need. It's okay to
4691 : * modify the tlist items in-place because set_subquery_pathlist made a
4692 : * copy of the subquery.
4693 : */
4694 70855 : foreach(lc, subquery->targetList)
4695 : {
4696 58537 : TargetEntry *tle = (TargetEntry *) lfirst(lc);
4697 58537 : Node *texpr = (Node *) tle->expr;
4698 :
4699 : /*
4700 : * If it has a sortgroupref number, it's used in some sort/group
4701 : * clause so we'd better not remove it. Also, don't remove any
4702 : * resjunk columns, since their reason for being has nothing to do
4703 : * with anybody reading the subquery's output. (It's likely that
4704 : * resjunk columns in a sub-SELECT would always have ressortgroupref
4705 : * set, but even if they don't, it seems imprudent to remove them.)
4706 : */
4707 58537 : if (tle->ressortgroupref || tle->resjunk)
4708 1502 : continue;
4709 :
4710 : /*
4711 : * If it's used by the upper query, we can't remove it.
4712 : */
4713 57035 : if (bms_is_member(tle->resno - FirstLowInvalidHeapAttributeNumber,
4714 : attrs_used))
4715 32600 : continue;
4716 :
4717 : /*
4718 : * If it contains a set-returning function, we can't remove it since
4719 : * that could change the number of rows returned by the subquery.
4720 : */
4721 24981 : if (subquery->hasTargetSRFs &&
4722 546 : expression_returns_set(texpr))
4723 412 : continue;
4724 :
4725 : /*
4726 : * If it contains volatile functions, we daren't remove it for fear
4727 : * that the user is expecting their side-effects to happen.
4728 : */
4729 24023 : if (contain_volatile_functions(texpr))
4730 16 : continue;
4731 :
4732 : /*
4733 : * OK, we don't need it. Replace the expression with a NULL constant.
4734 : * Preserve the exposed type of the expression, in case something
4735 : * looks at the rowtype of the subquery's result.
4736 : */
4737 24007 : tle->expr = (Expr *) makeNullConst(exprType(texpr),
4738 : exprTypmod(texpr),
4739 : exprCollation(texpr));
4740 : }
4741 : }
4742 :
4743 : /*
4744 : * create_partial_bitmap_paths
4745 : * Build partial bitmap heap path for the relation
4746 : */
4747 : void
4748 81359 : create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
4749 : Path *bitmapqual)
4750 : {
4751 : int parallel_workers;
4752 : double pages_fetched;
4753 :
4754 : /* Compute heap pages for bitmap heap scan */
4755 81359 : pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
4756 : NULL, NULL);
4757 :
4758 81359 : parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4759 : max_parallel_workers_per_gather);
4760 :
4761 81359 : if (parallel_workers <= 0)
4762 78871 : return;
4763 :
4764 2488 : add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
4765 : bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4766 : }
4767 :
4768 : /*
4769 : * Compute the number of parallel workers that should be used to scan a
4770 : * relation. We compute the parallel workers based on the size of the heap to
4771 : * be scanned and the size of the index to be scanned, then choose a minimum
4772 : * of those.
4773 : *
4774 : * "heap_pages" is the number of pages from the table that we expect to scan, or
4775 : * -1 if we don't expect to scan any.
4776 : *
4777 : * "index_pages" is the number of pages from the index that we expect to scan, or
4778 : * -1 if we don't expect to scan any.
4779 : *
4780 : * "max_workers" is caller's limit on the number of workers. This typically
4781 : * comes from a GUC.
4782 : */
4783 : int
4784 434901 : compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages,
4785 : int max_workers)
4786 : {
4787 434901 : int parallel_workers = 0;
4788 :
4789 : /*
4790 : * If the user has set the parallel_workers reloption, use that; otherwise
4791 : * select a default number of workers.
4792 : */
4793 434901 : if (rel->rel_parallel_workers != -1)
4794 1650 : parallel_workers = rel->rel_parallel_workers;
4795 : else
4796 : {
4797 : /*
4798 : * If the number of pages being scanned is insufficient to justify a
4799 : * parallel scan, just return zero ... unless it's an inheritance
4800 : * child. In that case, we want to generate a parallel path here
4801 : * anyway. It might not be worthwhile just for this relation, but
4802 : * when combined with all of its inheritance siblings it may well pay
4803 : * off.
4804 : */
4805 433251 : if (rel->reloptkind == RELOPT_BASEREL &&
4806 412853 : ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4807 14334 : (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4808 412365 : return 0;
4809 :
4810 20886 : if (heap_pages >= 0)
4811 : {
4812 : int heap_parallel_threshold;
4813 19820 : int heap_parallel_workers = 1;
4814 :
4815 : /*
4816 : * Select the number of workers based on the log of the size of
4817 : * the relation. This probably needs to be a good deal more
4818 : * sophisticated, but we need something here for now. Note that
4819 : * the upper limit of the min_parallel_table_scan_size GUC is
4820 : * chosen to prevent overflow here.
4821 : */
4822 19820 : heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
4823 22587 : while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
4824 : {
4825 2767 : heap_parallel_workers++;
4826 2767 : heap_parallel_threshold *= 3;
4827 2767 : if (heap_parallel_threshold > INT_MAX / 3)
4828 0 : break; /* avoid overflow */
4829 : }
4830 :
4831 19820 : parallel_workers = heap_parallel_workers;
4832 : }
4833 :
4834 20886 : if (index_pages >= 0)
4835 : {
4836 4991 : int index_parallel_workers = 1;
4837 : int index_parallel_threshold;
4838 :
4839 : /* same calculation as for heap_pages above */
4840 4991 : index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
4841 5129 : while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
4842 : {
4843 138 : index_parallel_workers++;
4844 138 : index_parallel_threshold *= 3;
4845 138 : if (index_parallel_threshold > INT_MAX / 3)
4846 0 : break; /* avoid overflow */
4847 : }
4848 :
4849 4991 : if (parallel_workers > 0)
4850 3925 : parallel_workers = Min(parallel_workers, index_parallel_workers);
4851 : else
4852 1066 : parallel_workers = index_parallel_workers;
4853 : }
4854 : }
4855 :
4856 : /* In no case use more than caller supplied maximum number of workers */
4857 22536 : parallel_workers = Min(parallel_workers, max_workers);
4858 :
4859 22536 : return parallel_workers;
4860 : }
4861 :
4862 : /*
4863 : * generate_partitionwise_join_paths
4864 : * Create paths representing partitionwise join for given partitioned
4865 : * join relation.
4866 : *
4867 : * This must not be called until after we are done adding paths for all
4868 : * child-joins. Otherwise, add_path might delete a path to which some path
4869 : * generated here has a reference.
4870 : */
4871 : void
4872 138637 : generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
4873 : {
4874 138637 : List *live_children = NIL;
4875 : int cnt_parts;
4876 : int num_parts;
4877 : RelOptInfo **part_rels;
4878 :
4879 : /* Handle only join relations here. */
4880 138637 : if (!IS_JOIN_REL(rel))
4881 0 : return;
4882 :
4883 : /* We've nothing to do if the relation is not partitioned. */
4884 138637 : if (!IS_PARTITIONED_REL(rel))
4885 135040 : return;
4886 :
4887 : /* The relation should have consider_partitionwise_join set. */
4888 : Assert(rel->consider_partitionwise_join);
4889 :
4890 : /* Guard against stack overflow due to overly deep partition hierarchy. */
4891 3597 : check_stack_depth();
4892 :
4893 3597 : num_parts = rel->nparts;
4894 3597 : part_rels = rel->part_rels;
4895 :
4896 : /* Collect non-dummy child-joins. */
4897 12820 : for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4898 : {
4899 9223 : RelOptInfo *child_rel = part_rels[cnt_parts];
4900 :
4901 : /* If it's been pruned entirely, it's certainly dummy. */
4902 9223 : if (child_rel == NULL)
4903 32 : continue;
4904 :
4905 : /* Make partitionwise join paths for this partitioned child-join. */
4906 9191 : generate_partitionwise_join_paths(root, child_rel);
4907 :
4908 : /* If we failed to make any path for this child, we must give up. */
4909 9191 : if (child_rel->pathlist == NIL)
4910 : {
4911 : /*
4912 : * Mark the parent joinrel as unpartitioned so that later
4913 : * functions treat it correctly.
4914 : */
4915 0 : rel->nparts = 0;
4916 0 : return;
4917 : }
4918 :
4919 : /* Else, identify the cheapest path for it. */
4920 9191 : set_cheapest(child_rel);
4921 :
4922 : /* Dummy children need not be scanned, so ignore those. */
4923 9191 : if (IS_DUMMY_REL(child_rel))
4924 0 : continue;
4925 :
4926 : /*
4927 : * Except for the topmost scan/join rel, consider generating partial
4928 : * aggregation paths for the grouped relation on top of the paths of
4929 : * this partitioned child-join. After that, we're done creating paths
4930 : * for the grouped relation, so run set_cheapest().
4931 : */
4932 9191 : if (child_rel->grouped_rel != NULL &&
4933 6438 : !bms_equal(IS_OTHER_REL(rel) ?
4934 : rel->top_parent_relids : rel->relids,
4935 6438 : root->all_query_rels))
4936 : {
4937 120 : RelOptInfo *grouped_rel = child_rel->grouped_rel;
4938 :
4939 : Assert(IS_GROUPED_REL(grouped_rel));
4940 :
4941 120 : generate_grouped_paths(root, grouped_rel, child_rel);
4942 120 : set_cheapest(grouped_rel);
4943 : }
4944 :
4945 : #ifdef OPTIMIZER_DEBUG
4946 : pprint(child_rel);
4947 : #endif
4948 :
4949 9191 : live_children = lappend(live_children, child_rel);
4950 : }
4951 :
4952 : /* If all child-joins are dummy, parent join is also dummy. */
4953 3597 : if (!live_children)
4954 : {
4955 0 : mark_dummy_rel(rel);
4956 0 : return;
4957 : }
4958 :
4959 : /* Build additional paths for this rel from child-join paths. */
4960 3597 : add_paths_to_append_rel(root, rel, live_children);
4961 3597 : list_free(live_children);
4962 : }
|
