allpaths.c source code [PostgreSQL/src/backend/optimizer/path/allpaths.c]

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

Browse the source code of PostgreSQL/src/backend/optimizer/path/allpaths.c