Debian Codegraph @

src/backend/optimizer/path/allpaths.c

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