Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pathnode.c
4 : * Routines to manipulate pathlists and create path nodes
5 : *
6 : * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
7 : * Portions Copyright (c) 1994, Regents of the University of California
8 : *
9 : *
10 : * IDENTIFICATION
11 : * src/backend/optimizer/util/pathnode.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 : #include "postgres.h"
16 :
17 : #include <math.h>
18 :
19 : #include "foreign/fdwapi.h"
20 : #include "miscadmin.h"
21 : #include "nodes/extensible.h"
22 : #include "nodes/nodeFuncs.h"
23 : #include "optimizer/appendinfo.h"
24 : #include "optimizer/clauses.h"
25 : #include "optimizer/cost.h"
26 : #include "optimizer/optimizer.h"
27 : #include "optimizer/pathnode.h"
28 : #include "optimizer/paths.h"
29 : #include "optimizer/planmain.h"
30 : #include "optimizer/prep.h"
31 : #include "optimizer/restrictinfo.h"
32 : #include "optimizer/tlist.h"
33 : #include "parser/parsetree.h"
34 : #include "utils/lsyscache.h"
35 : #include "utils/memutils.h"
36 : #include "utils/selfuncs.h"
37 :
38 : typedef enum
39 : {
40 : COSTS_EQUAL, /* path costs are fuzzily equal */
41 : COSTS_BETTER1, /* first path is cheaper than second */
42 : COSTS_BETTER2, /* second path is cheaper than first */
43 : COSTS_DIFFERENT /* neither path dominates the other on cost */
44 : } PathCostComparison;
45 :
46 : /*
47 : * STD_FUZZ_FACTOR is the normal fuzz factor for compare_path_costs_fuzzily.
48 : * XXX is it worth making this user-controllable? It provides a tradeoff
49 : * between planner runtime and the accuracy of path cost comparisons.
50 : */
51 : #define STD_FUZZ_FACTOR 1.01
52 :
53 : static List *translate_sub_tlist(List *tlist, int relid);
54 : static int append_total_cost_compare(const ListCell *a, const ListCell *b);
55 : static int append_startup_cost_compare(const ListCell *a, const ListCell *b);
56 : static List *reparameterize_pathlist_by_child(PlannerInfo *root,
57 : List *pathlist,
58 : RelOptInfo *child_rel);
59 :
60 :
61 : /*****************************************************************************
62 : * MISC. PATH UTILITIES
63 : *****************************************************************************/
64 :
65 : /*
66 : * compare_path_costs
67 : * Return -1, 0, or +1 according as path1 is cheaper, the same cost,
68 : * or more expensive than path2 for the specified criterion.
69 : */
70 : int
71 443080 : compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
72 : {
73 443080 : if (criterion == STARTUP_COST)
74 : {
75 225886 : if (path1->startup_cost < path2->startup_cost)
76 113922 : return -1;
77 111964 : if (path1->startup_cost > path2->startup_cost)
78 49988 : return +1;
79 :
80 : /*
81 : * If paths have the same startup cost (not at all unlikely), order
82 : * them by total cost.
83 : */
84 61976 : if (path1->total_cost < path2->total_cost)
85 39986 : return -1;
86 21990 : if (path1->total_cost > path2->total_cost)
87 2580 : return +1;
88 : }
89 : else
90 : {
91 217194 : if (path1->total_cost < path2->total_cost)
92 207656 : return -1;
93 9538 : if (path1->total_cost > path2->total_cost)
94 2132 : return +1;
95 :
96 : /*
97 : * If paths have the same total cost, order them by startup cost.
98 : */
99 7406 : if (path1->startup_cost < path2->startup_cost)
100 8 : return -1;
101 7398 : if (path1->startup_cost > path2->startup_cost)
102 0 : return +1;
103 : }
104 26808 : return 0;
105 : }
106 :
107 : /*
108 : * compare_path_fractional_costs
109 : * Return -1, 0, or +1 according as path1 is cheaper, the same cost,
110 : * or more expensive than path2 for fetching the specified fraction
111 : * of the total tuples.
112 : *
113 : * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
114 : * path with the cheaper total_cost.
115 : */
116 : int
117 2436 : compare_fractional_path_costs(Path *path1, Path *path2,
118 : double fraction)
119 : {
120 : Cost cost1,
121 : cost2;
122 :
123 2436 : if (fraction <= 0.0 || fraction >= 1.0)
124 1212 : return compare_path_costs(path1, path2, TOTAL_COST);
125 2448 : cost1 = path1->startup_cost +
126 1224 : fraction * (path1->total_cost - path1->startup_cost);
127 2448 : cost2 = path2->startup_cost +
128 1224 : fraction * (path2->total_cost - path2->startup_cost);
129 1224 : if (cost1 < cost2)
130 644 : return -1;
131 580 : if (cost1 > cost2)
132 580 : return +1;
133 0 : return 0;
134 : }
135 :
136 : /*
137 : * compare_path_costs_fuzzily
138 : * Compare the costs of two paths to see if either can be said to
139 : * dominate the other.
140 : *
141 : * We use fuzzy comparisons so that add_path() can avoid keeping both of
142 : * a pair of paths that really have insignificantly different cost.
143 : *
144 : * The fuzz_factor argument must be 1.0 plus delta, where delta is the
145 : * fraction of the smaller cost that is considered to be a significant
146 : * difference. For example, fuzz_factor = 1.01 makes the fuzziness limit
147 : * be 1% of the smaller cost.
148 : *
149 : * The two paths are said to have "equal" costs if both startup and total
150 : * costs are fuzzily the same. Path1 is said to be better than path2 if
151 : * it has fuzzily better startup cost and fuzzily no worse total cost,
152 : * or if it has fuzzily better total cost and fuzzily no worse startup cost.
153 : * Path2 is better than path1 if the reverse holds. Finally, if one path
154 : * is fuzzily better than the other on startup cost and fuzzily worse on
155 : * total cost, we just say that their costs are "different", since neither
156 : * dominates the other across the whole performance spectrum.
157 : *
158 : * This function also enforces a policy rule that paths for which the relevant
159 : * one of parent->consider_startup and parent->consider_param_startup is false
160 : * cannot survive comparisons solely on the grounds of good startup cost, so
161 : * we never return COSTS_DIFFERENT when that is true for the total-cost loser.
162 : * (But if total costs are fuzzily equal, we compare startup costs anyway,
163 : * in hopes of eliminating one path or the other.)
164 : */
165 : static PathCostComparison
166 1899688 : compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor)
167 : {
168 : #define CONSIDER_PATH_STARTUP_COST(p) \
169 : ((p)->param_info == NULL ? (p)->parent->consider_startup : (p)->parent->consider_param_startup)
170 :
171 : /*
172 : * Check total cost first since it's more likely to be different; many
173 : * paths have zero startup cost.
174 : */
175 1899688 : if (path1->total_cost > path2->total_cost * fuzz_factor)
176 : {
177 : /* path1 fuzzily worse on total cost */
178 907124 : if (CONSIDER_PATH_STARTUP_COST(path1) &&
179 34506 : path2->startup_cost > path1->startup_cost * fuzz_factor)
180 : {
181 : /* ... but path2 fuzzily worse on startup, so DIFFERENT */
182 17092 : return COSTS_DIFFERENT;
183 : }
184 : /* else path2 dominates */
185 890032 : return COSTS_BETTER2;
186 : }
187 992564 : if (path2->total_cost > path1->total_cost * fuzz_factor)
188 : {
189 : /* path2 fuzzily worse on total cost */
190 499550 : if (CONSIDER_PATH_STARTUP_COST(path2) &&
191 13222 : path1->startup_cost > path2->startup_cost * fuzz_factor)
192 : {
193 : /* ... but path1 fuzzily worse on startup, so DIFFERENT */
194 7100 : return COSTS_DIFFERENT;
195 : }
196 : /* else path1 dominates */
197 492450 : return COSTS_BETTER1;
198 : }
199 : /* fuzzily the same on total cost ... */
200 493014 : if (path1->startup_cost > path2->startup_cost * fuzz_factor)
201 : {
202 : /* ... but path1 fuzzily worse on startup, so path2 wins */
203 193244 : return COSTS_BETTER2;
204 : }
205 299770 : if (path2->startup_cost > path1->startup_cost * fuzz_factor)
206 : {
207 : /* ... but path2 fuzzily worse on startup, so path1 wins */
208 41570 : return COSTS_BETTER1;
209 : }
210 : /* fuzzily the same on both costs */
211 258200 : return COSTS_EQUAL;
212 :
213 : #undef CONSIDER_PATH_STARTUP_COST
214 : }
215 :
216 : /*
217 : * set_cheapest
218 : * Find the minimum-cost paths from among a relation's paths,
219 : * and save them in the rel's cheapest-path fields.
220 : *
221 : * cheapest_total_path is normally the cheapest-total-cost unparameterized
222 : * path; but if there are no unparameterized paths, we assign it to be the
223 : * best (cheapest least-parameterized) parameterized path. However, only
224 : * unparameterized paths are considered candidates for cheapest_startup_path,
225 : * so that will be NULL if there are no unparameterized paths.
226 : *
227 : * The cheapest_parameterized_paths list collects all parameterized paths
228 : * that have survived the add_path() tournament for this relation. (Since
229 : * add_path ignores pathkeys for a parameterized path, these will be paths
230 : * that have best cost or best row count for their parameterization. We
231 : * may also have both a parallel-safe and a non-parallel-safe path in some
232 : * cases for the same parameterization in some cases, but this should be
233 : * relatively rare since, most typically, all paths for the same relation
234 : * will be parallel-safe or none of them will.)
235 : *
236 : * cheapest_parameterized_paths always includes the cheapest-total
237 : * unparameterized path, too, if there is one; the users of that list find
238 : * it more convenient if that's included.
239 : *
240 : * This is normally called only after we've finished constructing the path
241 : * list for the rel node.
242 : */
243 : void
244 1199954 : set_cheapest(RelOptInfo *parent_rel)
245 : {
246 : Path *cheapest_startup_path;
247 : Path *cheapest_total_path;
248 : Path *best_param_path;
249 : List *parameterized_paths;
250 : ListCell *p;
251 :
252 : Assert(IsA(parent_rel, RelOptInfo));
253 :
254 1199954 : if (parent_rel->pathlist == NIL)
255 0 : elog(ERROR, "could not devise a query plan for the given query");
256 :
257 1199954 : cheapest_startup_path = cheapest_total_path = best_param_path = NULL;
258 1199954 : parameterized_paths = NIL;
259 :
260 2636092 : foreach(p, parent_rel->pathlist)
261 : {
262 1436138 : Path *path = (Path *) lfirst(p);
263 : int cmp;
264 :
265 1436138 : if (path->param_info)
266 : {
267 : /* Parameterized path, so add it to parameterized_paths */
268 65076 : parameterized_paths = lappend(parameterized_paths, path);
269 :
270 : /*
271 : * If we have an unparameterized cheapest-total, we no longer care
272 : * about finding the best parameterized path, so move on.
273 : */
274 65076 : if (cheapest_total_path)
275 8918 : continue;
276 :
277 : /*
278 : * Otherwise, track the best parameterized path, which is the one
279 : * with least total cost among those of the minimum
280 : * parameterization.
281 : */
282 56158 : if (best_param_path == NULL)
283 53220 : best_param_path = path;
284 : else
285 : {
286 2938 : switch (bms_subset_compare(PATH_REQ_OUTER(path),
287 2938 : PATH_REQ_OUTER(best_param_path)))
288 : {
289 36 : case BMS_EQUAL:
290 : /* keep the cheaper one */
291 36 : if (compare_path_costs(path, best_param_path,
292 : TOTAL_COST) < 0)
293 0 : best_param_path = path;
294 36 : break;
295 102 : case BMS_SUBSET1:
296 : /* new path is less-parameterized */
297 102 : best_param_path = path;
298 102 : break;
299 58 : case BMS_SUBSET2:
300 : /* old path is less-parameterized, keep it */
301 58 : break;
302 2742 : case BMS_DIFFERENT:
303 :
304 : /*
305 : * This means that neither path has the least possible
306 : * parameterization for the rel. We'll sit on the old
307 : * path until something better comes along.
308 : */
309 2742 : break;
310 : }
311 56158 : }
312 : }
313 : else
314 : {
315 : /* Unparameterized path, so consider it for cheapest slots */
316 1371062 : if (cheapest_total_path == NULL)
317 : {
318 1198434 : cheapest_startup_path = cheapest_total_path = path;
319 1198434 : continue;
320 : }
321 :
322 : /*
323 : * If we find two paths of identical costs, try to keep the
324 : * better-sorted one. The paths might have unrelated sort
325 : * orderings, in which case we can only guess which might be
326 : * better to keep, but if one is superior then we definitely
327 : * should keep that one.
328 : */
329 172628 : cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
330 172628 : if (cmp > 0 ||
331 94 : (cmp == 0 &&
332 94 : compare_pathkeys(cheapest_startup_path->pathkeys,
333 : path->pathkeys) == PATHKEYS_BETTER2))
334 41002 : cheapest_startup_path = path;
335 :
336 172628 : cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST);
337 172628 : if (cmp > 0 ||
338 8 : (cmp == 0 &&
339 8 : compare_pathkeys(cheapest_total_path->pathkeys,
340 : path->pathkeys) == PATHKEYS_BETTER2))
341 0 : cheapest_total_path = path;
342 : }
343 : }
344 :
345 : /* Add cheapest unparameterized path, if any, to parameterized_paths */
346 1199954 : if (cheapest_total_path)
347 1198434 : parameterized_paths = lcons(cheapest_total_path, parameterized_paths);
348 :
349 : /*
350 : * If there is no unparameterized path, use the best parameterized path as
351 : * cheapest_total_path (but not as cheapest_startup_path).
352 : */
353 1199954 : if (cheapest_total_path == NULL)
354 1520 : cheapest_total_path = best_param_path;
355 : Assert(cheapest_total_path != NULL);
356 :
357 1199954 : parent_rel->cheapest_startup_path = cheapest_startup_path;
358 1199954 : parent_rel->cheapest_total_path = cheapest_total_path;
359 1199954 : parent_rel->cheapest_unique_path = NULL; /* computed only if needed */
360 1199954 : parent_rel->cheapest_parameterized_paths = parameterized_paths;
361 1199954 : }
362 :
363 : /*
364 : * add_path
365 : * Consider a potential implementation path for the specified parent rel,
366 : * and add it to the rel's pathlist if it is worthy of consideration.
367 : * A path is worthy if it has a better sort order (better pathkeys) or
368 : * cheaper cost (on either dimension), or generates fewer rows, than any
369 : * existing path that has the same or superset parameterization rels.
370 : * We also consider parallel-safe paths more worthy than others.
371 : *
372 : * We also remove from the rel's pathlist any old paths that are dominated
373 : * by new_path --- that is, new_path is cheaper, at least as well ordered,
374 : * generates no more rows, requires no outer rels not required by the old
375 : * path, and is no less parallel-safe.
376 : *
377 : * In most cases, a path with a superset parameterization will generate
378 : * fewer rows (since it has more join clauses to apply), so that those two
379 : * figures of merit move in opposite directions; this means that a path of
380 : * one parameterization can seldom dominate a path of another. But such
381 : * cases do arise, so we make the full set of checks anyway.
382 : *
383 : * There are two policy decisions embedded in this function, along with
384 : * its sibling add_path_precheck. First, we treat all parameterized paths
385 : * as having NIL pathkeys, so that they cannot win comparisons on the
386 : * basis of sort order. This is to reduce the number of parameterized
387 : * paths that are kept; see discussion in src/backend/optimizer/README.
388 : *
389 : * Second, we only consider cheap startup cost to be interesting if
390 : * parent_rel->consider_startup is true for an unparameterized path, or
391 : * parent_rel->consider_param_startup is true for a parameterized one.
392 : * Again, this allows discarding useless paths sooner.
393 : *
394 : * The pathlist is kept sorted by total_cost, with cheaper paths
395 : * at the front. Within this routine, that's simply a speed hack:
396 : * doing it that way makes it more likely that we will reject an inferior
397 : * path after a few comparisons, rather than many comparisons.
398 : * However, add_path_precheck relies on this ordering to exit early
399 : * when possible.
400 : *
401 : * NOTE: discarded Path objects are immediately pfree'd to reduce planner
402 : * memory consumption. We dare not try to free the substructure of a Path,
403 : * since much of it may be shared with other Paths or the query tree itself;
404 : * but just recycling discarded Path nodes is a very useful savings in
405 : * a large join tree. We can recycle the List nodes of pathlist, too.
406 : *
407 : * As noted in optimizer/README, deleting a previously-accepted Path is
408 : * safe because we know that Paths of this rel cannot yet be referenced
409 : * from any other rel, such as a higher-level join. However, in some cases
410 : * it is possible that a Path is referenced by another Path for its own
411 : * rel; we must not delete such a Path, even if it is dominated by the new
412 : * Path. Currently this occurs only for IndexPath objects, which may be
413 : * referenced as children of BitmapHeapPaths as well as being paths in
414 : * their own right. Hence, we don't pfree IndexPaths when rejecting them.
415 : *
416 : * 'parent_rel' is the relation entry to which the path corresponds.
417 : * 'new_path' is a potential path for parent_rel.
418 : *
419 : * Returns nothing, but modifies parent_rel->pathlist.
420 : */
421 : void
422 2212394 : add_path(RelOptInfo *parent_rel, Path *new_path)
423 : {
424 2212394 : bool accept_new = true; /* unless we find a superior old path */
425 2212394 : int insert_at = 0; /* where to insert new item */
426 : List *new_path_pathkeys;
427 : ListCell *p1;
428 :
429 : /*
430 : * This is a convenient place to check for query cancel --- no part of the
431 : * planner goes very long without calling add_path().
432 : */
433 2212394 : CHECK_FOR_INTERRUPTS();
434 :
435 : /* Pretend parameterized paths have no pathkeys, per comment above */
436 2212394 : new_path_pathkeys = new_path->param_info ? NIL : new_path->pathkeys;
437 :
438 : /*
439 : * Loop to check proposed new path against old paths. Note it is possible
440 : * for more than one old path to be tossed out because new_path dominates
441 : * it.
442 : */
443 3167886 : foreach(p1, parent_rel->pathlist)
444 : {
445 1725086 : Path *old_path = (Path *) lfirst(p1);
446 1725086 : bool remove_old = false; /* unless new proves superior */
447 : PathCostComparison costcmp;
448 : PathKeysComparison keyscmp;
449 : BMS_Comparison outercmp;
450 :
451 : /*
452 : * Do a fuzzy cost comparison with standard fuzziness limit.
453 : */
454 1725086 : costcmp = compare_path_costs_fuzzily(new_path, old_path,
455 : STD_FUZZ_FACTOR);
456 :
457 : /*
458 : * If the two paths compare differently for startup and total cost,
459 : * then we want to keep both, and we can skip comparing pathkeys and
460 : * required_outer rels. If they compare the same, proceed with the
461 : * other comparisons. Row count is checked last. (We make the tests
462 : * in this order because the cost comparison is most likely to turn
463 : * out "different", and the pathkeys comparison next most likely. As
464 : * explained above, row count very seldom makes a difference, so even
465 : * though it's cheap to compare there's not much point in checking it
466 : * earlier.)
467 : */
468 1725086 : if (costcmp != COSTS_DIFFERENT)
469 : {
470 : /* Similarly check to see if either dominates on pathkeys */
471 : List *old_path_pathkeys;
472 :
473 1700904 : old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
474 1700904 : keyscmp = compare_pathkeys(new_path_pathkeys,
475 : old_path_pathkeys);
476 1700904 : if (keyscmp != PATHKEYS_DIFFERENT)
477 : {
478 1632818 : switch (costcmp)
479 : {
480 184674 : case COSTS_EQUAL:
481 184674 : outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
482 184674 : PATH_REQ_OUTER(old_path));
483 184674 : if (keyscmp == PATHKEYS_BETTER1)
484 : {
485 1516 : if ((outercmp == BMS_EQUAL ||
486 1516 : outercmp == BMS_SUBSET1) &&
487 1516 : new_path->rows <= old_path->rows &&
488 1500 : new_path->parallel_safe >= old_path->parallel_safe)
489 1500 : remove_old = true; /* new dominates old */
490 : }
491 183158 : else if (keyscmp == PATHKEYS_BETTER2)
492 : {
493 7348 : if ((outercmp == BMS_EQUAL ||
494 7348 : outercmp == BMS_SUBSET2) &&
495 7348 : new_path->rows >= old_path->rows &&
496 7272 : new_path->parallel_safe <= old_path->parallel_safe)
497 7272 : accept_new = false; /* old dominates new */
498 : }
499 : else /* keyscmp == PATHKEYS_EQUAL */
500 : {
501 175810 : if (outercmp == BMS_EQUAL)
502 : {
503 : /*
504 : * Same pathkeys and outer rels, and fuzzily
505 : * the same cost, so keep just one; to decide
506 : * which, first check parallel-safety, then
507 : * rows, then do a fuzzy cost comparison with
508 : * very small fuzz limit. (We used to do an
509 : * exact cost comparison, but that results in
510 : * annoying platform-specific plan variations
511 : * due to roundoff in the cost estimates.) If
512 : * things are still tied, arbitrarily keep
513 : * only the old path. Notice that we will
514 : * keep only the old path even if the
515 : * less-fuzzy comparison decides the startup
516 : * and total costs compare differently.
517 : */
518 349508 : if (new_path->parallel_safe >
519 174754 : old_path->parallel_safe)
520 32 : remove_old = true; /* new dominates old */
521 349444 : else if (new_path->parallel_safe <
522 174722 : old_path->parallel_safe)
523 84 : accept_new = false; /* old dominates new */
524 174638 : else if (new_path->rows < old_path->rows)
525 4 : remove_old = true; /* new dominates old */
526 174634 : else if (new_path->rows > old_path->rows)
527 32 : accept_new = false; /* old dominates new */
528 174602 : else if (compare_path_costs_fuzzily(new_path,
529 : old_path,
530 : 1.0000000001) == COSTS_BETTER1)
531 5322 : remove_old = true; /* new dominates old */
532 : else
533 169280 : accept_new = false; /* old equals or
534 : * dominates new */
535 : }
536 1056 : else if (outercmp == BMS_SUBSET1 &&
537 338 : new_path->rows <= old_path->rows &&
538 326 : new_path->parallel_safe >= old_path->parallel_safe)
539 326 : remove_old = true; /* new dominates old */
540 730 : else if (outercmp == BMS_SUBSET2 &&
541 618 : new_path->rows >= old_path->rows &&
542 554 : new_path->parallel_safe <= old_path->parallel_safe)
543 554 : accept_new = false; /* old dominates new */
544 : /* else different parameterizations, keep both */
545 : }
546 184674 : break;
547 516658 : case COSTS_BETTER1:
548 516658 : if (keyscmp != PATHKEYS_BETTER2)
549 : {
550 354194 : outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
551 354194 : PATH_REQ_OUTER(old_path));
552 354194 : if ((outercmp == BMS_EQUAL ||
553 304300 : outercmp == BMS_SUBSET1) &&
554 304300 : new_path->rows <= old_path->rows &&
555 302534 : new_path->parallel_safe >= old_path->parallel_safe)
556 301098 : remove_old = true; /* new dominates old */
557 : }
558 516658 : break;
559 931486 : case COSTS_BETTER2:
560 931486 : if (keyscmp != PATHKEYS_BETTER1)
561 : {
562 649260 : outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
563 649260 : PATH_REQ_OUTER(old_path));
564 649260 : if ((outercmp == BMS_EQUAL ||
565 616778 : outercmp == BMS_SUBSET2) &&
566 616778 : new_path->rows >= old_path->rows &&
567 593864 : new_path->parallel_safe <= old_path->parallel_safe)
568 592372 : accept_new = false; /* old dominates new */
569 : }
570 931486 : break;
571 0 : case COSTS_DIFFERENT:
572 :
573 : /*
574 : * can't get here, but keep this case to keep compiler
575 : * quiet
576 : */
577 0 : break;
578 : }
579 92268 : }
580 : }
581 :
582 : /*
583 : * Remove current element from pathlist if dominated by new.
584 : */
585 1725086 : if (remove_old)
586 : {
587 308282 : parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist,
588 : p1);
589 :
590 : /*
591 : * Delete the data pointed-to by the deleted cell, if possible
592 : */
593 308282 : if (!IsA(old_path, IndexPath))
594 294092 : pfree(old_path);
595 : }
596 : else
597 : {
598 : /* new belongs after this old path if it has cost >= old's */
599 1416804 : if (new_path->total_cost >= old_path->total_cost)
600 1147426 : insert_at = foreach_current_index(p1) + 1;
601 : }
602 :
603 : /*
604 : * If we found an old path that dominates new_path, we can quit
605 : * scanning the pathlist; we will not add new_path, and we assume
606 : * new_path cannot dominate any other elements of the pathlist.
607 : */
608 1725086 : if (!accept_new)
609 769594 : break;
610 : }
611 :
612 2212394 : if (accept_new)
613 : {
614 : /* Accept the new path: insert it at proper place in pathlist */
615 1442800 : parent_rel->pathlist =
616 1442800 : list_insert_nth(parent_rel->pathlist, insert_at, new_path);
617 : }
618 : else
619 : {
620 : /* Reject and recycle the new path */
621 769594 : if (!IsA(new_path, IndexPath))
622 717292 : pfree(new_path);
623 : }
624 2212394 : }
625 :
626 : /*
627 : * add_path_precheck
628 : * Check whether a proposed new path could possibly get accepted.
629 : * We assume we know the path's pathkeys and parameterization accurately,
630 : * and have lower bounds for its costs.
631 : *
632 : * Note that we do not know the path's rowcount, since getting an estimate for
633 : * that is too expensive to do before prechecking. We assume here that paths
634 : * of a superset parameterization will generate fewer rows; if that holds,
635 : * then paths with different parameterizations cannot dominate each other
636 : * and so we can simply ignore existing paths of another parameterization.
637 : * (In the infrequent cases where that rule of thumb fails, add_path will
638 : * get rid of the inferior path.)
639 : *
640 : * At the time this is called, we haven't actually built a Path structure,
641 : * so the required information has to be passed piecemeal.
642 : */
643 : bool
644 1912344 : add_path_precheck(RelOptInfo *parent_rel,
645 : Cost startup_cost, Cost total_cost,
646 : List *pathkeys, Relids required_outer)
647 : {
648 : List *new_path_pathkeys;
649 : bool consider_startup;
650 : ListCell *p1;
651 :
652 : /* Pretend parameterized paths have no pathkeys, per add_path policy */
653 1912344 : new_path_pathkeys = required_outer ? NIL : pathkeys;
654 :
655 : /* Decide whether new path's startup cost is interesting */
656 1912344 : consider_startup = required_outer ? parent_rel->consider_param_startup : parent_rel->consider_startup;
657 :
658 2370398 : foreach(p1, parent_rel->pathlist)
659 : {
660 2238048 : Path *old_path = (Path *) lfirst(p1);
661 : PathKeysComparison keyscmp;
662 :
663 : /*
664 : * We are looking for an old_path with the same parameterization (and
665 : * by assumption the same rowcount) that dominates the new path on
666 : * pathkeys as well as both cost metrics. If we find one, we can
667 : * reject the new path.
668 : *
669 : * Cost comparisons here should match compare_path_costs_fuzzily.
670 : */
671 2238048 : if (total_cost > old_path->total_cost * STD_FUZZ_FACTOR)
672 : {
673 : /* new path can win on startup cost only if consider_startup */
674 1465088 : if (startup_cost > old_path->startup_cost * STD_FUZZ_FACTOR ||
675 747642 : !consider_startup)
676 : {
677 : /* new path loses on cost, so check pathkeys... */
678 : List *old_path_pathkeys;
679 :
680 1448624 : old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
681 1448624 : keyscmp = compare_pathkeys(new_path_pathkeys,
682 : old_path_pathkeys);
683 1448624 : if (keyscmp == PATHKEYS_EQUAL ||
684 : keyscmp == PATHKEYS_BETTER2)
685 : {
686 : /* new path does not win on pathkeys... */
687 1018614 : if (bms_equal(required_outer, PATH_REQ_OUTER(old_path)))
688 : {
689 : /* Found an old path that dominates the new one */
690 1007034 : return false;
691 : }
692 : }
693 : }
694 : }
695 : else
696 : {
697 : /*
698 : * Since the pathlist is sorted by total_cost, we can stop looking
699 : * once we reach a path with a total_cost larger than the new
700 : * path's.
701 : */
702 772960 : break;
703 : }
704 : }
705 :
706 905310 : return true;
707 : }
708 :
709 : /*
710 : * add_partial_path
711 : * Like add_path, our goal here is to consider whether a path is worthy
712 : * of being kept around, but the considerations here are a bit different.
713 : * A partial path is one which can be executed in any number of workers in
714 : * parallel such that each worker will generate a subset of the path's
715 : * overall result.
716 : *
717 : * As in add_path, the partial_pathlist is kept sorted with the cheapest
718 : * total path in front. This is depended on by multiple places, which
719 : * just take the front entry as the cheapest path without searching.
720 : *
721 : * We don't generate parameterized partial paths for several reasons. Most
722 : * importantly, they're not safe to execute, because there's nothing to
723 : * make sure that a parallel scan within the parameterized portion of the
724 : * plan is running with the same value in every worker at the same time.
725 : * Fortunately, it seems unlikely to be worthwhile anyway, because having
726 : * each worker scan the entire outer relation and a subset of the inner
727 : * relation will generally be a terrible plan. The inner (parameterized)
728 : * side of the plan will be small anyway. There could be rare cases where
729 : * this wins big - e.g. if join order constraints put a 1-row relation on
730 : * the outer side of the topmost join with a parameterized plan on the inner
731 : * side - but we'll have to be content not to handle such cases until
732 : * somebody builds an executor infrastructure that can cope with them.
733 : *
734 : * Because we don't consider parameterized paths here, we also don't
735 : * need to consider the row counts as a measure of quality: every path will
736 : * produce the same number of rows. Neither do we need to consider startup
737 : * costs: parallelism is only used for plans that will be run to completion.
738 : * Therefore, this routine is much simpler than add_path: it needs to
739 : * consider only pathkeys and total cost.
740 : *
741 : * As with add_path, we pfree paths that are found to be dominated by
742 : * another partial path; this requires that there be no other references to
743 : * such paths yet. Hence, GatherPaths must not be created for a rel until
744 : * we're done creating all partial paths for it. Unlike add_path, we don't
745 : * take an exception for IndexPaths as partial index paths won't be
746 : * referenced by partial BitmapHeapPaths.
747 : */
748 : void
749 57424 : add_partial_path(RelOptInfo *parent_rel, Path *new_path)
750 : {
751 57424 : bool accept_new = true; /* unless we find a superior old path */
752 57424 : int insert_at = 0; /* where to insert new item */
753 : ListCell *p1;
754 :
755 : /* Check for query cancel. */
756 57424 : CHECK_FOR_INTERRUPTS();
757 :
758 : /* Path to be added must be parallel safe. */
759 : Assert(new_path->parallel_safe);
760 :
761 : /* Relation should be OK for parallelism, too. */
762 : Assert(parent_rel->consider_parallel);
763 :
764 : /*
765 : * As in add_path, throw out any paths which are dominated by the new
766 : * path, but throw out the new path if some existing path dominates it.
767 : */
768 76576 : foreach(p1, parent_rel->partial_pathlist)
769 : {
770 27424 : Path *old_path = (Path *) lfirst(p1);
771 27424 : bool remove_old = false; /* unless new proves superior */
772 : PathKeysComparison keyscmp;
773 :
774 : /* Compare pathkeys. */
775 27424 : keyscmp = compare_pathkeys(new_path->pathkeys, old_path->pathkeys);
776 :
777 : /* Unless pathkeys are incompatible, keep just one of the two paths. */
778 27424 : if (keyscmp != PATHKEYS_DIFFERENT)
779 : {
780 27296 : if (new_path->total_cost > old_path->total_cost * STD_FUZZ_FACTOR)
781 : {
782 : /* New path costs more; keep it only if pathkeys are better. */
783 8856 : if (keyscmp != PATHKEYS_BETTER1)
784 3614 : accept_new = false;
785 : }
786 36880 : else if (old_path->total_cost > new_path->total_cost
787 18440 : * STD_FUZZ_FACTOR)
788 : {
789 : /* Old path costs more; keep it only if pathkeys are better. */
790 13538 : if (keyscmp != PATHKEYS_BETTER2)
791 7324 : remove_old = true;
792 : }
793 4902 : else if (keyscmp == PATHKEYS_BETTER1)
794 : {
795 : /* Costs are about the same, new path has better pathkeys. */
796 0 : remove_old = true;
797 : }
798 4902 : else if (keyscmp == PATHKEYS_BETTER2)
799 : {
800 : /* Costs are about the same, old path has better pathkeys. */
801 1056 : accept_new = false;
802 : }
803 3846 : else if (old_path->total_cost > new_path->total_cost * 1.0000000001)
804 : {
805 : /* Pathkeys are the same, and the old path costs more. */
806 244 : remove_old = true;
807 : }
808 : else
809 : {
810 : /*
811 : * Pathkeys are the same, and new path isn't materially
812 : * cheaper.
813 : */
814 3602 : accept_new = false;
815 : }
816 : }
817 :
818 : /*
819 : * Remove current element from partial_pathlist if dominated by new.
820 : */
821 27424 : if (remove_old)
822 : {
823 7568 : parent_rel->partial_pathlist =
824 7568 : foreach_delete_current(parent_rel->partial_pathlist, p1);
825 7568 : pfree(old_path);
826 : }
827 : else
828 : {
829 : /* new belongs after this old path if it has cost >= old's */
830 19856 : if (new_path->total_cost >= old_path->total_cost)
831 13402 : insert_at = foreach_current_index(p1) + 1;
832 : }
833 :
834 : /*
835 : * If we found an old path that dominates new_path, we can quit
836 : * scanning the partial_pathlist; we will not add new_path, and we
837 : * assume new_path cannot dominate any later path.
838 : */
839 27424 : if (!accept_new)
840 8272 : break;
841 : }
842 :
843 57424 : if (accept_new)
844 : {
845 : /* Accept the new path: insert it at proper place */
846 49152 : parent_rel->partial_pathlist =
847 49152 : list_insert_nth(parent_rel->partial_pathlist, insert_at, new_path);
848 : }
849 : else
850 : {
851 : /* Reject and recycle the new path */
852 8272 : pfree(new_path);
853 : }
854 57424 : }
855 :
856 : /*
857 : * add_partial_path_precheck
858 : * Check whether a proposed new partial path could possibly get accepted.
859 : *
860 : * Unlike add_path_precheck, we can ignore startup cost and parameterization,
861 : * since they don't matter for partial paths (see add_partial_path). But
862 : * we do want to make sure we don't add a partial path if there's already
863 : * a complete path that dominates it, since in that case the proposed path
864 : * is surely a loser.
865 : */
866 : bool
867 34168 : add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost,
868 : List *pathkeys)
869 : {
870 : ListCell *p1;
871 :
872 : /*
873 : * Our goal here is twofold. First, we want to find out whether this path
874 : * is clearly inferior to some existing partial path. If so, we want to
875 : * reject it immediately. Second, we want to find out whether this path
876 : * is clearly superior to some existing partial path -- at least, modulo
877 : * final cost computations. If so, we definitely want to consider it.
878 : *
879 : * Unlike add_path(), we always compare pathkeys here. This is because we
880 : * expect partial_pathlist to be very short, and getting a definitive
881 : * answer at this stage avoids the need to call add_path_precheck.
882 : */
883 47994 : foreach(p1, parent_rel->partial_pathlist)
884 : {
885 38648 : Path *old_path = (Path *) lfirst(p1);
886 : PathKeysComparison keyscmp;
887 :
888 38648 : keyscmp = compare_pathkeys(pathkeys, old_path->pathkeys);
889 38648 : if (keyscmp != PATHKEYS_DIFFERENT)
890 : {
891 38520 : if (total_cost > old_path->total_cost * STD_FUZZ_FACTOR &&
892 : keyscmp != PATHKEYS_BETTER1)
893 24822 : return false;
894 18850 : if (old_path->total_cost > total_cost * STD_FUZZ_FACTOR &&
895 : keyscmp != PATHKEYS_BETTER2)
896 5152 : return true;
897 : }
898 : }
899 :
900 : /*
901 : * This path is neither clearly inferior to an existing partial path nor
902 : * clearly good enough that it might replace one. Compare it to
903 : * non-parallel plans. If it loses even before accounting for the cost of
904 : * the Gather node, we should definitely reject it.
905 : *
906 : * Note that we pass the total_cost to add_path_precheck twice. This is
907 : * because it's never advantageous to consider the startup cost of a
908 : * partial path; the resulting plans, if run in parallel, will be run to
909 : * completion.
910 : */
911 9346 : if (!add_path_precheck(parent_rel, total_cost, total_cost, pathkeys,
912 : NULL))
913 252 : return false;
914 :
915 9094 : return true;
916 : }
917 :
918 :
919 : /*****************************************************************************
920 : * PATH NODE CREATION ROUTINES
921 : *****************************************************************************/
922 :
923 : /*
924 : * create_seqscan_path
925 : * Creates a path corresponding to a sequential scan, returning the
926 : * pathnode.
927 : */
928 : Path *
929 250594 : create_seqscan_path(PlannerInfo *root, RelOptInfo *rel,
930 : Relids required_outer, int parallel_workers)
931 : {
932 250594 : Path *pathnode = makeNode(Path);
933 :
934 250594 : pathnode->pathtype = T_SeqScan;
935 250594 : pathnode->parent = rel;
936 250594 : pathnode->pathtarget = rel->reltarget;
937 250594 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
938 : required_outer);
939 250594 : pathnode->parallel_aware = parallel_workers > 0 ? true : false;
940 250594 : pathnode->parallel_safe = rel->consider_parallel;
941 250594 : pathnode->parallel_workers = parallel_workers;
942 250594 : pathnode->pathkeys = NIL; /* seqscan has unordered result */
943 :
944 250594 : cost_seqscan(pathnode, root, rel, pathnode->param_info);
945 :
946 250594 : return pathnode;
947 : }
948 :
949 : /*
950 : * create_samplescan_path
951 : * Creates a path node for a sampled table scan.
952 : */
953 : Path *
954 180 : create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
955 : {
956 180 : Path *pathnode = makeNode(Path);
957 :
958 180 : pathnode->pathtype = T_SampleScan;
959 180 : pathnode->parent = rel;
960 180 : pathnode->pathtarget = rel->reltarget;
961 180 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
962 : required_outer);
963 180 : pathnode->parallel_aware = false;
964 180 : pathnode->parallel_safe = rel->consider_parallel;
965 180 : pathnode->parallel_workers = 0;
966 180 : pathnode->pathkeys = NIL; /* samplescan has unordered result */
967 :
968 180 : cost_samplescan(pathnode, root, rel, pathnode->param_info);
969 :
970 180 : return pathnode;
971 : }
972 :
973 : /*
974 : * create_index_path
975 : * Creates a path node for an index scan.
976 : *
977 : * 'index' is a usable index.
978 : * 'indexclauses' is a list of IndexClause nodes representing clauses
979 : * to be enforced as qual conditions in the scan.
980 : * 'indexorderbys' is a list of bare expressions (no RestrictInfos)
981 : * to be used as index ordering operators in the scan.
982 : * 'indexorderbycols' is an integer list of index column numbers (zero based)
983 : * the ordering operators can be used with.
984 : * 'pathkeys' describes the ordering of the path.
985 : * 'indexscandir' is ForwardScanDirection or BackwardScanDirection
986 : * for an ordered index, or NoMovementScanDirection for
987 : * an unordered index.
988 : * 'indexonly' is true if an index-only scan is wanted.
989 : * 'required_outer' is the set of outer relids for a parameterized path.
990 : * 'loop_count' is the number of repetitions of the indexscan to factor into
991 : * estimates of caching behavior.
992 : * 'partial_path' is true if constructing a parallel index scan path.
993 : *
994 : * Returns the new path node.
995 : */
996 : IndexPath *
997 408190 : create_index_path(PlannerInfo *root,
998 : IndexOptInfo *index,
999 : List *indexclauses,
1000 : List *indexorderbys,
1001 : List *indexorderbycols,
1002 : List *pathkeys,
1003 : ScanDirection indexscandir,
1004 : bool indexonly,
1005 : Relids required_outer,
1006 : double loop_count,
1007 : bool partial_path)
1008 : {
1009 408190 : IndexPath *pathnode = makeNode(IndexPath);
1010 408190 : RelOptInfo *rel = index->rel;
1011 :
1012 408190 : pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
1013 408190 : pathnode->path.parent = rel;
1014 408190 : pathnode->path.pathtarget = rel->reltarget;
1015 408190 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1016 : required_outer);
1017 408190 : pathnode->path.parallel_aware = false;
1018 408190 : pathnode->path.parallel_safe = rel->consider_parallel;
1019 408190 : pathnode->path.parallel_workers = 0;
1020 408190 : pathnode->path.pathkeys = pathkeys;
1021 :
1022 408190 : pathnode->indexinfo = index;
1023 408190 : pathnode->indexclauses = indexclauses;
1024 408190 : pathnode->indexorderbys = indexorderbys;
1025 408190 : pathnode->indexorderbycols = indexorderbycols;
1026 408190 : pathnode->indexscandir = indexscandir;
1027 :
1028 408190 : cost_index(pathnode, root, loop_count, partial_path);
1029 :
1030 408190 : return pathnode;
1031 : }
1032 :
1033 : /*
1034 : * create_bitmap_heap_path
1035 : * Creates a path node for a bitmap scan.
1036 : *
1037 : * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
1038 : * 'required_outer' is the set of outer relids for a parameterized path.
1039 : * 'loop_count' is the number of repetitions of the indexscan to factor into
1040 : * estimates of caching behavior.
1041 : *
1042 : * loop_count should match the value used when creating the component
1043 : * IndexPaths.
1044 : */
1045 : BitmapHeapPath *
1046 192154 : create_bitmap_heap_path(PlannerInfo *root,
1047 : RelOptInfo *rel,
1048 : Path *bitmapqual,
1049 : Relids required_outer,
1050 : double loop_count,
1051 : int parallel_degree)
1052 : {
1053 192154 : BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
1054 :
1055 192154 : pathnode->path.pathtype = T_BitmapHeapScan;
1056 192154 : pathnode->path.parent = rel;
1057 192154 : pathnode->path.pathtarget = rel->reltarget;
1058 192154 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1059 : required_outer);
1060 192154 : pathnode->path.parallel_aware = parallel_degree > 0 ? true : false;
1061 192154 : pathnode->path.parallel_safe = rel->consider_parallel;
1062 192154 : pathnode->path.parallel_workers = parallel_degree;
1063 192154 : pathnode->path.pathkeys = NIL; /* always unordered */
1064 :
1065 192154 : pathnode->bitmapqual = bitmapqual;
1066 :
1067 192154 : cost_bitmap_heap_scan(&pathnode->path, root, rel,
1068 : pathnode->path.param_info,
1069 : bitmapqual, loop_count);
1070 :
1071 192154 : return pathnode;
1072 : }
1073 :
1074 : /*
1075 : * create_bitmap_and_path
1076 : * Creates a path node representing a BitmapAnd.
1077 : */
1078 : BitmapAndPath *
1079 44 : create_bitmap_and_path(PlannerInfo *root,
1080 : RelOptInfo *rel,
1081 : List *bitmapquals)
1082 : {
1083 44 : BitmapAndPath *pathnode = makeNode(BitmapAndPath);
1084 :
1085 44 : pathnode->path.pathtype = T_BitmapAnd;
1086 44 : pathnode->path.parent = rel;
1087 44 : pathnode->path.pathtarget = rel->reltarget;
1088 44 : pathnode->path.param_info = NULL; /* not used in bitmap trees */
1089 :
1090 : /*
1091 : * Currently, a BitmapHeapPath, BitmapAndPath, or BitmapOrPath will be
1092 : * parallel-safe if and only if rel->consider_parallel is set. So, we can
1093 : * set the flag for this path based only on the relation-level flag,
1094 : * without actually iterating over the list of children.
1095 : */
1096 44 : pathnode->path.parallel_aware = false;
1097 44 : pathnode->path.parallel_safe = rel->consider_parallel;
1098 44 : pathnode->path.parallel_workers = 0;
1099 :
1100 44 : pathnode->path.pathkeys = NIL; /* always unordered */
1101 :
1102 44 : pathnode->bitmapquals = bitmapquals;
1103 :
1104 : /* this sets bitmapselectivity as well as the regular cost fields: */
1105 44 : cost_bitmap_and_node(pathnode, root);
1106 :
1107 44 : return pathnode;
1108 : }
1109 :
1110 : /*
1111 : * create_bitmap_or_path
1112 : * Creates a path node representing a BitmapOr.
1113 : */
1114 : BitmapOrPath *
1115 370 : create_bitmap_or_path(PlannerInfo *root,
1116 : RelOptInfo *rel,
1117 : List *bitmapquals)
1118 : {
1119 370 : BitmapOrPath *pathnode = makeNode(BitmapOrPath);
1120 :
1121 370 : pathnode->path.pathtype = T_BitmapOr;
1122 370 : pathnode->path.parent = rel;
1123 370 : pathnode->path.pathtarget = rel->reltarget;
1124 370 : pathnode->path.param_info = NULL; /* not used in bitmap trees */
1125 :
1126 : /*
1127 : * Currently, a BitmapHeapPath, BitmapAndPath, or BitmapOrPath will be
1128 : * parallel-safe if and only if rel->consider_parallel is set. So, we can
1129 : * set the flag for this path based only on the relation-level flag,
1130 : * without actually iterating over the list of children.
1131 : */
1132 370 : pathnode->path.parallel_aware = false;
1133 370 : pathnode->path.parallel_safe = rel->consider_parallel;
1134 370 : pathnode->path.parallel_workers = 0;
1135 :
1136 370 : pathnode->path.pathkeys = NIL; /* always unordered */
1137 :
1138 370 : pathnode->bitmapquals = bitmapquals;
1139 :
1140 : /* this sets bitmapselectivity as well as the regular cost fields: */
1141 370 : cost_bitmap_or_node(pathnode, root);
1142 :
1143 370 : return pathnode;
1144 : }
1145 :
1146 : /*
1147 : * create_tidscan_path
1148 : * Creates a path corresponding to a scan by TID, returning the pathnode.
1149 : */
1150 : TidPath *
1151 616 : create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
1152 : Relids required_outer)
1153 : {
1154 616 : TidPath *pathnode = makeNode(TidPath);
1155 :
1156 616 : pathnode->path.pathtype = T_TidScan;
1157 616 : pathnode->path.parent = rel;
1158 616 : pathnode->path.pathtarget = rel->reltarget;
1159 616 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1160 : required_outer);
1161 616 : pathnode->path.parallel_aware = false;
1162 616 : pathnode->path.parallel_safe = rel->consider_parallel;
1163 616 : pathnode->path.parallel_workers = 0;
1164 616 : pathnode->path.pathkeys = NIL; /* always unordered */
1165 :
1166 616 : pathnode->tidquals = tidquals;
1167 :
1168 616 : cost_tidscan(&pathnode->path, root, rel, tidquals,
1169 : pathnode->path.param_info);
1170 :
1171 616 : return pathnode;
1172 : }
1173 :
1174 : /*
1175 : * create_append_path
1176 : * Creates a path corresponding to an Append plan, returning the
1177 : * pathnode.
1178 : *
1179 : * Note that we must handle subpaths = NIL, representing a dummy access path.
1180 : * Also, there are callers that pass root = NULL.
1181 : */
1182 : AppendPath *
1183 42188 : create_append_path(PlannerInfo *root,
1184 : RelOptInfo *rel,
1185 : List *subpaths, List *partial_subpaths,
1186 : List *pathkeys, Relids required_outer,
1187 : int parallel_workers, bool parallel_aware,
1188 : List *partitioned_rels, double rows)
1189 : {
1190 42188 : AppendPath *pathnode = makeNode(AppendPath);
1191 : ListCell *l;
1192 :
1193 : Assert(!parallel_aware || parallel_workers > 0);
1194 :
1195 42188 : pathnode->path.pathtype = T_Append;
1196 42188 : pathnode->path.parent = rel;
1197 42188 : pathnode->path.pathtarget = rel->reltarget;
1198 :
1199 : /*
1200 : * When generating an Append path for a partitioned table, there may be
1201 : * parameters that are useful so we can eliminate certain partitions
1202 : * during execution. Here we'll go all the way and fully populate the
1203 : * parameter info data as we do for normal base relations. However, we
1204 : * need only bother doing this for RELOPT_BASEREL rels, as
1205 : * RELOPT_OTHER_MEMBER_REL's Append paths are merged into the base rel's
1206 : * Append subpaths. It would do no harm to do this, we just avoid it to
1207 : * save wasting effort.
1208 : */
1209 42188 : if (partitioned_rels != NIL && root && rel->reloptkind == RELOPT_BASEREL)
1210 24320 : pathnode->path.param_info = get_baserel_parampathinfo(root,
1211 : rel,
1212 : required_outer);
1213 : else
1214 17868 : pathnode->path.param_info = get_appendrel_parampathinfo(rel,
1215 : required_outer);
1216 :
1217 42188 : pathnode->path.parallel_aware = parallel_aware;
1218 42188 : pathnode->path.parallel_safe = rel->consider_parallel;
1219 42188 : pathnode->path.parallel_workers = parallel_workers;
1220 42188 : pathnode->path.pathkeys = pathkeys;
1221 42188 : pathnode->partitioned_rels = list_copy(partitioned_rels);
1222 :
1223 : /*
1224 : * For parallel append, non-partial paths are sorted by descending total
1225 : * costs. That way, the total time to finish all non-partial paths is
1226 : * minimized. Also, the partial paths are sorted by descending startup
1227 : * costs. There may be some paths that require to do startup work by a
1228 : * single worker. In such case, it's better for workers to choose the
1229 : * expensive ones first, whereas the leader should choose the cheapest
1230 : * startup plan.
1231 : */
1232 42188 : if (pathnode->path.parallel_aware)
1233 : {
1234 : /*
1235 : * We mustn't fiddle with the order of subpaths when the Append has
1236 : * pathkeys. The order they're listed in is critical to keeping the
1237 : * pathkeys valid.
1238 : */
1239 : Assert(pathkeys == NIL);
1240 :
1241 15592 : list_sort(subpaths, append_total_cost_compare);
1242 15592 : list_sort(partial_subpaths, append_startup_cost_compare);
1243 : }
1244 42188 : pathnode->first_partial_path = list_length(subpaths);
1245 42188 : pathnode->subpaths = list_concat(subpaths, partial_subpaths);
1246 :
1247 : /*
1248 : * Apply query-wide LIMIT if known and path is for sole base relation.
1249 : * (Handling this at this low level is a bit klugy.)
1250 : */
1251 42188 : if (root != NULL && bms_equal(rel->relids, root->all_baserels))
1252 25954 : pathnode->limit_tuples = root->limit_tuples;
1253 : else
1254 16234 : pathnode->limit_tuples = -1.0;
1255 :
1256 134774 : foreach(l, pathnode->subpaths)
1257 : {
1258 92586 : Path *subpath = (Path *) lfirst(l);
1259 :
1260 169378 : pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
1261 76792 : subpath->parallel_safe;
1262 :
1263 : /* All child paths must have same parameterization */
1264 : Assert(bms_equal(PATH_REQ_OUTER(subpath), required_outer));
1265 : }
1266 :
1267 : Assert(!parallel_aware || pathnode->path.parallel_safe);
1268 :
1269 : /*
1270 : * If there's exactly one child path, the Append is a no-op and will be
1271 : * discarded later (in setrefs.c); therefore, we can inherit the child's
1272 : * size and cost, as well as its pathkeys if any (overriding whatever the
1273 : * caller might've said). Otherwise, we must do the normal costsize
1274 : * calculation.
1275 : */
1276 42188 : if (list_length(pathnode->subpaths) == 1)
1277 : {
1278 15478 : Path *child = (Path *) linitial(pathnode->subpaths);
1279 :
1280 15478 : pathnode->path.rows = child->rows;
1281 15478 : pathnode->path.startup_cost = child->startup_cost;
1282 15478 : pathnode->path.total_cost = child->total_cost;
1283 15478 : pathnode->path.pathkeys = child->pathkeys;
1284 : }
1285 : else
1286 26710 : cost_append(pathnode);
1287 :
1288 : /* If the caller provided a row estimate, override the computed value. */
1289 42188 : if (rows >= 0)
1290 300 : pathnode->path.rows = rows;
1291 :
1292 42188 : return pathnode;
1293 : }
1294 :
1295 : /*
1296 : * append_total_cost_compare
1297 : * list_sort comparator for sorting append child paths
1298 : * by total_cost descending
1299 : *
1300 : * For equal total costs, we fall back to comparing startup costs; if those
1301 : * are equal too, break ties using bms_compare on the paths' relids.
1302 : * (This is to avoid getting unpredictable results from list_sort.)
1303 : */
1304 : static int
1305 2606 : append_total_cost_compare(const ListCell *a, const ListCell *b)
1306 : {
1307 2606 : Path *path1 = (Path *) lfirst(a);
1308 2606 : Path *path2 = (Path *) lfirst(b);
1309 : int cmp;
1310 :
1311 2606 : cmp = compare_path_costs(path1, path2, TOTAL_COST);
1312 2606 : if (cmp != 0)
1313 2380 : return -cmp;
1314 226 : return bms_compare(path1->parent->relids, path2->parent->relids);
1315 : }
1316 :
1317 : /*
1318 : * append_startup_cost_compare
1319 : * list_sort comparator for sorting append child paths
1320 : * by startup_cost descending
1321 : *
1322 : * For equal startup costs, we fall back to comparing total costs; if those
1323 : * are equal too, break ties using bms_compare on the paths' relids.
1324 : * (This is to avoid getting unpredictable results from list_sort.)
1325 : */
1326 : static int
1327 19410 : append_startup_cost_compare(const ListCell *a, const ListCell *b)
1328 : {
1329 19410 : Path *path1 = (Path *) lfirst(a);
1330 19410 : Path *path2 = (Path *) lfirst(b);
1331 : int cmp;
1332 :
1333 19410 : cmp = compare_path_costs(path1, path2, STARTUP_COST);
1334 19410 : if (cmp != 0)
1335 7682 : return -cmp;
1336 11728 : return bms_compare(path1->parent->relids, path2->parent->relids);
1337 : }
1338 :
1339 : /*
1340 : * create_merge_append_path
1341 : * Creates a path corresponding to a MergeAppend plan, returning the
1342 : * pathnode.
1343 : */
1344 : MergeAppendPath *
1345 2318 : create_merge_append_path(PlannerInfo *root,
1346 : RelOptInfo *rel,
1347 : List *subpaths,
1348 : List *pathkeys,
1349 : Relids required_outer,
1350 : List *partitioned_rels)
1351 : {
1352 2318 : MergeAppendPath *pathnode = makeNode(MergeAppendPath);
1353 : Cost input_startup_cost;
1354 : Cost input_total_cost;
1355 : ListCell *l;
1356 :
1357 2318 : pathnode->path.pathtype = T_MergeAppend;
1358 2318 : pathnode->path.parent = rel;
1359 2318 : pathnode->path.pathtarget = rel->reltarget;
1360 2318 : pathnode->path.param_info = get_appendrel_parampathinfo(rel,
1361 : required_outer);
1362 2318 : pathnode->path.parallel_aware = false;
1363 2318 : pathnode->path.parallel_safe = rel->consider_parallel;
1364 2318 : pathnode->path.parallel_workers = 0;
1365 2318 : pathnode->path.pathkeys = pathkeys;
1366 2318 : pathnode->partitioned_rels = list_copy(partitioned_rels);
1367 2318 : pathnode->subpaths = subpaths;
1368 :
1369 : /*
1370 : * Apply query-wide LIMIT if known and path is for sole base relation.
1371 : * (Handling this at this low level is a bit klugy.)
1372 : */
1373 2318 : if (bms_equal(rel->relids, root->all_baserels))
1374 1220 : pathnode->limit_tuples = root->limit_tuples;
1375 : else
1376 1098 : pathnode->limit_tuples = -1.0;
1377 :
1378 : /*
1379 : * Add up the sizes and costs of the input paths.
1380 : */
1381 2318 : pathnode->path.rows = 0;
1382 2318 : input_startup_cost = 0;
1383 2318 : input_total_cost = 0;
1384 8720 : foreach(l, subpaths)
1385 : {
1386 6402 : Path *subpath = (Path *) lfirst(l);
1387 :
1388 6402 : pathnode->path.rows += subpath->rows;
1389 11550 : pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
1390 5148 : subpath->parallel_safe;
1391 :
1392 6402 : if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
1393 : {
1394 : /* Subpath is adequately ordered, we won't need to sort it */
1395 6254 : input_startup_cost += subpath->startup_cost;
1396 6254 : input_total_cost += subpath->total_cost;
1397 : }
1398 : else
1399 : {
1400 : /* We'll need to insert a Sort node, so include cost for that */
1401 : Path sort_path; /* dummy for result of cost_sort */
1402 :
1403 444 : cost_sort(&sort_path,
1404 : root,
1405 : pathkeys,
1406 : subpath->total_cost,
1407 148 : subpath->parent->tuples,
1408 148 : subpath->pathtarget->width,
1409 : 0.0,
1410 : work_mem,
1411 : pathnode->limit_tuples);
1412 148 : input_startup_cost += sort_path.startup_cost;
1413 148 : input_total_cost += sort_path.total_cost;
1414 : }
1415 :
1416 : /* All child paths must have same parameterization */
1417 : Assert(bms_equal(PATH_REQ_OUTER(subpath), required_outer));
1418 : }
1419 :
1420 : /*
1421 : * Now we can compute total costs of the MergeAppend. If there's exactly
1422 : * one child path, the MergeAppend is a no-op and will be discarded later
1423 : * (in setrefs.c); otherwise we do the normal cost calculation.
1424 : */
1425 2318 : if (list_length(subpaths) == 1)
1426 : {
1427 86 : pathnode->path.startup_cost = input_startup_cost;
1428 86 : pathnode->path.total_cost = input_total_cost;
1429 : }
1430 : else
1431 2232 : cost_merge_append(&pathnode->path, root,
1432 : pathkeys, list_length(subpaths),
1433 : input_startup_cost, input_total_cost,
1434 : pathnode->path.rows);
1435 :
1436 2318 : return pathnode;
1437 : }
1438 :
1439 : /*
1440 : * create_group_result_path
1441 : * Creates a path representing a Result-and-nothing-else plan.
1442 : *
1443 : * This is only used for degenerate grouping cases, in which we know we
1444 : * need to produce one result row, possibly filtered by a HAVING qual.
1445 : */
1446 : GroupResultPath *
1447 117512 : create_group_result_path(PlannerInfo *root, RelOptInfo *rel,
1448 : PathTarget *target, List *havingqual)
1449 : {
1450 117512 : GroupResultPath *pathnode = makeNode(GroupResultPath);
1451 :
1452 117512 : pathnode->path.pathtype = T_Result;
1453 117512 : pathnode->path.parent = rel;
1454 117512 : pathnode->path.pathtarget = target;
1455 117512 : pathnode->path.param_info = NULL; /* there are no other rels... */
1456 117512 : pathnode->path.parallel_aware = false;
1457 117512 : pathnode->path.parallel_safe = rel->consider_parallel;
1458 117512 : pathnode->path.parallel_workers = 0;
1459 117512 : pathnode->path.pathkeys = NIL;
1460 117512 : pathnode->quals = havingqual;
1461 :
1462 : /*
1463 : * We can't quite use cost_resultscan() because the quals we want to
1464 : * account for are not baserestrict quals of the rel. Might as well just
1465 : * hack it here.
1466 : */
1467 117512 : pathnode->path.rows = 1;
1468 117512 : pathnode->path.startup_cost = target->cost.startup;
1469 235024 : pathnode->path.total_cost = target->cost.startup +
1470 117512 : cpu_tuple_cost + target->cost.per_tuple;
1471 :
1472 : /*
1473 : * Add cost of qual, if any --- but we ignore its selectivity, since our
1474 : * rowcount estimate should be 1 no matter what the qual is.
1475 : */
1476 117512 : if (havingqual)
1477 : {
1478 : QualCost qual_cost;
1479 :
1480 278 : cost_qual_eval(&qual_cost, havingqual, root);
1481 : /* havingqual is evaluated once at startup */
1482 278 : pathnode->path.startup_cost += qual_cost.startup + qual_cost.per_tuple;
1483 278 : pathnode->path.total_cost += qual_cost.startup + qual_cost.per_tuple;
1484 : }
1485 :
1486 117512 : return pathnode;
1487 : }
1488 :
1489 : /*
1490 : * create_material_path
1491 : * Creates a path corresponding to a Material plan, returning the
1492 : * pathnode.
1493 : */
1494 : MaterialPath *
1495 230826 : create_material_path(RelOptInfo *rel, Path *subpath)
1496 : {
1497 230826 : MaterialPath *pathnode = makeNode(MaterialPath);
1498 :
1499 : Assert(subpath->parent == rel);
1500 :
1501 230826 : pathnode->path.pathtype = T_Material;
1502 230826 : pathnode->path.parent = rel;
1503 230826 : pathnode->path.pathtarget = rel->reltarget;
1504 230826 : pathnode->path.param_info = subpath->param_info;
1505 230826 : pathnode->path.parallel_aware = false;
1506 435712 : pathnode->path.parallel_safe = rel->consider_parallel &&
1507 204886 : subpath->parallel_safe;
1508 230826 : pathnode->path.parallel_workers = subpath->parallel_workers;
1509 230826 : pathnode->path.pathkeys = subpath->pathkeys;
1510 :
1511 230826 : pathnode->subpath = subpath;
1512 :
1513 230826 : cost_material(&pathnode->path,
1514 : subpath->startup_cost,
1515 : subpath->total_cost,
1516 : subpath->rows,
1517 230826 : subpath->pathtarget->width);
1518 :
1519 230826 : return pathnode;
1520 : }
1521 :
1522 : /*
1523 : * create_unique_path
1524 : * Creates a path representing elimination of distinct rows from the
1525 : * input data. Distinct-ness is defined according to the needs of the
1526 : * semijoin represented by sjinfo. If it is not possible to identify
1527 : * how to make the data unique, NULL is returned.
1528 : *
1529 : * If used at all, this is likely to be called repeatedly on the same rel;
1530 : * and the input subpath should always be the same (the cheapest_total path
1531 : * for the rel). So we cache the result.
1532 : */
1533 : UniquePath *
1534 12646 : create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1535 : SpecialJoinInfo *sjinfo)
1536 : {
1537 : UniquePath *pathnode;
1538 : Path sort_path; /* dummy for result of cost_sort */
1539 : Path agg_path; /* dummy for result of cost_agg */
1540 : MemoryContext oldcontext;
1541 : int numCols;
1542 :
1543 : /* Caller made a mistake if subpath isn't cheapest_total ... */
1544 : Assert(subpath == rel->cheapest_total_path);
1545 : Assert(subpath->parent == rel);
1546 : /* ... or if SpecialJoinInfo is the wrong one */
1547 : Assert(sjinfo->jointype == JOIN_SEMI);
1548 : Assert(bms_equal(rel->relids, sjinfo->syn_righthand));
1549 :
1550 : /* If result already cached, return it */
1551 12646 : if (rel->cheapest_unique_path)
1552 10656 : return (UniquePath *) rel->cheapest_unique_path;
1553 :
1554 : /* If it's not possible to unique-ify, return NULL */
1555 1990 : if (!(sjinfo->semi_can_btree || sjinfo->semi_can_hash))
1556 62 : return NULL;
1557 :
1558 : /*
1559 : * When called during GEQO join planning, we are in a short-lived memory
1560 : * context. We must make sure that the path and any subsidiary data
1561 : * structures created for a baserel survive the GEQO cycle, else the
1562 : * baserel is trashed for future GEQO cycles. On the other hand, when we
1563 : * are creating those for a joinrel during GEQO, we don't want them to
1564 : * clutter the main planning context. Upshot is that the best solution is
1565 : * to explicitly allocate memory in the same context the given RelOptInfo
1566 : * is in.
1567 : */
1568 1928 : oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1569 :
1570 1928 : pathnode = makeNode(UniquePath);
1571 :
1572 1928 : pathnode->path.pathtype = T_Unique;
1573 1928 : pathnode->path.parent = rel;
1574 1928 : pathnode->path.pathtarget = rel->reltarget;
1575 1928 : pathnode->path.param_info = subpath->param_info;
1576 1928 : pathnode->path.parallel_aware = false;
1577 3696 : pathnode->path.parallel_safe = rel->consider_parallel &&
1578 1768 : subpath->parallel_safe;
1579 1928 : pathnode->path.parallel_workers = subpath->parallel_workers;
1580 :
1581 : /*
1582 : * Assume the output is unsorted, since we don't necessarily have pathkeys
1583 : * to represent it. (This might get overridden below.)
1584 : */
1585 1928 : pathnode->path.pathkeys = NIL;
1586 :
1587 1928 : pathnode->subpath = subpath;
1588 1928 : pathnode->in_operators = sjinfo->semi_operators;
1589 1928 : pathnode->uniq_exprs = sjinfo->semi_rhs_exprs;
1590 :
1591 : /*
1592 : * If the input is a relation and it has a unique index that proves the
1593 : * semi_rhs_exprs are unique, then we don't need to do anything. Note
1594 : * that relation_has_unique_index_for automatically considers restriction
1595 : * clauses for the rel, as well.
1596 : */
1597 2368 : if (rel->rtekind == RTE_RELATION && sjinfo->semi_can_btree &&
1598 440 : relation_has_unique_index_for(root, rel, NIL,
1599 : sjinfo->semi_rhs_exprs,
1600 : sjinfo->semi_operators))
1601 : {
1602 0 : pathnode->umethod = UNIQUE_PATH_NOOP;
1603 0 : pathnode->path.rows = rel->rows;
1604 0 : pathnode->path.startup_cost = subpath->startup_cost;
1605 0 : pathnode->path.total_cost = subpath->total_cost;
1606 0 : pathnode->path.pathkeys = subpath->pathkeys;
1607 :
1608 0 : rel->cheapest_unique_path = (Path *) pathnode;
1609 :
1610 0 : MemoryContextSwitchTo(oldcontext);
1611 :
1612 0 : return pathnode;
1613 : }
1614 :
1615 : /*
1616 : * If the input is a subquery whose output must be unique already, then we
1617 : * don't need to do anything. The test for uniqueness has to consider
1618 : * exactly which columns we are extracting; for example "SELECT DISTINCT
1619 : * x,y" doesn't guarantee that x alone is distinct. So we cannot check for
1620 : * this optimization unless semi_rhs_exprs consists only of simple Vars
1621 : * referencing subquery outputs. (Possibly we could do something with
1622 : * expressions in the subquery outputs, too, but for now keep it simple.)
1623 : */
1624 1928 : if (rel->rtekind == RTE_SUBQUERY)
1625 : {
1626 304 : RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
1627 :
1628 304 : if (query_supports_distinctness(rte->subquery))
1629 : {
1630 : List *sub_tlist_colnos;
1631 :
1632 280 : sub_tlist_colnos = translate_sub_tlist(sjinfo->semi_rhs_exprs,
1633 280 : rel->relid);
1634 :
1635 320 : if (sub_tlist_colnos &&
1636 40 : query_is_distinct_for(rte->subquery,
1637 : sub_tlist_colnos,
1638 : sjinfo->semi_operators))
1639 : {
1640 0 : pathnode->umethod = UNIQUE_PATH_NOOP;
1641 0 : pathnode->path.rows = rel->rows;
1642 0 : pathnode->path.startup_cost = subpath->startup_cost;
1643 0 : pathnode->path.total_cost = subpath->total_cost;
1644 0 : pathnode->path.pathkeys = subpath->pathkeys;
1645 :
1646 0 : rel->cheapest_unique_path = (Path *) pathnode;
1647 :
1648 0 : MemoryContextSwitchTo(oldcontext);
1649 :
1650 0 : return pathnode;
1651 : }
1652 : }
1653 : }
1654 :
1655 : /* Estimate number of output rows */
1656 1928 : pathnode->path.rows = estimate_num_groups(root,
1657 : sjinfo->semi_rhs_exprs,
1658 : rel->rows,
1659 : NULL);
1660 1928 : numCols = list_length(sjinfo->semi_rhs_exprs);
1661 :
1662 1928 : if (sjinfo->semi_can_btree)
1663 : {
1664 : /*
1665 : * Estimate cost for sort+unique implementation
1666 : */
1667 3856 : cost_sort(&sort_path, root, NIL,
1668 : subpath->total_cost,
1669 : rel->rows,
1670 1928 : subpath->pathtarget->width,
1671 : 0.0,
1672 : work_mem,
1673 : -1.0);
1674 :
1675 : /*
1676 : * Charge one cpu_operator_cost per comparison per input tuple. We
1677 : * assume all columns get compared at most of the tuples. (XXX
1678 : * probably this is an overestimate.) This should agree with
1679 : * create_upper_unique_path.
1680 : */
1681 1928 : sort_path.total_cost += cpu_operator_cost * rel->rows * numCols;
1682 : }
1683 :
1684 1928 : if (sjinfo->semi_can_hash)
1685 : {
1686 : /*
1687 : * Estimate the overhead per hashtable entry at 64 bytes (same as in
1688 : * planner.c).
1689 : */
1690 1928 : int hashentrysize = subpath->pathtarget->width + 64;
1691 :
1692 1928 : if (hashentrysize * pathnode->path.rows > work_mem * 1024L)
1693 : {
1694 : /*
1695 : * We should not try to hash. Hack the SpecialJoinInfo to
1696 : * remember this, in case we come through here again.
1697 : */
1698 0 : sjinfo->semi_can_hash = false;
1699 : }
1700 : else
1701 1928 : cost_agg(&agg_path, root,
1702 : AGG_HASHED, NULL,
1703 : numCols, pathnode->path.rows,
1704 : NIL,
1705 : subpath->startup_cost,
1706 : subpath->total_cost,
1707 : rel->rows,
1708 1928 : subpath->pathtarget->width);
1709 : }
1710 :
1711 1928 : if (sjinfo->semi_can_btree && sjinfo->semi_can_hash)
1712 : {
1713 3856 : if (agg_path.total_cost < sort_path.total_cost)
1714 1878 : pathnode->umethod = UNIQUE_PATH_HASH;
1715 : else
1716 50 : pathnode->umethod = UNIQUE_PATH_SORT;
1717 : }
1718 0 : else if (sjinfo->semi_can_btree)
1719 0 : pathnode->umethod = UNIQUE_PATH_SORT;
1720 0 : else if (sjinfo->semi_can_hash)
1721 0 : pathnode->umethod = UNIQUE_PATH_HASH;
1722 : else
1723 : {
1724 : /* we can get here only if we abandoned hashing above */
1725 0 : MemoryContextSwitchTo(oldcontext);
1726 0 : return NULL;
1727 : }
1728 :
1729 1928 : if (pathnode->umethod == UNIQUE_PATH_HASH)
1730 : {
1731 1878 : pathnode->path.startup_cost = agg_path.startup_cost;
1732 1878 : pathnode->path.total_cost = agg_path.total_cost;
1733 : }
1734 : else
1735 : {
1736 50 : pathnode->path.startup_cost = sort_path.startup_cost;
1737 50 : pathnode->path.total_cost = sort_path.total_cost;
1738 : }
1739 :
1740 1928 : rel->cheapest_unique_path = (Path *) pathnode;
1741 :
1742 1928 : MemoryContextSwitchTo(oldcontext);
1743 :
1744 1928 : return pathnode;
1745 : }
1746 :
1747 : /*
1748 : * create_gather_merge_path
1749 : *
1750 : * Creates a path corresponding to a gather merge scan, returning
1751 : * the pathnode.
1752 : */
1753 : GatherMergePath *
1754 3876 : create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1755 : PathTarget *target, List *pathkeys,
1756 : Relids required_outer, double *rows)
1757 : {
1758 3876 : GatherMergePath *pathnode = makeNode(GatherMergePath);
1759 3876 : Cost input_startup_cost = 0;
1760 3876 : Cost input_total_cost = 0;
1761 :
1762 : Assert(subpath->parallel_safe);
1763 : Assert(pathkeys);
1764 :
1765 3876 : pathnode->path.pathtype = T_GatherMerge;
1766 3876 : pathnode->path.parent = rel;
1767 3876 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1768 : required_outer);
1769 3876 : pathnode->path.parallel_aware = false;
1770 :
1771 3876 : pathnode->subpath = subpath;
1772 3876 : pathnode->num_workers = subpath->parallel_workers;
1773 3876 : pathnode->path.pathkeys = pathkeys;
1774 3876 : pathnode->path.pathtarget = target ? target : rel->reltarget;
1775 3876 : pathnode->path.rows += subpath->rows;
1776 :
1777 3876 : if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
1778 : {
1779 : /* Subpath is adequately ordered, we won't need to sort it */
1780 3876 : input_startup_cost += subpath->startup_cost;
1781 3876 : input_total_cost += subpath->total_cost;
1782 : }
1783 : else
1784 : {
1785 : /* We'll need to insert a Sort node, so include cost for that */
1786 : Path sort_path; /* dummy for result of cost_sort */
1787 :
1788 0 : cost_sort(&sort_path,
1789 : root,
1790 : pathkeys,
1791 : subpath->total_cost,
1792 : subpath->rows,
1793 0 : subpath->pathtarget->width,
1794 : 0.0,
1795 : work_mem,
1796 : -1);
1797 0 : input_startup_cost += sort_path.startup_cost;
1798 0 : input_total_cost += sort_path.total_cost;
1799 : }
1800 :
1801 3876 : cost_gather_merge(pathnode, root, rel, pathnode->path.param_info,
1802 : input_startup_cost, input_total_cost, rows);
1803 :
1804 3876 : return pathnode;
1805 : }
1806 :
1807 : /*
1808 : * translate_sub_tlist - get subquery column numbers represented by tlist
1809 : *
1810 : * The given targetlist usually contains only Vars referencing the given relid.
1811 : * Extract their varattnos (ie, the column numbers of the subquery) and return
1812 : * as an integer List.
1813 : *
1814 : * If any of the tlist items is not a simple Var, we cannot determine whether
1815 : * the subquery's uniqueness condition (if any) matches ours, so punt and
1816 : * return NIL.
1817 : */
1818 : static List *
1819 280 : translate_sub_tlist(List *tlist, int relid)
1820 : {
1821 280 : List *result = NIL;
1822 : ListCell *l;
1823 :
1824 320 : foreach(l, tlist)
1825 : {
1826 280 : Var *var = (Var *) lfirst(l);
1827 :
1828 280 : if (!var || !IsA(var, Var) ||
1829 40 : var->varno != relid)
1830 240 : return NIL; /* punt */
1831 :
1832 40 : result = lappend_int(result, var->varattno);
1833 : }
1834 40 : return result;
1835 : }
1836 :
1837 : /*
1838 : * create_gather_path
1839 : * Creates a path corresponding to a gather scan, returning the
1840 : * pathnode.
1841 : *
1842 : * 'rows' may optionally be set to override row estimates from other sources.
1843 : */
1844 : GatherPath *
1845 10778 : create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1846 : PathTarget *target, Relids required_outer, double *rows)
1847 : {
1848 10778 : GatherPath *pathnode = makeNode(GatherPath);
1849 :
1850 : Assert(subpath->parallel_safe);
1851 :
1852 10778 : pathnode->path.pathtype = T_Gather;
1853 10778 : pathnode->path.parent = rel;
1854 10778 : pathnode->path.pathtarget = target;
1855 10778 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1856 : required_outer);
1857 10778 : pathnode->path.parallel_aware = false;
1858 10778 : pathnode->path.parallel_safe = false;
1859 10778 : pathnode->path.parallel_workers = 0;
1860 10778 : pathnode->path.pathkeys = NIL; /* Gather has unordered result */
1861 :
1862 10778 : pathnode->subpath = subpath;
1863 10778 : pathnode->num_workers = subpath->parallel_workers;
1864 10778 : pathnode->single_copy = false;
1865 :
1866 10778 : if (pathnode->num_workers == 0)
1867 : {
1868 0 : pathnode->path.pathkeys = subpath->pathkeys;
1869 0 : pathnode->num_workers = 1;
1870 0 : pathnode->single_copy = true;
1871 : }
1872 :
1873 10778 : cost_gather(pathnode, root, rel, pathnode->path.param_info, rows);
1874 :
1875 10778 : return pathnode;
1876 : }
1877 :
1878 : /*
1879 : * create_subqueryscan_path
1880 : * Creates a path corresponding to a scan of a subquery,
1881 : * returning the pathnode.
1882 : */
1883 : SubqueryScanPath *
1884 9498 : create_subqueryscan_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1885 : List *pathkeys, Relids required_outer)
1886 : {
1887 9498 : SubqueryScanPath *pathnode = makeNode(SubqueryScanPath);
1888 :
1889 9498 : pathnode->path.pathtype = T_SubqueryScan;
1890 9498 : pathnode->path.parent = rel;
1891 9498 : pathnode->path.pathtarget = rel->reltarget;
1892 9498 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1893 : required_outer);
1894 9498 : pathnode->path.parallel_aware = false;
1895 14902 : pathnode->path.parallel_safe = rel->consider_parallel &&
1896 5404 : subpath->parallel_safe;
1897 9498 : pathnode->path.parallel_workers = subpath->parallel_workers;
1898 9498 : pathnode->path.pathkeys = pathkeys;
1899 9498 : pathnode->subpath = subpath;
1900 :
1901 9498 : cost_subqueryscan(pathnode, root, rel, pathnode->path.param_info);
1902 :
1903 9498 : return pathnode;
1904 : }
1905 :
1906 : /*
1907 : * create_functionscan_path
1908 : * Creates a path corresponding to a sequential scan of a function,
1909 : * returning the pathnode.
1910 : */
1911 : Path *
1912 30492 : create_functionscan_path(PlannerInfo *root, RelOptInfo *rel,
1913 : List *pathkeys, Relids required_outer)
1914 : {
1915 30492 : Path *pathnode = makeNode(Path);
1916 :
1917 30492 : pathnode->pathtype = T_FunctionScan;
1918 30492 : pathnode->parent = rel;
1919 30492 : pathnode->pathtarget = rel->reltarget;
1920 30492 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1921 : required_outer);
1922 30492 : pathnode->parallel_aware = false;
1923 30492 : pathnode->parallel_safe = rel->consider_parallel;
1924 30492 : pathnode->parallel_workers = 0;
1925 30492 : pathnode->pathkeys = pathkeys;
1926 :
1927 30492 : cost_functionscan(pathnode, root, rel, pathnode->param_info);
1928 :
1929 30492 : return pathnode;
1930 : }
1931 :
1932 : /*
1933 : * create_tablefuncscan_path
1934 : * Creates a path corresponding to a sequential scan of a table function,
1935 : * returning the pathnode.
1936 : */
1937 : Path *
1938 144 : create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel,
1939 : Relids required_outer)
1940 : {
1941 144 : Path *pathnode = makeNode(Path);
1942 :
1943 144 : pathnode->pathtype = T_TableFuncScan;
1944 144 : pathnode->parent = rel;
1945 144 : pathnode->pathtarget = rel->reltarget;
1946 144 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1947 : required_outer);
1948 144 : pathnode->parallel_aware = false;
1949 144 : pathnode->parallel_safe = rel->consider_parallel;
1950 144 : pathnode->parallel_workers = 0;
1951 144 : pathnode->pathkeys = NIL; /* result is always unordered */
1952 :
1953 144 : cost_tablefuncscan(pathnode, root, rel, pathnode->param_info);
1954 :
1955 144 : return pathnode;
1956 : }
1957 :
1958 : /*
1959 : * create_valuesscan_path
1960 : * Creates a path corresponding to a scan of a VALUES list,
1961 : * returning the pathnode.
1962 : */
1963 : Path *
1964 3940 : create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
1965 : Relids required_outer)
1966 : {
1967 3940 : Path *pathnode = makeNode(Path);
1968 :
1969 3940 : pathnode->pathtype = T_ValuesScan;
1970 3940 : pathnode->parent = rel;
1971 3940 : pathnode->pathtarget = rel->reltarget;
1972 3940 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1973 : required_outer);
1974 3940 : pathnode->parallel_aware = false;
1975 3940 : pathnode->parallel_safe = rel->consider_parallel;
1976 3940 : pathnode->parallel_workers = 0;
1977 3940 : pathnode->pathkeys = NIL; /* result is always unordered */
1978 :
1979 3940 : cost_valuesscan(pathnode, root, rel, pathnode->param_info);
1980 :
1981 3940 : return pathnode;
1982 : }
1983 :
1984 : /*
1985 : * create_ctescan_path
1986 : * Creates a path corresponding to a scan of a non-self-reference CTE,
1987 : * returning the pathnode.
1988 : */
1989 : Path *
1990 912 : create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
1991 : {
1992 912 : Path *pathnode = makeNode(Path);
1993 :
1994 912 : pathnode->pathtype = T_CteScan;
1995 912 : pathnode->parent = rel;
1996 912 : pathnode->pathtarget = rel->reltarget;
1997 912 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1998 : required_outer);
1999 912 : pathnode->parallel_aware = false;
2000 912 : pathnode->parallel_safe = rel->consider_parallel;
2001 912 : pathnode->parallel_workers = 0;
2002 912 : pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */
2003 :
2004 912 : cost_ctescan(pathnode, root, rel, pathnode->param_info);
2005 :
2006 912 : return pathnode;
2007 : }
2008 :
2009 : /*
2010 : * create_namedtuplestorescan_path
2011 : * Creates a path corresponding to a scan of a named tuplestore, returning
2012 : * the pathnode.
2013 : */
2014 : Path *
2015 260 : create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel,
2016 : Relids required_outer)
2017 : {
2018 260 : Path *pathnode = makeNode(Path);
2019 :
2020 260 : pathnode->pathtype = T_NamedTuplestoreScan;
2021 260 : pathnode->parent = rel;
2022 260 : pathnode->pathtarget = rel->reltarget;
2023 260 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
2024 : required_outer);
2025 260 : pathnode->parallel_aware = false;
2026 260 : pathnode->parallel_safe = rel->consider_parallel;
2027 260 : pathnode->parallel_workers = 0;
2028 260 : pathnode->pathkeys = NIL; /* result is always unordered */
2029 :
2030 260 : cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info);
2031 :
2032 260 : return pathnode;
2033 : }
2034 :
2035 : /*
2036 : * create_resultscan_path
2037 : * Creates a path corresponding to a scan of an RTE_RESULT relation,
2038 : * returning the pathnode.
2039 : */
2040 : Path *
2041 702 : create_resultscan_path(PlannerInfo *root, RelOptInfo *rel,
2042 : Relids required_outer)
2043 : {
2044 702 : Path *pathnode = makeNode(Path);
2045 :
2046 702 : pathnode->pathtype = T_Result;
2047 702 : pathnode->parent = rel;
2048 702 : pathnode->pathtarget = rel->reltarget;
2049 702 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
2050 : required_outer);
2051 702 : pathnode->parallel_aware = false;
2052 702 : pathnode->parallel_safe = rel->consider_parallel;
2053 702 : pathnode->parallel_workers = 0;
2054 702 : pathnode->pathkeys = NIL; /* result is always unordered */
2055 :
2056 702 : cost_resultscan(pathnode, root, rel, pathnode->param_info);
2057 :
2058 702 : return pathnode;
2059 : }
2060 :
2061 : /*
2062 : * create_worktablescan_path
2063 : * Creates a path corresponding to a scan of a self-reference CTE,
2064 : * returning the pathnode.
2065 : */
2066 : Path *
2067 332 : create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel,
2068 : Relids required_outer)
2069 : {
2070 332 : Path *pathnode = makeNode(Path);
2071 :
2072 332 : pathnode->pathtype = T_WorkTableScan;
2073 332 : pathnode->parent = rel;
2074 332 : pathnode->pathtarget = rel->reltarget;
2075 332 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
2076 : required_outer);
2077 332 : pathnode->parallel_aware = false;
2078 332 : pathnode->parallel_safe = rel->consider_parallel;
2079 332 : pathnode->parallel_workers = 0;
2080 332 : pathnode->pathkeys = NIL; /* result is always unordered */
2081 :
2082 : /* Cost is the same as for a regular CTE scan */
2083 332 : cost_ctescan(pathnode, root, rel, pathnode->param_info);
2084 :
2085 332 : return pathnode;
2086 : }
2087 :
2088 : /*
2089 : * create_foreignscan_path
2090 : * Creates a path corresponding to a scan of a foreign base table,
2091 : * returning the pathnode.
2092 : *
2093 : * This function is never called from core Postgres; rather, it's expected
2094 : * to be called by the GetForeignPaths function of a foreign data wrapper.
2095 : * We make the FDW supply all fields of the path, since we do not have any way
2096 : * to calculate them in core. However, there is a usually-sane default for
2097 : * the pathtarget (rel->reltarget), so we let a NULL for "target" select that.
2098 : */
2099 : ForeignPath *
2100 2754 : create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel,
2101 : PathTarget *target,
2102 : double rows, Cost startup_cost, Cost total_cost,
2103 : List *pathkeys,
2104 : Relids required_outer,
2105 : Path *fdw_outerpath,
2106 : List *fdw_private)
2107 : {
2108 2754 : ForeignPath *pathnode = makeNode(ForeignPath);
2109 :
2110 : /* Historically some FDWs were confused about when to use this */
2111 : Assert(IS_SIMPLE_REL(rel));
2112 :
2113 2754 : pathnode->path.pathtype = T_ForeignScan;
2114 2754 : pathnode->path.parent = rel;
2115 2754 : pathnode->path.pathtarget = target ? target : rel->reltarget;
2116 2754 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
2117 : required_outer);
2118 2754 : pathnode->path.parallel_aware = false;
2119 2754 : pathnode->path.parallel_safe = rel->consider_parallel;
2120 2754 : pathnode->path.parallel_workers = 0;
2121 2754 : pathnode->path.rows = rows;
2122 2754 : pathnode->path.startup_cost = startup_cost;
2123 2754 : pathnode->path.total_cost = total_cost;
2124 2754 : pathnode->path.pathkeys = pathkeys;
2125 :
2126 2754 : pathnode->fdw_outerpath = fdw_outerpath;
2127 2754 : pathnode->fdw_private = fdw_private;
2128 :
2129 2754 : return pathnode;
2130 : }
2131 :
2132 : /*
2133 : * create_foreign_join_path
2134 : * Creates a path corresponding to a scan of a foreign join,
2135 : * returning the pathnode.
2136 : *
2137 : * This function is never called from core Postgres; rather, it's expected
2138 : * to be called by the GetForeignJoinPaths function of a foreign data wrapper.
2139 : * We make the FDW supply all fields of the path, since we do not have any way
2140 : * to calculate them in core. However, there is a usually-sane default for
2141 : * the pathtarget (rel->reltarget), so we let a NULL for "target" select that.
2142 : */
2143 : ForeignPath *
2144 702 : create_foreign_join_path(PlannerInfo *root, RelOptInfo *rel,
2145 : PathTarget *target,
2146 : double rows, Cost startup_cost, Cost total_cost,
2147 : List *pathkeys,
2148 : Relids required_outer,
2149 : Path *fdw_outerpath,
2150 : List *fdw_private)
2151 : {
2152 702 : ForeignPath *pathnode = makeNode(ForeignPath);
2153 :
2154 : /*
2155 : * We should use get_joinrel_parampathinfo to handle parameterized paths,
2156 : * but the API of this function doesn't support it, and existing
2157 : * extensions aren't yet trying to build such paths anyway. For the
2158 : * moment just throw an error if someone tries it; eventually we should
2159 : * revisit this.
2160 : */
2161 702 : if (!bms_is_empty(required_outer) || !bms_is_empty(rel->lateral_relids))
2162 0 : elog(ERROR, "parameterized foreign joins are not supported yet");
2163 :
2164 702 : pathnode->path.pathtype = T_ForeignScan;
2165 702 : pathnode->path.parent = rel;
2166 702 : pathnode->path.pathtarget = target ? target : rel->reltarget;
2167 702 : pathnode->path.param_info = NULL; /* XXX see above */
2168 702 : pathnode->path.parallel_aware = false;
2169 702 : pathnode->path.parallel_safe = rel->consider_parallel;
2170 702 : pathnode->path.parallel_workers = 0;
2171 702 : pathnode->path.rows = rows;
2172 702 : pathnode->path.startup_cost = startup_cost;
2173 702 : pathnode->path.total_cost = total_cost;
2174 702 : pathnode->path.pathkeys = pathkeys;
2175 :
2176 702 : pathnode->fdw_outerpath = fdw_outerpath;
2177 702 : pathnode->fdw_private = fdw_private;
2178 :
2179 702 : return pathnode;
2180 : }
2181 :
2182 : /*
2183 : * create_foreign_upper_path
2184 : * Creates a path corresponding to an upper relation that's computed
2185 : * directly by an FDW, returning the pathnode.
2186 : *
2187 : * This function is never called from core Postgres; rather, it's expected to
2188 : * be called by the GetForeignUpperPaths function of a foreign data wrapper.
2189 : * We make the FDW supply all fields of the path, since we do not have any way
2190 : * to calculate them in core. However, there is a usually-sane default for
2191 : * the pathtarget (rel->reltarget), so we let a NULL for "target" select that.
2192 : */
2193 : ForeignPath *
2194 466 : create_foreign_upper_path(PlannerInfo *root, RelOptInfo *rel,
2195 : PathTarget *target,
2196 : double rows, Cost startup_cost, Cost total_cost,
2197 : List *pathkeys,
2198 : Path *fdw_outerpath,
2199 : List *fdw_private)
2200 : {
2201 466 : ForeignPath *pathnode = makeNode(ForeignPath);
2202 :
2203 : /*
2204 : * Upper relations should never have any lateral references, since joining
2205 : * is complete.
2206 : */
2207 : Assert(bms_is_empty(rel->lateral_relids));
2208 :
2209 466 : pathnode->path.pathtype = T_ForeignScan;
2210 466 : pathnode->path.parent = rel;
2211 466 : pathnode->path.pathtarget = target ? target : rel->reltarget;
2212 466 : pathnode->path.param_info = NULL;
2213 466 : pathnode->path.parallel_aware = false;
2214 466 : pathnode->path.parallel_safe = rel->consider_parallel;
2215 466 : pathnode->path.parallel_workers = 0;
2216 466 : pathnode->path.rows = rows;
2217 466 : pathnode->path.startup_cost = startup_cost;
2218 466 : pathnode->path.total_cost = total_cost;
2219 466 : pathnode->path.pathkeys = pathkeys;
2220 :
2221 466 : pathnode->fdw_outerpath = fdw_outerpath;
2222 466 : pathnode->fdw_private = fdw_private;
2223 :
2224 466 : return pathnode;
2225 : }
2226 :
2227 : /*
2228 : * calc_nestloop_required_outer
2229 : * Compute the required_outer set for a nestloop join path
2230 : *
2231 : * Note: result must not share storage with either input
2232 : */
2233 : Relids
2234 1181674 : calc_nestloop_required_outer(Relids outerrelids,
2235 : Relids outer_paramrels,
2236 : Relids innerrelids,
2237 : Relids inner_paramrels)
2238 : {
2239 : Relids required_outer;
2240 :
2241 : /* inner_path can require rels from outer path, but not vice versa */
2242 : Assert(!bms_overlap(outer_paramrels, innerrelids));
2243 : /* easy case if inner path is not parameterized */
2244 1181674 : if (!inner_paramrels)
2245 910750 : return bms_copy(outer_paramrels);
2246 : /* else, form the union ... */
2247 270924 : required_outer = bms_union(outer_paramrels, inner_paramrels);
2248 : /* ... and remove any mention of now-satisfied outer rels */
2249 270924 : required_outer = bms_del_members(required_outer,
2250 : outerrelids);
2251 : /* maintain invariant that required_outer is exactly NULL if empty */
2252 270924 : if (bms_is_empty(required_outer))
2253 : {
2254 223680 : bms_free(required_outer);
2255 223680 : required_outer = NULL;
2256 : }
2257 270924 : return required_outer;
2258 : }
2259 :
2260 : /*
2261 : * calc_non_nestloop_required_outer
2262 : * Compute the required_outer set for a merge or hash join path
2263 : *
2264 : * Note: result must not share storage with either input
2265 : */
2266 : Relids
2267 846848 : calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
2268 : {
2269 846848 : Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
2270 846848 : Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
2271 : Relids required_outer;
2272 :
2273 : /* neither path can require rels from the other */
2274 : Assert(!bms_overlap(outer_paramrels, inner_path->parent->relids));
2275 : Assert(!bms_overlap(inner_paramrels, outer_path->parent->relids));
2276 : /* form the union ... */
2277 846848 : required_outer = bms_union(outer_paramrels, inner_paramrels);
2278 : /* we do not need an explicit test for empty; bms_union gets it right */
2279 846848 : return required_outer;
2280 : }
2281 :
2282 : /*
2283 : * create_nestloop_path
2284 : * Creates a pathnode corresponding to a nestloop join between two
2285 : * relations.
2286 : *
2287 : * 'joinrel' is the join relation.
2288 : * 'jointype' is the type of join required
2289 : * 'workspace' is the result from initial_cost_nestloop
2290 : * 'extra' contains various information about the join
2291 : * 'outer_path' is the outer path
2292 : * 'inner_path' is the inner path
2293 : * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
2294 : * 'pathkeys' are the path keys of the new join path
2295 : * 'required_outer' is the set of required outer rels
2296 : *
2297 : * Returns the resulting path node.
2298 : */
2299 : NestPath *
2300 625748 : create_nestloop_path(PlannerInfo *root,
2301 : RelOptInfo *joinrel,
2302 : JoinType jointype,
2303 : JoinCostWorkspace *workspace,
2304 : JoinPathExtraData *extra,
2305 : Path *outer_path,
2306 : Path *inner_path,
2307 : List *restrict_clauses,
2308 : List *pathkeys,
2309 : Relids required_outer)
2310 : {
2311 625748 : NestPath *pathnode = makeNode(NestPath);
2312 625748 : Relids inner_req_outer = PATH_REQ_OUTER(inner_path);
2313 :
2314 : /*
2315 : * If the inner path is parameterized by the outer, we must drop any
2316 : * restrict_clauses that are due to be moved into the inner path. We have
2317 : * to do this now, rather than postpone the work till createplan time,
2318 : * because the restrict_clauses list can affect the size and cost
2319 : * estimates for this path.
2320 : */
2321 625748 : if (bms_overlap(inner_req_outer, outer_path->parent->relids))
2322 : {
2323 121070 : Relids inner_and_outer = bms_union(inner_path->parent->relids,
2324 : inner_req_outer);
2325 121070 : List *jclauses = NIL;
2326 : ListCell *lc;
2327 :
2328 251814 : foreach(lc, restrict_clauses)
2329 : {
2330 130744 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2331 :
2332 130744 : if (!join_clause_is_movable_into(rinfo,
2333 130744 : inner_path->parent->relids,
2334 : inner_and_outer))
2335 8046 : jclauses = lappend(jclauses, rinfo);
2336 : }
2337 121070 : restrict_clauses = jclauses;
2338 : }
2339 :
2340 625748 : pathnode->path.pathtype = T_NestLoop;
2341 625748 : pathnode->path.parent = joinrel;
2342 625748 : pathnode->path.pathtarget = joinrel->reltarget;
2343 625748 : pathnode->path.param_info =
2344 625748 : get_joinrel_parampathinfo(root,
2345 : joinrel,
2346 : outer_path,
2347 : inner_path,
2348 : extra->sjinfo,
2349 : required_outer,
2350 : &restrict_clauses);
2351 625748 : pathnode->path.parallel_aware = false;
2352 1811694 : pathnode->path.parallel_safe = joinrel->consider_parallel &&
2353 625748 : outer_path->parallel_safe && inner_path->parallel_safe;
2354 : /* This is a foolish way to estimate parallel_workers, but for now... */
2355 625748 : pathnode->path.parallel_workers = outer_path->parallel_workers;
2356 625748 : pathnode->path.pathkeys = pathkeys;
2357 625748 : pathnode->jointype = jointype;
2358 625748 : pathnode->inner_unique = extra->inner_unique;
2359 625748 : pathnode->outerjoinpath = outer_path;
2360 625748 : pathnode->innerjoinpath = inner_path;
2361 625748 : pathnode->joinrestrictinfo = restrict_clauses;
2362 :
2363 625748 : final_cost_nestloop(root, pathnode, workspace, extra);
2364 :
2365 625748 : return pathnode;
2366 : }
2367 :
2368 : /*
2369 : * create_mergejoin_path
2370 : * Creates a pathnode corresponding to a mergejoin join between
2371 : * two relations
2372 : *
2373 : * 'joinrel' is the join relation
2374 : * 'jointype' is the type of join required
2375 : * 'workspace' is the result from initial_cost_mergejoin
2376 : * 'extra' contains various information about the join
2377 : * 'outer_path' is the outer path
2378 : * 'inner_path' is the inner path
2379 : * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
2380 : * 'pathkeys' are the path keys of the new join path
2381 : * 'required_outer' is the set of required outer rels
2382 : * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
2383 : * (this should be a subset of the restrict_clauses list)
2384 : * 'outersortkeys' are the sort varkeys for the outer relation
2385 : * 'innersortkeys' are the sort varkeys for the inner relation
2386 : */
2387 : MergePath *
2388 135668 : create_mergejoin_path(PlannerInfo *root,
2389 : RelOptInfo *joinrel,
2390 : JoinType jointype,
2391 : JoinCostWorkspace *workspace,
2392 : JoinPathExtraData *extra,
2393 : Path *outer_path,
2394 : Path *inner_path,
2395 : List *restrict_clauses,
2396 : List *pathkeys,
2397 : Relids required_outer,
2398 : List *mergeclauses,
2399 : List *outersortkeys,
2400 : List *innersortkeys)
2401 : {
2402 135668 : MergePath *pathnode = makeNode(MergePath);
2403 :
2404 135668 : pathnode->jpath.path.pathtype = T_MergeJoin;
2405 135668 : pathnode->jpath.path.parent = joinrel;
2406 135668 : pathnode->jpath.path.pathtarget = joinrel->reltarget;
2407 135668 : pathnode->jpath.path.param_info =
2408 135668 : get_joinrel_parampathinfo(root,
2409 : joinrel,
2410 : outer_path,
2411 : inner_path,
2412 : extra->sjinfo,
2413 : required_outer,
2414 : &restrict_clauses);
2415 135668 : pathnode->jpath.path.parallel_aware = false;
2416 385556 : pathnode->jpath.path.parallel_safe = joinrel->consider_parallel &&
2417 135668 : outer_path->parallel_safe && inner_path->parallel_safe;
2418 : /* This is a foolish way to estimate parallel_workers, but for now... */
2419 135668 : pathnode->jpath.path.parallel_workers = outer_path->parallel_workers;
2420 135668 : pathnode->jpath.path.pathkeys = pathkeys;
2421 135668 : pathnode->jpath.jointype = jointype;
2422 135668 : pathnode->jpath.inner_unique = extra->inner_unique;
2423 135668 : pathnode->jpath.outerjoinpath = outer_path;
2424 135668 : pathnode->jpath.innerjoinpath = inner_path;
2425 135668 : pathnode->jpath.joinrestrictinfo = restrict_clauses;
2426 135668 : pathnode->path_mergeclauses = mergeclauses;
2427 135668 : pathnode->outersortkeys = outersortkeys;
2428 135668 : pathnode->innersortkeys = innersortkeys;
2429 : /* pathnode->skip_mark_restore will be set by final_cost_mergejoin */
2430 : /* pathnode->materialize_inner will be set by final_cost_mergejoin */
2431 :
2432 135668 : final_cost_mergejoin(root, pathnode, workspace, extra);
2433 :
2434 135668 : return pathnode;
2435 : }
2436 :
2437 : /*
2438 : * create_hashjoin_path
2439 : * Creates a pathnode corresponding to a hash join between two relations.
2440 : *
2441 : * 'joinrel' is the join relation
2442 : * 'jointype' is the type of join required
2443 : * 'workspace' is the result from initial_cost_hashjoin
2444 : * 'extra' contains various information about the join
2445 : * 'outer_path' is the cheapest outer path
2446 : * 'inner_path' is the cheapest inner path
2447 : * 'parallel_hash' to select Parallel Hash of inner path (shared hash table)
2448 : * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
2449 : * 'required_outer' is the set of required outer rels
2450 : * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
2451 : * (this should be a subset of the restrict_clauses list)
2452 : */
2453 : HashPath *
2454 149046 : create_hashjoin_path(PlannerInfo *root,
2455 : RelOptInfo *joinrel,
2456 : JoinType jointype,
2457 : JoinCostWorkspace *workspace,
2458 : JoinPathExtraData *extra,
2459 : Path *outer_path,
2460 : Path *inner_path,
2461 : bool parallel_hash,
2462 : List *restrict_clauses,
2463 : Relids required_outer,
2464 : List *hashclauses)
2465 : {
2466 149046 : HashPath *pathnode = makeNode(HashPath);
2467 :
2468 149046 : pathnode->jpath.path.pathtype = T_HashJoin;
2469 149046 : pathnode->jpath.path.parent = joinrel;
2470 149046 : pathnode->jpath.path.pathtarget = joinrel->reltarget;
2471 149046 : pathnode->jpath.path.param_info =
2472 149046 : get_joinrel_parampathinfo(root,
2473 : joinrel,
2474 : outer_path,
2475 : inner_path,
2476 : extra->sjinfo,
2477 : required_outer,
2478 : &restrict_clauses);
2479 149046 : pathnode->jpath.path.parallel_aware =
2480 149046 : joinrel->consider_parallel && parallel_hash;
2481 422740 : pathnode->jpath.path.parallel_safe = joinrel->consider_parallel &&
2482 149046 : outer_path->parallel_safe && inner_path->parallel_safe;
2483 : /* This is a foolish way to estimate parallel_workers, but for now... */
2484 149046 : pathnode->jpath.path.parallel_workers = outer_path->parallel_workers;
2485 :
2486 : /*
2487 : * A hashjoin never has pathkeys, since its output ordering is
2488 : * unpredictable due to possible batching. XXX If the inner relation is
2489 : * small enough, we could instruct the executor that it must not batch,
2490 : * and then we could assume that the output inherits the outer relation's
2491 : * ordering, which might save a sort step. However there is considerable
2492 : * downside if our estimate of the inner relation size is badly off. For
2493 : * the moment we don't risk it. (Note also that if we wanted to take this
2494 : * seriously, joinpath.c would have to consider many more paths for the
2495 : * outer rel than it does now.)
2496 : */
2497 149046 : pathnode->jpath.path.pathkeys = NIL;
2498 149046 : pathnode->jpath.jointype = jointype;
2499 149046 : pathnode->jpath.inner_unique = extra->inner_unique;
2500 149046 : pathnode->jpath.outerjoinpath = outer_path;
2501 149046 : pathnode->jpath.innerjoinpath = inner_path;
2502 149046 : pathnode->jpath.joinrestrictinfo = restrict_clauses;
2503 149046 : pathnode->path_hashclauses = hashclauses;
2504 : /* final_cost_hashjoin will fill in pathnode->num_batches */
2505 :
2506 149046 : final_cost_hashjoin(root, pathnode, workspace, extra);
2507 :
2508 149046 : return pathnode;
2509 : }
2510 :
2511 : /*
2512 : * create_projection_path
2513 : * Creates a pathnode that represents performing a projection.
2514 : *
2515 : * 'rel' is the parent relation associated with the result
2516 : * 'subpath' is the path representing the source of data
2517 : * 'target' is the PathTarget to be computed
2518 : */
2519 : ProjectionPath *
2520 243242 : create_projection_path(PlannerInfo *root,
2521 : RelOptInfo *rel,
2522 : Path *subpath,
2523 : PathTarget *target)
2524 : {
2525 243242 : ProjectionPath *pathnode = makeNode(ProjectionPath);
2526 243242 : PathTarget *oldtarget = subpath->pathtarget;
2527 :
2528 243242 : pathnode->path.pathtype = T_Result;
2529 243242 : pathnode->path.parent = rel;
2530 243242 : pathnode->path.pathtarget = target;
2531 : /* For now, assume we are above any joins, so no parameterization */
2532 243242 : pathnode->path.param_info = NULL;
2533 243242 : pathnode->path.parallel_aware = false;
2534 523462 : pathnode->path.parallel_safe = rel->consider_parallel &&
2535 279500 : subpath->parallel_safe &&
2536 36258 : is_parallel_safe(root, (Node *) target->exprs);
2537 243242 : pathnode->path.parallel_workers = subpath->parallel_workers;
2538 : /* Projection does not change the sort order */
2539 243242 : pathnode->path.pathkeys = subpath->pathkeys;
2540 :
2541 243242 : pathnode->subpath = subpath;
2542 :
2543 : /*
2544 : * We might not need a separate Result node. If the input plan node type
2545 : * can project, we can just tell it to project something else. Or, if it
2546 : * can't project but the desired target has the same expression list as
2547 : * what the input will produce anyway, we can still give it the desired
2548 : * tlist (possibly changing its ressortgroupref labels, but nothing else).
2549 : * Note: in the latter case, create_projection_plan has to recheck our
2550 : * conclusion; see comments therein.
2551 : */
2552 253162 : if (is_projection_capable_path(subpath) ||
2553 9920 : equal(oldtarget->exprs, target->exprs))
2554 : {
2555 : /* No separate Result node needed */
2556 242044 : pathnode->dummypp = true;
2557 :
2558 : /*
2559 : * Set cost of plan as subpath's cost, adjusted for tlist replacement.
2560 : */
2561 242044 : pathnode->path.rows = subpath->rows;
2562 484088 : pathnode->path.startup_cost = subpath->startup_cost +
2563 242044 : (target->cost.startup - oldtarget->cost.startup);
2564 726132 : pathnode->path.total_cost = subpath->total_cost +
2565 484088 : (target->cost.startup - oldtarget->cost.startup) +
2566 242044 : (target->cost.per_tuple - oldtarget->cost.per_tuple) * subpath->rows;
2567 : }
2568 : else
2569 : {
2570 : /* We really do need the Result node */
2571 1198 : pathnode->dummypp = false;
2572 :
2573 : /*
2574 : * The Result node's cost is cpu_tuple_cost per row, plus the cost of
2575 : * evaluating the tlist. There is no qual to worry about.
2576 : */
2577 1198 : pathnode->path.rows = subpath->rows;
2578 2396 : pathnode->path.startup_cost = subpath->startup_cost +
2579 1198 : target->cost.startup;
2580 3594 : pathnode->path.total_cost = subpath->total_cost +
2581 2396 : target->cost.startup +
2582 1198 : (cpu_tuple_cost + target->cost.per_tuple) * subpath->rows;
2583 : }
2584 :
2585 243242 : return pathnode;
2586 : }
2587 :
2588 : /*
2589 : * apply_projection_to_path
2590 : * Add a projection step, or just apply the target directly to given path.
2591 : *
2592 : * This has the same net effect as create_projection_path(), except that if
2593 : * a separate Result plan node isn't needed, we just replace the given path's
2594 : * pathtarget with the desired one. This must be used only when the caller
2595 : * knows that the given path isn't referenced elsewhere and so can be modified
2596 : * in-place.
2597 : *
2598 : * If the input path is a GatherPath or GatherMergePath, we try to push the
2599 : * new target down to its input as well; this is a yet more invasive
2600 : * modification of the input path, which create_projection_path() can't do.
2601 : *
2602 : * Note that we mustn't change the source path's parent link; so when it is
2603 : * add_path'd to "rel" things will be a bit inconsistent. So far that has
2604 : * not caused any trouble.
2605 : *
2606 : * 'rel' is the parent relation associated with the result
2607 : * 'path' is the path representing the source of data
2608 : * 'target' is the PathTarget to be computed
2609 : */
2610 : Path *
2611 16556 : apply_projection_to_path(PlannerInfo *root,
2612 : RelOptInfo *rel,
2613 : Path *path,
2614 : PathTarget *target)
2615 : {
2616 : QualCost oldcost;
2617 :
2618 : /*
2619 : * If given path can't project, we might need a Result node, so make a
2620 : * separate ProjectionPath.
2621 : */
2622 16556 : if (!is_projection_capable_path(path))
2623 8064 : return (Path *) create_projection_path(root, rel, path, target);
2624 :
2625 : /*
2626 : * We can just jam the desired tlist into the existing path, being sure to
2627 : * update its cost estimates appropriately.
2628 : */
2629 8492 : oldcost = path->pathtarget->cost;
2630 8492 : path->pathtarget = target;
2631 :
2632 8492 : path->startup_cost += target->cost.startup - oldcost.startup;
2633 16984 : path->total_cost += target->cost.startup - oldcost.startup +
2634 8492 : (target->cost.per_tuple - oldcost.per_tuple) * path->rows;
2635 :
2636 : /*
2637 : * If the path happens to be a Gather or GatherMerge path, we'd like to
2638 : * arrange for the subpath to return the required target list so that
2639 : * workers can help project. But if there is something that is not
2640 : * parallel-safe in the target expressions, then we can't.
2641 : */
2642 9950 : if ((IsA(path, GatherPath) || IsA(path, GatherMergePath)) &&
2643 1458 : is_parallel_safe(root, (Node *) target->exprs))
2644 : {
2645 : /*
2646 : * We always use create_projection_path here, even if the subpath is
2647 : * projection-capable, so as to avoid modifying the subpath in place.
2648 : * It seems unlikely at present that there could be any other
2649 : * references to the subpath, but better safe than sorry.
2650 : *
2651 : * Note that we don't change the parallel path's cost estimates; it
2652 : * might be appropriate to do so, to reflect the fact that the bulk of
2653 : * the target evaluation will happen in workers.
2654 : */
2655 2916 : if (IsA(path, GatherPath))
2656 : {
2657 0 : GatherPath *gpath = (GatherPath *) path;
2658 :
2659 0 : gpath->subpath = (Path *)
2660 0 : create_projection_path(root,
2661 0 : gpath->subpath->parent,
2662 : gpath->subpath,
2663 : target);
2664 : }
2665 : else
2666 : {
2667 1458 : GatherMergePath *gmpath = (GatherMergePath *) path;
2668 :
2669 1458 : gmpath->subpath = (Path *)
2670 2916 : create_projection_path(root,
2671 1458 : gmpath->subpath->parent,
2672 : gmpath->subpath,
2673 : target);
2674 : }
2675 : }
2676 7034 : else if (path->parallel_safe &&
2677 2780 : !is_parallel_safe(root, (Node *) target->exprs))
2678 : {
2679 : /*
2680 : * We're inserting a parallel-restricted target list into a path
2681 : * currently marked parallel-safe, so we have to mark it as no longer
2682 : * safe.
2683 : */
2684 8 : path->parallel_safe = false;
2685 : }
2686 :
2687 8492 : return path;
2688 : }
2689 :
2690 : /*
2691 : * create_set_projection_path
2692 : * Creates a pathnode that represents performing a projection that
2693 : * includes set-returning functions.
2694 : *
2695 : * 'rel' is the parent relation associated with the result
2696 : * 'subpath' is the path representing the source of data
2697 : * 'target' is the PathTarget to be computed
2698 : */
2699 : ProjectSetPath *
2700 3956 : create_set_projection_path(PlannerInfo *root,
2701 : RelOptInfo *rel,
2702 : Path *subpath,
2703 : PathTarget *target)
2704 : {
2705 3956 : ProjectSetPath *pathnode = makeNode(ProjectSetPath);
2706 : double tlist_rows;
2707 : ListCell *lc;
2708 :
2709 3956 : pathnode->path.pathtype = T_ProjectSet;
2710 3956 : pathnode->path.parent = rel;
2711 3956 : pathnode->path.pathtarget = target;
2712 : /* For now, assume we are above any joins, so no parameterization */
2713 3956 : pathnode->path.param_info = NULL;
2714 3956 : pathnode->path.parallel_aware = false;
2715 8370 : pathnode->path.parallel_safe = rel->consider_parallel &&
2716 4394 : subpath->parallel_safe &&
2717 438 : is_parallel_safe(root, (Node *) target->exprs);
2718 3956 : pathnode->path.parallel_workers = subpath->parallel_workers;
2719 : /* Projection does not change the sort order XXX? */
2720 3956 : pathnode->path.pathkeys = subpath->pathkeys;
2721 :
2722 3956 : pathnode->subpath = subpath;
2723 :
2724 : /*
2725 : * Estimate number of rows produced by SRFs for each row of input; if
2726 : * there's more than one in this node, use the maximum.
2727 : */
2728 3956 : tlist_rows = 1;
2729 9098 : foreach(lc, target->exprs)
2730 : {
2731 5142 : Node *node = (Node *) lfirst(lc);
2732 : double itemrows;
2733 :
2734 5142 : itemrows = expression_returns_set_rows(root, node);
2735 5142 : if (tlist_rows < itemrows)
2736 3826 : tlist_rows = itemrows;
2737 : }
2738 :
2739 : /*
2740 : * In addition to the cost of evaluating the tlist, charge cpu_tuple_cost
2741 : * per input row, and half of cpu_tuple_cost for each added output row.
2742 : * This is slightly bizarre maybe, but it's what 9.6 did; we may revisit
2743 : * this estimate later.
2744 : */
2745 3956 : pathnode->path.rows = subpath->rows * tlist_rows;
2746 7912 : pathnode->path.startup_cost = subpath->startup_cost +
2747 3956 : target->cost.startup;
2748 11868 : pathnode->path.total_cost = subpath->total_cost +
2749 7912 : target->cost.startup +
2750 7912 : (cpu_tuple_cost + target->cost.per_tuple) * subpath->rows +
2751 3956 : (pathnode->path.rows - subpath->rows) * cpu_tuple_cost / 2;
2752 :
2753 3956 : return pathnode;
2754 : }
2755 :
2756 : /*
2757 : * create_incremental_sort_path
2758 : * Creates a pathnode that represents performing an incremental sort.
2759 : *
2760 : * 'rel' is the parent relation associated with the result
2761 : * 'subpath' is the path representing the source of data
2762 : * 'pathkeys' represents the desired sort order
2763 : * 'presorted_keys' is the number of keys by which the input path is
2764 : * already sorted
2765 : * 'limit_tuples' is the estimated bound on the number of output tuples,
2766 : * or -1 if no LIMIT or couldn't estimate
2767 : */
2768 : SortPath *
2769 1504 : create_incremental_sort_path(PlannerInfo *root,
2770 : RelOptInfo *rel,
2771 : Path *subpath,
2772 : List *pathkeys,
2773 : int presorted_keys,
2774 : double limit_tuples)
2775 : {
2776 1504 : IncrementalSortPath *sort = makeNode(IncrementalSortPath);
2777 1504 : SortPath *pathnode = &sort->spath;
2778 :
2779 1504 : pathnode->path.pathtype = T_IncrementalSort;
2780 1504 : pathnode->path.parent = rel;
2781 : /* Sort doesn't project, so use source path's pathtarget */
2782 1504 : pathnode->path.pathtarget = subpath->pathtarget;
2783 : /* For now, assume we are above any joins, so no parameterization */
2784 1504 : pathnode->path.param_info = NULL;
2785 1504 : pathnode->path.parallel_aware = false;
2786 2744 : pathnode->path.parallel_safe = rel->consider_parallel &&
2787 1240 : subpath->parallel_safe;
2788 1504 : pathnode->path.parallel_workers = subpath->parallel_workers;
2789 1504 : pathnode->path.pathkeys = pathkeys;
2790 :
2791 1504 : pathnode->subpath = subpath;
2792 :
2793 3008 : cost_incremental_sort(&pathnode->path,
2794 : root, pathkeys, presorted_keys,
2795 : subpath->startup_cost,
2796 : subpath->total_cost,
2797 : subpath->rows,
2798 1504 : subpath->pathtarget->width,
2799 : 0.0, /* XXX comparison_cost shouldn't be 0? */
2800 : work_mem, limit_tuples);
2801 :
2802 1504 : sort->nPresortedCols = presorted_keys;
2803 :
2804 1504 : return pathnode;
2805 : }
2806 :
2807 : /*
2808 : * create_sort_path
2809 : * Creates a pathnode that represents performing an explicit sort.
2810 : *
2811 : * 'rel' is the parent relation associated with the result
2812 : * 'subpath' is the path representing the source of data
2813 : * 'pathkeys' represents the desired sort order
2814 : * 'limit_tuples' is the estimated bound on the number of output tuples,
2815 : * or -1 if no LIMIT or couldn't estimate
2816 : */
2817 : SortPath *
2818 39716 : create_sort_path(PlannerInfo *root,
2819 : RelOptInfo *rel,
2820 : Path *subpath,
2821 : List *pathkeys,
2822 : double limit_tuples)
2823 : {
2824 39716 : SortPath *pathnode = makeNode(SortPath);
2825 :
2826 39716 : pathnode->path.pathtype = T_Sort;
2827 39716 : pathnode->path.parent = rel;
2828 : /* Sort doesn't project, so use source path's pathtarget */
2829 39716 : pathnode->path.pathtarget = subpath->pathtarget;
2830 : /* For now, assume we are above any joins, so no parameterization */
2831 39716 : pathnode->path.param_info = NULL;
2832 39716 : pathnode->path.parallel_aware = false;
2833 61068 : pathnode->path.parallel_safe = rel->consider_parallel &&
2834 21352 : subpath->parallel_safe;
2835 39716 : pathnode->path.parallel_workers = subpath->parallel_workers;
2836 39716 : pathnode->path.pathkeys = pathkeys;
2837 :
2838 39716 : pathnode->subpath = subpath;
2839 :
2840 79432 : cost_sort(&pathnode->path, root, pathkeys,
2841 : subpath->total_cost,
2842 : subpath->rows,
2843 39716 : subpath->pathtarget->width,
2844 : 0.0, /* XXX comparison_cost shouldn't be 0? */
2845 : work_mem, limit_tuples);
2846 :
2847 39716 : return pathnode;
2848 : }
2849 :
2850 : /*
2851 : * create_group_path
2852 : * Creates a pathnode that represents performing grouping of presorted input
2853 : *
2854 : * 'rel' is the parent relation associated with the result
2855 : * 'subpath' is the path representing the source of data
2856 : * 'target' is the PathTarget to be computed
2857 : * 'groupClause' is a list of SortGroupClause's representing the grouping
2858 : * 'qual' is the HAVING quals if any
2859 : * 'numGroups' is the estimated number of groups
2860 : */
2861 : GroupPath *
2862 548 : create_group_path(PlannerInfo *root,
2863 : RelOptInfo *rel,
2864 : Path *subpath,
2865 : List *groupClause,
2866 : List *qual,
2867 : double numGroups)
2868 : {
2869 548 : GroupPath *pathnode = makeNode(GroupPath);
2870 548 : PathTarget *target = rel->reltarget;
2871 :
2872 548 : pathnode->path.pathtype = T_Group;
2873 548 : pathnode->path.parent = rel;
2874 548 : pathnode->path.pathtarget = target;
2875 : /* For now, assume we are above any joins, so no parameterization */
2876 548 : pathnode->path.param_info = NULL;
2877 548 : pathnode->path.parallel_aware = false;
2878 834 : pathnode->path.parallel_safe = rel->consider_parallel &&
2879 286 : subpath->parallel_safe;
2880 548 : pathnode->path.parallel_workers = subpath->parallel_workers;
2881 : /* Group doesn't change sort ordering */
2882 548 : pathnode->path.pathkeys = subpath->pathkeys;
2883 :
2884 548 : pathnode->subpath = subpath;
2885 :
2886 548 : pathnode->groupClause = groupClause;
2887 548 : pathnode->qual = qual;
2888 :
2889 548 : cost_group(&pathnode->path, root,
2890 : list_length(groupClause),
2891 : numGroups,
2892 : qual,
2893 : subpath->startup_cost, subpath->total_cost,
2894 : subpath->rows);
2895 :
2896 : /* add tlist eval cost for each output row */
2897 548 : pathnode->path.startup_cost += target->cost.startup;
2898 1096 : pathnode->path.total_cost += target->cost.startup +
2899 548 : target->cost.per_tuple * pathnode->path.rows;
2900 :
2901 548 : return pathnode;
2902 : }
2903 :
2904 : /*
2905 : * create_upper_unique_path
2906 : * Creates a pathnode that represents performing an explicit Unique step
2907 : * on presorted input.
2908 : *
2909 : * This produces a Unique plan node, but the use-case is so different from
2910 : * create_unique_path that it doesn't seem worth trying to merge the two.
2911 : *
2912 : * 'rel' is the parent relation associated with the result
2913 : * 'subpath' is the path representing the source of data
2914 : * 'numCols' is the number of grouping columns
2915 : * 'numGroups' is the estimated number of groups
2916 : *
2917 : * The input path must be sorted on the grouping columns, plus possibly
2918 : * additional columns; so the first numCols pathkeys are the grouping columns
2919 : */
2920 : UpperUniquePath *
2921 584 : create_upper_unique_path(PlannerInfo *root,
2922 : RelOptInfo *rel,
2923 : Path *subpath,
2924 : int numCols,
2925 : double numGroups)
2926 : {
2927 584 : UpperUniquePath *pathnode = makeNode(UpperUniquePath);
2928 :
2929 584 : pathnode->path.pathtype = T_Unique;
2930 584 : pathnode->path.parent = rel;
2931 : /* Unique doesn't project, so use source path's pathtarget */
2932 584 : pathnode->path.pathtarget = subpath->pathtarget;
2933 : /* For now, assume we are above any joins, so no parameterization */
2934 584 : pathnode->path.param_info = NULL;
2935 584 : pathnode->path.parallel_aware = false;
2936 974 : pathnode->path.parallel_safe = rel->consider_parallel &&
2937 390 : subpath->parallel_safe;
2938 584 : pathnode->path.parallel_workers = subpath->parallel_workers;
2939 : /* Unique doesn't change the input ordering */
2940 584 : pathnode->path.pathkeys = subpath->pathkeys;
2941 :
2942 584 : pathnode->subpath = subpath;
2943 584 : pathnode->numkeys = numCols;
2944 :
2945 : /*
2946 : * Charge one cpu_operator_cost per comparison per input tuple. We assume
2947 : * all columns get compared at most of the tuples. (XXX probably this is
2948 : * an overestimate.)
2949 : */
2950 584 : pathnode->path.startup_cost = subpath->startup_cost;
2951 1168 : pathnode->path.total_cost = subpath->total_cost +
2952 584 : cpu_operator_cost * subpath->rows * numCols;
2953 584 : pathnode->path.rows = numGroups;
2954 :
2955 584 : return pathnode;
2956 : }
2957 :
2958 : /*
2959 : * create_agg_path
2960 : * Creates a pathnode that represents performing aggregation/grouping
2961 : *
2962 : * 'rel' is the parent relation associated with the result
2963 : * 'subpath' is the path representing the source of data
2964 : * 'target' is the PathTarget to be computed
2965 : * 'aggstrategy' is the Agg node's basic implementation strategy
2966 : * 'aggsplit' is the Agg node's aggregate-splitting mode
2967 : * 'groupClause' is a list of SortGroupClause's representing the grouping
2968 : * 'qual' is the HAVING quals if any
2969 : * 'aggcosts' contains cost info about the aggregate functions to be computed
2970 : * 'numGroups' is the estimated number of groups (1 if not grouping)
2971 : */
2972 : AggPath *
2973 33176 : create_agg_path(PlannerInfo *root,
2974 : RelOptInfo *rel,
2975 : Path *subpath,
2976 : PathTarget *target,
2977 : AggStrategy aggstrategy,
2978 : AggSplit aggsplit,
2979 : List *groupClause,
2980 : List *qual,
2981 : const AggClauseCosts *aggcosts,
2982 : double numGroups)
2983 : {
2984 33176 : AggPath *pathnode = makeNode(AggPath);
2985 :
2986 33176 : pathnode->path.pathtype = T_Agg;
2987 33176 : pathnode->path.parent = rel;
2988 33176 : pathnode->path.pathtarget = target;
2989 : /* For now, assume we are above any joins, so no parameterization */
2990 33176 : pathnode->path.param_info = NULL;
2991 33176 : pathnode->path.parallel_aware = false;
2992 50004 : pathnode->path.parallel_safe = rel->consider_parallel &&
2993 16828 : subpath->parallel_safe;
2994 33176 : pathnode->path.parallel_workers = subpath->parallel_workers;
2995 33176 : if (aggstrategy == AGG_SORTED)
2996 4238 : pathnode->path.pathkeys = subpath->pathkeys; /* preserves order */
2997 : else
2998 28938 : pathnode->path.pathkeys = NIL; /* output is unordered */
2999 33176 : pathnode->subpath = subpath;
3000 :
3001 33176 : pathnode->aggstrategy = aggstrategy;
3002 33176 : pathnode->aggsplit = aggsplit;
3003 33176 : pathnode->numGroups = numGroups;
3004 33176 : pathnode->transitionSpace = aggcosts ? aggcosts->transitionSpace : 0;
3005 33176 : pathnode->groupClause = groupClause;
3006 33176 : pathnode->qual = qual;
3007 :
3008 33176 : cost_agg(&pathnode->path, root,
3009 : aggstrategy, aggcosts,
3010 : list_length(groupClause), numGroups,
3011 : qual,
3012 : subpath->startup_cost, subpath->total_cost,
3013 33176 : subpath->rows, subpath->pathtarget->width);
3014 :
3015 : /* add tlist eval cost for each output row */
3016 33176 : pathnode->path.startup_cost += target->cost.startup;
3017 66352 : pathnode->path.total_cost += target->cost.startup +
3018 33176 : target->cost.per_tuple * pathnode->path.rows;
3019 :
3020 33176 : return pathnode;
3021 : }
3022 :
3023 : /*
3024 : * create_groupingsets_path
3025 : * Creates a pathnode that represents performing GROUPING SETS aggregation
3026 : *
3027 : * GroupingSetsPath represents sorted grouping with one or more grouping sets.
3028 : * The input path's result must be sorted to match the last entry in
3029 : * rollup_groupclauses.
3030 : *
3031 : * 'rel' is the parent relation associated with the result
3032 : * 'subpath' is the path representing the source of data
3033 : * 'target' is the PathTarget to be computed
3034 : * 'having_qual' is the HAVING quals if any
3035 : * 'rollups' is a list of RollupData nodes
3036 : * 'agg_costs' contains cost info about the aggregate functions to be computed
3037 : * 'numGroups' is the estimated total number of groups
3038 : */
3039 : GroupingSetsPath *
3040 1076 : create_groupingsets_path(PlannerInfo *root,
3041 : RelOptInfo *rel,
3042 : Path *subpath,
3043 : List *having_qual,
3044 : AggStrategy aggstrategy,
3045 : List *rollups,
3046 : const AggClauseCosts *agg_costs,
3047 : double numGroups)
3048 : {
3049 1076 : GroupingSetsPath *pathnode = makeNode(GroupingSetsPath);
3050 1076 : PathTarget *target = rel->reltarget;
3051 : ListCell *lc;
3052 1076 : bool is_first = true;
3053 1076 : bool is_first_sort = true;
3054 :
3055 : /* The topmost generated Plan node will be an Agg */
3056 1076 : pathnode->path.pathtype = T_Agg;
3057 1076 : pathnode->path.parent = rel;
3058 1076 : pathnode->path.pathtarget = target;
3059 1076 : pathnode->path.param_info = subpath->param_info;
3060 1076 : pathnode->path.parallel_aware = false;
3061 1528 : pathnode->path.parallel_safe = rel->consider_parallel &&
3062 452 : subpath->parallel_safe;
3063 1076 : pathnode->path.parallel_workers = subpath->parallel_workers;
3064 1076 : pathnode->subpath = subpath;
3065 :
3066 : /*
3067 : * Simplify callers by downgrading AGG_SORTED to AGG_PLAIN, and AGG_MIXED
3068 : * to AGG_HASHED, here if possible.
3069 : */
3070 1552 : if (aggstrategy == AGG_SORTED &&
3071 476 : list_length(rollups) == 1 &&
3072 236 : ((RollupData *) linitial(rollups))->groupClause == NIL)
3073 28 : aggstrategy = AGG_PLAIN;
3074 :
3075 1552 : if (aggstrategy == AGG_MIXED &&
3076 476 : list_length(rollups) == 1)
3077 0 : aggstrategy = AGG_HASHED;
3078 :
3079 : /*
3080 : * Output will be in sorted order by group_pathkeys if, and only if, there
3081 : * is a single rollup operation on a non-empty list of grouping
3082 : * expressions.
3083 : */
3084 1076 : if (aggstrategy == AGG_SORTED && list_length(rollups) == 1)
3085 208 : pathnode->path.pathkeys = root->group_pathkeys;
3086 : else
3087 868 : pathnode->path.pathkeys = NIL;
3088 :
3089 1076 : pathnode->aggstrategy = aggstrategy;
3090 1076 : pathnode->rollups = rollups;
3091 1076 : pathnode->qual = having_qual;
3092 1076 : pathnode->transitionSpace = agg_costs ? agg_costs->transitionSpace : 0;
3093 :
3094 : Assert(rollups != NIL);
3095 : Assert(aggstrategy != AGG_PLAIN || list_length(rollups) == 1);
3096 : Assert(aggstrategy != AGG_MIXED || list_length(rollups) > 1);
3097 :
3098 3732 : foreach(lc, rollups)
3099 : {
3100 2656 : RollupData *rollup = lfirst(lc);
3101 2656 : List *gsets = rollup->gsets;
3102 2656 : int numGroupCols = list_length(linitial(gsets));
3103 :
3104 : /*
3105 : * In AGG_SORTED or AGG_PLAIN mode, the first rollup takes the
3106 : * (already-sorted) input, and following ones do their own sort.
3107 : *
3108 : * In AGG_HASHED mode, there is one rollup for each grouping set.
3109 : *
3110 : * In AGG_MIXED mode, the first rollups are hashed, the first
3111 : * non-hashed one takes the (already-sorted) input, and following ones
3112 : * do their own sort.
3113 : */
3114 2656 : if (is_first)
3115 : {
3116 1076 : cost_agg(&pathnode->path, root,
3117 : aggstrategy,
3118 : agg_costs,
3119 : numGroupCols,
3120 : rollup->numGroups,
3121 : having_qual,
3122 : subpath->startup_cost,
3123 : subpath->total_cost,
3124 : subpath->rows,
3125 1076 : subpath->pathtarget->width);
3126 1076 : is_first = false;
3127 1076 : if (!rollup->is_hashed)
3128 476 : is_first_sort = false;
3129 : }
3130 : else
3131 : {
3132 : Path sort_path; /* dummy for result of cost_sort */
3133 : Path agg_path; /* dummy for result of cost_agg */
3134 :
3135 1580 : if (rollup->is_hashed || is_first_sort)
3136 : {
3137 : /*
3138 : * Account for cost of aggregation, but don't charge input
3139 : * cost again
3140 : */
3141 1172 : cost_agg(&agg_path, root,
3142 1172 : rollup->is_hashed ? AGG_HASHED : AGG_SORTED,
3143 : agg_costs,
3144 : numGroupCols,
3145 : rollup->numGroups,
3146 : having_qual,
3147 : 0.0, 0.0,
3148 : subpath->rows,
3149 1172 : subpath->pathtarget->width);
3150 1648 : if (!rollup->is_hashed)
3151 476 : is_first_sort = false;
3152 : }
3153 : else
3154 : {
3155 : /* Account for cost of sort, but don't charge input cost again */
3156 816 : cost_sort(&sort_path, root, NIL,
3157 : 0.0,
3158 : subpath->rows,
3159 408 : subpath->pathtarget->width,
3160 : 0.0,
3161 : work_mem,
3162 : -1.0);
3163 :
3164 : /* Account for cost of aggregation */
3165 :
3166 408 : cost_agg(&agg_path, root,
3167 : AGG_SORTED,
3168 : agg_costs,
3169 : numGroupCols,
3170 : rollup->numGroups,
3171 : having_qual,
3172 : sort_path.startup_cost,
3173 : sort_path.total_cost,
3174 : sort_path.rows,
3175 408 : subpath->pathtarget->width);
3176 : }
3177 :
3178 1580 : pathnode->path.total_cost += agg_path.total_cost;
3179 1580 : pathnode->path.rows += agg_path.rows;
3180 : }
3181 : }
3182 :
3183 : /* add tlist eval cost for each output row */
3184 1076 : pathnode->path.startup_cost += target->cost.startup;
3185 2152 : pathnode->path.total_cost += target->cost.startup +
3186 1076 : target->cost.per_tuple * pathnode->path.rows;
3187 :
3188 1076 : return pathnode;
3189 : }
3190 :
3191 : /*
3192 : * create_minmaxagg_path
3193 : * Creates a pathnode that represents computation of MIN/MAX aggregates
3194 : *
3195 : * 'rel' is the parent relation associated with the result
3196 : * 'target' is the PathTarget to be computed
3197 : * 'mmaggregates' is a list of MinMaxAggInfo structs
3198 : * 'quals' is the HAVING quals if any
3199 : */
3200 : MinMaxAggPath *
3201 398 : create_minmaxagg_path(PlannerInfo *root,
3202 : RelOptInfo *rel,
3203 : PathTarget *target,
3204 : List *mmaggregates,
3205 : List *quals)
3206 : {
3207 398 : MinMaxAggPath *pathnode = makeNode(MinMaxAggPath);
3208 : Cost initplan_cost;
3209 : ListCell *lc;
3210 :
3211 : /* The topmost generated Plan node will be a Result */
3212 398 : pathnode->path.pathtype = T_Result;
3213 398 : pathnode->path.parent = rel;
3214 398 : pathnode->path.pathtarget = target;
3215 : /* For now, assume we are above any joins, so no parameterization */
3216 398 : pathnode->path.param_info = NULL;
3217 398 : pathnode->path.parallel_aware = false;
3218 : /* A MinMaxAggPath implies use of subplans, so cannot be parallel-safe */
3219 398 : pathnode->path.parallel_safe = false;
3220 398 : pathnode->path.parallel_workers = 0;
3221 : /* Result is one unordered row */
3222 398 : pathnode->path.rows = 1;
3223 398 : pathnode->path.pathkeys = NIL;
3224 :
3225 398 : pathnode->mmaggregates = mmaggregates;
3226 398 : pathnode->quals = quals;
3227 :
3228 : /* Calculate cost of all the initplans ... */
3229 398 : initplan_cost = 0;
3230 820 : foreach(lc, mmaggregates)
3231 : {
3232 422 : MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);
3233 :
3234 422 : initplan_cost += mminfo->pathcost;
3235 : }
3236 :
3237 : /* add tlist eval cost for each output row, plus cpu_tuple_cost */
3238 398 : pathnode->path.startup_cost = initplan_cost + target->cost.startup;
3239 1194 : pathnode->path.total_cost = initplan_cost + target->cost.startup +
3240 796 : target->cost.per_tuple + cpu_tuple_cost;
3241 :
3242 : /*
3243 : * Add cost of qual, if any --- but we ignore its selectivity, since our
3244 : * rowcount estimate should be 1 no matter what the qual is.
3245 : */
3246 398 : if (quals)
3247 : {
3248 : QualCost qual_cost;
3249 :
3250 0 : cost_qual_eval(&qual_cost, quals, root);
3251 0 : pathnode->path.startup_cost += qual_cost.startup;
3252 0 : pathnode->path.total_cost += qual_cost.startup + qual_cost.per_tuple;
3253 : }
3254 :
3255 398 : return pathnode;
3256 : }
3257 :
3258 : /*
3259 : * create_windowagg_path
3260 : * Creates a pathnode that represents computation of window functions
3261 : *
3262 : * 'rel' is the parent relation associated with the result
3263 : * 'subpath' is the path representing the source of data
3264 : * 'target' is the PathTarget to be computed
3265 : * 'windowFuncs' is a list of WindowFunc structs
3266 : * 'winclause' is a WindowClause that is common to all the WindowFuncs
3267 : *
3268 : * The input must be sorted according to the WindowClause's PARTITION keys
3269 : * plus ORDER BY keys.
3270 : */
3271 : WindowAggPath *
3272 1204 : create_windowagg_path(PlannerInfo *root,
3273 : RelOptInfo *rel,
3274 : Path *subpath,
3275 : PathTarget *target,
3276 : List *windowFuncs,
3277 : WindowClause *winclause)
3278 : {
3279 1204 : WindowAggPath *pathnode = makeNode(WindowAggPath);
3280 :
3281 1204 : pathnode->path.pathtype = T_WindowAgg;
3282 1204 : pathnode->path.parent = rel;
3283 1204 : pathnode->path.pathtarget = target;
3284 : /* For now, assume we are above any joins, so no parameterization */
3285 1204 : pathnode->path.param_info = NULL;
3286 1204 : pathnode->path.parallel_aware = false;
3287 1204 : pathnode->path.parallel_safe = rel->consider_parallel &&
3288 0 : subpath->parallel_safe;
3289 1204 : pathnode->path.parallel_workers = subpath->parallel_workers;
3290 : /* WindowAgg preserves the input sort order */
3291 1204 : pathnode->path.pathkeys = subpath->pathkeys;
3292 :
3293 1204 : pathnode->subpath = subpath;
3294 1204 : pathnode->winclause = winclause;
3295 :
3296 : /*
3297 : * For costing purposes, assume that there are no redundant partitioning
3298 : * or ordering columns; it's not worth the trouble to deal with that
3299 : * corner case here. So we just pass the unmodified list lengths to
3300 : * cost_windowagg.
3301 : */
3302 1204 : cost_windowagg(&pathnode->path, root,
3303 : windowFuncs,
3304 1204 : list_length(winclause->partitionClause),
3305 1204 : list_length(winclause->orderClause),
3306 : subpath->startup_cost,
3307 : subpath->total_cost,
3308 : subpath->rows);
3309 :
3310 : /* add tlist eval cost for each output row */
3311 1204 : pathnode->path.startup_cost += target->cost.startup;
3312 2408 : pathnode->path.total_cost += target->cost.startup +
3313 1204 : target->cost.per_tuple * pathnode->path.rows;
3314 :
3315 1204 : return pathnode;
3316 : }
3317 :
3318 : /*
3319 : * create_setop_path
3320 : * Creates a pathnode that represents computation of INTERSECT or EXCEPT
3321 : *
3322 : * 'rel' is the parent relation associated with the result
3323 : * 'subpath' is the path representing the source of data
3324 : * 'cmd' is the specific semantics (INTERSECT or EXCEPT, with/without ALL)
3325 : * 'strategy' is the implementation strategy (sorted or hashed)
3326 : * 'distinctList' is a list of SortGroupClause's representing the grouping
3327 : * 'flagColIdx' is the column number where the flag column will be, if any
3328 : * 'firstFlag' is the flag value for the first input relation when hashing;
3329 : * or -1 when sorting
3330 : * 'numGroups' is the estimated number of distinct groups
3331 : * 'outputRows' is the estimated number of output rows
3332 : */
3333 : SetOpPath *
3334 272 : create_setop_path(PlannerInfo *root,
3335 : RelOptInfo *rel,
3336 : Path *subpath,
3337 : SetOpCmd cmd,
3338 : SetOpStrategy strategy,
3339 : List *distinctList,
3340 : AttrNumber flagColIdx,
3341 : int firstFlag,
3342 : double numGroups,
3343 : double outputRows)
3344 : {
3345 272 : SetOpPath *pathnode = makeNode(SetOpPath);
3346 :
3347 272 : pathnode->path.pathtype = T_SetOp;
3348 272 : pathnode->path.parent = rel;
3349 : /* SetOp doesn't project, so use source path's pathtarget */
3350 272 : pathnode->path.pathtarget = subpath->pathtarget;
3351 : /* For now, assume we are above any joins, so no parameterization */
3352 272 : pathnode->path.param_info = NULL;
3353 272 : pathnode->path.parallel_aware = false;
3354 272 : pathnode->path.parallel_safe = rel->consider_parallel &&
3355 0 : subpath->parallel_safe;
3356 272 : pathnode->path.parallel_workers = subpath->parallel_workers;
3357 : /* SetOp preserves the input sort order if in sort mode */
3358 272 : pathnode->path.pathkeys =
3359 272 : (strategy == SETOP_SORTED) ? subpath->pathkeys : NIL;
3360 :
3361 272 : pathnode->subpath = subpath;
3362 272 : pathnode->cmd = cmd;
3363 272 : pathnode->strategy = strategy;
3364 272 : pathnode->distinctList = distinctList;
3365 272 : pathnode->flagColIdx = flagColIdx;
3366 272 : pathnode->firstFlag = firstFlag;
3367 272 : pathnode->numGroups = numGroups;
3368 :
3369 : /*
3370 : * Charge one cpu_operator_cost per comparison per input tuple. We assume
3371 : * all columns get compared at most of the tuples.
3372 : */
3373 272 : pathnode->path.startup_cost = subpath->startup_cost;
3374 544 : pathnode->path.total_cost = subpath->total_cost +
3375 272 : cpu_operator_cost * subpath->rows * list_length(distinctList);
3376 272 : pathnode->path.rows = outputRows;
3377 :
3378 272 : return pathnode;
3379 : }
3380 :
3381 : /*
3382 : * create_recursiveunion_path
3383 : * Creates a pathnode that represents a recursive UNION node
3384 : *
3385 : * 'rel' is the parent relation associated with the result
3386 : * 'leftpath' is the source of data for the non-recursive term
3387 : * 'rightpath' is the source of data for the recursive term
3388 : * 'target' is the PathTarget to be computed
3389 : * 'distinctList' is a list of SortGroupClause's representing the grouping
3390 : * 'wtParam' is the ID of Param representing work table
3391 : * 'numGroups' is the estimated number of groups
3392 : *
3393 : * For recursive UNION ALL, distinctList is empty and numGroups is zero
3394 : */
3395 : RecursiveUnionPath *
3396 332 : create_recursiveunion_path(PlannerInfo *root,
3397 : RelOptInfo *rel,
3398 : Path *leftpath,
3399 : Path *rightpath,
3400 : PathTarget *target,
3401 : List *distinctList,
3402 : int wtParam,
3403 : double numGroups)
3404 : {
3405 332 : RecursiveUnionPath *pathnode = makeNode(RecursiveUnionPath);
3406 :
3407 332 : pathnode->path.pathtype = T_RecursiveUnion;
3408 332 : pathnode->path.parent = rel;
3409 332 : pathnode->path.pathtarget = target;
3410 : /* For now, assume we are above any joins, so no parameterization */
3411 332 : pathnode->path.param_info = NULL;
3412 332 : pathnode->path.parallel_aware = false;
3413 664 : pathnode->path.parallel_safe = rel->consider_parallel &&
3414 332 : leftpath->parallel_safe && rightpath->parallel_safe;
3415 : /* Foolish, but we'll do it like joins for now: */
3416 332 : pathnode->path.parallel_workers = leftpath->parallel_workers;
3417 : /* RecursiveUnion result is always unsorted */
3418 332 : pathnode->path.pathkeys = NIL;
3419 :
3420 332 : pathnode->leftpath = leftpath;
3421 332 : pathnode->rightpath = rightpath;
3422 332 : pathnode->distinctList = distinctList;
3423 332 : pathnode->wtParam = wtParam;
3424 332 : pathnode->numGroups = numGroups;
3425 :
3426 332 : cost_recursive_union(&pathnode->path, leftpath, rightpath);
3427 :
3428 332 : return pathnode;
3429 : }
3430 :
3431 : /*
3432 : * create_lockrows_path
3433 : * Creates a pathnode that represents acquiring row locks
3434 : *
3435 : * 'rel' is the parent relation associated with the result
3436 : * 'subpath' is the path representing the source of data
3437 : * 'rowMarks' is a list of PlanRowMark's
3438 : * 'epqParam' is the ID of Param for EvalPlanQual re-eval
3439 : */
3440 : LockRowsPath *
3441 5404 : create_lockrows_path(PlannerInfo *root, RelOptInfo *rel,
3442 : Path *subpath, List *rowMarks, int epqParam)
3443 : {
3444 5404 : LockRowsPath *pathnode = makeNode(LockRowsPath);
3445 :
3446 5404 : pathnode->path.pathtype = T_LockRows;
3447 5404 : pathnode->path.parent = rel;
3448 : /* LockRows doesn't project, so use source path's pathtarget */
3449 5404 : pathnode->path.pathtarget = subpath->pathtarget;
3450 : /* For now, assume we are above any joins, so no parameterization */
3451 5404 : pathnode->path.param_info = NULL;
3452 5404 : pathnode->path.parallel_aware = false;
3453 5404 : pathnode->path.parallel_safe = false;
3454 5404 : pathnode->path.parallel_workers = 0;
3455 5404 : pathnode->path.rows = subpath->rows;
3456 :
3457 : /*
3458 : * The result cannot be assumed sorted, since locking might cause the sort
3459 : * key columns to be replaced with new values.
3460 : */
3461 5404 : pathnode->path.pathkeys = NIL;
3462 :
3463 5404 : pathnode->subpath = subpath;
3464 5404 : pathnode->rowMarks = rowMarks;
3465 5404 : pathnode->epqParam = epqParam;
3466 :
3467 : /*
3468 : * We should charge something extra for the costs of row locking and
3469 : * possible refetches, but it's hard to say how much. For now, use
3470 : * cpu_tuple_cost per row.
3471 : */
3472 5404 : pathnode->path.startup_cost = subpath->startup_cost;
3473 10808 : pathnode->path.total_cost = subpath->total_cost +
3474 5404 : cpu_tuple_cost * subpath->rows;
3475 :
3476 5404 : return pathnode;
3477 : }
3478 :
3479 : /*
3480 : * create_modifytable_path
3481 : * Creates a pathnode that represents performing INSERT/UPDATE/DELETE mods
3482 : *
3483 : * 'rel' is the parent relation associated with the result
3484 : * 'operation' is the operation type
3485 : * 'canSetTag' is true if we set the command tag/es_processed
3486 : * 'nominalRelation' is the parent RT index for use of EXPLAIN
3487 : * 'rootRelation' is the partitioned table root RT index, or 0 if none
3488 : * 'partColsUpdated' is true if any partitioning columns are being updated,
3489 : * either from the target relation or a descendent partitioned table.
3490 : * 'resultRelations' is an integer list of actual RT indexes of target rel(s)
3491 : * 'subpaths' is a list of Path(s) producing source data (one per rel)
3492 : * 'subroots' is a list of PlannerInfo structs (one per rel)
3493 : * 'withCheckOptionLists' is a list of WCO lists (one per rel)
3494 : * 'returningLists' is a list of RETURNING tlists (one per rel)
3495 : * 'rowMarks' is a list of PlanRowMarks (non-locking only)
3496 : * 'onconflict' is the ON CONFLICT clause, or NULL
3497 : * 'epqParam' is the ID of Param for EvalPlanQual re-eval
3498 : */
3499 : ModifyTablePath *
3500 73116 : create_modifytable_path(PlannerInfo *root, RelOptInfo *rel,
3501 : CmdType operation, bool canSetTag,
3502 : Index nominalRelation, Index rootRelation,
3503 : bool partColsUpdated,
3504 : List *resultRelations, List *subpaths,
3505 : List *subroots,
3506 : List *withCheckOptionLists, List *returningLists,
3507 : List *rowMarks, OnConflictExpr *onconflict,
3508 : int epqParam)
3509 : {
3510 73116 : ModifyTablePath *pathnode = makeNode(ModifyTablePath);
3511 : double total_size;
3512 : ListCell *lc;
3513 :
3514 : Assert(list_length(resultRelations) == list_length(subpaths));
3515 : Assert(list_length(resultRelations) == list_length(subroots));
3516 : Assert(withCheckOptionLists == NIL ||
3517 : list_length(resultRelations) == list_length(withCheckOptionLists));
3518 : Assert(returningLists == NIL ||
3519 : list_length(resultRelations) == list_length(returningLists));
3520 :
3521 73116 : pathnode->path.pathtype = T_ModifyTable;
3522 73116 : pathnode->path.parent = rel;
3523 : /* pathtarget is not interesting, just make it minimally valid */
3524 73116 : pathnode->path.pathtarget = rel->reltarget;
3525 : /* For now, assume we are above any joins, so no parameterization */
3526 73116 : pathnode->path.param_info = NULL;
3527 73116 : pathnode->path.parallel_aware = false;
3528 73116 : pathnode->path.parallel_safe = false;
3529 73116 : pathnode->path.parallel_workers = 0;
3530 73116 : pathnode->path.pathkeys = NIL;
3531 :
3532 : /*
3533 : * Compute cost & rowcount as sum of subpath costs & rowcounts.
3534 : *
3535 : * Currently, we don't charge anything extra for the actual table
3536 : * modification work, nor for the WITH CHECK OPTIONS or RETURNING
3537 : * expressions if any. It would only be window dressing, since
3538 : * ModifyTable is always a top-level node and there is no way for the
3539 : * costs to change any higher-level planning choices. But we might want
3540 : * to make it look better sometime.
3541 : */
3542 73116 : pathnode->path.startup_cost = 0;
3543 73116 : pathnode->path.total_cost = 0;
3544 73116 : pathnode->path.rows = 0;
3545 73116 : total_size = 0;
3546 147430 : foreach(lc, subpaths)
3547 : {
3548 74314 : Path *subpath = (Path *) lfirst(lc);
3549 :
3550 74314 : if (lc == list_head(subpaths)) /* first node? */
3551 73116 : pathnode->path.startup_cost = subpath->startup_cost;
3552 74314 : pathnode->path.total_cost += subpath->total_cost;
3553 74314 : pathnode->path.rows += subpath->rows;
3554 74314 : total_size += subpath->pathtarget->width * subpath->rows;
3555 : }
3556 :
3557 : /*
3558 : * Set width to the average width of the subpath outputs. XXX this is
3559 : * totally wrong: we should report zero if no RETURNING, else an average
3560 : * of the RETURNING tlist widths. But it's what happened historically,
3561 : * and improving it is a task for another day.
3562 : */
3563 73116 : if (pathnode->path.rows > 0)
3564 73048 : total_size /= pathnode->path.rows;
3565 73116 : pathnode->path.pathtarget->width = rint(total_size);
3566 :
3567 73116 : pathnode->operation = operation;
3568 73116 : pathnode->canSetTag = canSetTag;
3569 73116 : pathnode->nominalRelation = nominalRelation;
3570 73116 : pathnode->rootRelation = rootRelation;
3571 73116 : pathnode->partColsUpdated = partColsUpdated;
3572 73116 : pathnode->resultRelations = resultRelations;
3573 73116 : pathnode->subpaths = subpaths;
3574 73116 : pathnode->subroots = subroots;
3575 73116 : pathnode->withCheckOptionLists = withCheckOptionLists;
3576 73116 : pathnode->returningLists = returningLists;
3577 73116 : pathnode->rowMarks = rowMarks;
3578 73116 : pathnode->onconflict = onconflict;
3579 73116 : pathnode->epqParam = epqParam;
3580 :
3581 73116 : return pathnode;
3582 : }
3583 :
3584 : /*
3585 : * create_limit_path
3586 : * Creates a pathnode that represents performing LIMIT/OFFSET
3587 : *
3588 : * In addition to providing the actual OFFSET and LIMIT expressions,
3589 : * the caller must provide estimates of their values for costing purposes.
3590 : * The estimates are as computed by preprocess_limit(), ie, 0 represents
3591 : * the clause not being present, and -1 means it's present but we could
3592 : * not estimate its value.
3593 : *
3594 : * 'rel' is the parent relation associated with the result
3595 : * 'subpath' is the path representing the source of data
3596 : * 'limitOffset' is the actual OFFSET expression, or NULL
3597 : * 'limitCount' is the actual LIMIT expression, or NULL
3598 : * 'offset_est' is the estimated value of the OFFSET expression
3599 : * 'count_est' is the estimated value of the LIMIT expression
3600 : */
3601 : LimitPath *
3602 4056 : create_limit_path(PlannerInfo *root, RelOptInfo *rel,
3603 : Path *subpath,
3604 : Node *limitOffset, Node *limitCount,
3605 : LimitOption limitOption,
3606 : int64 offset_est, int64 count_est)
3607 : {
3608 4056 : LimitPath *pathnode = makeNode(LimitPath);
3609 :
3610 4056 : pathnode->path.pathtype = T_Limit;
3611 4056 : pathnode->path.parent = rel;
3612 : /* Limit doesn't project, so use source path's pathtarget */
3613 4056 : pathnode->path.pathtarget = subpath->pathtarget;
3614 : /* For now, assume we are above any joins, so no parameterization */
3615 4056 : pathnode->path.param_info = NULL;
3616 4056 : pathnode->path.parallel_aware = false;
3617 5576 : pathnode->path.parallel_safe = rel->consider_parallel &&
3618 1520 : subpath->parallel_safe;
3619 4056 : pathnode->path.parallel_workers = subpath->parallel_workers;
3620 4056 : pathnode->path.rows = subpath->rows;
3621 4056 : pathnode->path.startup_cost = subpath->startup_cost;
3622 4056 : pathnode->path.total_cost = subpath->total_cost;
3623 4056 : pathnode->path.pathkeys = subpath->pathkeys;
3624 4056 : pathnode->subpath = subpath;
3625 4056 : pathnode->limitOffset = limitOffset;
3626 4056 : pathnode->limitCount = limitCount;
3627 4056 : pathnode->limitOption = limitOption;
3628 :
3629 : /*
3630 : * Adjust the output rows count and costs according to the offset/limit.
3631 : */
3632 4056 : adjust_limit_rows_costs(&pathnode->path.rows,
3633 : &pathnode->path.startup_cost,
3634 : &pathnode->path.total_cost,
3635 : offset_est, count_est);
3636 :
3637 4056 : return pathnode;
3638 : }
3639 :
3640 : /*
3641 : * adjust_limit_rows_costs
3642 : * Adjust the size and cost estimates for a LimitPath node according to the
3643 : * offset/limit.
3644 : *
3645 : * This is only a cosmetic issue if we are at top level, but if we are
3646 : * building a subquery then it's important to report correct info to the outer
3647 : * planner.
3648 : *
3649 : * When the offset or count couldn't be estimated, use 10% of the estimated
3650 : * number of rows emitted from the subpath.
3651 : *
3652 : * XXX we don't bother to add eval costs of the offset/limit expressions
3653 : * themselves to the path costs. In theory we should, but in most cases those
3654 : * expressions are trivial and it's just not worth the trouble.
3655 : */
3656 : void
3657 4198 : adjust_limit_rows_costs(double *rows, /* in/out parameter */
3658 : Cost *startup_cost, /* in/out parameter */
3659 : Cost *total_cost, /* in/out parameter */
3660 : int64 offset_est,
3661 : int64 count_est)
3662 : {
3663 4198 : double input_rows = *rows;
3664 4198 : Cost input_startup_cost = *startup_cost;
3665 4198 : Cost input_total_cost = *total_cost;
3666 :
3667 4198 : if (offset_est != 0)
3668 : {
3669 : double offset_rows;
3670 :
3671 606 : if (offset_est > 0)
3672 590 : offset_rows = (double) offset_est;
3673 : else
3674 16 : offset_rows = clamp_row_est(input_rows * 0.10);
3675 606 : if (offset_rows > *rows)
3676 28 : offset_rows = *rows;
3677 606 : if (input_rows > 0)
3678 1212 : *startup_cost +=
3679 606 : (input_total_cost - input_startup_cost)
3680 606 : * offset_rows / input_rows;
3681 606 : *rows -= offset_rows;
3682 606 : if (*rows < 1)
3683 28 : *rows = 1;
3684 : }
3685 :
3686 4198 : if (count_est != 0)
3687 : {
3688 : double count_rows;
3689 :
3690 4166 : if (count_est > 0)
3691 4162 : count_rows = (double) count_est;
3692 : else
3693 4 : count_rows = clamp_row_est(input_rows * 0.10);
3694 4166 : if (count_rows > *rows)
3695 68 : count_rows = *rows;
3696 4166 : if (input_rows > 0)
3697 8332 : *total_cost = *startup_cost +
3698 4166 : (input_total_cost - input_startup_cost)
3699 4166 : * count_rows / input_rows;
3700 4166 : *rows = count_rows;
3701 4166 : if (*rows < 1)
3702 0 : *rows = 1;
3703 : }
3704 4198 : }
3705 :
3706 :
3707 : /*
3708 : * reparameterize_path
3709 : * Attempt to modify a Path to have greater parameterization
3710 : *
3711 : * We use this to attempt to bring all child paths of an appendrel to the
3712 : * same parameterization level, ensuring that they all enforce the same set
3713 : * of join quals (and thus that that parameterization can be attributed to
3714 : * an append path built from such paths). Currently, only a few path types
3715 : * are supported here, though more could be added at need. We return NULL
3716 : * if we can't reparameterize the given path.
3717 : *
3718 : * Note: we intentionally do not pass created paths to add_path(); it would
3719 : * possibly try to delete them on the grounds of being cost-inferior to the
3720 : * paths they were made from, and we don't want that. Paths made here are
3721 : * not necessarily of general-purpose usefulness, but they can be useful
3722 : * as members of an append path.
3723 : */
3724 : Path *
3725 204 : reparameterize_path(PlannerInfo *root, Path *path,
3726 : Relids required_outer,
3727 : double loop_count)
3728 : {
3729 204 : RelOptInfo *rel = path->parent;
3730 :
3731 : /* Can only increase, not decrease, path's parameterization */
3732 204 : if (!bms_is_subset(PATH_REQ_OUTER(path), required_outer))
3733 0 : return NULL;
3734 204 : switch (path->pathtype)
3735 : {
3736 140 : case T_SeqScan:
3737 140 : return create_seqscan_path(root, rel, required_outer, 0);
3738 0 : case T_SampleScan:
3739 0 : return (Path *) create_samplescan_path(root, rel, required_outer);
3740 0 : case T_IndexScan:
3741 : case T_IndexOnlyScan:
3742 : {
3743 0 : IndexPath *ipath = (IndexPath *) path;
3744 0 : IndexPath *newpath = makeNode(IndexPath);
3745 :
3746 : /*
3747 : * We can't use create_index_path directly, and would not want
3748 : * to because it would re-compute the indexqual conditions
3749 : * which is wasted effort. Instead we hack things a bit:
3750 : * flat-copy the path node, revise its param_info, and redo
3751 : * the cost estimate.
3752 : */
3753 0 : memcpy(newpath, ipath, sizeof(IndexPath));
3754 0 : newpath->path.param_info =
3755 0 : get_baserel_parampathinfo(root, rel, required_outer);
3756 0 : cost_index(newpath, root, loop_count, false);
3757 0 : return (Path *) newpath;
3758 : }
3759 0 : case T_BitmapHeapScan:
3760 : {
3761 0 : BitmapHeapPath *bpath = (BitmapHeapPath *) path;
3762 :
3763 0 : return (Path *) create_bitmap_heap_path(root,
3764 : rel,
3765 : bpath->bitmapqual,
3766 : required_outer,
3767 : loop_count, 0);
3768 : }
3769 0 : case T_SubqueryScan:
3770 : {
3771 0 : SubqueryScanPath *spath = (SubqueryScanPath *) path;
3772 :
3773 0 : return (Path *) create_subqueryscan_path(root,
3774 : rel,
3775 : spath->subpath,
3776 : spath->path.pathkeys,
3777 : required_outer);
3778 : }
3779 32 : case T_Result:
3780 : /* Supported only for RTE_RESULT scan paths */
3781 32 : if (IsA(path, Path))
3782 32 : return create_resultscan_path(root, rel, required_outer);
3783 0 : break;
3784 0 : case T_Append:
3785 : {
3786 0 : AppendPath *apath = (AppendPath *) path;
3787 0 : List *childpaths = NIL;
3788 0 : List *partialpaths = NIL;
3789 : int i;
3790 : ListCell *lc;
3791 :
3792 : /* Reparameterize the children */
3793 0 : i = 0;
3794 0 : foreach(lc, apath->subpaths)
3795 : {
3796 0 : Path *spath = (Path *) lfirst(lc);
3797 :
3798 0 : spath = reparameterize_path(root, spath,
3799 : required_outer,
3800 : loop_count);
3801 0 : if (spath == NULL)
3802 0 : return NULL;
3803 : /* We have to re-split the regular and partial paths */
3804 0 : if (i < apath->first_partial_path)
3805 0 : childpaths = lappend(childpaths, spath);
3806 : else
3807 0 : partialpaths = lappend(partialpaths, spath);
3808 0 : i++;
3809 : }
3810 0 : return (Path *)
3811 0 : create_append_path(root, rel, childpaths, partialpaths,
3812 : apath->path.pathkeys, required_outer,
3813 : apath->path.parallel_workers,
3814 0 : apath->path.parallel_aware,
3815 : apath->partitioned_rels,
3816 : -1);
3817 : }
3818 32 : default:
3819 32 : break;
3820 : }
3821 32 : return NULL;
3822 : }
3823 :
3824 : /*
3825 : * reparameterize_path_by_child
3826 : * Given a path parameterized by the parent of the given child relation,
3827 : * translate the path to be parameterized by the given child relation.
3828 : *
3829 : * The function creates a new path of the same type as the given path, but
3830 : * parameterized by the given child relation. Most fields from the original
3831 : * path can simply be flat-copied, but any expressions must be adjusted to
3832 : * refer to the correct varnos, and any paths must be recursively
3833 : * reparameterized. Other fields that refer to specific relids also need
3834 : * adjustment.
3835 : *
3836 : * The cost, number of rows, width and parallel path properties depend upon
3837 : * path->parent, which does not change during the translation. Hence those
3838 : * members are copied as they are.
3839 : *
3840 : * If the given path can not be reparameterized, the function returns NULL.
3841 : */
3842 : Path *
3843 2876 : reparameterize_path_by_child(PlannerInfo *root, Path *path,
3844 : RelOptInfo *child_rel)
3845 : {
3846 :
3847 : #define FLAT_COPY_PATH(newnode, node, nodetype) \
3848 : ( (newnode) = makeNode(nodetype), \
3849 : memcpy((newnode), (node), sizeof(nodetype)) )
3850 :
3851 : #define ADJUST_CHILD_ATTRS(node) \
3852 : ((node) = \
3853 : (List *) adjust_appendrel_attrs_multilevel(root, (Node *) (node), \
3854 : child_rel->relids, \
3855 : child_rel->top_parent_relids))
3856 :
3857 : #define REPARAMETERIZE_CHILD_PATH(path) \
3858 : do { \
3859 : (path) = reparameterize_path_by_child(root, (path), child_rel); \
3860 : if ((path) == NULL) \
3861 : return NULL; \
3862 : } while(0)
3863 :
3864 : #define REPARAMETERIZE_CHILD_PATH_LIST(pathlist) \
3865 : do { \
3866 : if ((pathlist) != NIL) \
3867 : { \
3868 : (pathlist) = reparameterize_pathlist_by_child(root, (pathlist), \
3869 : child_rel); \
3870 : if ((pathlist) == NIL) \
3871 : return NULL; \
3872 : } \
3873 : } while(0)
3874 :
3875 : Path *new_path;
3876 : ParamPathInfo *new_ppi;
3877 : ParamPathInfo *old_ppi;
3878 : Relids required_outer;
3879 :
3880 : /*
3881 : * If the path is not parameterized by parent of the given relation, it
3882 : * doesn't need reparameterization.
3883 : */
3884 2876 : if (!path->param_info ||
3885 2852 : !bms_overlap(PATH_REQ_OUTER(path), child_rel->top_parent_relids))
3886 128 : return path;
3887 :
3888 : /* Reparameterize a copy of given path. */
3889 2748 : switch (nodeTag(path))
3890 : {
3891 288 : case T_Path:
3892 288 : FLAT_COPY_PATH(new_path, path, Path);
3893 288 : break;
3894 :
3895 1992 : case T_IndexPath:
3896 : {
3897 : IndexPath *ipath;
3898 :
3899 1992 : FLAT_COPY_PATH(ipath, path, IndexPath);
3900 1992 : ADJUST_CHILD_ATTRS(ipath->indexclauses);
3901 1992 : new_path = (Path *) ipath;
3902 : }
3903 1992 : break;
3904 :
3905 0 : case T_BitmapHeapPath:
3906 : {
3907 : BitmapHeapPath *bhpath;
3908 :
3909 0 : FLAT_COPY_PATH(bhpath, path, BitmapHeapPath);
3910 0 : REPARAMETERIZE_CHILD_PATH(bhpath->bitmapqual);
3911 0 : new_path = (Path *) bhpath;
3912 : }
3913 0 : break;
3914 :
3915 0 : case T_BitmapAndPath:
3916 : {
3917 : BitmapAndPath *bapath;
3918 :
3919 0 : FLAT_COPY_PATH(bapath, path, BitmapAndPath);
3920 0 : REPARAMETERIZE_CHILD_PATH_LIST(bapath->bitmapquals);
3921 0 : new_path = (Path *) bapath;
3922 : }
3923 0 : break;
3924 :
3925 0 : case T_BitmapOrPath:
3926 : {
3927 : BitmapOrPath *bopath;
3928 :
3929 0 : FLAT_COPY_PATH(bopath, path, BitmapOrPath);
3930 0 : REPARAMETERIZE_CHILD_PATH_LIST(bopath->bitmapquals);
3931 0 : new_path = (Path *) bopath;
3932 : }
3933 0 : break;
3934 :
3935 0 : case T_TidPath:
3936 : {
3937 : TidPath *tpath;
3938 :
3939 0 : FLAT_COPY_PATH(tpath, path, TidPath);
3940 0 : ADJUST_CHILD_ATTRS(tpath->tidquals);
3941 0 : new_path = (Path *) tpath;
3942 : }
3943 0 : break;
3944 :
3945 52 : case T_ForeignPath:
3946 : {
3947 : ForeignPath *fpath;
3948 : ReparameterizeForeignPathByChild_function rfpc_func;
3949 :
3950 52 : FLAT_COPY_PATH(fpath, path, ForeignPath);
3951 52 : if (fpath->fdw_outerpath)
3952 0 : REPARAMETERIZE_CHILD_PATH(fpath->fdw_outerpath);
3953 :
3954 : /* Hand over to FDW if needed. */
3955 52 : rfpc_func =
3956 52 : path->parent->fdwroutine->ReparameterizeForeignPathByChild;
3957 52 : if (rfpc_func)
3958 0 : fpath->fdw_private = rfpc_func(root, fpath->fdw_private,
3959 : child_rel);
3960 52 : new_path = (Path *) fpath;
3961 : }
3962 52 : break;
3963 :
3964 0 : case T_CustomPath:
3965 : {
3966 : CustomPath *cpath;
3967 :
3968 0 : FLAT_COPY_PATH(cpath, path, CustomPath);
3969 0 : REPARAMETERIZE_CHILD_PATH_LIST(cpath->custom_paths);
3970 0 : if (cpath->methods &&
3971 0 : cpath->methods->ReparameterizeCustomPathByChild)
3972 0 : cpath->custom_private =
3973 0 : cpath->methods->ReparameterizeCustomPathByChild(root,
3974 : cpath->custom_private,
3975 : child_rel);
3976 0 : new_path = (Path *) cpath;
3977 : }
3978 0 : break;
3979 :
3980 200 : case T_NestPath:
3981 : {
3982 : JoinPath *jpath;
3983 :
3984 200 : FLAT_COPY_PATH(jpath, path, NestPath);
3985 :
3986 200 : REPARAMETERIZE_CHILD_PATH(jpath->outerjoinpath);
3987 200 : REPARAMETERIZE_CHILD_PATH(jpath->innerjoinpath);
3988 200 : ADJUST_CHILD_ATTRS(jpath->joinrestrictinfo);
3989 200 : new_path = (Path *) jpath;
3990 : }
3991 200 : break;
3992 :
3993 24 : case T_MergePath:
3994 : {
3995 : JoinPath *jpath;
3996 : MergePath *mpath;
3997 :
3998 24 : FLAT_COPY_PATH(mpath, path, MergePath);
3999 :
4000 24 : jpath = (JoinPath *) mpath;
4001 24 : REPARAMETERIZE_CHILD_PATH(jpath->outerjoinpath);
4002 24 : REPARAMETERIZE_CHILD_PATH(jpath->innerjoinpath);
4003 24 : ADJUST_CHILD_ATTRS(jpath->joinrestrictinfo);
4004 24 : ADJUST_CHILD_ATTRS(mpath->path_mergeclauses);
4005 24 : new_path = (Path *) mpath;
4006 : }
4007 24 : break;
4008 :
4009 112 : case T_HashPath:
4010 : {
4011 : JoinPath *jpath;
4012 : HashPath *hpath;
4013 :
4014 112 : FLAT_COPY_PATH(hpath, path, HashPath);
4015 :
4016 112 : jpath = (JoinPath *) hpath;
4017 112 : REPARAMETERIZE_CHILD_PATH(jpath->outerjoinpath);
4018 112 : REPARAMETERIZE_CHILD_PATH(jpath->innerjoinpath);
4019 112 : ADJUST_CHILD_ATTRS(jpath->joinrestrictinfo);
4020 112 : ADJUST_CHILD_ATTRS(hpath->path_hashclauses);
4021 112 : new_path = (Path *) hpath;
4022 : }
4023 112 : break;
4024 :
4025 80 : case T_AppendPath:
4026 : {
4027 : AppendPath *apath;
4028 :
4029 80 : FLAT_COPY_PATH(apath, path, AppendPath);
4030 80 : REPARAMETERIZE_CHILD_PATH_LIST(apath->subpaths);
4031 80 : new_path = (Path *) apath;
4032 : }
4033 80 : break;
4034 :
4035 0 : case T_MergeAppendPath:
4036 : {
4037 : MergeAppendPath *mapath;
4038 :
4039 0 : FLAT_COPY_PATH(mapath, path, MergeAppendPath);
4040 0 : REPARAMETERIZE_CHILD_PATH_LIST(mapath->subpaths);
4041 0 : new_path = (Path *) mapath;
4042 : }
4043 0 : break;
4044 :
4045 0 : case T_MaterialPath:
4046 : {
4047 : MaterialPath *mpath;
4048 :
4049 0 : FLAT_COPY_PATH(mpath, path, MaterialPath);
4050 0 : REPARAMETERIZE_CHILD_PATH(mpath->subpath);
4051 0 : new_path = (Path *) mpath;
4052 : }
4053 0 : break;
4054 :
4055 0 : case T_UniquePath:
4056 : {
4057 : UniquePath *upath;
4058 :
4059 0 : FLAT_COPY_PATH(upath, path, UniquePath);
4060 0 : REPARAMETERIZE_CHILD_PATH(upath->subpath);
4061 0 : ADJUST_CHILD_ATTRS(upath->uniq_exprs);
4062 0 : new_path = (Path *) upath;
4063 : }
4064 0 : break;
4065 :
4066 0 : case T_GatherPath:
4067 : {
4068 : GatherPath *gpath;
4069 :
4070 0 : FLAT_COPY_PATH(gpath, path, GatherPath);
4071 0 : REPARAMETERIZE_CHILD_PATH(gpath->subpath);
4072 0 : new_path = (Path *) gpath;
4073 : }
4074 0 : break;
4075 :
4076 0 : case T_GatherMergePath:
4077 : {
4078 : GatherMergePath *gmpath;
4079 :
4080 0 : FLAT_COPY_PATH(gmpath, path, GatherMergePath);
4081 0 : REPARAMETERIZE_CHILD_PATH(gmpath->subpath);
4082 0 : new_path = (Path *) gmpath;
4083 : }
4084 0 : break;
4085 :
4086 0 : default:
4087 :
4088 : /* We don't know how to reparameterize this path. */
4089 0 : return NULL;
4090 : }
4091 :
4092 : /*
4093 : * Adjust the parameterization information, which refers to the topmost
4094 : * parent. The topmost parent can be multiple levels away from the given
4095 : * child, hence use multi-level expression adjustment routines.
4096 : */
4097 2748 : old_ppi = new_path->param_info;
4098 : required_outer =
4099 2748 : adjust_child_relids_multilevel(root, old_ppi->ppi_req_outer,
4100 : child_rel->relids,
4101 : child_rel->top_parent_relids);
4102 :
4103 : /* If we already have a PPI for this parameterization, just return it */
4104 2748 : new_ppi = find_param_path_info(new_path->parent, required_outer);
4105 :
4106 : /*
4107 : * If not, build a new one and link it to the list of PPIs. For the same
4108 : * reason as explained in mark_dummy_rel(), allocate new PPI in the same
4109 : * context the given RelOptInfo is in.
4110 : */
4111 2748 : if (new_ppi == NULL)
4112 : {
4113 : MemoryContext oldcontext;
4114 1284 : RelOptInfo *rel = path->parent;
4115 :
4116 1284 : oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
4117 :
4118 1284 : new_ppi = makeNode(ParamPathInfo);
4119 1284 : new_ppi->ppi_req_outer = bms_copy(required_outer);
4120 1284 : new_ppi->ppi_rows = old_ppi->ppi_rows;
4121 1284 : new_ppi->ppi_clauses = old_ppi->ppi_clauses;
4122 1284 : ADJUST_CHILD_ATTRS(new_ppi->ppi_clauses);
4123 1284 : rel->ppilist = lappend(rel->ppilist, new_ppi);
4124 :
4125 1284 : MemoryContextSwitchTo(oldcontext);
4126 : }
4127 2748 : bms_free(required_outer);
4128 :
4129 2748 : new_path->param_info = new_ppi;
4130 :
4131 : /*
4132 : * Adjust the path target if the parent of the outer relation is
4133 : * referenced in the targetlist. This can happen when only the parent of
4134 : * outer relation is laterally referenced in this relation.
4135 : */
4136 2748 : if (bms_overlap(path->parent->lateral_relids,
4137 2748 : child_rel->top_parent_relids))
4138 : {
4139 768 : new_path->pathtarget = copy_pathtarget(new_path->pathtarget);
4140 768 : ADJUST_CHILD_ATTRS(new_path->pathtarget->exprs);
4141 : }
4142 :
4143 2748 : return new_path;
4144 : }
4145 :
4146 : /*
4147 : * reparameterize_pathlist_by_child
4148 : * Helper function to reparameterize a list of paths by given child rel.
4149 : */
4150 : static List *
4151 80 : reparameterize_pathlist_by_child(PlannerInfo *root,
4152 : List *pathlist,
4153 : RelOptInfo *child_rel)
4154 : {
4155 : ListCell *lc;
4156 80 : List *result = NIL;
4157 :
4158 240 : foreach(lc, pathlist)
4159 : {
4160 160 : Path *path = reparameterize_path_by_child(root, lfirst(lc),
4161 : child_rel);
4162 :
4163 160 : if (path == NULL)
4164 : {
4165 0 : list_free(result);
4166 0 : return NIL;
4167 : }
4168 :
4169 160 : result = lappend(result, path);
4170 : }
4171 :
4172 80 : return result;
4173 : }
|
