1 /*-------------------------------------------------------------------------
2 *
3 * allpaths.c
4 * Routines to find possible search paths for processing a query
5 *
6 * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/optimizer/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 #ifdef OPTIMIZER_DEBUG
31 #include "nodes/print.h"
32 #endif
33 #include "optimizer/clauses.h"
34 #include "optimizer/cost.h"
35 #include "optimizer/geqo.h"
36 #include "optimizer/pathnode.h"
37 #include "optimizer/paths.h"
38 #include "optimizer/plancat.h"
39 #include "optimizer/planner.h"
40 #include "optimizer/prep.h"
41 #include "optimizer/restrictinfo.h"
42 #include "optimizer/tlist.h"
43 #include "optimizer/var.h"
44 #include "parser/parse_clause.h"
45 #include "parser/parsetree.h"
46 #include "partitioning/partprune.h"
47 #include "rewrite/rewriteManip.h"
48 #include "utils/lsyscache.h"
49
50
51 /* results of subquery_is_pushdown_safe */
52 typedef struct pushdown_safety_info
53 {
54 bool *unsafeColumns; /* which output columns are unsafe to use */
55 bool unsafeVolatile; /* don't push down volatile quals */
56 bool unsafeLeaky; /* don't push down leaky quals */
57 } pushdown_safety_info;
58
59 /* These parameters are set by GUC */
60 bool enable_geqo = false; /* just in case GUC doesn't set it */
61 int geqo_threshold;
62 int min_parallel_table_scan_size;
63 int min_parallel_index_scan_size;
64
65 /* Hook for plugins to get control in set_rel_pathlist() */
66 set_rel_pathlist_hook_type set_rel_pathlist_hook = NULL;
67
68 /* Hook for plugins to replace standard_join_search() */
69 join_search_hook_type join_search_hook = NULL;
70
71
72 static void set_base_rel_consider_startup(PlannerInfo *root);
73 static void set_base_rel_sizes(PlannerInfo *root);
74 static void set_base_rel_pathlists(PlannerInfo *root);
75 static void set_rel_size(PlannerInfo *root, RelOptInfo *rel,
76 Index rti, RangeTblEntry *rte);
77 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
78 Index rti, RangeTblEntry *rte);
79 static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel,
80 RangeTblEntry *rte);
81 static void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel);
82 static void set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
83 RangeTblEntry *rte);
84 static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
85 RangeTblEntry *rte);
86 static void set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel,
87 RangeTblEntry *rte);
88 static void set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
89 RangeTblEntry *rte);
90 static void set_foreign_size(PlannerInfo *root, RelOptInfo *rel,
91 RangeTblEntry *rte);
92 static void set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel,
93 RangeTblEntry *rte);
94 static void set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
95 Index rti, RangeTblEntry *rte);
96 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
97 Index rti, RangeTblEntry *rte);
98 static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
99 List *live_childrels,
100 List *all_child_pathkeys,
101 List *partitioned_rels);
102 static Path *get_cheapest_parameterized_child_path(PlannerInfo *root,
103 RelOptInfo *rel,
104 Relids required_outer);
105 static void accumulate_append_subpath(Path *path,
106 List **subpaths, List **special_subpaths);
107 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
108 Index rti, RangeTblEntry *rte);
109 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
110 RangeTblEntry *rte);
111 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
112 RangeTblEntry *rte);
113 static void set_tablefunc_pathlist(PlannerInfo *root, RelOptInfo *rel,
114 RangeTblEntry *rte);
115 static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel,
116 RangeTblEntry *rte);
117 static void set_namedtuplestore_pathlist(PlannerInfo *root, RelOptInfo *rel,
118 RangeTblEntry *rte);
119 static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel,
120 RangeTblEntry *rte);
121 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
122 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
123 pushdown_safety_info *safetyInfo);
124 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
125 pushdown_safety_info *safetyInfo);
126 static void check_output_expressions(Query *subquery,
127 pushdown_safety_info *safetyInfo);
128 static void compare_tlist_datatypes(List *tlist, List *colTypes,
129 pushdown_safety_info *safetyInfo);
130 static bool targetIsInAllPartitionLists(TargetEntry *tle, Query *query);
131 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
132 pushdown_safety_info *safetyInfo);
133 static void subquery_push_qual(Query *subquery,
134 RangeTblEntry *rte, Index rti, Node *qual);
135 static void recurse_push_qual(Node *setOp, Query *topquery,
136 RangeTblEntry *rte, Index rti, Node *qual);
137 static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel);
138
139
140 /*
141 * make_one_rel
142 * Finds all possible access paths for executing a query, returning a
143 * single rel that represents the join of all base rels in the query.
144 */
145 RelOptInfo *
make_one_rel(PlannerInfo * root,List * joinlist)146 make_one_rel(PlannerInfo *root, List *joinlist)
147 {
148 RelOptInfo *rel;
149 Index rti;
150
151 /*
152 * Construct the all_baserels Relids set.
153 */
154 root->all_baserels = NULL;
155 for (rti = 1; rti < root->simple_rel_array_size; rti++)
156 {
157 RelOptInfo *brel = root->simple_rel_array[rti];
158
159 /* there may be empty slots corresponding to non-baserel RTEs */
160 if (brel == NULL)
161 continue;
162
163 Assert(brel->relid == rti); /* sanity check on array */
164
165 /* ignore RTEs that are "other rels" */
166 if (brel->reloptkind != RELOPT_BASEREL)
167 continue;
168
169 root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
170 }
171
172 /* Mark base rels as to whether we care about fast-start plans */
173 set_base_rel_consider_startup(root);
174
175 /*
176 * Compute size estimates and consider_parallel flags for each base rel,
177 * then generate access paths.
178 */
179 set_base_rel_sizes(root);
180 set_base_rel_pathlists(root);
181
182 /*
183 * Generate access paths for the entire join tree.
184 */
185 rel = make_rel_from_joinlist(root, joinlist);
186
187 /*
188 * The result should join all and only the query's base rels.
189 */
190 Assert(bms_equal(rel->relids, root->all_baserels));
191
192 return rel;
193 }
194
195 /*
196 * set_base_rel_consider_startup
197 * Set the consider_[param_]startup flags for each base-relation entry.
198 *
199 * For the moment, we only deal with consider_param_startup here; because the
200 * logic for consider_startup is pretty trivial and is the same for every base
201 * relation, we just let build_simple_rel() initialize that flag correctly to
202 * start with. If that logic ever gets more complicated it would probably
203 * be better to move it here.
204 */
205 static void
set_base_rel_consider_startup(PlannerInfo * root)206 set_base_rel_consider_startup(PlannerInfo *root)
207 {
208 /*
209 * Since parameterized paths can only be used on the inside of a nestloop
210 * join plan, there is usually little value in considering fast-start
211 * plans for them. However, for relations that are on the RHS of a SEMI
212 * or ANTI join, a fast-start plan can be useful because we're only going
213 * to care about fetching one tuple anyway.
214 *
215 * To minimize growth of planning time, we currently restrict this to
216 * cases where the RHS is a single base relation, not a join; there is no
217 * provision for consider_param_startup to get set at all on joinrels.
218 * Also we don't worry about appendrels. costsize.c's costing rules for
219 * nestloop semi/antijoins don't consider such cases either.
220 */
221 ListCell *lc;
222
223 foreach(lc, root->join_info_list)
224 {
225 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
226 int varno;
227
228 if ((sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI) &&
229 bms_get_singleton_member(sjinfo->syn_righthand, &varno))
230 {
231 RelOptInfo *rel = find_base_rel(root, varno);
232
233 rel->consider_param_startup = true;
234 }
235 }
236 }
237
238 /*
239 * set_base_rel_sizes
240 * Set the size estimates (rows and widths) for each base-relation entry.
241 * Also determine whether to consider parallel paths for base relations.
242 *
243 * We do this in a separate pass over the base rels so that rowcount
244 * estimates are available for parameterized path generation, and also so
245 * that each rel's consider_parallel flag is set correctly before we begin to
246 * generate paths.
247 */
248 static void
set_base_rel_sizes(PlannerInfo * root)249 set_base_rel_sizes(PlannerInfo *root)
250 {
251 Index rti;
252
253 for (rti = 1; rti < root->simple_rel_array_size; rti++)
254 {
255 RelOptInfo *rel = root->simple_rel_array[rti];
256 RangeTblEntry *rte;
257
258 /* there may be empty slots corresponding to non-baserel RTEs */
259 if (rel == NULL)
260 continue;
261
262 Assert(rel->relid == rti); /* sanity check on array */
263
264 /* ignore RTEs that are "other rels" */
265 if (rel->reloptkind != RELOPT_BASEREL)
266 continue;
267
268 rte = root->simple_rte_array[rti];
269
270 /*
271 * If parallelism is allowable for this query in general, see whether
272 * it's allowable for this rel in particular. We have to do this
273 * before set_rel_size(), because (a) if this rel is an inheritance
274 * parent, set_append_rel_size() will use and perhaps change the rel's
275 * consider_parallel flag, and (b) for some RTE types, set_rel_size()
276 * goes ahead and makes paths immediately.
277 */
278 if (root->glob->parallelModeOK)
279 set_rel_consider_parallel(root, rel, rte);
280
281 set_rel_size(root, rel, rti, rte);
282 }
283 }
284
285 /*
286 * set_base_rel_pathlists
287 * Finds all paths available for scanning each base-relation entry.
288 * Sequential scan and any available indices are considered.
289 * Each useful path is attached to its relation's 'pathlist' field.
290 */
291 static void
set_base_rel_pathlists(PlannerInfo * root)292 set_base_rel_pathlists(PlannerInfo *root)
293 {
294 Index rti;
295
296 for (rti = 1; rti < root->simple_rel_array_size; rti++)
297 {
298 RelOptInfo *rel = root->simple_rel_array[rti];
299
300 /* there may be empty slots corresponding to non-baserel RTEs */
301 if (rel == NULL)
302 continue;
303
304 Assert(rel->relid == rti); /* sanity check on array */
305
306 /* ignore RTEs that are "other rels" */
307 if (rel->reloptkind != RELOPT_BASEREL)
308 continue;
309
310 set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
311 }
312 }
313
314 /*
315 * set_rel_size
316 * Set size estimates for a base relation
317 */
318 static void
set_rel_size(PlannerInfo * root,RelOptInfo * rel,Index rti,RangeTblEntry * rte)319 set_rel_size(PlannerInfo *root, RelOptInfo *rel,
320 Index rti, RangeTblEntry *rte)
321 {
322 if (rel->reloptkind == RELOPT_BASEREL &&
323 relation_excluded_by_constraints(root, rel, rte))
324 {
325 /*
326 * We proved we don't need to scan the rel via constraint exclusion,
327 * so set up a single dummy path for it. Here we only check this for
328 * regular baserels; if it's an otherrel, CE was already checked in
329 * set_append_rel_size().
330 *
331 * In this case, we go ahead and set up the relation's path right away
332 * instead of leaving it for set_rel_pathlist to do. This is because
333 * we don't have a convention for marking a rel as dummy except by
334 * assigning a dummy path to it.
335 */
336 set_dummy_rel_pathlist(rel);
337 }
338 else if (rte->inh)
339 {
340 /* It's an "append relation", process accordingly */
341 set_append_rel_size(root, rel, rti, rte);
342 }
343 else
344 {
345 switch (rel->rtekind)
346 {
347 case RTE_RELATION:
348 if (rte->relkind == RELKIND_FOREIGN_TABLE)
349 {
350 /* Foreign table */
351 set_foreign_size(root, rel, rte);
352 }
353 else if (rte->relkind == RELKIND_PARTITIONED_TABLE)
354 {
355 /*
356 * A partitioned table without any partitions is marked as
357 * a dummy rel.
358 */
359 set_dummy_rel_pathlist(rel);
360 }
361 else if (rte->tablesample != NULL)
362 {
363 /* Sampled relation */
364 set_tablesample_rel_size(root, rel, rte);
365 }
366 else
367 {
368 /* Plain relation */
369 set_plain_rel_size(root, rel, rte);
370 }
371 break;
372 case RTE_SUBQUERY:
373
374 /*
375 * Subqueries don't support making a choice between
376 * parameterized and unparameterized paths, so just go ahead
377 * and build their paths immediately.
378 */
379 set_subquery_pathlist(root, rel, rti, rte);
380 break;
381 case RTE_FUNCTION:
382 set_function_size_estimates(root, rel);
383 break;
384 case RTE_TABLEFUNC:
385 set_tablefunc_size_estimates(root, rel);
386 break;
387 case RTE_VALUES:
388 set_values_size_estimates(root, rel);
389 break;
390 case RTE_CTE:
391
392 /*
393 * CTEs don't support making a choice between parameterized
394 * and unparameterized paths, so just go ahead and build their
395 * paths immediately.
396 */
397 if (rte->self_reference)
398 set_worktable_pathlist(root, rel, rte);
399 else
400 set_cte_pathlist(root, rel, rte);
401 break;
402 case RTE_NAMEDTUPLESTORE:
403 set_namedtuplestore_pathlist(root, rel, rte);
404 break;
405 default:
406 elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind);
407 break;
408 }
409 }
410
411 /*
412 * We insist that all non-dummy rels have a nonzero rowcount estimate.
413 */
414 Assert(rel->rows > 0 || IS_DUMMY_REL(rel));
415 }
416
417 /*
418 * set_rel_pathlist
419 * Build access paths for a base relation
420 */
421 static void
set_rel_pathlist(PlannerInfo * root,RelOptInfo * rel,Index rti,RangeTblEntry * rte)422 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
423 Index rti, RangeTblEntry *rte)
424 {
425 if (IS_DUMMY_REL(rel))
426 {
427 /* We already proved the relation empty, so nothing more to do */
428 }
429 else if (rte->inh)
430 {
431 /* It's an "append relation", process accordingly */
432 set_append_rel_pathlist(root, rel, rti, rte);
433 }
434 else
435 {
436 switch (rel->rtekind)
437 {
438 case RTE_RELATION:
439 if (rte->relkind == RELKIND_FOREIGN_TABLE)
440 {
441 /* Foreign table */
442 set_foreign_pathlist(root, rel, rte);
443 }
444 else if (rte->tablesample != NULL)
445 {
446 /* Sampled relation */
447 set_tablesample_rel_pathlist(root, rel, rte);
448 }
449 else
450 {
451 /* Plain relation */
452 set_plain_rel_pathlist(root, rel, rte);
453 }
454 break;
455 case RTE_SUBQUERY:
456 /* Subquery --- fully handled during set_rel_size */
457 break;
458 case RTE_FUNCTION:
459 /* RangeFunction */
460 set_function_pathlist(root, rel, rte);
461 break;
462 case RTE_TABLEFUNC:
463 /* Table Function */
464 set_tablefunc_pathlist(root, rel, rte);
465 break;
466 case RTE_VALUES:
467 /* Values list */
468 set_values_pathlist(root, rel, rte);
469 break;
470 case RTE_CTE:
471 /* CTE reference --- fully handled during set_rel_size */
472 break;
473 case RTE_NAMEDTUPLESTORE:
474 /* tuplestore reference --- fully handled during set_rel_size */
475 break;
476 default:
477 elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind);
478 break;
479 }
480 }
481
482 /*
483 * Allow a plugin to editorialize on the set of Paths for this base
484 * relation. It could add new paths (such as CustomPaths) by calling
485 * add_path(), or add_partial_path() if parallel aware. It could also
486 * delete or modify paths added by the core code.
487 */
488 if (set_rel_pathlist_hook)
489 (*set_rel_pathlist_hook) (root, rel, rti, rte);
490
491 /*
492 * If this is a baserel, we should normally consider gathering any partial
493 * paths we may have created for it. We have to do this after calling the
494 * set_rel_pathlist_hook, else it cannot add partial paths to be included
495 * here.
496 *
497 * However, if this is an inheritance child, skip it. Otherwise, we could
498 * end up with a very large number of gather nodes, each trying to grab
499 * its own pool of workers. Instead, we'll consider gathering partial
500 * paths for the parent appendrel.
501 *
502 * Also, if this is the topmost scan/join rel (that is, the only baserel),
503 * we postpone gathering until the final scan/join targetlist is available
504 * (see grouping_planner).
505 */
506 if (rel->reloptkind == RELOPT_BASEREL &&
507 bms_membership(root->all_baserels) != BMS_SINGLETON)
508 generate_gather_paths(root, rel, false);
509
510 /* Now find the cheapest of the paths for this rel */
511 set_cheapest(rel);
512
513 #ifdef OPTIMIZER_DEBUG
514 debug_print_rel(root, rel);
515 #endif
516 }
517
518 /*
519 * set_plain_rel_size
520 * Set size estimates for a plain relation (no subquery, no inheritance)
521 */
522 static void
set_plain_rel_size(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)523 set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
524 {
525 /*
526 * Test any partial indexes of rel for applicability. We must do this
527 * first since partial unique indexes can affect size estimates.
528 */
529 check_index_predicates(root, rel);
530
531 /* Mark rel with estimated output rows, width, etc */
532 set_baserel_size_estimates(root, rel);
533 }
534
535 /*
536 * If this relation could possibly be scanned from within a worker, then set
537 * its consider_parallel flag.
538 */
539 static void
set_rel_consider_parallel(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)540 set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
541 RangeTblEntry *rte)
542 {
543 /*
544 * The flag has previously been initialized to false, so we can just
545 * return if it becomes clear that we can't safely set it.
546 */
547 Assert(!rel->consider_parallel);
548
549 /* Don't call this if parallelism is disallowed for the entire query. */
550 Assert(root->glob->parallelModeOK);
551
552 /* This should only be called for baserels and appendrel children. */
553 Assert(IS_SIMPLE_REL(rel));
554
555 /* Assorted checks based on rtekind. */
556 switch (rte->rtekind)
557 {
558 case RTE_RELATION:
559
560 /*
561 * Currently, parallel workers can't access the leader's temporary
562 * tables. We could possibly relax this if we wrote all of its
563 * local buffers at the start of the query and made no changes
564 * thereafter (maybe we could allow hint bit changes), and if we
565 * taught the workers to read them. Writing a large number of
566 * temporary buffers could be expensive, though, and we don't have
567 * the rest of the necessary infrastructure right now anyway. So
568 * for now, bail out if we see a temporary table.
569 */
570 if (get_rel_persistence(rte->relid) == RELPERSISTENCE_TEMP)
571 return;
572
573 /*
574 * Table sampling can be pushed down to workers if the sample
575 * function and its arguments are safe.
576 */
577 if (rte->tablesample != NULL)
578 {
579 char proparallel = func_parallel(rte->tablesample->tsmhandler);
580
581 if (proparallel != PROPARALLEL_SAFE)
582 return;
583 if (!is_parallel_safe(root, (Node *) rte->tablesample->args))
584 return;
585 }
586
587 /*
588 * Ask FDWs whether they can support performing a ForeignScan
589 * within a worker. Most often, the answer will be no. For
590 * example, if the nature of the FDW is such that it opens a TCP
591 * connection with a remote server, each parallel worker would end
592 * up with a separate connection, and these connections might not
593 * be appropriately coordinated between workers and the leader.
594 */
595 if (rte->relkind == RELKIND_FOREIGN_TABLE)
596 {
597 Assert(rel->fdwroutine);
598 if (!rel->fdwroutine->IsForeignScanParallelSafe)
599 return;
600 if (!rel->fdwroutine->IsForeignScanParallelSafe(root, rel, rte))
601 return;
602 }
603
604 /*
605 * There are additional considerations for appendrels, which we'll
606 * deal with in set_append_rel_size and set_append_rel_pathlist.
607 * For now, just set consider_parallel based on the rel's own
608 * quals and targetlist.
609 */
610 break;
611
612 case RTE_SUBQUERY:
613
614 /*
615 * There's no intrinsic problem with scanning a subquery-in-FROM
616 * (as distinct from a SubPlan or InitPlan) in a parallel worker.
617 * If the subquery doesn't happen to have any parallel-safe paths,
618 * then flagging it as consider_parallel won't change anything,
619 * but that's true for plain tables, too. We must set
620 * consider_parallel based on the rel's own quals and targetlist,
621 * so that if a subquery path is parallel-safe but the quals and
622 * projection we're sticking onto it are not, we correctly mark
623 * the SubqueryScanPath as not parallel-safe. (Note that
624 * set_subquery_pathlist() might push some of these quals down
625 * into the subquery itself, but that doesn't change anything.)
626 *
627 * We can't push sub-select containing LIMIT/OFFSET to workers as
628 * there is no guarantee that the row order will be fully
629 * deterministic, and applying LIMIT/OFFSET will lead to
630 * inconsistent results at the top-level. (In some cases, where
631 * the result is ordered, we could relax this restriction. But it
632 * doesn't currently seem worth expending extra effort to do so.)
633 */
634 {
635 Query *subquery = castNode(Query, rte->subquery);
636
637 if (limit_needed(subquery))
638 return;
639 }
640 break;
641
642 case RTE_JOIN:
643 /* Shouldn't happen; we're only considering baserels here. */
644 Assert(false);
645 return;
646
647 case RTE_FUNCTION:
648 /* Check for parallel-restricted functions. */
649 if (!is_parallel_safe(root, (Node *) rte->functions))
650 return;
651 break;
652
653 case RTE_TABLEFUNC:
654 /* not parallel safe */
655 return;
656
657 case RTE_VALUES:
658 /* Check for parallel-restricted functions. */
659 if (!is_parallel_safe(root, (Node *) rte->values_lists))
660 return;
661 break;
662
663 case RTE_CTE:
664
665 /*
666 * CTE tuplestores aren't shared among parallel workers, so we
667 * force all CTE scans to happen in the leader. Also, populating
668 * the CTE would require executing a subplan that's not available
669 * in the worker, might be parallel-restricted, and must get
670 * executed only once.
671 */
672 return;
673
674 case RTE_NAMEDTUPLESTORE:
675
676 /*
677 * tuplestore cannot be shared, at least without more
678 * infrastructure to support that.
679 */
680 return;
681 }
682
683 /*
684 * If there's anything in baserestrictinfo that's parallel-restricted, we
685 * give up on parallelizing access to this relation. We could consider
686 * instead postponing application of the restricted quals until we're
687 * above all the parallelism in the plan tree, but it's not clear that
688 * that would be a win in very many cases, and it might be tricky to make
689 * outer join clauses work correctly. It would likely break equivalence
690 * classes, too.
691 */
692 if (!is_parallel_safe(root, (Node *) rel->baserestrictinfo))
693 return;
694
695 /*
696 * Likewise, if the relation's outputs are not parallel-safe, give up.
697 * (Usually, they're just Vars, but sometimes they're not.)
698 */
699 if (!is_parallel_safe(root, (Node *) rel->reltarget->exprs))
700 return;
701
702 /* We have a winner. */
703 rel->consider_parallel = true;
704 }
705
706 /*
707 * set_plain_rel_pathlist
708 * Build access paths for a plain relation (no subquery, no inheritance)
709 */
710 static void
set_plain_rel_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)711 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
712 {
713 Relids required_outer;
714
715 /*
716 * We don't support pushing join clauses into the quals of a seqscan, but
717 * it could still have required parameterization due to LATERAL refs in
718 * its tlist.
719 */
720 required_outer = rel->lateral_relids;
721
722 /* Consider sequential scan */
723 add_path(rel, create_seqscan_path(root, rel, required_outer, 0));
724
725 /* If appropriate, consider parallel sequential scan */
726 if (rel->consider_parallel && required_outer == NULL)
727 create_plain_partial_paths(root, rel);
728
729 /* Consider index scans */
730 create_index_paths(root, rel);
731
732 /* Consider TID scans */
733 create_tidscan_paths(root, rel);
734 }
735
736 /*
737 * create_plain_partial_paths
738 * Build partial access paths for parallel scan of a plain relation
739 */
740 static void
create_plain_partial_paths(PlannerInfo * root,RelOptInfo * rel)741 create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel)
742 {
743 int parallel_workers;
744
745 parallel_workers = compute_parallel_worker(rel, rel->pages, -1,
746 max_parallel_workers_per_gather);
747
748 /* If any limit was set to zero, the user doesn't want a parallel scan. */
749 if (parallel_workers <= 0)
750 return;
751
752 /* Add an unordered partial path based on a parallel sequential scan. */
753 add_partial_path(rel, create_seqscan_path(root, rel, NULL, parallel_workers));
754 }
755
756 /*
757 * set_tablesample_rel_size
758 * Set size estimates for a sampled relation
759 */
760 static void
set_tablesample_rel_size(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)761 set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
762 {
763 TableSampleClause *tsc = rte->tablesample;
764 TsmRoutine *tsm;
765 BlockNumber pages;
766 double tuples;
767
768 /*
769 * Test any partial indexes of rel for applicability. We must do this
770 * first since partial unique indexes can affect size estimates.
771 */
772 check_index_predicates(root, rel);
773
774 /*
775 * Call the sampling method's estimation function to estimate the number
776 * of pages it will read and the number of tuples it will return. (Note:
777 * we assume the function returns sane values.)
778 */
779 tsm = GetTsmRoutine(tsc->tsmhandler);
780 tsm->SampleScanGetSampleSize(root, rel, tsc->args,
781 &pages, &tuples);
782
783 /*
784 * For the moment, because we will only consider a SampleScan path for the
785 * rel, it's okay to just overwrite the pages and tuples estimates for the
786 * whole relation. If we ever consider multiple path types for sampled
787 * rels, we'll need more complication.
788 */
789 rel->pages = pages;
790 rel->tuples = tuples;
791
792 /* Mark rel with estimated output rows, width, etc */
793 set_baserel_size_estimates(root, rel);
794 }
795
796 /*
797 * set_tablesample_rel_pathlist
798 * Build access paths for a sampled relation
799 */
800 static void
set_tablesample_rel_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)801 set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
802 {
803 Relids required_outer;
804 Path *path;
805
806 /*
807 * We don't support pushing join clauses into the quals of a samplescan,
808 * but it could still have required parameterization due to LATERAL refs
809 * in its tlist or TABLESAMPLE arguments.
810 */
811 required_outer = rel->lateral_relids;
812
813 /* Consider sampled scan */
814 path = create_samplescan_path(root, rel, required_outer);
815
816 /*
817 * If the sampling method does not support repeatable scans, we must avoid
818 * plans that would scan the rel multiple times. Ideally, we'd simply
819 * avoid putting the rel on the inside of a nestloop join; but adding such
820 * a consideration to the planner seems like a great deal of complication
821 * to support an uncommon usage of second-rate sampling methods. Instead,
822 * if there is a risk that the query might perform an unsafe join, just
823 * wrap the SampleScan in a Materialize node. We can check for joins by
824 * counting the membership of all_baserels (note that this correctly
825 * counts inheritance trees as single rels). If we're inside a subquery,
826 * we can't easily check whether a join might occur in the outer query, so
827 * just assume one is possible.
828 *
829 * GetTsmRoutine is relatively expensive compared to the other tests here,
830 * so check repeatable_across_scans last, even though that's a bit odd.
831 */
832 if ((root->query_level > 1 ||
833 bms_membership(root->all_baserels) != BMS_SINGLETON) &&
834 !(GetTsmRoutine(rte->tablesample->tsmhandler)->repeatable_across_scans))
835 {
836 path = (Path *) create_material_path(rel, path);
837 }
838
839 add_path(rel, path);
840
841 /* For the moment, at least, there are no other paths to consider */
842 }
843
844 /*
845 * set_foreign_size
846 * Set size estimates for a foreign table RTE
847 */
848 static void
set_foreign_size(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)849 set_foreign_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
850 {
851 /* Mark rel with estimated output rows, width, etc */
852 set_foreign_size_estimates(root, rel);
853
854 /* Let FDW adjust the size estimates, if it can */
855 rel->fdwroutine->GetForeignRelSize(root, rel, rte->relid);
856
857 /* ... but do not let it set the rows estimate to zero */
858 rel->rows = clamp_row_est(rel->rows);
859
860 /* also, make sure rel->tuples is not insane relative to rel->rows */
861 rel->tuples = Max(rel->tuples, rel->rows);
862 }
863
864 /*
865 * set_foreign_pathlist
866 * Build access paths for a foreign table RTE
867 */
868 static void
set_foreign_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)869 set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
870 {
871 /* Call the FDW's GetForeignPaths function to generate path(s) */
872 rel->fdwroutine->GetForeignPaths(root, rel, rte->relid);
873 }
874
875 /*
876 * set_append_rel_size
877 * Set size estimates for a simple "append relation"
878 *
879 * The passed-in rel and RTE represent the entire append relation. The
880 * relation's contents are computed by appending together the output of the
881 * individual member relations. Note that in the non-partitioned inheritance
882 * case, the first member relation is actually the same table as is mentioned
883 * in the parent RTE ... but it has a different RTE and RelOptInfo. This is
884 * a good thing because their outputs are not the same size.
885 */
886 static void
set_append_rel_size(PlannerInfo * root,RelOptInfo * rel,Index rti,RangeTblEntry * rte)887 set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
888 Index rti, RangeTblEntry *rte)
889 {
890 int parentRTindex = rti;
891 bool has_live_children;
892 double parent_rows;
893 double parent_size;
894 double *parent_attrsizes;
895 int nattrs;
896 ListCell *l;
897 Relids live_children = NULL;
898 bool did_pruning = false;
899
900 /* Guard against stack overflow due to overly deep inheritance tree. */
901 check_stack_depth();
902
903 Assert(IS_SIMPLE_REL(rel));
904
905 /*
906 * Initialize partitioned_child_rels to contain this RT index.
907 *
908 * Note that during the set_append_rel_pathlist() phase, we will bubble up
909 * the indexes of partitioned relations that appear down in the tree, so
910 * that when we've created Paths for all the children, the root
911 * partitioned table's list will contain all such indexes.
912 */
913 if (rte->relkind == RELKIND_PARTITIONED_TABLE)
914 rel->partitioned_child_rels = list_make1_int(rti);
915
916 /*
917 * If the partitioned relation has any baserestrictinfo quals then we
918 * attempt to use these quals to prune away partitions that cannot
919 * possibly contain any tuples matching these quals. In this case we'll
920 * store the relids of all partitions which could possibly contain a
921 * matching tuple, and skip anything else in the loop below.
922 */
923 if (enable_partition_pruning &&
924 rte->relkind == RELKIND_PARTITIONED_TABLE &&
925 rel->baserestrictinfo != NIL)
926 {
927 live_children = prune_append_rel_partitions(rel);
928 did_pruning = true;
929 }
930
931 /*
932 * If this is a partitioned baserel, set the consider_partitionwise_join
933 * flag; currently, we only consider partitionwise joins with the baserel
934 * if its targetlist doesn't contain a whole-row Var.
935 */
936 if (enable_partitionwise_join &&
937 rel->reloptkind == RELOPT_BASEREL &&
938 rte->relkind == RELKIND_PARTITIONED_TABLE &&
939 rel->attr_needed[InvalidAttrNumber - rel->min_attr] == NULL)
940 rel->consider_partitionwise_join = true;
941
942 /*
943 * Initialize to compute size estimates for whole append relation.
944 *
945 * We handle width estimates by weighting the widths of different child
946 * rels proportionally to their number of rows. This is sensible because
947 * the use of width estimates is mainly to compute the total relation
948 * "footprint" if we have to sort or hash it. To do this, we sum the
949 * total equivalent size (in "double" arithmetic) and then divide by the
950 * total rowcount estimate. This is done separately for the total rel
951 * width and each attribute.
952 *
953 * Note: if you consider changing this logic, beware that child rels could
954 * have zero rows and/or width, if they were excluded by constraints.
955 */
956 has_live_children = false;
957 parent_rows = 0;
958 parent_size = 0;
959 nattrs = rel->max_attr - rel->min_attr + 1;
960 parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
961
962 foreach(l, root->append_rel_list)
963 {
964 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
965 int childRTindex;
966 RangeTblEntry *childRTE;
967 RelOptInfo *childrel;
968 List *childquals;
969 Index cq_min_security;
970 bool have_const_false_cq;
971 ListCell *parentvars;
972 ListCell *childvars;
973 ListCell *lc;
974
975 /* append_rel_list contains all append rels; ignore others */
976 if (appinfo->parent_relid != parentRTindex)
977 continue;
978
979 childRTindex = appinfo->child_relid;
980 childRTE = root->simple_rte_array[childRTindex];
981
982 /*
983 * The child rel's RelOptInfo was already created during
984 * add_base_rels_to_query.
985 */
986 childrel = find_base_rel(root, childRTindex);
987 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
988
989 /*
990 * We have to copy the parent's targetlist and quals to the child,
991 * with appropriate substitution of variables. However, only the
992 * baserestrictinfo quals are needed before we can check for
993 * constraint exclusion; so do that first and then check to see if we
994 * can disregard this child.
995 *
996 * The child rel's targetlist might contain non-Var expressions, which
997 * means that substitution into the quals could produce opportunities
998 * for const-simplification, and perhaps even pseudoconstant quals.
999 * Therefore, transform each RestrictInfo separately to see if it
1000 * reduces to a constant or pseudoconstant. (We must process them
1001 * separately to keep track of the security level of each qual.)
1002 */
1003 childquals = NIL;
1004 cq_min_security = UINT_MAX;
1005 have_const_false_cq = false;
1006 foreach(lc, rel->baserestrictinfo)
1007 {
1008 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1009 Node *childqual;
1010 ListCell *lc2;
1011
1012 Assert(IsA(rinfo, RestrictInfo));
1013 childqual = adjust_appendrel_attrs(root,
1014 (Node *) rinfo->clause,
1015 1, &appinfo);
1016 childqual = eval_const_expressions(root, childqual);
1017 /* check for flat-out constant */
1018 if (childqual && IsA(childqual, Const))
1019 {
1020 if (((Const *) childqual)->constisnull ||
1021 !DatumGetBool(((Const *) childqual)->constvalue))
1022 {
1023 /* Restriction reduces to constant FALSE or NULL */
1024 have_const_false_cq = true;
1025 break;
1026 }
1027 /* Restriction reduces to constant TRUE, so drop it */
1028 continue;
1029 }
1030 /* might have gotten an AND clause, if so flatten it */
1031 foreach(lc2, make_ands_implicit((Expr *) childqual))
1032 {
1033 Node *onecq = (Node *) lfirst(lc2);
1034 bool pseudoconstant;
1035
1036 /* check for pseudoconstant (no Vars or volatile functions) */
1037 pseudoconstant =
1038 !contain_vars_of_level(onecq, 0) &&
1039 !contain_volatile_functions(onecq);
1040 if (pseudoconstant)
1041 {
1042 /* tell createplan.c to check for gating quals */
1043 root->hasPseudoConstantQuals = true;
1044 }
1045 /* reconstitute RestrictInfo with appropriate properties */
1046 childquals = lappend(childquals,
1047 make_restrictinfo((Expr *) onecq,
1048 rinfo->is_pushed_down,
1049 rinfo->outerjoin_delayed,
1050 pseudoconstant,
1051 rinfo->security_level,
1052 NULL, NULL, NULL));
1053 /* track minimum security level among child quals */
1054 cq_min_security = Min(cq_min_security, rinfo->security_level);
1055 }
1056 }
1057
1058 /*
1059 * In addition to the quals inherited from the parent, we might have
1060 * securityQuals associated with this particular child node.
1061 * (Currently this can only happen in appendrels originating from
1062 * UNION ALL; inheritance child tables don't have their own
1063 * securityQuals, see expand_inherited_rtentry().) Pull any such
1064 * securityQuals up into the baserestrictinfo for the child. This is
1065 * similar to process_security_barrier_quals() for the parent rel,
1066 * except that we can't make any general deductions from such quals,
1067 * since they don't hold for the whole appendrel.
1068 */
1069 if (childRTE->securityQuals)
1070 {
1071 Index security_level = 0;
1072
1073 foreach(lc, childRTE->securityQuals)
1074 {
1075 List *qualset = (List *) lfirst(lc);
1076 ListCell *lc2;
1077
1078 foreach(lc2, qualset)
1079 {
1080 Expr *qual = (Expr *) lfirst(lc2);
1081
1082 /* not likely that we'd see constants here, so no check */
1083 childquals = lappend(childquals,
1084 make_restrictinfo(qual,
1085 true, false, false,
1086 security_level,
1087 NULL, NULL, NULL));
1088 cq_min_security = Min(cq_min_security, security_level);
1089 }
1090 security_level++;
1091 }
1092 Assert(security_level <= root->qual_security_level);
1093 }
1094
1095 /*
1096 * OK, we've got all the baserestrictinfo quals for this child.
1097 */
1098 childrel->baserestrictinfo = childquals;
1099 childrel->baserestrict_min_security = cq_min_security;
1100
1101 if (have_const_false_cq)
1102 {
1103 /*
1104 * Some restriction clause reduced to constant FALSE or NULL after
1105 * substitution, so this child need not be scanned.
1106 */
1107 set_dummy_rel_pathlist(childrel);
1108 continue;
1109 }
1110
1111 if (did_pruning && !bms_is_member(appinfo->child_relid, live_children))
1112 {
1113 /* This partition was pruned; skip it. */
1114 set_dummy_rel_pathlist(childrel);
1115 continue;
1116 }
1117
1118 if (relation_excluded_by_constraints(root, childrel, childRTE))
1119 {
1120 /*
1121 * This child need not be scanned, so we can omit it from the
1122 * appendrel.
1123 */
1124 set_dummy_rel_pathlist(childrel);
1125 continue;
1126 }
1127
1128 /*
1129 * CE failed, so finish copying/modifying targetlist and join quals.
1130 *
1131 * NB: the resulting childrel->reltarget->exprs may contain arbitrary
1132 * expressions, which otherwise would not occur in a rel's targetlist.
1133 * Code that might be looking at an appendrel child must cope with
1134 * such. (Normally, a rel's targetlist would only include Vars and
1135 * PlaceHolderVars.) XXX we do not bother to update the cost or width
1136 * fields of childrel->reltarget; not clear if that would be useful.
1137 */
1138 childrel->joininfo = (List *)
1139 adjust_appendrel_attrs(root,
1140 (Node *) rel->joininfo,
1141 1, &appinfo);
1142 childrel->reltarget->exprs = (List *)
1143 adjust_appendrel_attrs(root,
1144 (Node *) rel->reltarget->exprs,
1145 1, &appinfo);
1146
1147 /*
1148 * We have to make child entries in the EquivalenceClass data
1149 * structures as well. This is needed either if the parent
1150 * participates in some eclass joins (because we will want to consider
1151 * inner-indexscan joins on the individual children) or if the parent
1152 * has useful pathkeys (because we should try to build MergeAppend
1153 * paths that produce those sort orderings).
1154 */
1155 if (rel->has_eclass_joins || has_useful_pathkeys(root, rel))
1156 add_child_rel_equivalences(root, appinfo, rel, childrel);
1157 childrel->has_eclass_joins = rel->has_eclass_joins;
1158
1159 /*
1160 * Note: we could compute appropriate attr_needed data for the child's
1161 * variables, by transforming the parent's attr_needed through the
1162 * translated_vars mapping. However, currently there's no need
1163 * because attr_needed is only examined for base relations not
1164 * otherrels. So we just leave the child's attr_needed empty.
1165 */
1166
1167 /*
1168 * If we consider partitionwise joins with the parent rel, do the same
1169 * for partitioned child rels.
1170 *
1171 * Note: here we abuse the consider_partitionwise_join flag by setting
1172 * it for child rels that are not themselves partitioned. We do so to
1173 * tell try_partitionwise_join() that the child rel is sufficiently
1174 * valid to be used as a per-partition input, even if it later gets
1175 * proven to be dummy. (It's not usable until we've set up the
1176 * reltarget and EC entries, which we just did.)
1177 */
1178 if (rel->consider_partitionwise_join)
1179 childrel->consider_partitionwise_join = true;
1180
1181 /*
1182 * If parallelism is allowable for this query in general, see whether
1183 * it's allowable for this childrel in particular. But if we've
1184 * already decided the appendrel is not parallel-safe as a whole,
1185 * there's no point in considering parallelism for this child. For
1186 * consistency, do this before calling set_rel_size() for the child.
1187 */
1188 if (root->glob->parallelModeOK && rel->consider_parallel)
1189 set_rel_consider_parallel(root, childrel, childRTE);
1190
1191 /*
1192 * Compute the child's size.
1193 */
1194 set_rel_size(root, childrel, childRTindex, childRTE);
1195
1196 /*
1197 * It is possible that constraint exclusion detected a contradiction
1198 * within a child subquery, even though we didn't prove one above. If
1199 * so, we can skip this child.
1200 */
1201 if (IS_DUMMY_REL(childrel))
1202 continue;
1203
1204 /* We have at least one live child. */
1205 has_live_children = true;
1206
1207 /*
1208 * If any live child is not parallel-safe, treat the whole appendrel
1209 * as not parallel-safe. In future we might be able to generate plans
1210 * in which some children are farmed out to workers while others are
1211 * not; but we don't have that today, so it's a waste to consider
1212 * partial paths anywhere in the appendrel unless it's all safe.
1213 * (Child rels visited before this one will be unmarked in
1214 * set_append_rel_pathlist().)
1215 */
1216 if (!childrel->consider_parallel)
1217 rel->consider_parallel = false;
1218
1219 /*
1220 * Accumulate size information from each live child.
1221 */
1222 Assert(childrel->rows > 0);
1223
1224 parent_rows += childrel->rows;
1225 parent_size += childrel->reltarget->width * childrel->rows;
1226
1227 /*
1228 * Accumulate per-column estimates too. We need not do anything for
1229 * PlaceHolderVars in the parent list. If child expression isn't a
1230 * Var, or we didn't record a width estimate for it, we have to fall
1231 * back on a datatype-based estimate.
1232 *
1233 * By construction, child's targetlist is 1-to-1 with parent's.
1234 */
1235 forboth(parentvars, rel->reltarget->exprs,
1236 childvars, childrel->reltarget->exprs)
1237 {
1238 Var *parentvar = (Var *) lfirst(parentvars);
1239 Node *childvar = (Node *) lfirst(childvars);
1240
1241 if (IsA(parentvar, Var))
1242 {
1243 int pndx = parentvar->varattno - rel->min_attr;
1244 int32 child_width = 0;
1245
1246 if (IsA(childvar, Var) &&
1247 ((Var *) childvar)->varno == childrel->relid)
1248 {
1249 int cndx = ((Var *) childvar)->varattno - childrel->min_attr;
1250
1251 child_width = childrel->attr_widths[cndx];
1252 }
1253 if (child_width <= 0)
1254 child_width = get_typavgwidth(exprType(childvar),
1255 exprTypmod(childvar));
1256 Assert(child_width > 0);
1257 parent_attrsizes[pndx] += child_width * childrel->rows;
1258 }
1259 }
1260 }
1261
1262 if (has_live_children)
1263 {
1264 /*
1265 * Save the finished size estimates.
1266 */
1267 int i;
1268
1269 Assert(parent_rows > 0);
1270 rel->rows = parent_rows;
1271 rel->reltarget->width = rint(parent_size / parent_rows);
1272 for (i = 0; i < nattrs; i++)
1273 rel->attr_widths[i] = rint(parent_attrsizes[i] / parent_rows);
1274
1275 /*
1276 * Set "raw tuples" count equal to "rows" for the appendrel; needed
1277 * because some places assume rel->tuples is valid for any baserel.
1278 */
1279 rel->tuples = parent_rows;
1280 }
1281 else
1282 {
1283 /*
1284 * All children were excluded by constraints, so mark the whole
1285 * appendrel dummy. We must do this in this phase so that the rel's
1286 * dummy-ness is visible when we generate paths for other rels.
1287 */
1288 set_dummy_rel_pathlist(rel);
1289 }
1290
1291 pfree(parent_attrsizes);
1292 }
1293
1294 /*
1295 * set_append_rel_pathlist
1296 * Build access paths for an "append relation"
1297 */
1298 static void
set_append_rel_pathlist(PlannerInfo * root,RelOptInfo * rel,Index rti,RangeTblEntry * rte)1299 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
1300 Index rti, RangeTblEntry *rte)
1301 {
1302 int parentRTindex = rti;
1303 List *live_childrels = NIL;
1304 ListCell *l;
1305
1306 /*
1307 * Generate access paths for each member relation, and remember the
1308 * non-dummy children.
1309 */
1310 foreach(l, root->append_rel_list)
1311 {
1312 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
1313 int childRTindex;
1314 RangeTblEntry *childRTE;
1315 RelOptInfo *childrel;
1316
1317 /* append_rel_list contains all append rels; ignore others */
1318 if (appinfo->parent_relid != parentRTindex)
1319 continue;
1320
1321 /* Re-locate the child RTE and RelOptInfo */
1322 childRTindex = appinfo->child_relid;
1323 childRTE = root->simple_rte_array[childRTindex];
1324 childrel = root->simple_rel_array[childRTindex];
1325
1326 /*
1327 * If set_append_rel_size() decided the parent appendrel was
1328 * parallel-unsafe at some point after visiting this child rel, we
1329 * need to propagate the unsafety marking down to the child, so that
1330 * we don't generate useless partial paths for it.
1331 */
1332 if (!rel->consider_parallel)
1333 childrel->consider_parallel = false;
1334
1335 /*
1336 * Compute the child's access paths.
1337 */
1338 set_rel_pathlist(root, childrel, childRTindex, childRTE);
1339
1340 /*
1341 * If child is dummy, ignore it.
1342 */
1343 if (IS_DUMMY_REL(childrel))
1344 continue;
1345
1346 /* Bubble up childrel's partitioned children. */
1347 if (rel->part_scheme)
1348 rel->partitioned_child_rels =
1349 list_concat(rel->partitioned_child_rels,
1350 list_copy(childrel->partitioned_child_rels));
1351
1352 /*
1353 * Child is live, so add it to the live_childrels list for use below.
1354 */
1355 live_childrels = lappend(live_childrels, childrel);
1356 }
1357
1358 /* Add paths to the append relation. */
1359 add_paths_to_append_rel(root, rel, live_childrels);
1360 }
1361
1362
1363 /*
1364 * add_paths_to_append_rel
1365 * Generate paths for the given append relation given the set of non-dummy
1366 * child rels.
1367 *
1368 * The function collects all parameterizations and orderings supported by the
1369 * non-dummy children. For every such parameterization or ordering, it creates
1370 * an append path collecting one path from each non-dummy child with given
1371 * parameterization or ordering. Similarly it collects partial paths from
1372 * non-dummy children to create partial append paths.
1373 */
1374 void
add_paths_to_append_rel(PlannerInfo * root,RelOptInfo * rel,List * live_childrels)1375 add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
1376 List *live_childrels)
1377 {
1378 List *subpaths = NIL;
1379 bool subpaths_valid = true;
1380 List *partial_subpaths = NIL;
1381 List *pa_partial_subpaths = NIL;
1382 List *pa_nonpartial_subpaths = NIL;
1383 bool partial_subpaths_valid = true;
1384 bool pa_subpaths_valid;
1385 List *all_child_pathkeys = NIL;
1386 List *all_child_outers = NIL;
1387 ListCell *l;
1388 List *partitioned_rels = NIL;
1389 double partial_rows = -1;
1390
1391 /* If appropriate, consider parallel append */
1392 pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
1393
1394 /*
1395 * AppendPath generated for partitioned tables must record the RT indexes
1396 * of partitioned tables that are direct or indirect children of this
1397 * Append rel.
1398 *
1399 * AppendPath may be for a sub-query RTE (UNION ALL), in which case, 'rel'
1400 * itself does not represent a partitioned relation, but the child sub-
1401 * queries may contain references to partitioned relations. The loop
1402 * below will look for such children and collect them in a list to be
1403 * passed to the path creation function. (This assumes that we don't need
1404 * to look through multiple levels of subquery RTEs; if we ever do, we
1405 * could consider stuffing the list we generate here into sub-query RTE's
1406 * RelOptInfo, just like we do for partitioned rels, which would be used
1407 * when populating our parent rel with paths. For the present, that
1408 * appears to be unnecessary.)
1409 */
1410 if (rel->part_scheme != NULL)
1411 {
1412 if (IS_SIMPLE_REL(rel))
1413 partitioned_rels = list_make1(rel->partitioned_child_rels);
1414 else if (IS_JOIN_REL(rel))
1415 {
1416 int relid = -1;
1417 List *partrels = NIL;
1418
1419 /*
1420 * For a partitioned joinrel, concatenate the component rels'
1421 * partitioned_child_rels lists.
1422 */
1423 while ((relid = bms_next_member(rel->relids, relid)) >= 0)
1424 {
1425 RelOptInfo *component;
1426
1427 Assert(relid >= 1 && relid < root->simple_rel_array_size);
1428 component = root->simple_rel_array[relid];
1429 Assert(component->part_scheme != NULL);
1430 Assert(list_length(component->partitioned_child_rels) >= 1);
1431 partrels =
1432 list_concat(partrels,
1433 list_copy(component->partitioned_child_rels));
1434 }
1435
1436 partitioned_rels = list_make1(partrels);
1437 }
1438
1439 Assert(list_length(partitioned_rels) >= 1);
1440 }
1441
1442 /*
1443 * For every non-dummy child, remember the cheapest path. Also, identify
1444 * all pathkeys (orderings) and parameterizations (required_outer sets)
1445 * available for the non-dummy member relations.
1446 */
1447 foreach(l, live_childrels)
1448 {
1449 RelOptInfo *childrel = lfirst(l);
1450 ListCell *lcp;
1451 Path *cheapest_partial_path = NULL;
1452
1453 /*
1454 * For UNION ALLs with non-empty partitioned_child_rels, accumulate
1455 * the Lists of child relations.
1456 */
1457 if (rel->rtekind == RTE_SUBQUERY && childrel->partitioned_child_rels != NIL)
1458 partitioned_rels = lappend(partitioned_rels,
1459 childrel->partitioned_child_rels);
1460
1461 /*
1462 * If child has an unparameterized cheapest-total path, add that to
1463 * the unparameterized Append path we are constructing for the parent.
1464 * If not, there's no workable unparameterized path.
1465 *
1466 * With partitionwise aggregates, the child rel's pathlist may be
1467 * empty, so don't assume that a path exists here.
1468 */
1469 if (childrel->pathlist != NIL &&
1470 childrel->cheapest_total_path->param_info == NULL)
1471 accumulate_append_subpath(childrel->cheapest_total_path,
1472 &subpaths, NULL);
1473 else
1474 subpaths_valid = false;
1475
1476 /* Same idea, but for a partial plan. */
1477 if (childrel->partial_pathlist != NIL)
1478 {
1479 cheapest_partial_path = linitial(childrel->partial_pathlist);
1480 accumulate_append_subpath(cheapest_partial_path,
1481 &partial_subpaths, NULL);
1482 }
1483 else
1484 partial_subpaths_valid = false;
1485
1486 /*
1487 * Same idea, but for a parallel append mixing partial and non-partial
1488 * paths.
1489 */
1490 if (pa_subpaths_valid)
1491 {
1492 Path *nppath = NULL;
1493
1494 nppath =
1495 get_cheapest_parallel_safe_total_inner(childrel->pathlist);
1496
1497 if (cheapest_partial_path == NULL && nppath == NULL)
1498 {
1499 /* Neither a partial nor a parallel-safe path? Forget it. */
1500 pa_subpaths_valid = false;
1501 }
1502 else if (nppath == NULL ||
1503 (cheapest_partial_path != NULL &&
1504 cheapest_partial_path->total_cost < nppath->total_cost))
1505 {
1506 /* Partial path is cheaper or the only option. */
1507 Assert(cheapest_partial_path != NULL);
1508 accumulate_append_subpath(cheapest_partial_path,
1509 &pa_partial_subpaths,
1510 &pa_nonpartial_subpaths);
1511
1512 }
1513 else
1514 {
1515 /*
1516 * Either we've got only a non-partial path, or we think that
1517 * a single backend can execute the best non-partial path
1518 * faster than all the parallel backends working together can
1519 * execute the best partial path.
1520 *
1521 * It might make sense to be more aggressive here. Even if
1522 * the best non-partial path is more expensive than the best
1523 * partial path, it could still be better to choose the
1524 * non-partial path if there are several such paths that can
1525 * be given to different workers. For now, we don't try to
1526 * figure that out.
1527 */
1528 accumulate_append_subpath(nppath,
1529 &pa_nonpartial_subpaths,
1530 NULL);
1531 }
1532 }
1533
1534 /*
1535 * Collect lists of all the available path orderings and
1536 * parameterizations for all the children. We use these as a
1537 * heuristic to indicate which sort orderings and parameterizations we
1538 * should build Append and MergeAppend paths for.
1539 */
1540 foreach(lcp, childrel->pathlist)
1541 {
1542 Path *childpath = (Path *) lfirst(lcp);
1543 List *childkeys = childpath->pathkeys;
1544 Relids childouter = PATH_REQ_OUTER(childpath);
1545
1546 /* Unsorted paths don't contribute to pathkey list */
1547 if (childkeys != NIL)
1548 {
1549 ListCell *lpk;
1550 bool found = false;
1551
1552 /* Have we already seen this ordering? */
1553 foreach(lpk, all_child_pathkeys)
1554 {
1555 List *existing_pathkeys = (List *) lfirst(lpk);
1556
1557 if (compare_pathkeys(existing_pathkeys,
1558 childkeys) == PATHKEYS_EQUAL)
1559 {
1560 found = true;
1561 break;
1562 }
1563 }
1564 if (!found)
1565 {
1566 /* No, so add it to all_child_pathkeys */
1567 all_child_pathkeys = lappend(all_child_pathkeys,
1568 childkeys);
1569 }
1570 }
1571
1572 /* Unparameterized paths don't contribute to param-set list */
1573 if (childouter)
1574 {
1575 ListCell *lco;
1576 bool found = false;
1577
1578 /* Have we already seen this param set? */
1579 foreach(lco, all_child_outers)
1580 {
1581 Relids existing_outers = (Relids) lfirst(lco);
1582
1583 if (bms_equal(existing_outers, childouter))
1584 {
1585 found = true;
1586 break;
1587 }
1588 }
1589 if (!found)
1590 {
1591 /* No, so add it to all_child_outers */
1592 all_child_outers = lappend(all_child_outers,
1593 childouter);
1594 }
1595 }
1596 }
1597 }
1598
1599 /*
1600 * If we found unparameterized paths for all children, build an unordered,
1601 * unparameterized Append path for the rel. (Note: this is correct even
1602 * if we have zero or one live subpath due to constraint exclusion.)
1603 */
1604 if (subpaths_valid)
1605 add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1606 NULL, 0, false,
1607 partitioned_rels, -1));
1608
1609 /*
1610 * Consider an append of unordered, unparameterized partial paths. Make
1611 * it parallel-aware if possible.
1612 */
1613 if (partial_subpaths_valid && partial_subpaths != NIL)
1614 {
1615 AppendPath *appendpath;
1616 ListCell *lc;
1617 int parallel_workers = 0;
1618
1619 /* Find the highest number of workers requested for any subpath. */
1620 foreach(lc, partial_subpaths)
1621 {
1622 Path *path = lfirst(lc);
1623
1624 parallel_workers = Max(parallel_workers, path->parallel_workers);
1625 }
1626 Assert(parallel_workers > 0);
1627
1628 /*
1629 * If the use of parallel append is permitted, always request at least
1630 * log2(# of children) workers. We assume it can be useful to have
1631 * extra workers in this case because they will be spread out across
1632 * the children. The precise formula is just a guess, but we don't
1633 * want to end up with a radically different answer for a table with N
1634 * partitions vs. an unpartitioned table with the same data, so the
1635 * use of some kind of log-scaling here seems to make some sense.
1636 */
1637 if (enable_parallel_append)
1638 {
1639 parallel_workers = Max(parallel_workers,
1640 fls(list_length(live_childrels)));
1641 parallel_workers = Min(parallel_workers,
1642 max_parallel_workers_per_gather);
1643 }
1644 Assert(parallel_workers > 0);
1645
1646 /* Generate a partial append path. */
1647 appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1648 NULL, parallel_workers,
1649 enable_parallel_append,
1650 partitioned_rels, -1);
1651
1652 /*
1653 * Make sure any subsequent partial paths use the same row count
1654 * estimate.
1655 */
1656 partial_rows = appendpath->path.rows;
1657
1658 /* Add the path. */
1659 add_partial_path(rel, (Path *) appendpath);
1660 }
1661
1662 /*
1663 * Consider a parallel-aware append using a mix of partial and non-partial
1664 * paths. (This only makes sense if there's at least one child which has
1665 * a non-partial path that is substantially cheaper than any partial path;
1666 * otherwise, we should use the append path added in the previous step.)
1667 */
1668 if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
1669 {
1670 AppendPath *appendpath;
1671 ListCell *lc;
1672 int parallel_workers = 0;
1673
1674 /*
1675 * Find the highest number of workers requested for any partial
1676 * subpath.
1677 */
1678 foreach(lc, pa_partial_subpaths)
1679 {
1680 Path *path = lfirst(lc);
1681
1682 parallel_workers = Max(parallel_workers, path->parallel_workers);
1683 }
1684
1685 /*
1686 * Same formula here as above. It's even more important in this
1687 * instance because the non-partial paths won't contribute anything to
1688 * the planned number of parallel workers.
1689 */
1690 parallel_workers = Max(parallel_workers,
1691 fls(list_length(live_childrels)));
1692 parallel_workers = Min(parallel_workers,
1693 max_parallel_workers_per_gather);
1694 Assert(parallel_workers > 0);
1695
1696 appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1697 pa_partial_subpaths,
1698 NULL, parallel_workers, true,
1699 partitioned_rels, partial_rows);
1700 add_partial_path(rel, (Path *) appendpath);
1701 }
1702
1703 /*
1704 * Also build unparameterized MergeAppend paths based on the collected
1705 * list of child pathkeys.
1706 */
1707 if (subpaths_valid)
1708 generate_mergeappend_paths(root, rel, live_childrels,
1709 all_child_pathkeys,
1710 partitioned_rels);
1711
1712 /*
1713 * Build Append paths for each parameterization seen among the child rels.
1714 * (This may look pretty expensive, but in most cases of practical
1715 * interest, the child rels will expose mostly the same parameterizations,
1716 * so that not that many cases actually get considered here.)
1717 *
1718 * The Append node itself cannot enforce quals, so all qual checking must
1719 * be done in the child paths. This means that to have a parameterized
1720 * Append path, we must have the exact same parameterization for each
1721 * child path; otherwise some children might be failing to check the
1722 * moved-down quals. To make them match up, we can try to increase the
1723 * parameterization of lesser-parameterized paths.
1724 */
1725 foreach(l, all_child_outers)
1726 {
1727 Relids required_outer = (Relids) lfirst(l);
1728 ListCell *lcr;
1729
1730 /* Select the child paths for an Append with this parameterization */
1731 subpaths = NIL;
1732 subpaths_valid = true;
1733 foreach(lcr, live_childrels)
1734 {
1735 RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1736 Path *subpath;
1737
1738 if (childrel->pathlist == NIL)
1739 {
1740 /* failed to make a suitable path for this child */
1741 subpaths_valid = false;
1742 break;
1743 }
1744
1745 subpath = get_cheapest_parameterized_child_path(root,
1746 childrel,
1747 required_outer);
1748 if (subpath == NULL)
1749 {
1750 /* failed to make a suitable path for this child */
1751 subpaths_valid = false;
1752 break;
1753 }
1754 accumulate_append_subpath(subpath, &subpaths, NULL);
1755 }
1756
1757 if (subpaths_valid)
1758 add_path(rel, (Path *)
1759 create_append_path(root, rel, subpaths, NIL,
1760 required_outer, 0, false,
1761 partitioned_rels, -1));
1762 }
1763 }
1764
1765 /*
1766 * generate_mergeappend_paths
1767 * Generate MergeAppend paths for an append relation
1768 *
1769 * Generate a path for each ordering (pathkey list) appearing in
1770 * all_child_pathkeys.
1771 *
1772 * We consider both cheapest-startup and cheapest-total cases, ie, for each
1773 * interesting ordering, collect all the cheapest startup subpaths and all the
1774 * cheapest total paths, and build a MergeAppend path for each case.
1775 *
1776 * We don't currently generate any parameterized MergeAppend paths. While
1777 * it would not take much more code here to do so, it's very unclear that it
1778 * is worth the planning cycles to investigate such paths: there's little
1779 * use for an ordered path on the inside of a nestloop. In fact, it's likely
1780 * that the current coding of add_path would reject such paths out of hand,
1781 * because add_path gives no credit for sort ordering of parameterized paths,
1782 * and a parameterized MergeAppend is going to be more expensive than the
1783 * corresponding parameterized Append path. If we ever try harder to support
1784 * parameterized mergejoin plans, it might be worth adding support for
1785 * parameterized MergeAppends to feed such joins. (See notes in
1786 * optimizer/README for why that might not ever happen, though.)
1787 */
1788 static void
generate_mergeappend_paths(PlannerInfo * root,RelOptInfo * rel,List * live_childrels,List * all_child_pathkeys,List * partitioned_rels)1789 generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
1790 List *live_childrels,
1791 List *all_child_pathkeys,
1792 List *partitioned_rels)
1793 {
1794 ListCell *lcp;
1795
1796 foreach(lcp, all_child_pathkeys)
1797 {
1798 List *pathkeys = (List *) lfirst(lcp);
1799 List *startup_subpaths = NIL;
1800 List *total_subpaths = NIL;
1801 bool startup_neq_total = false;
1802 ListCell *lcr;
1803
1804 /* Select the child paths for this ordering... */
1805 foreach(lcr, live_childrels)
1806 {
1807 RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1808 Path *cheapest_startup,
1809 *cheapest_total;
1810
1811 /* Locate the right paths, if they are available. */
1812 cheapest_startup =
1813 get_cheapest_path_for_pathkeys(childrel->pathlist,
1814 pathkeys,
1815 NULL,
1816 STARTUP_COST,
1817 false);
1818 cheapest_total =
1819 get_cheapest_path_for_pathkeys(childrel->pathlist,
1820 pathkeys,
1821 NULL,
1822 TOTAL_COST,
1823 false);
1824
1825 /*
1826 * If we can't find any paths with the right order just use the
1827 * cheapest-total path; we'll have to sort it later.
1828 */
1829 if (cheapest_startup == NULL || cheapest_total == NULL)
1830 {
1831 cheapest_startup = cheapest_total =
1832 childrel->cheapest_total_path;
1833 /* Assert we do have an unparameterized path for this child */
1834 Assert(cheapest_total->param_info == NULL);
1835 }
1836
1837 /*
1838 * Notice whether we actually have different paths for the
1839 * "cheapest" and "total" cases; frequently there will be no point
1840 * in two create_merge_append_path() calls.
1841 */
1842 if (cheapest_startup != cheapest_total)
1843 startup_neq_total = true;
1844
1845 accumulate_append_subpath(cheapest_startup,
1846 &startup_subpaths, NULL);
1847 accumulate_append_subpath(cheapest_total,
1848 &total_subpaths, NULL);
1849 }
1850
1851 /* ... and build the MergeAppend paths */
1852 add_path(rel, (Path *) create_merge_append_path(root,
1853 rel,
1854 startup_subpaths,
1855 pathkeys,
1856 NULL,
1857 partitioned_rels));
1858 if (startup_neq_total)
1859 add_path(rel, (Path *) create_merge_append_path(root,
1860 rel,
1861 total_subpaths,
1862 pathkeys,
1863 NULL,
1864 partitioned_rels));
1865 }
1866 }
1867
1868 /*
1869 * get_cheapest_parameterized_child_path
1870 * Get cheapest path for this relation that has exactly the requested
1871 * parameterization.
1872 *
1873 * Returns NULL if unable to create such a path.
1874 */
1875 static Path *
get_cheapest_parameterized_child_path(PlannerInfo * root,RelOptInfo * rel,Relids required_outer)1876 get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel,
1877 Relids required_outer)
1878 {
1879 Path *cheapest;
1880 ListCell *lc;
1881
1882 /*
1883 * Look up the cheapest existing path with no more than the needed
1884 * parameterization. If it has exactly the needed parameterization, we're
1885 * done.
1886 */
1887 cheapest = get_cheapest_path_for_pathkeys(rel->pathlist,
1888 NIL,
1889 required_outer,
1890 TOTAL_COST,
1891 false);
1892 Assert(cheapest != NULL);
1893 if (bms_equal(PATH_REQ_OUTER(cheapest), required_outer))
1894 return cheapest;
1895
1896 /*
1897 * Otherwise, we can "reparameterize" an existing path to match the given
1898 * parameterization, which effectively means pushing down additional
1899 * joinquals to be checked within the path's scan. However, some existing
1900 * paths might check the available joinquals already while others don't;
1901 * therefore, it's not clear which existing path will be cheapest after
1902 * reparameterization. We have to go through them all and find out.
1903 */
1904 cheapest = NULL;
1905 foreach(lc, rel->pathlist)
1906 {
1907 Path *path = (Path *) lfirst(lc);
1908
1909 /* Can't use it if it needs more than requested parameterization */
1910 if (!bms_is_subset(PATH_REQ_OUTER(path), required_outer))
1911 continue;
1912
1913 /*
1914 * Reparameterization can only increase the path's cost, so if it's
1915 * already more expensive than the current cheapest, forget it.
1916 */
1917 if (cheapest != NULL &&
1918 compare_path_costs(cheapest, path, TOTAL_COST) <= 0)
1919 continue;
1920
1921 /* Reparameterize if needed, then recheck cost */
1922 if (!bms_equal(PATH_REQ_OUTER(path), required_outer))
1923 {
1924 path = reparameterize_path(root, path, required_outer, 1.0);
1925 if (path == NULL)
1926 continue; /* failed to reparameterize this one */
1927 Assert(bms_equal(PATH_REQ_OUTER(path), required_outer));
1928
1929 if (cheapest != NULL &&
1930 compare_path_costs(cheapest, path, TOTAL_COST) <= 0)
1931 continue;
1932 }
1933
1934 /* We have a new best path */
1935 cheapest = path;
1936 }
1937
1938 /* Return the best path, or NULL if we found no suitable candidate */
1939 return cheapest;
1940 }
1941
1942 /*
1943 * accumulate_append_subpath
1944 * Add a subpath to the list being built for an Append or MergeAppend.
1945 *
1946 * It's possible that the child is itself an Append or MergeAppend path, in
1947 * which case we can "cut out the middleman" and just add its child paths to
1948 * our own list. (We don't try to do this earlier because we need to apply
1949 * both levels of transformation to the quals.)
1950 *
1951 * Note that if we omit a child MergeAppend in this way, we are effectively
1952 * omitting a sort step, which seems fine: if the parent is to be an Append,
1953 * its result would be unsorted anyway, while if the parent is to be a
1954 * MergeAppend, there's no point in a separate sort on a child.
1955 * its result would be unsorted anyway.
1956 *
1957 * Normally, either path is a partial path and subpaths is a list of partial
1958 * paths, or else path is a non-partial plan and subpaths is a list of those.
1959 * However, if path is a parallel-aware Append, then we add its partial path
1960 * children to subpaths and the rest to special_subpaths. If the latter is
1961 * NULL, we don't flatten the path at all (unless it contains only partial
1962 * paths).
1963 */
1964 static void
accumulate_append_subpath(Path * path,List ** subpaths,List ** special_subpaths)1965 accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
1966 {
1967 if (IsA(path, AppendPath))
1968 {
1969 AppendPath *apath = (AppendPath *) path;
1970
1971 if (!apath->path.parallel_aware || apath->first_partial_path == 0)
1972 {
1973 /* list_copy is important here to avoid sharing list substructure */
1974 *subpaths = list_concat(*subpaths, list_copy(apath->subpaths));
1975 return;
1976 }
1977 else if (special_subpaths != NULL)
1978 {
1979 List *new_special_subpaths;
1980
1981 /* Split Parallel Append into partial and non-partial subpaths */
1982 *subpaths = list_concat(*subpaths,
1983 list_copy_tail(apath->subpaths,
1984 apath->first_partial_path));
1985 new_special_subpaths =
1986 list_truncate(list_copy(apath->subpaths),
1987 apath->first_partial_path);
1988 *special_subpaths = list_concat(*special_subpaths,
1989 new_special_subpaths);
1990 return;
1991 }
1992 }
1993 else if (IsA(path, MergeAppendPath))
1994 {
1995 MergeAppendPath *mpath = (MergeAppendPath *) path;
1996
1997 /* list_copy is important here to avoid sharing list substructure */
1998 *subpaths = list_concat(*subpaths, list_copy(mpath->subpaths));
1999 return;
2000 }
2001
2002 *subpaths = lappend(*subpaths, path);
2003 }
2004
2005 /*
2006 * set_dummy_rel_pathlist
2007 * Build a dummy path for a relation that's been excluded by constraints
2008 *
2009 * Rather than inventing a special "dummy" path type, we represent this as an
2010 * AppendPath with no members (see also IS_DUMMY_APPEND/IS_DUMMY_REL macros).
2011 *
2012 * (See also mark_dummy_rel, which does basically the same thing, but is
2013 * typically used to change a rel into dummy state after we already made
2014 * paths for it.)
2015 */
2016 void
set_dummy_rel_pathlist(RelOptInfo * rel)2017 set_dummy_rel_pathlist(RelOptInfo *rel)
2018 {
2019 /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
2020 rel->rows = 0;
2021 rel->reltarget->width = 0;
2022
2023 /* Discard any pre-existing paths; no further need for them */
2024 rel->pathlist = NIL;
2025 rel->partial_pathlist = NIL;
2026
2027 /* Set up the dummy path */
2028 add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
2029 rel->lateral_relids,
2030 0, false, NIL, -1));
2031
2032 /*
2033 * We set the cheapest-path fields immediately, just in case they were
2034 * pointing at some discarded path. This is redundant when we're called
2035 * from set_rel_size(), but not when called from elsewhere, and doing it
2036 * twice is harmless anyway.
2037 */
2038 set_cheapest(rel);
2039 }
2040
2041 /* quick-and-dirty test to see if any joining is needed */
2042 static bool
has_multiple_baserels(PlannerInfo * root)2043 has_multiple_baserels(PlannerInfo *root)
2044 {
2045 int num_base_rels = 0;
2046 Index rti;
2047
2048 for (rti = 1; rti < root->simple_rel_array_size; rti++)
2049 {
2050 RelOptInfo *brel = root->simple_rel_array[rti];
2051
2052 if (brel == NULL)
2053 continue;
2054
2055 /* ignore RTEs that are "other rels" */
2056 if (brel->reloptkind == RELOPT_BASEREL)
2057 if (++num_base_rels > 1)
2058 return true;
2059 }
2060 return false;
2061 }
2062
2063 /*
2064 * set_subquery_pathlist
2065 * Generate SubqueryScan access paths for a subquery RTE
2066 *
2067 * We don't currently support generating parameterized paths for subqueries
2068 * by pushing join clauses down into them; it seems too expensive to re-plan
2069 * the subquery multiple times to consider different alternatives.
2070 * (XXX that could stand to be reconsidered, now that we use Paths.)
2071 * So the paths made here will be parameterized if the subquery contains
2072 * LATERAL references, otherwise not. As long as that's true, there's no need
2073 * for a separate set_subquery_size phase: just make the paths right away.
2074 */
2075 static void
set_subquery_pathlist(PlannerInfo * root,RelOptInfo * rel,Index rti,RangeTblEntry * rte)2076 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
2077 Index rti, RangeTblEntry *rte)
2078 {
2079 Query *parse = root->parse;
2080 Query *subquery = rte->subquery;
2081 Relids required_outer;
2082 pushdown_safety_info safetyInfo;
2083 double tuple_fraction;
2084 RelOptInfo *sub_final_rel;
2085 ListCell *lc;
2086
2087 /*
2088 * Must copy the Query so that planning doesn't mess up the RTE contents
2089 * (really really need to fix the planner to not scribble on its input,
2090 * someday ... but see remove_unused_subquery_outputs to start with).
2091 */
2092 subquery = copyObject(subquery);
2093
2094 /*
2095 * If it's a LATERAL subquery, it might contain some Vars of the current
2096 * query level, requiring it to be treated as parameterized, even though
2097 * we don't support pushing down join quals into subqueries.
2098 */
2099 required_outer = rel->lateral_relids;
2100
2101 /*
2102 * Zero out result area for subquery_is_pushdown_safe, so that it can set
2103 * flags as needed while recursing. In particular, we need a workspace
2104 * for keeping track of unsafe-to-reference columns. unsafeColumns[i]
2105 * will be set true if we find that output column i of the subquery is
2106 * unsafe to use in a pushed-down qual.
2107 */
2108 memset(&safetyInfo, 0, sizeof(safetyInfo));
2109 safetyInfo.unsafeColumns = (bool *)
2110 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
2111
2112 /*
2113 * If the subquery has the "security_barrier" flag, it means the subquery
2114 * originated from a view that must enforce row level security. Then we
2115 * must not push down quals that contain leaky functions. (Ideally this
2116 * would be checked inside subquery_is_pushdown_safe, but since we don't
2117 * currently pass the RTE to that function, we must do it here.)
2118 */
2119 safetyInfo.unsafeLeaky = rte->security_barrier;
2120
2121 /*
2122 * If there are any restriction clauses that have been attached to the
2123 * subquery relation, consider pushing them down to become WHERE or HAVING
2124 * quals of the subquery itself. This transformation is useful because it
2125 * may allow us to generate a better plan for the subquery than evaluating
2126 * all the subquery output rows and then filtering them.
2127 *
2128 * There are several cases where we cannot push down clauses. Restrictions
2129 * involving the subquery are checked by subquery_is_pushdown_safe().
2130 * Restrictions on individual clauses are checked by
2131 * qual_is_pushdown_safe(). Also, we don't want to push down
2132 * pseudoconstant clauses; better to have the gating node above the
2133 * subquery.
2134 *
2135 * Non-pushed-down clauses will get evaluated as qpquals of the
2136 * SubqueryScan node.
2137 *
2138 * XXX Are there any cases where we want to make a policy decision not to
2139 * push down a pushable qual, because it'd result in a worse plan?
2140 */
2141 if (rel->baserestrictinfo != NIL &&
2142 subquery_is_pushdown_safe(subquery, subquery, &safetyInfo))
2143 {
2144 /* OK to consider pushing down individual quals */
2145 List *upperrestrictlist = NIL;
2146 ListCell *l;
2147
2148 foreach(l, rel->baserestrictinfo)
2149 {
2150 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2151 Node *clause = (Node *) rinfo->clause;
2152
2153 if (!rinfo->pseudoconstant &&
2154 qual_is_pushdown_safe(subquery, rti, clause, &safetyInfo))
2155 {
2156 /* Push it down */
2157 subquery_push_qual(subquery, rte, rti, clause);
2158 }
2159 else
2160 {
2161 /* Keep it in the upper query */
2162 upperrestrictlist = lappend(upperrestrictlist, rinfo);
2163 }
2164 }
2165 rel->baserestrictinfo = upperrestrictlist;
2166 /* We don't bother recomputing baserestrict_min_security */
2167 }
2168
2169 pfree(safetyInfo.unsafeColumns);
2170
2171 /*
2172 * The upper query might not use all the subquery's output columns; if
2173 * not, we can simplify.
2174 */
2175 remove_unused_subquery_outputs(subquery, rel);
2176
2177 /*
2178 * We can safely pass the outer tuple_fraction down to the subquery if the
2179 * outer level has no joining, aggregation, or sorting to do. Otherwise
2180 * we'd better tell the subquery to plan for full retrieval. (XXX This
2181 * could probably be made more intelligent ...)
2182 */
2183 if (parse->hasAggs ||
2184 parse->groupClause ||
2185 parse->groupingSets ||
2186 parse->havingQual ||
2187 parse->distinctClause ||
2188 parse->sortClause ||
2189 has_multiple_baserels(root))
2190 tuple_fraction = 0.0; /* default case */
2191 else
2192 tuple_fraction = root->tuple_fraction;
2193
2194 /* plan_params should not be in use in current query level */
2195 Assert(root->plan_params == NIL);
2196
2197 /* Generate a subroot and Paths for the subquery */
2198 rel->subroot = subquery_planner(root->glob, subquery,
2199 root,
2200 false, tuple_fraction);
2201
2202 /* Isolate the params needed by this specific subplan */
2203 rel->subplan_params = root->plan_params;
2204 root->plan_params = NIL;
2205
2206 /*
2207 * It's possible that constraint exclusion proved the subquery empty. If
2208 * so, it's desirable to produce an unadorned dummy path so that we will
2209 * recognize appropriate optimizations at this query level.
2210 */
2211 sub_final_rel = fetch_upper_rel(rel->subroot, UPPERREL_FINAL, NULL);
2212
2213 if (IS_DUMMY_REL(sub_final_rel))
2214 {
2215 set_dummy_rel_pathlist(rel);
2216 return;
2217 }
2218
2219 /*
2220 * Mark rel with estimated output rows, width, etc. Note that we have to
2221 * do this before generating outer-query paths, else cost_subqueryscan is
2222 * not happy.
2223 */
2224 set_subquery_size_estimates(root, rel);
2225
2226 /*
2227 * For each Path that subquery_planner produced, make a SubqueryScanPath
2228 * in the outer query.
2229 */
2230 foreach(lc, sub_final_rel->pathlist)
2231 {
2232 Path *subpath = (Path *) lfirst(lc);
2233 List *pathkeys;
2234
2235 /* Convert subpath's pathkeys to outer representation */
2236 pathkeys = convert_subquery_pathkeys(root,
2237 rel,
2238 subpath->pathkeys,
2239 make_tlist_from_pathtarget(subpath->pathtarget));
2240
2241 /* Generate outer path using this subpath */
2242 add_path(rel, (Path *)
2243 create_subqueryscan_path(root, rel, subpath,
2244 pathkeys, required_outer));
2245 }
2246
2247 /* If outer rel allows parallelism, do same for partial paths. */
2248 if (rel->consider_parallel && bms_is_empty(required_outer))
2249 {
2250 /* If consider_parallel is false, there should be no partial paths. */
2251 Assert(sub_final_rel->consider_parallel ||
2252 sub_final_rel->partial_pathlist == NIL);
2253
2254 /* Same for partial paths. */
2255 foreach(lc, sub_final_rel->partial_pathlist)
2256 {
2257 Path *subpath = (Path *) lfirst(lc);
2258 List *pathkeys;
2259
2260 /* Convert subpath's pathkeys to outer representation */
2261 pathkeys = convert_subquery_pathkeys(root,
2262 rel,
2263 subpath->pathkeys,
2264 make_tlist_from_pathtarget(subpath->pathtarget));
2265
2266 /* Generate outer path using this subpath */
2267 add_partial_path(rel, (Path *)
2268 create_subqueryscan_path(root, rel, subpath,
2269 pathkeys,
2270 required_outer));
2271 }
2272 }
2273 }
2274
2275 /*
2276 * set_function_pathlist
2277 * Build the (single) access path for a function RTE
2278 */
2279 static void
set_function_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)2280 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
2281 {
2282 Relids required_outer;
2283 List *pathkeys = NIL;
2284
2285 /*
2286 * We don't support pushing join clauses into the quals of a function
2287 * scan, but it could still have required parameterization due to LATERAL
2288 * refs in the function expression.
2289 */
2290 required_outer = rel->lateral_relids;
2291
2292 /*
2293 * The result is considered unordered unless ORDINALITY was used, in which
2294 * case it is ordered by the ordinal column (the last one). See if we
2295 * care, by checking for uses of that Var in equivalence classes.
2296 */
2297 if (rte->funcordinality)
2298 {
2299 AttrNumber ordattno = rel->max_attr;
2300 Var *var = NULL;
2301 ListCell *lc;
2302
2303 /*
2304 * Is there a Var for it in rel's targetlist? If not, the query did
2305 * not reference the ordinality column, or at least not in any way
2306 * that would be interesting for sorting.
2307 */
2308 foreach(lc, rel->reltarget->exprs)
2309 {
2310 Var *node = (Var *) lfirst(lc);
2311
2312 /* checking varno/varlevelsup is just paranoia */
2313 if (IsA(node, Var) &&
2314 node->varattno == ordattno &&
2315 node->varno == rel->relid &&
2316 node->varlevelsup == 0)
2317 {
2318 var = node;
2319 break;
2320 }
2321 }
2322
2323 /*
2324 * Try to build pathkeys for this Var with int8 sorting. We tell
2325 * build_expression_pathkey not to build any new equivalence class; if
2326 * the Var isn't already mentioned in some EC, it means that nothing
2327 * cares about the ordering.
2328 */
2329 if (var)
2330 pathkeys = build_expression_pathkey(root,
2331 (Expr *) var,
2332 NULL, /* below outer joins */
2333 Int8LessOperator,
2334 rel->relids,
2335 false);
2336 }
2337
2338 /* Generate appropriate path */
2339 add_path(rel, create_functionscan_path(root, rel,
2340 pathkeys, required_outer));
2341 }
2342
2343 /*
2344 * set_values_pathlist
2345 * Build the (single) access path for a VALUES RTE
2346 */
2347 static void
set_values_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)2348 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
2349 {
2350 Relids required_outer;
2351
2352 /*
2353 * We don't support pushing join clauses into the quals of a values scan,
2354 * but it could still have required parameterization due to LATERAL refs
2355 * in the values expressions.
2356 */
2357 required_outer = rel->lateral_relids;
2358
2359 /* Generate appropriate path */
2360 add_path(rel, create_valuesscan_path(root, rel, required_outer));
2361 }
2362
2363 /*
2364 * set_tablefunc_pathlist
2365 * Build the (single) access path for a table func RTE
2366 */
2367 static void
set_tablefunc_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)2368 set_tablefunc_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
2369 {
2370 Relids required_outer;
2371
2372 /*
2373 * We don't support pushing join clauses into the quals of a tablefunc
2374 * scan, but it could still have required parameterization due to LATERAL
2375 * refs in the function expression.
2376 */
2377 required_outer = rel->lateral_relids;
2378
2379 /* Generate appropriate path */
2380 add_path(rel, create_tablefuncscan_path(root, rel,
2381 required_outer));
2382 }
2383
2384 /*
2385 * set_cte_pathlist
2386 * Build the (single) access path for a non-self-reference CTE RTE
2387 *
2388 * There's no need for a separate set_cte_size phase, since we don't
2389 * support join-qual-parameterized paths for CTEs.
2390 */
2391 static void
set_cte_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)2392 set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
2393 {
2394 Plan *cteplan;
2395 PlannerInfo *cteroot;
2396 Index levelsup;
2397 int ndx;
2398 ListCell *lc;
2399 int plan_id;
2400 Relids required_outer;
2401
2402 /*
2403 * Find the referenced CTE, and locate the plan previously made for it.
2404 */
2405 levelsup = rte->ctelevelsup;
2406 cteroot = root;
2407 while (levelsup-- > 0)
2408 {
2409 cteroot = cteroot->parent_root;
2410 if (!cteroot) /* shouldn't happen */
2411 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
2412 }
2413
2414 /*
2415 * Note: cte_plan_ids can be shorter than cteList, if we are still working
2416 * on planning the CTEs (ie, this is a side-reference from another CTE).
2417 * So we mustn't use forboth here.
2418 */
2419 ndx = 0;
2420 foreach(lc, cteroot->parse->cteList)
2421 {
2422 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
2423
2424 if (strcmp(cte->ctename, rte->ctename) == 0)
2425 break;
2426 ndx++;
2427 }
2428 if (lc == NULL) /* shouldn't happen */
2429 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
2430 if (ndx >= list_length(cteroot->cte_plan_ids))
2431 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
2432 plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
2433 Assert(plan_id > 0);
2434 cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
2435
2436 /* Mark rel with estimated output rows, width, etc */
2437 set_cte_size_estimates(root, rel, cteplan->plan_rows);
2438
2439 /*
2440 * We don't support pushing join clauses into the quals of a CTE scan, but
2441 * it could still have required parameterization due to LATERAL refs in
2442 * its tlist.
2443 */
2444 required_outer = rel->lateral_relids;
2445
2446 /* Generate appropriate path */
2447 add_path(rel, create_ctescan_path(root, rel, required_outer));
2448 }
2449
2450 /*
2451 * set_namedtuplestore_pathlist
2452 * Build the (single) access path for a named tuplestore RTE
2453 *
2454 * There's no need for a separate set_namedtuplestore_size phase, since we
2455 * don't support join-qual-parameterized paths for tuplestores.
2456 */
2457 static void
set_namedtuplestore_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)2458 set_namedtuplestore_pathlist(PlannerInfo *root, RelOptInfo *rel,
2459 RangeTblEntry *rte)
2460 {
2461 Relids required_outer;
2462
2463 /* Mark rel with estimated output rows, width, etc */
2464 set_namedtuplestore_size_estimates(root, rel);
2465
2466 /*
2467 * We don't support pushing join clauses into the quals of a tuplestore
2468 * scan, but it could still have required parameterization due to LATERAL
2469 * refs in its tlist.
2470 */
2471 required_outer = rel->lateral_relids;
2472
2473 /* Generate appropriate path */
2474 add_path(rel, create_namedtuplestorescan_path(root, rel, required_outer));
2475
2476 /* Select cheapest path (pretty easy in this case...) */
2477 set_cheapest(rel);
2478 }
2479
2480 /*
2481 * set_worktable_pathlist
2482 * Build the (single) access path for a self-reference CTE RTE
2483 *
2484 * There's no need for a separate set_worktable_size phase, since we don't
2485 * support join-qual-parameterized paths for CTEs.
2486 */
2487 static void
set_worktable_pathlist(PlannerInfo * root,RelOptInfo * rel,RangeTblEntry * rte)2488 set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
2489 {
2490 Path *ctepath;
2491 PlannerInfo *cteroot;
2492 Index levelsup;
2493 Relids required_outer;
2494
2495 /*
2496 * We need to find the non-recursive term's path, which is in the plan
2497 * level that's processing the recursive UNION, which is one level *below*
2498 * where the CTE comes from.
2499 */
2500 levelsup = rte->ctelevelsup;
2501 if (levelsup == 0) /* shouldn't happen */
2502 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
2503 levelsup--;
2504 cteroot = root;
2505 while (levelsup-- > 0)
2506 {
2507 cteroot = cteroot->parent_root;
2508 if (!cteroot) /* shouldn't happen */
2509 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
2510 }
2511 ctepath = cteroot->non_recursive_path;
2512 if (!ctepath) /* shouldn't happen */
2513 elog(ERROR, "could not find path for CTE \"%s\"", rte->ctename);
2514
2515 /* Mark rel with estimated output rows, width, etc */
2516 set_cte_size_estimates(root, rel, ctepath->rows);
2517
2518 /*
2519 * We don't support pushing join clauses into the quals of a worktable
2520 * scan, but it could still have required parameterization due to LATERAL
2521 * refs in its tlist. (I'm not sure this is actually possible given the
2522 * restrictions on recursive references, but it's easy enough to support.)
2523 */
2524 required_outer = rel->lateral_relids;
2525
2526 /* Generate appropriate path */
2527 add_path(rel, create_worktablescan_path(root, rel, required_outer));
2528 }
2529
2530 /*
2531 * generate_gather_paths
2532 * Generate parallel access paths for a relation by pushing a Gather or
2533 * Gather Merge on top of a partial path.
2534 *
2535 * This must not be called until after we're done creating all partial paths
2536 * for the specified relation. (Otherwise, add_partial_path might delete a
2537 * path that some GatherPath or GatherMergePath has a reference to.)
2538 *
2539 * If we're generating paths for a scan or join relation, override_rows will
2540 * be false, and we'll just use the relation's size estimate. When we're
2541 * being called for a partially-grouped path, though, we need to override
2542 * the rowcount estimate. (It's not clear that the particular value we're
2543 * using here is actually best, but the underlying rel has no estimate so
2544 * we must do something.)
2545 */
2546 void
generate_gather_paths(PlannerInfo * root,RelOptInfo * rel,bool override_rows)2547 generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
2548 {
2549 Path *cheapest_partial_path;
2550 Path *simple_gather_path;
2551 ListCell *lc;
2552 double rows;
2553 double *rowsp = NULL;
2554
2555 /* If there are no partial paths, there's nothing to do here. */
2556 if (rel->partial_pathlist == NIL)
2557 return;
2558
2559 /* Should we override the rel's rowcount estimate? */
2560 if (override_rows)
2561 rowsp = &rows;
2562
2563 /*
2564 * The output of Gather is always unsorted, so there's only one partial
2565 * path of interest: the cheapest one. That will be the one at the front
2566 * of partial_pathlist because of the way add_partial_path works.
2567 */
2568 cheapest_partial_path = linitial(rel->partial_pathlist);
2569 rows =
2570 cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
2571 simple_gather_path = (Path *)
2572 create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2573 NULL, rowsp);
2574 add_path(rel, simple_gather_path);
2575
2576 /*
2577 * For each useful ordering, we can consider an order-preserving Gather
2578 * Merge.
2579 */
2580 foreach(lc, rel->partial_pathlist)
2581 {
2582 Path *subpath = (Path *) lfirst(lc);
2583 GatherMergePath *path;
2584
2585 if (subpath->pathkeys == NIL)
2586 continue;
2587
2588 rows = subpath->rows * subpath->parallel_workers;
2589 path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2590 subpath->pathkeys, NULL, rowsp);
2591 add_path(rel, &path->path);
2592 }
2593 }
2594
2595 /*
2596 * make_rel_from_joinlist
2597 * Build access paths using a "joinlist" to guide the join path search.
2598 *
2599 * See comments for deconstruct_jointree() for definition of the joinlist
2600 * data structure.
2601 */
2602 static RelOptInfo *
make_rel_from_joinlist(PlannerInfo * root,List * joinlist)2603 make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
2604 {
2605 int levels_needed;
2606 List *initial_rels;
2607 ListCell *jl;
2608
2609 /*
2610 * Count the number of child joinlist nodes. This is the depth of the
2611 * dynamic-programming algorithm we must employ to consider all ways of
2612 * joining the child nodes.
2613 */
2614 levels_needed = list_length(joinlist);
2615
2616 if (levels_needed <= 0)
2617 return NULL; /* nothing to do? */
2618
2619 /*
2620 * Construct a list of rels corresponding to the child joinlist nodes.
2621 * This may contain both base rels and rels constructed according to
2622 * sub-joinlists.
2623 */
2624 initial_rels = NIL;
2625 foreach(jl, joinlist)
2626 {
2627 Node *jlnode = (Node *) lfirst(jl);
2628 RelOptInfo *thisrel;
2629
2630 if (IsA(jlnode, RangeTblRef))
2631 {
2632 int varno = ((RangeTblRef *) jlnode)->rtindex;
2633
2634 thisrel = find_base_rel(root, varno);
2635 }
2636 else if (IsA(jlnode, List))
2637 {
2638 /* Recurse to handle subproblem */
2639 thisrel = make_rel_from_joinlist(root, (List *) jlnode);
2640 }
2641 else
2642 {
2643 elog(ERROR, "unrecognized joinlist node type: %d",
2644 (int) nodeTag(jlnode));
2645 thisrel = NULL; /* keep compiler quiet */
2646 }
2647
2648 initial_rels = lappend(initial_rels, thisrel);
2649 }
2650
2651 if (levels_needed == 1)
2652 {
2653 /*
2654 * Single joinlist node, so we're done.
2655 */
2656 return (RelOptInfo *) linitial(initial_rels);
2657 }
2658 else
2659 {
2660 /*
2661 * Consider the different orders in which we could join the rels,
2662 * using a plugin, GEQO, or the regular join search code.
2663 *
2664 * We put the initial_rels list into a PlannerInfo field because
2665 * has_legal_joinclause() needs to look at it (ugly :-().
2666 */
2667 root->initial_rels = initial_rels;
2668
2669 if (join_search_hook)
2670 return (*join_search_hook) (root, levels_needed, initial_rels);
2671 else if (enable_geqo && levels_needed >= geqo_threshold)
2672 return geqo(root, levels_needed, initial_rels);
2673 else
2674 return standard_join_search(root, levels_needed, initial_rels);
2675 }
2676 }
2677
2678 /*
2679 * standard_join_search
2680 * Find possible joinpaths for a query by successively finding ways
2681 * to join component relations into join relations.
2682 *
2683 * 'levels_needed' is the number of iterations needed, ie, the number of
2684 * independent jointree items in the query. This is > 1.
2685 *
2686 * 'initial_rels' is a list of RelOptInfo nodes for each independent
2687 * jointree item. These are the components to be joined together.
2688 * Note that levels_needed == list_length(initial_rels).
2689 *
2690 * Returns the final level of join relations, i.e., the relation that is
2691 * the result of joining all the original relations together.
2692 * At least one implementation path must be provided for this relation and
2693 * all required sub-relations.
2694 *
2695 * To support loadable plugins that modify planner behavior by changing the
2696 * join searching algorithm, we provide a hook variable that lets a plugin
2697 * replace or supplement this function. Any such hook must return the same
2698 * final join relation as the standard code would, but it might have a
2699 * different set of implementation paths attached, and only the sub-joinrels
2700 * needed for these paths need have been instantiated.
2701 *
2702 * Note to plugin authors: the functions invoked during standard_join_search()
2703 * modify root->join_rel_list and root->join_rel_hash. If you want to do more
2704 * than one join-order search, you'll probably need to save and restore the
2705 * original states of those data structures. See geqo_eval() for an example.
2706 */
2707 RelOptInfo *
standard_join_search(PlannerInfo * root,int levels_needed,List * initial_rels)2708 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
2709 {
2710 int lev;
2711 RelOptInfo *rel;
2712
2713 /*
2714 * This function cannot be invoked recursively within any one planning
2715 * problem, so join_rel_level[] can't be in use already.
2716 */
2717 Assert(root->join_rel_level == NULL);
2718
2719 /*
2720 * We employ a simple "dynamic programming" algorithm: we first find all
2721 * ways to build joins of two jointree items, then all ways to build joins
2722 * of three items (from two-item joins and single items), then four-item
2723 * joins, and so on until we have considered all ways to join all the
2724 * items into one rel.
2725 *
2726 * root->join_rel_level[j] is a list of all the j-item rels. Initially we
2727 * set root->join_rel_level[1] to represent all the single-jointree-item
2728 * relations.
2729 */
2730 root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
2731
2732 root->join_rel_level[1] = initial_rels;
2733
2734 for (lev = 2; lev <= levels_needed; lev++)
2735 {
2736 ListCell *lc;
2737
2738 /*
2739 * Determine all possible pairs of relations to be joined at this
2740 * level, and build paths for making each one from every available
2741 * pair of lower-level relations.
2742 */
2743 join_search_one_level(root, lev);
2744
2745 /*
2746 * Run generate_partitionwise_join_paths() and generate_gather_paths()
2747 * for each just-processed joinrel. We could not do this earlier
2748 * because both regular and partial paths can get added to a
2749 * particular joinrel at multiple times within join_search_one_level.
2750 *
2751 * After that, we're done creating paths for the joinrel, so run
2752 * set_cheapest().
2753 */
2754 foreach(lc, root->join_rel_level[lev])
2755 {
2756 rel = (RelOptInfo *) lfirst(lc);
2757
2758 /* Create paths for partitionwise joins. */
2759 generate_partitionwise_join_paths(root, rel);
2760
2761 /*
2762 * Except for the topmost scan/join rel, consider gathering
2763 * partial paths. We'll do the same for the topmost scan/join rel
2764 * once we know the final targetlist (see grouping_planner).
2765 */
2766 if (lev < levels_needed)
2767 generate_gather_paths(root, rel, false);
2768
2769 /* Find and save the cheapest paths for this rel */
2770 set_cheapest(rel);
2771
2772 #ifdef OPTIMIZER_DEBUG
2773 debug_print_rel(root, rel);
2774 #endif
2775 }
2776 }
2777
2778 /*
2779 * We should have a single rel at the final level.
2780 */
2781 if (root->join_rel_level[levels_needed] == NIL)
2782 elog(ERROR, "failed to build any %d-way joins", levels_needed);
2783 Assert(list_length(root->join_rel_level[levels_needed]) == 1);
2784
2785 rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
2786
2787 root->join_rel_level = NULL;
2788
2789 return rel;
2790 }
2791
2792 /*****************************************************************************
2793 * PUSHING QUALS DOWN INTO SUBQUERIES
2794 *****************************************************************************/
2795
2796 /*
2797 * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
2798 *
2799 * subquery is the particular component query being checked. topquery
2800 * is the top component of a set-operations tree (the same Query if no
2801 * set-op is involved).
2802 *
2803 * Conditions checked here:
2804 *
2805 * 1. If the subquery has a LIMIT clause, we must not push down any quals,
2806 * since that could change the set of rows returned.
2807 *
2808 * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
2809 * quals into it, because that could change the results.
2810 *
2811 * 3. If the subquery uses DISTINCT, we cannot push volatile quals into it.
2812 * This is because upper-level quals should semantically be evaluated only
2813 * once per distinct row, not once per original row, and if the qual is
2814 * volatile then extra evaluations could change the results. (This issue
2815 * does not apply to other forms of aggregation such as GROUP BY, because
2816 * when those are present we push into HAVING not WHERE, so that the quals
2817 * are still applied after aggregation.)
2818 *
2819 * 4. If the subquery contains window functions, we cannot push volatile quals
2820 * into it. The issue here is a bit different from DISTINCT: a volatile qual
2821 * might succeed for some rows of a window partition and fail for others,
2822 * thereby changing the partition contents and thus the window functions'
2823 * results for rows that remain.
2824 *
2825 * 5. If the subquery contains any set-returning functions in its targetlist,
2826 * we cannot push volatile quals into it. That would push them below the SRFs
2827 * and thereby change the number of times they are evaluated. Also, a
2828 * volatile qual could succeed for some SRF output rows and fail for others,
2829 * a behavior that cannot occur if it's evaluated before SRF expansion.
2830 *
2831 * 6. If the subquery has nonempty grouping sets, we cannot push down any
2832 * quals. The concern here is that a qual referencing a "constant" grouping
2833 * column could get constant-folded, which would be improper because the value
2834 * is potentially nullable by grouping-set expansion. This restriction could
2835 * be removed if we had a parsetree representation that shows that such
2836 * grouping columns are not really constant. (There are other ideas that
2837 * could be used to relax this restriction, but that's the approach most
2838 * likely to get taken in the future. Note that there's not much to be gained
2839 * so long as subquery_planner can't move HAVING clauses to WHERE within such
2840 * a subquery.)
2841 *
2842 * In addition, we make several checks on the subquery's output columns to see
2843 * if it is safe to reference them in pushed-down quals. If output column k
2844 * is found to be unsafe to reference, we set safetyInfo->unsafeColumns[k]
2845 * to true, but we don't reject the subquery overall since column k might not
2846 * be referenced by some/all quals. The unsafeColumns[] array will be
2847 * consulted later by qual_is_pushdown_safe(). It's better to do it this way
2848 * than to make the checks directly in qual_is_pushdown_safe(), because when
2849 * the subquery involves set operations we have to check the output
2850 * expressions in each arm of the set op.
2851 *
2852 * Note: pushing quals into a DISTINCT subquery is theoretically dubious:
2853 * we're effectively assuming that the quals cannot distinguish values that
2854 * the DISTINCT's equality operator sees as equal, yet there are many
2855 * counterexamples to that assumption. However use of such a qual with a
2856 * DISTINCT subquery would be unsafe anyway, since there's no guarantee which
2857 * "equal" value will be chosen as the output value by the DISTINCT operation.
2858 * So we don't worry too much about that. Another objection is that if the
2859 * qual is expensive to evaluate, running it for each original row might cost
2860 * more than we save by eliminating rows before the DISTINCT step. But it
2861 * would be very hard to estimate that at this stage, and in practice pushdown
2862 * seldom seems to make things worse, so we ignore that problem too.
2863 *
2864 * Note: likewise, pushing quals into a subquery with window functions is a
2865 * bit dubious: the quals might remove some rows of a window partition while
2866 * leaving others, causing changes in the window functions' results for the
2867 * surviving rows. We insist that such a qual reference only partitioning
2868 * columns, but again that only protects us if the qual does not distinguish
2869 * values that the partitioning equality operator sees as equal. The risks
2870 * here are perhaps larger than for DISTINCT, since no de-duplication of rows
2871 * occurs and thus there is no theoretical problem with such a qual. But
2872 * we'll do this anyway because the potential performance benefits are very
2873 * large, and we've seen no field complaints about the longstanding comparable
2874 * behavior with DISTINCT.
2875 */
2876 static bool
subquery_is_pushdown_safe(Query * subquery,Query * topquery,pushdown_safety_info * safetyInfo)2877 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
2878 pushdown_safety_info *safetyInfo)
2879 {
2880 SetOperationStmt *topop;
2881
2882 /* Check point 1 */
2883 if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
2884 return false;
2885
2886 /* Check point 6 */
2887 if (subquery->groupClause && subquery->groupingSets)
2888 return false;
2889
2890 /* Check points 3, 4, and 5 */
2891 if (subquery->distinctClause ||
2892 subquery->hasWindowFuncs ||
2893 subquery->hasTargetSRFs)
2894 safetyInfo->unsafeVolatile = true;
2895
2896 /*
2897 * If we're at a leaf query, check for unsafe expressions in its target
2898 * list, and mark any unsafe ones in unsafeColumns[]. (Non-leaf nodes in
2899 * setop trees have only simple Vars in their tlists, so no need to check
2900 * them.)
2901 */
2902 if (subquery->setOperations == NULL)
2903 check_output_expressions(subquery, safetyInfo);
2904
2905 /* Are we at top level, or looking at a setop component? */
2906 if (subquery == topquery)
2907 {
2908 /* Top level, so check any component queries */
2909 if (subquery->setOperations != NULL)
2910 if (!recurse_pushdown_safe(subquery->setOperations, topquery,
2911 safetyInfo))
2912 return false;
2913 }
2914 else
2915 {
2916 /* Setop component must not have more components (too weird) */
2917 if (subquery->setOperations != NULL)
2918 return false;
2919 /* Check whether setop component output types match top level */
2920 topop = castNode(SetOperationStmt, topquery->setOperations);
2921 Assert(topop);
2922 compare_tlist_datatypes(subquery->targetList,
2923 topop->colTypes,
2924 safetyInfo);
2925 }
2926 return true;
2927 }
2928
2929 /*
2930 * Helper routine to recurse through setOperations tree
2931 */
2932 static bool
recurse_pushdown_safe(Node * setOp,Query * topquery,pushdown_safety_info * safetyInfo)2933 recurse_pushdown_safe(Node *setOp, Query *topquery,
2934 pushdown_safety_info *safetyInfo)
2935 {
2936 if (IsA(setOp, RangeTblRef))
2937 {
2938 RangeTblRef *rtr = (RangeTblRef *) setOp;
2939 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
2940 Query *subquery = rte->subquery;
2941
2942 Assert(subquery != NULL);
2943 return subquery_is_pushdown_safe(subquery, topquery, safetyInfo);
2944 }
2945 else if (IsA(setOp, SetOperationStmt))
2946 {
2947 SetOperationStmt *op = (SetOperationStmt *) setOp;
2948
2949 /* EXCEPT is no good (point 2 for subquery_is_pushdown_safe) */
2950 if (op->op == SETOP_EXCEPT)
2951 return false;
2952 /* Else recurse */
2953 if (!recurse_pushdown_safe(op->larg, topquery, safetyInfo))
2954 return false;
2955 if (!recurse_pushdown_safe(op->rarg, topquery, safetyInfo))
2956 return false;
2957 }
2958 else
2959 {
2960 elog(ERROR, "unrecognized node type: %d",
2961 (int) nodeTag(setOp));
2962 }
2963 return true;
2964 }
2965
2966 /*
2967 * check_output_expressions - check subquery's output expressions for safety
2968 *
2969 * There are several cases in which it's unsafe to push down an upper-level
2970 * qual if it references a particular output column of a subquery. We check
2971 * each output column of the subquery and set unsafeColumns[k] to true if
2972 * that column is unsafe for a pushed-down qual to reference. The conditions
2973 * checked here are:
2974 *
2975 * 1. We must not push down any quals that refer to subselect outputs that
2976 * return sets, else we'd introduce functions-returning-sets into the
2977 * subquery's WHERE/HAVING quals.
2978 *
2979 * 2. We must not push down any quals that refer to subselect outputs that
2980 * contain volatile functions, for fear of introducing strange results due
2981 * to multiple evaluation of a volatile function.
2982 *
2983 * 3. If the subquery uses DISTINCT ON, we must not push down any quals that
2984 * refer to non-DISTINCT output columns, because that could change the set
2985 * of rows returned. (This condition is vacuous for DISTINCT, because then
2986 * there are no non-DISTINCT output columns, so we needn't check. Note that
2987 * subquery_is_pushdown_safe already reported that we can't use volatile
2988 * quals if there's DISTINCT or DISTINCT ON.)
2989 *
2990 * 4. If the subquery has any window functions, we must not push down quals
2991 * that reference any output columns that are not listed in all the subquery's
2992 * window PARTITION BY clauses. We can push down quals that use only
2993 * partitioning columns because they should succeed or fail identically for
2994 * every row of any one window partition, and totally excluding some
2995 * partitions will not change a window function's results for remaining
2996 * partitions. (Again, this also requires nonvolatile quals, but
2997 * subquery_is_pushdown_safe handles that.)
2998 */
2999 static void
check_output_expressions(Query * subquery,pushdown_safety_info * safetyInfo)3000 check_output_expressions(Query *subquery, pushdown_safety_info *safetyInfo)
3001 {
3002 ListCell *lc;
3003
3004 foreach(lc, subquery->targetList)
3005 {
3006 TargetEntry *tle = (TargetEntry *) lfirst(lc);
3007
3008 if (tle->resjunk)
3009 continue; /* ignore resjunk columns */
3010
3011 /* We need not check further if output col is already known unsafe */
3012 if (safetyInfo->unsafeColumns[tle->resno])
3013 continue;
3014
3015 /* Functions returning sets are unsafe (point 1) */
3016 if (subquery->hasTargetSRFs &&
3017 expression_returns_set((Node *) tle->expr))
3018 {
3019 safetyInfo->unsafeColumns[tle->resno] = true;
3020 continue;
3021 }
3022
3023 /* Volatile functions are unsafe (point 2) */
3024 if (contain_volatile_functions((Node *) tle->expr))
3025 {
3026 safetyInfo->unsafeColumns[tle->resno] = true;
3027 continue;
3028 }
3029
3030 /* If subquery uses DISTINCT ON, check point 3 */
3031 if (subquery->hasDistinctOn &&
3032 !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
3033 {
3034 /* non-DISTINCT column, so mark it unsafe */
3035 safetyInfo->unsafeColumns[tle->resno] = true;
3036 continue;
3037 }
3038
3039 /* If subquery uses window functions, check point 4 */
3040 if (subquery->hasWindowFuncs &&
3041 !targetIsInAllPartitionLists(tle, subquery))
3042 {
3043 /* not present in all PARTITION BY clauses, so mark it unsafe */
3044 safetyInfo->unsafeColumns[tle->resno] = true;
3045 continue;
3046 }
3047 }
3048 }
3049
3050 /*
3051 * For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
3052 * push quals into each component query, but the quals can only reference
3053 * subquery columns that suffer no type coercions in the set operation.
3054 * Otherwise there are possible semantic gotchas. So, we check the
3055 * component queries to see if any of them have output types different from
3056 * the top-level setop outputs. unsafeColumns[k] is set true if column k
3057 * has different type in any component.
3058 *
3059 * We don't have to care about typmods here: the only allowed difference
3060 * between set-op input and output typmods is input is a specific typmod
3061 * and output is -1, and that does not require a coercion.
3062 *
3063 * tlist is a subquery tlist.
3064 * colTypes is an OID list of the top-level setop's output column types.
3065 * safetyInfo->unsafeColumns[] is the result array.
3066 */
3067 static void
compare_tlist_datatypes(List * tlist,List * colTypes,pushdown_safety_info * safetyInfo)3068 compare_tlist_datatypes(List *tlist, List *colTypes,
3069 pushdown_safety_info *safetyInfo)
3070 {
3071 ListCell *l;
3072 ListCell *colType = list_head(colTypes);
3073
3074 foreach(l, tlist)
3075 {
3076 TargetEntry *tle = (TargetEntry *) lfirst(l);
3077
3078 if (tle->resjunk)
3079 continue; /* ignore resjunk columns */
3080 if (colType == NULL)
3081 elog(ERROR, "wrong number of tlist entries");
3082 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
3083 safetyInfo->unsafeColumns[tle->resno] = true;
3084 colType = lnext(colType);
3085 }
3086 if (colType != NULL)
3087 elog(ERROR, "wrong number of tlist entries");
3088 }
3089
3090 /*
3091 * targetIsInAllPartitionLists
3092 * True if the TargetEntry is listed in the PARTITION BY clause
3093 * of every window defined in the query.
3094 *
3095 * It would be safe to ignore windows not actually used by any window
3096 * function, but it's not easy to get that info at this stage; and it's
3097 * unlikely to be useful to spend any extra cycles getting it, since
3098 * unreferenced window definitions are probably infrequent in practice.
3099 */
3100 static bool
targetIsInAllPartitionLists(TargetEntry * tle,Query * query)3101 targetIsInAllPartitionLists(TargetEntry *tle, Query *query)
3102 {
3103 ListCell *lc;
3104
3105 foreach(lc, query->windowClause)
3106 {
3107 WindowClause *wc = (WindowClause *) lfirst(lc);
3108
3109 if (!targetIsInSortList(tle, InvalidOid, wc->partitionClause))
3110 return false;
3111 }
3112 return true;
3113 }
3114
3115 /*
3116 * qual_is_pushdown_safe - is a particular qual safe to push down?
3117 *
3118 * qual is a restriction clause applying to the given subquery (whose RTE
3119 * has index rti in the parent query).
3120 *
3121 * Conditions checked here:
3122 *
3123 * 1. The qual must not contain any SubPlans (mainly because I'm not sure
3124 * it will work correctly: SubLinks will already have been transformed into
3125 * SubPlans in the qual, but not in the subquery). Note that SubLinks that
3126 * transform to initplans are safe, and will be accepted here because what
3127 * we'll see in the qual is just a Param referencing the initplan output.
3128 *
3129 * 2. If unsafeVolatile is set, the qual must not contain any volatile
3130 * functions.
3131 *
3132 * 3. If unsafeLeaky is set, the qual must not contain any leaky functions
3133 * that are passed Var nodes, and therefore might reveal values from the
3134 * subquery as side effects.
3135 *
3136 * 4. The qual must not refer to the whole-row output of the subquery
3137 * (since there is no easy way to name that within the subquery itself).
3138 *
3139 * 5. The qual must not refer to any subquery output columns that were
3140 * found to be unsafe to reference by subquery_is_pushdown_safe().
3141 */
3142 static bool
qual_is_pushdown_safe(Query * subquery,Index rti,Node * qual,pushdown_safety_info * safetyInfo)3143 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
3144 pushdown_safety_info *safetyInfo)
3145 {
3146 bool safe = true;
3147 List *vars;
3148 ListCell *vl;
3149
3150 /* Refuse subselects (point 1) */
3151 if (contain_subplans(qual))
3152 return false;
3153
3154 /* Refuse volatile quals if we found they'd be unsafe (point 2) */
3155 if (safetyInfo->unsafeVolatile &&
3156 contain_volatile_functions(qual))
3157 return false;
3158
3159 /* Refuse leaky quals if told to (point 3) */
3160 if (safetyInfo->unsafeLeaky &&
3161 contain_leaked_vars(qual))
3162 return false;
3163
3164 /*
3165 * It would be unsafe to push down window function calls, but at least for
3166 * the moment we could never see any in a qual anyhow. (The same applies
3167 * to aggregates, which we check for in pull_var_clause below.)
3168 */
3169 Assert(!contain_window_function(qual));
3170
3171 /*
3172 * Examine all Vars used in clause. Since it's a restriction clause, all
3173 * such Vars must refer to subselect output columns ... unless this is
3174 * part of a LATERAL subquery, in which case there could be lateral
3175 * references.
3176 */
3177 vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS);
3178 foreach(vl, vars)
3179 {
3180 Var *var = (Var *) lfirst(vl);
3181
3182 /*
3183 * XXX Punt if we find any PlaceHolderVars in the restriction clause.
3184 * It's not clear whether a PHV could safely be pushed down, and even
3185 * less clear whether such a situation could arise in any cases of
3186 * practical interest anyway. So for the moment, just refuse to push
3187 * down.
3188 */
3189 if (!IsA(var, Var))
3190 {
3191 safe = false;
3192 break;
3193 }
3194
3195 /*
3196 * Punt if we find any lateral references. It would be safe to push
3197 * these down, but we'd have to convert them into outer references,
3198 * which subquery_push_qual lacks the infrastructure to do. The case
3199 * arises so seldom that it doesn't seem worth working hard on.
3200 */
3201 if (var->varno != rti)
3202 {
3203 safe = false;
3204 break;
3205 }
3206
3207 /* Subqueries have no system columns */
3208 Assert(var->varattno >= 0);
3209
3210 /* Check point 4 */
3211 if (var->varattno == 0)
3212 {
3213 safe = false;
3214 break;
3215 }
3216
3217 /* Check point 5 */
3218 if (safetyInfo->unsafeColumns[var->varattno])
3219 {
3220 safe = false;
3221 break;
3222 }
3223 }
3224
3225 list_free(vars);
3226
3227 return safe;
3228 }
3229
3230 /*
3231 * subquery_push_qual - push down a qual that we have determined is safe
3232 */
3233 static void
subquery_push_qual(Query * subquery,RangeTblEntry * rte,Index rti,Node * qual)3234 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
3235 {
3236 if (subquery->setOperations != NULL)
3237 {
3238 /* Recurse to push it separately to each component query */
3239 recurse_push_qual(subquery->setOperations, subquery,
3240 rte, rti, qual);
3241 }
3242 else
3243 {
3244 /*
3245 * We need to replace Vars in the qual (which must refer to outputs of
3246 * the subquery) with copies of the subquery's targetlist expressions.
3247 * Note that at this point, any uplevel Vars in the qual should have
3248 * been replaced with Params, so they need no work.
3249 *
3250 * This step also ensures that when we are pushing into a setop tree,
3251 * each component query gets its own copy of the qual.
3252 */
3253 qual = ReplaceVarsFromTargetList(qual, rti, 0, rte,
3254 subquery->targetList,
3255 REPLACEVARS_REPORT_ERROR, 0,
3256 &subquery->hasSubLinks);
3257
3258 /*
3259 * Now attach the qual to the proper place: normally WHERE, but if the
3260 * subquery uses grouping or aggregation, put it in HAVING (since the
3261 * qual really refers to the group-result rows).
3262 */
3263 if (subquery->hasAggs || subquery->groupClause || subquery->groupingSets || subquery->havingQual)
3264 subquery->havingQual = make_and_qual(subquery->havingQual, qual);
3265 else
3266 subquery->jointree->quals =
3267 make_and_qual(subquery->jointree->quals, qual);
3268
3269 /*
3270 * We need not change the subquery's hasAggs or hasSubLinks flags,
3271 * since we can't be pushing down any aggregates that weren't there
3272 * before, and we don't push down subselects at all.
3273 */
3274 }
3275 }
3276
3277 /*
3278 * Helper routine to recurse through setOperations tree
3279 */
3280 static void
recurse_push_qual(Node * setOp,Query * topquery,RangeTblEntry * rte,Index rti,Node * qual)3281 recurse_push_qual(Node *setOp, Query *topquery,
3282 RangeTblEntry *rte, Index rti, Node *qual)
3283 {
3284 if (IsA(setOp, RangeTblRef))
3285 {
3286 RangeTblRef *rtr = (RangeTblRef *) setOp;
3287 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
3288 Query *subquery = subrte->subquery;
3289
3290 Assert(subquery != NULL);
3291 subquery_push_qual(subquery, rte, rti, qual);
3292 }
3293 else if (IsA(setOp, SetOperationStmt))
3294 {
3295 SetOperationStmt *op = (SetOperationStmt *) setOp;
3296
3297 recurse_push_qual(op->larg, topquery, rte, rti, qual);
3298 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
3299 }
3300 else
3301 {
3302 elog(ERROR, "unrecognized node type: %d",
3303 (int) nodeTag(setOp));
3304 }
3305 }
3306
3307 /*****************************************************************************
3308 * SIMPLIFYING SUBQUERY TARGETLISTS
3309 *****************************************************************************/
3310
3311 /*
3312 * remove_unused_subquery_outputs
3313 * Remove subquery targetlist items we don't need
3314 *
3315 * It's possible, even likely, that the upper query does not read all the
3316 * output columns of the subquery. We can remove any such outputs that are
3317 * not needed by the subquery itself (e.g., as sort/group columns) and do not
3318 * affect semantics otherwise (e.g., volatile functions can't be removed).
3319 * This is useful not only because we might be able to remove expensive-to-
3320 * compute expressions, but because deletion of output columns might allow
3321 * optimizations such as join removal to occur within the subquery.
3322 *
3323 * To avoid affecting column numbering in the targetlist, we don't physically
3324 * remove unused tlist entries, but rather replace their expressions with NULL
3325 * constants. This is implemented by modifying subquery->targetList.
3326 */
3327 static void
remove_unused_subquery_outputs(Query * subquery,RelOptInfo * rel)3328 remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel)
3329 {
3330 Bitmapset *attrs_used = NULL;
3331 ListCell *lc;
3332
3333 /*
3334 * Do nothing if subquery has UNION/INTERSECT/EXCEPT: in principle we
3335 * could update all the child SELECTs' tlists, but it seems not worth the
3336 * trouble presently.
3337 */
3338 if (subquery->setOperations)
3339 return;
3340
3341 /*
3342 * If subquery has regular DISTINCT (not DISTINCT ON), we're wasting our
3343 * time: all its output columns must be used in the distinctClause.
3344 */
3345 if (subquery->distinctClause && !subquery->hasDistinctOn)
3346 return;
3347
3348 /*
3349 * Collect a bitmap of all the output column numbers used by the upper
3350 * query.
3351 *
3352 * Add all the attributes needed for joins or final output. Note: we must
3353 * look at rel's targetlist, not the attr_needed data, because attr_needed
3354 * isn't computed for inheritance child rels, cf set_append_rel_size().
3355 * (XXX might be worth changing that sometime.)
3356 */
3357 pull_varattnos((Node *) rel->reltarget->exprs, rel->relid, &attrs_used);
3358
3359 /* Add all the attributes used by un-pushed-down restriction clauses. */
3360 foreach(lc, rel->baserestrictinfo)
3361 {
3362 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3363
3364 pull_varattnos((Node *) rinfo->clause, rel->relid, &attrs_used);
3365 }
3366
3367 /*
3368 * If there's a whole-row reference to the subquery, we can't remove
3369 * anything.
3370 */
3371 if (bms_is_member(0 - FirstLowInvalidHeapAttributeNumber, attrs_used))
3372 return;
3373
3374 /*
3375 * Run through the tlist and zap entries we don't need. It's okay to
3376 * modify the tlist items in-place because set_subquery_pathlist made a
3377 * copy of the subquery.
3378 */
3379 foreach(lc, subquery->targetList)
3380 {
3381 TargetEntry *tle = (TargetEntry *) lfirst(lc);
3382 Node *texpr = (Node *) tle->expr;
3383
3384 /*
3385 * If it has a sortgroupref number, it's used in some sort/group
3386 * clause so we'd better not remove it. Also, don't remove any
3387 * resjunk columns, since their reason for being has nothing to do
3388 * with anybody reading the subquery's output. (It's likely that
3389 * resjunk columns in a sub-SELECT would always have ressortgroupref
3390 * set, but even if they don't, it seems imprudent to remove them.)
3391 */
3392 if (tle->ressortgroupref || tle->resjunk)
3393 continue;
3394
3395 /*
3396 * If it's used by the upper query, we can't remove it.
3397 */
3398 if (bms_is_member(tle->resno - FirstLowInvalidHeapAttributeNumber,
3399 attrs_used))
3400 continue;
3401
3402 /*
3403 * If it contains a set-returning function, we can't remove it since
3404 * that could change the number of rows returned by the subquery.
3405 */
3406 if (subquery->hasTargetSRFs &&
3407 expression_returns_set(texpr))
3408 continue;
3409
3410 /*
3411 * If it contains volatile functions, we daren't remove it for fear
3412 * that the user is expecting their side-effects to happen.
3413 */
3414 if (contain_volatile_functions(texpr))
3415 continue;
3416
3417 /*
3418 * OK, we don't need it. Replace the expression with a NULL constant.
3419 * Preserve the exposed type of the expression, in case something
3420 * looks at the rowtype of the subquery's result.
3421 */
3422 tle->expr = (Expr *) makeNullConst(exprType(texpr),
3423 exprTypmod(texpr),
3424 exprCollation(texpr));
3425 }
3426 }
3427
3428 /*
3429 * create_partial_bitmap_paths
3430 * Build partial bitmap heap path for the relation
3431 */
3432 void
create_partial_bitmap_paths(PlannerInfo * root,RelOptInfo * rel,Path * bitmapqual)3433 create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
3434 Path *bitmapqual)
3435 {
3436 int parallel_workers;
3437 double pages_fetched;
3438
3439 /* Compute heap pages for bitmap heap scan */
3440 pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
3441 NULL, NULL);
3442
3443 parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
3444 max_parallel_workers_per_gather);
3445
3446 if (parallel_workers <= 0)
3447 return;
3448
3449 add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
3450 bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
3451 }
3452
3453 /*
3454 * Compute the number of parallel workers that should be used to scan a
3455 * relation. We compute the parallel workers based on the size of the heap to
3456 * be scanned and the size of the index to be scanned, then choose a minimum
3457 * of those.
3458 *
3459 * "heap_pages" is the number of pages from the table that we expect to scan, or
3460 * -1 if we don't expect to scan any.
3461 *
3462 * "index_pages" is the number of pages from the index that we expect to scan, or
3463 * -1 if we don't expect to scan any.
3464 *
3465 * "max_workers" is caller's limit on the number of workers. This typically
3466 * comes from a GUC.
3467 */
3468 int
compute_parallel_worker(RelOptInfo * rel,double heap_pages,double index_pages,int max_workers)3469 compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages,
3470 int max_workers)
3471 {
3472 int parallel_workers = 0;
3473
3474 /*
3475 * If the user has set the parallel_workers reloption, use that; otherwise
3476 * select a default number of workers.
3477 */
3478 if (rel->rel_parallel_workers != -1)
3479 parallel_workers = rel->rel_parallel_workers;
3480 else
3481 {
3482 /*
3483 * If the number of pages being scanned is insufficient to justify a
3484 * parallel scan, just return zero ... unless it's an inheritance
3485 * child. In that case, we want to generate a parallel path here
3486 * anyway. It might not be worthwhile just for this relation, but
3487 * when combined with all of its inheritance siblings it may well pay
3488 * off.
3489 */
3490 if (rel->reloptkind == RELOPT_BASEREL &&
3491 ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
3492 (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
3493 return 0;
3494
3495 if (heap_pages >= 0)
3496 {
3497 int heap_parallel_threshold;
3498 int heap_parallel_workers = 1;
3499
3500 /*
3501 * Select the number of workers based on the log of the size of
3502 * the relation. This probably needs to be a good deal more
3503 * sophisticated, but we need something here for now. Note that
3504 * the upper limit of the min_parallel_table_scan_size GUC is
3505 * chosen to prevent overflow here.
3506 */
3507 heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
3508 while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
3509 {
3510 heap_parallel_workers++;
3511 heap_parallel_threshold *= 3;
3512 if (heap_parallel_threshold > INT_MAX / 3)
3513 break; /* avoid overflow */
3514 }
3515
3516 parallel_workers = heap_parallel_workers;
3517 }
3518
3519 if (index_pages >= 0)
3520 {
3521 int index_parallel_workers = 1;
3522 int index_parallel_threshold;
3523
3524 /* same calculation as for heap_pages above */
3525 index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
3526 while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
3527 {
3528 index_parallel_workers++;
3529 index_parallel_threshold *= 3;
3530 if (index_parallel_threshold > INT_MAX / 3)
3531 break; /* avoid overflow */
3532 }
3533
3534 if (parallel_workers > 0)
3535 parallel_workers = Min(parallel_workers, index_parallel_workers);
3536 else
3537 parallel_workers = index_parallel_workers;
3538 }
3539 }
3540
3541 /* In no case use more than caller supplied maximum number of workers */
3542 parallel_workers = Min(parallel_workers, max_workers);
3543
3544 return parallel_workers;
3545 }
3546
3547 /*
3548 * generate_partitionwise_join_paths
3549 * Create paths representing partitionwise join for given partitioned
3550 * join relation.
3551 *
3552 * This must not be called until after we are done adding paths for all
3553 * child-joins. Otherwise, add_path might delete a path to which some path
3554 * generated here has a reference.
3555 */
3556 void
generate_partitionwise_join_paths(PlannerInfo * root,RelOptInfo * rel)3557 generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
3558 {
3559 List *live_children = NIL;
3560 int cnt_parts;
3561 int num_parts;
3562 RelOptInfo **part_rels;
3563
3564 /* Handle only join relations here. */
3565 if (!IS_JOIN_REL(rel))
3566 return;
3567
3568 /* We've nothing to do if the relation is not partitioned. */
3569 if (!IS_PARTITIONED_REL(rel))
3570 return;
3571
3572 /* The relation should have consider_partitionwise_join set. */
3573 Assert(rel->consider_partitionwise_join);
3574
3575 /* Guard against stack overflow due to overly deep partition hierarchy. */
3576 check_stack_depth();
3577
3578 num_parts = rel->nparts;
3579 part_rels = rel->part_rels;
3580
3581 /* Collect non-dummy child-joins. */
3582 for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
3583 {
3584 RelOptInfo *child_rel = part_rels[cnt_parts];
3585
3586 /* If it's been pruned entirely, it's certainly dummy. */
3587 if (child_rel == NULL)
3588 continue;
3589
3590 /* Add partitionwise join paths for partitioned child-joins. */
3591 generate_partitionwise_join_paths(root, child_rel);
3592
3593 set_cheapest(child_rel);
3594
3595 /* Dummy children will not be scanned, so ignore those. */
3596 if (IS_DUMMY_REL(child_rel))
3597 continue;
3598
3599 #ifdef OPTIMIZER_DEBUG
3600 debug_print_rel(root, child_rel);
3601 #endif
3602
3603 live_children = lappend(live_children, child_rel);
3604 }
3605
3606 /* If all child-joins are dummy, parent join is also dummy. */
3607 if (!live_children)
3608 {
3609 mark_dummy_rel(rel);
3610 return;
3611 }
3612
3613 /* Build additional paths for this rel from child-join paths. */
3614 add_paths_to_append_rel(root, rel, live_children);
3615 list_free(live_children);
3616 }
3617
3618
3619 /*****************************************************************************
3620 * DEBUG SUPPORT
3621 *****************************************************************************/
3622
3623 #ifdef OPTIMIZER_DEBUG
3624
3625 static void
print_relids(PlannerInfo * root,Relids relids)3626 print_relids(PlannerInfo *root, Relids relids)
3627 {
3628 int x;
3629 bool first = true;
3630
3631 x = -1;
3632 while ((x = bms_next_member(relids, x)) >= 0)
3633 {
3634 if (!first)
3635 printf(" ");
3636 if (x < root->simple_rel_array_size &&
3637 root->simple_rte_array[x])
3638 printf("%s", root->simple_rte_array[x]->eref->aliasname);
3639 else
3640 printf("%d", x);
3641 first = false;
3642 }
3643 }
3644
3645 static void
print_restrictclauses(PlannerInfo * root,List * clauses)3646 print_restrictclauses(PlannerInfo *root, List *clauses)
3647 {
3648 ListCell *l;
3649
3650 foreach(l, clauses)
3651 {
3652 RestrictInfo *c = lfirst(l);
3653
3654 print_expr((Node *) c->clause, root->parse->rtable);
3655 if (lnext(l))
3656 printf(", ");
3657 }
3658 }
3659
3660 static void
print_path(PlannerInfo * root,Path * path,int indent)3661 print_path(PlannerInfo *root, Path *path, int indent)
3662 {
3663 const char *ptype;
3664 bool join = false;
3665 Path *subpath = NULL;
3666 int i;
3667
3668 switch (nodeTag(path))
3669 {
3670 case T_Path:
3671 switch (path->pathtype)
3672 {
3673 case T_SeqScan:
3674 ptype = "SeqScan";
3675 break;
3676 case T_SampleScan:
3677 ptype = "SampleScan";
3678 break;
3679 case T_SubqueryScan:
3680 ptype = "SubqueryScan";
3681 break;
3682 case T_FunctionScan:
3683 ptype = "FunctionScan";
3684 break;
3685 case T_TableFuncScan:
3686 ptype = "TableFuncScan";
3687 break;
3688 case T_ValuesScan:
3689 ptype = "ValuesScan";
3690 break;
3691 case T_CteScan:
3692 ptype = "CteScan";
3693 break;
3694 case T_WorkTableScan:
3695 ptype = "WorkTableScan";
3696 break;
3697 default:
3698 ptype = "???Path";
3699 break;
3700 }
3701 break;
3702 case T_IndexPath:
3703 ptype = "IdxScan";
3704 break;
3705 case T_BitmapHeapPath:
3706 ptype = "BitmapHeapScan";
3707 break;
3708 case T_BitmapAndPath:
3709 ptype = "BitmapAndPath";
3710 break;
3711 case T_BitmapOrPath:
3712 ptype = "BitmapOrPath";
3713 break;
3714 case T_TidPath:
3715 ptype = "TidScan";
3716 break;
3717 case T_SubqueryScanPath:
3718 ptype = "SubqueryScanScan";
3719 break;
3720 case T_ForeignPath:
3721 ptype = "ForeignScan";
3722 break;
3723 case T_CustomPath:
3724 ptype = "CustomScan";
3725 break;
3726 case T_NestPath:
3727 ptype = "NestLoop";
3728 join = true;
3729 break;
3730 case T_MergePath:
3731 ptype = "MergeJoin";
3732 join = true;
3733 break;
3734 case T_HashPath:
3735 ptype = "HashJoin";
3736 join = true;
3737 break;
3738 case T_AppendPath:
3739 ptype = "Append";
3740 break;
3741 case T_MergeAppendPath:
3742 ptype = "MergeAppend";
3743 break;
3744 case T_ResultPath:
3745 ptype = "Result";
3746 break;
3747 case T_MaterialPath:
3748 ptype = "Material";
3749 subpath = ((MaterialPath *) path)->subpath;
3750 break;
3751 case T_UniquePath:
3752 ptype = "Unique";
3753 subpath = ((UniquePath *) path)->subpath;
3754 break;
3755 case T_GatherPath:
3756 ptype = "Gather";
3757 subpath = ((GatherPath *) path)->subpath;
3758 break;
3759 case T_GatherMergePath:
3760 ptype = "GatherMerge";
3761 subpath = ((GatherMergePath *) path)->subpath;
3762 break;
3763 case T_ProjectionPath:
3764 ptype = "Projection";
3765 subpath = ((ProjectionPath *) path)->subpath;
3766 break;
3767 case T_ProjectSetPath:
3768 ptype = "ProjectSet";
3769 subpath = ((ProjectSetPath *) path)->subpath;
3770 break;
3771 case T_SortPath:
3772 ptype = "Sort";
3773 subpath = ((SortPath *) path)->subpath;
3774 break;
3775 case T_GroupPath:
3776 ptype = "Group";
3777 subpath = ((GroupPath *) path)->subpath;
3778 break;
3779 case T_UpperUniquePath:
3780 ptype = "UpperUnique";
3781 subpath = ((UpperUniquePath *) path)->subpath;
3782 break;
3783 case T_AggPath:
3784 ptype = "Agg";
3785 subpath = ((AggPath *) path)->subpath;
3786 break;
3787 case T_GroupingSetsPath:
3788 ptype = "GroupingSets";
3789 subpath = ((GroupingSetsPath *) path)->subpath;
3790 break;
3791 case T_MinMaxAggPath:
3792 ptype = "MinMaxAgg";
3793 break;
3794 case T_WindowAggPath:
3795 ptype = "WindowAgg";
3796 subpath = ((WindowAggPath *) path)->subpath;
3797 break;
3798 case T_SetOpPath:
3799 ptype = "SetOp";
3800 subpath = ((SetOpPath *) path)->subpath;
3801 break;
3802 case T_RecursiveUnionPath:
3803 ptype = "RecursiveUnion";
3804 break;
3805 case T_LockRowsPath:
3806 ptype = "LockRows";
3807 subpath = ((LockRowsPath *) path)->subpath;
3808 break;
3809 case T_ModifyTablePath:
3810 ptype = "ModifyTable";
3811 break;
3812 case T_LimitPath:
3813 ptype = "Limit";
3814 subpath = ((LimitPath *) path)->subpath;
3815 break;
3816 default:
3817 ptype = "???Path";
3818 break;
3819 }
3820
3821 for (i = 0; i < indent; i++)
3822 printf("\t");
3823 printf("%s", ptype);
3824
3825 if (path->parent)
3826 {
3827 printf("(");
3828 print_relids(root, path->parent->relids);
3829 printf(")");
3830 }
3831 if (path->param_info)
3832 {
3833 printf(" required_outer (");
3834 print_relids(root, path->param_info->ppi_req_outer);
3835 printf(")");
3836 }
3837 printf(" rows=%.0f cost=%.2f..%.2f\n",
3838 path->rows, path->startup_cost, path->total_cost);
3839
3840 if (path->pathkeys)
3841 {
3842 for (i = 0; i < indent; i++)
3843 printf("\t");
3844 printf(" pathkeys: ");
3845 print_pathkeys(path->pathkeys, root->parse->rtable);
3846 }
3847
3848 if (join)
3849 {
3850 JoinPath *jp = (JoinPath *) path;
3851
3852 for (i = 0; i < indent; i++)
3853 printf("\t");
3854 printf(" clauses: ");
3855 print_restrictclauses(root, jp->joinrestrictinfo);
3856 printf("\n");
3857
3858 if (IsA(path, MergePath))
3859 {
3860 MergePath *mp = (MergePath *) path;
3861
3862 for (i = 0; i < indent; i++)
3863 printf("\t");
3864 printf(" sortouter=%d sortinner=%d materializeinner=%d\n",
3865 ((mp->outersortkeys) ? 1 : 0),
3866 ((mp->innersortkeys) ? 1 : 0),
3867 ((mp->materialize_inner) ? 1 : 0));
3868 }
3869
3870 print_path(root, jp->outerjoinpath, indent + 1);
3871 print_path(root, jp->innerjoinpath, indent + 1);
3872 }
3873
3874 if (subpath)
3875 print_path(root, subpath, indent + 1);
3876 }
3877
3878 void
debug_print_rel(PlannerInfo * root,RelOptInfo * rel)3879 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
3880 {
3881 ListCell *l;
3882
3883 printf("RELOPTINFO (");
3884 print_relids(root, rel->relids);
3885 printf("): rows=%.0f width=%d\n", rel->rows, rel->reltarget->width);
3886
3887 if (rel->baserestrictinfo)
3888 {
3889 printf("\tbaserestrictinfo: ");
3890 print_restrictclauses(root, rel->baserestrictinfo);
3891 printf("\n");
3892 }
3893
3894 if (rel->joininfo)
3895 {
3896 printf("\tjoininfo: ");
3897 print_restrictclauses(root, rel->joininfo);
3898 printf("\n");
3899 }
3900
3901 printf("\tpath list:\n");
3902 foreach(l, rel->pathlist)
3903 print_path(root, lfirst(l), 1);
3904 if (rel->cheapest_parameterized_paths)
3905 {
3906 printf("\n\tcheapest parameterized paths:\n");
3907 foreach(l, rel->cheapest_parameterized_paths)
3908 print_path(root, lfirst(l), 1);
3909 }
3910 if (rel->cheapest_startup_path)
3911 {
3912 printf("\n\tcheapest startup path:\n");
3913 print_path(root, rel->cheapest_startup_path, 1);
3914 }
3915 if (rel->cheapest_total_path)
3916 {
3917 printf("\n\tcheapest total path:\n");
3918 print_path(root, rel->cheapest_total_path, 1);
3919 }
3920 printf("\n");
3921 fflush(stdout);
3922 }
3923
3924 #endif /* OPTIMIZER_DEBUG */
3925